Overview of concert multilisp: a multiprocessor symbolic computing system

ABSTRACT

Multilisp is a parallel programming language derived from the Scheme dialect of Lisp by addition of the future construct. Multilisp has been implemented on Concert, a shared-memory muitiprocessor that uses a novel RingBus interconnection. Concert currently has 28 MC68000 processors, with a design goal of 32 processors. Several application programs have been developed and measured using Concert Multilisp. Experience with these programs has contributed to tuning the Multilisp language design and will ultimately contribute to the design of a parallel architecture streamlined for high performance on Multilisp programs.

REFERENCES

• 1: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 2: T. L. Anderson, THE DESIGN OF A MULTIPROCESSOR DEVELOPMENT SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1982
• 3: 3. Arvind, K. Gostelow, and W. Plouffe, An Asynchronous Programming Language and Computing Machine, U.C. Irvine Report TR114a, 1978.
• 4: 4. Back, H. J., Parallel Retrieval Algorithms for Semantic Nets, S.B. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., June 1986.
• 5: Henry G. Baker, Jr. , Carl Hewitt, The Incremental Garbage Collection of Processes, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 6: 6. Bradley, E., Logic Simulation on a Multiprocessor, S.M. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., June 1986.
• 7: 7. Courtemanche, A., MultiTrash, a Parallel Garbage Collector for MultiScheme, S.B. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., Jan. 1986.
• 8: 8. Dennis, J. B., "Data Flow Supercomputers," IEEE Computer 13:11, Nov. 1980, pp. 48-56.
• 9: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 10: 10. Gray, S., Using Futures to Exploit Parallelism in Lisp, S.M. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., Jan. 1986.
• 11: 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]
• 12: 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]
• 13: 13. Halstead, R., and J. Loaiza, "Exception Handling in Multilisp," 1985 Int'l. Conf. on Parallel Processing, St. Charles, III., Aug. 1985, pp. 822-830.
• 14: R. R. Halstead, Jr. , T. L. Anderson , R. B. Osborne , T. L. Sterling, Concert: design of a multiprocessor development system, Proceedings of the 13th annual international symposium on Computer architecture, p.40-48, June 02-05, 1986, Tokyo, Japan
• 15: Robert H Halstead, Jr., Parallel Symbolic Computing, Computer, v.19 n.8, p.35-43, August 1986 [doi>10.1109/MC.1986.1663306]
• 16: 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]
• 17: 17. Katz, M., ParaTran: A Transparent, Transaction Based Runtime Mechanism for Parallel Execution of Scheme, S.M. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., May 1986.
• 18: 18. Keller, R., and F. Lin, "Simulated Performance of a Reduction-Based Multiprocessor," IEEE Computer 17:7, July 1984, pp. 70-82.
• 19: Tom Knight, An architecture for mostly functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.105-112, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319854]
• 20: 20. Knueven, P., P. Hibbard, and B. Leverett, "A Language System for a Multiprocessor Environment," Fourth International Conf. on the Design and Implementation of Algorithmic Languages, Courant Institute of Mathematical Studies, New York, June 1976, pp. 264-274.
• 21: Edward J Krall , Patrick F McGehearty, A case study of parallel execution of a rule-based expert system, International Journal of Parallel Programming, v.15 n.1, p.5-32, Feb. 1986 [doi>10.1007/BF01379148]
• 22: 22. Lau, W., Lexical Analysis of Noisy Phonetic Transcriptions, S.M. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., Feb. 1986.
• 23: 23. Ma, M., Efficient Message-Based System for Concurrent Simulation, Ph.D. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., in preparation.
• 24: 24. Miller, J., MultiScheme: A Parallel Processing System Based on MIT Scheme, Ph.D. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., in preparation.
• 25: 25. Nuth, P., A Processor for Multilisp, S.M. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., in preparation.
• 26: 26. Osborne, R., Modeling the Performance of the Concert Multiprocessor, S.M. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., June 1986.
• 27: 27. Solomon, S., A Query Language on a Parallel Machine Operating System, S.B. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., May 1985.
• 28: 28. Turner, D., "A New Implementation Technique for Applicative Languages," Software -- Practice and Experience 9:1, Jan. 1979, pp. 31-49.
• 29: 29. Wang, A., Exploiting Parallelism in Lisp Programs with Side Effects, S.B. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., May 1986.

INDEX TERMS

Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

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

          Nouns: MULTILISP

General Terms:
Design, Languages