G.M. Megson
X. Chen
University of Newcastle upon Tyne. 1994
The emphasis in this paper is on the formal derivation of regular arrays for the so-called Knapsack problem. Both 2-D and 1-D arrays are derived by applying extensions to standard synthesis methods to cope with run-time dependencies and locally sequential globally parallel mappings onto fixed sized architectures. For the 2-D case we produce arrays with O (bwmax ) and O (mwmax ) cells and computing time b + m - 1 for a Knapsack with m items and capacity b with wmax the maximum weight. In the 1-D case a uni-directional design is produced with a run-time of h (bwmax /(b + wmax ) + 1) + (b + 1) m + 1 steps where h > 0 is the number of processors.