File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/71.722221
- Scopus: eid_2-s2.0-0032166239
- WOS: WOS:000076179000005
- Find via
Supplementary
-
Bookmarks:
- CiteULike: 2
- Citations:
- Appears in Collections:
Article: On exploiting task duplication in parallel program scheduling
Title | On exploiting task duplication in parallel program scheduling |
---|---|
Authors | |
Keywords | Algorithms Distributed systems Duplication-based scheduling Multiprocessors Parallel scheduling Task graphs |
Issue Date | 1998 |
Publisher | I 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? |
Abstract | One 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 Identifier | http://hdl.handle.net/10722/42803 |
ISSN | 2023 Impact Factor: 5.6 2023 SCImago Journal Rankings: 2.340 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahmad, I | en_HK |
dc.contributor.author | Kwok, YK | en_HK |
dc.date.accessioned | 2007-03-23T04:32:30Z | - |
dc.date.available | 2007-03-23T04:32:30Z | - |
dc.date.issued | 1998 | en_HK |
dc.identifier.citation | Ieee Transactions On Parallel And Distributed Systems, 1998, v. 9 n. 9, p. 872-892 | en_HK |
dc.identifier.issn | 1045-9219 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/42803 | - |
dc.description.abstract | One 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.extent | 700180 bytes | - |
dc.format.extent | 28160 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.format.mimetype | application/msword | - |
dc.language | eng | en_HK |
dc.publisher | I E E E. The Journal's web site is located at http://www.computer.org/tpds | en_HK |
dc.relation.ispartof | IEEE Transactions on Parallel and Distributed Systems | en_HK |
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. | - |
dc.subject | Algorithms | en_HK |
dc.subject | Distributed systems | en_HK |
dc.subject | Duplication-based scheduling | en_HK |
dc.subject | Multiprocessors | en_HK |
dc.subject | Parallel scheduling | en_HK |
dc.subject | Task graphs | en_HK |
dc.title | On exploiting task duplication in parallel program scheduling | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+scheduling | en_HK |
dc.identifier.email | Kwok, YK:ykwok@eee.hku.hk | en_HK |
dc.identifier.authority | Kwok, YK=rp00128 | en_HK |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.doi | 10.1109/71.722221 | en_HK |
dc.identifier.scopus | eid_2-s2.0-0032166239 | en_HK |
dc.identifier.hkuros | 44694 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0032166239&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 9 | en_HK |
dc.identifier.issue | 9 | en_HK |
dc.identifier.spage | 872 | en_HK |
dc.identifier.epage | 892 | en_HK |
dc.identifier.isi | WOS:000076179000005 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Ahmad, I=7201878459 | en_HK |
dc.identifier.scopusauthorid | Kwok, YK=7101857718 | en_HK |
dc.identifier.citeulike | 2974118 | - |
dc.identifier.issnl | 1045-9219 | - |