A provably time-efficient parallel implementation of full speculation

ABSTRACT

Speculative evaluation, including leniency and futures, is often used to produce high degrees of parallelism. Understanding the performance characteristics of such evaluation, however, requires having a detailed understanding of the implementation. For example, the particular implementaion technique used to suspend and reactivate threads can have an asymptotic effect on performance. With the goal of giving the users some understanding of performance without requiring them to understand the implementation, we present a provable implementation bound for a language based on speculative evaluation. The idea is (1) to supply the users with a semantics for a language that defines abstract costs for measuring or analyzing the performance of computations, (2) to supply the users with a mapping of these costs onto runtimes on various machine models, and (3) to describe an implementation strategy of the language and prove that it meets these mappings. For this purpose we consider a simple language based on speculative evaluation. For every computation, the semantics of the language returns a directed acyclic graph (DAG) in which each node represents a unit of computation, and each edge represents a dependence. We then describe an implementation strategy of the language and show that any computation with w work (the number of nodes in the DAG) and d depth (the length of the longest path in the DAG) will run on a p-processor PRAM in O(w/p + d log p) time. The bounds are work efficient (within a constant factor of linear speedup) when there is sufficient parallelism, w/d ≥ p log p. These are the first time bounds we know of for languages with speculative evaluation. The main challenge is in parallelizing the necessary queuing operations on suspended threads.

REFERENCES

