File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Benchmarking the task graph scheduling algorithms

TitleBenchmarking the task graph scheduling algorithms
Authors
KeywordsComputers
Computer architecture
Issue Date1998
PublisherI E E E, Computer Society. The Journal's web site is located at http://www.ipdps.org
Citation
Proceedings Of The International Parallel Processing Symposium, Ipps, 1998, p. 531-537 How to Cite?
AbstractThe problem of scheduling a weighted directed acyclic graph (DAG) to a set of homogeneous processors to minimize the completion time has been extensively studied. The NP-completeness of the problem has instigated researchers to propose a myriad of heuristic algorithms. While these algorithms are individually reported to be efficient, it is not clear how effective they are and how well they compare against each other. A comprehensive performance evaluation and comparison of these algorithms entails addressing a number of difficult issues. One of the issues is that a large number of scheduling algorithms are based upon radically different assumptions, making their comparison on a unified basis a rather intricate task. Another issue is that there is no standard set of benchmarks that can be used to evaluate and compare these algorithms. Furthermore, most algorithms are evaluated using small problem sizes, and it is not clear how their performance scales with the problem size. In this paper, we first provide a taxonomy for classifying various algorithms into different categories according to their assumptions and functionalities. We then propose a set of benchmarks which are of diverse structures without being biased towards a particular scheduling technique and still allow variations in important parameters. We have evaluated 15 scheduling algorithms, and compared them using the proposed benchmarks. Based upon the design philosophies and principles behind these algorithms, we interpret the results and discuss why some algorithms perform better than the others.
Persistent Identifierhttp://hdl.handle.net/10722/54065
ISSN

 

DC FieldValueLanguage
dc.contributor.authorKwok, YuKwongen_HK
dc.contributor.authorAhmad, Ishfaqen_HK
dc.date.accessioned2009-04-03T07:35:49Z-
dc.date.available2009-04-03T07:35:49Z-
dc.date.issued1998en_HK
dc.identifier.citationProceedings Of The International Parallel Processing Symposium, Ipps, 1998, p. 531-537en_HK
dc.identifier.issn1063-7133en_HK
dc.identifier.urihttp://hdl.handle.net/10722/54065-
dc.description.abstractThe problem of scheduling a weighted directed acyclic graph (DAG) to a set of homogeneous processors to minimize the completion time has been extensively studied. The NP-completeness of the problem has instigated researchers to propose a myriad of heuristic algorithms. While these algorithms are individually reported to be efficient, it is not clear how effective they are and how well they compare against each other. A comprehensive performance evaluation and comparison of these algorithms entails addressing a number of difficult issues. One of the issues is that a large number of scheduling algorithms are based upon radically different assumptions, making their comparison on a unified basis a rather intricate task. Another issue is that there is no standard set of benchmarks that can be used to evaluate and compare these algorithms. Furthermore, most algorithms are evaluated using small problem sizes, and it is not clear how their performance scales with the problem size. In this paper, we first provide a taxonomy for classifying various algorithms into different categories according to their assumptions and functionalities. We then propose a set of benchmarks which are of diverse structures without being biased towards a particular scheduling technique and still allow variations in important parameters. We have evaluated 15 scheduling algorithms, and compared them using the proposed benchmarks. Based upon the design philosophies and principles behind these algorithms, we interpret the results and discuss why some algorithms perform better than the others.en_HK
dc.languageengen_HK
dc.publisherI E E E, Computer Society. The Journal's web site is located at http://www.ipdps.orgen_HK
dc.relation.ispartofProceedings of the International Parallel Processing Symposium, IPPSen_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.subjectComputersen_HK
dc.subjectComputer architectureen_HK
dc.titleBenchmarking the task graph scheduling algorithmsen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1063-7133&volume=&spage=531&epage=537&date=1998&atitle=Benchmarking+the+task+graph+scheduling+algorithmsen_HK
dc.identifier.emailKwok, YuKwong:ykwok@eee.hku.hken_HK
dc.identifier.authorityKwok, YuKwong=rp00128en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/IPPS.1998.669967en_HK
dc.identifier.scopuseid_2-s2.0-0031700698en_HK
dc.identifier.hkuros37016-
dc.identifier.spage531en_HK
dc.identifier.epage537en_HK
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridKwok, YuKwong=7101857718en_HK
dc.identifier.scopusauthoridAhmad, Ishfaq=7201878459en_HK
dc.identifier.citeulike266337-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats