MULTILISP: a language for concurrent symbolic computation

ABSTRACT

Multilisp is a version of the Lisp dialect Scheme extended with constructs for parallel execution. Like Scheme, Multilisp is oriented toward symbolic computation. Unlike some parallel programming languages, Multilisp incorporates constructs for causing side effects and for explicitly introducing parallelism. The potential complexity of dealing with side effects in a parallel context is mitigated by the nature of the parallelism constructs and by support for abstract data types: a recommended Multilisp programming style is presented which, if followed, should lead to highly parallel, easily understandable programs. Multilisp is being implemented on the 32-processor Concert multiprocessor; however, it is ultimately intended for use on larger multiprocessors. The current implementation, called Concert Multilisp, is complete enough to run the Multilisp compiler itself and has been run on Concert prototypes including up to eight processors. Concert Multilisp uses novel techniques for task scheduling and garbage collection. The task scheduler helps control excessive resource utilization by means of an unfair scheduling policy; the garbage collector uses a multiprocessor algorithm based on the incremental garbage collector of Baker.

REFERENCES

• 2: W. B. Acherman , J. B. Dennis , William B Ackerman, VAL- ORIENTED ALGORITHMIC LANGUAGE, PRELIMINARY REFERENCE MANUAL, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 3: T. L. Anderson, THE DESIGN OF A MULTIPROCESSOR DEVELOPMENT SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1982
• 4: ARVIND, GOSTELOW, $. G., AND PLOUrFE, W. An Asynchronous Programming Langauge and Computing Machine. Rep. TR114a, University of California, Irvine, 1978.
• 5: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 6: H. G. Baker, ACTOR SYSTEMS FOR REAL-TIME COMPUTATION, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 7: Henry G. Baker, Jr. , Carl Hewitt, The Incremental Garbage Collection of Processes, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 8: BBN. Development of a Voice Funnel System: Quarterly Technical Report. BBN Reports 4845 (Jan. 1982) and 5284 (Apr. 1983). Bolt, Beranek, and Newman, Cambridge, Mass.
• 9: BOUKNIGHT, W. J., ET AL. The Illiac IV system. Proc. IEEE 60, 4 (Apr. 1972), 369-388.
• 10: Frederick P. Brooks, Jr., The Mythical Man-Month: Essays on Softw, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 11: COHEN, S., ROSNER, R., ANO ZIDON, A. Paralisp Simulator (reference manual). Hebrew University Computer Science Dep. Res. Rep. 83-2, Jerusalem, Israel, Jan. 1983.
• 12: CORRELL, S. 8-1 uniprocessor architecture. S-1 Project 1979 Annual Report. Lawrence Livermore National Lab., Livermore, Calif., 1979.
• 13: DEMINET, J. Experience with multiprocessor algorithms. IEEE Trans. Comput. C-31, 4 (Apr. 1982), 278-288.
• 14: Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
• 15: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , Carel S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Language Hierarchies and Interfaces, International Summer School, p.43-56, July 23-August 02, 1975
• 16: FODERARO, J. K., SKLOWER, K., AND LAYER, K. The Franz Lisp Manual. University of California UNIX distribution, 1983.
• 17: FRIEDMAN, D., AND WISE, D. Aspects of applicative programming for parallel processing. IEEE Trans. Comput. C-27, 4 (Apr. 1978), 289-296.
• 18: FRIEDMAN, D., AND WLSE, D. CONS should not evaluate its arguments. In S. Michaelson and R. Milner (Eds.), Automata, Languages and Programming, Edinburgh University Press, Edinburgh, 1976, pp. 257-284.
• 19: Richard P. Gabriel , John McCarthy, Queue-based multi-processing LISP, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.25-44, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802019]
• 20: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 21: GOTTLIEB, A., ET AL. The NYU ultracomputer--Designing an MIMD shared memory parallel computer. IEEE Trans. Comput. C-32, 2 (Feb. 1983), 175-189.
• 22: 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]
• 23: J. R Gurd , C. C Kirkham , I. Watson, The Manchester prototype dataflow computer, Communications of the ACM, v.28 n.1, p.34-52, Jan. 1985 [doi>10.1145/2465.2468]
• 24: HALSTEAD, R. Architecture of a myriaprocessor. In IEEE COMPCON Spring 81 (San Francisco, Feb. 1981), 299-302.
• 25: HALSTEAD, R. Architecture of a myriaprocessor. In J. Solinsky (Ed.), Advanced Computer Concepts. La JoIla Institute, La Jolla, Calif., 1981.
• 26: Robert H. Halstead, Jr., Implementation of multilisp: Lisp on a multiprocessor, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.9-17, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802017]
• 27: HALSTEAD, R. Reference Tree Networks: Virtual Machine and Implementation. M.I.T. Laboratory for Computer Science Tech. Rep. TR-222, Cambridge, Mass., July 1979.
• 28: HALSTEAD, R., AND LOAIZA, J. Exception handling in Multilisp. Presented at the 1985 Int. Conf. Parallel Processing (St. Charles, Ill., Aug. 1985).
• 29: Christopher T. Haynes , Daniel P. Friedman , Mitchell Wand, Continuations and coroutines, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.293-298, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802046]
• 30: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 31: HEWITT, C. Viewing control structures as patterns of passing messages. Working Paper 92, Artificial Intelligence Laboratory, M.I.T., Cambridge, Mass., Apr. 1976.
• 32: 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]
• 33: 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]
• 34: J. D. Ichbiah, Preliminary Ada reference manual, ACM SIGPLAN Notices, v.14 n.6a, p.1-145, June 1979 [doi>10.1145/956650.956651]
• 35: IEEE Task P796/D2. Proposed microcomputer system 796 bus standard. IEEE Comput. 13, 10 (Oct. 1980), 89-105.
• 36: KELLSR, R. Redifiow multiprocessing. IEEE COMPCON Spring 84 (San Francisco, Feb. 1984).
• 37: KELLER, R., AND LIN, F. Simulated performance of a reduction-based multiprocessor. IEEE Comput. 17, 7 (July 1984), 70-82.
• 38: KERN1OHAN, B., AND RITCHIE, D. The C Programming Langauge. Prentice-Hall, Englewood Cliffs, N.J., 1978.
• 39: KNUEVEN, P., HIBBARD, P., AND LEVERETT, B. A language system for a multiprocessor environment. In Proc. 4th Int. Conf. Design and Implementation of Algorithmic Languages (Courant Institute of Mathematical Studies, New York, June 1976), 264-274.
• 40: KUCK, D., MURAOKA, Y., AND CHEN, S.-C. On the number of operations simultaneously executable in Fortran-like programs and their resulting speedup. }EEE Trans. Comput. C-21, 12 (Dec. 1972), 1293-1310.
• 41: Butler W. Lampson , Robert F. Sproull, An open operating system for a single-user machine, Proceedings of the seventh ACM symposium on Operating systems principles, p.98-105, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806575]
• 42: Jed Marti , John Fitch, The Bath concurrent LISP machine, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.78-90, March 28-30, 1983
• 43: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 44: MCGRAW, J., ET AL. SISAL--Streams and Iteration in a Single-Assignment Language. Language Reference Manual (version 1.0), Lawrence Livermore National Lab., Livermore, Calif., July 1983.
• 45: MOLLER-NIELSEN, P., AND STAUNSTRUP, J. Experiments with a Multiprocessor. Tech. Rep. PB-185, Aarhus University Computer Science Dep., Aarhus, Denmark, Nov. 1984.
• 46: RETTBERG, R., ET AL. Development of a Voice Funnel System: Design Report. BBN Rep. 4088, Bolt, Beranek, and Newman, Cambridge, Mass., Aug. 1979.
• 47: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 48: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 49: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• 50: S~APIRO, E.Y. A Subset of Concurrent Prolog and Its Interpreter. Institute for New Generation Computer Technology Tech. Rep. TR-003, Jan. 1983.
• 51: SMITH, B. J. A pipelined, shared resource MIMD computer. In Proc. Int. Conf. Parallel Processing, 1978.
• 52: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 53: SUGIMOTO, S., ET AL. A multimicroprocessor system for concurrent Lisp. In Proc. 1983 Int. Conf. Parallel Processing (June 1983).
• 54: TURNER, D. A new implementation technique for applicative languages. Softw. Pract. Exper. 9, 1 (Jan. 1979), 31-49.
• 55: Daniel Weinreb, Lisp machine manual, Massachusetts Institute of Technology, 1981
• 56: WENG, K. Stream-Oriented Computation in Recursive Data Flow Schemas. Tech. Memo TM-68, M.I.T. Laboratory for Computer Science, Cambridge, Mass., Oct. 1975.

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: MULTILISP; LISP; SCHEME
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Design, Languages, Performance