A library of constructive skeletons for sequential style of parallel programming

ABSTRACT

With the increasing popularity of parallel programming environments such as PC clusters, more and more sequential programmers, with little knowledge about parallel architectures and parallel programming, are hoping to write parallel programs. Numerous attempts have been made to develop high-level parallel programming libraries that use abstraction to hide low-level concerns and reduce difficulties in parallel programming. Among them, libraries of parallel skeletons have emerged as a promising way towards this direction. Unfortunately, these libraries are not well accepted by sequential programmers, because of incomplete elimination of lower-level details, ad-hoc selection of library functions, unsatisfactory performance, or lack of convincing application examples. This paper addresses principle of designing skeleton libraries of parallel programming and reports implementation details and practical applications of a skeleton library SkeTo. The SkeTo library is unique in its feature that it has a solid theoretical foundation based on the theory of Constructive Algorithmics, and is practical to be used to describe various parallel computations in a sequential manner.

REFERENCES

• 1: K. Abrahamson , N. Dadoun , D. G. Kirkpatrick , T. Przytycka, A simple parallel tree contraction algorithm, Journal of Algorithms, v.10 n.2, p.287-302, June 1989 [doi>10.1016/0196-6774(89)90017-5]
• 2: B. Bacci, M. Danelutto, S. Orlando, S. Pelagatti, and M. Vanneschi. P3L: A structured high level programming language and its structured support. Concurrency Practice and Experience, 7(3):225--255, 1995.
• 3: R. Backhouse. An exploration of the Bird-Meertens formalism. In STOP Summer School on Constructive Algorithmics, Ameland, September 1989.
• 4: J.-P. Banâtre and D. L. Métayer, editors. Research Directions in High-Level Parallel Programming Languages, Mont Saint-Michel, France, June 17--19, 1991, Proceedings, volume 574 of Lecture Notes in Computer Science. Springer, 1992.
• 5: A. Benoit and M. Cole. Two fundamental concepts in skeletal parallel programming. In International Conference on Computational Science (2), volume 3515 of Lecture Notes in Computer Science, pages 764--771. Springer-Verlag, 2005.
• 6: A. Benoit, M. Cole, J. Hillston, and S. Gilmore. Flexible skeletal programming with eSkel. In Proc. 11th International Euro-Par Conference (Euro-Par2005), volume 3648 of Lecture Notes in Computer Science, pages 761--770. Springer-Verlag, 2005.
• 7: R. S. Bird, An introduction to the theory of lists, Proceedings of the NATO Advanced Study Institute on Logic of programming and calculi of discrete design, p.5-42, June 1987, Marktoberdorf, Germany
• 8: R. Bird. Constructive functional programming. In STOP Summer School on Constructive Algorithmics, Abeland, 9 1989.
• 9: Richard Bird, Introduction to Functional Programming, Pearson Education, 1998
• 10: Richard Bird , Oege de Moor, Algebra of programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 11: R. S. Bird. Lectures on constructive functional programming. Technical Report Technical Monograph PRG-69, Oxford University Computing Laboratory, 1988.
• 12: H. Bischof, S. Gorlatch, and R. Leshchinskiy. Dattel: A data-parallel C++ template library. Parallel Processing Letters, 13(3):461--472, 2003.
• 13: G. E. Blelloch, Scans as Primitive Parallel Operations, IEEE Transactions on Computers, v.38 n.11, p.1526-1538, November 1989 [doi>10.1109/12.42122 ]
• 14: George Horatiu Botorog , Herbert Kuchen, Skil: An Imperative Language with Algorithmic Skeletons for Efficient Distributed Programming, Proceedings of the High Performance Distributed Computing (HPDC '96), p.243, August 06-09, 1996
• 15: George Horaţiu Botorog , Herbert Kuchen, Efficient high-level parallel programming, Theoretical Computer Science, v.196 n.1-2, p.71-107, April 6, 1998 [doi>10.1016/S0304-3975(97)00196-5 ]
• 16: Shigeru Chiba, A metaobject protocol for C++, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.285-299, October 15-19, 1995, Austin, Texas, United States
• 17: M. Cole. Algorithmic skeletons: a structured approach to the management of parallel computation. Research Monographs in Parallel and Distributed Computing, Pitman, London, 1989.
• 18: M. Cole. Parallel programming, list homomorphisms and the maximum segment sum problems. Report CSR-25-93, Department of Computing Science, The University of Edinburgh, May 1993.
• 19: Murray Cole, Bringing skeletons out of the closet: a pragmatic manifesto for skeletal parallel programming, Parallel Computing, v.30 n.3, p.389-406, March 2004 [doi>10.1016/j.parco.2003.12.002]
• 20: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 21: Marco Danelutto , Fabrizio Pasqualetti , Susanna Pelagatti, Skeletons for Data Parallelism in p3l, Proceedings of the Third International Euro-Par Conference on Parallel Processing, p.619-628, August 26-29, 1997
• 22: John Darlington , A. J. Field , Peter G. Harrison , Paul H. J. Kelly , D. W. N. Sharp , Q. Wu, Parallel Programming Using Skeleton Functions, Proceedings of the 5th International PARLE Conference on Parallel Architectures and Languages Europe, p.146-160, June 14-17, 1993
• 23: John Darlington , Yi-ke Guo , Hing Wing To , Jin Yang, Parallel skeletons for structured composition, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.19-28, July 19-21, 1995, Santa Barbara, California, United States
• 24: Oege De Moor, Categories, relations and dynamic programming, University of Oxford, Oxford, UK, 1991
• 25: K. Emoto, Z. Hu, K. Kakehi, and M. Takeichi. A compositional framework for developing parallel programs on two dimensional arrays. Technical Report METR2005-09, Department of Mathematical Informatics, University of Tokyo, 2005.
• 26: M. Fokkinga. A gentle introduction to category theory --- the calculational approach ---. Technical Report Lecture Notes, Dept. INF, University of Twente, The Netherlands, September 1992.
• 27: Jeremy D. Frens , David S. Wise, QR factorization with Morton-ordered quadtree matrices for memory re-use and parallelism, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 28: Andrew Gill , John Launchbury , Simon L. Peyton Jones, A short cut to deforestation, Proceedings of the conference on Functional programming languages and computer architecture, p.223-232, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165214]
• 29: S. Gorlatch. Constructing list homomorphisms. Technical Report MIP-9512, Fakultät für Mathematik und Informatik, Universität Passau, August 1995.
• 30: Sergei Gorlatch, Systematic Efficient Parallelization of Scan and Other List Homomorphisms, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.401-408, August 26-29, 1996
• 31: Sergei Gorlatch , Christoph Wedler , Christian Lengauer, Optimization Rules for Programming with Collective Operations, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.492-499, April 12-16, 1999
• 32: Zhenjiang Hu , Hideya Iwasaki , Masato Takechi, Formal derivation of efficient parallel programs by construction of list homomorphisms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.444-461, May 1997 [doi>10.1145/256167.256201]
• 33: Zhenjiang Hu , Hideya Iwasaki , Masato Takeichi, An Accumulative Parallel Skeleton for All, Proceedings of the 11th European Symposium on Programming Languages and Systems, p.83-97, April 08-12, 2002
• 34: Zhenjiang Hu , Masato Takeichi , Wei-Ngan Chin, Parallelization in calculational forms, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.316-328, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268972]
• 35: Hideya Iwasaki , Zhenjiang Hu, A new parallel skeleton for general accumulative computations, International Journal of Parallel Programming, v.32 n.5, p.389-414, October 2004 [doi>10.1023/B:IJPP.0000038069.80050.74]
• 36: J. Jeuring. Incremental data compression - extended abstract. In P. Fisher, editor, Proceedings of the Navy Environmental Systems Workshop, 1992.
• 37: J. Jeuring. Theories for Algorithm Calculation. Ph.D thesis, Faculty of Science, Utrecht University, 1993.
• 38: Elizabeth Johnson , Dennis Gannon, HPC++: experiments with the parallel standard template library, Proceedings of the 11th international conference on Supercomputing, p.124-131, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263614]
• 39: Herbert Kuchen, A Skeleton Library, Proceedings of the 8th International Euro-Par Conference on Parallel Processing, p.620-629, August 27-30, 2002
• 40: K. Matsuzaki, Z. Hu, and M. Takeichi. Design and implementation of general tree skeletons. Technical Report METR2005-30, Department of Mathematical Engineering and Information Physics, University of Tokyo, 2005.
• 41: K. Matsuzaki, K. Kakehi, H. Iwasaki, Z. Hu, and Y. Akashi. A fusion-embedded skeleton library. In 10th International Euro-Par Conference (EuroPar 2004), volume 3149 of Lecture Notes in Computer Science, pages 644--653. Springer, August 2004.
• 42: E. W. Mayr and R. Werchner. Optimal tree constraction and term matching on the hypercube and related networks. Algorithmica, 18(3):445--460, 1997.
• 43: Erik Meijer , Maarten Fokkinga , Ross Paterson, Functional programming with bananas, lenses, envelopes and barbed wire, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.124-144, June 1991, Cambridge, Massachusetts, United States
• 44: G. Miller and J. Reif. Parallel tree contraction and its application. In 6th Annual IEEE Syrup, on the Foundations of Comp. Science, pages 478--489, 1985.
• 45: Shin-Cheng Mu , Richard Bird, Theory and applications of inverting functions as folds, Science of Computer Programming, v.51 n.1-2, p.87-116, May 2004 [doi>10.1016/j.scico.2003.09.003]
• 46: Fethi A. Rabhi , Sergei Gorlatch, Patterns and skeletons for parallel and distributed computing, Springer-Verlag, London, 2003
• 47: M. Reid-Miller, G. L. Miller, and F. Modugno. List ranking and parallel tree contraction. In J. H. Reif, editor, Synthesis of Parallel Algorithms, chapter 3, pages 115--194. Morgan Kaufmann Publishers, 1996.
• 48: Isao Sasano , Zhenjiang Hu , Masato Takeichi , Mizuhito Ogawa, Make it practical: a generic linear-time algorithm for solving maximum-weightsum problems, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.137-149, September 2000
• 49: David Skillicorn, Foundations of parallel programming, Cambridge University Press, New York, NY, 1995
• 50: Kai Tan , Duane Szafron , Jonathan Schaeffer , John Anvik , Steve MacDonald, Using generative design patterns to generate parallel code for a distributed memory environment, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 51: David S. Wise, Representing matrices as quadtrees for parallel processors: extended abstract, ACM SIGSAM Bulletin, v.18 n.3, p.24-25, August 1984 [doi>10.1145/1089389.1089398]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Data abstraction
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design