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 条
[21]   DYNAMIC-PROGRAMMING AND THE BACKPACKERS LINEAR SEARCH PROBLEM [J].
WASHBURN, A .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 1995, 60 (03) :357-365
[22]   DYNAMIC-PROGRAMMING APPROACH FOR NONLINEAR-SYSTEMS [J].
MORENO, L ;
ACOSTA, L ;
HAMILTON, A ;
MENDEZ, JA ;
SANCHEZ, JL ;
PINEIRO, JD .
IEE PROCEEDINGS-CONTROL THEORY AND APPLICATIONS, 1994, 141 (06) :409-417
[23]   IMPLANTATION AND COMPLEXITY OF DYNAMIC-PROGRAMMING TECHNIQUES IN SCHEDULING [J].
DESROCHERS, M ;
SOUMIS, F .
RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH, 1991, 25 (03) :291-310
[24]   EVALUATION OF THE PARAMETERS USED IN ITERATIVE DYNAMIC-PROGRAMMING [J].
BOJKOV, B ;
LUUS, R .
CANADIAN JOURNAL OF CHEMICAL ENGINEERING, 1993, 71 (03) :451-459
[25]   COLOR QUANTIZATION BY DYNAMIC-PROGRAMMING AND PRINCIPAL ANALYSIS [J].
WU, XL .
ACM TRANSACTIONS ON GRAPHICS, 1992, 11 (04) :348-372
[26]   AN INTELLIGENT DYNAMIC-PROGRAMMING FOR UNIT COMMITMENT APPLICATION [J].
OUYANG, Z ;
SHAHIDEHPOUR, SM .
IEEE TRANSACTIONS ON POWER SYSTEMS, 1991, 6 (03) :1203-1209
[27]   DYNAMIC-PROGRAMMING ON A SHARED-MEMORY MULTIPROCESSOR [J].
EDMONDS, P ;
CHU, E ;
GEORGE, A .
PARALLEL COMPUTING, 1993, 19 (01) :9-22
[28]   DYNAMIC-PROGRAMMING OF THE NAVIER-STOKES EQUATIONS [J].
SRITHARAN, SS .
SYSTEMS & CONTROL LETTERS, 1991, 16 (04) :299-307
[29]   MULTISTAGE SAFETY STOCK OPTIMIZATION WITH DYNAMIC-PROGRAMMING [J].
INDERFURTH, K .
OR SPEKTRUM, 1992, 14 (01) :19-32
[30]   MARITIME ROUTING-PROBLEMS AND DYNAMIC-PROGRAMMING [J].
WANG, CT ;
CHRETIENNE, P .
RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH, 1993, 27 (01) :61-76
12345