Knapsack on VLSI: From algorithm to optimal circuit

Rumen Andonov

doi:10.1109/71.595572

Knapsack on VLSI: From algorithm to optimal circuit

1997-06-01

7

PRE

AI

DOI：10.1109/71.595572

Original

Original request for help

Save

Abstract

En 中文

We present a parallel solution to the unbounded knapsack problem on a linear systolic array. It achieves optimal speedup for this well-known, NP-hard problem on a model of computation that is weaker than the PRAM. Our array is correct by construction, as it is formally derived by transforming a recurrence equation specifying the algorithm. This recurrence has dynamic dependencies, a property that puts it beyond the scope of previous methods for automatic systolic synthesis. Our derivation thus serves as a case study. We generalize the technique and propose a systematic method for deriving systolic arrays by nonlinear transformations of recurrences. We give sufficient conditions that the transformations must satisfy, thus extending systolic synthesis methods. We address a number of pragmatic considerations: implementing the array on only a fixed number of PEs, simplifying the control to just two counters and a few latches, and loading the coefficients so that successive problems can be pipelined without any loss of throughput. Using a register level model of VLSI, we formulate a nonlinear optimization problem to minimize the expected running time of the array. The analytical solution of this problem allows us to choose the memory size of each PE in an optimal manner.

Keywords:

application specific VLSI design

systolic arrays

unbounded knapsack problem

space-time transformations

recurrence equations

dynamic dependencies

nonlinear discrete optimization

correctness preserving transformations

Knapsack on VLSI: From algorithm to optimal circuit

Abstract

AI Summary

Journal

Organization