1. Introduction
2. Parallelize RowMult
In class we discussed that RowMult
could not be trivially
parallelized with parallel loops. Write a \(O(\log n)\) span, \(O(n)\)
work divide-and-conquer version of RowMult
to multiply one row of an
\(n\times n\)-matrix by a \(n\)-vector. Prove that your algorithm meets the
specified bounds.
3. Sum with parallel for
Write a dynamic multithreaded algorithm to sum the numbers in an array
using only parallel for
, not spawn
. Prove asymptotic upper bounds
for the work and span of your algorithm. For full credit your
algorithm should have span at most \(O((\log n)^2)\). Make sure you
avoid race conditions (and explain why they are avoided); you may use
up to \(O(n)\) extra memory for intermediate results. Don’t use any
extra features from OpenMP, only the basic parallel for
in the
textbook.