Provably efficient scheduling for languages with fine-grained parallelism

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Provably efficient scheduling for languages with fine-grained parallelism

Full text

Pdf (1.62 MB)

Source

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

Santa Barbara, California, United States

Pages: 1 - 12

Year of Publication: 1995

ISBN:0-89791-717-0

Authors

Guy E. Blelloch	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA
Phillip B. Gibbons	AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ
Yossi Matias	AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
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): 12, Downloads (12 Months): 43, Citation Count: 23

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/215399.215403 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.

	ANP89	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]
	BCH+94	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]
	BG95	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]
	BGM95	G.E. Blelloch, P.B. Gibbons, and Y. Matias, 1995. In preparation.
	BL93	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]
	BL94	R.D. Blumofe and C. E. Leiserson. Scheduling multithreaded computations by work stealing. In Proc. 35th IEEE Symp. on Foundations o} Computer Science, pages 356-368, November 1994.
	Ble90	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	Ble93	Guy E. Blelloch, NESL: A Nested Data-Parallel Language, Carnegie Mellon University, Pittsburgh, PA, 1992
	Ble95	G.E. Blellech, Progr#mmlng p#rall#i algorithm#. Communications of the A CM, 1995. To appear.
	Bre74	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]
	BS81	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]
	BS94	F.W. Burton and D. J. Simpson. Space efficient execution of deterministic parallel programs. Manuscript., December 1994.
	Bur88	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]
	BV93	Omer Berkman , Uzi Vishkin, Recursive star-tree parallel data structure, SIAM Journal on Computing, v.22 n.2, p.221-242, April 1993 [doi>10.1137/0222017]
	CA88	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
	CLR90	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	FCO90	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]
	GM95	Joseph Gil , Yossi Matias, An effective load balancing policy for geometric-decaying algorithms, Journal of Parallel and Distributed Computing, v.36 n.2, p.185-188, Aug. 1, 1996 [doi>10.1006/jpdc.1996.0098]
	GMV91	Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
	GMV94	Michael T. Goodrich , Yossi Matias , Uzi Vishkin, Optimal parallel approximation for prefix sums and integer sorting, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 23-25, 1994, Arlington, Virginia, United States
	Goo91	Michael T. Goodrich, Using approximation algorithms to design parallel algorithms that may ignore processor allocation (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.711-722, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185439]
	Gra66	R.L. Graham. Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 45(9):1563-1581, 1966.
	Gra69	R.L. Graham. Bounds on multiprocessing timing anomalies. SIAM J. of Applied Mathematics, 17(2):416-429, 1969.
	GZ95	Optimal deterministic approximate parallel prefix sums and their applications, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.220, January 04-06, 1995
	Hag91	T. Hagerup. Fast parallel space allocation, estimation and integer sorting. Technical Report 03/91, SFB 124, Fachbereich Informatik, Universit#t des Saarlandes, D-6600 Saarbrficken, Germany, 1991.
	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]
	Hig93	High Performance Fortran Forum. High Per}ormance Fortran Language Specification, May 1993.
	HWe91	P. Hudak, P. Wadler, and S. P. Jones (eds). Report on the Functional Programming Language HASKELL, June 1991. Version 1.1.
	JáJ92	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	LF80	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	Mat92	Y. Matias. Highly Parallel Randomized Algorithmics. PhD thesis, Tel A viv University, Israel, 1992.
	MNP+ 90	P. H. Mills, L. S. Nyland, 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.
	MV91	Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103453]
	PU87	Christos H. Papadimitriou , Jeffrey D. Ullman, A communication-time tradeoff, SIAM Journal on Computing, v.16 n.4, p.639-646, Aug. 1987 [doi>10.1137/0216044]
	PVW83	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
	PY88	Christos Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.510-513, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62262]
	Rag93	Prabhakar Ragde, The parallel simplicity of compaction and chaining, Journal of Algorithms, v.14 n.3, p.371-380, May 1993 [doi>10.1006/jagm.1993.1019]
	RS87	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
	SDDS86	J. T. Schwartz , R. B. Dewar , E. Schonberg , E. Dubinsky, Programming with sets; an introduction to SETL, Springer-Verlag New York, Inc., New York, NY, 1986
	Sip95	J. Sipelstein. Data Representation Optimizations for Collection-Oriented Languages. PhD thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 1995. To appear.
	ST94	Dan Suciu , Val Tannen, Efficient compilation of high-level data parallel algorithms, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.57-66, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181032]
	Val90	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

CITED BY 23

	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
	Girija J. Narlikar , Guy E. Blelloch, Space-efficient implementation of nested parallelism, ACM SIGPLAN Notices, v.32 n.7, p.25-36, July 1997
	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
	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
	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
	Xiaotie Deng , Patrick Dymond, On multiprocessor system scheduling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.82-88, June 24-26, 1996, Padua, Italy
	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
	Girija J. Narlikar , Guy E. Blelloch, Space-efficient scheduling of nested parallelism, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.1, p.138-173, Jan. 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
	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
	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
	Cong Fu , Tao Yang, Space and time efficient execution of parallel irregular computations, ACM SIGPLAN Notices, v.32 n.7, p.57-68, July 1997
	Umut A. Acar , Guy E. Blelloch , Robert D. Blumofe, The data locality of work stealing, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.1-12, July 09-13, 2000, Bar Harbor, Maine, United States
	Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, An analysis of dag-consistent distributed shared-memory algorithms, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.297-308, June 24-26, 1996, Padua, Italy
	Tao Yang , Cong Fu, Space/time-efficient scheduling and execution of parallel irregular computations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1195-1222, Nov. 1998
	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
	Girija J. Narlikar , Guy E. Blelloch, Pthreads for dynamic and irregular parallelism, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-16, November 07-13, 1998, San Jose, CA
	F. Warren Burton, Guaranteeing Good Memory Bounds for Parallel Programs, IEEE Transactions on Software Engineering, v.22 n.10, p.762-773, October 1996
	Kunal Agrawal , Yuxiong He , Wen Jing Hsu , Charles E. Leiserson, Adaptive scheduling with parallelism feedback, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Jan F. Prins , Siddhartha Chatterjee , Martin Simons, Irregular computations in Fortran - expression and implementation strategies, Scientific Programming, v.7 n.3-4, p.313-326, August 1999
	Kunal Agrawal , Yuxiong He , Charles E. Leiserson, Adaptive work stealing with parallelism feedback, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
	Kunal Agrawal , Charles E. Leiserson , Yuxiong He , Wen Jing Hsu, Adaptive work-stealing with parallelism feedback, ACM Transactions on Computer Systems (TOCS), v.26 n.3, p.1-32, September 2008