• 1: Henry C. Baker, Jr. , Carl Hewitt, The incremental garbage collection of processes, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.55-59, August 15-17, 1977
• 2: Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215403]
• 3: Guy Blelloch , John Greiner, Parallelism in sequential functional languages, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.226-237, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224210]
• 4: Guy E. Blelloch , Margaret Reid-Miller, Pipelining with futures, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.249-259, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258517]
• 5: Guy E. Blelloch, NESL: A Nested Data-Parallel Language, Carnegie Mellon University, Pittsburgh, PA, 1992
• 6: Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.213-225, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 7: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 8: Robert D. Blumofe , Charles E. Leiserson, Space-efficient scheduling of multithreaded computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.362-371, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167196]
• 9: David Callahan , Burton Smith, A future-based parallel language for a general-purpose highly-parallel computer, Selected papers of the second workshop on Languages and compilers for parallel computing, p.95-113, May 1990, Urbana, Illinois, United States
• 10: Robit Chandra , Anoop Gupta , John L. Hennessy, COOL: a language for parallel programming, Selected papers of the second workshop on Languages and compilers for parallel computing, p.126-148, May 1990, Urbana, Illinois, United States
• 11: Marc Feeley, An efficient and general implementation of futures on large scale shared-memory multiprocessors, Brandeis University, Waltham, MA, 1993
• 12: M. Felleisen , D. P. Friedman, A calculus for assignments in higher-order languages, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.314, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41654]
• 13: Cormac Flanagan , Matthias Felleisen, The semantics of future and its use in program optimization, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.209-220, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199484]
• 14: Joseph Gil , Yossi Matias, Fast and efficient simulations among CRCW PRAMs, Journal of Parallel and Distributed Computing, v.23 n.2, p.135-148, Nov. 1994 [doi>10.1006/jpdc.1994.1127]
• 15: Ron Goldman , Richard P. Gabriel, Qlisp: experience and new directions, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.111-123, July 19-21, 1988, New Haven, Connecticut, United States
• 16: 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]
• 17: GREINER, J. 1997. Semantics-based parallel cost models and their use in provably efficient implementations. Ph.D. thesis, Carnegie Mellon University.
• 18: John Greiner , Guy E. Blelloch, A provably time-efficient parallel implementation of full speculation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.309-321, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237797]
• 19: 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]
• 20: 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]
• 21: R. H. Halstead, Jr., New ideas in parallel Lisp: language design, implementations, and programming tools, Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, p.2-57, June 1990, Sendai, Japan
• 22: Paul Hudak , Steve Anderson, Pomset interpretations of parallel function programs, Proc. of a conference on Functional programming languages and computer architecture, p.234-256, October 1987, Portland, Oregon, United States
• 23: 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]
• 24: Paul Hudak , Eric Hohr, Graphinators and the duality of SIMD and MIMD, Proceedings of the 1988 ACM conference on LISP and functional programming, p.224-234, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62714]
• 25: T. Ito , M. Matsui, A parallel Lisp language PaiLisp and its kernel specification, Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, p.58-100, June 1990, Sendai, Japan
• 26: M. S. Joy , T. H. Axford, Parallel Combinator Reduction: Some Performance Bounds, University of Warwick, Coventry, UK, 1992
• 27: Richard Kennaway, A Conflict Between Call-by-Need Computation and Parallelism, Proceedings of the 4th International Workshop on Conditional and Typed Rewriting Systems, p.247-261, July 13-15, 1994
• 28: 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
• 29: LANDIN, P. J. 1964. The mechanical evaluation of expressions. The Computer Journal 6, 308-320.
• 30: Yossi Matias , Uzi Vishkin, Parallel hashing and integer sorting, Journal of Algorithms, v.12 n.4, p.573-606, Dec. 1991 [doi>10.1016/0196-6774(91)90034-V]
• 31: Yossi Matias , Uzi Vishkin, A note on reducing parallel model simulations to integer sorting, Proceedings of the 9th International Symposium on Parallel Processing, p.208-212, April 25-28, 1995
• 32: MILLER, J. S. 1987. MultiScheme: A parallel processing system based on MIT Scheme. Ph.D. thesis, Massachusetts Institute of Technology.
• 33: Luc Moreau, The PCKS-Machine: An Abstract Machine for Sound Evaluation of Parallel Functional Programs with First-Class Continuations, Proceedings of the 5th European Symposium on Programming: Programming Languages and Systems, p.424-438, April 11-13, 1994
• 34: MOREAU, L. 1995. The semantics of Scheme with future. Tech. Rep. M95/7, Department of Electronics and Computer Science, University of Southampton.
• 35: Luc Moreau, The semantics of Scheme with future, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.146-156, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 36: NIKHIL, R. S. 1990. The parallel programming language Id and its compilation for parallel machines. Tech. Rep. Computation Structures Group Memo 313, Massachusetts Institute of Technology. July.
• 37: NIKHIL, R. S. 1991. Id version 90.1 reference manual. Tech. Rep. Computation Structures Group Memo 284-1, Laboratory for Computer Science, Massachusetts Institute of Technology. July.
• 38: NIKHIL, R. S., ARVIND, HICKS, J., ADITYA, S., AUGUSTSSON, L., MAESSEN, J.-W., AND ZHOU, Y. 1995. pH language reference manual, version 1.0--preliminary. Tech. Rep. Computation Structures Group Memo 369, Laboratory for Computer Science, Massachusetts Institute of Technology. Jan.
• 39: OSBORNE, R. B. 1989. Speculative computation in Multilisp. Ph.D. thesis, Massachusetts Institute of Technology.
• 40: Michel Parigot, Programming with Proofs: A Second Order Type Theory, Proceedings of the 2nd European Symposium on Programming, p.145-159, March 21-24, 1988
• 41: PARTRIDGE, t. S. 1991. Speculative evaluation in parallel implementations of lazy functional languages. Ph.D. thesis, Department of Computer Science, University of Tasmania.
• 42: PARTRIDGE, A. S. AND DEKKER, A. H. 1989. Speculative parallelism in a distributed graph reduction machine. In Proceedings Hawaii International Conference on System Sciences. Vol. 2. 771-779.
• 43: S. L. Peyton Jones, Parallel implementations of functional programming languages, The Computer Journal, v.32 n.2, p.175-186, April 1989 [doi>10.1093/comjnl/32.2.175]
• 44: PLOTKIN, G. D. 1974. Call-by-name, call-by-value and the A-calculus. Theor. Comput. Sci. 1.
• 45: Abhiram Gorakhanath Ranade, Fluent parallel computation, 1989
• 46: ROE, P. 1990. Calculating lenient programs' performance. In Proceedings Functional Programruing, Glasgow 1990, S. L. Peyton Jones, G. Hutton, and C. K. Holst, Eds. Workshops in computing. Springer-Verlag, 227-236.
• 47: ROE, P. 1991. Parallel programming using functional languages. Ph.D. thesis, Department of Computing Science, University of Glasgow.
• 48: Mads Rosendahl, Automatic complexity analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.144-156, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99381]
• 49: SANDS, D. 1990. Calculi for time analysis of functional programs. Ph.D. thesis, University of London, Imperial College.
• 50: TRAUB, K. R. 1988. Sequential implementation of lenient programming languages. Ph.D. thesis, Massachusetts Institute of Technology.
• 51: TREMBLAY, G. AND GAO, G. R. 1995. The impact of laziness on parallelism and the limits of strictness analysis. In Proceedings High Performance Functional Computing, A. P. W. Bohm and J. T. Feo, Eds. 119-133.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Data-flow languages

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Languages, Performance, Theory

Keywords:
abstract machines, parallel languages, profiling semantics, speculation, threads