Execution Efficace d'une Application de Calcul Distribué sur une Grille de Calcul

RAPPORT DE STAGE

Stage e�ectué à l'ÉCOLE NORMALE SUPÉRIEURE DE LYONLABORATOIRE DE L'INFORMATIQUE DU PARALLÉLISME (LIP)

pour l'obtention du diplôme de Master

Exécution E�cace d'une Applicationde Calcul Distribué sur une Grille de

Calcul

Par :

EWELLE EWELLE [email protected]

Encadrant :

Monsieur Olivier GLUCK (UCB Lyon)[email protected]

Hanoi, décembre 2010

Remerciements

Un stage est une route que l'on ne parcours pas seul. Pour cela avant de vous présentermon travail, je tiens à remercier tous ceux qui m'ont aidé à la réalisation de ce travail.

Mes premiers remerciements vont à mon encadreur Olivier GLUCK pour le temps qu'ilm'a consacré durant ce stage, son soutien, ses conseils scienti�ques, sa disponibilité et sesaides précieuses qui ont été nécessaires pour aller jusqu'au bout de ce travail de stage. Jetiens également à remercier tous les membres de l'équipe RESO du LIP, pour leur amitié, leursoutien et leur accueil dans le groupe.

Je remercie ensuite mes enseignants de l'IFI, Messieurs Nguyen Hong Quang, Victor Mo-raru et Alain Boucher pour leur disponibilité et le partage de leurs connaissances, mes ca-marades de classe qui m'ont accueilli et couvert de beaucoup de chaleur pendant ces annéespassées au Vietnam. Je fais un clin d'÷il particulier à Van Dan, Manh Cuong, Ngoc Khuonget Ngoc Thang.

Je ne saurais terminer sans remercier le seigneur mon Dieu sans qui rien de ceci ne seraitpossible, les membres de ma grande famille au Cameroun pour leurs encouragements, leursprières et leur présence malgré la distance et en�n mes frères Camerounais de l'IFI qui m'ontsoutenu durant mon séjour au Vietnam. Je pense à Landry, Hervé, Dieudonné et William.

Résumé

L'exécution en parallèle des tâches d'une application dans un système distribué permetla mise en commun de la puissance de calcul de plusieurs processeurs ce qui se traduit pardes économies en temps dans presque tous les domaines du calcul. Dans l'évolution du calculparallèle, plusieurs auteurs ([Hab09], [HGM+09]) ont remarqués que les standards commeMPI[MPI09] (Message Passing Interface) ne gèrent pas de manière e�cace les communicationsentre des machines séparées par un réseau longue distance. En e�et, deux problèmes se posent :Premièrement, les messages MPI sont transmis de manière �able sur le réseau longue distancevia le protocole TCP. Or TCP est basé sur un transfert de données par �ux ; il est doncpeu adapté aux communications MPI. Ensuite, la grande latence du réseau longue distanceimplique des communications et des retransmissions de paquets perdus qui sont coûteuses.Ceci introduit donc la problématique de la réduction de l'impact des mécanismes de TCP surles communications MPI longue distance.

Une thèse sur ce sujet a été e�ectuée par Ludovic Hablot [Hab09], thèse au cours de la-quelle une approche a été proposée : L'éclatement des connexions TCP qui consiste à éclaterune connexion TCP longue distance en trois connexions di�érentes : une connexion locale,une connexion longue distance, et une connexion locale. Ce qui permet par intermédiaire depasserelles à l'interface LAN-WAN de di�érencier les deux types de tra�c a�n d'améliorerl'exécution d'applications MPI sur une grille.

Ce stage se place dans la continuité de ce travail de thèse et se propose de résoudre quelquesproblèmes pas complètement résolus avec l'éclatement des connexions TCP. Notre contributionse matérialise ainsi par la proposition, l'étude et la mise en ÷uvre de 4 approches (dont uneseule a été validée par expérimentation) visant toutes à améliorer les communications desapplications dans le cadre de l'éclatement des connexions TCP.

Dans ce rapport, nous faisons d'abord le point sur l'architecture MPI5000 proposée parLudovic Hablot, en analysant ses avantages et ses inconvénients, a�n de déboucher sur despistes ou des questions visant à diminuer les surcoûts introduits par cette approche. Aprèsl'état de l'art sur chacune des questions soulevées, nous présentons la modélisation et la miseen ÷uvre de nos di�érentes approches. Les résultats de l'évaluation de la méthode d'ordonnan-cement de messages montrent qu'un ordonnancement e�cace permet une diminution du goulotd'étranglement créé sur les passerelles par l'éclatement des connexions TCP, rendant ainsi lescommunications plus rapides et donc permet une complétion au plus tôt de l'application.

Mots-clés : grille de calcul, MPI, TCP, GridFTP, ordonnancement, placement.

Abstract

Parallel execution of application's tasks in a distributed system allows the pooling of com-puting power of multiple processors resulting into savings in execution time in almost all areasof computing. In the evolution of distributed systems and parallel computing, several authors([Hab09], [HGM+09]) have noticed that standards such as MPI do not handle e�ciently com-munications between machines separated by a WAN connection. In fact, two problems arise :First, MPI messages are transmitted reliably over the WAN via TCP. Yet, TCP is designedfor Internet-type network, but still the most used transport protocol in Grids. TCP is basedon a �ow data transfer and is therefore not suitable for MPI communications. Then, the largelatency of WAN implies costly communications and retransmission of lost packets. This there-fore introduces the question of reducing the impact of TCP mechanisms on MPI long distancecommunications.

A PhD thesis on this subject was conducted by Ludovic Hablot [Hab09] and an approachwas proposed : Splitting TCP connections. This approach involves dividing a long distanceTCP connection in three di�erent connections : a local connection, a long distance connection,and a local connection. Allowing through gateways on the LAN-WAN interface to di�erentiatethe two types of tra�c to improve the performance of MPI applications on a Grid.

This internship is in the continuity of this thesis and proposes to solve some problemsthat are not completely solved with the Splitting of TCP connections. Our contribution ismaterialized by the proposal and the design of 4 approaches (of which only one has beenvalidated by experiment), all aimed at optimising application's communications in the Splittingof TCP connections approach.

In this report, we �rst make an update on the architecture MPI5000 proposed by LudovicHablot, analyzing its advantages and disadvantages with the objective of �nding ways orquestions related to the issue of reducing the overhead introduced by this approach. Afterthe state of the art on each issue raised, we present the modeling and implementation ofour di�erent approaches. The results of the evaluation of the scheduling method show thate�cient scheduling can decrease the bottleneck created on the gateways with the Splitting ofTCP connections, making communications faster and therefore allows completion of the earlierapplication.

Keywords : Grid computing, MPI, TCP, GridFTP, scheduling, placement.

Table des matières

Remerciements

Résumé

Abstract

1 Introduction 11.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Applications parallèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Les grilles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Éclatement des connexions TCP : Architecture MPI5000 . . . . . . . . . . . . . 6

1.4.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4.2 Hypothèses et contribution . . . . . . . . . . . . . . . . . . . . . . . . . 71.4.3 Performances de MPI5000 . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Organisation du document . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Problématique 112.1 Amélioration des passerelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.1 Diminution du nombre de recopies . . . . . . . . . . . . . . . . . . . . . 122.1.2 Ordonnancement e�cace des messages . . . . . . . . . . . . . . . . . . . 13

2.2 Architecture d'exécution de l'application et TCP . . . . . . . . . . . . . . . . 132.2.1 Placement e�cace des tâches . . . . . . . . . . . . . . . . . . . . . . . . 142.2.2 Plusieurs connexions TCP sur le WAN . . . . . . . . . . . . . . . . . . 142.2.3 Choix d'utilisation ou pas des passerelles . . . . . . . . . . . . . . . . . 15

3 État de l'art 173.1 Ordonnancement e�cace des messages . . . . . . . . . . . . . . . . . . . . . . . 183.2 Placement e�cace des tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.3 Plusieurs connexions TCP sur le WAN . . . . . . . . . . . . . . . . . . . . . . . 213.4 Choix d'utilisation ou pas des passerelles . . . . . . . . . . . . . . . . . . . . . . 223.5 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.6 Propositions et Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Ordonnancement 254.1 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.1.1 Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.1.2 Modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.1.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

TABLE DES MATIÈRES

4.2 Mise en ÷uvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.2.1 Correspondance Paquet-Type de message . . . . . . . . . . . . . . . . . 314.2.2 Etiquetage des paquets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.3 Validation expérimentale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.3.1 Analyse des communications des NPB . . . . . . . . . . . . . . . . . . . 344.3.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.3.3 Gain sur les communications . . . . . . . . . . . . . . . . . . . . . . . . 38

4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5 Autres propositions 405.1 Placement e�cace des tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.1.1 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.1.2 Méthode de placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.2 Plusieurs connexions TCP sur le WAN . . . . . . . . . . . . . . . . . . . . . . . 435.2.1 Quelques mots sur le contrôle de congestion de TCP . . . . . . . . . . . 445.2.2 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.2.3 Mise en ÷uvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.3 Choix d'utilisation ou pas des passerelles . . . . . . . . . . . . . . . . . . . . . . 465.3.1 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.3.2 Mise en ÷uvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6 Conclusion 486.1 Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Appendices 57

A Algorithmes 58

Table des �gures

1.1 Exemple d'un cluster de clusters [Hab09]. . . . . . . . . . . . . . . . . . . . . . 41.2 Grille hétérogène multi-site [JEA07]. . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Vue d'ensemble de la grille Grid5000 [Hab09]. . . . . . . . . . . . . . . . . . . . 51.4 Eclatement des connexions TCP à l'aide de passerelles [Hab09]. . . . . . . . . . 71.5 Banc d'essai générique utilisé dans nos expériences [Hab09]. . . . . . . . . . . . 81.6 Temps d'exécution des NPB avec MPI5000 normalisés par MPICH2 [Hab09]. . 91.7 Recopies dans chaque passerelle [Hab09]. . . . . . . . . . . . . . . . . . . . . . . 9

2.1 Files d'attente de grandes tailles sur les passerelles. . . . . . . . . . . . . . . . . 142.2 Files d'attente de tailles moyennes sur les passerelles. . . . . . . . . . . . . . . . 152.3 Files d'attente de petites tailles sur les passerelles. . . . . . . . . . . . . . . . . 16

3.1 Deux clusters reliés par une dorsale lente [Fre05]. . . . . . . . . . . . . . . . . . 193.2 Déploiement automatique d'une application MPI [LPP05]. . . . . . . . . . . . . 21

4.1 Exemple d'opérations collectives. . . . . . . . . . . . . . . . . . . . . . . . . . . 274.2 Ordonnancement suivant la taille des messages. . . . . . . . . . . . . . . . . . . 294.3 Ordonnancement des messages MPI. . . . . . . . . . . . . . . . . . . . . . . . . 314.4 Entête des paquets MPI avec Données. . . . . . . . . . . . . . . . . . . . . . . . 324.5 Entête MPI5000 + Type de Message. . . . . . . . . . . . . . . . . . . . . . . . . 334.6 Résultats de l'ordonnancement. . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.1 Évolution de la fenêtre de congestion de TCP New Reno. . . . . . . . . . . . . 445.2 Plusieurs connexions sur le WAN. . . . . . . . . . . . . . . . . . . . . . . . . . . 455.3 Choix d'utilisation d'MPI5000. . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

Liste des tableaux

2.1 Latence et débit MPI sans et avec MPI5000 sur la grille[01]. . . . . . . . . . . . 12

4.1 Comparaison des communications des NAS . . . . . . . . . . . . . . . . . . . . 344.2 Récapitulatif des résultats des NAS . . . . . . . . . . . . . . . . . . . . . . . . . 374.3 Gain sur les communications des NPB . . . . . . . . . . . . . . . . . . . . . . . 38

5.1 Schémas de communication de IS (Wi,j) . . . . . . . . . . . . . . . . . . . . . . 43

Chapitre 1

Introduction

1.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Applications parallèles . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Les grilles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 Éclatement des connexions TCP : Architecture MPI5000 . . . . . 6

1.4.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.2 Hypothèses et contribution . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.3 Performances de MPI5000 . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Organisation du document . . . . . . . . . . . . . . . . . . . . . . . . 10

1

CHAPITRE 1. INTRODUCTION 2

Dans ces travaux de stage, l'objectif général est de permettre à la mesure du possible,une exécution e�cace des applications distribuées dans les grilles de calcul. Dans ce premierchapitre, il sera question de présenter le contexte du sujet, les applications cibles et leurs ar-chitectures d'exécution, les travaux précédents [Hab09] dont ce stage constitue une continuité,avant de préciser les objectifs précis du stage.

1.1 Contexte

Dans l'évolution des moyens informatiques dédiés à la résolution de problèmes scienti�ques,plusieurs générations se sont succédées. La science avançant à grands pas et les problèmes à ré-soudre étant toujours plus complexes, la puissance d'un seul processeur n'était plus su�sante.L'ère du parallélisme est donc apparue. L'idée est de diviser un problème complexe en plu-sieurs problèmes simples a�n de pouvoir les résoudre sur plusieurs processeurs simultanément.Le calcul parallèle permet donc, contrairement aux applications classiques qui exécutent unalgorithme de manière séquentielle sur un seul processeur, d'exécuter des tâches d'une mêmeapplication sur plusieurs processeurs en même temps. Cette exécution simultanée des tâchespermet de booster les capacités de calcul, diminuant ainsi considérablement le temps d'exécu-tion des applications. Les applications parallèles s'appuient la plupart du temps sur le standardMPI[MPI09] (Message Passing Interface) qui fonctionne par passage de message.

Dans l'évolution des systèmes distribués et du calcul parallèle, plusieurs auteurs ([Hab09] ,[HGM+09]) ont remarqués que les standards comme MPI ne sont pas particulièrement e�caceslorsqu'il s'agit de distribuer le calcul entre des machines séparées par un réseau longue distance.En e�et, deux problèmes se posent : Tout d'abord, les messages MPI sont transmis de manière�able sur le réseau longue distance via le protocole TCP[Ins81]. Or TCP, qui reste le protocolede transport utilisé dans la plupart des grilles, est basé sur un transfert de données à l'aidede �ux ; il est donc peu adapté aux communications MPI. Ensuite, la grande latence duréseau longue distance implique des communications et des retransmissions de paquets perdusqui sont coûteuses. Une question importante qu'il faut se poser ici c'est de savoir commentéliminer si non réduire l'impact de TCP sur les communications MPI longue distance. Unethèse [Hab09] a été réalisée sur ce sujet et il a été question d'étudier en détails les interactionsentre les applications parallèles et la couche de transport dans le réseau longue distance etde proposer une solution au problème de latence observé. Il en est ressorti, une approche :l'éclatement des connexions TCP qui consiste à diviser une connexion TCP longue distance partrois connexions di�érentes : une connexion locale(LAN - Local Area Network), une connexionlongue distance(WAN - Wide Area Network), et une autre connexion locale(LAN - Local AreaNetwork). Ce qui permet par l'intermédiaire de proxy à l'interface LAN-WAN de di�érencierles deux types de tra�c a�n d'améliorer l'exécution d'application MPI sur une grille.

Ce stage se situe dans le cadre de la suite de ces travaux et se propose de résoudre quelquesproblèmes pas complètement résolus avec l'éclatement des connexions TCP.

1.2 Applications parallèles

Durant des décennies, la plupart des ordinateurs étaient séquentiels ; le processeur exécu-tait les instructions une par une telle qu'elles lui étaient fournies. L'exécution en parallèle destâches d'une application dans un système distribué permet la mise en commun de la puissancede calcul de plusieurs processeurs ce qui se traduit par des économies en temps dans presque


tous les domaines du calcul, incluant : la dynamique des �uides, les prédictions météorolo-giques, la modélisation et simulation de problèmes de dimensions plus grandes, le traitementde l'information et l'exploration de données, le traitement d'images ou la fabrication d'imagesde synthèse (avec les fermes de rendu), l'intelligence arti�cielle et la fabrication automati-sée. Dans la littérature, il existe plusieurs standards pour la parallélisation des tâches d'uneapplication : OpenMP[Ope] (Open MultiProcessing), une API de programmation parallèledestinée à l'exécution d'applications sur des architectures multiprocesseurs à mémoire parta-gée. PVM [GBD+94] (Parallel Virtual Machine), un logiciel de programmation parallèle peu àpeu abandonné au pro�t du standard MPI. De ce fait, MPI devient le standard de fait pourl'exécution d'applications MPI dans une grille de calcul.

MPI est un standard d'une bibliothèque de communication pour applications parallèles,dont il existe plusieurs implémentations di�érentes, qui permet l'échange de messages entreles di�érentes tâches d'une même application parallèle. Dans un modèle de programmationparallèle suivant le standard MPI, le programme est dupliqué sur plusieurs processus. Chaqueprocessus exécute un exemplaire du programme et a accès à sa mémoire propre. La commu-nication entre processus se fait uniquement par passage de messages entre processus. Techni-quement, cette communication se fait via des fonctions de la bibliothèque MPI appelées dansle programme. Ces fonctions peuvent être soit point à point pour l'échange de messages entredeux processus, ou des opérations collectives qui impliquent plusieurs processus. Les deux pri-mitives standards d'envoi et de réception de messages sont MPI_SEND et MPI_RECV. Lescommunications peuvent être bloquantes ou non bloquantes.

1.3 Les grilles

Cluster

Les clusters (également appelés graphes) sont des architectures qui inter-connectent desordinateurs �grand public�, peu couteux, par un réseau local (LAN), dans le but de disposerd'une puissance de calcul plus grande et extensible. Cependant, ces performances restent légè-rement en dessous de celles observées pour les communications au sein d'un supercalculateur.Il est donc plus coûteux de communiquer entre deux machines d'un cluster qu'entre deux pro-cesseurs situés au sein de la même machine. Pour étendre toujours plus la puissance de calculet donc le nombre de machines de la plateforme d'exécution, il arrive qu'il soit nécessaire d'in-terconnecter des machines géographiquement voisines mais avec des réseaux locaux distincts,pour ne faire qu'une seule plateforme. Nous parlons alors de cluster de clusters. La �gure 1.1([Hab09]) montre une interconnexion de deux clusters (1 et 2). Le cluster 1 est connecté parun réseau Myrinet alors que le cluster 2 possède un réseau Quadrics. Les deux clusters sontinterconnectés par un réseau Ethernet commun ainsi que par une passerelle qui possède lesdeux interfaces.

Grille de calcul

Le concept de grille de calcul a été introduit pour la première fois en 1999 par Ian Fos-ter et Carl Kesselman [FK99] qui l'ont dé�ni comme étant une coordination bon marché deressources matérielles et logicielles qui fournit une haute puissance de calcul. En e�et, unegrille informatique est une infrastructure virtuelle constituée d'un ensemble de ressources in-formatiques potentiellement partagées, distribuées, hétérogènes, délocalisées et autonomes. Unmodèle de grille le plus utilisé présente une architecture hétérogène. Comme le montre la �-


Figure 1.1 � Exemple d'un cluster de clusters [Hab09].

Figure 1.2 � Grille hétérogène multi-site [JEA07].

