Two fast and efficient message scheduling algorithms for data redistribution through a backbone

Emmanuel Jeannot 1 Frédéric Wagner 1
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we study the problem of redistributing in parallel data between clusters interconnected by a backbone. This problem is a generalization of the well-known redistribution problem that appears in parallelism. We suppose that at most k communications can be performed at the same time (the value of k depending on the characteristics of the platform). We use the knowledge of the application in order to schedule the messages and perform a control of the congestion by ourselves. Previous results show that this problem is NP-Complete. We propose and study two fast and efficient algorithms for this problem. We prove that these algorithms are 2-approximation algorithms. Simulation results show that both algorithms perform very well compared to the optimal solution. These algorithms have been implemented using MPI. Experimental results show that both algorithms outperform a brute-force TCP based solution, where no scheduling of the messages is performed.
Mots-clés : redistribution de données data redistribution messages scheduling bipartite graphs grid computing ordonnancement de messages graphes bipartis grid kpbs
Type de document :
Communication dans un congrès
18th International Parallel and Distributed Processing Symposium - IPDPS'04, 2004, Santa Fe, New Mexico, IEEE, 10 p, 2004
Liste complète des métadonnées
https://hal.inria.fr/inria-00099979
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:13:04
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099979, version 1

Collections

INRIA | LORIA | UNIV-LORRAINE

Citation

Emmanuel Jeannot, Frédéric Wagner. Two fast and efficient message scheduling algorithms for data redistribution through a backbone. 18th International Parallel and Distributed Processing Symposium - IPDPS'04, 2004, Santa Fe, New Mexico, IEEE, 10 p, 2004. 〈inria-00099979〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

160

Contact


archive-ouverte@inria.fr