Asymptotically optimal algorithm for Laplace task graphs on heterogeneous platforms

Olivier Beaumont 1, 2 Pierre Ramet 1, 3 Jean Roman 3, 4
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
3 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
4 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
INRIA Futurs, Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : In this paper, we focus on the scheduling of Laplace task graph on a general platform where both communication links and processing units are heterogeneous. In this context, it is known that deriving optimal algorithm, in the sense of makespan minimization, is NP-Complete, and several inapproximation results have been proved. Nevertheless, we provide an asymtotically optimal algorithm in this general context. Moreover, we expect that this methodolgy can be extended to more general task graphs, especially for nested loops where the inner-most loop is parallel.
Mots-clés : Overlap
Type de document :
Communication dans un congrès
Fifth International Conference on Parallel Processing and Applied Mathematics, Workshop HeteroPar, 2003, Czestochowa, Poland. Springer Verlag, 3019, pp.880--887, 2003, LNCS
Liste complète des métadonnées

https://hal.inria.fr/inria-00346587
Contributeur : Pierre Ramet <>
Soumis le : jeudi 11 décembre 2008 - 18:33:27
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Identifiants

  • HAL Id : inria-00346587, version 1

Collections

Citation

Olivier Beaumont, Pierre Ramet, Jean Roman. Asymptotically optimal algorithm for Laplace task graphs on heterogeneous platforms. Fifth International Conference on Parallel Processing and Applied Mathematics, Workshop HeteroPar, 2003, Czestochowa, Poland. Springer Verlag, 3019, pp.880--887, 2003, LNCS. 〈inria-00346587〉

Partager

Métriques

Consultations de la notice

143