Pipeline architectures for dynamic programming algorithms (Q1263945)

The paper deals with dynamic programming algorithms for the knapsack problem, and their implementation using a pipeline architecture of processor arrays, queues and memory modules. The classical NP-hard knapsack problem formulated via dynamic programming has the following characteristics: (i) repeating operations at various stages with computational independence between two nonadjacent stages; and for capacity limitation g and stage k, the optimal profit functions f(k,g) can be computed in an increasing order of g. This permits a pipeline architecture consisting of a linear processor array, a queue and memory modules. The related complexity is \(O(nM/q+n)\) where n is the number of stage, M the knapsack capacity and q the pipeline length. Its variant, o/1 knapsack is also discussed with a further speedup.