Compositional parallel programming languages

ABSTRACT

In task-parallel programs, diversee activities can take place concurrently, and communication and synchronization patterns are complex and not easily predictable. Previous work has identified compositionality as an important design principle for task-parallel programs. In this article, we discuss alternative approaches to the realization of this principle, which holds that properties of program components should be preserved when those co ponents are composed in parallel with other program components. We review two programming languages, Strand and Program Composition Notation, that support compositionality via a small number of simple concepts, namely, monotone operations on shared opbects, a uniform addressing mechanism, and parallel composition. Both languages have been used extensively for large-scale application development, allowing us to provide an informed assessment of both their strengths and their weaknesses. We observe that while compositionality simplifies development of complex applications, the use of specialized languages hinders reuse of existing code and tools and the specification of domain decomposition strategies. This suggests an alternative approach based on small extensions to existing sequential languages. We conclude the article with a discussion of two languages that realized this strategy.

REFERENCES

• 1: Ackerman, W. B. 1982. Data flow languages. Computer 15, 2 (Feb.), 15-25.
• 2: Armstrong, J. and Virding, S. 1989. Programming telephony. In Strand: New Concepts in Parallel Programming. Prentice Hall, Englewood Cliffs, N.J.
• 3: Ralph M. Butler , Ewing L. Lusk, Monitors, messages, and clusters: the p4 parallel programming system, Parallel Computing, v.20 n.4, p.547-564, April 1994 [doi>10.1016/0167-8191(94)90028-0]
• 4: Butler, R., Foster, I., Karonis, N., Olson, R., Pfluger, N., Price. M., and Tuecke, S. 1989. Aligning genetic sequences. In Strand: New Concepts in Parallel Programming. Prentice Hall, Englewood Cliffs, N.J.
• 5: Cann, D., Feo, J., and DeBoni, T. 1990. Sisal 1,2: High performance applicative computing. In Proceedings of the Symposium on Parallel and Distributed Processing. IEEE Computer Science Press, Los Alamitos, Calif., 612-616.
• 6: Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989 [doi>10.1145/63334.63337]
• 7: K. Mani Chandy , Ian Foster, A Notation for Deterministic Cooperating Processes, IEEE Transactions on Parallel and Distributed Systems, v.6 n.8, p.863-871, August 1995 [doi>10.1109/71.406962]
• 8: Chandy, K. M. and Kesselman, C. 1992. The derivation of compositional programs. In Proceedings of the 1992 Joint International Conference and Symposium on Logic Programming. MIT Press, Cambridge, Mass.
• 9: K. Mani Chandy , Carl Kesselman, CC++: a declarative concurrent object-oriented programming notation, Research directions in concurrent object-oriented programming, MIT Press, Cambridge, MA, 1993
• 10: K. Mani Chandy , Stephen Taylor, An introduction to parallel programming, Jones and Bartlett Publishers, Inc., 1992
• 11: Chapman, B., Mehrotra, P., and Zima, H. 1992. Programming in Vienna Fortran. Sci. Program. 1, 1, 31-50.
• 12: Keith L. Clark , Steve Gregory, A relational language for parallel programming, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.171-178, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806776]
• 13: W F. Clocksin , Christopher S. Mellish, Programming in Prolog (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1984
• 14: Murray Cole, Algorithmic skeletons: structured management of parallel computation, MIT Press, Cambridge, MA, 1991
• 15: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 16: Ian Foster, A multicomputer garbage collector for a single-assignment language, International Journal of Parallel Programming, v.18 n.3, p.181-203, Jun. 1990 [doi>10.1007/BF01407898]
• 17: Ian Foster , Stephen Taylor, Strand: new concepts in parallel programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 18: I. Foster , C. Kesselman , S. Taylor, Concurrency: simple concepts and powerful tools, The Computer Journal, v.33 n.6, p.501-507, Dec. 1990 [doi>10.1093/comjnl/33.6.501]
• 19: Foster, I., Olson, R., and Tuecke, S. 1992. Productive parallel programming: The PCN approach. Sci. Program. 1, 1, 51-66.
• 20: Fox, G., Hiranandani, S., Kennedy, K., Koelbel, C., Kremer, U., Tseng, C., and Wu, M. 1990. Fortran D language specification. Tech. Rep. TR90-141, Dept. of Computer Science, Rice Univ., Houston, Tex. Dec.
• 21: Steve Gregory, Parallel logic programming in PARLOG: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 22: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI: portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1994
• 23: Harrar, D., Keller, H., Lin, D., and Taylor, S. 1991. Parallel computation of Taylor-vortex flows. In Proceedings of the Conference on Parallel Computational Fluid Dynamics. Elsevier Science Publishers B.V., Amsterdam.
• 24: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 25: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 26: Kahn, G. and MacQueen, D. 1977. Coroutines and networks of parallel processes. In Information Processing 77: Proceedings of the IFIP Congress. North-Holland, Amsterdam, 993-998.
• 27: Paul H. Kelly, Functional Programming for Loosely-Coupled Multiprocessors, MIT Press, Cambridge, MA, 1989
• 28: Carl Kesselman, Tools and techniques for performance measurement and performance improvement in parallel programs, University of California at Los Angeles, Los Angeles, CA, 1991
• 29: Charles H. Koelbel , David B. Loveman , Robert S. Schreiber , Guy L. Steele, Jr. , Mary E. Zosel, The high performance Fortran handbook, MIT Press, Cambridge, MA, 1994
• 30: Robert Kowalski, Logic for problem-solving, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 31: Steven Lucco , Oliver Sharp, Parallel programming with coordination structures, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.197-208, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99612]
• 32: Lusk, E., Disz, T., Olson, R., Overbeek, R., Stevens, R., Warren, D., Calderwood, A., Szeredi, P., Haridi, S., Brand, P., Carlsson, M., Ciepielewski, A., and Hausman, B. 1988. The Aurora or-parallel Prolog system. In Proceedings of the Fifth Generation Computer Systems Conference. ICOT,Tokyo, 819-830.
• 33: Bruce J. MacLennan, Functional programming: practice and theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 34: Mierowsky, C., Taylor, S., Shapiro, E., Levy, J., and Safra, S. 1985. Design and implementation of Flat Concurrent Prolog. Tech. Rep. CS85-09, Weizmann Institute of Science, Rehovot, Israel.
• 35: Martin C. Rinard , Daniel J. Scales , Monica S. Lam, Jade: A High-Level, Machine-Independent Language for Parallel Programming, Computer, v.26 n.6, p.28-38, June 1993 [doi>10.1109/2.214440]
• 36: G. A. Ringwood, Parlog86 and the dining logicians, Communications of the ACM, v.31 n.1, p.10-25, Jan. 1988 [doi>10.1145/35043.35044]
• 37: E. Shapiro, Concurrent prolog: collected papers, MIT Press, Cambridge, MA, 1987
• 38: V. S. Sunderam, PVM: a framework for parallel distributed computing, Concurrency: Practice and Experience, v.2 n.4, p.315-339, Dec. 1990 [doi>10.1002/cpe.4330020404]
• 39: Stephen Taylor, Parallel logic programming techniques, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 40: Xu, M. and Turner, S. 1990. A multi-level time warp mechanism. In Proceedings of the 1990 Summer Computer Simulation Conference Society for Computer Simulation. San Diego, Calif., 165-170.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Languages

Keywords:
compositionality, parallel languages, parallel programming