A Bi-Criteria Algorithm for Scheduling Parallel Task Graphs on Clusters

Frédéric Desprez (1) , Frédéric Suter (2)

1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
2 CC-IN2P3 - Centre de Calcul de l'IN2P3

Applications structured as parallel task graphs exhibit both data and task parallelism, and arise in many domains. Scheduling these applications on parallel platforms has been a long-standing challenge. In the case of a single homogeneous cluster, most of the existing algorithms focus on the reduction of the application completion time (makespan). But in presence of resource managers such as batch schedulers and due to accentuated pressure on energy concerns, the produced schedules also have to be efficient in terms of resource usage. In this paper we propose a novel bi-criteria algorithm, called biCPA, able to optimize these two performance metrics either simultaneously or separately. Using simulation over a wide range of experimental scenarios, we find that biCPA leads to better results than previously published algorithms.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Algorithme et structure de données [cs.DS]

Frédéric Desprez, Frédéric Suter. A Bi-Criteria Algorithm for Scheduling Parallel Task Graphs on Clusters. 10th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, May 2010, Melbourne, Australia. pp.243-252. ⟨hal-00533904⟩