Let\'s assume we have an m x n matrix A and we want to multiply it by an n x p m
ID: 3622381 • Letter: L
Question
Let's assume we have an m x n matrix A and we want to multiply it by an n x p matrix B. We can express their product as an m x p matrix denoted by AB(or A dot B). If we assign C = AB and ci,j denotes the entry C at position (i, j), then for each element i and j with 1 <= i <= m and 1 <= j <= p. Now we want to see if we can parallelize the computation of C. Assume that matrices are laid out in memory sequentiall as follows:
a1,1 , a2,1 , a3,1 ... etc.
Assume that we are going to compute C on both a single core shared memory machine and a 4-core shared memory machine. Compute the speedup we would expect to obtain on the 4-core machine, ignoring any memory issues.
Explanation / Answer
Dear, This problem presents an “embarrassingly parallel” computation and asks the student to fi nd the speed-up obtained on a 4-core system. The computations involved are: (m × p × n) multiplications and (m × p × (n - 1)) additions. The multiplications and additions associated with a single element in C are dependent (we cannot start summing up the results of the multiplications for a element until two products are available). So in this question, the speed-up should be very close to 4. Hope this will help you
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.