gure 1.2 ([JEA07]), une telle grille peut être constituée de super-calculateurs, de cluster declusters, de réseaux de stations de travail ou encore d'ordinateurs personnels. Ces ressourcessont connectées par des réseaux SAN (Storage Area Network) ou LAN au sein d'une mêmeinstitution et via un WAN entre deux institutions. L'échelle considérée peut être très grande,certaines ressources peuvent être très stables et d'autres très volatiles.

Di�érents projets de grilles scienti�ques ont vu le jour ces dernières années, parmi lesquelson peut citer EGEE [GJG+05] (Enabling Grids for E-sciencE, Europe), NAREGI [Miu06](NationalREsearch Grid Initiative, Japon), ou TeraGrid [C+07](États-Unis). D'autres projets commeDAS-3 [DAS](Distributed ASCI Supercomputer 3, Pays-bas), ou encore Grid5000 [BCC+06](France)sont uniquement dédiés aux recherches sur les grilles et ne servent pas de grille de production.

Plusieurs dé�nitions de la grille de calcul peuvent être trouvées dans la littérature. Pournotre part, nous utiliserons une dé�nition plus précise mais plus réduite de la grille qui estbasée sur la notion de cluster : cluster de clusters d'ordinateurs indépendants mais reliés enréseau et fonctionnant comme un seul et même système, et fournit une énorme puissance pourtraiter les données. Une grille est donc une agrégation de clusters ou de clusters de clusters,


Liens 10 GbE

Liens 1 GbE

Lyon

Bordeaux

Lille

Grenoble

Nancy

Rennes

SophiaToulouse

Orsay

48 noeuds

Bordemer

Myrinet 2000 Infiniband 10G

51 noeuds

Bordeplage

Ethernet 1G

93 noeuds

Bordereau

Myrinet 10G

10 noeuds

Borderline

Infiniband 10G

Ethernet 1G

53 noeuds

Chuque

Myrinet 10G

20 noeuds

Chti

Myrinet 10G

26 noeuds

Chicon

Myrinet 10G

46 noeuds

ChinqChint

Infiniband 20G

34 noeuds

Genepi

Ethernet 1G

120 noeuds

Grelon

Myrinet 10G

33 noeuds

Paramount

Myrinet 10G

64 noeuds

Paraquad

Ethernet 1G

64 noeuds

Paradent

2* Ethernet 1G

50 noeuds

Sol

Myrinet 2000

56 noeuds

Helios

Myrinet 2000

72 noeuds

Azur

Ethernet 1G

57 noeuds

Violette

Ethernet 1G

80 noeuds

Pastel

Myrinet 10G

312 noeuds

GDX

2 * Ethernet 1G

30 noeuds

NetGDX

Myrinet 2000

56 noeuds

Capricorne

Ethernet 1G

79 noeuds

Sagittaire

Griffon

92 noeuds

Infiniband 20G

Figure 1.3 � Vue d'ensemble de la grille Grid5000 [Hab09].

géographiquement éloignés et inter-connectés par un réseau longue distance. La �gure 1.3représente une vue d'ensemble de la grille Grid5000. Cette grille inter-connecte 9 sites (clustersou clusters de clusters) répartis sur toute la France(Bordeaux, Grenoble, Lille, Lyon, Nancy,Orsay, Rennes, Sophia et Toulouse).

Cette dé�nition, nous permet de mettre en exergue certaines spéci�cités des grilles de calculpar rapport aux autres architectures distribuées :

1. Hétérogénéité des machines : Les machines ont des capacités de calcul (nombre/puissancedes c÷urs/processeurs...), des capacités mémoire et de stockage di�érentes. Il est doncnécessaire de tenir compte de cette hétérogénéité lors du placement des processus d'uneapplication sur les ressources obtenues pour son exécution.

2. Hétérogénéité des réseaux : Chaque cluster utilise un, voire plusieurs réseaux rapidespermettant d'inter-connecter ses n÷uds localement. Ces réseaux fournissent une bandepassante élevée ainsi qu'une faible latence. Ils peuvent di�érer d'un cluster à l'autre.Les communications locales du cluster A peuvent par exemple utiliser un réseau de typeMyrinet et celles du cluster B un réseau de type In�niband. La di�culté consiste alorsà faire communiquer entre elles des machines qui utilisent des réseaux di�érents.

3. Grande latence WAN : La latence est plus grande sur le réseau longue distance (entreles sites de la grille) qu'à l'intérieur d'un même site. La latence fournie par les réseauxrapides est de l'ordre de quelques microsecondes (par exemple, 2.2µs pour Myrinet et1µs pour In�niband). De même, la latence de TCP sur Ethernet est de l'ordre de 50 µs,voire similaire à celle des réseaux rapides si l'on utilise une carte spéci�que qui fournitdu RDMA. A contrario, la latence sur le réseau longue distance dépend essentiellement


de la distance physique entre les sites. Elle peut varier de quelques millisecondes à plusde cent millisecondes si on considère des liens intercontinentaux.

4. Goulot d'étranglement du WAN : Le débit du lien d'accès au WAN est inférieur àla somme des débits des n÷uds qui peuvent communiquer dessus. La bande passante duréseau WAN est de l'ordre de 10 Gb/s alors qu'un cluster est constituée de centaines den÷uds qui peuvent communiquer sur ce réseau à 1 Gb/s. Il y a donc risque de congestionà l'interface LAN/WAN.

5. Partage des ressources : Les utilisateurs de la grille partagent ses di�érentes res-sources : les n÷uds, voire les di�érents c÷urs, leur mémoire et leur accès aux périphé-riques, le système de stockage, les di�érents réseaux. Il faut donc partager et arbitrerl'accès à ces ressources.

Plateforme expérimentale

Nos expériences ont été menées à l'aide de la grille de recherche Grid'5000. Dans cettegrille, les sites sont inter-connectés par un réseau longue distance avec des liens à 1 ou 10Gbit/s opérés par RENATER. Les latences entre les sites sont variées. Par exemple, la latenceTCP entre Lyon et Grenoble est de 4 µs alors que celle entre Rennes et Sophia est de 19 µs.Le nombre de processeurs par n÷uds est également variable conduisant à des puissances decalcul di�érentes. Les réseaux rapides locaux sont hétérogènes (In�niband, Myrinet, Ethernet1 ou 10 Gbit/s) et certaines machines possèdent plusieurs interfaces. Les utilisateurs doiventréserver les n÷uds avant de pouvoir les utiliser. Grid'5000 fournit aux chercheurs la possibilitéde con�gurer aisément l'environnement sur lequel s'exécutent leurs expériences grâce à unsystème de déploiement d'image disque. Celle-ci contient leur système d'exploitation, leurslogiciels et leur con�guration qu'ils copieront sur tous les n÷uds au début de leur expérience.De cette manière, ils peuvent exécuter leurs applications avec un environnement identique surtous les n÷uds et obtenir les droits d'administration a�n de les con�gurer à leur guise.

Les Nas Parallel Benchmark

Les applications utilisées dans nos expérimentations sont les NAS Parallel Benchmark[FY02](NPB) ; C'est un ensemble de 8 programmes (BT, CG, EP, FT, IS, LU, MG et SP)développées par la NASA qui donnent un aperçu représentatif des applications parallèles quipeuvent s'exécuter sur un cluster ou sur une grille : BT (Block Tridiagonal), CG (ConjugateGradient), EP(Embarrassingly Parallel), FT (Fast Fourier Transform), IS (Integer sort), LU(Lower-Upper symmetric Gauss-Seidel), MG (MultiGrid), SP (Scalar Pentadiagonal).

Les données fournies en entrée des NPB correspondent à des problèmes de di�érentes taillesclassés en six classes (S, W, A, B, C, D). Pour nos expérimentations, nous avons utilisé la classeB sur 16 n÷uds. Chaque programme a un schéma de communication particulier dépendantde la classe et du nombre n÷uds mais pas du réseau d'exécution. Les études ont montré lasimilarité des applications BT, LU, MG et SP selon la classe et le nombre de n÷uds. Ainsi,BT et MG sont similaires selon la taille des classes mais SP et BT varient dans la quantité dedonnées quelles envoient.

1.4 Éclatement des connexions TCP : Architecture MPI5000

En analysant les interactions entre les applications parallèles et la couche de transport dansle réseau longue distance des grilles de calcul, Hablot[Hab09] a mis en évidence la di�érence


des caractéristiques entre les réseaux locaux et les réseaux longue distance. Ce qui lui a permisde proposer une approche d'éclatement des connexions TCP consistant à di�érentier les deuxtypes de réseaux, de manière à optimiser spéci�quement les communications sur la connexionlongue distance.

1.4.1 Principe

WAN

N1.2

N1.1

N2.1

N2.2

P1.1.1

G1 G2

P1.1.0

P2.2.0

P2.1.0

P1.2.0

Figure 1.4 � Eclatement des connexions TCP à l'aide de passerelles [Hab09].

L'éclatement des connexions nécessite l'introduction de passerelles à l'interface entre cha-cune des connexions. La �gure 1.4 ( [Hab09]) illustre le découpage des connexions TCP parl'utilisation de passerelles. Les lignes rouges pointillées sur la �gure représentent les connexionsdans le cas sans utilisation de passerelles alors que les traits continus verts représententles connexions avec passerelles. Chaque connexion LAN-WAN-LAN est remplacée par troisconnexions LAN-LAN, WAN-WAN, LAN-LAN. De plus, on remplace plusieurs connexionsWAN par une seule. Ns,n est le n÷ud n du site s. Ps,n,p est le processus p exécuté sur le n÷udn du site s. Gs est la passerelle et Sws le commutateur du site s. Chaque processus est connectéà la passerelle de son site et les passerelles sont connectées entre elles. Par exemple, au lieude réaliser une connexion entre les processus P1,1,0 et P2,1,1, l'éclatement crée une connexionentre P1,1,0 et G1, G1 et G2, G2 et P2,1,1. Cet architecture est appelée par Ludovic Hablot,l'architecture MPI5000. Dans le suite de ce document, les termes "Éclatement de connexionsTCP" et "MPI5000" seront utilisés indi�éremment.

1.4.2 Hypothèses et contribution

L'utilisation de l'éclatement des connexions TCP permettra aux applications de diminuerleurs temps d'exécution en agissant à plusieurs niveaux :

1. Diminution du nombre de connexions et donc de la quantité de mémoireutilisée : grâce à l'agrégation des connexions sur le WAN, le nombre de connexionslongues distances devient fonction du nombre de sites.

2. Diminution des pertes longues distances : comme les passerelles émettent au débitdu lien longue distance, la congestion potentielle sur ce lien sera uniquement liée au tra�cconcurrent.

3. Fenêtre de congestion plus proche de la capacité réelle du lien longue dis-tance : les passerelles agrègent tout le tra�c MPI sur le lien longue distance. Le tra�crésultant sera plus proche des �ux habituellement gérés par TCP. Ainsi la fenêtre decongestion longue distance sera mise à jour plus souvent et sera de ce fait plus prochede la bande passante réellement disponible sur le lien.


4. Détection de pertes plus rapide : grâce aux passerelles, situées sur le même siteque les n÷uds, les paquets ACK sont générés plus rapidement et le temps de détectiond'une perte est donc diminué.

Un inconvénient à souligner de cette approche est la masse de traitement pour la trans-mission de chaque message. En e�et, l'utilisation des passerelles implique plusieurs recopiessupplémentaires de données qui augmentent la latence logicielle des transferts entre deux pro-cessus.

1.4.3 Performances de MPI5000

A�n de valider cette approche, Ludovic Hablot a e�ectué des expériences sur la grille decalcul Française Grid5000. Les applications utilisées ici sont les NPB. Ces expériences ont étémenées à l'aide d'un même environnement d'expérimentation, composé de deux sites séparéspar le réseau longue distance. La �gure 1.5 ([Hab09]) représente un schéma générique de cetenvironnement paramétré par n, qui constitue le nombre de n÷uds. Nous utilisons le mêmenombre de n÷uds (8) sur les deux sites s1 et s2. Ni,j est le n÷ud j du site i. La puissancedes n÷uds est di�érente d'un site à l'autre et peut grandement faire varier les performancesselon que l'on se trouve sur des machines avec 2 ou 8 c÷urs par exemple mais les comparaisonssont e�ectuées de manière unitaire c.-à-d. avec les même machines. bdp représente la capacitédu lien longue distance à 1 ou 10 Gbit/s. Le RTT varie selon les sites choisis (9,9 µs entreLyon et Bordeaux). Les n÷uds sont reliés par des cartes Ethernet à 1 Gbit/s. Les n÷udspasserelles sont représentées par Gs sur la �gure (G pour �gateway�). Nous exécutons toujoursun seul processus par n÷ud. Ce modèle de type �dumpbell� est le modèle classique d'étudedes problématiques TCP. Nous utiliserons ce même banc d'essai pour toutes nos expériences.

1 Gbit/s

1 Gbit/s

1 Gbit/s

1 Gbit/s1 Gbit/s

Grappe du siteGrappe du site

1 Gbit/s

WAN

N2.1

N2.2

N2.3

N2.n

G2

S2

N1.1

N1.2

N1.3

N1.n

G1

S1

RTTbdp

Figure 1.5 � Banc d'essai générique utilisé dans nos expériences [Hab09].

La �gure 1.6 ([Hab09]) présente les résultats obtenus. D'une manière générale, on constateque les applications BT, CG et SP voient leurs temps d'exécution diminués, tandis que pourles applications FT, IS, LU et MG le temps d'exécution est plutôt augmenté. Ceci est dûau goulot d'étranglement constitué par les passerelles. Une analyse plus approfondie de cesrésultats a abouti aux conclusions suivantes :

1. Surcoût introduit par les passerelles� Recopies : Chaque passerelle introduit deux surcoûts : un surcoût physique et unsurcoût logiciel. Le surcoût physique est dû au chemin supplémentaire pour envoyerles données vers la passerelle. Il correspond au temps d'un aller-retour entre la pas-serelle et le commutateur commun à la passerelle et au n÷ud (environ 80µs sur la


0

0.5

1

1.5

2

2.5

3

BT CG FT IS LU MG SP

Tem

ps

d’e

xecu

tio

n r

elat

if

MPICH2MPICH2 avec MPI5000

Figure 1.6 � Temps d'exécution des NPB avec MPI5000 normalisés par MPICH2 [Hab09].

No

ya

uu

tilis

ate

ur

Esp

ace

Drive

r

reception carteFile de

receptionTampon

utilisateurTampon

Tamponemission

d’emission carteFile

PasserelleNoeud localdistante

Figure 1.7 � Recopies dans chaque passerelle [Hab09].

plateforme utilisée). Comme le montre la �gure 1.7 ( [Hab09]), le surcoût logiciel estdû à l'introduction de recopies supplémentaires sur les passerelles : recopie de la cartevers le tampon de réception de TCP, puis de ce tampon vers l'espace utilisateur (ousont exécutées les passerelles). Les mêmes recopies ont lieu dans le sens inverse (del'espace utilisateur vers la carte) environ 20µs.

� Débit : Le débit chute de 7 % et ce surcoût augmente quand la taille des messagescroit. (Pertes importantes pour les gros messages : QoS) : ceci est due aux limitationsmatérielles induites par l'utilisation d'une seule carte 1 Gbit/s

2. Evaluation des paramètres de TCP� Contrôle d'erreurs et retransmissions : MPI5000 diminue les performancesdes applications qui communiquent avec de gros messages de façon synchrone. Ce


qui est dû au problème matériel qui limite la bande passante et favorise donc lesretransmissions au niveau des applications à gros messages. La passerelle devient doncici un goulot d'étranglement. Pour certaines applications MPI5000 n'améliore pas letemps de détection des pertes (se comporte mal face aux tra�cs concurrents). ExempleLU et MG. En e�et, comme leurs communications sont synchrones et que la congestionqu'elles créent n'est pas assez importante, la réduction du nombre de DuPacks et RTOsest inférieur au surcout engendré par les recopies. (Synchrone et petits messages)

� Contrôle de congestion et démarrage lent :MPI5000 supprime une bonne partiedes redémarrages lents, et donne un temps d'exécution comparable (parfois meilleur)à celui obtenu avec les applications tirant pro�t de la désactivation du démarrage lent.

� Exécution du problème à grande échelle : Avec 64 n÷uds répartis sur deuxsites, aucun résultat sur les applications ne montre d'amélioration avec MPI5000. Ceciest dû à la bande passante limitée au niveau de la passerelle et le surcoût élevé desrecopies.

1.5 Organisation du document

Vu le surcoût de l'utilisation des passerelles et les inconvénients qu'elles apportent auxapplications communiquant de façon synchrone, il importe de savoir comment et dans quellemesure on peut diminuer les inconvénients de MPI5000. A ce sujet, beaucoup d'approchessont envisageables, mais pour résoudre ce problème général, nous avons examiné 5 questionsprécises qui sont détaillées dans le chapitre 2. En d'autres termes, l'objectif de ce stage estd'étudier les problèmes posés par l'utilisation des passerelles pour les applications utilisantbeaucoup d'opérations collectives et de gros messages et d'essayer d'apporter des améliorationsen mettant en ÷uvre les approches décrites par les questions du chapitre 2. La suite de cedocument est organisée comme suit :

Le chapitre 2, présente les di�érentes questions liées à la problématique d'utilisation del'architecture MPI5000. Nous allons ici détailler de quoi il s'agit dans chacune des questionset expliquer pourquoi nous pensons que ces questions sont justi�ées dans ce contexte précisde MPI5000. Dans le chapitre 3, nous évoquerons l'état de l'art pour chacune des questionssoulevées en soulignant les travaux d'autres auteurs liés à la question traitée, et en identi�antsi la solution à la question existe ou pas ou à moitié. Nous allons ensuite lister avec un peu dedétails les di�érentes propositions apportées pour chacune des questions. Et dans les chapitres 4et 5, nous allons aborder la conception, et la mise en ÷uvre des di�érentes approches proposées,le chapitre 6 conclura nos travaux et présentera quelques perspectives d'amélioration.

Chapitre 2

Problématique

2.1 Amélioration des passerelles . . . . . . . . . . . . . . . . . . . . . . 12

2.1.1 Diminution du nombre de recopies . . . . . . . . . . . . . . . . . . . 12

2.1.2 Ordonnancement e�cace des messages . . . . . . . . . . . . . . . . . 13

2.2 Architecture d'exécution de l'application et TCP . . . . . . . . . 13

2.2.1 Placement e�cace des tâches . . . . . . . . . . . . . . . . . . . . . . 14

2.2.2 Plusieurs connexions TCP sur le WAN . . . . . . . . . . . . . . . . 14

2.2.3 Choix d'utilisation ou pas des passerelles . . . . . . . . . . . . . . . 15

11

CHAPITRE 2. PROBLÉMATIQUE 12

L'éclatement des connexions TCP tel que décrit par Hablot[Hab09], propose une meilleureinteraction entre les applications MPI et TCP permettant de diminuer le temps d'exécutiond'une bonne majorité des applications MPI. Néanmoins les applications communiquant demanière synchrone se comportent moins bien que les applications point à point. Plusieursquestions se posent donc quant à l'approche à utiliser pour diminuer cet impact négatif sur lescommunications collectives. Certaines ont attiré notre attention et seront donc étudiées. Pourcela, nous les avons divisé en deux groupes : Améliorations à apporter aux passerelles et lesquestions concernant l' architecture d'exécution de l'application et TCP.

2.1 Amélioration des passerelles

Nous avons observé dans le chapitre 1 que l'utilisation des passerelles dans l'architectured'exécution des applications introduit des surcoûts qui masquent les avantages de MPI5000.Dans cette partie, nous nous posons donc la question à savoir quelles améliorations peuventêtre apportées au fonctionnement des passerelles a�n de diminuer leurs impacts.

2.1.1 Diminution du nombre de recopies

Comme nous l'avons vu précédemment, l'introduction des passerelles ajoute des surcoûtsphysiques et logiciels qui contribuent à l'augmentation de la latence. Dans [Hab09] , pourévaluer l'impact de MPI5000 sur les communications MPI, l'auteur a exécuté un pingpong(application simple d'envoi et de réception de messages) a�n de mesurer le temps aller-retourd'un message entre deux n÷uds. Cette expérience a été réalisée entre deux n÷uds reliés parun réseau longue distance avec 18µs de latence. Les résultats comparent l'exécution de cepingpong sans et avec MPI5000. Le tableau 2.1 montre que la latence est augmentée de 141µs pour des messages de 1 o. Comme il a été expliqué dans le chapitre 1 ce surcoût correspondau temps d'un aller-retour entre le commutateur et la passerelle, ajouté aux temps de recopiesde la carte vers le tampon de réception et de ce tampon vers le tampon utilisateur, et la mêmechose en sens inverse. Il est aussi à noter ici qu'avec MPI5000, le débit chute de 7% passantde 840Mbit/s à 785Mbits/s.

