File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors

TitleDynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors
Authors
KeywordsAlgorithms
Clustering
List Scheduling
Multiprocessors
Parallel Scheduling
Processor Allocation
Task Graphs
Issue Date1996
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, 1996, v. 7 n. 5, p. 506-521 How to Cite?
AbstractIn this paper, we propose a static scheduling algorithm for allocating task graphs to fully connected multiprocessors. We discuss six recently reported scheduling algorithms and show that they possess one drawback or the other which can lead to poor performance. The proposed algorithm, which is called the Dynamic Critical-Path (DCP) scheduling algorithm, is different from the previously proposed algorithms in a number of ways. First, it determines the critical path of the task graph and selects the next node to be scheduled in a dynamic fashion. Second, it rearranges the schedule on each processor dynamically in the sense that the positions of the nodes in the partial schedules are not fixed until all nodes have been considered. Third, it selects a suitable processor for a node by looking ahead the potential start times of the remaining nodes on that processor, and schedules relatively less important nodes to the processors already in use. A global as well as a pair-wise comparison is carried out for all seven algorithms under various scheduling conditions. The DCP algorithm outperforms the previous algorithms by a considerable margin. Despite having a number of new features, the DCP algorithm has admissible time complexity, is economical in terms of the number of processors used and is suitable for a wide range of graph structures. © 1996 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/155038
ISSN
2023 Impact Factor: 5.6
2023 SCImago Journal Rankings: 2.340
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorKwok, YKen_US
dc.contributor.authorAhmad, Ien_US
dc.date.accessioned2012-08-08T08:31:37Z-
dc.date.available2012-08-08T08:31:37Z-
dc.date.issued1996en_US
dc.identifier.citationIeee Transactions On Parallel And Distributed Systems, 1996, v. 7 n. 5, p. 506-521en_US
dc.identifier.issn1045-9219en_US
dc.identifier.urihttp://hdl.handle.net/10722/155038-
dc.description.abstractIn this paper, we propose a static scheduling algorithm for allocating task graphs to fully connected multiprocessors. We discuss six recently reported scheduling algorithms and show that they possess one drawback or the other which can lead to poor performance. The proposed algorithm, which is called the Dynamic Critical-Path (DCP) scheduling algorithm, is different from the previously proposed algorithms in a number of ways. First, it determines the critical path of the task graph and selects the next node to be scheduled in a dynamic fashion. Second, it rearranges the schedule on each processor dynamically in the sense that the positions of the nodes in the partial schedules are not fixed until all nodes have been considered. Third, it selects a suitable processor for a node by looking ahead the potential start times of the remaining nodes on that processor, and schedules relatively less important nodes to the processors already in use. A global as well as a pair-wise comparison is carried out for all seven algorithms under various scheduling conditions. The DCP algorithm outperforms the previous algorithms by a considerable margin. Despite having a number of new features, the DCP algorithm has admissible time complexity, is economical in terms of the number of processors used and is suitable for a wide range of graph structures. © 1996 IEEE.en_US
dc.languageengen_US
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tpdsen_US
dc.relation.ispartofIEEE Transactions on Parallel and Distributed Systemsen_US
dc.subjectAlgorithmsen_US
dc.subjectClusteringen_US
dc.subjectList Schedulingen_US
dc.subjectMultiprocessorsen_US
dc.subjectParallel Schedulingen_US
dc.subjectProcessor Allocationen_US
dc.subjectTask Graphsen_US
dc.titleDynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessorsen_US
dc.typeArticleen_US
dc.identifier.emailKwok, YK:ykwok@eee.hku.hken_US
dc.identifier.authorityKwok, YK=rp00128en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/71.503776en_US
dc.identifier.scopuseid_2-s2.0-0030142084en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0030142084&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume7en_US
dc.identifier.issue5en_US
dc.identifier.spage506en_US
dc.identifier.epage521en_US
dc.identifier.isiWOS:A1996UR26300008-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridKwok, YK=7101857718en_US
dc.identifier.scopusauthoridAhmad, I=7201878459en_US
dc.identifier.citeulike2974035-
dc.identifier.issnl1045-9219-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats