BARTHOU, Denis; JEANNOT, Emmanuel

doi:10.1007/978-3-319-09873-9_15

Métadonnées

Licence d’utilisation du document

BARTHOU, Denis
Efficient runtime systems for parallel architectures [RUNTIME]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]

JEANNOT, Emmanuel
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Efficient runtime systems for parallel architectures [RUNTIME]

Langue

Communication dans un congrès

Ce document a été publié dans

Euro-Par, 2014-08-24, Lisboa. 2014, vol. 8632, p. 174 - 185

Résumé en anglais

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.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

SPAGHETtI: Scheduling/Placement Approach for Task-Graphs on HETerogeneous archItecture

Langue

Ce document a été publié dans

Résumé en anglais

URI

DOI

Origine

Unités de recherche