Static scheduling of dependent parallel tasks on heterogeneous clusters

• Type: Article in International Conference Proceedings Book
• Date: 2005

Authors

J. Barbosa (Author) FEUP; C. Morais (Author) Other; R. Nóbrega (Author) FEUP; A. P. Monteiro (Author) FEUP

Conference proceedings International

Title: 4th International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks

Pages: 1-8

IEEE Cluster

Boston, 26-09-2005 a 20-09-2005

Scientific classification

CORDIS: Technological sciences > Engineering > Computer engineering

Other information

Abstract (EN): 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 alloted 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.

Language: Portuguese

Type (Professor's evaluation): Scientific