A simple load balancing scheme for task allocation in parallel machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A simple load balancing scheme for task allocation in parallel machines

Full text

Pdf (845 KB)

Source

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

Hilton Head, South Carolina, United States

Pages: 237 - 245

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Larry Rudolph	Department of Computer Science, Hebrew University, Jerusalem, Israel and currently visiting, IBM TJ Watson Research Center, Yorktown Heights, NY
Miriam Slivkin-Allalouf	John Bryce Ltd., Science Based Industries, PO BOX 23838, Jerusalem, Israel
Eli Upfal	Department of Applied Mathematics, Weizman Institute, Rehovot, Israel, and IBM Almaden Research Center, San Jose, Ca

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): 5, Downloads (12 Months): 40, Citation Count: 29

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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

	BKW89	Baumartner, K., R. Kling, and B. Wah, "Implementation of GAMMON: an emcient load balancing strategy for a local computer system," Proceedings of the International Conference on Parai'lel Processing, Vol 2, pp. 77-80, Aug. 1989.
	BK90	F. Bonomi , A. Kumar, Adaptive Optimal Load Balancing in a Nonhomogeneous Multiserver System with a Central Job Scheduler, IEEE Transactions on Computers, v.39 n.10, p.1232-1250, October 1990 [doi>10.1109/12.59854]
	CK79	Y.C. Chow and W. Kohler, "Models for Dynamic Load Baiancing in a Heterogeneous Mu1~iple Processor System," IEEE Transactions on Computers, Vol. C-28, pp. 334-361, May 1979.
	DG90	Dehne, F. and M. Gastaldo, "A note on the load bMancing problem for coarse grained hypercube dictionary machines," Parallel Computing, Vol 16, pp. 75-79, Nov 1990.
	DG89	Dragon, K, and }. Gustafson, "A low cost hypercube load balancing algorithm," Proceedings of the Fourth Conference on Hypercubes, Concurrent Computers and Applications, Vol 1, pp. 583-589, March 1989
	FFKS89	Fox, G., W. Furmanski, J. Koiier, and P. Simic, "Physical optimization and load balancJing algorithms," Proceedings of the Fourth Conference on Hypercubes, Concurrent Computers and Applications, Vol 1, pp. 591-594, March 1989
	HTC89	Hong, 3., X. Tan, and M. Chert, "Dynamic cyclic load balancing on hypercubes," Proceedings of the Fourth Conference on Hypercubes, Concurrent Computers and Applications, Vol 1, pp. 595-598, March 1989
	JW89	Juang, J. and B. Wah, "Load balancing and ordered selection in a computer system with multiple contention buses," journal of Parallel and Distribu~ed Computing, Vol 7, pp 391-415, Dec. 1989.
	KR89	Kumar, V, and V. Rao, "Load balancing on the hypercube architecture," Proceedings of the Fourth Conference on Hypercubes, Concurrent Computers and Applications, Vol 1, pp. 603-608, March 1989
	K89	Koller, J., "The MOOS II Operating System and Dynamic Load Balancing' Proceedings of the Fourth Conference on Hypercubes, Concurrent Compu~lers and Applications, Vol 1, pp 599-602, March 1989
	R87	Raetz, G. "Sequent general purpose parallel processing system," Northcon/87, pp. 7/2/1-5, Sept. 1987.

CITED BY 29

	Danny Hendler , Yossi Lev , Mark Moir , Nir Shavit, A dynamic-sized nonblocking work stealing deque, Distributed Computing, v.18 n.3, p.189-207, February 2006
	Yan Tang , Tao Wang , Xiaoming Li, The design and implementation of LilyTask in shared memory, ACM SIGOPS Operating Systems Review, v.39 n.3, p.52-63, July 2005
	Danny Hendler , Nir Shavit, Non-blocking steal-half work queues, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Nir Shavit , Dan Touitou, Elimination trees and the construction of pools and stacks: preliminary version, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.54-63, June 24-26, 1995, Santa Barbara, California, United States
	Danny Hendler , Nir Shavit, Work dealing, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Petra Berenbrink , Tom Friedetzky , Ernst W. Mayr, Parallel continuous randomized load balancing (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.192-201, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Uwe Brinkschulte , Alexander von Renteln , Mathias Pacher, Measuring the quality of an artificial hormone system based task mapping, Proceedings of the 2nd International Conference on Autonomic Computing and Communication Systems, p.1-8, September 23-25, 2008, Turin, Italy
	Gagan Aggarwal , Rajeev Motwani , An Zhu, The load rebalancing problem, Journal of Algorithms, v.60 n.1, p.42-59, July 2006
	Gagan Aggarwal , Rajeev Motwani , An Zhu, The load rebalancing problem, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Giovanni Della-Libera , Nir Shavit, Reactive diffracting trees, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.24-32, June 23-25, 1997, Newport, Rhode Island, United States
	Maurice Herlihy , Beng-Hong Lim , Nir Shavit, Low contention load balancing on large-scale multiprocessors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.219-227, June 29-July 01, 1992, San Diego, California, United States
	Petra Berenbrink , Tom Friedetzky , Angelika Steger, Randomized and adversarial load balancing, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.175-184, June 27-30, 1999, Saint Malo, France
	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
	Susan Flynn Hummel , Jeanette Schmidt , R. N. Uma , Joel Wein, Load-sharing in heterogeneous systems via weighted factoring, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.318-328, June 24-26, 1996, Padua, Italy
	Nir Shavit , Asaph Zemach, Diffracting trees (preliminary version), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.167-176, June 27-29, 1994, Cape May, New Jersey, United States
	Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada
	Steven Lucco, A dynamic scheduling method for irregular parallel programs, ACM SIGPLAN Notices, v.27 n.7, p.200-211, July 1992
	Bhaskar Ghosh , S. Muthukrishnan, Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.226-235, June 27-29, 1994, Cape May, New Jersey, United States
	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
	Costas Busch , Marios Mavronicolas, A combinatorial treatment of balancing networks, Journal of the ACM (JACM), v.43 n.5, p.794-839, Sept. 1996
	Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, ACM SIGPLAN Notices, v.30 n.8, p.207-216, Aug. 1995
	Ioana Banicescu , Ricolindo L. Cariño , Jaderick P. Pabico , Mahadevan Balasubramaniam, Design and implementation of a novel dynamic load balancing library for cluster computing, Parallel Computing, v.31 n.7, p.736-756, July 2005
	Ioana Banicescu , Ricolindo L. Carino , Jaderick P. Pabico , Mahadevan Balasubramaniam, Performance evaluation of a dynamic load-balancing library for cluster computing, International Journal of Computational Science and Engineering, v.1 n.2-4, p.118-133, May 2005
	Nir Shavit , Asaph Zemach, Diffracting trees, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.385-428, Nov. 1996
	Vinay Kanitkar , Alex Delis, Efficient processing of client transactions in real-time, Distributed and Parallel Databases, v.17 n.1, p.39-74, January 2005
	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
	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
	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