CS475 Fall 2009 - HW 3
Parallel Dynamic Programming Knapsack Solver
Objectives
To learn data decomposition, point-to-point
communication, and dynamic programming.
Problem Statement
Design, implement, an MPI based parallel
program to determine the optimal profit when filling a knapsack of
capacity C choosing out of N objects. Note that, this
program will eventually become a module in your class project. This
module will be memory efficient in the sense that only O(C) memory
is saved in each processor. Measure and analyze its performance,
and report your findings.
In this homework, you are not going to implement the backtracking part,
nor the part that uses the divide-and-conquer approach to compute the
entire solution in a memory efficient manner. You will implement only the
part that computes the last row of the table, updating in a row-by-row
manner (thus at any time, there are two global arrays, curr
and prev and the two are swapped at the end of each iteration of
the outer loop. The arrays are distributed in a block-wise manner.
Start off with the sequential (rowwise) code provided here, which is a slight modification of the code
which was used in the knapsack lab. Your final code should take the same
command line arguments and follow the same output format.
Instead of trying to send a variable size each time, we suggest
starting
from a simpler but less efficient implementation of sending a fixed size
(either the full block or max of the weights). However, your final version of the
code should implement variable sends efficiently.
What/When/How to Submit:
- 11:59 pm Sunday, Oct. 25. MPI Programs to be submitted via checkin
as HW3. Here
are Instructions
for turning in your tar file. Code can be turned in up until 11:59 pm,
Wednesday, Oct. 29 at a 5% late penalty charge per day.
- 11:59 pm, Tuesday, Oct. 27. Lab report, and data and scripts to be
turned in via checkin. Please submit a pdf file of the report
to HW3_REPORT,
- Makefile should be written in a way that typing "make" will compile
the program and produce an executable named "knapsack" on Bassi. Not
conforming to this specification is one of the major causes for delays in
grading your homeworks. Please make sure your code compiles on Bassi using
the makefile!
- Output should be identical to the sequential program without debug
mode on.
- Larger problems to better measure the parallel performance will be
provided soon. Here are two larger
problems k1000 k2000.
- Don't forget the assumption C/p > maximum weight.
- We do want you to implement the variable size communication in the
end. Keep your working implementation aside so that you can turn in what
works. Also, you may be able to do some interesting analysis by comparing
the performance as you reduce the communication volume.
- We will test with large and small problems that are not provided.
Make sure your program works with other problems.
Good luck and have fun!