Description
This assignment is intended to introduce you to the Pthreads library and give you a little more
experience with C. In this assignment you will implement a small multithreaded program for a classic
parallel programming algorithm: matrix product, a.k.a. matrix multiplication. Matrix products are an
extremely common and important numerical operation used in a wide variety of computer science
applications, such as 3D graphics, artificial intelligence, data compression, and cryptography. In this
assignment you’ll focus on just computing a matrix product without any specific application. Starter
code for this assignment is available on the course Canvas page for this assignment.
Implementation Specifications
The provided main.c source file contains a skeleton for the matrix product function you’re to
implement, multithreaded_matrix_product, as well as an example of its invocation in the
main function. You will need to implement your own testing mechanisms.
While matrices are conceptually two-dimensional structures, within this program they are stored as onedimensional arrays in row-major order. For example, imagine a 6-by-4 matrix (6 rows, 4 columns) as
shown below. This matrix is stored in an array of 24 elements. The first four elements of the array hold
the first row of matrix elements, the second four elements hold the second row of matrix elements, and
so on.
A 6-by-4 matrix:
The matrix’s array representation:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
int * multithreaded_matrix_product(const int A[], const int B[],
int r, int s, int t)
This function should return a new, dynamically allocated matrix that is the product of matrices A and B
(in that order, remember that the matrix product is not commutative). The product will be referred to as
matrix C hereafter. A is an r-by-s matrix and B is an s-by-t matrix, thus C will be an r-by-t matrix.
Calculation of the product should utilize four threads, theoretically improving the speed of the
multiplication by up to a factor of four. Each element of matrix C is the dot product of a row of matrix A
and a column of matrix B. The traditional way to split this work among multiple threads is to partition
the elements of C and make each thread responsible for computing a different subset of the partition.
For example, using four threads the most straightforward ways to partition the elements of C are by
quadrant (a) or by row, either in blocks (b) or interleaved (c). When the width and/or height of C is not
evenly divisible some threads may do slightly more work than others.
One of the major advantages of these forms of partitioning is that there is no problematic data
contention. While multiple threads will read the same data from matrices A and B, each element of
matrix C is written by only one thread and there are no race conditions. Consequently, no thread
synchronization is needed. Calculation of the matrix product is complete when all four threads
terminate.
Deliverables
The following items should be submitted to the instructor. Failure to correctly submit assignment files
will result in a 10% grade penalty.
1) The completed main.c source file.
2) Any new supporting files, e.g., additional source code, needed by main.c.
Do not include any extraneous files, such as Eclipse IDE files, object files, or subversion files.
c1,1 c1,2 c1,3 c1,4 c1,5 c1,6 c1,7 c1,8 c1,9 c1,10 c1,11 c1,12
c2,1 c2,2 c2,3 c2,4 c2,5 c2,6 c2,7 c2,8 c2,9 c2,10 c2,11 c2,12
c3,1 c3,2 c3,3 c3,4 c3,5 c3,6 c3,7 c3,8 c3,9 c3,10 c3,11 c3,12
c4,1 c4,2 c4,3 c4,4 c4,5 c4,6 c4,7 c4,8 c4,9 c4,10 c4,11 c4,12
c5,1 c5,2 c5,3 c5,4 c5,5 c5,6 c5,7 c5,8 c5,9 c5,10 c5,11 c5,12
c6,1 c6,2 c6,3 c6,4 c6,5 c6,6 c6,7 c6,8 c6,9 c6,10 c6,11 c6,12
c7,1 c7,2 c7,3 c7,4 c7,5 c7,6 c7,7 c7,8 c7,9 c7,10 c7,11 c7,12
c8,1 c8,2 c8,3 c8,4 c8,5 c8,6 c8,7 c8,8 c8,9 c8,10 c8,11 c8,12
c9,1 c9,2 c9,3 c9,4 c9,5 c9,6 c9,7 c9,8 c9,9 c9,10 c9,11 c9,12
c10,1 c10,2 c10,3 c10,4 c10,5 c10,6 c10,7 c10,8 c10,9 c10,10 c10,11 c10,12
c11,1 c11,2 c11,3 c11,4 c11,5 c11,6 c11,7 c11,8 c11,9 c11,10 c11,11 c11,12
c12,1 c12,2 c12,3 c12,4 c12,5 c12,6 c12,7 c12,8 c12,9 c12,10 c12,11 c12,12
(a)
c1,1 c1,2 c1,3 c1,4 c1,5 c1,6 c1,7 c1,8 c1,9 c1,10 c1,11 c1,12
c2,1 c2,2 c2,3 c2,4 c2,5 c2,6 c2,7 c2,8 c2,9 c2,10 c2,11 c2,12
c3,1 c3,2 c3,3 c3,4 c3,5 c3,6 c3,7 c3,8 c3,9 c3,10 c3,11 c3,12
c4,1 c4,2 c4,3 c4,4 c4,5 c4,6 c4,7 c4,8 c4,9 c4,10 c4,11 c4,12
c5,1 c5,2 c5,3 c5,4 c5,5 c5,6 c5,7 c5,8 c5,9 c5,10 c5,11 c5,12
c6,1 c6,2 c6,3 c6,4 c6,5 c6,6 c6,7 c6,8 c6,9 c6,10 c6,11 c6,12
c7,1 c7,2 c7,3 c7,4 c7,5 c7,6 c7,7 c7,8 c7,9 c7,10 c7,11 c7,12
c8,1 c8,2 c8,3 c8,4 c8,5 c8,6 c8,7 c8,8 c8,9 c8,10 c8,11 c8,12
c9,1 c9,2 c9,3 c9,4 c9,5 c9,6 c9,7 c9,8 c9,9 c9,10 c9,11 c9,12
c10,1 c10,2 c10,3 c10,4 c10,5 c10,6 c10,7 c10,8 c10,9 c10,10 c10,11 c10,12
c11,1 c11,2 c11,3 c11,4 c11,5 c11,6 c11,7 c11,8 c11,9 c11,10 c11,11 c11,12
c12,1 c12,2 c12,3 c12,4 c12,5 c12,6 c12,7 c12,8 c12,9 c12,10 c12,11 c12,12
(b)
c1,1 c1,2 c1,3 c1,4 c1,5 c1,6 c1,7 c1,8 c1,9 c1,10 c1,11 c1,12
c2,1 c2,2 c2,3 c2,4 c2,5 c2,6 c2,7 c2,8 c2,9 c2,10 c2,11 c2,12
c3,1 c3,2 c3,3 c3,4 c3,5 c3,6 c3,7 c3,8 c3,9 c3,10 c3,11 c3,12
c4,1 c4,2 c4,3 c4,4 c4,5 c4,6 c4,7 c4,8 c4,9 c4,10 c4,11 c4,12
c5,1 c5,2 c5,3 c5,4 c5,5 c5,6 c5,7 c5,8 c5,9 c5,10 c5,11 c5,12
c6,1 c6,2 c6,3 c6,4 c6,5 c6,6 c6,7 c6,8 c6,9 c6,10 c6,11 c6,12
c7,1 c7,2 c7,3 c7,4 c7,5 c7,6 c7,7 c7,8 c7,9 c7,10 c7,11 c7,12
c8,1 c8,2 c8,3 c8,4 c8,5 c8,6 c8,7 c8,8 c8,9 c8,10 c8,11 c8,12
c9,1 c9,2 c9,3 c9,4 c9,5 c9,6 c9,7 c9,8 c9,9 c9,10 c9,11 c9,12
c10,1 c10,2 c10,3 c10,4 c10,5 c10,6 c10,7 c10,8 c10,9 c10,10 c10,11 c10,12
c11,1 c11,2 c11,3 c11,4 c11,5 c11,6 c11,7 c11,8 c11,9 c11,10 c11,11 c11,12
c12,1 c12,2 c12,3 c12,4 c12,5 c12,6 c12,7 c12,8 c12,9 c12,10 c12,11 c12,12
(c)
