Comparison of contention aware list scheduling heuristics forcluster computing

摘要

In the area of static scheduling, list scheduling is one of themost common heuristics for the temporal and spatial assignment of aDirected Acyclic Graph (DAG) to a target machine. As most heuristics,list scheduling assumes fully connected homogeneous processors andignores contention on the inter communication links. This articleextends the list scheduling heuristic for contention aware scheduling onheterogenous arbitrary machines. The extension is based on the idea ofscheduling edges to links, likewise the scheduling of nodes toprocessors. Based on this extension, we compare eight priority schemesfor the node order determination of the first phase of list scheduling.Random graphs are generated and scheduled with the different schemes tohomogenous and heterogenous parallel systems from the area of clustercomputing. The experiments demonstrate the appropriateness of ourextended list scheduling for homogeneous and heterogenous clusterarchitectures