Description
Part A. Processes (Mutrix-Vector Multiplication)
In this project, you will develop a multi-process application that will perform
matrix-vector multiplication for large matrices and vectors. More precisely, the
application will multiply an nxn matrix M with a vector v of size n. For matrix M, the
element in row i and column j is denoted as mij. For vector v, jth element is denoted
as vj. Then the matrix-vector product is the vector x of length n, whose ith element xi
is given by:
�! = �!”�!
!
!!!
The matrix M information is stored in an input text file (ascii). The vector v
information is also stored in an input text file (ascii). We assume that the row-column
coordinates of each matrix element is also is stored in the file. Hence for each nonzero matrix value we store a triple (i, j,mij) in a line of the matrixfile. The line format
is:
For exampe, for row 3, column 13, and the corresponding value 2, the line will
be:
3 13 2
We assume the position of element vj in the vector v is also stored together with the
value as a 2-tuple (j, vj) in a line of the vectorfile. The line format will be:
For example, if the 5th element of vector v has value 10, we will store:
5 10
For vector v, information about zero-valued entries will be stored in the input
file as well. But for matrix, we do not store information about zero-valued entries in
the input file.
You will develop a multi-process program called mv that will do the matrixvector multiplication in the following way (for educational purposes). It will take the
following parameters.
mv matrixfile vectorfile resultfile K
The main process will read the matrixfile (which can be quite large) and will
partition it into K splits (each split will be a file). The partitioning will be very simple.
Assume there are L values (lines) in matrixfile. Then the first split will contain the
first s = ceiling(L/K) values from the matrixfile, the next split will contain the next s
values, and so on. The last split may contain less than s, which is fine. The number of
2
values L in the file can be obtained by first reading the file from beginning to end in
the main process before generating the splits (yes this is not efficient, but for this
project it is fine).
After generating the split files, the main process will create K child processes
to process (map) the split files. These child processes will be called as mapper
processes (mappers). Each mapper process will process another split file. Mapper
processes will run and process their splits concurrently.
The processing of a split file in a mapper process will be as follows. The
mapper process will first read the whole vectorfile and put the vector values into an
array in main memory. If the vector is of size n, the array size will be n. Then the
mapper will start reading its split file one value at a time (one line at a time). The
value will be multiplied by the corresponding element in vector v and the result will
be added into the corresponding entry in a (partial) result array. If, for example, the
triple read from a line is (i, j, mij), then mij will be multiplied by vj and the
multiplication result will be added to the value at entry i of the partial result array.
Each line of the split file will be read and processed as described. In this way, the
mapper will create a partial result for the multiplication. After mapper has finished
with processing its split file, it will write out the partial result array into an
intermediate output file, one result per line in the following format:
When all mappers finish, a reducer process (another child) will be started by
the main process. The reducer process will open and read and process the
intermediate files produced by the mappers. It will read the intermediate files and will
sum up the respective values corresponding to the same vector index. At the end, the
result vector will be obtained (after processing all input files). The result vector will
be printed out to the resultfile in sorted order with respect to row numbers. The line
format for the resultfile will be:
Let us consider an example. Assume we have a 6×6 matix and a vector of size
6, as follows.
Matrix M
1 2 3 4 5 6
1 1 0 3 0 2 2
2 5 0 0 1 0 4
3 4 3 0 2 0 0
4 0 2 3 5 4 1
5 2 1 1 0 0 2
6 0 3 4 2 1 0
Vector v
1 2
2 1
3 0
4 3
5 0
6 1
Assume there are 2 mappers. The first mapper will read the first 12 lines and
the second mapper will read the remaining 11 lines. The figure below shows the
results (intermediate files) produced by mapper 1 and mapper 2. Reducer will read
the intermediate files and will aggregate the values corresponding to the same row
numbers, and finally will generate the resultfile as shown below. In example below,
(4, 17) from intermediate file 1 and (4, 1) from intermediate file 2 are aggregated to
be (4, 18). The figure below is also an example for the content format of the files.
3
Part B. IPC (with pipes)
Implement the same program this time using pipes instread of use of
intermediate files between mapper processes and reducer process. The name of the
program will be mvp. If there are K mappers, then there will K pipes created. Each
pipe will be used for sending data from a mapper process to the reducer process. Each
mapper will put data in a different pipe. Reducer process will get data from all pipes.
Part C. Threads
Implement the same program using threads this time. The name of the
program will be mvt. There will be K mapper threads and 1 reducer thread created.
Global variables (structures like arrays or linked lists) will be used to pass
information between mapper threads and the reducer thread.
Part D: Experiments
Do some timing experiments to measure the running time (turnaround time) of
the 3 programs for various values of inputs. Try to draw some conclusion.
Submission
Put all your files into a project directory named with your ID (one of the IDs
of team members), tar the directory (using tar xvf), zip it (using gzip) and upload it
to Moodle. For example, a student with ID 20140013 will create a directory named
20140013, will put the files there, tar and gzip the directory and upload the file. The
uploaded file will be 20140013.tar.gz. Include a README.txt file as part of your
upload. It will have the names and IDs of group members, at least. Include also a
4
Makefile to compile your programs. We want to type just make and obtain the
executables. Do not forget to put your report (PDF form) into your project directory.
Additional Information and Clarifications
• Maximum value of K is 10.
• Maximum value of n is 10000.
• The matrix information in the matrix file does not have to be order. For example,
the information for row 2 can be earlier then for row 1, or the information for an
entry (x, 3) can be earlier than an entry (x, 2).
• The project is to teach processes, IPC, and threads. We would normally not write
this program the way descibed for a single compute node. For cluster computing,
however, multiple processes running in different nodes (computers of the cluster)
can be used to do fast matrix multiplication for very large sparse matrices (n in the
order of 10^9 or 10^12).
