Optimal online scheduling of parallel jobs with dependencies

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal online scheduling of parallel jobs with dependencies

Full text

Pdf (1.09 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: 642 - 651

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Anja Feldmann
Ming-Yang Kao
Jiří Sgall
Shang-Hua Teng

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 24, Citation Count: 8

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/167088.167254 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	Sandeep Bhatt , Fan Chung , Jia-Wei Hong , Arnold Rosenberg, Optimal simulations by Butterfly Networks, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.192-204, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62229]
	2	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	3	Ernest Davis , Jeffrey M. Jaffe, Algorithms for Scheduling Tasks on Unrelated Processors, Journal of the ACM (JACM), v.28 n.4, p.721-736, Oct. 1981 [doi>10.1145/322276.322284]
	4	D. G. Feitelson , L. Rudolph, Wasted resources in gang scheduling, Proceedings of the fifth Jerusalem conference on Information technology, p.127-136, September 1990, Jerusalem, Israel
	5	Anja Feldmann , Jiří Sgall , Shang-Hua Teng, Dynamic scheduling on parallel machines, Proceedings of the 32nd annual symposium on Foundations of computer science, p.111-120, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185355]
	6	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	7	R.L. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical Journal., pages 1563- 1581, 1966.
	8	Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
	9	S R Kosaraju , M J Atallah, Optimal simulations between mesh-connected arrays of processors, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.264-272, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12157]
	10	H.T. Kung. Computational Models for Parallel Computers. Technical report, CMU-CS-88-164, 1987.
	11	James L. Peterson , Abraham Silberschatz, Operating system concepts (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
	12	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	13	David B. Shmoys , Joel Wein , David P. Williamson, Scheduling parallel machines on-line, Proceedings of the 32nd annual symposium on Foundations of computer science, p.131-140, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185361]
	14	Qingzhou Wang , Kam Hoi Cheng, A heuristic of scheduling parallel tasks and its analysis, SIAM Journal on Computing, v.21 n.2, p.281-294, April 1992 [doi>10.1137/0221021]

CITED BY 8

	Keqin Li , Yi Pan, Probabilistic Analysis of Scheduling Precedence Constrained Parallel Tasks on Multicomputers with Contiguous Processor Allocation, IEEE Transactions on Computers, v.49 n.10, p.1021-1030, October 2000
	Soumen Chakrabarti , S. Muthukrishnan, Resource scheduling for parallel database and scientific applications, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.329-335, June 24-26, 1996, Padua, Italy
	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
	Klaus Jansen , Lorant Porkolab, Linear-time approximation schemes for scheduling malleable parallel tasks, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.490-498, January 17-19, 1999, Baltimore, Maryland, United States
	Amrinder Arora , Fanchun Jin , Hyeong-Ah Choi, Scheduling resource allocation with timeslot penalty for changeover, Theoretical Computer Science, v.369 n.1, p.323-337, 15 December 2006
	Walter Ludwig , Prasoon Tiwari, Scheduling malleable and nonmalleable parallel tasks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.167-176, January 23-25, 1994, Arlington, Virginia, United States
	Houman Alborzi , Eric Torng , Patchrawat Uthaisombut , Stephen Wagner, The k-client problem, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.73-82, January 05-07, 1997, New Orleans, Louisiana, 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