World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on High-Level Parallel Programming and ApplicationsNo Access

HIGH LEVEL PARALLEL SKELETONS FOR DYNAMIC PROGRAMMING

    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 et al. , Optimal semi-oblique tiling and its application to sequence comparison , 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA) ( 2001 ) . Google Scholar
    • R. Andonov and S. Rajopadhye, Journal of Parallel and Distributed Computing 45, 159 (1997), DOI: 10.1006/jpdc.1997.1371. Crossref, ISIGoogle Scholar
    • F. Bitz and H. T. Kung, Inter. J. Computer Math. 25, 173 (1988), DOI: 10.1080/00207168808803670. Crossref, ISIGoogle Scholar
    • B. Le Cun, Bob++ library illustrated by VRP, European Operational Research Conference (EURO'2001) (2001) p. 157. Google Scholar
    • D. Moraleset al., 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. Albaet al., 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
    • Zvi Galil and Kunsoo Park, Journal of Parallel and Distributed Computing 21, 213 (1994), DOI: 10.1006/jpdc.1994.1053. Crossref, ISIGoogle Scholar
    • A.   Gibbons and W.   Rytter , Efficient parallel algorithms ( Cambridge University Press , 1988 ) . Google Scholar
    • P. Helman, Journal of the ACM 36, 97 (1989), DOI: 10.1145/58562.59304. Crossref, ISIGoogle Scholar
    • T. Ibaraki, Annals of Operations Research 11, 1 (1988). ISIGoogle Scholar
    • R. M. Karp and M. Held, SIAM Journal in Applied Mathematics 15, 693 (1967), DOI: 10.1137/0115060. Crossref, ISIGoogle Scholar
    • V.   Kumar et al. , 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
    • B. Louka and M. Tchuente, Information Processing Letters 29, 97 (1988), DOI: 10.1016/0020-0190(88)90036-1. Crossref, ISIGoogle Scholar
    • B. C. Lubow, Wildlife Society Bulletin 23, 738 (1997). ISIGoogle Scholar
    • S. Miguet and Y. Robert, Hypercube and Distributed Computers (1989) pp. 19–33. Google Scholar
    • C. Rodríguezet al., Parallel algorithms for polyadic problems, Proceedings of the 5th Euromicro Workshop on Parallel and Distributed Processing (1997) pp. 394–400. Google Scholar
    • W. Rytter, Theoretical Computer Science 59, (1988), DOI: 10.1016/0304-3975(88)90147-8. Google Scholar
    • B. Wah, G. Li and C. Fen, Multiprocessing of combinatorial search problems 18, 93 (1985). Google Scholar