TY - GEN
T1 - Clustering algorithm for scheduling parallel programs on NOWs with synchronization requirements at the application level
AU - Arafeh, B. R.
N1 - Publisher Copyright:
© 2002 IEEE.
PY - 2002
Y1 - 2002
N2 - In this work, we are interested in developing an efficient heuristic algorithm for scheduling the tasks of a parallel program based on the class of UNC (Unbounded Number of Clusters) scheduling algorithms for clusters of NOWs. The main objective of the proposed UNC algorithm is to consider synchronous communication with deadlock avoidance strategy for inter-task message-passing. The proposed algorithm generates non-linear clusters by traversing the task graph (DAG) once, using the Edge-Zeroing (EZ) technique. The objectives of the clustering algorithm is reducing the parallel time of the program, reducing the communication cost, improving the program computation to communication ratio (PCCR), and avoiding deadlock situations. The algorithm achieves its objectives with a time complexity O(|V|(log|V| + (|E|)2)) using nonlinear clustering in order to avoid more than one pass through the task DAG and to be able to deal with task DAGs with fine, medium, and coarse granularity.
AB - In this work, we are interested in developing an efficient heuristic algorithm for scheduling the tasks of a parallel program based on the class of UNC (Unbounded Number of Clusters) scheduling algorithms for clusters of NOWs. The main objective of the proposed UNC algorithm is to consider synchronous communication with deadlock avoidance strategy for inter-task message-passing. The proposed algorithm generates non-linear clusters by traversing the task graph (DAG) once, using the Edge-Zeroing (EZ) technique. The objectives of the clustering algorithm is reducing the parallel time of the program, reducing the communication cost, improving the program computation to communication ratio (PCCR), and avoiding deadlock situations. The algorithm achieves its objectives with a time complexity O(|V|(log|V| + (|E|)2)) using nonlinear clustering in order to avoid more than one pass through the task DAG and to be able to deal with task DAGs with fine, medium, and coarse granularity.
UR - http://www.scopus.com/inward/record.url?scp=84966551184&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84966551184&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2002.1015567
DO - 10.1109/IPDPS.2002.1015567
M3 - Conference contribution
AN - SCOPUS:84966551184
T3 - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002
SP - 625
EP - 632
BT - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 16th International Parallel and Distributed Processing Symposium, IPDPS 2002
Y2 - 15 April 2002 through 19 April 2002
ER -