CS475 Fall 2008 - 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 prrofit 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 that you have
already experimented with in the lab. Your final code should take the
same command line arguments and follow the same output format.
Instead of trying to send 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).
What/When/How to Submit:
- 11:59 pm Saturday, Oct. 25. MPI Programs to be submitted via checkin
as HW3. Here
are Instructions
for turning in your tar file.
- 11:59 pm, Tuesday, Oct. 28. Lab report, and data and scripts to be
turned in via checkin. Please submit a pdf file of the report
to HW3_REPORT, and all others (revised program, data, scripts)
tared into a single file to HW3_PART2.
- 11:59 pm, Thursday, Oct. 30. Revised report after reviewing should
be turned into HW3_REPORT2.
- Makefile should be written in a way that typing "make" will compile
the program and produce an executable named "knapsack".
- 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!