Design and Implementation of the Systolic Array for Dynamic Programming

David Tien, Jae Lee, Gi Yong Song

Research output: Contribution to journalArticle

9 Downloads (Pure)

Abstract

We propose a systolic array for dynamic programming which is a technique for solving combinatorial optimization problems. We derive a systolic array for single source shortest path Problem, SA SSSP, and then show that the systolic array serves as dynamic Programming systolic array which is applicable to any dynamic programming problem by developing a systolic array for 0 1 knapsack problem, SA 01KS, with SA SSSP for a basis. In this paper, each of SA SSSP and SA 01KS is modeled and simulated in RT level using VHDL, then synthesized to a schematic and finally implemented to a layout using the cell library based on 0.35 1 poly 4 metal CMOS technology.
Original languageEnglish
Pages (from-to)61-67
Number of pages7
JournalJournal of signal processing
Volume4
Issue number3
Publication statusPublished - 2003

    Fingerprint

Cite this