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 条
[41]   A DYNAMIC-PROGRAMMING SOLUTION TO THE N-QUEENS PROBLEM [J].
RIVIN, I ;
ZABIH, R .
INFORMATION PROCESSING LETTERS, 1992, 41 (05) :253-256
[42]   PARALLEL PATTERN-RECOGNITION USING DYNAMIC-PROGRAMMING [J].
BECKA, M ;
THANG, GV .
COMPUTERS AND ARTIFICIAL INTELLIGENCE, 1994, 13 (06) :537-555
[43]   MAXIMUM PRINCIPLE, DYNAMIC-PROGRAMMING, AND THEIR CONNECTION IN DETERMINISTIC CONTROL [J].
ZHOU, XY .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1990, 65 (02) :363-373
[44]   PARALLEL VARIABLE-METRIC DYNAMIC-PROGRAMMING ALGORITHM [J].
BROWNRIGG, RD .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1979, 28 (02) :163-184
[45]   DISPATCH OF DIRECT LOAD CONTROL USING DYNAMIC-PROGRAMMING [J].
HSU, YY ;
SU, CC .
IEEE TRANSACTIONS ON POWER SYSTEMS, 1991, 6 (03) :1056-1061
[46]   DYNAMIC-PROGRAMMING ALIGNMENT OF SEQUENCES REPRESENTING CYCLIC PATTERNS [J].
GREGOR, J ;
THOMASON, MG .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1993, 15 (02) :129-135
[47]   A DYNAMIC-PROGRAMMING APPROACH TO LINE SEGMENT MATCHING IN STEREO VISION [J].
LEE, SH ;
LEOU, JJ .
PATTERN RECOGNITION, 1994, 27 (08) :961-986
[48]   A FULLY-PIPELINED SOLUTIONS CONSTRUCTOR FOR DYNAMIC-PROGRAMMING PROBLEMS [J].
FREDERIC, J .
LECTURE NOTES IN COMPUTER SCIENCE, 1991, 497 :420-430
[49]   Evolutionary algorithms and dynamic programming [J].
Doerr, Benjamin ;
Eremeev, Anton ;
Neumann, Frank ;
Theile, Madeleine ;
Thyssen, Christian .
THEORETICAL COMPUTER SCIENCE, 2011, 412 (43) :6020-6035
[50]   USING DYNAMIC-PROGRAMMING FOR SOLVING VARIATIONAL-PROBLEMS IN VISION [J].
AMINI, AA ;
WEYMOUTH, TE ;
JAIN, RC .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1990, 12 (09) :855-867
12345