Question

Multiplication of Matrix is one of the tasks that takes time to compute. Note that the time complexity of multiplying two square matrix is o(n^3) using the nested loops method, and Strassen algorithm improves it to O(n^2.8074). Multi-threading can be used to further enhance this.

Using the matrices below, write

(a) a serial program (the normal nested loops method) to perform the multiplication.

(b) a multithreaded program using pthreads to perform this computation.

(c) compare the execution times of (a) and (b) in a table.

Answer 1

Solution

#include<stdio.h>
#include<pthread.h>
#include<time.h>
#include<stdlib.h>
#define SIZE 12
#define FACTOR 4
struct xy {
int x,y;
};
int a[SIZE][SIZE],b[SIZE][SIZE],ans2[SIZE][SIZE];
void *calculate(void *arg) {
int i,j,k,t=0;
struct xy *c = arg;
int x=(c->x),y=(c->y);

for(j=0;j<(SIZE/FACTOR);j++) {
for(k=0;k<(SIZE/FACTOR);k++) {
t=0;
for(i=0;i<SIZE;i++) {
t+=a[x+j][i]*b[i][y+k];

}
ans2[x+j][y+k]=t;
}
}
}
void main() {
int ans1[SIZE][SIZE],i,j,t,k;
for(i=0;i<SIZE;i++) {
for(j=0;j<SIZE;j++) {
a[i][j]=1;
b[i][j]=1;
}
}
clock_t start,end;
double t1,t2;

// (a). Multiplication of matrix using normal sequential execution
start=clock();
for(i=0;i<SIZE;i++) {
for(j=0;j<SIZE;j++) {
t=0;
for(k=0;k<SIZE;k++) {
t+=a[i][k]*b[k][j];
}
ans1[i][j]=t;
}
}
end=clock();
// (b). Multiplication of matrix using multithreading
t1=(double)(end-start)/CLOCKS_PER_SEC;
start=clock();
int sub_size=(int)(SIZE/FACTOR);
pthread_t threads[FACTOR*FACTOR];
struct xy coords[FACTOR*FACTOR];
k=0;
for(i=0;i<FACTOR;i++) {
for(j=0;j<FACTOR;j++) {
coords[k].x=i*sub_size;
coords[k].y=j*sub_size;
k++;
}
}
for(i=0;i<FACTOR*FACTOR;i++) {
pthread_create(&threads[i],NULL,calculate,&coords[i]);
}
for(i=0;i<FACTOR*FACTOR;i++) {
pthread_join(threads[i],NULL);
}
end=clock();
t2=(double)(end-start)/CLOCKS_PER_SEC;
for(i=0;i<SIZE;i++) {
for(j=0;j<SIZE;j++) {
if(ans1[i][j]!=ans2[i][j]) {
printf("Error in Calculation\n");
return;
}
else {
// printf("%d ",ans1[i][j]);
}
}
printf("\n");
}
// (c). Comparision of execution time of both methods

printf("Normal Execution - %f s...\n",t1);
printf("Threaded Execution - %f s...\n",t2);
}