TY - GEN
T1 - A new heuristic for scheduling parallel programs on multiprocessor
AU - Liou, Jing Chiou
AU - Palis, Michael A.
N1 - Publisher Copyright:
© 1998 IEEE.
PY - 1998
Y1 - 1998
N2 - In this paper we present an efficient algorithm, called CASS-II, for task clustering without task duplication. Unlike the DSC algorithm, which is empirically the best known algorithm to date in terms of both speed and solution quality, CASS-II uses only limited »global» information and does not recompute the critical path in each refinement step. Therefore, the algorithm runs in O(|E|+|V|lg|V|) which is faster than O((|V|+|E|)lg|V|) of the DSC algorithm. Indeed, our experimental results show that CASS-II is between 3 to 5 times faster than DSC. (It is worth pointing out that we used the C code for DSC developed by the authors of the DSC algorithm. The C code for CASS-II was developed by the authors of this paper). With respect to solution quality, experimental results show that CASS-II is virtually as good as DSC and, in fact, even outperforms DSC for very fine grain DAGs (granularity less than 0.6).
AB - In this paper we present an efficient algorithm, called CASS-II, for task clustering without task duplication. Unlike the DSC algorithm, which is empirically the best known algorithm to date in terms of both speed and solution quality, CASS-II uses only limited »global» information and does not recompute the critical path in each refinement step. Therefore, the algorithm runs in O(|E|+|V|lg|V|) which is faster than O((|V|+|E|)lg|V|) of the DSC algorithm. Indeed, our experimental results show that CASS-II is between 3 to 5 times faster than DSC. (It is worth pointing out that we used the C code for DSC developed by the authors of the DSC algorithm. The C code for CASS-II was developed by the authors of this paper). With respect to solution quality, experimental results show that CASS-II is virtually as good as DSC and, in fact, even outperforms DSC for very fine grain DAGs (granularity less than 0.6).
UR - http://www.scopus.com/inward/record.url?scp=0004511937&partnerID=8YFLogxK
U2 - 10.1109/PACT.1998.727277
DO - 10.1109/PACT.1998.727277
M3 - Conference contribution
AN - SCOPUS:0004511937
T3 - Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT
SP - 358
EP - 365
BT - Proceedings - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998
Y2 - 12 October 1998 through 18 October 1998
ER -