1-4244-1027-4/07/$25.00 ©2007 IEEE 0/1 Knapsack on Hardware: A Complete Solution

We present a memory efficient, practical, systolic, par-allel architecture for the complete 0/1 knapsack dynamic programming problem, including backtracking. This prob-lem was intentionally selected because its dynamic de-pendencies introduce difficulties in hardware implementa-tion. The architecture uses a divide-and-conquer technique that results in a pseudo-linear memory requirement. This memory reduction comes in exchange for a factor of two slowdown due to redundant computation. The architecture uses Θ(n + p(C + Wmax)) memory and the run time is Θ(nC/p + nlog(n/p)). The heart of the architecture is a systolic module to compute the optimal profit for any prob-lem that fits in available hardware resources. We imple-mented the module using 64 processors on an Alpha Data coprocessor board using a Xilinx VirtexII FPGA(2001 tech-nology). Our implementation showed a factor of 32 im-provement on the total execution time over a sequential al-gorithm running on a 1.5GHz Xeon processor(2000 tech-nology) and a factor of 16 improvement over a 3.2 GHz Pentium4(2004 technology) and a 64 bit 3.4GHz Pentium4 (2006 technology). We measured complete wall-clock time, including the time to download the problem to the board, but not the time to download the bit stream to the FPGA.