A Skeleton for Parallel Dynamic Programming
The development of skeleton tools constitutes an alternative to cover the gap between current parallel architectures and sequential programmers. Its contruction involves formal models, paradigms and methologies. Based in the automata theory we have develo
- PDF / 204,287 Bytes
- 11 Pages / 431 x 666 pts Page_size
- 92 Downloads / 298 Views
Abstract. The development of skeleton tools constitutes an alternative to cover the gap between current parallel architectures and sequential programmers. Its contruction involves formal models, paradigms and methologies. Based in the automata theory we have developed a formal model for Parallel Dynamic Programming over pipeline networks. This model makes up a paradigm which is the core of skeleton tools oriented to the Dynamic Programming Technique. Following the methodology coerced by the model, we present a tool that provides the user with the ability to obtain parallel programs adapted to the parallel architecture. The efficiency is contrasted on three current parallel platforms: Cray T3E, IBM SP2 and SG Origin 2000.
1
Introduction
Dynamic programming (DP) is an important problem-solving technique that has widely been used in various fields such as control theory, operations research, biology and computer science. Sequential computation for dynamic programming has been studied extensively. General discrete DP programs viewed as multistage finite automatons with a certain superimposed cost structure were presented in [7]. Parallel dynamic programming algorithms for specific problems and specific recurrence relations have been presented for different architectures [2, 4, 8, 6]. However, few effort has been done for a general parallel dynamic programming formal model. The only proposal for a general parallel DP approach was due to Wah et al. in 1985 [10]. They suggest parallelizations of certain classes of DP formulations using parallel matrix product algorithms. However, the resolution of DP problems through matrix products leads, in general, to inefficient solutions. Neither this approach nor any other, lead to a general tool or skeleton for DP. Following Ibaraki’s [7] discrete DP approach, we extend the sequential model for DP to a parallel model. We propose a general parallel dynamic programming algorithm for pipeline and ring networks for multistage automatons. The parallel algorithm presented constitutes a paradigm to solve DP problems and provides the conceptual framework for the development of skeleton tools. Based in this paradigm, we present a skeletton oriented tool for the implementation of Multistage DP algorithms. The level of this skeleton tool not only simplifies the writing of parallel programs but also the development of the sequential case. P. Amestoy et al. (Eds.): Euro-Par’99, LNCS 1685, pp. 877–887, 1999. c Springer-Verlag Berlin Heidelberg 1999
878
D. Morales et al.
The tool presented derives a parallel DP program from the user specification of a sequential code. The tool manages the optimal mapping of the stages of the associated DP automata in the actual processors, the generation of the corresponding messages and the handle of the involved data structures. To study the performance of our skeleton, experiments were carried out in three different architectures: a distributed memory computer, the IBM-SP2; a distributed-shared memory computer, the Origin 2000 and a distributed memory wi
Data Loading...
