Space-efficient scheduling of parallelism with synchronization variables

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Space-efficient scheduling of parallelism with synchronization variables

Full text

Pdf (1.67 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures table of contents

Newport, Rhode Island, United States

Pages: 12 - 23

Year of Publication: 1997

ISBN:0-89791-890-8

Authors

Guy E. Blelloch	Carnegie Mellon
Phillip B. Gibbons	Bell Laboratories
Girija J. Narlikar	Bell Laboratories
Yossi Matias	Carnegie Mellon

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 30, Citation Count: 16

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/258492.258494 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	Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
	2	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994 [doi>10.1145/185675.185815]
	3	Guy E. Blelloch , Jonathan C. Hardwick , Jay Sipelstein , Marco Zagha , Siddhartha Chatterjee, Implementation of a portable nested data-parallel language, Journal of Parallel and Distributed Computing, v.21 n.1, p.4-14, April 1994 [doi>10.1006/jpdc.1994.1038]
	4	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]
	5	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
	6	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]
	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	R. D. Blumofe and C. E. Leiserson. Scheduling multithreaded computations by work stealing. In Proc. 35th IEEE Syrup. on Foundations of Computer Science, pages 356-368, November 1994.
	10	F. Warren Burton , M. Ronan Sleep, Executing functional programs on a virtual tree of processors, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.187-194, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806778]
	11	F. W. Burton, Storage Management in Virtual Tree Machines, IEEE Transactions on Computers, v.37 n.3, p.321-328, March 1988 [doi>10.1109/12.2169]
	12	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
	13	Martin C. Carlisle , Anne Rogers , John H. Reppy , Laurie J. Hendren, Early Experiences with Olden, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.1-20, August 12-14, 1993
	14	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
	15	Chris Clack , Simon L. Peyton Jones, Strictness analysis—a practical approach, Proc. of a conference on Functional programming languages and computer architecture, p.35-49, January 1985, Nancy, France
	16	D. E. Culler , Arvind, Resource requirements of dataflow programs, Proceedings of the 15th Annual International Symposium on Computer architecture, p.141-150, May 30-June 02, 1988, Honolulu, Hawaii, United States
	17	E.G. Coffman, Jr., editor. Computer and job-shop scheduling theory. John Wiley & Sons, New York, 1976.
	18	John T. Feo , David C. Cann , Rodney R. Oldehoeft, A report on the Sisal language project, Journal of Parallel and Distributed Computing, v.10 n.4, p.349-366, Dec. 1990 [doi>10.1016/0743-7315(90)90035-N]
	19	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]
	20	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]
	21	R. L. Graham. Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 45(9):1563-1581, 1966.
	22	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]
	23	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]
	24	High Performance Fortran Forum. High Performance Fortran Language Specification, May 1993.
	25	J. E. Hoch, D. M. Davenport, V. G. Grafe, and K. M. Steele. Compile-time partitioning of a non-strict language into sequential threads. In Proc. Symposium on Parallel and Distributed Computing, Dec. 1991.
	26	Suresh Jagannathan , Jim Philbin, A foundation for an efficient multi-threaded scheme system, Proceedings of the 1992 ACM conference on LISP and functional programming, p.345-357, June 22-24, 1992, San Francisco, California, United States
	27	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
	28	P. H. Mills, L. S. N yland, J. F. Prins, J. H. Reif, and R. A. Wagner. Prototyping parallel and distributed programs in Proteus. Technical Report UNC-CH TR90- 041, Computer Science Dept., University of North Carolina, 1990.
	29	G. J. N arlikar and G. E. Blelloch. A framework for space and time efficient schedufing of parallelism. Technical Report CMU-CS-96-197, Computer Science Department, Carnegie Mellon University, 1996.
	30	Girija J. Narlikar , Guy E. Blelloch, Space-efficient implementation of nested parallelism, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.25-36, June 18-21, 1997, Las Vegas, Nevada, United States
	31	Wolfgang J. Paul , Uzi Vishkin , Hubert Wagener, Parallel Dictionaries in 2-3 Trees, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.597-609, July 18-22, 1983
	32	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]
	33	Martin C. Rinard , Daniel J. Scales , Monica S. Lam, Jade: A High-Level, Machine-Independent Language for Parallel Programming, Computer, v.26 n.6, p.28-38, June 1993 [doi>10.1109/2.214440]
	34	Carlos A. Ruggiero , John Sargeant, Control of parallelism in the Manchester Dataflow Machine, Proc. of a conference on Functional programming languages and computer architecture, p.1-15, October 1987, Portland, Oregon, United States
	35	Klaus E Schauser, Compiling Lenient Languages for, University of California at Berkeley, Berkeley, CA, 1994
	36	Klaus E. Schauser , David E. Culler , Seth C. Goldstein, Separation constraint partitioning: a new algorithm for partitioning non-strict programs into sequential threads, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.259-271, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199511]
	37	Nir Shavit , Eli Upfal , Asaph Zemach, A steady state analysis of diffracting trees (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.33-41, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237505]
	38	B. T. Smith. Parallel computing forum (PCF) fortran. In Aspects of Computation on Asynchronous Parallel Processors. Proc. 1FIP WG 2.5 Working Con}erence. North-Holland, August 1988.

CITED BY 16

	Uzi Vishkin , Shlomit Dascal , Efraim Berkovich , Joseph Nuzman, Explicit multi-threading (XMT) bridging models for instruction parallelism (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.140-151, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999
	Clem Baker-Finch , David J. King , Phil Trinder, An operational semantics for parallel lazy evaluation, ACM SIGPLAN Notices, v.35 n.9, p.162-173, Sept. 2000
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Journal of the ACM (JACM), v.46 n.2, p.281-321, March 1999
	Girija J. Narlikar, Scheduling threads for low space requirement and good locality, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.83-95, June 27-30, 1999, Saint Malo, France
	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
	Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	David J. Simpson , F. Warren Burton, Space Efficient Execution of Deterministic Parallel Programs, IEEE Transactions on Software Engineering, v.25 n.6, p.870-882, November 1999
	Guy E. Blelloch , Phillip B. Gibbons, Effectively sharing a cache among threads, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Uzi Vishkin, Two techniques for reconciling algorithm parallelism with memory constraints, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Thierry Gautier , Hamid-Reza Hamidi, Re-scheduling invocations of services for RPC grids, Computer Languages, Systems and Structures, v.33 n.3-4, p.168-178, October, 2007
	Guy E. Blelloch , Rezaul A. Chowdhury , Phillip B. Gibbons , Vijaya Ramachandran , Shimin Chen , Michael Kozuch, Provably good multicore cache performance for divide-and-conquer algorithms, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.501-510, January 20-22, 2008, San Francisco, California
	Shimin Chen , Phillip B. Gibbons , Michael Kozuch , Vasileios Liaskovitis , Anastassia Ailamaki , Guy E. Blelloch , Babak Falsafi , Limor Fix , Nikos Hardavellas , Todd C. Mowry , Chris Wilkerson, Scheduling threads for constructive cache sharing on CMPs, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Daniel Spoonhower , Guy E. Blelloch , Phillip B. Gibbons , Robert Harper, Beyond nested parallelism: tight bounds on work-stealing overheads for parallel futures, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada