GENERATING MESSAGE-PASSING PROGRAMS FROM ABSTRACT SPECIFICATIONS BY PARTIAL EVALUATION
Abstract
This paper demonstrates how parallel programs with message-passing can be generated from abstract specifications embedded in the functional language MetaOCaml. The functional style permits to design parallel programs with a high degree of parameterization, so-called skeletons. Programmers who are unexperienced in parallelism can take such skeletons for a simple and safe generation of parallel applications. Since MetaOCaml also has efficient imperative features and an MPI interface, the entire program can be written in one language, without the need to use a language interface restricting the set of data objects which could be exchanged.
The semantics of abstract specifications is expressed by an interpreter written in MetaOCaml. A cost model is defined by abstract interpretation of the specification. Partial evaluation of the interpreter with a specification, a feature which MetaOCaml provides, yields a parallel program. The partial evaluation process takes time on each MPI process directly before the execution of the application program, exploiting knowledge of the number of processes, the current process identifier and the communication structure. Our example is the specification of a divide-and-conquer skeleton which is used to compute the multiplication of multi-digit numbers using Karatsuba's algorithm.
References
- IEEE Computer 23(12), 25 (1990). Crossref, ISI, Google Scholar
- , Euro-Par 2003: Parallel Processing,
Lecture Notes in Computer Science 2790 , eds.H. Kosch , L. Böszörményi and H. Hellwagner (Springer-Verlag, 2003) pp. 682–693. Crossref, Google Scholar - Communications of the ACM 39(3), 85 (1996). Crossref, ISI, Google Scholar
- SIAM Review 37(2), 151 (1995). Crossref, ISI, Google Scholar
- Higher-Order and Symbolic Computation 12(4), 381 (1999). Crossref, Google Scholar
- K. S. Gatlin and L. Carter. Faster FFTs via architecture-cognizance. In IEEE PACT, pages 249–260, 2000 . Google Scholar
- 26(1), 47 (2004). Google Scholar
- C. A. Herrman, Functional meta-programming in the construction of parallel programs. In S. Gorlatch, editor, 4th International Workshop on "Constructive Methods for Parallel Programming" (CMPP 2004), Stirling (Scotland, UK), pages 3–17 Technical Report of Westfälische Wilhelmas-Universität Münster 2004 . Google Scholar
- , Generative Programming and Component Engineering,
Lecture Notes in Computer Science 2487 , eds.D. Batory , C. Consel and W. Taha (Springer-Verlag, 2002) pp. 1–31. Crossref, Google Scholar - Doklady Akademii Nauk SSSR 145(2), 293 (1962). Google Scholar
-
C. Lengauer (eds.) , Domain-Specific Program Generation ,Lecture Notes in Computer Science 3016 ( Springer-Verlag , 2004 ) . Crossref, Google Scholar - , Euro-Par 2002: Parallel Processing,
Lecture Notes in Computer Science 2400 , eds.B. Monien and R. Feldmann (Springer-Verlag, 2002) pp. 666–673. Crossref, Google Scholar - , Patterns and Skeletons for Parallel and Distributed Computing, eds.
F. A. Rabhi and S. Gorlatch (Springer-Verlag, 2003) pp. 129–153. Crossref, Google Scholar - MPI Forum. MPI-2: Extensions to the Message-Passing Interface. Univ. of Tennessee at Knoxville, 1997. http://www.mpi-forum.org/ . Google Scholar
- , Semantics, Applications, and Implementation of Program Generation (SAIG'01),
Lecture Notes in Computer Science 2196, ed.W. Taha (Springer-Verlag, 2001) pp. 2–44. Crossref, Google Scholar - , Domain-Specific Program Generation,
Lecture Notes in Computer Science 3016, eds.C. Lengauer (Springer-Verlag, 2004) pp. 30–50. Crossref, Google Scholar - http://www.cs.rice.edu/~taha/MetaOCaml/ . Google Scholar
- http://www.infosun.fmi.uni-passau.de/cl/metaprog/ . Google Scholar
- http://caml.inria.fr/ . Google Scholar


