Pipelining in Dynamic Programming Architectures

Research output: Contribution to journalArticle

15 Citations (Scopus)

Abstract

Achieving fine-grain pipelining in forward dynamic programming (DP) architectures is difficult. This correspondence proposes novel computation techniques to achieve fine-grain pipelining in such architectures. We implement the sequential DP algorithm using fewer finer grain pipelined processors, and achieve increased hardware efficiency by using a novel computation sequence. We also use look-ahead computation to obtain a concurrent DP algorithm, and use this in combination with an approprite computation sequence to achieve further pipelining in DP architectures. The finer grain pipelined architectures are mapped to ring and mesh processor arrays, and achieve approximately the same iteration rate as the coarse-grain pipelined architectures, but with use of much less hardware. The design of interleaved architectures using multiple clocks is also outlined.

Original languageEnglish (US)
Pages (from-to)1442-1450
Number of pages9
JournalIEEE Transactions on Signal Processing
Volume39
Issue number6
DOIs
StatePublished - Jan 1 1991

Fingerprint

Dynamic programming
Hardware
Parallel processing systems
Clocks

Cite this

Pipelining in Dynamic Programming Architectures. / Parhi, Keshab K.

In: IEEE Transactions on Signal Processing, Vol. 39, No. 6, 01.01.1991, p. 1442-1450.

Research output: Contribution to journalArticle

@article{ec469acd5c8d4487b73881fc993cf82f,
title = "Pipelining in Dynamic Programming Architectures",
abstract = "Achieving fine-grain pipelining in forward dynamic programming (DP) architectures is difficult. This correspondence proposes novel computation techniques to achieve fine-grain pipelining in such architectures. We implement the sequential DP algorithm using fewer finer grain pipelined processors, and achieve increased hardware efficiency by using a novel computation sequence. We also use look-ahead computation to obtain a concurrent DP algorithm, and use this in combination with an approprite computation sequence to achieve further pipelining in DP architectures. The finer grain pipelined architectures are mapped to ring and mesh processor arrays, and achieve approximately the same iteration rate as the coarse-grain pipelined architectures, but with use of much less hardware. The design of interleaved architectures using multiple clocks is also outlined.",
author = "Parhi, {Keshab K}",
year = "1991",
month = "1",
day = "1",
doi = "10.1109/78.136556",
language = "English (US)",
volume = "39",
pages = "1442--1450",
journal = "IEEE Transactions on Signal Processing",
issn = "1053-587X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "6",

}

TY - JOUR

T1 - Pipelining in Dynamic Programming Architectures

AU - Parhi, Keshab K

PY - 1991/1/1

Y1 - 1991/1/1

N2 - Achieving fine-grain pipelining in forward dynamic programming (DP) architectures is difficult. This correspondence proposes novel computation techniques to achieve fine-grain pipelining in such architectures. We implement the sequential DP algorithm using fewer finer grain pipelined processors, and achieve increased hardware efficiency by using a novel computation sequence. We also use look-ahead computation to obtain a concurrent DP algorithm, and use this in combination with an approprite computation sequence to achieve further pipelining in DP architectures. The finer grain pipelined architectures are mapped to ring and mesh processor arrays, and achieve approximately the same iteration rate as the coarse-grain pipelined architectures, but with use of much less hardware. The design of interleaved architectures using multiple clocks is also outlined.

AB - Achieving fine-grain pipelining in forward dynamic programming (DP) architectures is difficult. This correspondence proposes novel computation techniques to achieve fine-grain pipelining in such architectures. We implement the sequential DP algorithm using fewer finer grain pipelined processors, and achieve increased hardware efficiency by using a novel computation sequence. We also use look-ahead computation to obtain a concurrent DP algorithm, and use this in combination with an approprite computation sequence to achieve further pipelining in DP architectures. The finer grain pipelined architectures are mapped to ring and mesh processor arrays, and achieve approximately the same iteration rate as the coarse-grain pipelined architectures, but with use of much less hardware. The design of interleaved architectures using multiple clocks is also outlined.

UR - http://www.scopus.com/inward/record.url?scp=0026169529&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026169529&partnerID=8YFLogxK

U2 - 10.1109/78.136556

DO - 10.1109/78.136556

M3 - Article

VL - 39

SP - 1442

EP - 1450

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 6

ER -