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 $n\times n$-matrix by a $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 $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?