File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On multiprocessor task scheduling using efficient state space search approaches

TitleOn multiprocessor task scheduling using efficient state space search approaches
Authors
KeywordsMultiprocessors
Optimal scheduling
Parallel A
Parallel processing
State-space search
Task graphs
Issue Date2005
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jpdc
Citation
Journal Of Parallel And Distributed Computing, 2005, v. 65 n. 12, p. 1515-1532 How to Cite?
AbstractObtaining an optimal schedule for a set of precedence-constrained tasks is a well-known NP-complete problem in its general form. In view of the intractability of the problem, most of the previous work relies on heuristics that try to find reasonably high quality solutions in an acceptable amount of time. While optimal polynomial-time algorithms are known only for a few simple cases (and in other cases can only be obtained through an exhaustive search with prohibitively high time complexity), they may be critically important for applications in which performance is the prime objective. Optimal solutions can also serve as a reference to test the performance of various heuristics. Moreover, an optimal schedule for a program at hand needs to be determined only once (and off-line) but the program using that schedule is in general executed several times. In this paper, we propose optimal algorithms for static scheduling of task graphs with arbitrary parameters to multiple homogeneous processors. The first algorithm is based on the A* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity. Additionally, we propose a number of effective state-pruning techniques to reduce the search space. For further lowering the complexity, we propose an efficient parallelization of the search algorithm. We parallelize the algorithm with reduced interprocessor communication as well as with static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but executes in a considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions of reasonably large problems while the approximate algorithm is effective if slightly degraded solutions are acceptable. © 2005 Elsevier Inc. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/73897
ISSN
2023 Impact Factor: 3.4
2023 SCImago Journal Rankings: 1.187
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorKwok, YKen_HK
dc.contributor.authorAhmad, Ien_HK
dc.date.accessioned2010-09-06T06:55:49Z-
dc.date.available2010-09-06T06:55:49Z-
dc.date.issued2005en_HK
dc.identifier.citationJournal Of Parallel And Distributed Computing, 2005, v. 65 n. 12, p. 1515-1532en_HK
dc.identifier.issn0743-7315en_HK
dc.identifier.urihttp://hdl.handle.net/10722/73897-
dc.description.abstractObtaining an optimal schedule for a set of precedence-constrained tasks is a well-known NP-complete problem in its general form. In view of the intractability of the problem, most of the previous work relies on heuristics that try to find reasonably high quality solutions in an acceptable amount of time. While optimal polynomial-time algorithms are known only for a few simple cases (and in other cases can only be obtained through an exhaustive search with prohibitively high time complexity), they may be critically important for applications in which performance is the prime objective. Optimal solutions can also serve as a reference to test the performance of various heuristics. Moreover, an optimal schedule for a program at hand needs to be determined only once (and off-line) but the program using that schedule is in general executed several times. In this paper, we propose optimal algorithms for static scheduling of task graphs with arbitrary parameters to multiple homogeneous processors. The first algorithm is based on the A* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity. Additionally, we propose a number of effective state-pruning techniques to reduce the search space. For further lowering the complexity, we propose an efficient parallelization of the search algorithm. We parallelize the algorithm with reduced interprocessor communication as well as with static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but executes in a considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions of reasonably large problems while the approximate algorithm is effective if slightly degraded solutions are acceptable. © 2005 Elsevier Inc. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jpdcen_HK
dc.relation.ispartofJournal of Parallel and Distributed Computingen_HK
dc.subjectMultiprocessorsen_HK
dc.subjectOptimal schedulingen_HK
dc.subjectParallel Aen_HK
dc.subjectParallel processingen_HK
dc.subjectState-space searchen_HK
dc.subjectTask graphsen_HK
dc.titleOn multiprocessor task scheduling using efficient state space search approachesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0743-7315&volume=65&issue=12&spage=1515&epage=1532&date=2005&atitle=On+Multiprocessor+Task+Scheduling+Using+Efficient+State+Space+Search+Approachesen_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.1016/j.jpdc.2005.05.028en_HK
dc.identifier.scopuseid_2-s2.0-27844522261en_HK
dc.identifier.hkuros120624en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-27844522261&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume65en_HK
dc.identifier.issue12en_HK
dc.identifier.spage1515en_HK
dc.identifier.epage1532en_HK
dc.identifier.isiWOS:000233760100004-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridKwok, YK=7101857718en_HK
dc.identifier.scopusauthoridAhmad, I=7201878459en_HK
dc.identifier.issnl0743-7315-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats