0/1 Knapsack on Hardware: A Complete Solution

We present a memory efficient, practical, systolic, parallel architecture for the complete 0/1 knapsack dynamic programming problem, including backtracking. This problem was intentionally selected because its dynamic dependencies introduce difficulties in hardware implementation. 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 TΘ(𝓃 + 𝒑(С + 𝑾 max )) memory and the run time is Θ(𝓃С/𝒑 + 𝓃log(𝓃/𝒑)). The heart of the architecture is a systolic module to compute the optimal profit for any problem that fits in available hardware resources. We implemented the module using 64 processors on an Alpha Data coprocessor board using a Xilinx VirtexII FPGA(2001 technology). Our implementation showed a factor of 32 improvement on the total execution time over a sequential algorithm running on a 1.5GHz Xeon processor(2000 technology) and a factor of 16 improvement over a 3.2GHz Pentium 4(2004 technology) and a 64 bit 3.4GHz Pentium 4(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.