File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Optimal and near-optimal allocation of precedence-constrained tasks to parallel processors: defying the high complexity using effective search techniques

TitleOptimal and near-optimal allocation of precedence-constrained tasks to parallel processors: defying the high complexity using effective search techniques
Authors
KeywordsComputers
Computer architecture
Issue Date1998
PublisherIEEE, Computer Society.
Citation
Proceedings of the 1998 International Conference on Parallel Processing (ICPP'98), Minneapolis, MN, 10-14, August, 1998, p. 424-431 How to Cite?
AbstractObtaining an optimal schedule for a set of precedence-constrained tasks with arbitrary costs is a well-known NP-complete problem. However, optimal solutions are desired in many situations. In this paper we propose search-based algorithms for determining optimal schedules for moderately large problem sizes. The first algorithm which is based on the A* search technique uses a computationally efficient cost function for guiding the search with reduced complexity. We propose a number of state-pruning techniques to reduce the size of the search space. For further lowering the complexity, we parallelize the search. The parallel version is based on reduced interprocessor communication and is guided by 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 takes 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 for medium to moderately large problems while the approximate algorithm is a useful alternative if slightly degraded solutions are acceptable.
Persistent Identifierhttp://hdl.handle.net/10722/54064
ISSN

 

DC FieldValueLanguage
dc.contributor.authorKwok, YKen_HK
dc.contributor.authorAhmad, Ien_HK
dc.date.accessioned2009-04-03T07:35:48Z-
dc.date.available2009-04-03T07:35:48Z-
dc.date.issued1998en_HK
dc.identifier.citationProceedings of the 1998 International Conference on Parallel Processing (ICPP'98), Minneapolis, MN, 10-14, August, 1998, p. 424-431en_HK
dc.identifier.issn1530-2016en_HK
dc.identifier.urihttp://hdl.handle.net/10722/54064-
dc.description.abstractObtaining an optimal schedule for a set of precedence-constrained tasks with arbitrary costs is a well-known NP-complete problem. However, optimal solutions are desired in many situations. In this paper we propose search-based algorithms for determining optimal schedules for moderately large problem sizes. The first algorithm which is based on the A* search technique uses a computationally efficient cost function for guiding the search with reduced complexity. We propose a number of state-pruning techniques to reduce the size of the search space. For further lowering the complexity, we parallelize the search. The parallel version is based on reduced interprocessor communication and is guided by 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 takes 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 for medium to moderately large problems while the approximate algorithm is a useful alternative if slightly degraded solutions are acceptable.en_HK
dc.languageengen_HK
dc.publisherIEEE, Computer Society.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.en_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectComputersen_HK
dc.subjectComputer architectureen_HK
dc.titleOptimal and near-optimal allocation of precedence-constrained tasks to parallel processors: defying the high complexity using effective search techniquesen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1530-2016&volume=&spage=424&epage=431&date=1998&atitle=Optimal+and+near-optimal+allocation+of+precedence-constrained+tasks+to+parallel+processors:+defying+the+high+complexity+using+effective+search+techniquesen_HK
dc.identifier.emailKwok, YK: ykwok@eee.hku.hken_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/ICPP.1998.708514en_HK
dc.identifier.hkuros44727-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats