Portal de Periódicos da CAPES

Static scheduling of dependent parallel tasks on heterogeneous clusters

2005; Institute of Electrical and Electronics Engineers; Linguagem: Inglês

10.1109/clustr.2005.347024

2168-9253

Jorge G. Barbosa, Carla Morais, Rui Nóbrega, Alexandrina Monteiro,

Interconnection Networks and Systems

This paper addresses the problem of scheduling parallel tasks, represented by a direct acyclic graph (DAG) on heterogeneous clusters. Parallel tasks, also called malleable tasks, are tasks that can be executed on any number of processors with its execution time being a function of the number of processors allotted to it. The scheduling of independent parallel tasks on homogeneous machines has been extensively studied and the case of parallel tasks with precedence constraints has been studied for tree-like graphs. For arbitrary precedence graphs and for heterogeneous machines, the optimization problem is more complex because the processing time of a given task depends on the number of processors and on the total processing capacity of those processors. This paper presents a list scheduling algorithm to minimize the total length of the schedule (makespan) of a given set of parallel tasks, whose dependencies are represented by a DAG