Models and languages for parallel computation

ABSTRACT

We survey parallel programming models and languages using six criteria to assess their suitability for realistic portable parallel programming. We argue that an ideal model should by easy to program, should have a software development methodology, should be architecture-independent, should be easy to understand, should guarantee performance, and should provide accurate information about the cost of programs. These criteria reflect our belief that developments in parallelism must be driven by a parallel software industry based on portability and efficiency. We consider programming models in six categories, depending on the level of abstraction they provide. Those that are very abstract conceal even the presence of parallelism at the software level. Such models make software easy to build and port, but efficient and predictable performance is usually hard to achieve. At the other end of the spectrum, low-level models make all of the messy issues of parallel programming explicit (how many threads, how to place them, how to express communication, and how to schedule communication), so that software is hard to build and not very portable, but is usually efficient. Most recent models are near the center of this spectrum, exploring the best tradeoffs between expressiveness and performance. A few models have achieved both abstractness and efficiency. Both kinds of models raise the possibility of parallelism as part of the mainstream of computing.

REFERENCES

• 1: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• 2: Gul Agha , Christian J. Callsen, ActorSpace: an open distributed programming paradigm, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.23-32, May 19-22, 1993, San Diego, California, United States
• 3: AHMED, S., CARRIERO, N., AND GELERNTER, D. 1994. A program building tool for parallel applications. In DIMACS Workshop on Specification of Parallel Algorithms (Princeton University, May), 161-178.
• 4: Sudhir Ahuja , Nicholas J. Carriero , David H. Gelernter , Venkatesh Krishnaswamy, Matching Language and Hardware for Parallel Computation in the Linda Machine, IEEE Transactions on Computers, v.37 n.8, p.921-929, August 1988 [doi>10.1109/12.2244]
• 5: Pierre America, Pool-T: a parallel object-oriented language, Object-oriented concurrent programming, MIT Press, Cambridge, MA, 1987
• 6: ANDRE, F. AND THOMAS, H. 1989. The Pandore System. In IFIP Working Conference on Decentralized Systems (Dec.) poster presentation.
• 7: ANDRE, F., MAHEO, Y., LE FUR, M., AND PAZAT, J.-L. 1994. The Pandore compiler: Overview and experimental results. Tech. Rep. PI-869, IRISA, October.
• 8: Gregory R. Andrews , Ronald A. Olsson, The SR programming language: concurrency in practice, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1993
• 9: Gregory R. Andrews , Michael Coffin , Irving Elshoff , Kelvin Nilson , Gregg Townsend , Ronald A. Olsson , Titus Purdin, An overview of the SR language and implementation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.1, p.51-86, Jan. 1988 [doi>10.1145/42192.42324]
• 10: ARBEIT, B., CAMPBELL, G., COPPINGER, R., PEIERLS, R., AND STAMPF, D. 1993. The ALMS systern: Implementation and performance. Brookhaven National Laboratory, internal report.
• 11: Ralph-Johan Back, A Method for Refining Atomicity in Parallel Algorithms, Proceedings of the Parallel Architectures and Languages Europe, Volume II: Parallel Languages, p.199-216, June 12-16, 1989
• 12: BACK, R. J.R. 1989b. Refinement calculus part II: Parallel and reactive programs. Tech. Rep. 93, bo Akademi, Departments of Computer Science and Mathematics, SF-20500 bo, Finland.
• 13: Ralph-Johan Back , Kaisa Sere, Stepwise Refinement of Action Systems, Proceedings of the International Conference on Mathematics of Program Construction, 375th Anniversary of the Groningen University, p.115-138, June 26-30, 1989
• 14: BACK, R. J. R. AND SERE, K. 1990. Deriving an Occam implementation of action systems. Tech. Rep. 99, bo Akademi, Departments of Computer Science and Mathematics, SF-20500 bo, Finland.
• 15: BAIARDI, F., DANELUTTO, M., JAZAYERI, M., PEL- AGATTI, S., AND VANNESCHI, M. 1991. Architectural models and design methodologies for general-purpose highly-parallel computers. In IEEE CompEuro 91--Advanced Computer Technology, Reliable Systems and Applications (May).
• 16: Henri E. Bal , Jennifer G. Steiner , Andrew S. Tanenbaum, Programming languages for distributed computing systems, ACM Computing Surveys (CSUR), v.21 n.3, p.261-322, Sep. 1989 [doi>10.1145/72551.72552]
• 17: Henri E. Bal, Orca: a language for distributed programming, ACM SIGPLAN Notices, v.25 n.5, p.17-24, May 1990 [doi>10.1145/382080.382082]
• 18: Jean-Pierre Banâtre , Daniel Le Métayer, Introduction to Gamma, Research Directions in High-Level Parallel Programming Languages, p.197-202, June 17-19, 1991
• 19: BANGER, C. 1992. Arrays with categorical type constructors. In ATABLE'92 Proceedings of a Workshop on Arrays (June), 105-121.
• 20: Colin Roy Banger, Construction of multidimensional arrays as categorical data types, Queen's University, Kingston, Ont., Canada, 1996
• 21: BAUDE, F. 1991. Utilisation du paradigme acteur pour le calcul parall~le. Ph.D. thesis, Universit6 de Paris-Sud.
• 22: Franç Baude , Guy Vidal-Naquet, Actors as a parallel programming model, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.184-195, February 1991, Hamburg, Germany
• 23: BEGUELIN, A., DONGARRA, J., GEIST, A., MANCHEK, R., MOORE, K., AND SUNDERAM, V. 1993. PVM and HENCE: Tools for heterogeneous network computing. In Software for Parallel Computation, NATO ASI Series F., Vol. 106 J.S. Kowalik and L. Grandinetti, Eds. Springer-Verlag, 91-99.
• 24: BEGUELIN, A., DONGARRA, J., GEIST, A., MANCHEK, R., AND SUNDERAM, V. 1995. Recent enhancements to PVM. Int. J. Supercomput. Appl. High Perform. Comput.
• 25: BEGUELIN, A., DONGARRA, J.J., GEIST, G.A., MANCHEK, R., AND SUNDERAM, V.S. PVM software system and documentation. Email to [e-mail].
• 26: Adam Beguelin , Jack Dongarra , Al Geist , Robert Manchek , Steve Otto , Jon Walpole, PVM: Experiences, Current Status and Future Direction, Oregon Graduate Institute School of Science & Engineering, 1994
• 27: Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, PRESTO: a system for object-oriented parallel programming, Software—Practice & Experience, v.18 n.8, p.713-732, August 1988 [doi>10.1002/spe.4380180802]
• 28: BICKFORD, M. 1994. Composable specifications for asynchronous systems using UNITY. In Proceedings International Symposium on Advanced Research in Asynchronous Circuits and Systems (Nov.), 216-227.
• 29: Gianfranco Bilardi , Kieran T. Herley , Andrea Pietracaprina , Geppino Pucci , Paul Spirakis, BSP vs LogP, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.25-32, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237504]
• 30: R. S. Bird, An introduction to the theory of lists, Proceedings of the NATO Advanced Study Institute on Logic of programming and calculi of discrete design, p.5-42, June 1987, Marktoberdorf, Germany
• 31: Andrew Black , Norman Hutchinson , Eric Jul , Henry Levy , Larry Carter, Distributed and abstract types in Emerald, IEEE Transactions on Software Engineering, v.13 n.1, p.65-76, Jan. 1987 [doi>10.1109/TSE.1987.232836]
• 32: BLACK, A. ET AL. 1984. EPL programmers' guide. University of Washington, Seattle, June.
• 33: BLELLOCH, G. 1987. Scans as primitive parallel operations. In Proceedings of the International Conference on Parallel Processing (August), 355-362.
• 34: Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
• 35: Guy E. Blelloch, NESL: A Nested Data-Parallel Language (Version 2.6), Carnegie Mellon University, Pittsburgh, PA, 1993
• 36: Guy E. Blelloch, Programming parallel algorithms, Communications of the ACM, v.39 n.3, p.85-97, March 1996 [doi>10.1145/227234.227246]
• 37: Guy Blelloch , John Greiner, A Parallel Complexity Model for Functional Languages, Carnegie Mellon University, Pittsburgh, PA, 1994
• 38: BLELLOCH, G. E. AND SABOT, G.W. 1988. Compiling collection-oriented languages onto massively parallel computers. In Proceedings of the Second Symposium on the Frontiers of Massively Parallel Computation, 575-585.
• 39: Guy E. Blelloch , Gary W. Sabot, Compiling collection-oriented languages onto massively parallel computers, Journal of Parallel and Distributed Computing, v.8 n.2, p.119-134, February 1990 [doi>10.1016/0743-7315(90)90087-6]
• 40: J. Briat , M. Favre , C. Geyer , J. Chassin de Kergommeaux, Scheduling of OR-parllel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor, Proceedings on Parallel architectures and languages Europe : volume II: parallel languages: volume II: parallel languages, p.385-402, June 1991, Eindhoven, The Netherlands
• 41: BUHR, P.A. AND STROOBOSSCHER, R.A. 1990. The t~System: Providing light-weight concurrency on shared-memory multiprocessor computers running UNIX. Softw. Pract. Exper. 20, 9 (Sept.), 929-963.
• 42: BUHR, P.A., MACDONALD, H.I., AND STROOBOSS- CHER, R.A. 1991. t~System reference manual, version 4.3.3. Tech. Rep., Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1, March.
• 43: BURKHART, H., FALC() KORN, C., GUTZWILLER, S., OHNACKER, P., AND WASER, S. 1993. BACS: Basel algorithm classification scheme. Tech. Rep. 93-3, Institut ffir Informatik der Universit~t Basel, March.
• 44: BUTLER, R. AND LUSK, E. 1992. User's guide to the p4 programming system. Tech. Rep. ANL- 92/17, Argonne National Laboratory, Mathematics and Computer Science Division, October.
• 45: M. Cannataro , S. Di Gregorio , R. Rongo , W. Spataro , G. Spezzano , D. Talia, A parallel cellular automata environment on multicomputers for computational science, Parallel Computing, v.21 n.5, p.803-823, May 1995 [doi>10.1016/0167-8191(94)00099-V]
• 46: CANNATARO, M., SPEZZANO, a., AND TALIA, D. 1991. A parallel logic system on a multicomputer architecture. In Fut. Gen. Comput. Syst. 6, 317-331.
• 47: CARRIERO, N. 1987. Implementation of tuple space machines. Tech. Rep. YALEU/DCS/RR- 567, Department of Computer Science, Yale University, December.
• 48: 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
• 49: CARRIERO, N. AND GELERNTER, D. 1993. Learning from our success. In Software for Parallel Computation, NATO ASI Series F, Vol. 106 J.S. Kowalik and L. Grandinetti, Eds. Springer-Verlag, 37-45.
• 50: K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 51: Jacques Chassin de Kergommeaux , Philippe Codognet, Parallel logic programming systems, ACM Computing Surveys (CSUR), v.26 n.3, p.295-336, Sept. 1994 [doi>10.1145/185403.185453]
• 52: Marina Chen , Young-il Choo , Jingke Li, Crystal: theory and pragmatics of generating efficient parallel code, Parallel functional languages and compilers, ACM Press, New York, NY, 1991 [doi>10.1145/107214.129259]
• 53: Andrew A. Chien, Concurrent aggregates: using multiple-access data abstractions to manage complexity in concurrent programs, ACM SIGPLAN OOPS Messenger, v.2 n.2, p.31-36, Apr. 1991
• 54: A. A. Chien , W. J. Dally, Concurrent aggregates (CA), Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.177-186, March 14-16, 1990, Seattle, Washington, United States
• 55: Andrew Chin , W. F. McColl, Virtual shared memory: algorithms and complexity, Information and Computation, v.113 n.2, p.199-219, Sept. 1994 [doi>10.1006/inco.1994.1069]
• 56: Murray Cole, Algorithmic skeletons: structured management of parallel computation, MIT Press, Cambridge, MA, 1991
• 57: COLE, M. 1990. Towards fully local multicomputer implementations of functional programs. Tech. Rep. CS90/R7, Department of Computing Science, University of Glasgow, January.
• 58: COLE, M. 1992. Writing parallel programs in non-parallel languages. In Software for Parallel Computers: Exploiting Parallelism through Software Environments, Tools, Algorithms and Application Libraries, R. Perrot, Ed., Chapman and Hall, London, 315-325.
• 59: COLE, M. 1994. Parallel programming, list homomorphisms and the maximum segment sum problem. In Parallel Computing: Trends and Applications, G.R. Joubert, Ed., North- Holland, 489-492.
• 60: John S. Conery, Parallel execution of logic programs, Kluwer Academic Publishers, Norwell, MA, 1986
• 61: R. C. B Cooper , K. G. Hamilton, Preserving Abstraction in Concurrent Programming, IEEE Transactions on Software Engineering, v.14 n.2, p.258-263, February 1988 [doi>10.1109/32.4643]
• 62: Christian Creveuil, Implementation of Gamma on the Connection Machine, Research Directions in High-Level Parallel Programming Languages, p.219-230, June 17-19, 1991
• 63: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 64: William J. Dally , D. Scott Wills, Universal Mechanisms for Concurrency, Proceedings of the Parallel Architectures and Languages Europe, Volume I: Parallel Architectures, p.19-33, June 12-16, 1989
• 65: William J. Dally , J. A. Stuart Fiske , John S. Keen , Richard A. Lethin , Michael D. Noakes , Peter R. Nuth , Roy E. Davison , Gregory A. Fyler, The Message-Driven Processor: A Multicomputer Processing Node with Efficient Mechanisms, IEEE Micro, v.12 n.2, p.23-39, March 1992 [doi>10.1109/40.127581]
• 66: DANELUTTO, M., DI MEGLIO, R., ORLANDO, S., PEL- AGATTI, S., AND VANNESCHI, M. 1991a. A methodology for the development and the support of massively parallel programs. Fut. Gen. Comput. Syst. Also appears as "The P3L language: An introduction," Hewlett-Packard Rep. HPL-PSC-91-29, December.
• 67: DANELUTTO, M., DI MEGLIO, R., PELAGATTI, S., AND VANNESCHI, M. 1990. High level language constructs for massively parallel computing. Tech. Rep., Hewlett-Packard Pisa Science Center, HPL-PSC-90-19.
• 68: DANELUTTO, M., PELAGATTI, S., AND VANNESCHI, M. 1991b. High level languages for easy massively parallel computing. Tech. Rep., Hewlett-Packard Pisa Science Center, HPL- PSC-91-16.
• 69: DARLINGTON, J., CRIPPS, M., FIELD, T., HARRISON, P.G., AND REEVE, M.J. 1987. The design and implementation of ALICE: A parallel graph reduction machine. In Selected Reprints on Dataflow and Reduction Architectures, S.S. Thakkar, Ed., IEEE Computer Society Press, Los Alamitos, CA.
• 70: John Darlington , A. J. Field , Peter G. Harrison , Paul H. J. Kelly , D. W. N. Sharp , Q. Wu, Parallel Programming Using Skeleton Functions, Proceedings of the 5th International PARLE Conference on Parallel Architectures and Languages Europe, p.146-160, June 14-17, 1993
• 71: J. Darlington , Y. Guo , Jin Yang, The parallel Fortran family and a new perspective, Proceedings of the conference on Programming Models for Massively Parallel Computers, p.126, October 09-12, 1995
• 72: F. de Dinechin , P. Quinton , T. Risset, Structuration of the ALPHA language, Proceedings of the conference on Programming Models for Massively Parallel Computers, p.18, October 09-12, 1995
• 73: Jack J. Dongarra , Steve W. Otto , Marc Snir , David Walker, An Introduction to the MPI Standard, University of Tennessee, Knoxville, TN, 1995
• 74: Jack J. Dongarra , Steve W. Otto , Marc Snir , David Walker, A message passing standard for MPP and workstations, Communications of the ACM, v.39 n.7, p.84-90, July 1996 [doi>10.1145/233977.234000]
• 75: DOUGLAS, A., ROWSTRON, A., AND WOOD, A. 1995. ISETL-Linda: Parallel programming with bags. Tech. Rep. YCS 257, Department of Computer Science, University of York, UK, September.
• 76: J. Dana Eckart, Cellang 2.0: language reference manual, ACM SIGPLAN Notices, v.27 n.8, p.107-112, Aug. 1992 [doi>10.1145/142137.142166]
• 77: EISENBACH, S. AND PATTERSON, R. 1993. ~r-calculus semantics for the concurrent configuration language Darwin. In Proceedings of 26th Annual Hawaii International Conference on Systern Science (Jan.) Vol. II, IEEE Computer Society Press, Los Alamitos, CA.
• 78: Kattamuri Ekanadham, A perspective on Id, Parallel functional languages and compilers, ACM Press, New York, NY, 1991 [doi>10.1145/107214.129258]
• 79: Barry S. Fagin , Alvin M. Despain, The Performance of Parallel Prolog Programs, IEEE Transactions on Computers, v.39 n.12, p.1434-1445, December 1990
• 80: FAIGLE, C., FURMANSKI, W., HAUPT, T., NIEMIC, J., PODGORNY, M., AND SIMONI, D. 1993. MOVIE model for open systems based high performance distributed computing. Concurrency Pract. Exper. 5, 4 (June), 287-308.
• 81: John E. Faust , Henry M. Levy, The performance of an object-oriented threads package, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.278-288, September 1990, Ottawa, Canada
• 82: David Feldcamp , Alan Wagner, Parsec—a software development environment for performance oriented parallel programming, Proceedings of the sixth conference of the North American Transputer Users Group on Transputer research and applications 6, p.247-262, June 1993, Vancouver, British Columbia, Canada
• 83: FLYNN-HUMMEL, S. AND KELLY, R. 1993. A rationale for parallel programming with sets. J. Program. Lang. 1, 187-207.
• 84: Ian Foster , Stephen Taylor, Strand: new concepts in parallel programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 85: FOSTER, I. AND TUECKE, S. 1991. Parallel programming with PCN. Tech. Rep. ANL-91/32, Rev. 1, Mathematics and Computer Science Division, Argonne National Laboratory, December.
• 86: FOSTER, I., OLSON, R., AND TUECKE, S. 1992. Productive parallel programming: The PCN approach. Sci. Program. 1, 1, 51-66.
• 87: FOSTER, I., TUECKE, S., AND TAYLOR, S. 1991. A portable run-time system for PCN. Tech. Rep. ALMS/MCS-TM-137. Argonne National Laboratory and CalTech, December. Available at ftp ://i nfo. mcs. an l. go v/p u b/t ec h_re ports/.
• 88: N H Gehani , W D Roome, Concurrent C, Software—Practice & Experience, v.16 n.9, p.821-844, Sept. 1986
• 89: G. A. Geist, II, Invited Lecture: PVM 3 Beyong Network Computing, Proceedings of the Second International ACPC Conference on Parallel Computation, p.194-203, October 04-06, 1993
• 90: R. Gerth , A. Pnueli, Rooting UNITY, Proceedings of the 5th international workshop on Software specification and design, p.11-19, April 1989, Pittsburgh, Pennsylvania, United States
• 91: Jeremy Gibbons, Algebras for tree algorithms, 1991
• 92: GOGUEN, J. AND WINKLER, T. 1988. Introducing OBJ3. Tech. Rep. SRI-CSL-88-9, SRI International, Menlo Park, CA, August.
• 93: J. Goguen , C. Kirchner , J. Meseguer , H. Kirchner , T. Winkler , A. Megrelis, An introduction to OBJ 3, 1st international workshop on Conditional Term Rewriting Systems, p.258-263, August 1988, Orsay, France
• 94: GOGUEN, J., WINKLER, T., MESEGUER, J., FUTAT- SUGI, K., AND JOUANNAUD, J.-P. 1993. Introducing OBJ. In Applications of Algebraic Specification using OBJ. J. Gouguen, Ed., Cambridge.
• 95: GOLDMAN, K.J. 1989. Paralation views: Abstractions for efficient scientific computing on the Connection Machine. Tech. Rep. MIT/ LCS/TM398, MIT Laboratory for Computer Science.
• 96: GOTTLIEB, A. ET AL. 1983a. The NYU Ultracomputer--designing an MIMD shared memory parallel computer. IEEE Trans. Comput. C-32 (Feb.), 175-189.
• 97: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• 98: Steve Gregory, Parallel logic programming in PARLOG: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 99: Andrew S. Grimshaw, An Introduction to Parallel Object-Oriented Programming with Mentat, University of Virginia, Charlottesville, VA, 1991
• 100: Andrew S. Grimshaw, Easy-to-Use Object-Oriented Parallel Processing with Mentat, Computer, v.26 n.5, p.39-51, May 1993 [doi>10.1109/2.211896]
• 101: Andrew S. Grimshaw, The Mentat Computation Model Data-Driven Support for Object-Oriented Parallel Processing, University of Virginia, Charlottesville, VA, 1993
• 102: GRIMSHAW, A.S., LOYOT, E.C., AND WEISSMAN, J.B. 1991a. Mentat programming language. MPL Reference Manual 91-32, University of Virginia, 3 November.
• 103: GRIMSHAW, A. S., LOYOT, E. C., SMOOTAND, S., AND WEISSMAN, J.B. 1991b. Mentat user's manual. Tech. Rep. 91-31, University of Virginia, 3 November 1991.
• 104: Gaétan Hains , Christian Foisy, The Data-Parallel Categorical Abstract Machine, Proceedings of the 5th International PARLE Conference on Parallel Architectures and Languages Europe, p.56-67, June 14-17, 1993
• 105: Per Brinch Hansen, Distributed processes: a concurrent programming concept, Communications of the ACM, v.21 n.11, p.934-941, Nov. 1978 [doi>10.1145/359642.359651]
• 106: Philip J. Hatcher , Michael J. Quinn, Data-parallel programming on MIMD computers, MIT Press, Cambridge, MA, 1992
• 107: HEINZ, E.A. 1993. Modula-3*: An efficiently compilable extension of Modula-3 for problemoriented explicitly parallel programming. In Proceedings of the Joint Symposium on Parallel Processing 1993 (Waseda University, Tokyo, May), 269-276.
• 108: HEMPEL, R. 1991. The ANL/GMD macros (PAR- MACS) in FORTRAN for portable parallel programming using the message passing programming model--users' guide and reference manual. Tech. Rep., GMD, Postfach 1316, D-5205 Sankt Augustin 1, Germany, November.
• 109: HEMPEL, R., HOPPE, H.-C., AND SUPALOV, A. 1992. PARMACS-6.0 library interface specification. Tech. Rep., GMD, Postfach 1316, D-5205 Sankt Augustin 1, Germany, December.
• 110: J. Herath , T. Yuba , N. Saito, Dataflow computing, Proc. of an international workshop on Parallel algorithms and architectures, p.25-36, July 1987, Suhl, Germany
• 111: HIGH PERFORMANCE FORTRAN LANGUAGE SPECIFICATION 1993. Available by ftp from titan.rice.cs.edu, January.
• 112: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 113: Paul Hudak, Para-functional programming, Computer, v.19 n.8, p.60-69, Aug. 1986 [doi>10.1109/MC.1986.1663309]
• 114: Paul Hudak , Joseph H. Fasel, A gentle introduction to Haskell, ACM SIGPLAN Notices, v.27 n.5, p.1-52, May 1992 [doi>10.1145/130697.130698]
• 115: HUMMEL, R., KELLY, R., AND FLYNN-HUMMEL, S. 1991. A set-based language for prototyping parallel algorithms. In Proceedings of the Computer Architecture for Machine Perception '91 Conference (Dec.).
• 116: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 117: C. Barry Jay, A semantics for shape, Science of Computer Programming, v.25 n.2-3, p.251-283, Dec. 1995
• 118: JERID, L., ANDRE, F., CHERON, O., PAZAT, J. L., AND ERNST, T. 1994. HPF to C-PANDORE translator. Tech. Rep. 824, IRISA: Institut de Recherche en Informatique et Systemes Aleatoires, May.
• 119: Geraint Jones, Programming in Occam, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1986
• 120: Robert H Halstead, Jr., Parallel symbolic computing, Computer, v.19 n.8, p.35-43, Aug. 1986 [doi>10.1109/MC.1986.1663306]
• 121: KALE, L.V. 1987. The REDUCE-OR process model for parallel evaluation of logic programs. In Proceedings of the Fourth International Conference on Logic Programming (Melbourne, Australia), 616-632.
• 122: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 123: Paul H. Kelly, Functional Programming for Loosely-Coupled Multiprocessors, MIT Press, Cambridge, MA, 1989
• 124: C. W. Kessler , H. Seidl, Integrating synchronous and asynchronous paradigms: the Fork95 parallel programming language, Proceedings of the conference on Programming Models for Massively Parallel Computers, p.134, October 09-12, 1995
• 125: KILIAN, M.F. 1992a. Can O-O aid massively parallel programming? In Proceedings of the Dartmouth Institute for Advanced Graduate Study in Parallel Computation Symposium D. B. Johnson, F. Makedon, and P. Metaxas, Eds. (June), 246-256.
• 126: Michael Kilian, Parallel sets: an object-oriented methodology for massively parallel programming, Harvard University, Cambridge, MA, 1992
• 127: WooYoung Kim , Gul Agha, Efficient support of location transparency in concurrent object-oriented programming languages, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.39-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224297]
• 128: Donald E. Knuth, Big Omicron and big Omega and big Theta, ACM SIGACT News, v.8 n.2, p.18-24, April-June 1976 [doi>10.1145/1008328.1008329]
• 129: KUNG, H.T. 1982. Why systolic architectures? IEEE Comput. 15, 1, 37-46.
• 130: LARUS, J.R., RICHARDS, B., AND VISWANATHAN, G. 1992. C**: A large-grain, object-oriented, data-parallel programming language. Tech. Rep. TRl126, University of Wisconsin- Madison, November.
• 131: Douglas Lea , Doug Lea, Concurrent Programming in Java: Design Principles and Patterns, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 132: Ulrike Lechner , Christian Lengauer , Martin Wirsing, An Object-Oriented Airport: Specification and Refinement in Maude, Selected papers from the 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop on Recent Trends in Data Type Specification, p.351-367, May 30-June 03, 1994
• 133: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• 134: LINCOLN, P., MARTi-OILIET, N., AND MESEGUER, J. 1994. Specification, transformation, and programming of concurrent systems in rewriting logic. Tech. Rep. SRI-CSL-94-11, SRI, May.
• 135: B. Liskov , D. Curtis , P. Johnson , R. Scheifer, Implementation of Argus, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.111-122, November 08-11, 1987, Austin, Texas, United States
• 136: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• 137: LOBE, G., Lu, P., MELAX, S., PARSONS, I., SCHAEF- FER, J., SMITH, C., AND SZAFRON, D. 1992. The Enterprise model for developing distributed applications. Tech. Rep. 92-20, Department of Computing Science, University of Alberta, November.
• 138: MALCOLM, G. 1990. Algebraic data types and program transformation. Ph.D. Thesis, Rijksuniversiteit Groningen, September.
• 139: W. F. McColl, General purpose parallel computing, Lectures on parallel computation, Cambridge University Press, New York, NY, 1993
• 140: W. F. McColl, Special purpose parallel computing, Lectures on parallel computation, Cambridge University Press, New York, NY, 1993
• 141: W. F. McColl, Bulk synchronous parallel computing, Abstract machine models for highly parallel computers, Oxford University Press, Oxford, 1995
• 142: MCCOLL, W.F. 1994b. An architecture independent programming model for scalable parallel computing. In Portability and Performance for Parallel Processors, J. Ferrante and A. J. G. Hey, Eds., Wiley, New York.
• 143: MCGRAW, J., SKEDZIELEWSKI, S., ALLAN, S., OLDE- HOEFT, R., GLAUERT, J., KIRKHAM, C., NOYCE, B., AND THOMAS, R. 1985. Sisal: Streams and iteration in a single assignment language: Reference manual 1.2. Tech. Rep. M-146, Rev. 1, Lawrence Livermore National Laboratory, March.
• 144: MCGRAW, J.R. 1993. Parallel functional programming in Sisal: Fictions, facts, and future. In Advanced Workshop, Programming Tools for Parallel Machines (June). Also available as Laurence Livermore National Laboratories Tech. Rep. UCRL-JC-114360.
• 145: Piyush Mehrotra , Matthew Haines, AN OVERVIEW OF THE OPUS LANGUAGE AND RUNTIME SYSTEM, Institute for Computer Applications in Science and Engineering (ICASE), 1994
• 146: MENTAT 1994. Mentat tutorial. Available at ftp ://uv acs. cs. vi r g i n ia. ed u/p u b/m e ntat/t uto ri al. ps.Z.
• 147: MESEGUER, J. 1992. A logical theory of concurrent objects and its realization in the Maude language. Tech. Rep. SRI-CSL-92-08, SRI International, July.
• 148: José Meseguer , Timothy C. Winkler, Parallel Programmming in Maude, Research Directions in High-Level Parallel Programming Languages, p.253-293, June 17-19, 1991
• 149: CORPORATE The MPI Forum, MPI: a message passing interface, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.878-883, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169855]
• 150: MORE, T. 1986. On the development of array theory. Tech. Rep., IBM Cambridge Scientific Center.
• 151: Bodhisattwa Mukherjee , Greg Eisenhauer , Kaushik Ghosh, A machine independent interface for lightweight threads, ACM SIGOPS Operating Systems Review, v.28 n.1, p.33-47, Jan. 1994 [doi>10.1145/164853.164864]
• 152: MULLIN, L. M.R. 1988. A mathematics of arrays. Ph.D. Dissertation, Syracuse University, Syracuse, NY, December.
• 153: David A Mundie , David A Fisher, Parallel processing in Ada, Computer, v.19 n.8, p.20-25, Aug. 1986 [doi>10.1109/MC.1986.1663304]
• 154: Louis Mussat, Parallel Programming with Bags, Research Directions in High-Level Parallel Programming Languages, p.203-218, June 17-19, 1991
• 155: Peter Newton , James C. Browne, The CODE 2.0 graphical parallel programming language, Proceedings of the 6th international conference on Supercomputing, p.167-177, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143405]
• 156: Michael Noakes , William J. Dally, System design of the J-Machine, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.179-194, March 1990, Boston, Massachusetts, United States
• 157: PEIERLS, R. AND CAMPBELL, G. 1991. ALMS-- programming tools for coupling application codes in a network environment. In Proceedings of the Heterogeneous Network-Based Concurrent Computing Workshop (Tallahassee, FL, Oct.). Supercomputing Computations Research Institute, Florida State University. Proceedings available via anonymous ftp from ftp.scri.fsu.edu in directory pub/parallel-workshop.91.
• 158: PEREIRA, L.M. AND NASR, R. 1984. Delta-Prolog: A distributed logic programming language. In Proceedings of the International Conference on Fifth Generation Computer Systerns (Tokyo, Nov.), 283-291.
• 159: PEYTON-JONES, S.L., CLACK, C., AND HARRIS, N. 1987. GRIP--a parallel graph reduction machine. Tech. Rep., Department of Computer Science, University of London.
• 160: Simon L. Peyton Jones , David R. Lester, Implementing functional languages, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 161: Michael J. Quinn , Philip J. Hatcher, Data-Parallel Programming on Multicomputers, IEEE Software, v.7 n.5, p.69-76, September 1990 [doi>10.1109/52.57894]
• 162: Fethi A. Rabhi , Gordon A. Manson, Experiments with a transputer-based parallel graph reduction machine, Concurrency: Practice and Experience, v.3 n.4, p.413-422, Aug. 1991 [doi>10.1002/cpe.4330030417]
• 163: Matthias Radestock , Susan Eisenbach, What Do You get From a Pi-Calculus Semantics?, Proceedings of the 6th International PARLE Conference on Parallel Architectures and Languages Europe, p.635-647, July 04-08, 1994
• 164: S. Radha , C. R. Muthukrishnan, A portable implementation of UNITY on von Neumann machines, Computer Languages, v.18 n.1, p.17-30, 1993 [doi>10.1016/0096-0551(93)90028-Y]
• 165: RAINA, S. 1990. Software controlled shared virtual memory management on a transputer based multiprocessor. In Transputer Research and Applications 4, D.L. Fielding, Ed., IOS Press, Amsterdam, 143-152.
• 166: Abhiram Gorakhanath Ranade, Fluent parallel computation, 1989
• 167: Gary W. Sabot, The Paralation Model: Architecture-Independent Parallel Programming, MIT Press, Cambridge, MA, 1989
• 168: Vijay A. Saraswat , Martin Rinard , Prakash Panangaden, The semantic foundations of concurrent constraint programming, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-352, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99627]
• 169: SEUTTER, F. 1985. CEPROL, a cellular programming language. Parallel Comput. 2, 327- 333.
• 170: Ehud Shapiro, Concurrent Prolog: A progress report, Computer, v.19 n.8, p.44-58, Aug. 1986 [doi>10.1109/MC.1986.1663307]
• 171: Ehud Shapiro, The family of concurrent logic programming languages, ACM Computing Surveys (CSUR), v.21 n.3, p.413-510, Sep. 1989 [doi>10.1145/72551.72555]
• 172: Thomas Jay Sheffler, Match and move: an approach to data parallel computing, Carnegie Mellon University, Pittsburgh, PA, 1992
• 173: SINGH, P. 1993. Graphs as a categorical data type. Master's Thesis, Computing and Information Science, Queen's University, Kingston, Canada.
• 174: Stephen K. Skedzielewski, Sisal, Parallel functional languages and compilers, ACM Press, New York, NY, 1991 [doi>10.1145/107214.129256]
• 175: David B. Skillicorn, Architecture-Independent Parallel Computation, Computer, v.23 n.12, p.38-50, December 1990 [doi>10.1109/2.62092]
• 176: D. B. Skillicorn, Categorical data types, Abstract machine models for highly parallel computers, Oxford University Press, Oxford, 1995
• 177: David Skillicorn, Foundations of parallel programming, Cambridge University Press, New York, NY, 1995
• 178: D. B. Skillicorn, Communication skeletons, Abstract machine models for parallel and distributed computing, IOS Press, Amsterdam, The Netherlands, 1997
• 179: D. B. Skillicorn , W. Cai, A cost calculus for parallel functional programming, Journal of Parallel and Distributed Computing, v.28 n.1, p.65-83, July 1995 [doi>10.1006/jpdc.1995.1089]
• 180: David B. Skillicorn , Domenico Talia, Programming languages for parallel processing, IEEE Computer Society Press, Los Alamitos, CA, 1995
• 181: SKILLICORN, D.B., HILL, J. M. D., AND MCCOLL, W.F. 1997. Questions and answers about BSP. Sci. Program. 6, 3, 249-274.
• 182: SPEZZANO, G. AND TALIA, D. 1997. A high-level cellular programming model for massively parallel processing. In Proceedings of the Second International Workshop on High-Level Programming Models and Supportive Environments, HIPS'97, IEEE Computer Society Press, Los Alamitos, CA, 55-63.
• 183: J. Michael Spivey, A Categorial Approch to the Theory of Lists, Proceedings of the International Conference on Mathematics of Program Construction, 375th Anniversary of the Groningen University, p.399-408, June 26-30, 1989
• 184: Guy L. Steele, Jr., High performance Fortran: status report, ACM SIGPLAN Notices, v.28 n.1, p.1-4, Jan. 1993 [doi>10.1145/156668.156670]
• 185: SUNDERAM, V. 1992. Concurrent computing with PVM. In Proceedings of the Workshop on Cluster Computing (Tallahassee, FL, Dec.). Supercomputing Computations Research Institute, Florida State University. Proceedings available via anonymous ftp from ftp.scri.fsu. edu in directory pub/parallel-workshop.92.
• 186: 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]
• 187: Daniel C. Swinehart , Polle T. Zellweger , Robert B. Hagmann, The structure of Cedar, ACM SIGPLAN Notices, v.20 n.7, p.230-244, July 1985
• 188: SZAFRON, D., SCHAEFFER, J., TONG, P. S., CHAN, E., LU, P., AND SMITH, C. 1991. Enterprise: An interactive graphical programming environment for distributed software. Available by ftp from cs.ualberta.ca.
• 189: Domenico Talia, A survey of PARLOG and concurrent PROLOG: the integration of logic and parallelism, Computer Languages, v.18 n.3, p.185-196, 1993 [doi>10.1016/0096-0551(93)90024-U]
• 190: TALIA, D. 1994. Parallel logic programming systerns on multicomputers. J. Program. Lang. 2, 1 (March), 77-87.
• 191: THOMPSON, S.J. 1992. Formulating Haskell. Tech. Rep. No. 29/92, Computing Laboratory, University of Kent, Canterbury, UK.
• 192: Chau-Wen Tseng, An optimizing Fortran D compiler for MIMD distributed-memory machines, Rice University, Houston, TX, 1993
• 193: UEDA, K. 1985. Guarded Horn clauses. Tech. Rep. TR-103, ICOT, Tokyo.
• 194: VALIANT, L.G. 1989. Bulk synchronous parallel computers. Tech. Rep. TR-08-89, Computer Science, Harvard University.
• 195: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 196: L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 197: VAN HENTENRYCK, P. 1989. Parallel constraint satisfaction in logic programming: Preliminary results of Chip within PEPSys. In Proceedings of the Sixth International Congress on Logic Programming, MIT, Cambridge, MA, 165-180.
• 198: VIOLARD, E. 1994. A mathematical theory and its environment for parallel programming. Parallel Process. Lett. 4, 3, 313-328.
• 199: Takuo Watanabe , Akinori Yonezawa, Reflection in an object-oriented concurrent language, ACM SIGPLAN Notices, v.23 n.11, p.306-315, Nov. 1988
• 200: WILKINSON, T., STIEMERLING, T., OSMON, P., SAULS- BURY, A., AND KELLY, P. 1992. Angel: A proposed multiprocessor operating system kernel. In Proceedings of the European Workshops on Parallel Computing (EWPC'92), (Barcelona, March 23-24) 316-319.
• 201: Donald S Wills, Pi: A Parallel Architecture Interface for Multi-Model Execution, Massachusetts Institute of Technology, Cambridge, MA, 1990
• 202: Timothy C. Winkler, Programming in OBJ and Maude, Functional Programming, Concurrency, Simulation and Automated Reasoning: International Lecture Series 1991-1992, McMaster University, Hamilton, Ontario, Canada, p.229-277, January 1993
• 203: J. Allan Yang , Young-il Choo, Parallel-program transformation using a metalanguage, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.11-20, April 21-24, 1991, Williamsburg, Virginia, United States
• 204: J. Allan Yang , Young-il Choo, Formal Derivation of an Efficient Parallel 2-D Gauss-Siedel Method, Proceedings of the 6th International Parallel Processing Symposium, p.204-207, March 01, 1992
• 205: YANG, A. AND CHOO, Y. 1992b. Metalinguistic features for formal parallel-program transformation. In Proceedings of the Fourth IEEE International Conference on Computer Languages (April), IEEE Computer Society Press, Los Alamitos, CA.
• 206: Yasuhiko Yokote , Mario Tokoro, Concurrent programming in concurrent Smalltalk, Object-oriented concurrent programming, MIT Press, Cambridge, MA, 1987
• 207: Akinori Yonezawa , Mario Tokoro, Object-oriented concurrent programming, MIT Press, Cambridge, MA, 1987
• 208: ZENITH, S.E. 1991a. The axiomatic characterization of Ease. In Linda-Like Systems and their Implementation, Edinburgh Parallel Computing Centre, TR91-13, 143-152.
• 209: Steven Ericsson Zenith, A Rationale for Programming with Ease, Research Directions in High-Level Parallel Programming Languages, p.147-156, June 17-19, 1991
• 210: ZENITH, S.E. 1991c. Programming with Ease. Centre de Recherche en Informatique, I~cole Nationale Sup~rieure des Mines de Paris, Sept. 20.
• 211: Steven Ericsson Zenith, Ease; the model and its implementation, ACM SIGPLAN Notices, v.28 n.1, p.87, Jan. 1993 [doi>10.1145/156668.156710]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES

General Terms:
Languages, Performance, Theory

Keywords:
general-purpose parallel computation, logic programming languages, object-oriented languages, parallel programming languages, parallel programming models, software development methods, taxonomy