matmul_multithreaded.c

/*
Pure C code for multi-threaded matrix mutliplication of two
dynamically created and randomly instiated matrices. 
Two different mutli-threading strategies are implemented, along 
with the non-threaded multiplication kernel for comparison.
The functions are timed using system time.

CS347(M): Operating Systems, IIT Bombay (Autumn 2017)
*/

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <string.h>
#include <pthread.h>

double** A; //Input matrix 1
double** B; //Input matrix 2
double** C; //Output matrix

//Sizes of matrices
struct matsize{
    int m; // #rows
    int n; // #columns
};

//1D Index for threads
struct threadData{
    int i; //row
    double** A; //Input matrix 1
    double** B; //Input matrix 2
    double** C; //Output matrix
    struct matsize SA; //Size of A
    struct matsize SB; //Size of B
};

//2D Index for threads
struct threadData2D{
    int i; //row
    int j; //column
    double** A; //Input matrix 1
    double** B; //Input matrix 2
    double** C; //Output matrix
    struct matsize SA; //Size of A
    struct matsize SB; //Size of B
};

//Allocates space and returns a pointer to the matrix of given size
double** createMat(struct matsize A){
    int row = A.m;
    int col = A.n;
    double **arr = (double **)malloc(row * sizeof(double *));
    for(int i = 0; i < row; i++){
        arr[i] = malloc(sizeof(double) * col);
    }
    return arr;
}

//Initializes elements of the matrix to random values
void initMat(double** M, struct matsize S){
    int row = S.m;
    int col = S.n;

    for(int i = 0; i < row; i++){
        for(int j=0; j < col; j++){
            M[i][j] = rand()%100;
        }
    }
}

void noThreadMul(double** A, double** B, double** C, struct matsize SA, struct matsize SB){
    int row = SA.m;
    int col = SB.n;
    int iter = SA.n;

    for(int i=0; i < row; i++){
        for(int j=0; j < col; j++){
            C[i][j] = 0;
            for(int k=0; k < iter; k++){
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

void* rowMul(void* data){
    struct threadData *par = data;
    int row = par->i;
    double** A = par->A;
    double** B = par->B;
    double** C = par->C;
    struct matsize SA = par->SA;
    struct matsize SB = par->SB;

    for(int i=0; i < SA.n; i++){
        C[row][i] = 0;
        for(int j=0; j < SB.m; j++){
            C[row][i] += A[row][j] * B[j][i];
        }
    }
    return 0;
}

void* rowColMul(void* data){
    struct threadData2D *par = data;
    int row = par->i;
    int col = par->j;
    double** A = par->A;
    double** B = par->B;
    double** C = par->C;
    struct matsize SA = par->SA;
    struct matsize SB = par->SB;

    C[row][col] = 0;
    for(int i=0; i < SA.n; i++){
        C[row][col] += A[row][i] * B[i][col];
    }
    return 0;
}

int threadMul(double** A, double** B, double** C, struct matsize SA, struct matsize SB){
    int row = SA.m;
    pthread_t thread[row];
    int errorFlag = 0;
    int tx = 0;
    for(int i = 0;i<row;i++){
        struct threadData *data = (struct threadData *)malloc(sizeof(struct threadData));
        data->i = i; data->A = A; data->B = B; data->C = C;
        data->SA = SA; data->SB = SB;
        if(pthread_create(&thread[i], NULL, rowMul, data)!=0){
            perror("Cannot create thread!");
            errorFlag = 1;
            break;
        }
        free(data);
        //Don't spawn more than 100 threads at a time.
        if((i+1) % 100 == 0){
            for( ;tx < i; tx++){
                pthread_join(thread[tx],NULL);
            }
        }
    }
    for(int j = tx; j < row; j++){
        pthread_join(thread[j],NULL);
    }
    return errorFlag;
}


int threadMul2D(double** A, double** B, double** C, struct matsize SA, struct matsize SB){
    int row = SA.m;
    int col = SB.n;
    pthread_t thread[row * col];

    int errorFlag = 0;
    int index = 0;
    int tx = 0;
    for(int i=0; i < row; i++){
        for(int j=0; j < col; j++){
            struct threadData2D *data = (struct threadData *)malloc(sizeof(struct threadData));
            data->i = i; data->j = j;
            data->A = A; data->B = B; data->C = C;
            data->SA = SA; data->SB = SB;
            if(pthread_create(&thread[index], NULL, rowColMul, data)!=0){
                perror("Cannot create thread!");
                errorFlag = 1;
                break;
            }
            free(data);
            index++;
            //Don't spawn more than 100 threads at a time.
            if((index+1) % 100 == 0){
                for( ;tx < index; tx++){
                    pthread_join(thread[tx],NULL);
                }
            }
        }
    }
    for(int k=tx; k < row*col; k++){
        pthread_join(thread[k],NULL);
    }
    return errorFlag;
}


int main(){
    struct matsize sizeA, sizeB, sizeC;
    int errorFlag;

    sizeA.m = 1000; sizeA.n = 1000;
    sizeB.m = 1000; sizeB.n = 1000;
    if(sizeA.n != sizeB.m){
        printf("Incorrect size of matrices!. Exiting...");
        return -1;
    }
    sizeC.m = sizeA.m; sizeC.n = sizeB.n;

    time_t t;
    srand((unsigned)time(&t));

    A = createMat(sizeA); initMat(A, sizeA);
    B = createMat(sizeB); initMat(B, sizeB);
    C = createMat(sizeC);

    struct timeval stop,start;

    //Multiply without multithreading
    gettimeofday(&start, NULL);
    printf("Without multi-threading:\n");
    noThreadMul(A, B, C, sizeA, sizeB);
    gettimeofday(&stop, NULL);
    printf("Number of threads: 1\n");
    printf("Seconds taken --> %lu\n",stop.tv_sec - start.tv_sec);
    printf("(Micro)Seconds taken --> %lu\n",stop.tv_usec - start.tv_usec);

    //Multiply with a '1D' array of threads
    gettimeofday(&start, NULL);
    printf("With multi-threading:\n");
    errorFlag = threadMul(A, B, C, sizeA, sizeB);
    if(errorFlag == 1){
        printf("Error!\n");
    }
    else{
        gettimeofday(&stop, NULL);
        printf("Number of threads: %i\n", sizeA.m);
        printf("Seconds taken --> %lu\n",stop.tv_sec - start.tv_sec);
        printf("(Micro)Seconds taken --> %lu\n",stop.tv_usec - start.tv_usec);
    }

    //Multiply with a '2D' array of threads
    gettimeofday(&start, NULL);
    printf("With '2D' multi-threading:\n");
    errorFlag = threadMul2D(A, B, C, sizeA, sizeB);
    if(errorFlag == 1){
        printf("Error!\n");
    }
    else{
        gettimeofday(&stop, NULL);
        printf("Number of threads: %i\n", sizeC.m * sizeC.n);
        printf("Seconds taken --> %lu\n",stop.tv_sec - start.tv_sec);
        printf("(Micro)Seconds taken --> %lu\n",stop.tv_usec - start.tv_usec);
    }

    return 0;
}