MPICH2 sans MPICH2 avec CoûtMPI5000 MPI5000

Latence (µs) 9114 9255 141 µs (1.5%)Débit (Mbps) 840 785 -7%

Table 2.1 � Latence et débit MPI sans et avec MPI5000 sur la grille[01].

Puisque le premier problème est un problème physique et que nous n'avons pas la mainsur les infrastructures de la grille, nous allons donc nous attarder au problème des recopies.On se pose donc la question suivante :�

��

Q1 � La diminution du nombre de recopies permettrait-elle d'accélérer laretransmission d'un message et favoriser ainsi un avancement plus rapidede l'application ?En d'autres terme est-ce que le fait d'éviter la recopie supplémentaire de données de l'in-

terface réseau au tampon de l'espace utilisateur, et la même chose en sens inverse, diminueraitle temps de retransmission des paquets par conséquent une complétion plus rapide de l'appli-cation ?


2.1.2 Ordonnancement e�cace des messages

L'analyse des performances de MPI5000 faite au chapitre 1 nous a permis de remarquer queles applications utilisant beaucoup de communications synchrones subissent plus sévèrementles surcoûts des passerelles. Dans le standard MPI, les communications synchrones se font àl'aide d'opérations collectives comme MPI_BCAST, MPI_ALLTOALL, ect. . . Pour la bonnemarche de ces opérations, le standard envoi des messages de synchronisation et de signalisationaux di�érents processus impliqués dans l'opération. Une autre particularité des opérationscollectives est qu'elles sont pour la plus part bloquantes, les processus restent donc ainsibloqués, en attente d'un signal a�n de continuer leurs exécutions. Il est donc sensé de penserque, le retardement de l'envoi de certains messages peut avoir un impact plus négatif qued'autres à l'instar des messages de contrôle des communications collectives par exemple. Endehors des caractéristiques des communications, il a été évoqué au chapitre 1, les limitesphysiques au niveau des interfaces des passerelles, et pour les applications qui communiquentbeaucoup ainsi que pour une exécution à grande échelle, les �les d'attente au niveau despasserelles commencent rapidement à gon�er.

Ceci peut être observé par les �gures 2.1, 2.2 et 2.3. Sur ces �gures, nous avons exécutéles NPB sur l'architecture MPI5000 avec le même banc d'essai de la �gure 1.5, et nous avonsmonitoré l'évolution de la �le d'attente au niveaux d'une passerelle. En e�et, pour la retrans-mission des messages, la passerelle écoute sur son interface les messages venant des n÷udslocaux. Cette écoute est faite à l'aide de l'appel système select() sur tous les descripteurs dessockets correspondant aux connexions avec les n÷uds locaux. Les messages portés par les so-ckets renvoyés par le select() constituent donc la �le d'attente. Ainsi, pour une exécution avec8 n÷uds par site, la taille (nombre de sockets contenant des données en attente de lecture)maximale d'une �le est de 8 messages, dans ce cas, tous les n÷uds du site communiquent etcréent donc une surcharge sur la passerelle. Sur ces �gures, nous notons donc tous les appelsde select() en abscisse et le nombre de messages en attente correspondant en ordonnée. Nousconstatons sur ces �gures que les applications FT et IS ( 2.1) ont plus de messages en transitsur les passerelles lors de leurs exécutions, tandis que les applications CG et LU ( 2.3) ontun nombre faible de messages en attente avec pour maximum 3. Nous avons également lesapplications BT, MG et SP dont les �les ont un nombre moyen de messages ( 2.2).

La question que nous nous posons donc ici est la suivante :��

�

Q2 � Un ordonnancement e�cace suivant le type de communication ou lataille du message permettrait-il de diminuer l'impact du goulot d'étran-glement sur la passerelle ?Il sera question ici de voir si la mise en ÷uvre d'un ordonnancement des messages lors de

leurs passages sur la passerelle a�n de faire passer en priorité soit les messages de contrôle,soit les messages collectifs et soit les messages de plus petites tailles pourrait permettre uneévolution plus rapide de l'application globale en diminuant les inconvénients produits parMPI5000.

2.2 Architecture d'exécution de l'application et TCP

Les problèmes évoqués dans cette section sont liés à la recherche d'une interaction e�-cace entre la couche TCP et les applications MPI avec leurs di�érentes caractéristiques. Defaçon générale, nous nous demandons ici si des modi�cations tant au niveau de l'architec-ture MPI5000 qu'au niveau de la distribution des tâches aux di�érents processus pourraientaméliorer le temps d'exécution des applications.


0

1

2

3

4

5

6

7

8

9

0 500 1000 1500 2000 2500

Nom

bre

de m

essa

ges

pres

ents

dan

s la

file

d’a

ttent

e

Numero du groupe de messages traites par la passerelle

y

(a) FT

0

1

2

3

4

5

6

7

8

9

0 100 200 300 400 500

Nom

bre

de m

essa

ges

pres

ents

dan

s la

file

d’a

ttent

e


y

(b) IS

Figure 2.1 � Files d'attente de grandes tailles sur les passerelles.

2.2.1 Placement e�cace des tâches

L'analyse des communications des applications MPI sur une grille de calcul, faite dans[Hab09] permet de constater des pertes de performances importantes en comparaison à uneexécution sur un même cluster avec autant de ressources. La di�érence entre les grilles etles clusters se situe au niveau du réseau qui inter connecte les sites de la grille. Dans uncluster nous avons des connexions LAN très rapides tandis que dans une grille les réseauxinter-connectant les di�érents sites ou clusters sont des réseaux de type WAN avec de grandeslatences. La diminution de performances a�ecte donc uniquement les communications WAN oulongues distances. Donc une application e�ectuant moins de communications longues distances,observera moins de latences et verra ainsi son temps d'exécution diminuer. Ces remarques nouspoussent alors à se poser la question suivante :�

�

�

�Q3 � Une distribution e�cace des tâches aux di�érents processeurs defaçon à rapprocher (dans un même cluster) les tâches communiquant leplus entre elles, pourrait-elle diminuer les pertes de performances duesaux communications longue distance ?Cette approche favoriserait les communications LAN (intra cluster) en diminuant les com-

munications WAN (inter cluster).

2.2.2 Plusieurs connexions TCP sur le WAN

Le mécanisme de contrôle d'erreurs de TCP sur des applications à gros messages, à cause dela limitation de la bande passante sur l'interface de la passerelle, favorise des retransmissionsqui vont diminuer la taille de la fenêtre de congestion de TCP et diminuer ainsi le débit detransmission sur le lien WAN. L'intuition que nous avons ici c'est de chercher un mécanismepermettant d'éviter la chute brutale de cette fenêtre de congestion face à une perte ou uneretransmission sur le WAN. Nous nous sommes donc posé la question de savoir si l'utilisationde plusieurs connexions TCP sur le WAN pourrait permettre en cas de perte, une diminutionlégère du débit global sur ce lien du fait que la chute de la fenêtre de congestion n'a�ectera


0

1

2

3

4

5

6

7

8

9

0 2000 4000 6000 8000 10000

Nom

bre

de m

essa

ges

pres

ents

dan

s la

file

d’a

ttent

e


y

(a) BT

0

1

2

3

4

5

6

7

8

9

0 500 1000 1500 2000

Nom

bre

de m

essa

ges

pres

ents

dan

s la

file

d’a

ttent

e


y

(b) MG

0

1

2

3

4

5

6

7

8

9

0 5000 10000 15000 20000

Nom

bre

de m

essa

ges

pres

ents

dan

s la

file

d’a

ttent

e


y

(c) SP

Figure 2.2 � Files d'attente de tailles moyennes sur les passerelles.

qu'une seule connexion ? Autrement dit :�

�

�

�Q4 � L'utilisation de plusieurs connections TCP entre les passerelles desorte à disposer de plus de bande passante donc de capacité de trans-mission, pourrait-il être utile pour les communications créant des goulotsd'étranglement comme les communications collectives ?L'avantage de cette approche est qu'elle diminuerait la latence, les pertes et les retrans-

missions sur le lien longue distance d'où on aura une augmentation de la performance globalede l'application.

2.2.3 Choix d'utilisation ou pas des passerelles

Les communications collectives à gros messages sont les plus impactées. En e�et, le goulotd'étranglement créé sur la passerelle ne permet pas un avancement rapide des applications


0

1

2

3

4

5

6

7

8

9

0 1000 2000 3000 4000 5000 6000 7000

Nom

bre

de m

essa

ges

pres

ents

dan

s la

file

d’a

ttent

e


y

(a) CG

0

1

2

3

4

5

6

7

8

9

0 5000 10000 15000 20000 25000 30000 35000 40000

Nom

bre

de m

essa

ges

pres

ents

dan

s la

file

d’a

ttent

e


y

(b) LU

Figure 2.3 � Files d'attente de petites tailles sur les passerelles.

utilisant beaucoup ce type de communication. Il serait donc sensé de choisir ne pas utiliser lespasserelles pour les communications collectives, et de ne les utiliser que pour les communica-tions point à point, ainsi on évitera la surcharge des passerelles. L'objectif est donc de pouvoirrépondre à la question suivante :�

��

Q5 � Est-ce que le fait de ne pas faire transiter les communications collec-tives des applications sur les passerelles permettrait un avancement plusrapide des applications utilisant beaucoup ce type de communication ?Cette approche pourrait garantir au moins un temps d'exécution égal au cas sans MPI5000

pour les applications aux communications collectives et de béné�cier des améliorations deMPI5000 pour les applications aux communications point à point.

Synthèse

En guise de synthèse, nous pouvons dire que ces questions sont aussi importantes les unesque les autres pour l'amélioration des performances de MPI5000. Mais par manque de temps,nous n'avons pas étudié la question de "Diminution du nombre de recopies". Il sera doncquestion tout au long de ce document de répondre aux questions suivantes :

� Un ordonnancement e�cace suivant le type de communication ou la taille du messagepermettrait-il de diminuer l'impact du goulot d'étranglement sur la passerelle ?

� Une distribution e�cace des tâches aux di�érents processeurs de façon à rapprocher (dansun même cluster) les tâches communiquant le plus entre elles, pourrait-elle diminuer lespertes de performances dues aux communications longue distance ?

� L'utilisation de plusieurs connections TCP entre les passerelles de sorte à disposer deplus de bande passante donc de capacité de transmission, pourrait-il être utile pour lescommunications créant des goulots d'étranglement comme les communications collec-tives ?

� Est-ce que le fait de ne pas faire transiter les communications collectives des applica-tions sur les passerelles permettrait un avancement plus rapide des applications utilisantbeaucoup ce type de communication ?

Chapitre 3

État de l'art

3.1 Ordonnancement e�cace des messages . . . . . . . . . . . . . . . . 183.2 Placement e�cace des tâches . . . . . . . . . . . . . . . . . . . . . . 193.3 Plusieurs connexions TCP sur le WAN . . . . . . . . . . . . . . . . 213.4 Choix d'utilisation ou pas des passerelles . . . . . . . . . . . . . . . 223.5 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.6 Propositions et Contribution . . . . . . . . . . . . . . . . . . . . . . 23

17

CHAPITRE 3. ÉTAT DE L'ART 18

De nombreuses approches ont été proposées dans la littérature pour une meilleure exploi-tation des ressources de la grille. Certaines de ces approches visent à créer des intergicielspermettant pour certains systèmes de simpli�er les communications entre les ressources d'unegrille, d'autres prennent complètement en charge la gestion des ressources et d'autres four-nissent des environnements de programmation pour la création d'applications de grilles. Enplus des travaux de Hablot[Hab09], d'autres études ont prouvé que l'utilisation de passerellespouvait améliorer sensiblement le temps de transmission entre le réseau �laire et le réseaudégradé, d'autres encore ( [VKM02] et [CC06]) montrent l'utilisation des � proxies � dansles réseaux à très forte latence tels que les réseaux satellites pour permettre de di�érencierle réseau �laire (rapide) et le réseau satellite (lent) et avec une bande passante plus faible.La RFC3135 [BKG+01] décrit le principe général des PEP (Performance Enhancing Proxies).Ces passerelles permettent d'optimiser une partie d'une connexion point à point qui utiliseplusieurs liens aux caractéristiques di�érentes.

En ce qui concerne l'état de l'art sur les approches permettant la diminution de l'impactde l'utilisation des passerelles sur la performance des applications synchrones, nous allonsprocéder question par question.

3.1 Ordonnancement e�cace des messages

L'ordonnancement est un sujet très discuté dans les grilles de calcul et les systèmes d'ex-ploitation. Dans la plupart des cas, il s'agit de l'ordonnancement e�ectué par les gestionnairesde ressources a�n de déterminer l'ordre d'exécution des tâches sur un nombre �xe de proces-seurs de façon à ce que l'exécution de l'ensemble soit le plus rapide possible sachant que l'onpeut exécuter certaines tâches en parallèle. Dans ce contexte de distribution des ressources,il existe une très large littérature considérant le problème de l'ordonnancement des tâchesd'un programme parallèle ( [PCL95] , [Hoc96] et [Dro96] ). L'éventail des travaux réalisésva des théoriques sur des modèles abstraits, aux outils pratiques comme les implantationsd'applications sur la plupart des plateformes d'exécutions parallèles ou distribuées.

Dans le cadre de ce stage, il ne s'agit pas de cela ; il s'agit ici de l'ordonnancement desmessages en transit sur les passerelles pour leurs redistributions. Ce problème de redistributionde données a été essentiellement étudiée dans le cadre de réseaux locaux sur lesquels lesdélais d'initialisations des di�érentes communications peuvent être relativement faibles et lesliens entre sources et destinations relativement directs. L'article [Fre05] étudie ce problème deredistribution de données à travers un réseau haut débit. Les auteurs de cet article utilisentune topologie semblable à celle de l'éclatement des connexions TCP avec pour di�érencesl'utilisation d'un commutateur à la place de la passerelle et l'utilisation de plusieurs �ux entreles commutateurs. (voir �gure 3.1 ( [Fre05]) )

En e�et, les auteurs étudient comment e�ectuer une telle redistribution de données le pluse�cacement possible en minimisant le temps de communication et de congestion du réseau.Leurs expériences ont prouvé qu'il est e�ectivement possible par des ordonnancements simplesd'augmenter jusqu'à 20% les performances d'une application. Ils mettent également l'accentsur les communications de courte durée en insistant que celles-ci ne doivent pas se retrouverbloquées derrière de longues transmissions. La di�érence avec notre conteste c'est qu'ici, il n'ya pas d'éclatement des connexions, il existe donc plusieurs connexions parallèles se partageantle débit de la dorsale.

Comme nous l'avons souligné dans le chapitre 2, nos critères d'ordonnancement sont baséssur le type des communications et la taille des messages. Nous avons pour cela choisi d'utiliser


Figure 3.1 � Deux clusters reliés par une dorsale lente [Fre05].

un ordonnancement par priorité a�n de donner la priorité à un type de message. D'une façonintuitive on peut imaginer que ces fonctionnalités peuvent être mises en oeuvre à deux niveauxdi�érents sur les couches du modèle OSI :

� Au niveau application : En utilisant le daemon présent au niveau des passerelles ;Ce qui nécessitera un e�ort de programmation car tous le système d'ordonnancementdoit être fait à la main par le programmeur. Et le traitement fait ici peut être lourdet constituer un goulot d'étranglement et augmenter la consommation des ressourcesmémoire des passerelles.

� Au niveau réseau : En utilisant l'implémentation Linux d'un routeur à di�érentiationde services [TBS00] au niveau des passerelles. En e�et, le noyau Linux, permet une grandevariété de fonctions de contrôle de tra�c, et des modules Di�Serv sont disponibles pourLinux. Il nous permet de mettre en place un système de �le d'attente comme modulecharge-able du noyau sans modi�er les sources du noyau. La couche d'interface réseaude linux possède un mécanisme générique d'ordonnancement appelé Qdisc, avec despolitiques d'ordonnancement "built in" comme FIFO (First In, First Out), CBQ(Class-based queueing) ou RED(Random early detection). Il est donc ainsi possible d'utiliserune machine Linux comme un routeur de bordure et y e�ectuer de la di�érentiation deservices juste avec quelques commandes de con�guration. De plus cette implémentationpermet un traitement du paquet avant que la classi�cation ne soit e�ectuée ; ceci aural'avantage de ne nécessiter aucun changement dans le code du daemon de la passerelleet interviendra seulement lorsqu'il faut envoyer le paquet sur la carte réseau. Un autreavantage est que cet ordonnancement est réalisé à un niveau plus bas qu'à la solutioncitée plus haut.

3.2 Placement e�cace des tâches

L'interrogation ici, est de savoir si il est possible par une distribution e�cace des tâchesaux processeurs, de minimiser les communications longues distances favorisant ainsi une exé-cution plus rapide de l'application. Il s'agit en fait de trouver une meilleure association hôte -tâche pour l'exécution de l'application. Plusieurs auteurs ont déjà travaillé sur des questionsanalogues de "Task Mapping" ou de "Task Scheduling" dé�nies comme une association destâches aux processeurs et une plani�cation ou ordonnancement de l'exécution de l'application.Deux grands critères sont le plus souvent utilisés pour comparer les di�érentes solutions de cesalgorithmes :

� Makespan : Dans cette formulation, on considère que chaque tâche à un temps decomplétion, la solution optimal ici est donc celle qui minimise le temps de complétion de


la dernière tâche, par conséquent minimise le temps total d'exécution de l'application. Lesarticles comme [EKBO08] et [BKM+04] utilisent le Makespan pour l'ordonnancementdes tâches malléables (tâches pouvant être exécutées sur plusieurs processeurs de façonparallèle) sur un nombre �xe de processeurs.

