Improved parallel job scheduling with overhead

Title:
Improved parallel job scheduling with overhead
Authors:
Havill, Jessen T.; Mao, Weizhen; Dimitrov, Vesselin
Citation:
J. Havill, W. Mao, and V. Dimitrov, Improved parallel job scheduling with overhead. Proceedings of the Seventh Joint Conference on Information Sciences, 393-396, 2003.
Publisher:
Proceedings of the Seventh Joint Conference on Information Sciences
DATE ISSUED:
2003
PERMANENT LINK:
http://hdl.handle.net/2374.DEN/4998; http://hdl.handle.net/2374
Type:
Article; Book chapter
Language:
en_US
Description:
We consider a parallel job scheduling model that incorporates both computation time and communication overhead. For any job Jj with length pj , if kj processors are assigned to execute the job, then the actual execution time of the job is tj = pj=kj+(kj􀀀���1)c, where c is a constant overhead cost associated with each processor except the master processor that initiates the parallel computation. Previously, it was shown that the Shortest Execution Time (SET) algorithm has competitive ratio 4(m􀀀���1)=m for even m 2 and 4m=(m + 1) for odd m 3 with respect to makespan. Here we study the Earliest Completion Time (ECT) algorithm, and show that its competitive ratio is 2 and 2.25 on 2 and 3 processors, respectively. We also offer simulation results that show that ECT compares favorably to SET on larger numbers of processors. Finally, we show that any online algorithm for our problem has competitive ratio at least 3/2 for arbitrarily large m.
ISBN:
0970789025; 9780970789020
Appears in Collections:
Faculty Publications

Full metadata record

DC FieldValue Language
dc.contributor.authorHavill, Jessen T.en
dc.contributor.authorMao, Weizhenen
dc.contributor.authorDimitrov, Vesselinen
dc.date.accessioned2013-01-02T16:05:57Zen
dc.date.accessioned2013-12-18T21:04:48Z-
dc.date.available2013-01-02T16:05:57Zen
dc.date.available2013-12-18T21:04:48Z-
dc.date.created2003en
dc.date.issued2003en
dc.identifier.citationJ. Havill, W. Mao, and V. Dimitrov, Improved parallel job scheduling with overhead. Proceedings of the Seventh Joint Conference on Information Sciences, 393-396, 2003.en_US
dc.identifier.isbn0970789025en
dc.identifier.isbn9780970789020en
dc.identifier.urihttp://hdl.handle.net/2374.DEN/4998en
dc.identifier.urihttp://hdl.handle.net/2374-
dc.descriptionWe consider a parallel job scheduling model that incorporates both computation time and communication overhead. For any job Jj with length pj , if kj processors are assigned to execute the job, then the actual execution time of the job is tj = pj=kj+(kj􀀀���1)c, where c is a constant overhead cost associated with each processor except the master processor that initiates the parallel computation. Previously, it was shown that the Shortest Execution Time (SET) algorithm has competitive ratio 4(m􀀀���1)=m for even m 2 and 4m=(m + 1) for odd m 3 with respect to makespan. Here we study the Earliest Completion Time (ECT) algorithm, and show that its competitive ratio is 2 and 2.25 on 2 and 3 processors, respectively. We also offer simulation results that show that ECT compares favorably to SET on larger numbers of processors. Finally, we show that any online algorithm for our problem has competitive ratio at least 3/2 for arbitrarily large m.en_US
dc.language.isoen_USen_US
dc.publisherProceedings of the Seventh Joint Conference on Information Sciencesen_US
dc.relation.ispartofFaculty Publicationsen_US
dc.titleImproved parallel job scheduling with overheaden_US
dc.typeArticleen_US
dc.typeBook chapteren_US
dc.contributor.institutionDenison Universityen_US
dc.date.digitized2013-01-02en
dc.contributor.repositoryDenison Resource Commonsen_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.