CS475 Fall 2010 - HW 3
Memory-efficient Knapsack Dynamic Programming and parallelization
Problem Statement
Design and implement a recursive, memory
efcient program to solve the knapsack problem for a knapsack
of capacity C choosing out of N objects. The program should
be memory efficient in the sense that only O(C) memory is saved.
In this assignment you will implement a sequential program
and two parallel versions of your sequential program. Most of your work
may be done on the CS department machines, but your final program should
compile and produce correct results on carver. You report for this
assignment should be short and briefly explain the parallelizations
performed
Divide and Conquer
In this program, you are going to use the
divide-and-conquer approach to compute the entire solution in a memory
efficient manner. Since you never build the entire table there will be no
backtracking, as such, the base case will simply return the solution for a
single element knapsack. The main recursive function that you write will
have three parameters, start, stop and capacity. The
base case (termination of the recursion) should be when you are solving a
knapsack sub problem with a single item (start=stop). In the
general case, you will divide the problem into two roughly equal halves
some mid between stop and start. Then you will
produce the last row of the table for the two halves, saving only the
previous row of the table. You will use these two answer rows to
determine how much capacity should be given to each of the two recursive
calls.
Implement the part that computes the last row of each half in a row-by-row
manner. Thus at any time, there are two arrays, curr
and prev and the two are swapped at the end of each iteration of
the outer loop.
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.
Parallel
Use the previous divide and Conquer program you wrote and
parallelize the function that computes the last row. This would be a
straight forward parallelization. Report the performance obtained as a
function of no of threads and input problem size k2000
Task parallelism
Use the serial divide and Conquer program you
wrote and parallelize using task parallelism feature of OpenMP. This is
similar to the Merge sort task parallelism explored in the lab. Each
subproblem is divided into two rougly equal halves untill the terminaing
condition previouly specified, so this can easily be parallelized using
the task feature.Again report the performance obtained as a function of no
of threads and input problem size k2000
What/When:
- 11:59 pm Sunday, Oct. 23. Code (knapsack.c knapsack_block.c) is due.
This should include your Makefile.
- 11:59 pm, Tuesday, Oct. 25. Lab report is due. Please submit
a pdf file of the report.
- You should use the given Makefile or you can write you own
Makefile but it should be written in a way that typing "make" will compile
the program and produce the executables named
"divide_conquer","divide_conquer_debug",
"parallel","parallel_debug","task_parallel" and "task_parallel_debug" on
Carver.
- Output should be identical to the sequential program. With debug
mode on it should include the solution vector. With debug mode off, it
still calculates the solution vector, but does not print it.
- Here are two larger
problems k1000 k2000
to better measure the performance..
- We will test with large and small problems that are not provided.
Make sure your program works with other problems.
How to Submit:
- You must submit the file from one of the Linux machines, such as crestone
or dmx.
-
All assignments are submitted electronically via the
~cs475/bin/checkin program.
-
You must submit a single tar file containg all of your source code and your
Makefile.
- You must name the tar file as HW3.tgz
- You may resubmit the file as many times as you like. Subsequent
submissions will not overwrite previous submissions.Please do not modify the
filename when resubmitting.The system will take care of it.
-
If you have more than one file for your program, then you should provide a
makefile that will compile all executables. Your executables should contain
names as described previoudly. Any assignment submitted that contains code
that will not compile will receive a 0%.
-
The checkin program should be used as follows:
~cs475/bin/checkin HW3
HW3.tgz
How to tar files:
Good luck and have fun!