26-28 Jun 2019 Bordeaux (France)
SPAGHETtI: Scheduling/Placement Approach for task-Graphs on HETerogeneous archItecture
Emmanuel Jeannot  1@  , Denis Barthou  2  
1 : Inria Bordeaux - Sud-Ouest
Institut National de Recherche en Informatique et en Automatique
2 : Laboratoire Bordelais de Recherche en Informatique  (LaBRI)  -  Website
L'Institut National de Recherche en Informatique et e n Automatique (INRIA)
Université de Bordeaux -  France

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 |Eis the number of edges, |the number of vertices of the scheduled DAG and |Athe 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.

  • Poster
Online user: 1