CS332/Programming Project/Spring 2007

CS332/Principles of Operating Systems/Spring 2007/Programming Project: Matrix Multiplication via a Multi-Threaded Program

The problem

Use pthreads to implement matrix multiplication (of 4x4 integer matrices). (This is the Project in Chapter 4 of Silberschatz, Galvin, and Gagne, pp. 149-151).

Matrix multiplication

A n-by-m matrix is a 2-dimensional array of numbers, with n rows and m columns. If A is an n-by-m matrix, and B is an m-by-p matrix, then we can take the matrix product C=AB. C is then an n-by-p matrix. The entries of C are sums of products of entries of A and B. In particular, the entry C[i][j] (row i and column j) is given by the formula

C[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][m-1]*B[m-1][j]

Program requirements

Your program should run on pegasus.
Your program should implement the case of multiplying two 4-by-4 matrices (so n=m=p=4) by computing each of the 16=4*4 entries of the product C in a separate thread.
Your program should have the following global variables (so that they are shared by all threads):
```
const int dim = 4;
int A[dim][dim];
int B[dim][dim];
int C[dim][dim];
```
In all relevant loops, you should use the constant dim instead of 4. This makes it easy to change your program to multiply dim-by-dim for different values of dim.
You should allow the user to enter the entries of the matrices A and B, by implementing a function similar to
```
void matrix_input(int mat[][dim], char* name)
```
Your program should include a function such as
```
void matrix_print(int mat[][dim])
```
to print each matrix in a rectangular form. Your program should output several lines explaining the computation, in a form similar to
```
The matrix product of A and B is C.
```

How to do it

The program vector-add.cpp, which we discussed in class, provides a model for much of the threading issues you will face in coding the project. Also, the discussion of the project in Silberschatz et al, Chapter 4, should also be useful.
Recall that the pthread_create function requires as a parameter a function such as f of the form void* f(void*). In order to pass data into such an f, there must be a single pointer (automatically cast to type void*) to be passed in. In the case of matrix multiplication, however, two pieces of data (representing the row i and the column j of the product matrix C) must be passed in (since there is to be one thread for each entry C[i][j]). Use a struct, as on page 150 of Silberschatz, et al, in order to package the i and j into a single variable.
Your program (the main thread) should wait for all the other threads to complete. This should be accomplished by using the pthread_join function, as on page 151 of Silberschatz, et al.
Each thread should have it own thread id, declared as in
```
pthread_t tid[dim][dim];
```
When compiling your program on pegasus, remember to use the format
```
g++ myprogram.cpp -lpthread
```
and to include the line
```
#include<pthread.h>
```
in the introductory section of your program.

To turn in your solution

You should email me your file as an attachment to my pegasus email address
```
loftin@pegasus.rutgers.edu
```
by midnight on the due date, Monday, March 5.

A sample output of my solution

Input the 16 entries of the 4 x 4 matrix A: 1 2 3 4 0 -1 -2 -3 
7 8 -1 1 
5 10 -7 3
Input the 16 entries of the 4 x 4 matrix B: 9 1 0 0 
5 7 -5 -7
0 0 2 2
8 1 4 5
The matrix product of
  1   2   3   4 
  0  -1  -2  -3 
  7   8  -1   1 
  5  10  -7   3 
and
  9   1   0   0 
  5   7  -5  -7 
  0   0   2   2 
  8   1   4   5 
is
 51  19  12  12 
-29 -10 -11 -12 
111  64 -38 -53 
119  78 -52 -69

How to run my solution

At the pegasus prompt, type

~loftin/public_html/op/project/solution