Traditional (Textbook) algorithm is We have gotten it down to
alg. PInnerProduct. Use PSum
from Parallel Algorithmss. Calculates Inner Product of two vectors
- Span
- #processors
- Work:
alg. Matrix Multiplication.
def MatMult(A, B)
for i=1 to n
for j=1 to n
# calculate inner product
c_ij = 0
for k=1 to n
c_ij += a_ik * b_jk
end for
end for
end for
alg. Parallel Matrix Multiplication.
def PMatMult(A, B)
parallel for i=1 to n
parallel for j=1 to n
c_ij = 0
for k=1 to n
c_ij += a_ik * b_jk
end for
end for
end for
alg. Parallel Recursive Matrix Multiplication. A Divide-and-Conquer algorithm.
Idea:
def PRMatMult(A, B, C)
# base case
if n=1
return a * b
# parallel recursion
spawn PRMatMult(A_11, B_11, D_11)
...# 8 parallel threads
spawn PRMatMult(A_22, B_22, E_22)
sync
# add matricies D and E together
parallel for i=1 to n
parallel for j=1 to n
c_ij = d_ij + e_ij
- Span
- Work