Implementation of multilisp: Lisp on a multiprocessor

ABSTRACT

Multilisp is an extension of Lisp (more specifically, of the Lisp dialect Scheme [15]) with additional operators and additional semantics to deal with parallel execution. It is being implemented on the 32-processor Concert multiprocessor. The current implementation is complete enough to run the Multilisp compiler itself, and has been run on Concert prototypes including up to four processors. Novel techniques are used 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 modeled after the incremental garbage collector of Baker [2]. A companion paper [9] discusses language design issues relating to Multilisp.

REFERENCES

• 1: T. L. Anderson, THE DESIGN OF A MULTIPROCESSOR DEVELOPMENT SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1982
• 2: H. G. Baker, ACTOR SYSTEMS FOR REAL-TIME COMPUTATION, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 3: Henry G. Baker, Jr. , Carl Hewitt, The Incremental Garbage Collection of Processes, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 4: Cohen, S., R. Rosner, and A. Zidon, "Paralisp Simulator (reference manual)," Hebrew University Computer Science Dept. Research Report 83-2, Jerusalem, Israel, Jan. 1983.
• 5: Dijkstra, E., et al., "On-the-fly Garbage Collection: An Exercise in Co-operation," Language Hierarchies and Interfaces (Lecture Notes in Computer Science 46), Springer-Verlag, 1976.
• 6: Friedman, D., and D. Wise, "Aspects of Applicative Programming for Parallel Processing," IEEE Trans. Comp. C-27:4, April 1978, pp. 289-296.
• 7: Halstead, R., "Architecture of a Myriaprocessor," IEEE COMPCON Spring 81, San Francisco, Feb. 1981, pp. 299-302.
• 8: Halstead, R., "Architecture of a Myriaprocessor," in Advanced Computer Concepts, J. Solinsky, ed., La Jolla Institute, La Jolla, California, 1981.
• 9: Halstead, R., "The Multilisp Language: Lisp for a Multiprocessor," submitted to International Conference on Fifth Generation Computer Systems, Tokyo, Nov. 1984.
• 10: Keller, R., "Rediflow Multiprocessing," IEEE COMPCON Spring 84, San Francisco, Feb. 1984.
• 11: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 12: 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
• 13: 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]
• 14: Sugimoto, S., et al., "A Multi-Microprocessor System for Concurrent Lisp," Proc. 1983 International Conf. on Parallel Processing, June 1983.
• 15: Harold Abelson , Gerald J. Sussman, Structure and Interpretation of Computer Programs, MIT Press, Cambridge, MA, 1996

INDEX TERMS

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

          Nouns: MULTILISP

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

General Terms:
Design, Languages