Assignment 4 (June 20)

Your task in this assignment is to parallelize a simple subset sum program, which given a (randomly generated set) of numbers, searches for a subset with maximal sum of their elements not larger than half the sum of all numbers.  You can either use Cilk or Lace.

The sequential implementation uses global arrays 'current' and 'best' to hold the picked elements and best found subset. The first challenge is to localize theses data structure to the working threads in a recursive way. For Cilk leaf coarsening might be necessary. Also having global statistics counters ('recursions' and 'leafs') might need some additional ideas.

Finding sequential optimizations is not necessary, but if you add some to the sequential code, you should also keep (or better port) them to the parallel code.