File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On exploiting task duplication in parallel program scheduling

TitleOn exploiting task duplication in parallel program scheduling
Authors
KeywordsAlgorithms
Distributed systems
Duplication-based scheduling
Multiprocessors
Parallel scheduling
Task graphs
Issue Date1998
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tpds
Citation
Ieee Transactions On Parallel And Distributed Systems, 1998, v. 9 n. 9, p. 872-892 How to Cite?
AbstractOne of the main obstacles in obtaining high performance from message-passing multicomputer systems is the inevitable communication overhead which is incurred when tasks executing on different processors exchange data. Given a task graph, duplication-based scheduling can mitigate this overhead by allocating some of the tasks redundantly on more than one processor. In this paper, we focus on the problem of using duplication in static scheduling of task graphs on parallel and distributed systems. We discuss five previously proposed algorithms and examine their merits and demerits. We describe some of the essential principles for exploiting duplication in a more useful manner and, based on these principles, propose an algorithm which outperforms the previous algorithms. The proposed algorithm generates optimal solutions for a number of task graphs. The algorithm assumes an unbounded number of processors. For scheduling on a bounded number of processors, we propose a second algorithm which controls the degree of duplication according to the number of available processors. The proposed algorithms are analytically and experimentally evaluated and are also compared with the previous algorithms. © 1998 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/42803
ISSN
2015 Impact Factor: 2.661
2015 SCImago Journal Rankings: 1.590
References

 

DC FieldValueLanguage
dc.contributor.authorAhmad, Ien_HK
dc.contributor.authorKwok, YKen_HK
dc.date.accessioned2007-03-23T04:32:30Z-
dc.date.available2007-03-23T04:32:30Z-
dc.date.issued1998en_HK
dc.identifier.citationIeee Transactions On Parallel And Distributed Systems, 1998, v. 9 n. 9, p. 872-892en_HK
dc.identifier.issn1045-9219en_HK
dc.identifier.urihttp://hdl.handle.net/10722/42803-
dc.description.abstractOne of the main obstacles in obtaining high performance from message-passing multicomputer systems is the inevitable communication overhead which is incurred when tasks executing on different processors exchange data. Given a task graph, duplication-based scheduling can mitigate this overhead by allocating some of the tasks redundantly on more than one processor. In this paper, we focus on the problem of using duplication in static scheduling of task graphs on parallel and distributed systems. We discuss five previously proposed algorithms and examine their merits and demerits. We describe some of the essential principles for exploiting duplication in a more useful manner and, based on these principles, propose an algorithm which outperforms the previous algorithms. The proposed algorithm generates optimal solutions for a number of task graphs. The algorithm assumes an unbounded number of processors. For scheduling on a bounded number of processors, we propose a second algorithm which controls the degree of duplication according to the number of available processors. The proposed algorithms are analytically and experimentally evaluated and are also compared with the previous algorithms. © 1998 IEEE.en_HK
dc.format.extent700180 bytes-
dc.format.extent28160 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tpdsen_HK
dc.relation.ispartofIEEE Transactions on Parallel and Distributed Systemsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rights©1998 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.en_HK
dc.subjectAlgorithmsen_HK
dc.subjectDistributed systemsen_HK
dc.subjectDuplication-based schedulingen_HK
dc.subjectMultiprocessorsen_HK
dc.subjectParallel schedulingen_HK
dc.subjectTask graphsen_HK
dc.titleOn exploiting task duplication in parallel program schedulingen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1045-9219&volume=9&issue=9&spage=872&epage=892&date=1998&atitle=On+exploiting+task+duplication+in+parallel+program+schedulingen_HK
dc.identifier.emailKwok, YK:ykwok@eee.hku.hken_HK
dc.identifier.authorityKwok, YK=rp00128en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/71.722221en_HK
dc.identifier.scopuseid_2-s2.0-0032166239en_HK
dc.identifier.hkuros44694-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0032166239&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume9en_HK
dc.identifier.issue9en_HK
dc.identifier.spage872en_HK
dc.identifier.epage892en_HK
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridAhmad, I=7201878459en_HK
dc.identifier.scopusauthoridKwok, YK=7101857718en_HK
dc.identifier.citeulike2974118-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats