How to write parallel programs: a guide to the perplexed

ABSTRACT

We present a framework for parallel programming, based on three conceptual classes for understanding parallelism and three programming paradigms for implementing parallel programs. The conceptual classes are result parallelism, which centers on parallel computation of all elements in a data structure; agenda parallelism, which specifies an agenda of tasks for parallel execution; and specialist parallelism, in which specialist agents solve problems cooperatively. The programming paradigms center on live data structures that transform themselves into result data structures; distributed data structures that are accessible to many processes simultaneously; and message passing, in which all data objects are encapsulated within explicitly communicating processes. There is a rough correspondence between the conceptual classes and the programming methods, as we discuss. We begin by outlining the basic conceptual classes and programming paradigms, and by sketching an example solution under each of the three paradigms. The final section develops a simple example in greater detail, presenting and explaining code and discussing its performance on two commercial parallel computers, an 18-node shared-memory multiprocessor, and a 64-node distributed-memory hypercube. The middle section bridges the gap between the abstract and the practical by giving an overview of how the basic paradigms are implemented. We focus on the paradigms, not on machine architecture or programming languages: The programming methods we discuss are useful on many kinds of parallel machine, and each can be expressed in several different parallel programming languages. Our programming discussion and the examples use the parallel language C-Linda for several reasons: The main paradigms are all simple to express in Linda; efficient Linda implementations exist on a wide variety of parallel machines; and a wide variety of parallel programs have been written in Linda.

REFERENCES

