File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/ICPP.1998.708514
- Scopus: eid_2-s2.0-84878660881
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Optimal and near-optimal allocation of precedence-constrained tasks to parallel processors: defying the high complexity using effective search techniques
Title | Optimal and near-optimal allocation of precedence-constrained tasks to parallel processors: defying the high complexity using effective search techniques |
---|---|
Authors | |
Keywords | Computers Computer architecture |
Issue Date | 1998 |
Publisher | IEEE, 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? |
Abstract | Obtaining 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 Identifier | http://hdl.handle.net/10722/54064 |
ISSN | 2020 SCImago Journal Rankings: 0.211 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kwok, YK | en_HK |
dc.contributor.author | Ahmad, I | en_HK |
dc.date.accessioned | 2009-04-03T07:35:48Z | - |
dc.date.available | 2009-04-03T07:35:48Z | - |
dc.date.issued | 1998 | en_HK |
dc.identifier.citation | Proceedings of the 1998 International Conference on Parallel Processing (ICPP'98), Minneapolis, MN, 10-14, August, 1998, p. 424-431 | en_HK |
dc.identifier.issn | 1530-2016 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/54064 | - |
dc.description.abstract | Obtaining 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.language | eng | en_HK |
dc.publisher | IEEE, 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. | - |
dc.subject | Computers | en_HK |
dc.subject | Computer architecture | en_HK |
dc.title | Optimal and near-optimal allocation of precedence-constrained tasks to parallel processors: defying the high complexity using effective search techniques | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.openurl | http://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+techniques | en_HK |
dc.identifier.email | Kwok, YK: ykwok@eee.hku.hk | en_HK |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.doi | 10.1109/ICPP.1998.708514 | en_HK |
dc.identifier.scopus | eid_2-s2.0-84878660881 | - |
dc.identifier.hkuros | 44727 | - |
dc.identifier.issnl | 1530-2016 | - |