� Steady state : L'idée ici c'est de caractériser l'activité de chaque ressource pendantl'unité de temps a�n de savoir le temps mis pour le calcul, pour l'envoi et pour la ré-ception des messages. Ces variables sont donc utilisées pour construire un problème deprogrammation linéaire caractérisant le comportement global du système. L'objectif estdonc de maximiser le débit (calculs et communications) en état stable de chaque res-source (n÷ud), c'est à dire la charge total exécutée par unité de temps. Les auteursde [LMR05] présentent une formulation de ce problème et évoquent les avantages dece genre d'objectifs comparé aux Makespan comme la simplicité (c'est une version sim-pli�é du Makespan), l'e�cacité d'implémentation et l'adaptabilité à la disponibilité desressources.

Ce problème est reconnu comme un problème NP-Complet [FB89] et [IK77], d'où la néces-sité de construire des heuristiques permettant d'avoir une solution proche de l'optimale. Maisces heuristiques sont di�ciles à comparer les unes des autres à cause des di�érentes assomp-tions faites dans leurs études [BSB+98]. L'article [BSB+01] e�ectue une évaluation de 12 heu-ristiques (Opportunistic Load Balancing, User-Directed Assignment, Fast Greedy, Min-min,Max-min, Greedy, Genetic Algorithm, Simulated Annealing, Genetic Simulated Annealing,Tabu, and A*) de plani�cation existant dans la littérature. Il en ressort que, la meilleure heu-ristique dépend fortement du scénario choisi, mais dans la majorité, certaines des heuristiquesréagissent mieux que d'autres : Greedy(Glouton), GA, A*, Min-min. Dans le cadre du stead-state, l'article [LMR05] utilise également l'heuristique Glouton et trois autres heuristiquesbasées sur la solution des programmes linéaires LPR, LPRG et LPRR dé�nis au préalable.De même que dans [BSB+01] l'heuristique Glouton donne de meilleurs résultats. D'autres au-teurs [JWL06] proposent de couplé les méthode de recherche locale comme glouton à d'autreméthode comme celle du Branch and Bound, dans la résolution du problème d'optimisationQuadratic Assignment Problem (QAP).

Mais à la di�érence de [EKBO08] et [BKM+04] qui proposent des ordonnancements consi-dérant que les tâches sont indépendantes et ne prennent pas en compte le temps des commu-nications entre les processus, [MYH+01], [OSD01] proposent des algorithmes de Mappingdans des systèmes homogènes et hétérogènes à multiples clusters, optimisant le coût total descommunications tout en faisant du "Load balancing" entre le processeurs.

Au niveau intergiciel, ADAGE (Automatic Deployment of Applications in a Grid Envi-ronment) [LPP05] o�re des possibilités intéressantes. Adage c'est une plate-forme logicielle,développée par Globus [IFT02], dans l'objectif de faciliter le déploiement des applications.Adage propose un formalisme abstrait pour la description d'une application qui prend encompte la topologie du réseau et les applications, fondées sur le modèle de composants. Laplate-forme utilise donc comme paramètres d'entrée la description des ressources (n÷uds)disponibles pour l'exécution de l'application, ainsi que la description du schéma de commu-nication de l'application. La �gure 3.2 [LPP05] nous présente ce processus de déploiement endeux étapes :

� Plani�cation du déploiement : cette phase prend en entrée les deux �chiers citésplus haut et fournie en sortie un plan de déploiement. Pour ce faire, Adage e�ectued'abord un mapping entre les processus et les ressources et après fait la plani�cation dudéploiement de l'application.

� Exécution du plan de déploiement : c'est la phase de con�guration, de distribution


Figure 3.2 � Déploiement automatique d'une application MPI [LPP05].

et de lancement de l'application.Le projet Globus est également très utilisé dans la littérature ; il possède une panoplie

d'outils permettant d'utiliser de façon sécurisée une grille dont les ressources sont répartiesà travers plusieurs domaines d'administration. Deux outils principalement nous intéressentici : GRAM(Globus Resource Allocation Manager) et DUROC [KCK99] (Dynamically Upda-ted Request Online Co-allocator). GRAM permet de soumettre des tâches sur des ressourcesdistantes et d'en surveiller l'exécution tandis que DUROC est un service au dessus de GRAMqui permet la soumission simultanée de multiples tâches, c'est-à-dire, la co-allocation de res-sources. Il existe plusieurs autres intergiciels pour la gestion des ressources dans la grille, maisles projets Adage et Globus ont l'avantage de pouvoir être utilisés dans tous les contextes degrille mais Globus o�re moins de fonctionnalités de haut niveau. Dans [IFT02] il est dit que lanature de l'architecture de Globus en fait un système très polyvalent mais complexe à utilisercar il ne fournit que les briques de base et c'est souvent à l'utilisateur qu'est laissé le soind'adaptation pour des utilisations spéci�ques.

Conceptuellement, il est possible d'utiliser ces approches de manière complémentaire. Parexemple, mettre en ÷uvre un algorithme Makespan ou Steady-state suivant l'heuristique Glou-ton et de l'introduire dans le composant de déploiement d'ADAGE. Mais pour pouvoir résoudrele problème précis exposé ici ; qui est de rapprocher les n÷uds communiquant le plus, il estnécessaire de faire une formulation exacte du problème sous forme de programmation linéaireet d'y appliquer l'heuristique choisi.

3.3 Plusieurs connexions TCP sur le WAN

Bien que la question d'optimisation des transferts des données de grandes tailles sur unegrille de calcul est largement étudiée, peu d'auteurs se penchent sur la possibilité d'utiliserplusieurs connexions TCP pour le transfert des données. En fait plusieurs articles analysent leproblème de contrôle d'admission et de réservation de la bande passante sur le lien entre deuxn÷uds a�n de garantir une certaine qualité de service aux �ux gourmands. Dans [BBC07], lesauteurs proposent une approche de réservation de ressources à intervalles multiples, qui divisela fenêtre de congestion active en plusieurs intervalles et réserve une quantité constante de res-sources sur chacun de ces intervalles. Cette approche s'oppose à l'approche traditionnel Intservde réservation d'une quantité �xe de ressources pour un temps �xe. L'article [SCBPVB08] pré-sente une interaction entre le service de réservation de bande passante et le service de transfertde données garantissant un transfert optimal des données de grandes tailles.


L'article [TJM10] e�ectue une comparaison entre les outils de transfert de données degrandes tailles. Il explique comment le parallélisme dans le transfert est plus performant quel'utilisation d'une seule connexion. Il classe le transfert en parallèles devant les transferts detype ftp suivit de scp ou sftp. Il existe plusieurs outils utilisant des connexions FTP parallèles.Ils peuvent être des outils ou commandes comme bbcp, lftp, axel etc ou des gestionnaires detéléchargement comme aria, speed download ou des outils ftp comme �lezilla. Mais aucun deces outils n'ai compatible aux communications d'une applications dans les grilles de calculs.

Par contre le Projet Globus possède une plateforme très intéressante basé sur l'utilisationde plusieurs connexions TCP sur une grille de calcul : GridFTP [Lab03] ; c'est un protocoleexceptionnel de transport de données sur un environnement de grille de calcul. Étant uneextension du protocole FTP, il a été prouvé dans les articles [TJM10] et [STWF03] que lesserveurs de cette plateforme sont les plus rapides de tous les serveurs FTP existant et ceci parle biais de plusieurs connexions qu'ils utilisent pour le transfert d'un même �chier.

Pour un rendement optimal de GridFTP, un certain nombre de paramètres sont à prendreen compte :

� La taille du bu�er : La quantité optimale de données pouvant être envoyées avantl'attente d'un ACK, elle doit correspondre à la taille de la fenêtre de congestion TCP.[STWF03] propose ainsi une optimisation de GridFTP avec une mise à jour dynamiquede la taille de bu�er durant le transfert.

� Le parallélisme : Modère l'impact du contrôle de congestion de TCP dans les réseauxà très grande congestion et latence.

� La taille du �chier à transférer : Plus les �chiers à transférer sont petits, plusils entraînent de slow start soit par l'expiration du idle time (car il faut attendre que le�chier précédent soit totalement transmis avant de faire la requête du transfert du �chiersuivant), soit par l'ouverture d'une nouvelle connexion pour chaque �chier à transférer.Pour diminuer ces inconvénients, les chercheurs de Globus ont proposé deux méthodes :Pipeline et Channel caching.

3.4 Choix d'utilisation ou pas des passerelles

Cette question est intimement liée aux problèmes de l'éclatement des connexions TCP, quipénalisent certains types d'applications et pas d'autres. On ne saurait donc pas trouver destravaux reliés à ce genre de situation très particulière. Cette approche nous permet juste detrouver un compromis entre l'utilisation des passerelles ou non suivant le type de communica-tion de l'application. Les applications e�ectuant beaucoup d'opérations collectives vont voirleurs paquets transmis directement au destinataire, sans passer par la passerelle et ainsi ellespourront avoir des performances semblables à celles obtenues avec l'exécution de l'applicationsans passerelles.

3.5 Synthèse

Nous avons présenté dans ce chapitre une étude sur les di�érents travaux reliés à notreobjectif d'amélioration des performances de l'architecture MPI5000.

Ensuite, nous avons fait un aperçu des di�érentes approches de distribution intelligentedes tâches aux processus, ainsi que la plani�cation, le déploiement et l'exécution des applica-tions sur une grille de calcul. Finalement, nous avons fait une étude des di�érents outils ouplateformes de transfert de données de grandes tailles.


De cette étude, nous pouvons tirer di�érentes leçons :� En ce qui concerne l'ordonnancement, des deux types (tâches et paquets), celle quinous intéresse c'est l'ordonnancement des paquets. Et à ce niveau la redistribution faitepar l'article [Fre05] propose des algorithmes d'ordonnancement se basant sur la tailledes paquets. Ce pendant, ces algorithmes considèrent plusieurs �ux parallèles entre lespasserelles. De plus dans notre contexte, nous avons besoin d'un ordonnancement prenantégalement en compte le type de communication MPI du paquet à retransmettre. Ce quin'a pas encore été fait dans la littérature.

� Pour le placement des tâches, beaucoup d'algorithmes de placement ou de mappage detâches et plani�cation reposent soit sur la minimisation du Makespan, soit la maximisa-tion du débit des ressources en Steady-state. Bien que Makespan soit le critère le plusutilisé [BKM+04], [BSB+98], Steady-state [LMR05] présente les avantages d'être plussimple, plus e�cace et plus adaptable aux variations de disponibilités des ressources. Detoutes les heuristiques utilisées pour la résolution de ce problème NP-Complet, l'heu-ristique Glouton (Greedy) est celle qui fournit de façon générale de meilleurs résultatssurtout dans les environnements hétérogènes comme les grilles de calcul. L'outil de dé-ploiement automatique ADAGE [LPP05] est une bonne plateforme pour la mise en ÷uvreet l'introduction des heuristiques dans le processus de déploiement automatique.

� Pour le transfert de données, l'utilisation des connexions TCP parallèles o�re de meilleuresperformances. C'est ainsi que les outils comme GridFTP[Lab03], bbcp, lftp, axel sontbeaucoup plus rapides que des outils comme ftp, scp, ssh. GridFTP est le seul outil validepour le transfert des données en parallèles dans les grilles de calcul. De plus l'équipe deGlobus travaillant sur GridFTP e�ectue régulièrement des optimisations [STWF03] et[BKL+07] rendant GridFTP de plus en plus performant.

Pour conclure, les intergiciels actuels ne concilient pas complètement tous les aspects sou-lignés sur les questions soulevées. Toutefois, ADAGE et GridFTP à quelques modi�cationsprès semblent répondre à certaines de nos questions. Cette étude bibliographique nous permetdonc de nous rendre compte de la pertinence de nos questions et de présenter des propositionsde mise en ÷uvre et d'évaluation. Nous verrons dans les chapitres suivants comment nousutilisons ces notions pour la mise en ÷uvre de nos di�érentes approches.

3.6 Propositions et Contribution

L'étude bibliographique faite ci-dessus, montre que nous ne sommes pas les seuls à s'in-terroger sur les problèmes d'optimisation des communications dans les grilles de calcul. Maisdans le contexte particulier de l'éclatement des connexions TCP, nous avons e�ectué quatreprincipales propositions à travers l'étude de nos questions :

Ordonnancement e�cace des messages

La mise en ÷uvre d'un système de �les d'attente sur la passerelle nous a permis de con�r-mer la forte congestion que subissent les paquets avant leurs retransmissions vers le WAN.Nous avons ici e�ectué la proposition et la validation de trois politiques d'ordonnancementpermettant pour la première de donner la priorité aux messages de contrôle qui peuvent êtreconsidérés ici comme � Urgents �, pour le déblocage des n÷uds en attente d'un signal de syn-chronisation. Avec la deuxième politique nous avons donné la priorité aux messages collectifsmais cette politique s'avère moins performante que la première car ces applications utilisenten très grandes majorité des opérations collectives. La troisième politique consiste à donner


la priorité aux messages de petites tailles. Pour la mise en ÷uvre de ces politiques, il nousa fallut d'abord identi�er les di�érents types de communications dans les applications MPI,nous avons ensuite inclus ces informations d'identi�cation dans l'entête des paquets et crée unsystème de �le d'attente sur les passerelles avec deux �les.

Placement e�cace des tâches

Nous avons formulé le problème d'attribution de ressources aux tâches avec pour objectifde diminuer les communications longue distance très coûteuses, et proposé une résolution duproblème en combinant l'heuristique Glouton à la méthode de recherche Branch And Bound.Cette formulation met en exergue deux facteurs importants qui sont la diminution de la latencedes communications par rapprochement des n÷uds qui communiquent le plus, et la diminutionde manière globale du temps d'exécution de l'application.

Plusieurs connexions TCP sur le WAN

Nous avons étudié la faisabilité de l'utilisation de plusieurs connexions TCP entre lespasserelles dans le contexte de l'éclatement des connexions TCP, et proposé un protocole àla GridFTP rendant possible un transfert plus rapide de données entre les passerelles. Nousavons démontré que l'e�cacité d'une telle architecture dépend fortement de deux facteurs : Lenombre de connexions, ce nombre de connexions doit être su�samment petit pour agrégerles connexions TCP, et su�samment grand pour permettre une bonne exploitation de la bandepassante disponible sur le lien longue distance. La taille du bu�er TCP, pour l'e�cacitéface aux mécanismes de contrôle de congestion et de retransmission de TCP, la taille du bu�erdoit être proportionnelle à la taille de la fenêtre de congestion sur la connexion TCP.

Choix d'utilisation ou pas des passerelles

Étant donnée que les faibles performances de l'éclatement des connexions pour certainesapplications sont dues à la grande abondance des opérations collectives, nous proposons iciune architecture permettant de décider suivant le type de communication, de l'utilisation oupas de passerelles. La création d'une connexion directe supplémentaire pour chaque couple den÷uds nous permet à chaque instant d'avoir deux possibilités d'envoi de message du n÷udsource vers le n÷ud destinataire.

Chapitre 4

Ordonnancement

4.1 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.1.1 Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.1.2 Modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.1.3 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.2 Mise en ÷uvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.2.1 Correspondance Paquet-Type de message . . . . . . . . . . . . . . . 31

4.2.2 Etiquetage des paquets . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.3 Validation expérimentale . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.3.1 Analyse des communications des NPB . . . . . . . . . . . . . . . . . 34

4.3.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.3.3 Gain sur les communications . . . . . . . . . . . . . . . . . . . . . . 38

25

CHAPITRE 4. ORDONNANCEMENT 26

4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Nous allons aborder ici la conception, la mise en ÷uvre et l'évaluation de la propositiond'ordonnancement e�cace des messages MPI.

Introduction

L'ordonnancement le plus souvent rencontré dans les systèmes d'exploitation, permet dedé�nir des enchainements entre les traitements, qu'il s'agisse de l'ordonnancement des tâches oudes entrées/sorties, les ordonnanceurs doivent permettre une plani�cation optimale et équitablepour toutes les applications. Dans notre contexte d'éclatement des connexions TCP, il s'agitpour l'ordonnanceur (la passerelle) de choisir un ordre pour la retransmission des paquetsvenant des n÷uds d'un site vers le lien longue distance de sorte à accélérer l'exécution d'uneapplication MPI. Il sera ensuite question de faire une évaluation des performances a�n desavoir si e�ectivement le système ainsi crée permet d'observer des améliorations dans le tempsd'exécution des applications.

4.1 Proposition

Les applications distribuées fonctionnent en deux modes : le mode de traitement et lemode de communication. Le temps d'exécution d'une application est donc une combinaisonde son temps de traitement et son temps de communication. Le temps de traitement estdiminué en parallélisant les traitements sur plusieurs machines et le temps de communicationest donc fonction du nombre de communications, et de la latence pour chaque communication.L'objectif général de ce stage étant de réduire le temps nécessaire pour chaque communication,l'ordonnancement rendrait cela possible en transférant d'abord les messages urgents a�n dedébloquer rapidement les n÷uds en attentes et ensuite les messages considérés comme moinsurgents et qui prennent trop de temps pour leurs transmissions. Pour faire une homologie avecun ordonnanceur de tâches, on peut considérer la taille du message comme la taille de la tâcheet les types du message comme des priorités de tâches di�érentes. Avant de parler du modèlegénérale utilisé pour la mise en ÷uvre de cette proposition, nous allons d'abord nous attardersur les critères ou politiques d'ordonnancement, qui constituent notre principale contribution.

4.1.1 Principes

Nous allons dans cette partie, lister toutes les politiques d'ordonnancement proposées etjusti�er en quoi elles pourraient améliorer le temps d'exécution de l'application. La questionposée ici est de savoir si en modi�ant de façon intelligente l'ordre d'envoi des paquets, nouspouvons observer de meilleures performances pour les applications communiquant de manièresynchrone. Mais avant de parler des politiques proprement dites, il importe de faire le pointsur les types et modes de communications MPI.

Les implémentations MPI, utilisent deux modes de transferts de données : le mode Eageret le mode Rendez-vous (pour le transfert des données de petites et de grandes tailles res-pectivement). Dans le mode eager, les données sont associées à la requête d'envoi et le tout esttransmis directement au récepteur. A contrario, dans le mode rendez-vous, l'émetteur envoied'abord une requête d'envoi (Request_To_Send) sans donnée indiquant qu'il a des donnéesà transmettre. Lorsque le récepteur reçoit l'appel à la fonction qui va réceptionner les don-


P0

BP1

CP2

P0

P1

P2

A DCB

A DCB

A DCB

A DCBP3

A

DP3

All Gather

P0

B0 B3B2B1P1

C0 C3C2C1P2

P0

P1

P2

A0 D0C0B0

A1 D1C1B1

A2 D2C2B2

A3 D3C3B3P3

A0 A3A2A1

D0 D3D2D1P3

All to All

Figure 4.1 � Exemple d'opérations collectives.

nées, il envoie un message d'acceptation à l'émetteur (Clear_To_Send) et à la réception dece message, l'émetteur peut alors transmettre les données.

Avec MPI, les communications entre processus se font suivant deux modes : le mode pointà point ou asynchrone (communication unicast entre deux processus), et le mode collec-tif ou synchrone(communication multicast, besoin de synchronisation). Les communicationscollectives en MPI, se réalisent dans un groupe de processus. Il existe 3 classes d'opérationscollectives :

� Les opérations de synchronisation : Un exemple ici c'est MPI_BARRIER qui bloquele processus en attente que tous les processus du groupe font le même appel.

� Les opérations de mouvement de données : Elles servent à l'envoi et à la réceptiondes données. comme exemple, nous pouvons citer MPI_BCAST, MPI_ALLGATHER,MPI_ALLTOALL.

� Les opérations de calculs collectifs : Opérations de calcul et de réduction globaux,tels que la somme, max, min, ou des fonctions dé�nies par l'utilisateur, où le résultatest retourné à tous les membres d'un groupe et une variante où le résultat est renvoyé à unseul membre. Exemple : MPI_ALLREDUCE, MPI_REDUCE, MPI_REDUCE_SCATTER.

Toutes les opérations collectives sont bloquantes, d'où les opérations de mouvement ou decalcul utilisent les opérations de synchronisation ( MPI_BARRIER). La �gure 4.1 montre ledéroulement des opérations MPI_ALLGATHER et MPI_ALLTOALL. Pour le MPI_ALLGATHERtous les processus possèdent une donnée à transmettre dans le groupe de processus, ils e�ec-tuent chacun un broadcast et à la �n ils ont tous une donnée venant de chaque membredu groupe. Le MPI_ALLTOALL est une extention de MPI_ALLGATHER où les processusenvoient des données di�érentes à chaque processus du groupe.


L'étude de ces di�érents modes de transfert de données et types de communications, nous apermis de distinguer 4 types de messages di�érents, que l'on peut regrouper en deux niveaux :

1. Les messages de contrôle : Un message de contrôle est un message qui sert à lasynchronisation ou à la signalisation entre les processus pour la bonne exécution del'application ; C'est un message ne contenant pas de données utiles au point de vue del'application. Dans cette classe, nous avons donc :

� Les messages de contrôle collectif : Ce sont les messages de contrôle commedé�nis ci-dessus, qui font référence aux communications collectives. Dans MPI, cecicorrespond à une requête de rendez-vous pour l'envoi d'une donnée par une opéra-tion collective (Request_To_Send, Clear_To_Send) ou une opération collective desynchronisation du type MPI_BARRIER.

� Les messages de contrôle point à point : Ce sont les messages de contrôle commedé�nis ci-dessus qui font référence aux communications point à point. Pour faire simple,nous avons considéré que c'est tout message de contrôle ne faisant pas référence à unecommunication collective. Les détails sur ce type de paquets sont données à la partie??.

2. Les messages de données : Un message de données est un message contenant desdonnées utiles au point de vue de l'application. Nous avons donc dans cette catégorie :

� Les messages de données collectifs : Ce sont les messages de données qui fontréférence aux communications collectives. Ça peut être une opération de mouvementde données ou de calcul : MPI_BCAST, MPI_ALLGATHER, MPI_ALLTOALL,MPI_ALLREDUCE, MPI_REDUCE_SCATTER ect...

� Les messages de données point à point : Ce sont les messages de données quifont référence aux communications point à point. Pour faire simple, nous avons consi-déré que c'est tout message de données ne faisant pas référence à une communicationcollective. Comme exemple nous avons : MPI_SEND, MPI_RECV ,MPI_ISEND,MPI_IRECV, etc ...

Ainsi, pour améliorer le temps de communication des applications MPI utilisant l'archi-tecture MPI5000, nous avons pensé à trois principales politiques d'ordonnancement :

� Messages collectifs vs Messages point à point : Dans le chapitre 1, nous avonsvu que ce sont les applications collectives qui sont le plus impactées par l'utilisation despasserelles. Cette politique permettra donc de donner la priorité aux messages collectifspar rapport aux messages point à point. Ainsi, les applications utilisant plus de messagescollectifs verront leurs messages retransmis plus rapidement d'où on pourrait avoir desaméliorations dans le temps d'exécution global de l'application.

� Messages contrôle vs Message de données : Étant données que toutes les opé-rations collectives sollicitent des opérations de contrôles (synchronisation), et puisqueces opérations bloquent l'exécution des tâches, ils devient donc urgent de retransmettreces messages en premier. Nous allons donc dans cette optique, donner la priorité auxmessages de contrôle. Ainsi, ces messages de contrôle pourront arriver à leurs destina-tions plus rapidement et libérer ainsi les processus récepteurs dans le cas où ceux-ciétaient bloqués en attente (ce qui est fréquent dans les communications synchrones).Cela devrait normalement favoriser un avancement plus rapide de l'application et parconséquent, une diminution du temps d'exécution.

� Petits messages vs grands messages : On donnera la priorité aux petits messages.L'objectif ici est d'éviter les cas où les petits messages sont bloqués derrière les grandsmessages. Un message de grande taille mettra plus de temps à être transmis et causera


A

B

C

1

2

3

1 2 3

(a)

A

B

C

1

2

3

1 2 3

(b)

Temps Temps

Figure 4.2 � Ordonnancement suivant la taille des messages.

donc une attente globale plus grande. Voici un scénario simple montrant l'importancede cette politique.Exemple : On cherche ici à e�ectuer une retransmission très simple : Nous avons troispaquets A, B et C de taille respective 30 ko, 10 ko et 20 ko. Sur un lien où on metrespectivement pour la retransmission de chacun des paquets : 1.5, 0.5et1.0 secondes. Lapartie (a) de la �gure 4.2 montre le cas où les paquets sont retransmis suivant l'ordredes arrivées et la partie (b) de la �gure 4.2 montre la retransmission suivant l'ordre degrandeur des paquets. Nous constatons que le temps pour que tous les messages soittransmis est le même (3 secondes), mais lorsque l'on regarde la somme des attentes dechaque paquet, on voit que dans le premier cas, il y a 1.5 + 2 = 3.5 secondes d'attente,mais dans l'autre cas on a 0.5 + 1.5 = 2 secondes d'attente donc 1.5 secondes de moins.On peut en conclure que cette attente individuelle est importante et peut impacter letemps de complétion globale de l'application.

La mise en ÷uvre de ces politiques est simple, nous envoyons les paquets sur le réseau endonnant la priorité aux messages dans la �le la plus prioritaire. Pour cela nous avons modi�él'algorithme des passerelles tel que écrit par Ludovic Hablot en y ajoutant cet ordonnancement.

4.1.2 Modèle

Pour pouvoir réaliser cette proposition, il importe de distinguer deux phases distinctes :� La première c'est l'identi�cation du type de communication des paquets : elle s'e�ectueau niveau du n÷ud source. Il est donc question ici de pouvoir à tout moment savoir àquel type de communication est associé à un paquet. D'où avant l'envoi du paquet (dansl'appel system write () de TCP), nous allons modi�er l'entête MPI5000 et y ajouter unidenti�ant du type de communication : msgtype.

