PIPELINE ARCHITECTURES FOR DYNAMIC-PROGRAMMING ALGORITHMS

被引：15

作者：

CHEN, GH ^{[1
]}

CHERN, MS ^{[1
]}

JANG, JH ^{[1
]}

机构：

[1] NATL TSING HUA UNIV,DEPT IND ENGN,HSINCHU 300,TAIWAN

来源：

PARALLEL COMPUTING | 1990年 / 13卷 / 01期

关键词：

knapsack problems; dynamic programming; Pipelined computation;

D O I：

10.1016/0167-8191(90)90124-R

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Dynamic programming is one of the most powerful approaches to many combinatorial optimization problems. In this paper, we present pipeline architectures for the dynamic programming algorithms for the knapsack problems. They enable us to achieve an optimal speedup using processor arrays, queues, and memory modules. The processor arrays can be regarded as pipelines where the dynamic programming algorithms are implemented through pipelining. © 1990.

引用

页码：111 / 117

页数：7

共 50 条

[1] ALGORITHMS AND ARCHITECTURES FOR DYNAMIC-PROGRAMMING ON MARKOV-CHAINS
BLISS, WG
SCHARF, LL
IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1989, 37 (06): : 900 - 912
[2] PIPELINING IN DYNAMIC-PROGRAMMING ARCHITECTURES
PARHI, KK
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 1991, 39 (06) : 1442 - 1450
[3] PARALLEL DYNAMIC-PROGRAMMING ALGORITHMS
VELDHORST, M
LECTURE NOTES IN COMPUTER SCIENCE, 1986, 237 : 393 - 402
[4] DYNAMIC-PROGRAMMING MODELS AND ALGORITHMS
DREYFUS, S
MANAGEMENT SCIENCE, 1959, 5 (03) : 346 - 346
[5] DYNAMIC-PROGRAMMING ALGORITHMS FOR PICTURE COMPARISON
WATERMAN, MS
ADVANCES IN APPLIED MATHEMATICS, 1985, 6 (01) : 129 - 134
[6] THE CONSTRUCTION OF DISCRETE DYNAMIC-PROGRAMMING ALGORITHMS
HELD, M
KARP, RM
IBM SYSTEMS JOURNAL, 1965, 4 (02) : 136 - 147
[7] SYSTOLIC ALGORITHMS FOR THE DYNAMIC-PROGRAMMING PROBLEM
DHRIF, H
SARKAR, D
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1992, 41 (3-4) : 151 - 163
[8] DYNAMIC-PROGRAMMING ALGORITHMS FOR BIOLOGICAL SEQUENCE COMPARISON
PEARSON, WR
MILLER, W
METHODS IN ENZYMOLOGY, 1992, 210 : 575 - 601
[9] ON THE CONVERGENCE OF STOCHASTIC ITERATIVE DYNAMIC-PROGRAMMING ALGORITHMS
JAAKKOLA, T
JORDAN, MI
SINGH, SP
NEURAL COMPUTATION, 1994, 6 (06) : 1185 - 1201
[10] DYNAMIC-PROGRAMMING ALGORITHMS FOR RESTRICTION MAP COMPARISON
HUANG, XQ
WATERMAN, MS
COMPUTER APPLICATIONS IN THE BIOSCIENCES, 1992, 8 (05): : 511 - 520

← 1 2 3 4 5 →