Design and Implementation of the Systolic Array for Dynamic Programming

David Tien, Jae Lee, Gi Yong Song

Research output: Contribution to journalArticle

5 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

Systolic arrays
Dynamic programming
Computer hardware description languages
Combinatorial optimization
Schematic diagrams
Metals

Cite this

@article{671d8f559a2a4e35b68035d9d7aca6c4,
title = "Design and Implementation of the Systolic Array for Dynamic Programming",
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.",
keywords = "Open access version available",
author = "David Tien and Jae Lee and Song, {Gi Yong}",
note = "Imported on 12 Apr 2017 - DigiTool details were: Journal title (773t) = Journal of signal processing. ISSNs: 1342-6230;",
year = "2003",
language = "English",
volume = "4",
pages = "61--67",
journal = "Journal of signal processing",
issn = "1342-6230",
number = "3",

}

Design and Implementation of the Systolic Array for Dynamic Programming. / Tien, David; Lee, Jae; Song, Gi Yong.

In: Journal of signal processing, Vol. 4, No. 3, 2003, p. 61-67.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Design and Implementation of the Systolic Array for Dynamic Programming

AU - Tien, David

AU - Lee, Jae

AU - Song, Gi Yong

N1 - Imported on 12 Apr 2017 - DigiTool details were: Journal title (773t) = Journal of signal processing. ISSNs: 1342-6230;

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - Open access version available

M3 - Article

VL - 4

SP - 61

EP - 67

JO - Journal of signal processing

JF - Journal of signal processing

SN - 1342-6230

IS - 3

ER -