HIGH LEVEL PARALLEL SKELETONS FOR DYNAMIC PROGRAMMING

被引：1

作者：

Pelaez, Ignacio ^{[1
]}

Almeida, Francisco ^{[1
]}

Gonzalez, Daniel ^{[1
]}

机构：

[1] Univ La Laguna, Dept Estadist IO & Computac, C Astrofis F Sanchez S-N, San Cristobal la Laguna 38271, Spain

来源：

PARALLEL PROCESSING LETTERS | 2008年 / 18卷 / 01期

关键词：

Algorithmic skeletons; dynamic programming; shared memory; message passing;

D O I：

10.1142/S0129626408003272

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Dynamic Programming is an important problem-solving technique used for solving a wide variety of optimization problems. Dynamic Programming programs are commonly designed as individual applications and software tools are usually tailored to specific classes of recurrences and methodologies. That contrasts with some other algorithmic techniques where a single generic program may solve all the instances. We have developed a general skeleton tool providing support for a wide range of dynamic programming methodologies on different parallel architectures. Genericity, flexibility and efficiency are basic issues of the design strategy. Parallelism is supplied to the user in a transparent manner through a common sequential interface. A set of test problems representative of different classes of Dynamic Programming formulations has been used to validate our skeleton on an IBM-SP.

引用

页码：133 / 147

页数：15

共 21 条

[1] Alba E, 2002, LECT NOTES COMPUT SC, V2400, P927
[2] Optimal orthogonal tiling of 2-D iterations
Andonov, R
Rajopadhye, S
[J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1997, 45 (02) : 159 - 165
[3] Andonov R., 2001, 13 ACM S PAR ALG ARC
[4] PATH PLANNING ON THE WARP COMPUTER - USING A LINEAR SYSTOLIC ARRAY IN DYNAMIC-PROGRAMMING
BITZ, F
KUNG, HT
[J]. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1988, 25 (3-4) : 173 - 188
[5] de Moor O., 1999, P 3 WSEAS INT C CIRC
[6] ECKSTEIN J, 2000, PICO OBJECT ORIENTED
[7] PARALLEL ALGORITHMS FOR DYNAMIC-PROGRAMMING RECURRENCES WITH MORE THAN O(1) DEPENDENCY
GALIL, Z
PARK, K
[J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1994, 21 (02) : 213 - 222
[8] Gibbons A., 1988, EF FICIENT PARALLEL
[9] A COMMON SCHEMA FOR DYNAMIC-PROGRAMMING AND BRANCH AND BOUND ALGORITHMS
HELMAN, P
[J]. JOURNAL OF THE ACM, 1989, 36 (01) : 97 - 128
[10] Ibaraki T, 1988, ENUMERATIVE APPROA 2, V11, P1

← 1 2 3 →