A provably time-efficient parallel implementation of full speculation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A provably time-efficient parallel implementation of full speculation

Full text

Pdf (1.45 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

St. Petersburg Beach, Florida, United States

Pages: 309 - 321

Year of Publication: 1996

ISBN:0-89791-769-3

Authors

John Greiner	Carnegie Mellon University
Guy E. Blelloch	Carnegie Mellon University

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 20, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237721.237797 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	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]
	3	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	4	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	5	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
	6	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
	7	Marc Feeley, An efficient and general implementation of futures on large scale shared-memory multiprocessors, Brandeis University, Waltham, MA, 1993
	8	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]
	9	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]
	10	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
	11	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]
	12	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]
	13	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]
	14	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
	15	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
	16	Lorenz Huelsbergen , James R. Larus , Alexander Aiken, Using the run-time sizes of data structures to guide parallel-thread creation, Proceedings of the 1994 ACM conference on LISP and functional programming, p.79-90, June 27-29, 1994, Orlando, Florida, United States
	17	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
	18	M. S. Joy , T. H. Axford, Parallel Combinator Reduction: Some Performance Bounds, University of Warwick, Coventry, UK, 1992
	19	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
	20	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
	21	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]
	22	James S. Miller. Mult#Scheme: A Parallel Processm9 System Based on MIT Scheme. PhD thesis, Massachusetts Institute ot Technology, September 1987.
	23	J. S. Miller , B. S. Epstein, Garbage collection in MultiScheme, Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, p.138-160, June 1990, Sendai, Japan
	24	Rishiyur S. Nikhil. The parallel programming language Id and its compilation for parallel machines. Technical Report Computation Structures Group Memo 313, Massachusetts Institute of Technology, July 1990.
	25	Rishiyur S. Nikhil. Id version 90.1 reference manual. Technical Report Computation Structures Group Memo 284-1, Laboratory for Computer Science, Massachusetts Institute of Technology, july 1991.
	26	Rishiyur S. Nikhil, Arvind, James Hicks# Shail Aditya, Lennar Augustsson, Jan-Willem Maessen# and Yuli Zhou. pH language reference manual, version 1.0- preliminary. Technical Report Computation Structures Group Memo 369, Laboratory for Computer Science, Massachusetts Institute of Technology, January 1995.
	27	Randy B. Osborne. Speculatwe Computation #n MuIt#l- #sp. PhD thesis, Massachusetts Institute of Technology, December 1989.
	28	Andrew S. Partridge. SpecuIatwe Evaluation #n Parallel Implcmcntatzons of Lazy Functional Languages. PhD thesis, Department of Computer Science# University of Tasmania, 1991.
	29	Andrew S. Partridge and Anthony H. Dekker. Speculative parallelism in a distributed graph reduction machine. In Proceedings Hawai# International Conference on System Sciences, volume 2, pages 771-779, 1989.
	30	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]
	31	Abhiram Gorakhanath Ranade, Fluent parallel computation, 1989
	32	Paul Roe. Calculating lenient programs' performance. In Simon L Peyton Jones, Graham Hutton, and Carsten Kehler Holst, editors, Proceedings Functional Programming, Glasgow 1990, Workshops in computing, pages 227-236. Springer-Verlag, August 1990.
	33	Paul Roe. Parallel Programming using Functional Languages. PhD thesis, Department of Computing Science, University of Glasgow, February 1991.
	34	David Sands. Calcuh for T'tme Analysis of Functional Programs. PhD thesis, University of London, Imperial College, September 1990.
	35	D. B. Skillicorn , W. Cai, A cost calculus for parallel functional programming, Journal of Parallel and Distributed Computing, v.28 n.1, p.65-83, July 1995 [doi>10.1006/jpdc.1995.1089]
	36	Guy Tremblay and G. R. Gao. The impact of laziness on parallelism and the limits of strictness analysis, in A. P Wim Bohm and John T. Peo, editors, Proceedings H#gh Performance Functional Computing, pages 119- 133, April 1995.
	37	C K Yuen, M D Feng, and J J Yee. Speculative parallelism in BaLinda Lisp. Technical Report TR31/92, Department of Information Systems and Computer Science, National University of Singapore, November 1992.
	38	Wolf Zimmermann. Automatic worst case complexity analysis of parallel programs. Technical Report TR-90- 066, International Computer Science Institute, December 1990.
	39	Wolf Zimmermann. Complexity issues in the design of functional languages with explicit parallelism. In Proceed#ngs International Conference on Computer Languaqes, pages 34-43, 1992.

CITED BY 6

	Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, ACM SIGPLAN Notices, v.31 n.6, p.213-225, June 15, 1996
	Guy E. Blelloch , Phillip B. Gibbons , Girija J. Narlikar , Yossi Matias, Space-efficient scheduling of parallelism with synchronization variables, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.12-23, June 23-25, 1997, Newport, Rhode Island, United States
	John Greiner , Guy E. Blelloch, A provably time-efficient parallel implementation of full speculation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.240-285, March 1999
	Panagiota Fatourou, Low-contention depth-first scheduling of parallel computations with write-once synchronization variables, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.189-198, July 2001, Crete Island, Greece
	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
	Yasuhiko Minamide , Jacques Garrigue, On the runtime complexity of type-directed unboxing, ACM SIGPLAN Notices, v.34 n.1, p.1-12, Jan. 1999