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

共 15 条

[1]

Bellman R. E., 1957, DYNAMIC PROGRAMMING

[2]

CHEN GH, 1987, THESIS NATIONAL TSIN

[3] DESIGN AND SIMULATION OF A SEQUENTIAL PROLOG MACHINE [J].

CLOCKSIN, WF .

NEW GENERATION COMPUTING, 1985, 3 (01) :101-120

[4]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[5]

Hockney R., 1981, PARALLEL COMPUTERS

[6]

Hwang K., 1984, COMPUTER ARCHITECTUR

[7]

MOLDOVAN DI, 1986, IEEE T COMPUT, V35, P1, DOI 10.1109/TC.1986.1676652

[8]

NEMHAUSER G, 1972, INTEGER PROGRAMMING

[9] DISCRETE DYNAMIC PROGRAMMING AND CAPITAL ALLOCATION [J].

NEMHAUSER, GL ;

ULLMANN, Z .

MANAGEMENT SCIENCE SERIES A-THEORY, 1969, 15 (09) :494-505

[10] EVOLUTION AND IMPLEMENTATIONS OF THE RAP DATABASE MACHINE [J].

OZKARAHAN, EA .

NEW GENERATION COMPUTING, 1985, 3 (03) :237-271

← 1 2 →