HIGH LEVEL PARALLEL SKELETONS FOR DYNAMIC PROGRAMMING
Abstract
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.
References
-
R. Andonov , Optimal semi-oblique tiling and its application to sequence comparison , 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA) ( 2001 ) . Google Scholar - Journal of Parallel and Distributed Computing 45, 159 (1997), DOI: 10.1006/jpdc.1997.1371. Crossref, ISI, Google Scholar
- Inter. J. Computer Math. 25, 173 (1988), DOI: 10.1080/00207168808803670. Crossref, ISI, Google Scholar
B. Le Cun , Bob++ library illustrated by VRP, European Operational Research Conference (EURO'2001) (2001) p. 157. Google Scholar- Parallel Computing (2000). Google Scholar
-
O. de Moor , Dynamic programming as a software component , Proc. 3rd WSEAS Int. Conf. Circuits, Systems, Communications and Computers , ed.N. Mastorakis ( 1999 ) . Google Scholar - J. Eckstein, C. A. Phillips, and W. E. Hart. PICO: An object-oriented framework for parallel branch and bound. Technical report, RUTCOR, 2000 . Google Scholar
E. Alba , MALLBA: A library of skeletons for combinatorial optimisation (research note), Proceedings of the 8th International Euro-Par Conference2400,LNCS (2002) pp. 927–932. Google Scholar- Journal of Parallel and Distributed Computing 21, 213 (1994), DOI: 10.1006/jpdc.1994.1053. Crossref, ISI, Google Scholar
-
A. Gibbons and W. Rytter , Efficient parallel algorithms ( Cambridge University Press , 1988 ) . Google Scholar - Journal of the ACM 36, 97 (1989), DOI: 10.1145/58562.59304. Crossref, ISI, Google Scholar
- Annals of Operations Research 11, 1 (1988). ISI, Google Scholar
- SIAM Journal in Applied Mathematics 15, 693 (1967), DOI: 10.1137/0115060. Crossref, ISI, Google Scholar
-
V. Kumar , Introduction to Parallel Computing Design and Analysis of Algorithms ( The Benjamin/Cummings Publishing Company, Inc. , 1994 ) . Google Scholar G. Li and B. Wah , Parallel processing of serial dynamic programming programs, Proc. of COMPSAC 85 (1985) pp. 81–89. Google Scholar- P. Lohmander. Deterministic and stochastic dynamic programming. www.sekon.slu.se/~PLO/diskreto/dynp.htm . Google Scholar
- Information Processing Letters 29, 97 (1988), DOI: 10.1016/0020-0190(88)90036-1. Crossref, ISI, Google Scholar
- Wildlife Society Bulletin 23, 738 (1997). ISI, Google Scholar
S. Miguet and Y. Robert , Hypercube and Distributed Computers (1989) pp. 19–33. Google ScholarC. Rodríguez , Parallel algorithms for polyadic problems, Proceedings of the 5th Euromicro Workshop on Parallel and Distributed Processing (1997) pp. 394–400. Google Scholar- Theoretical Computer Science 59, (1988), DOI: 10.1016/0304-3975(88)90147-8. Google Scholar
- Multiprocessing of combinatorial search problems 18, 93 (1985). Google Scholar


