OpenMP parallelization of Memory Efficient Dynamic Programming 0/1 Knapsack Problem

The objective of this assignment is for you to review OpenMP parallelization, implement the memory efficient dynamic programming algorithm, parallelize it in OpenMP and measure its performance. Next, you will implement a multi-pass version. Everything except this is something that you must have done in a previous class such as CS475 (if you took a parallel programming class elsewhere where you did not do this specific set of program, please discuss with the instructor).

• First do PA3 of CS 475 (from Fall 2016). Do not do the coarse grain parallelization or the extra credit (unless you are having too much fun). Be sure to complete the report (or at least gather the performance data and plot the results) since they are going to motivate the next part.
• Next do the multi-pass version as described below.

  You may notice that the value of C greatly influences the performance (the performance is highest when C is smaller than a certain machine-dependent parameter. The trick in this part is to "fill up" the table in (vertical bands) of a certain, width, but to still do this in a memory efficient manner. We call such a section of the table a pass. The problem is that in each row, the last w_i elements just computed are going to be required in the next pass, and must be saved in memory (so the program is not as memory efficient as the original one, but this extra memory is a tunable parameter, although exploring this part is beyond the scope of this assignment).

Submit, using the Checkin tab, your sequential and parallel codes, your time and speedup statistics, and observations in a report (maximum 4 pages).