Pipeline architectures for dynamic programming algorithms (Q1263945)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pipeline architectures for dynamic programming algorithms |
scientific article |
Statements
Pipeline architectures for dynamic programming algorithms (English)
0 references
1990
0 references
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.
0 references
dynamic programming algorithms
0 references
knapsack problem
0 references
pipeline architecture
0 references
complexity
0 references