Parallelization in calculational forms

ABSTRACT

The problems involved in developing efficient parallel programs have proved harder than those in developing efficient sequential ones, both for programmers and for compilers. Although program calculation has been found to be a promising way to solve these problems in the sequential world, we believe that it needs much more effort to study its effective use in the parallel world. In this paper, we propose a calculational framework for the derivation of efficient parallel programs with two main innovations:. -We propose a novel inductive synthesis lemma based on which an elementary but powerful parallelization theorem is developed. -We make the first attempt to construct a calculational algorithm for parallelization, deriving associative operators from data type definition and making full use of existing fusion and tupling calculations.Being more constructive, our method is not only helpful in the design of efficient parallel programs in general but also promising in the construction of parallelizing compiler. Several interesting examples are used for illustration.

References

1. Bac89.R. Backhouse. An exploration of the Bird- Meertens formalism. In STOP Summer School on Constructive Algorithmies, Ametand, September 1989.
2. Bir87.tL Bird. An introduction to the theory of lists. In M. Broy, editor, Logic of Program. ruing and Calculi of Discrete Design, pages 5- 42. Springer-Verlag, 1987.
3. Bir89.tL Bird. Constructive functional programming, In STOP Summer School on Constructive AI- gorithmics: Abeland, 9 1989.
4. Ble89.Guy E. Blelloch. Scans as primitive operations. IBBB Trans. on Computers, 38(11):1526-1538, November 1989.
5. Ble92.G.E. Bleiloch. NESL: a nested data parallel language. Technical Report CMU-CS-92-103, School of Computer Science, Carnegie-Mellon University, January 1992.
6. Bra94.T.A. Bratvold. Parallelising a functional program'using a list-homomorphism skeleton. In Hoon tIong, editor, PASCO~9$: Firs~ International Symposium on Parallel Symbolic ~ompu. ration, pages 44-53. World Scien~ific~ September 1994.
7. BSS91.D. Barnard, J. Schmeiser, and D. $killicorn. Deriving associative operators for language recognition. In Bulletiu of EATCS (43), pages 131- 139, 1991.
8. CDG96.W. Chin, J. Dariington, and Y. Guo. Parallelizing conditional recurrences. In Annual European Conference on Parallel Processing, LNCS 1123, pages 579-586, LIP, F_~S Lyon, France, Augus~ 199{}. Springer-Verlag.
9. Chi93.W. Chin. Towards an automated tupling strategy. In Prec. Conference on Partial Eva~ualion and Program Manipufaflon~ pages 119-132, Copenhagen, June 1993. ACM Press.
10. Col89.M. Cole. Algorithmic skeletons : a structured approach to the managemen~ of parallel computation. Reseaxch Monographs in Parallel and Distributed Computing, Pitman~ London, 1989,
11. Col95.M. Coie. Parallel programming with lis~ homomorphisms. Parallel Processing Letters, 5(2), 1995.
12. CTT97.W. Chin, S. Tan, and Y. Tee. Deriving efficien~ parallel programs for complex recurrences. In A GM SIGSAM/SIGNUM International Conference on Parallel Symbolic Compu. ~agion, pages 101-110, Hawaii, July 1997, ACM Press.
13. Dar81.J. Darlington. An experimental program transformation system. Artificial Intelligence, 16:1- 46, 1981.
14. DFH+93.J. Darlington, A.J. Field, P.G. Harrison, P.H.J. Kelly, D.W.N. Sharp, Q. Wu, and R,L. While. Parallel programming using skeleton funcLions. In Parallel Architectures ~ Languages Burope. Springer-Verlag, June 93.
15. dM92.O. de Moor. Gategories, relations and dynamic programming. Ph.D thesis, Programming research group, Oxford Univ., 1992. Technical Monograph PRG-98.
16. FG94.A. Fischer and A. Ghuloum. Parallelizing complex scans and reductions. In A UM PLDI, pages 135-146, Orlando, Florida, 1994. ACM Press.
17. Fok92.M. Folddnga. A gentle introduction to category theory m the calculational approac~--. Technical Report Lecture Notes, Dept. INF, University of Twente, The Netherlands, September 1992.
18. GDH96.Z.N. Grant-Duff and P. Harrison. Parallelism via homomorphism. Parallel Processing Letters, 6(2):279-295, 1996.
19. GG97.A. Geser and S. Gorlateh. Parallelizing functional programs by generalization, tn Algebraic and Logic Programming. ALP'97, Lecture Notes in Computer Science. Springer-Verlag, 1997.
20. Gib92.J. Gibbons. Upwards and downwards accumulations on trees. In Mathematics of Program Construetion (LNCS 669), pages 122-138. Springer- Verlag, 1992.
21. Gib96.J. Gibbons. The third homomorphism theorem. Journal of Functional Programming, 6(4):657- 665, 1996.
22. GLJ93.A. Gill, J. Launchbury, and S. Peyton Jones. A short cut to deforestation. In Proc. Conference on Functional Programming Languages and Computer Architecture, pages 223-232, Copenhagen, June 1993. #
23. Gor96a.S. Gorlatch. Systematie efficient parallelization of scan and other list homomorphisms. In Annual European Conference on Parallel Processing, LNGS 11~, pages 401-408, LIP, ENS Lyon, France, August 1996. Springer-Verlag.
24. Gor96b.S. Gorlatch. Systematic extraction and implementation of divide-and-conquer parallelism. In Proc. Conference on Programming Languages: Implementation, Logics and Programs, LNCS 1140, pages 274-288. Springer-Verlag, 1996.
25. Hei94.B. Heinz. Lemma discovery by anti-unification of regular sorts. Technical report no. 94-21, FM Informatik, Technische Universitat Berlin, May 1994.
26. HIT96.Z. Hu, H. lwasaki, and M. Takeichi. Deriving structural hylomorphisms from recursive definitions. In A CM SIGPLAN International Conference on Functional Programming, pages 73-82, Philadelphia, PA, May 1996. ACM Press.
27. HIT97.Z. Hu, H. Iwasaki, and M. Takeichi. Formal derivation of efficient parallel programs by construction of list homomorphisms. ACM Transactions on Programming Languages and .qysterns, 19(3):444-461, 1997.
28. HITT97.Z. Hu, H. Iwasaki, M. TakeiehJ, and A. T~o. Tupling calculation eliminates multiple data traversals. In A GM SIGPLAN International Conference on Functional Programming, pages 164-175, Amsterdam, The Netherlands, June 1997. ACM Press.
29. HPJWe92.Paul Hudak, Simon L. Peyton Jones, and Philip Wadler (editors). Report on the programming language HaskeU, a non-strict purely functional language (version 1.2). SIGPLAN Notices, Mar, 1992.
30. Jeu93.J. Jeuring. Theories for Algorithm Calculation. Ph.D thesis, Faculty of Science, Utrecht University, 1993.
31. JJ96.J. Jeuring and P. Jansson. Polytypic programruing. In ~nd International Summer School on Advanced Functional Programming Techniques, LNCS. Springer Verlag, July 1996.
32. JS90.Geraint Jones and Mary Sheeran. Circuit design in Ruby. In Staunstrup, editor, Formal Methods for VL,gI Design, Amsterdam, 1990. Elsevier Science Publications.
33. Len96.C. Lemganer. Automatic parallelization and high performance compiler. In Annual European Conference on Parallel Processing, LIVCS 1123, pages 377-378, LIP, ENS Lyon, France, August 1996. Springer-Verlag.
34. Mal89.G. Malcolm. Homomorphisms and promotability. In J.L.A. van de Snepscheut, editor, Mathematics of Program Construction, pages 335- 347. Springer-Verlag, 1989.
35. Mal90.G. Malcolm. Data structures and program transformation. Science of Computer Programming, (14):255-279, August 1990.
36. Mee92.L. Me~. Paxamorphisms. Formal Aspects of Computing, 4(5):413-424, 1992.
37. O’D94.J. O'Donnell. A correctness proof of parallel scan. Parallel Processing Letters, 4(3):329-338, 1994.
38. OHIT97.Y. Onoue, Z. Hu, H. Iwasaki, and M. Takeichi. A ealculational fusion system HYLO. In IFIP TC ~ Working Conference on Algorithmic Languages and Galculi~ Le Bischenberg, France, February 1997. Chapman&Hall.
39. SF93.T. Sheard and L. Fegaras. A fold for all seasons. In Proc. Conference on Functional Pro- 9rammin9 Languages and Computer Architecture, pages 233-242, Copenhagen, June 1993.
40. Ski90.D.B. Skillieorn. ArehSteeture-independent parallel computation. IEEE Computer, 23(12):38- 51, December 1990.
41. Ski94a.David B. Skillicorn. Foundations of Parallel Programming. Cambridge University Press, 1994.
42. Ski94b.D.B. SkilIicorn. The categorical data type approach to general-purpose parallel computation. In B. Pehrson and I. Simon, editors, Workshop on General-Purpose Parallel Computing, tgth tFtP World Congress, volume IFIP Transactions A-51, pages 565-570. Norfh-Holland, September 1994.
43. Ski92.D.B. Skillicorn. The Bird-Meertens Formalism as a Parallel Model. In NATO ARW "Software for Parallel Computation", June 92.
44. TM95.A. ~o and E. Meijer. Shortcut deforestation in calculational form. In Proc. Conference on Functional Programming Languages and Compuier Architecture, pages 30~-313, La Jolla, California, June 1995.

Index Terms

• Computing methodologies

  • Parallel computing methodologies

    • Parallel programming languages

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features

        • Data types and structures

      • Language types

        • Parallel programming languages

• Theory of computation

  • Logic

  • Semantics and reasoning

    • Program constructs

      • Functional constructs

    • Program reasoning