LaPIe : Communications Collectives adaptées aux Grilles de Calcul

The popularity of heterogeneous parallel processing environments like clusters and computer grids has emphasised the impact of network heterogeneity on the performance of parallel applications. Collective communication operations are especially concerned by this problem, as communication heterogeneity interfers directly on the performance of the communication strategies. Therefore, the aim of this dissertation is the study the optimisation of collective communications in heterogeneous systems like computational grids. We investigate how to optimise communications according to the approach proposed by Karonis, where the communication among the different clusters that compose a grid are organised in multiple levels, minimising the total communication time (makespan). Hence, in a first moment, we study how to accurately model the performance of collective communications in homogeneous clusters, and, we validate such models under different network architectures. In parallel, we study how to minimise the impact of network heterogeneity on the complexity of communication scheduling techniques. Therefore, we investigated how topology discovery techniques can be used to decompose the grid environment into islands of homogeneous clusters, more adapted to an hierarchical modelling of the network. Finally, we study how performance modelling and topology discovery can be associated to construct gridaware collective communications. Using the information from both performance models and network topology, we compare different communication scheduling heuristics present on the literature. We also propose new heuristics to schedule inter-cluster communications, taking into account the performance of each different cluster. These heuristics seem to be specially efficient when the number of interconnected clusters augments, a tendency for the next years.Avec la démocratisation des environnements du type grappe et grille de calcul, la performance des opérations de communication collective devient un aspect critique dans le coût total des applications parallèles. Fortement influencées par l'hétérogénéité des ressources, ces opérations dépendent à la fois des paramètres de communication des réseaux et des stratégies de communication employées. Cette thèse a pour objet d'étude l'optimisation des communications collectives selon l'approche préconisée par Karonis, où les différentes grappes de calcul sont organisées en plusieurs couches de communication de manière à minimiser le temps total de communication. Pour cela, nous proposons des modèles de communications qui permettent l'optimisation des communications collectives à travers l'ordonnancement hiérarchique des communications et la prédiction des performances. Dans un premier temps, nous démontrons que l'utilisation du modèle de coût pLogP permet la modélisation des performances de communications collectives dans des environnements homogènes. Ces modèles de performance ont été validés expérimentalement sur différentes plates-formes réseaux (Fast Ethernet, Giga Ethernet et Myrinet). Parallèlement, nous étudions la découverte automatique de la topologie du réseau. En effet, la décomposition de l'environnement de grille en îlots d'homogénéité permettrait la réduction de la complexité des optimisations, notamment dans ce qui concerne la modélisation des performances et l'obtention des caractéristiques du réseau. Notre principale contribution a été de proposer certaines heuristiques d'ordonnancement des communications qui tiennent compte de l'organisation hiérarchique de la grille. Ces heuristiques, adaptées aux différents patrons de communication collective, utilisent les techniques étudiées précédemment (dont la découverte des îlots d'homogénéité et la modélisation des performances) afin de réduire la complexité de l'optimisation des communications et de minimiser le temps total de communication