TOWARDS PARALLEL PROGRAMMING BY TRANSFORMATION: THE FAN SKELETON FRAMEWORKFootnote*

* Parts of this work were presented in the preliminary version at the HiPS workshop of IPPS’99 (Puerto Rico)and at the PaCT’99 conference (St. Petersburg)

References

• Akl , S. G. , The Design and Analysis of Parallel Algorithms. , Prentice-Hall, 1989 .
   Google Scholar
• Aldinucci , M. , Coppola , M. and Danelutto , M. , Rewriting skeleton programs: How to evaluate the data-parallel stream-parallel tradeoff. In: Gorlatch , S. Editor, Proc. 1st Int. Workshop on Constructive Methods for Parallel Programming (CMPP'98) , pp. 48 – 58 . Fakultät für Mathematik und Informatik, Universität Passau , May , 1998 . Technical Report MIP-9805.
   Google Scholar
• Bacci , B. , Danelutto , M. , Orlando , S. , Pelagatti , S. and Vanneschi , M. , P3L: A structured high level programming language and its structured support. Concurrency: Practice and Experience , 7 ( 3 ), 225 – 255 , May , 1995 .
   Web of Science ®Google Scholar
• Bacci , B. , Danelutto , M. , Pelagatti , S. and Vanneschi , M. , SKIE: an heterogeneous HPC environment. Parallel Computing , 25 ( 13 – 14 ), 1827 – 1852 , December , 1999 .
   Web of Science ®Google Scholar
• Bacci , B. , Gorlatch , S. , Lengauer , C. and Pelagalti , S. , Skeletons and transformations in an integrated parallel programming environment. In: Parallel Computing Technologies (PaCT-99) , LNCS 1662, pp. 13 – 27 . Springer-Verlag, 1999 .
   Google Scholar
• Bentley , J. J. , Programming pearls: Algorithm design techniques. Comm. ACM , 27 ( 9 ), 865 – 871 , Sept. , 1984 .
   Google Scholar
• Bird , R. , Lectures on constructive functional programming. In: Broy , M. Editor, Constructive Methods in Computing Science, NATO ASI Series F: Computer and Systems Sciences , 55 , 151 – 216 . Springer-Verlag, 1988 .
   Google Scholar
• Bird , R. , Introduction to Functional Programming using Haskell, 2nd edition. Series in Computer Science. , Prentice Hall Europe , 1998 .
   Google Scholar
• Botorog , G. H. and Kuchen , Skil, H. , An imperative language with algorithmic skeletons for efficient distributed programming. In: Proc. Fifth Int. Symp. on High Performance Distributed Computing (HPDC-5) , pp. 243–252. IEEE Computer Society Press, 1996.
   Google Scholar
• Cole , M. , Gorlatch , S. , Prins , J. and Skillicorn , D. Editors, High Level Parallel Programming: Applicability, Analysis and Performance. , Dagstuhl-Seminar Report 238, Schloß Dagstuhl, 1999 .
   Google Scholar
• Cole , M. I. , Algorithmic Skeletons: Structured Management of Parallel Computation. Research Monographs in Parallel and Distributed Computing. , Pitman, 1989 .
   Google Scholar
• Cole , M. I. , Parallel programming with list homomorphisms. Parallel Processing Letters , 5 ( 2 ), 191 – 204 , June , 1995 .
   Google Scholar
• Cole , M. I. , Gorlatch , S. , Lengauer , C. and Skillicorn , D. B. Editors, Theory and Practice of Higher-Order Parallel Programming. , Schloß Dagstuhl, Feb. , 1997 . Report 169.
   Google Scholar
• Darlington , J. , Guo , Y. , To , H. W. , and Jing , Y. ( 1995 ). Skeletons for structured parallel composition. In: Proc. of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ,
   Google Scholar
• di Martino , B. and Kessler , C. W. , Program comprehension engines for automatic parallelization: A comparative study. In: Jelly , I. , Gorton , I. and Croll , P. Editors, Software Engineeringfor Paralleland Distributed Systems , pp. 146 – 157 . Chapman & Hall, 1996 .
   Google Scholar
• Gardner , M. , The fantastic combinations of John Conway's new game of life. Scientific American, pp. 100 – 123 , October , 1970 .
   Web of Science ®Google Scholar
• Gorlatch , S. , Systematic efficient parallelization of scan and other list homomorphisms. In: Bougé , L. , Fraigniaud , P. , Mignotte , A. and Robert , Y. Editors, Euro-Par'96: Parallel Processing, II, Lecture Notes in Computer Science 1124 , 401 – 408 . Springer-Verlag, 1996 .
   Google Scholar
• Gorlatch , S. and Lengauer , C. (De)Compositions for parallel scan and reduction. In: Proc. 3rd Working Con! on Massively Parallel Programming Models (MPPM'97) , pp. 23 – 32 . IEEE Computer Society Press, 1998 .
   Google Scholar
• Gorlatch , S. and Pelagatti , S. , A transformational framework for skeletal programs: Overview and case study. In: Rohlim, J. et al. Editors, Parallel and Distributed Processing. IPPS/SPDP'99 Workshops Proceedings, Lecture Notes in Computer Science 1586 , pp. 123 – 137 . Springer-Verlag, 1999 .
   Google Scholar
• Gorlatch , S. , Wedler , C. and Lengauer , C. , Optimization rules for programming with collective operations. In: Atallah , M. Editor, 13th Int. Parallel Processing Symp, and 10th Symp. on Parallel and Distributed Processing (IPPS/SPDP'99) , pp. 492 – 499 . IEEE Computer Society Press, 1999 .
   Google Scholar
• Hamdan , M. , Michaelson , G. and King , P. , A scheme for nesting algorithmic skeletons. In: Hammond , K. , Davie , T. and Clack , C. Editors, Proc. 10th Int. Workshop on the Implementation of Functional Languages (IFL'98) , pp. 195 – 211 . Department of Computer Science, University College London , 1998 .
   Google Scholar
• Harrison , P. G. ( 1992 ). A higher-order approach to parallel algorithms. The Computer Journal , 35 ( 6 ), 555 – 566 .
   Web of Science ®Google Scholar
• Herrmann , C. A. and Lengauer , C. ( 1999 ). Parallelization of divide-and-conquer by translation to nested loops. J. Functional Programming , 9 ( 3 ), 279 – 310 .
   Google Scholar
• Hoffmann , C. M. and O'Donnell , M. , Interpreter generation using tree pattern matching. In: Proc. 6th ACM Symp. on Principles of Programming Languages (POPL'79) , pp. 169 – 179 . ACM Press, 1979 .
   Google Scholar
• Hoffmann , C. M. and O'Donnell , M. , Pattern matching in trees. , J. ACM , 29 ( 1 ), 68 – 95 , Jan. , 1982 .
   Google Scholar
• Jay , B. , Cole , M. , Sekanina , M. and Steckler , P. , A monadic calculus for parallel costing of a functional language of arrays. In: Lengauer , C. , Griebl , M. and Gorlatch , S. Editors, Parallel Processing. Euro-Par'97, Lecture Notes in Computer Science 1300 , pp. 650 – 661 . Springer-Verlag, 1997 .
   Google Scholar
• Kasaraju , S. R. , Efficient tree pattern matching. In: Proc. 30th IEEE Ann. Symp, on Foundations of Computer Science (FOCS'89) , pp. 178 – 183 . IEEE Computer Society Press, 1989 .
   Google Scholar
• Kessler , C. W. , Pattern-driven automatic program transformation and parallelization. In: Proc. 3rd EUROMICRO Workshop on Parallel and Distributed Processing (PDP'95) , pp. 76 – 83 . IEEE Computer Society Press, 1995 .
   Google Scholar
• McColl , W. F. , Scalable computing. In: van Leeuwen , J. Editor, Computer Science Today, Lecture Notes in Computer Science 1000 , pp. 46–61. Springer-Verlag, 1995.
   Google Scholar
• Mäkinen , E. , On the subtree isomorphism problem for ordered trees. Parallel Processing Letters , 32 ( 5 ), 271 – 273 , Sept. , 1989 .
   Web of Science ®Google Scholar
• Parnas , D. L. , On the design and development of program families. IEEE Trans. on Software Engineering , SE-2(1), 1 – 9 Mar. , 1976 .
   Google Scholar
• Parsons , P. J. and Rabhi , F. A. ( 1998 ). Generating parallel programs from paradigm based specifications. Journal of Systems Architecture , 45 ( 4 ), 261 – 283 .
   Web of Science ®Google Scholar
• Rauber , T. and Rünger , G. , A coordination language for mixed task and data parallel programs. In: Proc. of3rd Annual ACM Symposium on Applied Computing (SAC'99) , pp. 146 – 155 . ACM Press, 1999 .
   Google Scholar
• Skillicorn , D. B. , Foundations of Parallel Programming. Cambridge International Series on Parallel Computation. Cambridge University Press, 1994 .
   Google Scholar
• Skillicorn , D. B. and Cai , W. , A cost calculus for parallel functional programming. J. Parallel and Distributed Computing , 28 ( 1 ), 65 – 83 , July , 1995 .
   Web of Science ®Google Scholar
• Smith , D. ( 1987 ). Applications of a strategy for designing divide-and-conquer algorithms. Science of Computer Programming , 8 ( 3 ), 213 – 229 .
   Web of Science ®Google Scholar
• Südholt , M. , Data distribution algebras - a formal basis for programming using skeletons. In: Olderog , E.-R. Editor. Programming Concepts, Methods and Calculi (PROCOMET'94) , pp. 19 – 38 . Elsevier, 1994 .
   Google Scholar
• Swierstra , D. and de Moor , O. , Virtual data structures. In: Möller , B. , Partsch , H. and Schuman , S. Editors, Formal Program Development, LNCS 755 , pp. 355 – 371 . Springer-Verlag, 1993 .
   Google Scholar
• Wedler , C. and Lengauer , C. ( 1998 ). On linear list recursion in parallel. Acta Informatica , 35 ( 10 ), 875 – 909 .
   Web of Science ®Google Scholar
• * Parts of this work were presented in the preliminary version at the HiPS workshop of IPPS’99 (Puerto Rico)and at the PaCT’99 conference (St. Petersburg)
   Google Scholar
• †Corresponding author.
   Google Scholar