A SHIFT REGISTER-BASED SYSTOLIC ARRAY FOR THE UNBOUNDED KNAPSACK PROBLEM
Rumen Andonov, Patrice Quinton, Sanjay V. Rajopadhye, Doran K. Wilde · Parallel Processing Letters · 1995
We present a shift register-based systolic array for a class of recurrences, with dynamic dependencies called knapsack problem recurrences. All previous arrays or parallel implementations led to either low efficiency or to complicated control. To the best of our knowledge, the proposed design is the first realistic pure systolic and optimal array for this pseudo-polynomial, NP-hard problem. The key feature of the array is that it requires almost no control circuitry.