File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors

TitleStatic Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors
Authors
KeywordsAutomatic parallelization
DAG
Multiprocessors
Parallel processing
Software tools
Static scheduling
Task graphs
Issue Date1999
PublisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://surveys.acm.org
Citation
Acm Computing Surveys, 1999, v. 31 n. 4, p. 406-471 How to Cite?
AbstractStatic scheduling of a program represented by a directed task graph on a multiprocessor system to minimize the program completion time is a well-known problem in parallel processing. Since finding an optimal schedule is an NP-complete problem in general, researchers have resorted to devising efficient heuristics. A plethora of heuristics have been proposed based on a wide spectrum of techniques, including branch-and-bound, integer-programming, searching, graphtheory, randomization, genetic algorithms, and evolutionary methods. The objective of this survey is to describe various scheduling algorithms and their functionalities in a contrasting fashion as well as examine their relative merits in terms of performance and time-complexity. Since these algorithms are based on diverse assumptions, they differ in their functionalities, and hence are difficult to describe in a unified context. We propose a taxonomy that classifies these algorithms into different categories. We consider 27 scheduling algorithms, with each algorithm explained through an easy-to-understand description followed by an illustrative example to demonstrate its operation. We also outline some of the novel and promising optimization approaches and current research trends in the area. Finally, we give an overview of the software tools that provide scheduling/mapping functionalities.
Persistent Identifierhttp://hdl.handle.net/10722/73660
ISSN
2023 Impact Factor: 23.8
2023 SCImago Journal Rankings: 6.280
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorKwok, YKen_HK
dc.contributor.authorAhmad, Ien_HK
dc.date.accessioned2010-09-06T06:53:32Z-
dc.date.available2010-09-06T06:53:32Z-
dc.date.issued1999en_HK
dc.identifier.citationAcm Computing Surveys, 1999, v. 31 n. 4, p. 406-471en_HK
dc.identifier.issn0360-0300en_HK
dc.identifier.urihttp://hdl.handle.net/10722/73660-
dc.description.abstractStatic scheduling of a program represented by a directed task graph on a multiprocessor system to minimize the program completion time is a well-known problem in parallel processing. Since finding an optimal schedule is an NP-complete problem in general, researchers have resorted to devising efficient heuristics. A plethora of heuristics have been proposed based on a wide spectrum of techniques, including branch-and-bound, integer-programming, searching, graphtheory, randomization, genetic algorithms, and evolutionary methods. The objective of this survey is to describe various scheduling algorithms and their functionalities in a contrasting fashion as well as examine their relative merits in terms of performance and time-complexity. Since these algorithms are based on diverse assumptions, they differ in their functionalities, and hence are difficult to describe in a unified context. We propose a taxonomy that classifies these algorithms into different categories. We consider 27 scheduling algorithms, with each algorithm explained through an easy-to-understand description followed by an illustrative example to demonstrate its operation. We also outline some of the novel and promising optimization approaches and current research trends in the area. Finally, we give an overview of the software tools that provide scheduling/mapping functionalities.en_HK
dc.languageengen_HK
dc.publisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://surveys.acm.orgen_HK
dc.relation.ispartofACM Computing Surveysen_HK
dc.rightsACM Computing Surveys. Copyright © Association for Computing Machinery, Inc.en_HK
dc.subjectAutomatic parallelizationen_HK
dc.subjectDAGen_HK
dc.subjectMultiprocessorsen_HK
dc.subjectParallel processingen_HK
dc.subjectSoftware toolsen_HK
dc.subjectStatic schedulingen_HK
dc.subjectTask graphsen_HK
dc.titleStatic Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessorsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0360-0300&volume=31&issue=4&spage=406&epage=471&date=1999&atitle=Static+Scheduling+Algorithms+for+Allocating+Directed+Task+Graphs+to+Multiprocessorsen_HK
dc.identifier.emailKwok, YK:ykwok@eee.hku.hken_HK
dc.identifier.authorityKwok, YK=rp00128en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/344588.344618en_HK
dc.identifier.scopuseid_2-s2.0-0002050141en_HK
dc.identifier.hkuros53824en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0002050141&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume31en_HK
dc.identifier.issue4en_HK
dc.identifier.spage406en_HK
dc.identifier.epage471en_HK
dc.identifier.isiWOS:000088698200004-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridKwok, YK=7101857718en_HK
dc.identifier.scopusauthoridAhmad, I=7201878459en_HK
dc.identifier.citeulike173788-
dc.identifier.issnl0360-0300-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats