Introduction
For general information about assignments in this course, see assignments
Parallelize RowMult
In class we discussed that RowMult
could not be trivially
parallelized with parallel loops. Write a $O(\lg n)$ span, $O(n)$
work divide-and-conquer version of RowMult
to multiply one row of an
@@math:n\times n@@-matrix by a @@math:n@@-vector. Prove that your algorithm meets the
specified bounds.
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 @@math:O(\lg(n)^{2})@@ and work at most
$O(n\lg{}n)$. 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.
Single writer race
Consider the following racy pseudocode from the lectures
x ← spawn foo(x);
y ← bar(x);
sync
return x+y
For at least two distinct (in terms of results) possible execution orders (at the procedure call level), give equivalent non-racy pseudocode.
Is there a non-racy version that has some potential parallelism? If so, does this version match the output of the serialized code? If there is no non-racy version with potential parallelism, why not?