� En suite l'ordonnancement : il est réalisé par la passerelle reliée au site source du paquet.Nous avons ici mis en place un système de �le d'attente avec deux �les : la premièrepour les paquets prioritaires et l'autre pour les paquets dont l'envoi n'est pas � urgent� donc peut attendre un peu.

Ces traitements sont seulement e�ectués à l'envoi du message donc sur le site source car lapasserelle de destination recevra les paquets dans l'ordre de leurs émissions par la passerellesource. La �gure 4.3 résume bien cette architecture.

4.1.3 Algorithme

L'algorithme général des passerelles est constitué de deux parties, une partie de créa-tion et d'initialisation des connexions, et une partie de retransmission. Notre ordonnancement


concerne uniquement la partie de retransmission des paquets venant du LAN vers le WAN,nous allons donc ainsi présenter seulement la portion de l'algorithme de la passerelle, consacréeà l'ordonnancement.Algorithm 1: Fonction d'ordonnancement des paquets

/* Boucle select pour recuperer les paquets en attente */

while select(fdw∗, s, fdls, ∗, ∗) dofor fd in fdls do

/* Lire le paquet sur fd et extraire les champs de l'entête */

header = read(fd, header_size);elt = create(fd,�ag,dest,len,src,msgtype);/* Inserer le paquet dans la file appropriée en fonction du msgtype

*/

if priority(msgtype) = high theninsert(FILE0,elt);

elseinsert(FILE1,elt);

endendwhile FILE0 or FILE1 6= empty do

/* Récuperer le prochain paquet à envoyé suivant le principe

d'ordonnancement choisi */

elt= getNext(FILE0,FILE1) ; fd=elt.fd;fdw = dest(elt.fdl);/* Retransmettre le paquet en bouts de tailles limitées */

while !all data read dodata = read(fd, max(MAX_CHUNK, len));if x = s then

/* transmission au noeud local */

if connect thenconnect(connect_fdx,y,z, �ndIP(x,y), �ndPort(x,y,z));portx,y = read(fdx,y,z)

elsewrite(fdlx,y,z, len + src + data);

endelse

/* transmission à la passerelle distante */

write(fdws,x, header + data);end

endend

end

4.2 Mise en ÷uvre

Pour la mise en ÷uvre de cette solution, nous avons utilisé comme implémentation MPIMPICH2 [Gro02]. MPICH [GLDS96], comme la plupart des autres implémentations, utilise


1. Etiquetage des paquets

2. Ordonnancement des paquets

Priorité 1

Priorité 0

Figure 4.3 � Ordonnancement des messages MPI.

deux modes de transferts de données : le mode eager et le mode rendez-vous. La di�érenciationdes deux modes est faite grâce à un seuil stocké en dur. MPICH2 est le successeur de MPICHet y ajoute les fonctionnalités du standard MPI2.1, ainsi que des optimisations des opérationscollectives à destination des clusters. Les performances de cette implémentation sont bienconnus, elle servira donc de référence dans nos travaux. En gros, nous allons dans un premiertemps extraire les informations de l'entête du paquet MPI, les utiliser pour déterminer le typede message contenu par ce paquet (correspondance paquet - type de message) et ensuite insérerce type dans l'entête de MPI5000 de Ludovic Hablot (étiquetage des paquets).

4.2.1 Correspondance Paquet-Type de message

Comme nous l'avons dit plus haut, nous allons e�ectuer cette correspondance à l'envoi dumessage, c'est-à-dire au niveau de la procédure write() de la couche TCP sur chaque n÷ud.Nous allons utiliser les informations de l'entête MPI a�n d'associer chaque message à un destypes cités à la section 4.1.1. Pour ce faire il est nécessaire de comprendre le fonctionnementd'MPICH2 et des entêtes MPI.

Cette partie a été réalisée essentiellement avec l'utilisation de l'implémentation MPICH2,mais peut s'étendre sur toutes les autres implémentations MPI. MPICH2 utilise un certainnombre de couches et un petit nombre de procédures pour e�ectuer des opérations de com-munication de données simples. La couche MPI communique par envoi de messages constituésd'une entête � packet header � (à ne pas confondre au message MPI) et si possible des donnéesà transmettre. Elle dé�nit :

� Des types de paquets : C'est une énumération de types décrivant l'ensemble destypes de messages nécessaires pour l'implémentation de la sémantique de passage demessages MPI.

� Des formats de paquets : C'est la structure du paquet ; à chaque type de paquet, il ya un format de paquet correspondant. Tous les entêtes de paquets ont une taille �xe de


Type Data sizeSender_requestMatch

1 byte 27 bytes 4 bytes8 bytes

Figure 4.4 � Entête des paquets MPI avec Données.

40 octets et éventuellement suivis par les données. Donc suivant les types de messagesd'entête, on a les paquets MPI de tailles �xes ou variables.

Suivant leurs formats, ont a pu classer ces paquets en deux groupes : le groupe des paquetsfaisant référence à un transfert de données (suivit par une donnée) et le groupe des paquetssans données. Voici leurs formats respectifs :

1. Paquets avec données : La �gure 4.4 représente l'entête de ce type de paquet. Cespaquets correspondent aux types de messages de données tel que décrits plus haut dans4.1.1. Ces paquets sont constitués des champs suivants :

