Ian Foster
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.
Supplemental Material
Available for Download
- Ackerman, W. B. 1982. Data flow languages. Computer 15, 2 (Feb.), 15-25.Google Scholar
- Armstrong, J. and Virding, S. 1989. Programming telephony. In Strand: New Concepts in Parallel Programming. Prentice Hall, Englewood Cliffs, N.J.Google Scholar
- Butler, R. and Lusk, E. 1994. Monitors, message, and clusters: The p4 parallel programming system. Parallel Comput. 20, 547-564. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Carriero, N. and Gelernter, D. 1989. Linda in context. Commun. ACM 32, 4 (Apr.), 444-458. Google Scholar
- Chandy, K. M. and Foster, I. 1995. A deterministic notation for cooperating processes. IEEE Trans. Parallel Distrib. Syst. 6, 8, 863-871. Google Scholar
- 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.Google Scholar
- Chandy, K. M. and Kesselman, C. 1993. CC++: A declarative concurrent object oriented programming notation. In Research Directions in Object Oriented Programming. MIT Press, Cambridge, Mass. Google Scholar
- Chandy, K. M. and Taylor, S. 1991. An Introduction to Parallel Programming. Jones and Bartlett, Boston, Mass. Google Scholar
- Chapman, B., Mehrotra, P., and Zima, H. 1992. Programming in Vienna Fortran. Sci. Program. 1, 1, 31-50.Google Scholar
- Clark, K. and Gregory, S. 1981. A relational language for parallel programming. In Proceedings of the 1981 ACM Conference on Functional Programming Languages and Computer Architectures, ACM, New York, 171-178. Google Scholar
- Clocksin, W. and Mellish, C. 1981. Programming in Prolog. Springer-Verlag, Berlin. Google Scholar
- Cole, M. 1989. Algorithmic Skeletons: Structured Management of Parallel Computation. MIT Press, Cambridge, Mass. Google Scholar
- Dijkstra, E. 1975. Guarded commands, nondeterminacy and the formal derivation of programs. Commun. ACM 18, 453-457. Google Scholar
- Foster, I. 1989. A multicomputer garbage collector for a single-assignment language. Intl J. Parallel Program. 18, 3, 181-203. Google Scholar
- Foster, I. and Taylor, S. 1990. Strand: New Concepts in Parallel Programming. Prentice Hall, Englewood Cliffs, N.J. Google Scholar
- Foster, I., Kesselman, C., and Taylor, S. 1990. Concurrency: Simple concepts and powerful tools. Comput. J. 33, 6, 501-507. Google Scholar
- Foster, I., Olson, R., and Tuecke, S. 1992. Productive parallel programming: The PCN approach. Sci. Program. 1, 1, 51-66.Google Scholar
- 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.Google Scholar
- Gregory, S. 1987. Parallel Logic Programming in PARLOG. Addison-Wesley, Reading, Mass. Google Scholar
- Gropp, W., Lusk, E., and Skjellum, A. 1995. Using MPI: Portable Parallel Programming with the Message Passing Interface. MIT Press, Cambridge, Mass. Google Scholar
- 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.Google Scholar
- Hoare, C. 1974. Monitors: An operating system structuring concept. Commun. ACM 17, 10 (Oct.), 549-557. Google Scholar
- Hoare, C. 1978. Communicating sequential processes. Commun. ACM 21, 8, 666-677. Google Scholar
- 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.Google Scholar
- Kelly, P. 1989. Functional Programming for Loosely-Coupled Multiprocessors, MIT Press, Cambridge, Mass. Google Scholar
- Kesselman, C. 1991. Integrating performance analysis with performance improvement in parallel programs. Ph.D. thesis, UCLA, Los Angeles, Calif. Google Scholar
- Koelbel, C., Loveman, D., Schreiber, R., Steele, G., and Zosel, M. 1994. The High Performance Fortran Handbook. MIT Press, Cambridge, Mass. Google Scholar
- Kowalski, R. 1979. Logic for Problem Solving. North-Holland, Amsterdam. Google Scholar
- Lucco, S. and Sharp, O. 1991. Parallel programming with coordinationstructures. In Proceedings of the 18th Annual ACM Symposium on the Principles of Programming Languages. ACM, New York. Google Scholar
- 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.Google Scholar
- McLennan, B. 1990. Functional Programming: Practice and Theory. Addison-Wesley, Reading, Mass. Google Scholar
- 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.Google Scholar
- Rinard, M., Scales, D., and Lam, M. 1993. Jade: A high-level machine-independent language for parallel programming. Computer 26, 6, 28-38. Google Scholar
- Ringwood, G. 1988. PARLOG86 and the dining logicians. Commun. ACM 31, 10-25. Google Scholar
- Shapiro, E. 1987. Concurrent Prolog: Collected Papers. MIT Press, Cambridge, Mass. Google Scholar
- Sunderam, V. 1990. PVM: A framework for parallel distributed computing. Concurr. Pract. Exper. 2, 4, 315-339. Google Scholar
- Taylor, S. 1989. Parallel Logic Programming Techniques. Prentice Hall, Englewood Cliffs, N.J. Google Scholar
- 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.Google Scholar
Index Terms
- Compositional parallel programming languages
Recommendations
Data-Parallel Programming on MIMD Computers
The implementation of two compilers for the data-parallel programming language Dataparallel C is described. One compiler generates code for Intel and nCUBE hypercube multicomputers; the other generates code for Sequent multiprocessors. A suite of ...
Tools-supported HPF and MPI parallelization of the NAS parallel benchmarks
FRONTIERS '96: Proceedings of the 6th Symposium on the Frontiers of Massively Parallel ComputationHigh Performance Fortran (HPF) compilers and communication libraries with the standardized Message Passing Interface (MPI) are becoming widely available, easing the development of portable parallel applications. The Annai tool environment supports ...
Data Management and Control-Flow Aspects of an SIMD/SPMD Parallel Language/Compiler
Features of an explicitly parallel programming language targeted for reconfigurable parallel processing systems, where the machine's N processing elements (PEs) are capable of operating in both the SIMD and SPMD modes of parallelism, are described. The ...
Reviews
David B. Skillicorn
Parallel programs are complex objects and are hard to build. One way to make building one easier is to insist that the programming language be compositional, that is, the properties of the whole must be (simple) functions of the properties of the pieces. The paper is an argument for this thesis, using the languages Strand and PCN as successful examples. In fact, only compositionality of behavior is really discussed. I would argue that compositionality of costs is at least as important, perhaps moreso, because without it, it is impossible to break designs into pieces and build them independently. This paper would have been an interesting contribution to the discussion of parallel programming models, had it appeared in a timely way. In a fast-changing field, the delay in publication has necessarily reduced the value of its contribution.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments