Parallel Dynamic Programming using Data-Parallel Skeletons
Skeletal parallel programming serves us as a successful method for parallelization. It provides a fixed set of program components called skeletons, each of which has its efficient parallel implementation. Their combination enables users to develop parallel programs without concerning themselves with communication deadlocks. For demostrating the powerfulness of skeletal programming the authors have developed parallelization technique toward one class of optimization problems called maximum marking problems. This can be recognized as one class of dynamic programming. This paper focuses on problems of dynamic programming in general, and examines how the skeletal approache parallelizes problems of dynamic programming.
日本ソフトウェア科学会大会講演論文集 22(0), 313-319, 2005