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.

GENERATING MESSAGE-PASSING PROGRAMS FROM ABSTRACT SPECIFICATIONS BY PARTIAL EVALUATION

    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

    • A. Berlin and D. Weise, IEEE Computer 23(12), 25 (1990). Crossref, ISIGoogle Scholar
    • H. Bischof, S. Gorlatch and E. Kitzelmann, 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. CrossrefGoogle Scholar
    • G. E. Blelloch, Communications of the ACM 39(3), 85 (1996). Crossref, ISIGoogle Scholar
    • J. J. Dongarra and D. W. Walker, SIAM Review 37(2), 151 (1995). Crossref, ISIGoogle Scholar
    • Y. Futamura, Higher-Order and Symbolic Computation 12(4), 381 (1999). CrossrefGoogle Scholar
    • K. S. Gatlin and L. Carter. Faster FFTs via architecture-cognizance. In IEEE PACT, pages 249–260, 2000 . Google Scholar
    • S. Gorlatch,  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
    • N. D. Jones and A. J. Glenstrup, 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. CrossrefGoogle Scholar
    • A. Karatsuba and Y. Ofman, Doklady Akademii Nauk SSSR 145(2), 293 (1962). Google Scholar
    • C.   Lengauer et al. (eds.) , Domain-Specific Program Generation , Lecture Notes in Computer Science 3016 ( Springer-Verlag , 2004 ) . CrossrefGoogle Scholar
    • P. Liniker, O. Beckmann and P. H. J. Kelly, Euro-Par 2002: Parallel Processing, Lecture Notes in Computer Science 2400, eds. B. Monien and R. Feldmann (Springer-Verlag, 2002) pp. 666–673. CrossrefGoogle Scholar
    • G. Michaelson and N. Scaife, Patterns and Skeletons for Parallel and Distributed Computing, eds. F. A. Rabhi and S. Gorlatch (Springer-Verlag, 2003) pp. 129–153. CrossrefGoogle Scholar
    • MPI Forum. MPI-2: Extensions to the Message-Passing Interface. Univ. of Tennessee at Knoxville, 1997. http://www.mpi-forum.org/ . Google Scholar
    • T. Sheard, Semantics, Applications, and Implementation of Program Generation (SAIG'01), Lecture Notes in Computer Science 2196, ed. W. Taha (Springer-Verlag, 2001) pp. 2–44. CrossrefGoogle Scholar
    • W. Taha, Domain-Specific Program Generation, Lecture Notes in Computer Science 3016, eds. C. Lengaueret al. (Springer-Verlag, 2004) pp. 30–50. CrossrefGoogle 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