• 1: ASHCRAFT, C., CARRIERO, N., AND GELERNTER, D. 1989. Is explicit parallelism natural? Hybrid DB search and sparse LDLT factorization using Linda. Res. Rep. 744, Dept. of Computer Science, Yale Univ., New Haven, Conn., Jan.
• 2: BAL, H. E., AND TANENBAUM, A. S. 1987. Orca: A language for distributed object-based programming. Internal Rep. 140, Dept. Wiskunde en Informatica, Vrije Universiteit, Amsterdam, Dec.
• 3: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• 4: BJORNSON, R., CARRIERO, N., AND GELERNTER, U. 1989. The implementation and performance of hypercube Linda. Res. Rep. 690, Dept. of Computer Science, Yale Univ., New Haven, Conn., Mar.
• 5: BJORNSON, U., CARRIERO, N., GELERNTER, D., AND LEICHTER, J. 1988. Linda, the portable parallel. Res. Rep. 520, Dept. of Computer Science, Yale Univ., New Haven, Conn., Jan.
• 6: L. Borrmann , M. Herdieckerhoff , A. Klein, Tuple space integrated into Modula-2, implementation of the Linda concept on a hierarchical multiprocessor, Proceedings of the conference on CONPAR 88, p.659-666, October 1989, UMIST, Manchester, United Kingdom
• 7: BRINCH HANSEN, P. 1975. The programming language Concurrent Pascal. IEEE Trans. Softw. Eng. SE-1, 2, 199-206.
• 8: Nicholas Carriero , David Gelernter, Applications experience with Linda, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.173-187, July 19-21, 1988, New Haven, Connecticut, United States
• 9: 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]
• 10: Nicholas Carriero , David Gelernter , Jerrold Leichter, Distributed data structures in Linda, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.236-242, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512666]
• 11: Marina C. Chen, A parallel language and its compilation to multiprocessor machines or VLSI, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.131-139, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512656]
• 12: David R. Cheriton , Willy Zwaenepoel, Distributed process groups in the V Kernel, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.77-107, May 1985 [doi>10.1145/214438.214439]
• 13: W. J. Dally , A. A. Chien, Object-oriented concurrent programming in CST, Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues, p.434-439, January 19-20, 1988, Pasadena, California, United States [doi>10.1145/62297.62346]
• 14: DEPARTMENT OF DEFENSE, U.S. 1982. Reference Manual for the Ada Programming Language. ACM AdaTEC, July.
• 15: GELERNTER, D. 1989. Information management in Linda. In M. Reeve and S. E. Zenith, eds., Parallel processing and artificial intelligence, J. Wiley (1989):/23-34, Proceedings of AI and Communicating Process Architectures (London, July).
• 16: D. Gelernter , S. Jagannathan , T. London, Environments as first class objects, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.98-110, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41634]
• 17: GELERNTER, D., CARRIERO, N., CHANDRAN, $., AND CHANG, S. 1985. Parallel programming in Linda. In Proceedings of the International Conference on Parallel Processing (St. Charles, Ill., Aug.). IEEE, 255-263.
• 18: GILMORE, P. 1979. Massive Parallel Processor (MPP):/Phase One Final Report. Tech. Rep. GER-16684, Goodyear Aeorospace Co., Akron.
• 19: L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
• 20: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 21: HENDERSON, P. 1982. Purely functional operating systems. In Functional Programming and Its Applications, J. Darlington, P. Henderson, and D. A. Turner, Eds. Cambridge Univ. Press, New York, pp. 177-192.
• 22: W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
• 23: 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]
• 24: 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]
• 25: Paul Hudak, Para-functional programming, Computer, v.19 n.8, p.60-69, Aug. 1986 [doi>10.1109/MC.1986.1663309]
• 26: H F Jordan, Structuring parallel algorithms in an MIMD, shared memory environment, Parallel Computing, v.3 n.2, p.93-110, May 1986 [doi>10.1016/0167-8191(86)90028-1]
• 27: Eric Jul , Henry Levy , Norman Hutchinson , Andrew Black, Fine-grained mobility in the Emerald system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.109-133, Feb. 1988 [doi>10.1145/35037.42182]
• 28: KAHN, G. 1974. The semantics of a simple language for parallel processing. In Proceedings of the IFIP Congress 74. North Holland, 471.
• 29: Butler W. Lampson , David D. Redell, Experience with processes and monitors in Mesa, Communications of the ACM, v.23 n.2, p.105-117, Feb. 1980 [doi>10.1145/358818.358824]
• 30: Ching-Cheng Lee , Stephen Skedzielewski , John Feo, On the implementation of applicative languages on shared-memory, MIMD multiproce, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.188-197, July 19-21, 1988, New Haven, Connecticut, United States
• 31: LELER, W. 1989. PIX, the latest NEWS. In Proceedings of COMPCON Spring '89 (San Francisco, Feb.). IEEE.
• 32: T. A. Marsland , M. Campbell, Parallel Search of Strongly Ordered Game Trees, ACM Computing Surveys (CSUR), v.14 n.4, p.533-551, Dec. 1982 [doi>10.1145/356893.356895]
• 33: Satoshi Matsuoka , Satoru Kawai, Using tuple space communication in distributed object-oriented languages, Conference proceedings on Object-oriented programming systems, languages and applications, p.276-284, September 25-30, 1988, San Diego, California, United States
• 34: David May, OCCAM, ACM SIGPLAN Notices, v.18 n.4, p.69-79, April 1983 [doi>10.1145/948176.948183]
• 35: MULLENDER, S. J., AND TANENBAUM, A. S. 1986. The design of a capability-based distributed operating system. Comput. J. 29, 4 (Mar.), 289-300.
• 36: IEEE Computer Graphics and Applications Staff, Natura ex Machina, IEEE Computer Graphics and Applications, v.9 n.1, p.4-7, January 1989
• 37: NAREM, J. E. 1988. DB: A parallel news database in Linda. Tech. memo, Dept. of Computer Science, Yale Univ., New Haven, Conn., Aug.
• 38: NIKHIL, R., PINGALI, K., AND ARVIND. 1986. Id Nouveau. Memo 265, Computation Structures Group, MIT, Cambridge, Mass.
• 39: OLSON, T. J. 1986. Finding lines with the Hough Transform on the BBN Butterfly parallel processor. Butterfly Proj: Rep. 10, Dept. of Comput. Science, Univ. of Rochester, New York, Sept.
• 40: 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]
• 41: ROTH, P. 1985. Portnoy's Complaint. Fawcett Crest, p. 309 (first published by Random House, New York 1967).
• 42: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• 43: E. Shapiro, Concurrent prolog: collected papers, MIT Press, Cambridge, MA, 1987
• 44: R. A. Whiteside , J. S. Leichter, Using Linda for supercomputing on a local area network, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.192-199, November 12-17, 1988, Orlando, Florida, United States
• 45: WIRTH, N. 1977. Modula: A language for modular multiprogramming. Softw. Pract. Exp. 7, 3-35.
• 46: A. S. Xu, A FAULT-TOLERANT NETWORK KERNEL FOR LINDA, Massachusetts Institute of Technology, Cambridge, MA, 1988
• 47: M. Young , A. Tevanian , R. Rashid , D. Golub , J. Eppinger, The duality of memory and communication in the implementation of a multiprocessor operating system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.63-76, November 08-11, 1987, Austin, Texas, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C; Linda
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

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

General Terms:
Design, Languages, Performance