Question

[12:18, 10/2/2020] Mohan Reddy: You are to implement a program for matrix multiplication in C++ without thread AND with thread.
[12:18, 10/2/2020] Mohan Reddy: ou are to implement (M by N matrix) times (N by 1 vector) operation and see how multiple threads can speed up the computation. The resulting vector will be (M by 1 vector).

See the following steps/requirements.

1. Accept M and N as keyboard input.

2. Generate a random (M by N matrix) and a random (N by 1 vector). They are populated with random floating point numbers. Any number range is fine.

3. Compute (M by N matrix) times (N by 1 vector) operations. Measure execution time.

4. Compute (M by N matrix) times (N by 1 vector) operations with threads. Think about how many threads are needed. Use the same matrix and vector from step 3. Measure execution time.

5. Resulting vectors from step 3 and step 4 should match.

6. Print the speedup factor to the screen.

Answer 1

The number of threads required is the number if rows in the resultant vector. Here there are M rows in the resultant vector so there are M threads.

Please find the code for the above question:

#include <bits/stdc++.h>
using namespace std;

//This function generates float random numbers
float floatRand()
{
        return (float(rand()) / (float(RAND_MAX) + 1.0)) *10;
}

//This function do multiplication for thread based matrix multiplication
void *mult(void *arg)
{
        float *data = (float*) arg;
        float k = 0;
        int i = 0;

        int x = data[0];
        for (i = 1; i <= x; i++)
                k += data[i] *data[i + x];

        float *p = (float*) malloc(sizeof(float));
        *p = k;

        //Used to terminate a thread and the return value is passed as a pointer
        pthread_exit(p);
}

//This function is utility function for matrix multiplication using threads
void multiplyWithThread(int M, int N, float **A, vector<float> B, vector<float> &result)
{
        pthread_t * threads;
        threads = (pthread_t*) malloc(M* sizeof(pthread_t));

        int count = 0;
        float *data = NULL;

        for (int i = 0; i < M; i++)
        {

                //storing row and column elements in data  
                data = (float*) malloc((2 *N + 2) *sizeof(float));
                data[0] = N;

                for (int k = 0; k < N; k++)
                        data[k + 1] = A[i][k];

                for (int k = 0; k < N; k++)
                        data[k + N + 1] = B[k];

                //creating threads
                pthread_create(&threads[count++], NULL, mult, (void*)(data));
        }

        for (int i = 0; i < M; i++)
        {
                void *k;
                //Joining all threads and collecting return value  
                pthread_join(threads[i], &k);
                float *p = (float*) k;
                result[i] = *p;
        }
}

//This function is used for simple multiplication
void multiplySimple(int M, int N, float **A, vector<float> B, vector<float> &result)
{

        for (int i = 0; i < M; i++)
        {

                for (int k = 0; k < N; k++)
                {
                        result[i] += A[i][k] *B[k];
                }
        }
}

int main()
{
        int M, N;
        cout << "Please enter the value of M and N" << endl;
        cin >> M >> N;
        float **A;
        A = new float *[M];
        for (int i = 0; i < M; i++)
                A[i] = new float[N];
        vector<float> B;

        //Creating Matrix A
        for (int i = 0; i < M; i++)
        {
                for (int j = 0; j < N; j++)
                {
                        A[i][j] = floatRand();
                }
        }
        //Creating Matrix B
        for (int i = 0; i < N; i++)
        {
                B.push_back(floatRand());
        }

        // Displaying Matrix A
        cout << "Matrix A" << endl;
        for (int i = 0; i < M; i++)
        {
                for (int j = 0; j < N; j++)
                        printf("%f ", A[i][j]);
                printf("\n");
        }
        cout << endl;

        // Displaying Matrix B    
        cout << "Matrix B" << endl;
        for (int i = 0; i < N; i++)
        {
                printf("%f ", B[i]);
                printf("\n");
        }
        cout << endl;

        vector<float> result;
        for (int i = 0; i < M; i++)
        {
                result.push_back(0);
        }
        clock_t tStart = clock();
        multiplySimple(M, N, A, B, result);

        // Displaying resultant Matrix
        cout << "Resultant Matrix" << endl;
        for (int i = 0; i < M; i++)
        {
                printf("%f\n", result[i]);
        }
        cout<<endl;
        printf("Time taken  for simple multiplication: %.10fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC);
        cout<<endl;
        vector<float> result2;
        for (int i = 0; i < M; i++)
        {
                result2.push_back(0);
        }
        tStart = clock();
        multiplyWithThread(M, N, A, B, result2);
        // Displaying resultant Matrix
        cout << "Resultant Matrix" << endl;
        for (int i = 0; i < M; i++)
        {
                printf("%f\n", result2[i]);
        }
        cout<<endl;
        printf("Time taken  for simple multiplication: %.10fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC);

        return 0;
}

On giving the input value of M and N as 5 and 5. We get the below output: