CLUSTER-BASED TASK SCHEDULING FOR THE LOGP MODEL

While the task scheduling problem under the delay model has been studied extensively, relatively little research exists for more realistic communication models such as the LogP model which considers, in addition to latency, the cost of sending and receiving messages, and the network or link capacity. The task scheduling problem is known to be NP-complete even under the delay model (a special case of the LogP model). This paper investigates the similarities and differences between task-clustering algorithms for the delay and LogP models, and describes task-scheduling algorithm for the allocation of arbitrary task graphs to fully connected networks of processors under the LogP model. The strategy exploits the replication and clustering of tasks to minimize the ill effects of communication overhead on the makespan. A number of restrictions are presented which are used to simplify the design of the new algorithm. The quality of the schedules produced by the algorithm compare favorably with two well-known delay model-based algorithms and a previously existing LogP strategy.