Two fast and efficient message scheduling algorithms for data redistribution through a backbone
| Autor: | E. Jeannot, F. Wagner |
|---|---|
| Přispěvatelé: | Algorithms for the Grid (ALGORILLE), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Loria, Publications |
| Jazyk: | angličtina |
| Rok vydání: | 2004 |
| Předmět: |
Computational complexity theory
Computer science [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] graphes bipartis 0102 computer and information sciences 02 engineering and technology Parallel computing computer.software_genre 01 natural sciences grid computing grid Scheduling (computing) 0202 electrical engineering electronic engineering information engineering data redistribution Cluster analysis bipartite graphs Message passing 020206 networking & telecommunications Grid ordonnancement de messages messages scheduling [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH] Grid computing redistribution de données 010201 computation theory & mathematics Bipartite graph kpbs computer |
| Zdroj: | 18th International Parallel and Distributed Processing Symposium-IPDPS'04 18th International Parallel and Distributed Processing Symposium-IPDPS'04, 2004, Santa Fe, New Mexico, 10 p IPDPS |
| Popis: | Colloque avec actes et comité de lecture. internationale.; International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|