� Type de paquet : Entier identi�ant le type du message au sens MPI. ; chaque paquetMPI envoyé ici, est associé à une requête (au sens de l'implémentation). L'implémen-tation MPICH par exemple utilise 28 types de paquets pour identi�er les paquets etchaque type est codé en un octet sur l'entête MPI

� Message match : Structure qui permet l'identi�cation des messages. Elle contientles informations� Rank : C'est le rang du processus source du message.� Tag : Le tag, c'est un entier utilisé dans les opérations point à point pour identi�erla communication. Étant donné qu'une opération collective se traduit par plusieursopérations point à point, les implémentations comme MPICH utilisent des tags spé-ci�ques pour identi�er les opérations point à points qui font référence aux opérationscollectives. Ce tag nous sera donc utile pour distinguer les messages point à pointdes messages collectifs. Ainsi on pourra distinguer les messages de données collectifsaux messages de données point à point tel que cité dans 4.1.1

� Context : Entier codé sur un octet.� Requête de l'émetteur : Structure contenant les informations d'identi�cation dela requête faite par l'émetteur ; c'est une structure importante pour le transfert desdonnées de manière synchrone ou par rendez-vous. Elle contient entre autre, des infor-mations d'envoi en mode rendez-vous, les informations de traitement du tampon dedonnées et beaucoup d'autres informations assurant le bon transfert des données.

� Taille des données : La taille des données qui suivent cet entête.

Dans cette catégorie on a les types MPI suivants : MPIDI_CH3_PKT_EAGER_SEND :Envoi d'un paquet de taille comprise entre 16 o et la limite des messages eager (256 ko)en mode eager. MPIDI_CH3_PKT_EAGERSHORT_SEND : Envoi d'un paquet detaille inférieur à 16 o en mode eager. MPIDI_CH3_PKT_EAGER_SYNC_SEND :Envoi d'un message synchrone en mode eager MPIDI_CH3_PKT_READY_SEND :Envoi d'un message en mode ready. MPIDI_CH3_PKT_RNDV_REQ_TO_SEND :Envoi d'une requête pour un transfert de données en mode rendez-vous.

2. Paquets sans données : Ces paquets correspondent aux types de messages de contrôlespoint à point tel que décrits plus haut dans 4.1.1. Ils sont constitués des champs suivants :� Type de paquet : Entier identi�ant le type du message au sens MPI.� Suivant les messages on a les champs comme Requête de l'émetteur, Requête du


Message MPI

Message MPI

Message MPI

SourceLenghtDestinationFlag

Header MPI5000Message

type

Entête TCP Message MPIHeader MPI5000Message

typeTCP

MPI5000

MPI5000 +

message type

MPI

1 byte 4 bytes 4 bytes 4 bytes

1 byte

1 byte

13 bytes

13 bytes

Figure 4.5 � Entête MPI5000 + Type de Message.

récepteur, Acquittement.Dans cette catégorie, on des types MPI comme : MPIDI_CH3_PKT_EAGER_SYNC_ACK,MPIDI_CH3_PKT_RNDV_CLR_TO_SEND, MPIDI_CH3_PKT_CANCEL_SEND_REQ,MPIDI_CH3_PKT_CANCEL_SEND_RESP, MPIDI_CH3_PKT_CLOSE ect . . .

NB :Pour la di�érenciation des types de communication, nous avons utilisé dans un premiertemps le type MPI du paquet pour identi�er les messages de contrôle aux messages de données,et ensuite le tag pour identi�er les messages point à point aux messages collectifs.

Note : La majorité des messages de contrôle (dans notre sens et avec MPICH) ont unetaille de 40 o (pour ceux qui ne sont pas suivis de données. Mais il y a quelques exceptionspar exemple les messages de type (EAGER_SYNC_ACK) qui sont des acquittements et fontparfois plus de 80 o. Et de même, certaines données de taille inférieure à 16 o sont associéesà la requête et sont envoyées avec en tout une taille égale à 40 o. Que se soit un message decontrôle ou pas la taille minimal d'un paquet MPI est de 40 o.

4.2.2 Etiquetage des paquets

Il s'agit du marquage de chaque paquet suivant le type de message qu'il contient. Pourmieux aborder le processus d'étiquetage des paquets, nous allons d'abord faire un aperçusur l'entête MPI5000. Pour permettre l'éclatement des connexions, il a fallut ajouter auxpaquets MPI, une entête propre à MPI5000, pour garantir la transparence par rapport àl'implémentation. Elle contient les informations nécessaires pour réaliser la redirection desconnexions des n÷uds vers les passerelles et entre les passerelles. La �gure 4.5 montre l'entêtede MPI5000. Elle contient quatre champs :

� La destination permet de connaître le site et le n÷ud destinataire.� La source permet de connaître le site et le n÷ud source.� Le drapeau permet de distinguer les messages de contrôle propre à l'éclatement desconnexions TCP. Ces messages sont utilisés par l'architecture MPI5000 pour la commu-nication avec les passerelles de manière à réaliser un connect ou un close distant,

� La taille permet de savoir la quantité de données transmises à la suite de cet entête.A cet entête nous allons ajouter 1 octet pour l'identi�ant du type de message porté par lepaquet. Étant données que nous n'avons que 4 types de messages, nous aurions idéalement puutiliser seulement 2 bits pour le codage du type dans l'entête.

Une étape importante dans ce processus, c'est l'extraction du type de message transportépar chaque paquet. La partie suivante va nous montrer comment obtenir cette information.


Contrôle DonnéeTypecommunication Contrôle

collectifsContrôle

point à pointDonnéecollectifs

Donnéepoint à point

TailleMin/max

BT Point à point 192 575 459 77280 26ko / 160ko

CG Collective 119888 406 96045 0 150ko

FT Collective 128 798 5866 0 200o / 2Mo

IS Collective 64 836 4782 15 400o / 600ko

LU Collective 288474 417 888215 2 1ko / 200ko

MG Point à point 448 330 13191 37590 40 o /135ko

SP Point à point 192 570 444 154080 45ko/ 160ko

Table 4.1 � Comparaison des communications des NAS

4.3 Validation expérimentale

Les expériences ont été faites sur le banc d'essai tel que décrit dans la section 1.3. Nousavons écrit des scripts pour pouvoir lancer les applications et récupérer le temps d'exécutionet la répartition des paquets dans les �les d'attentes après leurs arrivées sur les descripteursde sockets de l'interface LAN côté passerelle. Nous avons également fait un pro�lage de l'envoides messages a�n d'avoir un récapitulatifs sur le nombre de messages envoyés de chaque type.

Le principe d'expérimentation est le suivant : Pour chaque application et pour chaque typed'ordonnancement, on exécute l'application 4 fois et on conserve l'exécution ayant un tempsminimal. on conserve aussi cette exécution au niveau de la passerelle et utilise des commandesgrep pour recueillir les informations de debuging sur l'évolution des �les d'attente pendantl'exécution de la passerelle.

4.3.1 Analyse des communications des NPB

Nous allons ici faire une analyse des applications des NPB a�n de savoir les types d'opé-rations MPI qu'ils utilisent ainsi que la taille des paquets (min, max). Cette analyse nouspermettra de mieux interpréter les résultats de l'ordonnancement. Nous avons dans cette par-tie, essayé de comprendre le fonctionnement des applications a�n d'anticiper l'impact de lanature de l'application sur les résultats de l'ordonnancement. Pour chaque application, nousavons donc utilisé l'étiquetage des paquets suivant le type de communication, pour identi�er :

� Le nombre de paquets de contrôle� Le nombre de paquets de contrôle associés à une transmission point à point� Le nombre de paquets de contrôle associés à une transmission collective

� Le nombre de paquets de données� Le nombre de paquets de données associés à une transmission point à point� Le nombre de paquets de données associés à une transmission collective

Le tableau 4.1 récapitule ces observations.Ces chi�res ont été récupérés à partir d'une seule passerelle ; ils ne représentent pas l'en-

semble des paquets de l'application, mais sont important pour observer le fonctionnementd'une passerelle face à l'ordonnancement.

De cette étude nous pouvons séparer ces applications en trois classes :� C1 : Classe d'applications qui communiquent beaucoup de façon synchrone avec de grosmessages, susceptibles de créer plus de goulot d'étranglement au niveau des passerelles(besoin d'ordonnancement) : constituée de IS et FT.


� C2 : Classe des applications qui communiquent beaucoup mais de manière asynchroneset avec de petits messages qui n'ont nécessairement pas besoin d'un ordonnancement(�le de petite taille) : constituée de SP et BT.

� C3 : Classe des applications qui utilisent beaucoup d'opérations collectives mais avecde petites tailles de messages (besoin d'ordonnancement) : constituée de CG, LU et MG.

De plus ces observations ont été prouvées par les résultats de Hablot Ludovic où l'onconstate que pour ces applications de classe C1 et C3, MPI5000, n'apporte aucun avantage, aucontraire on a des résultats moins bons que sans MPI5000, ce qui est du au goulot d'étrangle-ment crée au niveau des passerelles.De plus, avec les �gures 2.1, 2.2 et 2.3 ont remarque que lataille de la �le d'attente pour la classe C1 est constamment élevée et moyenne pour les classesC2 et C3. L'objectif de cet ordonnancement est donc de diminuer ce goulot d'étranglementpour les applications de la classe C1 et C3.

4.3.2 Résultats

Nous allons exécuter ici toutes les NAS avec les di�érentes politiques d'ordonnancementprésentées à la section 4.1.1 a�n de voir laquelle améliore les performances. Sur la �gure 4.6,ces politiques seront désignées de la manière suivante :

� MPI5000 + collectif : On donne la priorité aux messages collectifs� MPI5000 + contrôle : On donne la priorité aux messages de contrôle� MPI5000 + Ordre : Les paquets sont envoyés par ordre de grandeur en taille. Le pluspetit message d'abord.

Après plusieurs expérimentations nous avons obtenu des résultats représentés sur la �gure 4.6.Elle présente le temps d'exécution des NPB sur MPI5000 avec l'ordonnancement relatif autemps sans ordonnancement. Les temps d'exécution de chaque application avec et sans chaquetype d'ordonnancement sont relevés et le calcul du pourcentage entre les deux exécutions este�ectué.

A�n d'analyser ces résultats, nous allons d'abord parcourir les applications une par une a�nde voir quel type d'ordonnancement est le mieux adapté et pourquoi. Ensuite nous ferons uneclassi�cation des types d'ordonnancement par groupe d'applications ; ainsi nous indiquerons letype d'ordonnancement qui donne de meilleurs résultats avec les applications e�ectuant plusd'opérations point à point et des messages de petites tailles, et ensuite les applications auxopérations collectives et des messages de grandes tailles.

� BT : Pour cette application, il ressort que le type d'ordonnancement le mieux adapté estMPI5000+Contrôle avec 2% de diminution de temps d'exécution, suivi de MPI5000+Collectifavec 1,5%. Étant donnée que BT communique de manière asynchrone, elle ne crée pasbeaucoup de congestion sur la passerelle, et de plus la majorité des messages envoyés iciétant de contrôles, avec quelques messages collectifs, nos ordonnancements n'améliorentpas grand chose au temps d'exécution.

� CG :Avec cette application, le type d'ordonnancement le mieux adapté est MPI5000+Contrôleavec 2% de diminution de temps d'exécution, suivi de MPI5000+Ordre avec environ 2%d'amélioration. Comme nous l'avons vu sur la �gure 2.3 CG ne provoque pas une grandetaille de �les sur les passerelles, il y a toujours au maximum 3 messages dans la �led'attente, et de plus CG envoie 120294 paquets de contrôle contre 96045 de paquetsde données seulement et ces messages sont en majorité des messages collectifs, d'où lesmessages sont à chaque fois tous dirigés vers une seule �le d'attente ce qui ne changepas grand chose au temps d'exécution de l'application.

� FT : Elle envoie 926 paquets de contrôle contre 5866 paquets de données. C'est des


0.8

0.9

1

1.1

1.2


Tem

ps d

’exe

cutio

n re

latif

Applications

MPI5000MPI5000 + CollectifMPI5000 + Controle

MPI5000 + Ordre

Figure 4.6 � Résultats de l'ordonnancement.



Premier Contrôle Contrôle Contrôle Collectif Contrôle Contrôle Contrôle

Amélioration 02% 02% 09% 06% 02% 04% 02%

Deuxième Collectif Ordre Ordre Contrôle Ordre Ordre Collectif

Amélioration 1.5% 02% 07% 03% négatif négatif 1.7%

TempsMPI5000

168s 134s 186s 15s 73s 11s 237s

Table 4.2 � Récapitulatif des résultats des NAS

opérations collectives à gros messages. Les résultats obtenus nous montrent que le typed'ordonnancement le mieux adapté pour FT est MPI5000+Contrôle avec 9% de dimi-nution de temps d'exécution, suivi de MPI5000+Ordre avec 7% d'amélioration. Nousobservons ici une meilleure répartition des messages entre les deux �les.

� IS : Pour cette application, qui envoie 900 paquets de contrôle contre 4797 paquets dedonnées dont la majorité sont des opérations collectives à gros messages, il ressort quele type d'ordonnancement le mieux adapté est MPI5000+Collectif avec 6% de diminu-tion de temps d'exécution, suivi MPI5000+Contrôle avec 3%. Cette application est trèssimilaire à FT avec une bonne di�érenciation des paquets donc de meilleurs résultats.

� LU : Elle envoie en majorité (au 3/4) des paquets de données et e�ectue des opéra-tions collectives (888215 paquets collectifs/888217 paquets de données). Les résultatsmontrent que le type d'ordonnancement le mieux adapter est MPI5000+ Contrôle avec2% de diminution de temps d'exécution. Mais en général, pour cette expérimentationtous les autres ordonnancements sont mauvais. Cette application crée un léger goulotd'étranglement sur les passerelles (confère 2.3) d'où il y a pas une grande améliorationavec l'ordonnancement.

� MG : C'est une application, qui envoie 778 paquets de contrôle contre 50781 paquetsde données. 2/3 de ces paquets de données sont des paquets point à point. D'après lesexpérimentations, il ressort que le type d'ordonnancement le mieux adapté pour MG estMPI5000+Contrôle avec 4% d'amélioration. Mais en général, pour cette expérimentationparticulière tous les ordonnancements sont mauvais. NB : Les résultats obtenus pour ISet MG sont très changeants compte tenu de leurs temps d'exécution qui sont très courtsdonc les résultats ne sont pas tout le temps valide et il est presque impossible d'en tirerune conclusion.

� SP : Pour cette application, qui envoie 762 paquets de contrôle contre 154524 paquetsde données dont 154080/ 154524 paquets, sont des paquets point à point, il ressort que letype d'ordonnancement le mieux adapté est MPI5000+Contrôle avec 2% de diminutionde temps d'exécution, suivi de MPI5000+Collectif avec également 1.7%.

Comme récapitulatif, nous avons le tableau 4.2, où nous avons pour chaque application,les deux premiers types d'ordonnancement avec les pourcentages de gains associés.

A l'aide de ce tableau, nous pouvons déduire que le meilleur ordonnancement pour lesapplications point à point ou à petits messages (C2) est MPI5000+Contrôle avec en moyenneune amélioration de 2% et le meilleur ordonnancement pour les applications collectives àgros messages (C1) est également MPI5000+Contrôle avec des améliorations allant de 6 à9%. Quant aux applications utilisant en majorité des messages collectifs de petites tailles(C3) on a des résultats semblables à C1, excepté avec MG où l'on a avec l'ordonnancementMPI5000+Contrôle une amélioration de 4%. Il est également à noter que les résultats de FTsont les plus signi�catifs et les plus constants qui con�rment que dans la mesure du possible,



1 site 74s 20s 32s 4s 44s 2s 88s

2 sites +MPI5000

168s 134s 186s 15s 73s 11s 237s

surcoût sans Ordo 94s 114s 154s 11s 29s 9s 149s

2 sites + Ordo 165s 131s 166s 14s 71s 10s 233s

surcoût avec Ordo 91s 111s 134s 10s 27s 8s 145s

Gain surCommunications

3.2% 2.6% 13% 9% 6.8% 11% 2.6%

Table 4.3 � Gain sur les communications des NPB

un bon ordonnancement permet d'améliorer le temps d'exécution des applications à fort goulotd'étranglement.

4.3.3 Gain sur les communications

Avant de conclure ce chapitre, deux questions se posent : Est-ce que les résultats obtenussont conformes à ce qu'on espérait ? Une amélioration de 9% sur le temps d'exécution d'uneapplication est-ce su�sante ? Pour répondre à ces questions, il est important de noter que letemps d'exécution d'une application est constitué du temps de calcul et du temps de commu-nication. Le temps de calcul est �xe ici, et nos optimisations concernent seulement le temps decommunication. A�n de pouvoir de façon tangible avoir une vision sur la proportion du gainen temps de communication, nous avons fait une expérience où nous avons dans un premiertemps exécuté les NPB avec 16 n÷uds d'un même site (temps de communication minimal)et ensuite nous avons fait la même expérience entre deux sites dont la latence est de 9.9µs(temps de communication longue distance entre Lyon et Bordeaux).

Le tableau 4.3 resume nos observations. Nous avons les résultats de l'exécution des applica-tions sur 1 seul site, sur 2 sites avec MPI5000 et sur 2 sites avec Ordonnancement. Nous avonségalement calculé le surcoût du passage de 1 site à 2 sites en faisant juste la di�érence entreles temps d'exécution. Nous l'avons fait pour les exécutions sans et avec l'ordonnancement.On observe donc une di�érence de surcoût entre les exécutions avec et sans ordonnancement.On utilise donc ensuite cette di�érence pour trouver le pourcentage de gain sur les communi-cations.

Ce tableau montre que le surcoût est variable suivant les applications. Si nous prenons lecas de FT par exemple on a 154 secondes de surcoût du aux communications longue distancepour MPI5000 contre 134 secondes de surcoût avec l'utilisation de l'ordonnancement, ce quicorrespond à une amélioration de 13% sur temps de communication. De même on constatequ'avec IS on arrive à une augmentation de 9% sur le temps de communication.

On constate également une bonne amélioration des communications pour les applicationsLU (6.8%) et MG (11%) qui appartiennent à la classe C3 (communiquent beaucoup par desopérations collectives avec de petits messages). D'où nous pouvons conclure que les résultatsobtenus par l'ordonnancement donnant la priorité aux messages de contrôles répondent à nosattentes car améliorent les communications des applications qui communique beaucoup defaçon synchrone : C1 et C3.


4.4 Conclusion

De manière générale, l'ordonnancement donnant la priorité aux messages de contrôle l'em-porte sur les autres. Dans certains cas les résultats sont médiocres car le critère d'ordonnance-ment fait qu'il y a qu'une seule �le qui soit utilisée et aussi certaines applications ne créent pasassez de surcharge sur les passerelles et dans ces circonstances, l'ordonnancement n'apportepas su�samment d'avantage.. Suivant les analyses des applications faites en 4.1, nous avonsvu que toutes ces applications à l'exception de BT et SP (C2), envoient beaucoup de mes-sages collectifs, d'où la présence des paquets de synchronisation et d'envoi de requêtes entreles n÷uds. Ce type d'ordonnancement permet donc à ces types de messages `urgents' d'êtreenvoyés en priorité et de débloquer ainsi plus rapidement les n÷uds en attente. De plus nousvoyons qu'avec des applications comme FT et IS, qui envoient en même temps de très grosmessages qui pour être envoyés utilisent le mode rendez-vous qui lui aussi multiplie les paquetsde contrôle.

Chapitre 5

Autres propositions

5.1 Placement e�cace des tâches . . . . . . . . . . . . . . . . . . . . . . 41

5.1.1 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.1.2 Méthode de placement . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.2 Plusieurs connexions TCP sur le WAN . . . . . . . . . . . . . . . . 43

5.2.1 Quelques mots sur le contrôle de congestion de TCP . . . . . . . . . 44

5.2.2 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.2.3 Mise en ÷uvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.3 Choix d'utilisation ou pas des passerelles . . . . . . . . . . . . . . . 46

5.3.1 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.3.2 Mise en ÷uvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

40

CHAPITRE 5. AUTRES PROPOSITIONS 41

L'ordonnancement est la seule question que nous avons traité en intégralité, de la mise en÷uvre à l'évaluation. Nous allons ici présenter les di�érentes propositions faites au niveau desautres questions pas moins importantes de ce stage.

5.1 Placement e�cace des tâches

Nous allons aborder dans cette section la modélisation et la mise en ÷uvre de la proposi-tion du placement e�cace des tâches. Dans un environnement de grille de calcul multi-clusters,le réseau longue distance (par sa grande latence) connectant les di�érents clusters coûte trèscher pour les applications parallèles et devient un véritable goulot d'étranglement freinantl'exécution rapide de l'application. Il importe donc dans un contexte d'optimisation des com-munications de diminuer les communications longue distance au pro�t des communicationsplus rapides. Dans notre approche, il sera donc question de proposer une méthode de place-ment e�cace des processus aux processeurs pour l'exécution d'applications parallèles dans desgrilles hétérogènes, prenant en compte le schéma de communication de l'application et le coûtdes communications entre les processus (distance). L'objectif étant d'associer les processus quicommuniquent le plus aux processeurs les plus proches les uns des autres.

5.1.1 Proposition

Dans une grille de recherche comme grid5000, pour l'exécution d'une application, plusieurschoix s'o�rent : Puisque nous désirons minimiser les communications longue distance (inter-cluster ou inter-site), il serait sensé d'utiliser un seul cluster pouvant satisfaire la demande enressource (nombre de processeurs). Mais dans certains cas aucun site ne possède l'ensembledes ressources, il faut donc chercher des ressources supplémentaires sur d'autres sites. Commepremier site, on prendra le site o�rant un maximum de ressources et on complétera les res-sources manquantes en cherchant les sites les plus proches du premier en termes de latence,pouvant compléter la demande. Ainsi on aura une bonne majorité des n÷uds dans un mêmesite (communications rapides) et peu de n÷uds à l'extérieur (communications longue distance).Dans certains cas aussi on peut avoir une architecture �xe comme par exemple le banc d'es-sai utilisé dans nos expérimentations avec un nombre de n÷uds et les di�érents sites �xes etconnus d'avance. Peu importe le cas, des améliorations peuvent être apportées à l'exécutionen diminuant le nombre de communications coûteuses.

Pour pouvoir e�ectuer cette distribution de processus (tâches) aux processeurs (n÷uds),trois sous problèmes doivent être résolus. Dans un premier temps, il faudra mesurer ou estimerles besoins en terme de communication de l'application, ensuite il faudra également mesurerou fournir les ressources réseau disponibles, et en�n il nous faut des critères permettant dejuger l'e�cacité d'une association de tâches aux n÷uds disponibles.

Exigences de communication : Ce qui nous intéresse ici c'est de savoir pour chaquecouple de tâches la quantité d'information qu'elles s'échangent pendant l'exécution de l'appli-cation. Ceci peut être fait par des mesures prises au cours de l'exécution complète ou partiellede l'application. Il existe des applications pour lesquelles le schéma de communication peuêtre estimé par exécution d'une petite partie de l'application, car leurs façons de communi-quer reste inchangées jusqu'à la �n de leurs exécutions. Pour notre part, nous allons utiliser unoutil développé par Ludovic Hablot instrAppli pour déterminer le schéma de communicationdes applications par leur exécution complète. Pour n tâches, nous aurons donc une matrice


W de n ∗ n éléments, chaque élément Wi,j représentant le nombre de paquets envoyés par latâche i à la tâche j.

Ressources réseau disponibles : Il importe également de pouvoir identi�er pour chaquecouple de n÷uds, les ressources réseaux des liens qui les séparent a�n de connaitre le coûtd'une communication entre ces deux n÷uds. Pour plus de simplicité et avec deux clusters,nous considérons toutes les communications intra cluster de coût 0 et les communicationsinter-cluster de coût 1. Pour s n÷uds, nous obtenons donc une matrice binaire D de s ∗ séléments, chaque élément Di,j représentant le coût de l'envoi d'un paquet du n÷ud i vers len÷ud j.

5.1.2 Méthode de placement

Nous allons ici formuler le problème sous forme de problème de satisfaction de contraintebasé sur l'utilisation des deux tables (taux de communication, coût de communication) et nousallons utiliser une heuristique de recherche a�n d'approcher la solution optimale au problème.Ce problème peut être formulé de la manière suivante :

Ce problème peut être formulé de la manière suivante : Soit une application repartie sur ntâches à exécuter sur s n÷uds, et une matriceW dont les élémentsWi,j représentent le taux decommunication de la tâche i vers la tâche j et une matrice D dont les élémentsDi,j représententle coût de chaque communication du n÷uds i vers le n÷ud j. (i, j = 1, . . . , n) pourW et (i, j =1, . . . , s) pour D. Soit P un vecteur de n éléments, représentant un placement des n tâches surn n÷uds (n ≤ s), Pi étant le n÷ud attribué à la tâche i. Notre objectif est donc de trouver untel placement minimisant le coe�cient de placement : Pcoef =

∑ni=1

∑sj=1Wi,j ∗DPi,Pj . Une

telle attribution minimise le coût total des communications de l'application.

Formulation mathématique :Minimiser

∑ni=1

∑sj=1Wi,j ∗DPi,Pj

Contraintes∑n

i=1Di,j ≥ 0 j = 1, . . . , sWi,j ∈ { 0, 1 } i = 1, . . . , n, j = 1, . . . , s

Ce problème étant désigné comme étant NP-Complet, il existe plusieurs heuristiques dans lalittérature pour ce genre de problème de recherche dans un grand espace de solution. L'article[BSB+01] e�ectuer une comparaison de 12 heuristiques di�érentes, dont nous allons utilisercelle qui semble la plus prometteuse. L'heuristique Glouton. Cette méthode nous permettrade trouver un coe�cient de placement proche de l'optimal, qui minimise le coût des com-munications de l'application. Un algorithme Glouton pour résoudre ce problème procède en nitérations : à chaque itération, une tâche est placée sur un n÷ud libre, en essayant de minimiserla fonction objectif. La procédure est la suivante :

� Choisir la tâche i non attribuée avec le plus grand taux de communication avec uneautres tâches j

� Placer la tâche i sur un n÷uds permettant de minimiser la distance potentielle entre iet j.

Après avoir trouvé une première solution possible avec l'algorithme Glouton, nous applique-rons des technique de branch and bound pour approcher d'avantage la solution optimal enapprofondissant la recherche. Vous trouverez cet algorithme (2) en annexe.


0 1 2 3 4 5 6 7

0 143 Msg 14 Msg 220 Msg 50 Msg 26 Msg 15 Msg 48 Msg 15 Msg








Table 5.1 � Schémas de communication de IS (Wi,j)

Cas d'utilisation

Nous allons ici étudier de manière théorique l'amélioration aux quel on pourrait s'attendre.Dans cet exemple, le tableau 5.1 présente les di�érentes communications entre les tâches del'application IS des NPB : La matrice Wi,j . Nous l'avons exécuté en utilisant l'implémentationMPICH avec 8 tâches. Nous avons utilisé InstrAppli pour compter le nombre de messageséchangés entre les deux tâches.

Pour cette architecture, on aura la matrice binaire des distances 8*8 Di,j .Après réservation des n÷uds et suivant l'ordre d'attribution des tâches habituelle (alpha-

bétique), nous aurons la con�guration suivante :

(Pi)1 :tâche0 : n÷ud0 site1 ; tâche1 : n÷ud1 site1 ; tâche2 : n÷ud2 site1, tâche3 : n÷ud3 site1tâche4 : n÷ud4 site2 ; tâche5 : n÷ud5 site2 ; tâche6 : n÷ud6 site2 ; tâche7 : n÷ud7 site2

Le coe�cient de placement (∑n

i=1

∑sj=1Wi,j ∗ DPi,Pj ) avec cette distribution nous donne

Pcoef = 2369 qui représente le coût total de l'exécution de l'application avec ce placement.Par contre, le placement obtenus avec notre approche est le suivant :

(Pi)2 :tâche0 : n÷ud7 site2 ; tâche1 : n÷ud3 site1 ; tâche2 : n÷ud2 site1 ; tâche3 : n÷ud6 site2tâche4 : n÷ud1 site1 ; tâche5 : n÷ud4 site2 ; tâche6 : n÷ud0 site1 ; tâche7 : n÷ud5 site2

Le coe�cient de placement avec cette distribution nous donnes Pcoef = 1465 ce qui représente38% d'amélioration par rapport au placement arbitraire du premier cas.

5.2 Plusieurs connexions TCP sur le WAN

Cette proposition vise à savoir si le fait d'avoir plusieurs connexions sur le WAN peut fa-voriser une complétion au plus tôt de l'application en permettant une utilisation plus e�cacede la bande passante disponible sur le lien longue distance. Il est clair avec les résultats de Ha-blot, que les applications à gros messages comme FT et IS ont beaucoup de mal avec MPI5000.Cette approche à donc pour objectif, une retransmission rapide des paquets, diminuant ainsile temps d'attente des paquets dans les �les et donc le temps d'exécution de l'application.


5.2.1 Quelques mots sur le contrôle de congestion de TCP

TCP utilise une fenêtre de congestion qui détermine la quantité maximale de paquetsen vol c.-à-d. la quantité de paquets non acquittés. Cette fenêtre a pour but de déterminerdynamiquement la quantité e�ective de paquets que le réseau est capable d'absorber. De cefait, elle contribue à limiter le débit d'émission de manière à éviter les pertes. La fenêtrede congestion évolue au cours du temps en fonction des informations sur le réseau qui sontrapportées par les acquittements (ACK). La �gure 5.1 montre l'évolution de la fenêtre decongestion de TCP New Reno [FHG04] qui est la version standard de TCP. Tout d'abord,TCP utilise un mécanisme de démarrage lent (slowstart) de manière à déterminer la bandepassante disponible sur le lien. La fenêtre de congestion est initialement �xée à deux paquets,puis elle est augmentée exponentiellement à chaque réception d'un ACK, jusqu'à ce qu'uneperte soit détectée ou que la taille de la fenêtre de congestion ait atteint un certain seuil(slowstart threshold). TCP quitte alors la phase de slowstart pour passer en mode d'évitementde congestion et divise par deux la fenêtre de congestion. Durant cette phase, la fenêtre decongestion est incrémentée d'un paramètre par RTT. a est égal à 1 dans TCP New Reno :cwnd = cwnd+a; Quand une perte est détectée (par trois ACK identiques ou par l'expirationdu délai de retransmission (RTO), la fenêtre de congestion est diminuée en fonction de b quiest égale à 0,5 dans TCP New Reno. Le RTO est calculé en fonction du RTT (200µs + RTTdans Linux). cwnd = cwnd˘b ∗ cwnd;

En�n, lorsque qu'aucune donnée n'est transmise pendant un certain temps (idle time,équivalent au délai de retransmission) ou lorsqu'une perte est détectée par l'expiration dudélai de retransmission, TCP recommence à émettre par une phase de démarrage lent.

RTO

idle time

slowstart slowstart

perte

perte

Taille

dela

fen.decongestion

perte

Temps

perte ou

Figure 5.1 � Évolution de la fenêtre de congestion de TCP New Reno.

5.2.2 Proposition

Avec l'utilisation de TCP sur le lien long distance, à chaque congestion ou expiration duidle-time, nous voyons la fenêtre de congestion chuter drastique-ment. En utilisant plusieursconnexions, si l'une d'entre elles fait recours au slow start ou à une diminution de la fenêtre decongestion, elle seule sera pénalisée. Les autres connexions auront leurs fenêtres de congestioninchangés ce qui permet d'avoir un débit général plus grand qu'avec une seule connexion.

Un exemple simple : On a un cas avec une connexion avec 50 Mb comme fenêtre decongestion, un autre cas avec 5 connexions de 10Mb de fenêtre de congestion. Si une congestionsurvient, le cas 1 aura une fenêtre de congestion de 25 Mb alors que le cas 2 aura une fenêtrede 45 Mb car une seule connexion va voir sa fenêtre de congestion divisée par deux.

Mais l'utilisation de cette approche peut également poser des problèmes avec MPI5000 ;


A B

Eclatement du paquet Fusion des bouts de paquets

Figure 5.2 � Plusieurs connexions sur le WAN.

Avec plusieurs connexions en parallèles au niveau du WAN, on béné�cie moins de l'agrégationde �ux réalisée par l'éclatement des connexions TCP par MPI5000. D'où les applicationscommuniquant peu vont sou�rir de l'expiration du Idle-time et donc du slow start sur cesconnexions. Deux solutions ont été proposées pour le problème de slow start dans GridFTPdans le contexte du transfert de plusieurs petits �chiers : le pipeline et le Channel caching.

� Pipeline : Consiste à ne pas attendre la �n du transfert d'un �chier avant de demanderle transfert du �chier suivant. Ceci est réalisable dans le cas où on connaît d'avance tousles �chiers (données) et dans quel ordre les transférer. Mais dans le cadre de MPI5000,les passerelles n'ont aucune informations d'avance sur les données à transférer ni leursordre de précédence. D'où nous ne pouvons pas appliquer cette technique avec MPI5000.

� Channel caching : Consiste à ne pas fermer la connexion à chaque �n de transfert ;ainsi plus besoin d'établir une nouvelle connexion (très coûteux par la phase d'authenti�-cation), on garde la même fenêtre de congestion et les transferts suivant peuvent donc enbéné�cier. Ici, il y a aucune attente car tous les �chiers (données) à transférer sont déjàdisponible au niveau de l'émetteur, ainsi pas d'expiration du idle-time, ni diminution dela fenêtre de congestion (si pas de perte).

Mais dans notre cas, les données ne sont transférées que lorsqu'elles arrivent et pour lesapplications qui communiquent peu, il peut y avoir un grand écart entre deux communicationsqui entraînera une expiration du idle-time et donc un slow start. D'où nous avons prévu unenvoi périodique de paquets (de contrôles) entre les passerelles a�n de maintenir les connexionsactives et les fenêtres de congestions à jours. La �gure 5.2 , résume le fonctionnement de notrenouvelle architecture.

Dans ce scénario, A veut envoyer un message à B ; il envoie donc l'intégralité du messagevers la passerelle ; celle-ci subdivise le message suivant un seuil à dé�nir (la taille de la fenêtrede congestion désirée) en petits paquets, les paquets seront étiquetés par un numéro pourpermettre la reconstitution du paquet initial et ensuite transmis en utilisant des connexionsTCP parallèles sur le WAN. Dès leurs arrivées sur la passerelle distante, les bouts de paquetsseront réordonnés, fusionnés et retransmis au n÷ud destinataire de paquet. Le nombre deconnexions ici dépendra de la taille du paquets d'origine ; si le paquet est très petit, il n'estpas nécessaire d'utiliser plusieurs connexions pour son transfert. Nous aurons donc un nombremaximum de connexions (renseigné lors du lancement de l'application) pouvant être utiliséespour une redistribution, mais le nombre réellement utilisé pour une la retransmission d'un


paquet donnée, se situe donc entre 1 et ce Max.

5.2.3 Mise en ÷uvre

Pour que ce processus puisse marcher, il est important d'e�ectuer certaines modi�cationssur la bibliothèque MPI5000 et sur le code de la passerelle.

� Nous modi�erons le processus de connexion entre les passerelles de sorte à établir nconnexions entre les passerelles ; chaque connexion utilisant un numéro de port di�érent.Le nombre de connexion est dé�ni par l'utilisateur.

� Nous réaliserons des envois parallèles de bouts de paquets sur chacune de ces connexions.� Sur chacune des connexions, envoyer un paquet périodiquement a�n d'éviter l'expirationdu idle-time.

� Deux facteurs importants peuvent in�uencer les performances de cette architecture :La taille du bu�er TCP sur chacune de ces connexions et le nombre de connexions surle WAN. Il est clair qu'un nombre très grand de connexions reviendrais à l'architec-ture d'origine sans éclatement de connexion, ce qui ne favoriserait pas les applicationsutilisant plus des communications point à point. De même la taille du bu�er doit êtreproportionnelle à la taille de la fenêtre de congestion sur chaque connexion a�n de maxi-miser le débit réel sur la connexion. Dans l'article [STWF03] sur gridFTP, les chercheursde globus ont introduit une méthode dynamique d'initialisation et de mise à jour de lataille du bu�er TCP par rapport aux changements subis par la fenêtre de congestion toutau long de la durée de la connexion. Windowsize = Throughput ∗ Round− tripT ime.Ils proposent une technique de détermination de la bande passante courante et du RTTcourant en faisant des mesures. Pour la bande passante, ils capturent le débit actuel à desintervalles de temps périodiques et pour le RTT, ils envoient périodiquement des paquetsécho sur le lien et attende la réponse de l'hôte distant. Nous pouvons également utiliserce même principe ici a�n de garantir une bonne performance de TCP pour chacune desconnexions.

5.3 Choix d'utilisation ou pas des passerelles

Nous allons aborder ici la conception, et la mise en ÷uvre de la proposition du choixd'utilisation de la passerelle ou pas pour une communication donnée.

5.3.1 Proposition

Les passerelles dans l'architecture MPI5000 se chargent du routage et la retransmission despaquets vers leurs destinataires distants. L'évaluation faite par Hablot nous a permis de voirque les applications envoyant beaucoup de messages collectifs créent un goulot d'étranglementimportant au niveau de la passerelle. D'où vient la nécessité d'alléger le travail de la passerelleen utilisant des connexions auxiliaires pour le transfert de certains types de données. En e�et,la nature des opérations collectives et les di�érentes synchronisations nécessaires ici, rendentles applications utilisant beaucoup d'opérations collectives d'avantage susceptible de subirde la latence sur les liens longues distances. Il est donc question ici de mettre en place unmiddleware permettant suivant la nature de la communication de décider de passer par lapasserelle MPI5000 ou par une connexion directe vers le n÷ud distant. Plus précisément, lespaquets faisant références aux communications collectives devront utiliser la connexion directe


Connexion directe

Eclatement des connexions

A B

Figure 5.3 � Choix d'utilisation d'MPI5000.

tandis que les communications point à point devrons passer par le passerelle MPI5000. Ceprincipe est résumé par la �gure 5.3.

5.3.2 Mise en ÷uvre

Pour la mise en ÷uvre de cette solution, nous préconisons utilisation de l'interception desappels socket fait par MPI5000. Le principe ici est de créer une connexion directe vers le n÷uddistant, chaque fois qu'une connexion vers la passerelle est crée dans la phase de lancementde l'application et du daemon de la passerelle. C'est-à-dire que chaque n÷ud sera relié à deuxsockets pour chaque n÷ud distant, une vers la passerelle ( pour les messages point à point),et une autre directe vers le n÷ud distant. La création de la connexion directe se fera lors desl'appels connect() et accept(). Les communications respecteront le protocole suivant :

� A l'envoi, (interception du write)� On décode le paquet TCP a�n de savoir de quel type de communication il s'agit : cecirespecte le principe d'étiquetage et de di�érentiation au chapitre 4.

� Si c'est une opération collective on récupère le descripteur de socket correspondant àla connexion directe vers le n÷ud distant et on retransmet le paquet sur ce socket.

� Si ce n'est pas une opération collective on récupère le descripteur de socket correspon-dant à la connexion vers la passerelle et on retransmet le paquet sur ce socket.

� A la réception, (interception du read)� On e�ectue un select sur les deux descripteurs de socket (passerelle et directe), poursavoir le socket sur lequel une donnée est en attente de lecture.

� Si les deux sockets ont des données en attentes, on copie les données des deux socketdans le tampon de réception, et on lit la première donnée en laissant la seconde pourun prochain appel du read.

� Si un seul socket a des données en attente, on lit sur ce socket.Vous trouverez l'algorithme complet de cette approche en annexe de ce document A.

Chapitre 6

Conclusion

6.1 Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

48

CHAPITRE 6. CONCLUSION 49

6.1 Conclusion générale

Les développements des réseaux et des technologies de communication ont permis l'émer-gence du calcul parallèle et des grilles de calculs. Néanmoins, les nombreuses possibilités d'uti-lisation des grilles sont encore tempérées par une complexité de mise en ÷uvre importante.Il convient donc de s'assurer une gestion la plus e�cace possible des communications, et ceciparticulièrement dans l'optique d'améliorer les communications parallèles massives a�n defavoriser la complétion au plus tôt des applications.

La plupart des applications parallèles sont écrites à l'aide du standard MPI (Message Pas-sing Interface) qui fonctionne par passage de messages entre processus. Le temps d'exécutiond'une application parallèle est constitué de deux composantes qui sont le temps de calcul et letemps de communication entre les processus.

Dans ces travaux de stage, nous avons considéré le problème général d'exécution e�caced'application MPI sur une grille de calcul avec TCP comme protocole de transport sur le réseaulongue distance. Plus précisément, nous sommes partis d'une plateforme utilisant l'éclatementdes connexions TCP et avons proposé des approches permettant de diminuer le temps de com-munication des applications, améliorant ainsi les performances en termes de temps d'exécutionglobale d'une application MPI en se basant sur un ordonnancement e�cace, un placement in-telligent des tâches et une multiplication des connexions sur le longue distance a�n de mieuxexploiter la capacité de ce type de lien.

6.2 Contribution

Pour la réalisation de ce travail, nous avons commencé par identi�er les di�érentes pro-blématiques des communications dans notre contexte d'éclatement des connexions TCP avecutilisation des passerelles, pour cela, il nous a fallut dans un premier temps comprendre lefonctionnement de cet éclatement des connexions, et d'analyser leurs performances sur les ap-plications de NPB. Les observations faites à base de cette analyse nous ont permit de nousposer quelques questions sur les possibilités d'amélioration des performances de l'éclatementdes connexions.

Ces questions sont les suivantes :� Est-ce qu'un ordonnancement e�cace au niveau des passerelles permettrait de diminuerl'impact du goulot d'étranglement et faciliter l'exécution rapide de l'application ?

� Est-ce qu'une attribution e�cace des tâches aux processeurs de sorte à diminuer lenombre de communications longues distances permettrait de diminuer le temps d'exé-cution global de l'application ?

� Est-ce que le fait d'utiliser plusieurs connexions TCP sur le WAN de sorte à disposer deplus de bande passante sur le WAN pourrait améliorer le comportement des applicationssynchrones à gros message est diminuer le temps de complétion ?

� Est-ce que le fait d'utiliser les passerelles pour certaines communications et pas pourd'autres dans une même application (par exemple ne pas utiliser les passerelles pour lescommunications collectives) pourrait faire avancer plus rapidement l'application ?

En gros, notre contribution se résume à l'étude des problèmes posés par l'utilisation despasserelles pour les applications utilisant beaucoup d'opérations collectives et de gros messageset l'apport des améliorations en mettant en ÷uvre les approches décrites par les questionsprécédentes.

Pour répondre à la première question, nous proposons une solution dont le but est dediminuer l'impact du goulot d'étranglement sur les passerelles de l'architecture MPI5000 en


utilisant un ordonnancement des messages MPI suivant le type de communication. En e�et,le standard d'envoi de message MPI, utilise plusieurs types d'opérations permettant de les ré-partir en opérations collectives et opérations point à point. La signalisation et synchronisationentre les processus pour un bon déroulement de l'application sont e�ectuées par les messagesde contrôle. Nous avons mis en place plusieurs politiques d'ordonnancement a�n de favoriserun type de messages par rapport aux autres. Nous avons montré que ce mécanisme pouvaitdiminuer le temps d'attente individuel des processus et nous avons validé notre approche pardes expérimentations sur la plateforme grid5000 et il en ressort que, l'ordonnancement don-nant la priorité aux messages de contrôle donne de meilleurs résultats avec une augmentationde 9% sur le temps d'exécution et 13% sur le temps de communication des applications àcommunications parallèles massives et pour les applications à communications point à point,on a 2% d'amélioration de temps d'exécution et 2.6% à 11% sur le temps de communication.

Nous avons également au cours de ce travail, fait d'autres propositions relatif dans unpremier temps au placement e�cace des tâches dans la grille, et ensuite à l'utilisation deplusieurs connexions TCP sur le lien longue distance.

Pour ce qui est du placement des tâches, nous avons proposé une formulation et unerésolution de ce problème en utilisant l'heuristique Glouton et la méthode Branch and Bound,mettant en évidence la minimisation du nombre de communications longue distance. Nousavons montré que cette approche pourrait permettre une amélioration du temps de complétionde l'application par diminution de la latence causée par les liaisons longue distance.

Nous avons également proposé une extension de l'architecture MPI5000 en utilisant plu-sieurs connexions TCP sur le WAN. A la gridFTP, cette solution permettrait d'utiliser pluse�cacement la bande passante disponible sur le lien long distance. Par de simples cas d'utilisa-tions, nous avons montré que cette approche serait grandement béné�que pour les applicationsà communications parallèles massives.

Une autre approche évoquée au cours de ce travail c'est celle de décider de l'utilisation ounon de MPI5000 suivant le type de communication applications, ceci permettrait de choisir defaçon automatique de ne pas utiliser MPI5000 pour les communications massives (qui donnentde mauvais résultats par rapport au cas sans MPI5000) et d'utiliser MPI5000 seulement pourles applications qui communiquent moins.

6.3 Perspectives

Les travaux e�ectués dans ce stage, ouvrent les portes à de nombreuses perspectives àcourt ou long terme pour la réduction de l'impact négatif d'MPI5000 sur les applications àcommunications parallèles massives. En court terme nous pouvons citer comme perspective lamise en ÷uvre et l'évaluation des approches pas évaluées ici par manque de temps. En longterme on peut envisager :

1. Utilisation de plusieurs passerelles par siteEn fait, le problème des applications à communications collectives, est qu'elles réalisentbeaucoup de communications, créant ainsi un goulot d'étranglement incontournable auniveau des passerelles. Une redistribution e�cace des messages permet une certaine amé-lioration, mais qui est toujours limitée par les capacités physiques des cartes sur les pas-serelles. De même l'utilisation de plusieurs connexions TCP pour le transfert d'un même�ux de données optimise l'utilisation de TCP sur le lien entre les passerelles, mais nechange pas les propriétés physiques des passerelles. De plus le goulot se trouve à deuxniveau : à l'envoi (LANtoWAN) et à la reception (WANtoLAN) donc les paquets dont


la transmission est rapides au niveau de WAN-WAN, seront ralentit sur la passerelled'arrivée.

Une alternative qui permettrait à priori de diminuer de façon considérable ce goulotd'étranglement (à 50%) et de favoriser une évolution plus rapide de l'application, seraitd'utiliser plusieurs passerelles par site suivant la charge du système.

� PrincipeL'approche ici consiste à ajouter des passerelles aux di�érents sites, suivant les besoinsen communication de l'application. Pour les applications de la classe C2 par exempleon utilisera seulement une passerelle par site (pour pouvoir béné�cier de l'éclatementdes connexions), et pour C1 et C3 on peut utiliser 2 ou 3 passerelles par site suivant letaux de communication. Chaque passerelle sera donc chargé de la retransmission desmessages d'une partie des n÷uds du site auquel elle est reliée. On prévoira égalementun équilibrage de charges entre les passerelles et théoriquement on pourra diminuer legoulot d'étranglement de 50% donc avoir une redistribution de messages plus rapide,et par conséquent diminuer le temps d'exécution des applications du type C1 et C2.Le principe est le suivant : On lance l'exécution de l'application avec une passerellepar site et on augmente le nombre de passerelles suivant le taux de communication.On aura un seuil de communication au dessus duquel on passera de 1 à 2 et de 2 à3 passerelles. On mettra également en place un protocole de communication entre lesn÷uds et les passerelles a�n d'indiquer aux n÷ud vers quelle passerelle il faut envoyerchaque paquet.

� AvantagesCette approche a le béné�ce de jumeler les avantages de l'utilisation de plusieursconnexions TCP sur le WAN et la diminution linéaire du goulot d'étranglement surles passerelles. En e�et elle optimisera l'utilisation de la bande passante entre les deuxpasserelles pour les communications collectives massives, et fera disparaitre le gou-lot d'étranglement au niveau des passerelles. Un autre avantage de cette méthodeest quelle aura un succès avec les exécutions à grande échelle dont sou�re à présentl'architecture MPI5000. On pourra donc avoir de bons résultats en augmentant pro-gressivement le nombre de passerelles en réponse à la charge du système.

2. Optimisation des opérations collectives Nous avons vu que les applications collec-tives, créent un goulot d'étranglement très fort au niveau de la passerelle par la taille etla quantité des paquets à retransmettre vers le WAN. Cette approche d'optimisation desdi�usions collectives à pour objectif d'améliorer le fonctionnement de la passerelle dansle cas di�usion des applications collectives a�n de diminuer le nombre de retransmissionsà faire pour une di�usion.

Il s'agit ici de diminuer le nombre de communications inter-site (WAN : plus couteux)pour la distribution d'un paquet en utilisant une opération collective en adaptant lescommunications des application à l'architecture de MPI5000. On voudrait donc quepour une opérations comme MPI_BCAST dans un groupe de 16 n÷uds répartis surdeux sites, on ait un seul message envoyé du site source vers le site distant au lieude 8 messages en direction de chacun d'un n÷ud du site distant. Cette approche nouspermettrait de gagner énormément en temps d'exécution en utilisant plus des connexionslocales qui sont moins couteux.

Une approche similaire est décrite dans l'article [JWL06], qui présente un ensembled'opérations collectives optimisées pour les grilles de calcul et une méthodologie d'or-ganisation du schéma de communication des applications suivant la topologie physique.


Les auteurs ont fait des expériences réalisées sur la plateforme Grid5000, avec 32 n÷udsdes clusters d'Orsay et Rennes. Les résultats obtenus on prouvé une grande diminutiondes communications inter-clusters et par conséquent une meilleurs performance des ap-plications. Des améliorations ont été constater avec toutes les 5 opérations collectivesréécrites. Pour une di�usion par exemple, au lieu d'envoyer log(p) messages inter-cluster,avec cette approche on envoi juste log(c). (p = nombre de processus et c = nombre decluster). Pour deux clusters on aura seulement 1 message inter-cluster envoyé.

L'idée utilisé ici est la même, mais l'architecture MPI5000 avec la présence des passerellesqui centralisent les communications rend un peu plus complexe sa mise en oeuvre surMPI5000.

Références

Articles

[AGTT03] David Ashton, William Gropp, Rajeev Thakur, and Brian Toonen. The CH3 designfor a simple implementation of adi-3 for MPICH with a TCP-based Implementa-tion. The International Journal of High Performance Computing Applications,September 2003.

[BBC07] Pascale Vicat-Blanc Primet. B. Bin Chen. Supporting bulk data transfers of high-end applications with guaranteed completion time. In The IEEE Computer So-ciety., 2007.

[BCC+06] Raphaël Bolze, Franck Cappello, Eddy Caron, Michel Daydé, Frédéric Desprez,Emmanuel Jeannot, Yvon Jégou, Stephane Lantéri, Julien Leduc, Noredine Me-lab, Guillaume Mornet, Raymond Namyst, Pascale Primet, Benjamin Quetier,Olivier Richard, El-Ghazali Talbi, and Touche Iréa. Grid'5000 : a large scaleand highly recon�gurable experimental Grid testbed. International Journal ofHigh Performance Computing Applications, 20(4) :481�494, Nov 2006. https:

//www.grid5000.fr/.

[BKL+07] J. Bresnahan, R. Kettimuthu, M. Link, D. Fraser, and I. Foster. GridFTP Pipeli-ning. TERAGRID Conference., 2007.

[BKM+04] J. Bªa»ewicz, M.Y. Kovalyov, M. Machowiak, D. Trystram, and J. We glarz. Sche-duling malleable tasks on parallel processors to minimize the makespan, Annals ofOperations Research. Annals of Operations Research, 129 :65�80, 2004.

[BSB+98] T. D. Brauny, H. J. Siegel, N. Beck, L. Bölöni, M. Maheswaran, and al. A taxonomyfor describing matching and scheduling heuristics for mixed-machine heterogeneouscomputing systems. 17th IEEE Symposium on Reliable Distributed Systems, pages330�335, 1998.

[BSB+01] Tracy D. Brauny, Howard Jay Siegely, Noah Becky, Ladislau, and al. A ComparisonStudy of Static Mapping Heuristics for a Class of Meta-tasks on HeterogeneousComputing Systems. Journal of Parallel and Distributed Computing, 61 :810�837,2001.

[C+07] Charlie Catlett et al. TeraGrid : Analysis of Organization, System Architecture,and Middleware Enabling New Types of Applications. In Ed. Lucio Grandinetti,editor, HPC and Grids in Action. IOS Press 'Advances in Parallel Computing'series, 2007.

[CC06] D. Lacamera C. Caini, R. Firrincieli. PEPsal : a Performance Enhancing Proxydesigned for TCP satellite connections. In IEEE 63rd Vehicular Technology Confe-rence (VTCSpring06), May 2006.

53

https://www.grid5000.fr/

https://www.grid5000.fr/

ARTICLES 54

[Dro96] M. Drozdowski. Scheduling Multiprocessor tasks � an overview. European JournalOf Operational Research, 94 :215�230, 1996.

[EKBO08] Moshe Dror y Edmund K. Burke and James B. Orlinz. Scheduling malleabletasks with interdependent processing rates : Comments and observations. DiscreteApplied Mathematics, 156(5) :620�626, 2008.

[FB89] D. Fernandez-Baca. Allocating modules to processors in a distributed system.IEEE Transactions on Software Engineering, Vol. SE-15, No. 11 :1427�1436, Nov1989.

[FHG04] S. Floyd, T. Henderson, and A. Gurtov. The NewReno Modi�cation to TCP'sFast Recovery Algorithm. RFC2582, 2004.

[FK99] Ian Foster and Carl Kesselman. The Grid : Blueprint for a New Computing Infra-structure. Morgan Kaufmann Publishers, 1999.

[FY02] Ahmad Faraj and Xin Yuan. Communication Characteristics in the NAS ParallelBenchmarks. In IASTED PDCS, pages 724�729, 2002.

[GBD+94] Al Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Bob Manchek, andVaidy Sunderam. PVM : Parallel Virtual Machine-A User's Guide and Tutorialfor Network Parallel Computing. MIT Press, 1994.

[GJG+05] Fabrizio Gagliardi, Bob Jones, François Grey, Marc-Elian Bégin, and Matti Heik-kurinen. Building an infrastructure for scienti�c Grid computing : status andgoals of the EGEE project. Philosophical Transactions of the Royal Society A :Mathematical, Physical and Engineering Sciences, pages 1729�1742, 2005.

[GLDS96] William Gropp, Ewing Lusk, Nathan Doss, and Anthony Skjellum. High-performance, portable implementation of the MPI Message Passing Interface Stan-dard. Parallel Computing, 22(6) :789�828, 1996.

[Gro02] William Gropp. MPICH2 : A New Start for MPI Implementations. In RecentAdvances in PVM and MPI : 9th European PVM/MPI Users' Group Meeting,Linz, Austria, Oct. 2002.

[Hoc96] D. Hochbaum. Approximation Algorithm for NP-Hard Problems. September 1996.

[IFT02] Carl KESSELMAN Ian FOSTER and Steve TUECKE. The Anatomy of the Grid :Enabling Scalable Virtual Organizations. International Journal of SupercomputingApplications., 2002.

[IK77] O. H. Ibarra and C. E. Kim. Heuristic algorithms for scheduling independent taskson nonidentical processors. Journal of the ACM, Vol. 24, No. 2 :280�289, Nov 1977.

[JWL06] P. Ji, Yongzhong Wu, and Haozhao Liu. A solution method for the quadraticassignment problem (qap). The Sixth International Symposium on OperationsResearch and Its Applications, 2006.

[KCK99] Ian FOSTER Karl CZAJKOWSKI and Carl KESSELMAN. Resource Co-Allocation in Computational Grids . In The Eighth IEEE International Symposiumon High Performance Distributed Computing (HPDC-8)., pages 219�228, 1999.

[LMR05] H. Casanova L. Marchal, Y. Yang and Y. Robert. A Realistic Network/ApplicationModel for Scheduling Divisible Loads on Large-Scale Platforms. Proc. 19th Int'lParallel and Distributed Processing Symp (IPDPS '05)., page 48b, April 2005.

[Miu06] Kenichi Miura. Overview of Japanese science Grid project NAREGI. Progress inInformatics, Volume 3, 2006.

SITES WEB 55

[MYH+01] S. Moh, C. Yu, D. Han, H. Y. Youn, and B. Mapping strategies for switch-basedcluster systems of irregular topology. 8th International Conference on Parallel andDistributed Systems, pages 733�740, June 2001.

[OSD01] J.M. Orduña, F. Silla, and J. Duato. A new task mapping technique for commu-nicationaware scheduling strategies. 30th Int'lWorkshops on Parallel Processing(ICPP)., pages 349�354, September 2001.

[PCL95] J.K Lenstra P. Chretienne, E.G Co�man and Z. Liu. Scheduling Theory and ItsApplications. 1995.

[STWF03] M. Gardner. S. Thulasidasann W Feng. Optimizing GridFTP through DynamicRight-Sizing. US Department of Energy., 2003.

[TBS00] M. Scheidegger T. Braun, H. Joachim Einsiedler1 and G. Stattenberger. A Li-nux Implementation of a Di�erentiated Services Router. INTERWORKING'2000,2000.

[TJM10] Brian Tierney and ESnet. Joe Metzger. High Performance Bulk Data Transfer.Joint Techs, Columbus OH., July 2010.

[VKM02] D. Velenis, D. Kalogeras, and B. Maglaris. SaTPEP : a TCP Performance Enhan-cing Proxy for Satellite Links. In 2nd International IFIPTC6 Networking Confe-rence, May 2002.

Sites Web

[DAS] DAS-3 : Distributed ASCI Supercomputer 3. http://www.cs.vu.nl/das3/.

Standards et RFCs

[BKG+01] J. Border, M. Kojo, J. Griner, G. Montenegro, and Z. Shelby. Performance enhan-cing proxies intended to mitigate link-related degradations. RFC3135, June 2001.http://www.isi.edu/in-notes/rfc3135.txt.

[Ins81] Information Science Institute. Transmission control protocol. RFC793, September 1981.http://tools.ietf.org/html/rfc793.

[Lab03] Argonne National Laboratory. GridFTP : Protocol Extension to FTP for the Grid. GFD-R-P.020, April 2003. http://www.ggf.org/documents/GWD-R/GFD-R.020.pdf.

[MPI09] MPI standard 2.2, Septembre 2009. http://www.mpi-forum.org/docs/mpi-2.2/mpi22-report.pdf

.

[Ope] OpenMP API speci�cation. http://www.openmp.org/mp-documents/spec30.pdf.

Rapports de recherche

[CHC08] Camille Codi, Thomas Herault, and Franck Cappello. Mpi applications on grids :a topology aware approach. 2008.

[HGM+09] Ludovic Hablot, Olivier Glück, Jean-Christophe Mignot, Romaric Guillier, Sé-bastien Soudan, and Pascale Vicat-Blanc Primet. Interaction between mpi andtcp in grids. 2009.

[LPP05] Sébastien Lacour, Christian Pérez, and Thierry Priol. Description and packagingof mpi applications for automatic deployment on computational grids. 2005.

http://www.cs.vu.nl/das3/

http ://www.isi.edu/in-notes/rfc3135.txt

http://tools.ietf.org/html/rfc793

http://www.ggf.org/documents/GWD-R/GFD-R.020.pdf

http://www.mpi-forum.org/docs/mpi-2.2/mpi22-report.pdf

http://www.openmp.org/mp-documents/spec30.pdf

THÈSES 56

[SCBPVB08] Sebastien Soudan, Christian Cadéré, Dominique Barth, and Pascale PrimetVicat-Blanc. Dynamic bandwidth provisioning and malleable bulk data transferscheduling. 2008.

Thèses

[Fre05] Wagner Frederic. Redistribution de données à travers un réseau à haut débit. PhDthesis, Universite Henri Poincare Nancy 1, 2005.

[Hab09] Ludovic Hablot. Réseau longue distance et application distribuée dans les grilles decalcul : étude et propositions pour une interaction e�cace. PhD thesis, Ecole NormaleSupérieure de Lyon, 2009.

[JEA07] Emmanuel JEANVOINE. Intergiciel pour l'exécution e�cace et �able d'applicationsdistribuées dans des grilles dynamiques de très grande taille. PhD thesis, INRIA -Équipe-Projet PARIS, 2007.

Appendices

57

Annexe A

Algorithmes

58

ANNEXE A. ALGORITHMES 59

Algorithm 2: Placement des tâches aux noeuds

/* Lecture des données des fichiers */

int n = nodeInput.getInt();range Task = 1..n;int nodeCost[Task,Task];int taskCom[Task,Task];/* Lecture de la matrice des distances Di,j entre noeuds */

for i in Task dofor i in Task do

nodeCost[i,j] = nodeInput.getInt();end

end/* Lecture des taux de communications Wi,j entre tâches */

for i in Task dofor i in Task do

taskCom[i,j] = taskInput.getInt();end

endSolver<CP> cp();/* Placement des tâches */

var<CP>int place[Task](cp,Task);/* Controleur Brand and Bound */

cp.setSearchController(BDSController(cp));/* L'objectif: minimisation de coefficient */

minimize<cp>;sum(i in Task, j in Task) taskCom[i,j] * nodeCost[place[i],place[j]];/* Contrainte */

subject to cp.post(alldi�erent(place));/* Propagation: Méthode gouton */

using while ( !bound(place) doselectMax (i in Task : !place[i].bound(), j in Task) (taskCom[i,j]);tryall <cp> (s in Task : place[i].memberOf(s));by (min(l in Task : place[j].memberOf(l) and l != s) nodeCost[s,l]);cp.post(place[i] == s);

end


Algorithm 3: Algorithme de la librairie

/* Interception of bind, connect, accept, poll, read, write */

/* Bind(in: fd_ecoute, in: ports,n,p) */socktfd=ConnectToGw();/* Create the direct socket and maintain a table of socket descriptors */

sockfd_direct = Direct_bind();insert(SOCKTABLE, sockfd, sockfd_direct, sockind);sockind++;

/* Connect(in: ipx,y, in: portx,y,z) */

if connect distant thenfdl = ConnectToGw();fdLibre = rechercheFd();listeFd[fdLibre] = x, y, z;len = 4 + 4 + 4 ; /* 1 indicate a propagated connect */

write(fdls,n,p, x, y, z + 1 + len + s, n, p + ips,n + ports,n,p);/* Connect to the distant node via the direct socket and maintain a

table of connected socket descriptors */

fdl_direct = direct_connect();insert(FDTABLE, fdl, fdl_direct, fdind);fdind++;return fdLibre;

else/* local connection */

return connect();end

/* Accept(in: fd_ecoute, out: addr_cli) *//* accept is realised even for a distant connect but this socket will

never be used */

if accept distant thenfd = accept();dest = read(fd);write(fd, fd_port);/* Accept distant connection from node via the direct socket and

maintain a table of connected socket descriptors */

fdl_direct=direct_accept();insert(FDTABLE, fdl, fdl_direct, fdind);fdind++;return fd;

elsereturn accept();

end



Algorithm 4: Nodes algorithm (following)

/* Read(in: fd) */if fd in listeFd then

/* distant connection: reading on fdls,n,p */

fdl,fdl_direct = �ndFD(FDTABLE,fd) ; /* Find ready data on both sockets

*/

select(fdl,fdl_direct) ; if isset fdl then/* Read from the gateway */

if full[fd] then full[fd] = false;return data[fd];x',y',z' = �ndId(fd);repeat

len = read(4);x,y,z + data[fdlx,y,z) = read(fdls,n,p, len)

until x',y',z' 6= x,y,z ;full[fd] = false;return data[fdlx,y,z]

end/* Read from the direct connection */

return read(fdl_direct)else

return read(fd)end

/* Write(in: fd) */if fd dans la table then

/* distant connection: writing on fdls,n,p */

fdl,fdl_direct = �ndFD(FDTABLE,fd);/* Get the message type */

msgtype=GetMsgtype(fdl,data);if msgtype 6= collectif then

/* Read from the gateway */

x,y,z=�ndId(fd);return write(fdls,n,p, x,y,z + (len + 4) + s,n,p + data)

end/* Read from the direct connection */

return write(fdl_direct)else

return write(fd)end

/* Close(in: fd) */if fd in listeFd then

/* distant connection */

listeFd[fd]=0;nbFd�;fdl,fdl_direct = �ndFD(FDTABLE,fd);close(fdl_direct);if nbFd = 0 then close(fdls,n,p)

elseclose(fd);

end

Documents

Execution Efficace d'une Application de Calcul Distribué sur une Grille de Calcul