A Clustering Algorithm for Scheduling Synchronous Parallel Programs on NOWs

B.R. Arafeh (Oman)


Clustering, scheduling algorithms, synchronous communication, deadlocks, network of workstations.


In this work, we have an interest in developing an efficient heuristic algorithm for scheduling the tasks of a parallel program on clusters of NOW's. The main objective of the proposed algorithm is to consider synchronous communication with deadlock avoidance strategy, for inter task message-passing. That is, the algorithm should avoid merging a task to an already existing cluster, if it may cause a deadlock situation with some other cluster. 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 in the context of a synchronous communication environment.

Important Links:

Go Back