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 language | English (US) |
|---|---|
| Pages (from-to) | 1382-1387 |
| Number of pages | 6 |
| Journal | Proceedings - IEEE International Symposium on Circuits and Systems |
| Volume | 2 |
| State | Published - Dec 1 1989 |
Fingerprint
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 journal › Article
}
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 -