Look-ahead in dynamic programming and quantizer loops

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

The add-compare-select (ACS) loop operation in serial dynamic programming (DP) problems inherently limits the speed or the iteration period. The author shows that the ACS loop operation (although nonlinear) can exploit look-ahead. He uses techniques of look-ahead, decomposition, and incremental computation, and proposes fine-grain pipelined and parallel architectures for area-efficient high-speed VLSI implementation of DP problems. The word-level arithmetic implementation complexity of the architecture is proportional to the cube of the number of states of the DP problem, logarithmic in number of loop pipeline levels, linear in block size, and additive with respect to pipelining and block processing. The data-dependent nature of the quantization operation limits the opportunities to pipeline the quantizer loops. The author proposes an approach to transform the quantizer loop into an equivalent form that can exploit look-ahead. The transformed quantizer loop recursion is shown to be similar to the DP recursion, and variations of the DP processor architectures can be used for high-speed implementation of simple quantizer loops.

Original languageEnglish (US)
Pages (from-to)1382-1387
Number of pages6
JournalProceedings - IEEE International Symposium on Circuits and Systems
Volume2
StatePublished - Dec 1 1989

Fingerprint

Dynamic programming
Pipelines
Parallel architectures
Decomposition
Processing

Cite this

Look-ahead in dynamic programming and quantizer loops. / Parhi, Keshab K.

In: Proceedings - IEEE International Symposium on Circuits and Systems, Vol. 2, 01.12.1989, p. 1382-1387.

Research output: Contribution to journalArticle

@article{a8ec795672034b069862655311aac39a,
title = "Look-ahead in dynamic programming and quantizer loops",
abstract = "The add-compare-select (ACS) loop operation in serial dynamic programming (DP) problems inherently limits the speed or the iteration period. The author shows that the ACS loop operation (although nonlinear) can exploit look-ahead. He uses techniques of look-ahead, decomposition, and incremental computation, and proposes fine-grain pipelined and parallel architectures for area-efficient high-speed VLSI implementation of DP problems. The word-level arithmetic implementation complexity of the architecture is proportional to the cube of the number of states of the DP problem, logarithmic in number of loop pipeline levels, linear in block size, and additive with respect to pipelining and block processing. The data-dependent nature of the quantization operation limits the opportunities to pipeline the quantizer loops. The author proposes an approach to transform the quantizer loop into an equivalent form that can exploit look-ahead. The transformed quantizer loop recursion is shown to be similar to the DP recursion, and variations of the DP processor architectures can be used for high-speed implementation of simple quantizer loops.",
author = "Parhi, {Keshab K}",
year = "1989",
month = "12",
day = "1",
language = "English (US)",
volume = "2",
pages = "1382--1387",
journal = "Proceedings - IEEE International Symposium on Circuits and Systems",
issn = "0271-4310",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Look-ahead in dynamic programming and quantizer loops

AU - Parhi, Keshab K

PY - 1989/12/1

Y1 - 1989/12/1

N2 - The add-compare-select (ACS) loop operation in serial dynamic programming (DP) problems inherently limits the speed or the iteration period. The author shows that the ACS loop operation (although nonlinear) can exploit look-ahead. He uses techniques of look-ahead, decomposition, and incremental computation, and proposes fine-grain pipelined and parallel architectures for area-efficient high-speed VLSI implementation of DP problems. The word-level arithmetic implementation complexity of the architecture is proportional to the cube of the number of states of the DP problem, logarithmic in number of loop pipeline levels, linear in block size, and additive with respect to pipelining and block processing. The data-dependent nature of the quantization operation limits the opportunities to pipeline the quantizer loops. The author proposes an approach to transform the quantizer loop into an equivalent form that can exploit look-ahead. The transformed quantizer loop recursion is shown to be similar to the DP recursion, and variations of the DP processor architectures can be used for high-speed implementation of simple quantizer loops.

AB - The add-compare-select (ACS) loop operation in serial dynamic programming (DP) problems inherently limits the speed or the iteration period. The author shows that the ACS loop operation (although nonlinear) can exploit look-ahead. He uses techniques of look-ahead, decomposition, and incremental computation, and proposes fine-grain pipelined and parallel architectures for area-efficient high-speed VLSI implementation of DP problems. The word-level arithmetic implementation complexity of the architecture is proportional to the cube of the number of states of the DP problem, logarithmic in number of loop pipeline levels, linear in block size, and additive with respect to pipelining and block processing. The data-dependent nature of the quantization operation limits the opportunities to pipeline the quantizer loops. The author proposes an approach to transform the quantizer loop into an equivalent form that can exploit look-ahead. The transformed quantizer loop recursion is shown to be similar to the DP recursion, and variations of the DP processor architectures can be used for high-speed implementation of simple quantizer loops.

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

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

M3 - Article

VL - 2

SP - 1382

EP - 1387

JO - Proceedings - IEEE International Symposium on Circuits and Systems

JF - Proceedings - IEEE International Symposium on Circuits and Systems

SN - 0271-4310

ER -