Speculative computation in multilisp

ABSTRACT

We present experimental evidence that performing computations in parallel before their results are known to be required can yield performance improvements over conventional approaches to parallel computing. We call such eager computation of expressions speculative computation, as opposed to conventional mandatory computation that is used in almost all contemporary parallel programming languages and systems. The two major requirements for speculative computation are: 1) a means to control computation to favor the most promising computations and 2) a means to abort computation and reclaim computation resources. We discuss these requirements in the parallel symbolic language Multilisp and present a sponsor model for speculative computation in Multilisp which handles control and reclamation of computation in a single, elegant framework. We outline an implementation of this sponsor model and present performance results for several applications of speculative computation. The results demonstrate that our support for speculative computation adds expressive and computational power to Multilisp, with observed performance improvement as great as 26 times over conventional approaches to parallel computation.

REFERENCES

• Bur85: F.W. Burton. Speculative computation, parallelism, and functional programming. IEEE Trans. on Computers, pages 1190-1193, December 1985.
• CG87: K. Clark , S. Gregory, PARLOG: Parallel programming in logic, Concurrent Prolog, MIT Press, Cambridge, MA, 1988
• CSM88: T. Chikayama, H. Sato, and T. Miyazaki. Overview of the parallel inference machine operating system (PIMOS). In Int'l. Con/. on Fifth Generation Computer Systems, pages 230-251, 1988.
• Eps89: B. Epstein. Support for speculative computation in MultiScheme. Bachelor's Thesis, Brandeis University, May 1989.
• Gab85: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• GG89: Ron Goldman , Richard P. Gabriel, Qlisp: Parallel Processing in Lisp, IEEE Software, v.6 n.4, p.51-59, July 1989 [doi>10.1109/52.31652]
• GP81: Dale H. Grit , Rex L. Page, Deleting Irrelevant Tasks in an Expression-Oriented Multiprocessor System, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.1, p.49-59, Jan. 1981 [doi>10.1145/357121.357125]
• Hal85: 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]
• HAOS86: 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
• HK82: Paul Hudak , Robert M. Keller, Garbage collection and task deletion in distributed applicative processing systems, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.168-178, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802147]
• KH81: W. Kornfeld and C. Hewitt. The scientific community metaphor. IEEE Trans. on Systems, Man, and Cybernetics, pages 24-33, January 1981.
• KHM89: D. A. Kranz , R. H. Halstead, Jr. , E. Mohr, Mul-T: a high-performance parallel Lisp, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.81-90, June 19-23, 1989, Portland, Oregon, United States
• KM86: 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]
• Lus88: E. Lusk et al. The Aurora Or-parallel Prolog system. In Proc. of Int'l. Conf. on Fifth Generation Computer Systems, pages 819-830, 1988.
• Mil87: J. Miller. MultiScheme: A parallel processing system based on MIT Scheme. Technical Report TR-402, L~boratory for Computer Science, M.I.T., September 1987.
• Nil80: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• Osb89: R. Osborne. Speculative computation in Multilisp. Technical Report TR-464, Laboratory for Computer Science, M.I.T., November 1989.
• Osb90: Randy B. Osborne, Speculative Computation in Multilisp, Proceedings of the US/Japan Workshop on Parallel Lisp: Languages and Systems, p.103-137, June 05-08, 1989
• PD89: A. Partridge and A. Dekker. Speculative parallelism in a distributed graph reduction machine. In Bruce Shriver, editor, Proceedings of ~r~d An. nual Hawaii Int'l Conf. on System Sciences, Volume 2, pages 771-779, 1989.
• Sha87: E. Shapiro, Concurrent Prolog: a progress report, Concurrent Prolog, MIT Press, Cambridge, MA, 1988
• Sol89: R. Soley. On the efficient exploitation of speculation under datattow paradigms of control. Technical Report Ttk-443, Laboratory for Computer Science, M.I.T., 1989.
• Ued87: K. Ueda, Guarded horn clauses, Concurrent Prolog, MIT Press, Cambridge, MA, 1988

INDEX TERMS

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

          Nouns: MULTILISP

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      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
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Experimentation, Languages, Theory