Parallel execution of sequential scheme with ParaTran

ABSTRACT

This paper describes a system called ParaTran for executing sequential Scheme in parallel. It supports arbitrary side effects without requiring user annotations. The ParaTran runtime system detects and corrects data dependency violations using an automatic history and rollback mechanism. ParaTran is first described by analogy with Time Warp, a system for distributed simulation; this description is followed by a discussion of ParaTran's implementation and presentation of preliminary results.

REFERENCES

• 1: Orna Berry, Performance evaluation of the time warp distributed simulation mechanism, University of Southern California, Los Angeles, CA, 1986
• 2: K.M. Chandy and J. Misra. Distributed simulation: a case study in design and verification of distributed programs. IEEE Transactions on Software Engineering, SE-5(5):440-452, 1979.
• 3: Richard M. Fujimoto. Performance measurements of distributed simulation strategies. In Dislribuied Simulation Conference, Society for Computer Simulation, San Diego, CA, February 1988 (to appear).
• 4: 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]
• 5: 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]
• 6: 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]
• 7: W. Ludwell Harrison IIi. Compiling Lisp for Evaluation on a Tightly Coupled Multiprocessor. PhD thesis, University of Illinois, Urbana- Champaign, March 1986.
• 8: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 9: Morris J. Katz. ParaTran: A Transparent, Transaction Based Runiime Mechanism for Parallel Execution of Scheme. Master's thesis, MIT, Cambridge, MA, June 1986.
• 10: 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]
• 11: D.J. Kuck, R.H. Kuhn, B. Leasure, and M. Wolfe. Analysis and transformation of programs for parallel computation. In Fourth International Computer Software and Applications Conference, October 1980.
• 12: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 13: Greg Lomow, John Cleary, Brian Unger, and Darrin West. A performance study of Time Warp. In Distributed Simulation Conference, Society for Computer Simulation, San Diego, CA, February 1988 (to appear).
• 14: James Slocum Miller. MultiScheme: A Parallel Processing System Based on MIT Scheme. PhD thesis, MIT, August 1987.
• 15: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 16: Jonathan Rees and Williiam Clinger et al. Revised 3 Report on the Algorithmic Language Scheme. AI Memo 848a, MIT, September 1986.
• 17: Curtis Scott. Butterfly Lisp Reference Manual. BBN Laboratories, Cambridge, MA, April 1986.
• 18: Seth Steinberg et al. Butterfly Lisp system. In Proceedings of the AAAI, 1986.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

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

          Nouns: SCHEME

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Languages, Performance