Space-efficient scheduling of multithreaded computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Space-efficient scheduling of multithreaded computations

Full text

Pdf (1.32 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 362 - 371

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Robert D. Blumofe
Charles E. Leiserson

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/167088.167196 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	Anant Agarwal , Beng-Hong Lim , David Kranz , John Kubiatowicz, APRIL: a processor architecture for multiprocessing, Proceedings of the 17th annual international symposium on Computer Architecture, p.104-114, May 28-31, 1990, Seattle, Washington, United States
	2	Sandeep Bhatt , David Greenberg , Tom Leighton , Pangfeng Liu, Tight bounds for on-line tree embeddings, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.344-350, January 28-30, 1991, San Francisco, California, United States
	3	R. D. Blumofe, MANAGING STORAGE FOR MULTITHREADED COMPUTATIONS, Massachusetts Institute of Technology, Cambridge, MA, 1992
	4	Bob Boothe , Abhiram Ranade, Improved multithreading techniques for hiding communication latency in multiprocessors, Proceedings of the 19th annual international symposium on Computer architecture, p.214-223, May 19-21, 1992, Queensland, Australia
	5	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]
	6	David E. Culler. Resource management for the tagged token dataflow architecture. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, January 1980.
	7	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
	8	David E. Culler , Anurag Sah , Klaus E. Schauser , Thorsten von Eicken , John Wawrzynek, Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.164-175, April 08-11, 1991, Santa Clara, California, United States
	9	W. J. Dally , L. Chao , A. Chien , S. Hassoun , W. Horwat , J. Kaplan , P. Song , B. Totty , S. Wills, Architecture of a message-driven processor, Proceedings of the 14th annual international symposium on Computer architecture, p.189-196, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30372]
	10	R. Feldmann, P. Mysliwietz, and B. Monien. A fully distributed chess program. Technical Report 79, University of Paderborn, Germany, February 1991.
	11	V. G. Grafe and J. E. Hoch. The Epsilon-2 hybrid datafiow architecture. In COMPCON 90, pages 88-93, San Francisco, California, February 1990.
	12	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]
	13	R. A. Iannucci, Toward a dataflow/von Neumann hybrid architecture, Proceedings of the 15th Annual International Symposium on Computer architecture, p.131-140, May 30-June 02, 1988, Honolulu, Hawaii, United States
	14	Christos Kaklamanis , Giuseppe Persiano, Branch-and-bound and backtrack search on mesh-connected arrays of processors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.118-126, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140914]
	15	Richard Karp , Yanjun Zhang, A randomized parallel branch-and-bound procedure, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.290-300, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62240]
	16	Bradley Kuszmaul. Private communication, February 1993.
	17	T. Leighton , M. Newman , A. G. Ranade , E. Schwabe, Dynamic tree embeddings in butterflies and hypercubes, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.224-234, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72959]
	18	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	19	Abhiram Ranade, Optimal speedup for backtrack search on a butterfly network, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.40-48, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113383]
	20	Larry Rudolph , Miriam Slivkin-Allalouf , Eli Upfal, A simple load balancing scheme for task allocation in parallel machines, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.237-245, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113401]
	21	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
	22	Mitsuhisa Sato , Yuetsu Kodama , Shuichi Sakai , Yoshinori Yamaguchi , Yasuhito Koumura, Thread-based programming for the EM-4 hybrid dataflow machine, Proceedings of the 19th annual international symposium on Computer architecture, p.146-155, May 19-21, 1992, Queensland, Australia
	23	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
	24	Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
	25	Yanjun Zhang , Richard M. Karp, Parallel algorithms for combinatorial search problems, 1989

CITED BY 22

	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
	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
	Michael Mitzenmacher, Analyses of load stealing models based on differential equations, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.212-221, 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
	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
	Arnold L. Rosenberg, Optimal Schedules for Cycle-Stealing in a Network of Workstations with a Bag-of-Tasks Workload, IEEE Transactions on Parallel and Distributed Systems, v.13 n.2, p.179-191, February 2002
	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
	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
	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
	Michael A. Bender , Michael O. Rabin, Scheduling Cilk multithreaded parallel programs on processors of different speeds, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.13-21, July 09-13, 2000, Bar Harbor, Maine, United States
	Lixin Gao , Arnold L. Rosenberg , Ramesh K. Sitaraman, On trading task reallocation for thread management in partitionable multiprocessors, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.309-317, June 24-26, 1996, Padua, Italy
	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
	Arnold L. Rosenberg, Optimal schedules for data-parallel cycle-stealing in networks of workstations (extended abstract), Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.22-29, July 09-13, 2000, Bar Harbor, Maine, United States
	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
	F. Warren Burton, Guaranteeing Good Memory Bounds for Parallel Programs, IEEE Transactions on Software Engineering, v.22 n.10, p.762-773, October 1996
	Wolfgang Blochinger , Michael Kaufmann , Martin Siebenhaller, Visualizing structural properties of irregular parallel computations, Proceedings of the 2005 ACM symposium on Software visualization, May 14-15, 2005, St. Louis, Missouri
	Marcel van Lohuizen, A generic approach to parallel chart parsing with an application to LinGO, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.507-514, July 06-11, 2001, Toulouse, France
	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
	Wolfgang Blochinger , Michael Kaufmann , Martin Siebenhaller, Visualization aided performance tuning of irregular task-parallel computations, Information Visualization, v.5 n.2, p.81-94, June 2006
	Matteo Frigo, Multithreaded programming in Cilk, Proceedings of the 2007 international workshop on Parallel symbolic computation, July 27-28, 2007, London, Ontario, Canada
	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