SPAGHETtI: Scheduling-Placement Approach for Task-Graphs on HETerogeneous archItectureReport as inadecuate

SPAGHETtI: Scheduling-Placement Approach for Task-Graphs on HETerogeneous archItecture - Download this document for free, or read online. Document in PDF available to download.

1 RUNTIME - Efficient runtime systems for parallel architectures Inria Bordeaux - Sud-Ouest, UB - Université de Bordeaux, CNRS - Centre National de la Recherche Scientifique : UMR5800 2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : We propose a new algorithm, called SPAGHETtI, for static scheduling tasks on an unbounded heterogeneous resources where re-sources belongs to different architecture e.g. CPU or GPU. We show that this algorithm is optimal in complexity O|E||A| 2 + |V ||A|, where |E| is the number of edges, |V | the number of vertices of the scheduled DAG and |A| the number of architectures – usually a small value – and that it is able to compute the optimal makespan. Moreover, the number of resources to be used for executing the schedule is given by a linear time algorithm. When the resources are bounded we provide a method to reduce the number of necessary resources up to the bound providing a set of compromises between the makespan and the size of the infrastructure.

Author: Denis Barthou - Emmanuel Jeannot -



Related documents