Tˆaches divisibles pour plates-formes à grande échelle

Télécharger le fichier original (Mémoire de fin d’études)

Modèles et travaux précédents

Dans cette partie, nous étudions les différents modélisations de plates-formes qui ont déjà et´ proposées, en discutant leurs avantages et leurs inconvénients, puis nous décrivons les modèles que nous utiliserons dans ce manuscrit.

Modèles homogènes

Dans le modèle utilisé par Bertsimas et Gamarnik pour étudier le routage de messages, le transfert d’un message sur une arˆete du graphe de communication prend un temps unité, et toutes les arˆetes peuvent ˆetre utilisées simultanément. Au contraire, dans le ✓modèle du téléphone✔(ou telephone call model ), un processeur ne peut participer qu’à une seule communi-cation, soit en tant qu’émetteur, soit en tant que récepteur. Ce modèle est homogène car toutes les communications prennent un temps unité. Elaborer un ordonnancement pour un ensemble de communications dans ce modèle revient à trouver un ensemble de couplages entre les nœuds du graphe. C’est par exemple ce que font Khuller et al. [67] pour des problèmes de communications collectives.
Des modèles plus elaborés ont et´ imaginés pour prendre en compte les différents paramètres intervenant dans la modélisation des machines parallèles. On peut citer le modèle LogP [46, 45], et son extension LogGP au messages de grande taille [3].
Ces modèles homogènes ont permis d’étudier l’ordonnancement de communication sur des topologies structurées, comme les grilles ou les tores a` n dimensions, et les hypercubes [97, 59].
Les algorithmes de communications collectives de l’implantation MPICH du standard MPI s’appuient également sur une modélisation homogène des grappes de calcul, prenant en compte latence et bande-passante et faisant une distinction entre les messages de petite taille (pour lesquels la latence est prépondérante) et les messages de grande taille [95].

Modèles hétérogènes

Les modèles homogènes ont ensuite et´ adaptés pour prendre en compte l’hétérogénéit´ des réseaux d’interconnexion. Une variante hétérogène du modèle LogP a et´ proposée : le modèle LogP paramétr´ [68], qui possède de nombreux paramètres difficiles a` mesurer.
Banikazemi et al. [8] introduisent un modèle simple dans lequel l’hétérogénéit´ est caracté-risée par des temps d’envoi de messages différents pour chaque processeurs. Dans ce modèle, le réseau d’interconnexion est un graphe complet, chaque processeur Pi envoie un message en un temps ti a` n’importe quel autre processeur. Les auteurs expliquent que ce modèle simple d’hétérogénéit´ suffit a` décrire les différents coˆuts de communication dans une grappe hét´-rogène. Les communications collectives, et en particulier la diffusion, ont et´ etudiées avec ce modèle [58, 77, 76].
Ce modèle de coˆut de communication a aussi et´ utilisé pour étudier des réseaux constitué de deux types de nœuds : les commutateurs du réseau (ou switch) et les processeurs. Dans ce cas, on suppose qu’une communication entre deux processeurs occupe tous les liens sur la route entre ces processeurs (routage wormhole). Des résultats ont eté obtenus pour les communications collectives sous ce modèle [74, 75].
Un autre modèle de communication est encore introduit dans [31, 30] pour les communi-cations collectives : le temps nécessaire au transfert d’un message entre Pi et Pj est composé d’une latence fixe Ti,j et d’une partie dépendant de la taille m du message . Dans le cas de la diffusion et de nombreuses autres communications collectives, la taille des messages est la mˆeme, le temps de communication d’un message de Pi à Pj est donc Ci,j = Ti,j + m .

Modèles multi-port

Les modèles précédents sont une généralisation au cas hétérogène du modèle du téléphone, en ce qu’ils n’autorisent un processeur a` communiquer qu’avec un seul autre processeur a` un instant donné. On leur donne la caractéristique de modèle un-port, en considérant qu’une machine possède un seul port pour gérer les communications. Il existe également des modèles multi-port qui supposent que plusieurs communications peuvent avoir lieu simultanément sur le mˆeme processeur, sous certaines contraintes.
Dans le modèle proposé par Banikazemi et al. [9], le coˆut d’une communication d’un message de taille L du processeur Pi au processeur Pj ˆetre décompos´ en trois parties consécutives : sendi,j + Ti,j (L) + recvi,j
L’occupation du processeur émetteur, du lien de communication, et du processeur récepteur est représentée sur la figure 1.1(a). Le processeur émetteur Pi est en particulier occupé pendant sendi,j unités de temps, mais peut ensuite commencer une autre émission de message alors que le premier transfert n’est pas termin´.
Bar-Noy propose un modèle très proche de celui de Banikazemi dans [11]. La seule différence est le recouvrement entre les différentes parties du temps de transfert du message, qui correspond a` la figure 1.1(b) : ici, le lien de communication est occupé pendant tous le transfert, alors que dans le modèle précédent, il n’était occupé qu’après le temps d’initialisation sendi,j par le processeur émetteur et avant le temps de finalisation recvi,j par le récepteur.
A. Rosenberg propose également un modèle décomposant l’envoi d’un message en plusieurs partie, prenant en compte le processeur émetteur, les interfaces de communication et le pro-cesseur récepteur dans [85, 1]. Cependant, la complexit´ d’un tel modèle rend délicat l’analyse d’ordonnancements.
B. Hong et V. Prasanna proposent dans [63] un modèle beaucoup plus simple pour le multi-port : dans leur modèle multi-port borné, un nombre illimité de transferts de messages peuvent coexister sur un mˆeme lien, ou ˆetre initiés par un mˆeme processeur, pourvu que des contraintes de capacités soient respectées : la bande-passante totale sur un lien est limitée, de mˆeme que la bande-passante totale en entrée ou en sortie d’un processeur, ce qui correspond a` la limitation de l’interface réseau de chaque machine.

Autres travaux précédents

Les principaux travaux théoriques d’optimisation de communications collectives sur les mo-dèles homogènes, hétérogènes et multi-port ont et´ cités dans les parties précédentes. Il convient néanmoins de citer quelques autres travaux se rapportant a` notre étude.
Techniques d’optimisation. Les techniques d’optimisation par programmation linéaire que nous utilisons sont principalement inspirées par l’étude de Bertsimas et Gamarnik présent´ dans la partie précédente. Nous utilisons également au chapitre 7 une technique d’arrondi d’une solution rationnelle d’un programme linéaire vers une solution entière qui s’inspire des travaux de Coudert et Rivano [44]. Bar-Noy et al.[12] proposent également une technique d’arrondi vers une solution entière pour l’ordonnancement de tˆaches avec date d’arrivée et date limite d’exécution.
L’utilisation concurrente de plusieurs arbres afin d’optimiser le débit d’une diffusion a d’abord et´ etudiée sur les topologies homogènes. On peut par exemple citer le cas de l’hyper-cube de dimension n, dans lequel on peut construire n arbres couvrant arˆetes-disjoints enracinés en un processeur, ce qui permet une diffusion très efficace. Plus récemment dans le contexte des réseaux pair-a`-pair, ce principe a et´ utilisé dans Splitstream [38], en cherchant a` minimiser l’occupation des nœuds et leur degr´ sortant, afin de maximiser le débit de la diffusion. L’étude utilisant ce principe d’arbres de diffusion concurrents qui est la plus proche de la notre est sans doute celle de den Burger et al.[32], qui utilise plusieurs arbres pour effectuer une diffusion sur des grilles de calcul. Remarquant que le nombre d’arbres de diffusion a` considérer est exponen-tiel, les auteurs de cette étude commencent par sélectionner un ensemble d’arbres intéressants, générés par plusieurs heuristiques de recherche d’arbre de meilleur débit. Ils utilisent ensuite cet ensemble restreint d’arbres d’une fa¸con très proche de la notre, en écrivant un programme linéaire qui a pour variables les débits des différents arbres, et pour contraintes les limitations de bande-passante mesurées dans le réseau. Ces travaux sont validés par des expérimentations, montrant que le débit total obtenu par leur implantation est supérieur a` celui des bibliothèques de communication actuelles.
Bibliothèques de communication. Il existe de nombreuses bibliothèques de communication implantant des primitives de communications collectives, plus ou moins adaptées a` un environ-nement hétérogène.
PVM est une bibliothèque de communication populaire [52], mais elle ne comprend que peu de communications collectives. Leur implémentation est laissée a` la charge du programmeur, qui peut ainsi les adapter a` l’environnement de calcul qu’il vise, mais ceci représente une grosse charge de travail.
Standard MPI Il définit précisément de nombreuses primitives de communications. Une im-plémentation récente, nommée MPICH-G2 [64] est adaptée a` un environnement de calcul distribué, de type grille : on commence par regrouper les nœuds de calcul qui sont sur les mˆemes sous-réseaux en se basant sur leurs possibilités de communication, puis on utilise ce découpage en niveaux pour une effectuer les communications de fa¸con hiérarchique, d’abord entre les sous-réseaux différents, puis ensuite a` l’intérieur d’un mˆeme sous-réseau. Cependant la segmentation des messages en vue d’un pipeline des opérations est toujours en projet pour une prochaine version.
ECO est une bibliothèque dédiée aux communications collectives sur environnement hétérogène [78]. Comme la précédente, elle commence par regrouper les machines en sous-réseaux (proches des réseaux locaux) en mesurant la latence entre deux machines, puis effectue également un traitement hiérarchique sur ces deux niveaux. A l’intérieur des sous-réseaux, le traitement est différenci´ selon les caractéristiques de ceux-ci, ce qui conduit par exemple à des arbres de diffusion de largeur différente selon le type de réseau.
MagPIe est une autre bibliothèque qui implémente des communications collectives pour MPI sur un environnement hétérogène [69]. De la mˆeme fa¸con que les précédentes, elle utilise un traitement en couches. La limitation a` deux couches est justifiée par le fait que les communications longue-distance apportent toujours une latence importance et que le gain d’une approche avec plus de couches, par exemple dans le cas d’un ensemble de grappes de machines parallèles (donc a` 3 niveaux), est négligeable devant la latence incompres-sible d’un transfert sur un lien longue-distance. Les auteurs cherchent donc a` effectuer le minimum de transferts sur ce type de lien, et obtiennent ainsi des gains significatifs par rapport a` l’implémentation commune MPICH.

Choix d’un modèle

Le choix d’un modèle de communication résulte d’un compromis entre réalisme, instanciabi-lité et maniabilité pour la conception d’algorithmes. Le modèle de Rosenberg est probablement très proche de la réalité, mais très difficile a` instancier, et concevoir des algorithmes pour des schémas de communications complexes parait extrˆemement difficile dans ce modèle. En re-vanche, le modèle homogène du téléphone, sans difficulté d’instanciation, manque cruellement de réalisme pour les plates-formes que nous voulons étudier. Cependant, le fait que l’optimisa-tion du temps de diffusion d’un message soit NP-complet dans ce modèle met en évidence le caractère intrinsèquement difficile de cette opération.
Le modèle multi-port borné utilisé par Hong et Prasanna [63] paraˆıt intéressant car très simple, mais ne nous semble pas assez réaliste en ce qui concerne l’existence de plusieurs trans-ferts simultanés : Saif et Parashar [86] ont montré que les envois asynchrones de MPI étaient effectués de fa¸con sérialisée dès que la taille des données excédait quelque méga-octets, et ce pour deux implémentations populaire de MPI : MPICH et le MPI d’IBM sur le SP2. Nous pré-férerons donc utiliser des modèles un-port, mais nous utiliserons occasionnellement ce modèle multi-port.
Modèles utilisés dans ce manuscrit
Nous utiliserons par la suite principalement deux variantes du modèles un-port hétérogène, sans latence : les modèles un-port bidirectionnel avec recouvrement, et un-port unidirectionnel avec recouvrement.
Nous considérons que la plate-forme est modélisée par un graphe G = (V, E) dont les sommets sont des machines, assimilées a` des processeurs. Nous notons Pi les sommets de V , et nous préférerons souvent la notation (i, j) a` la place de (Pi, Pj ) pour désigner les arˆetes du graphe, afin de ne pas alourdir les notations.
Dans tous les cas, nous choisissons de modéliser la durée du transfert d’un message de taille N entre les processeurs Pi et Pj par N × ci,j , o`u ci,j représente l’inverse de la bande passante du lien de communication (i, j), c’est-a`-dire le temps nécessaire a` la transmission d’un message de taille unité sur le lien (i, j)
Dans le modèle un-port bidirectionnel avec recouvrement, l’interaction entre différentes com-munications simultanées est modélisée comme suit :
– Si le processeur Pi commence au temps t a` envoyer un message de taille N au processeur Pj , alors il ne peut initier une autre émission avant la fin de la communication, c’est-a`-dire avant t + N × ci,j , et le processeur Pj ne peut commencer a` recevoir un autre message avant cette date (modèle un-port ).
– Par contre, pendant ce temps, le processeur Pi peut tout a` fait recevoir un message d’un autre processeur, et Pj peut également envoyer un message a` un autre processeur (modèle bidirectionnel ). On peut imaginer que cela représente un processeur muni de deux ports de communication, un pour les envois et un pour les réceptions.
– Pendant la durée de la communication, Pi et Pj peuvent continuer leur activité de cal-cul sans ˆetre ralenti par la communication (recouvrement total entre les calculs et les communications).
Dans le modèle un-port unidirectionnel avec recouvrement, on considère qu’il n’y a qu’une seule interface de communication pour chaque processeur, en charge des communications sor-tantes et entrantes. Ainsi un processeur Pi ne peut pas simultanément envoyer un message a` un processeur Pj et recevoir un message d’un processeur Pk , mais ces communications doivent ˆetre sérialisées.
Calculs Pour étudier des problèmes mˆelant communications et calculs, nous modélisons le temps d’exécution d’une tˆache T sur un processeur Pi par zi × δT , o`u zi est le temps de calcul d’une tˆache de taille unitaire sur le processeur Pi, et δt est la taille de la tˆache T .
Latence Bien que la latence puisse ˆetre un paramètre important sur les réseaux de commu-nication, notre modèle ne la prend pas en compte. Nous faisons ce choix principalement afin de pouvoir concevoir des algorithmes de communication de débit optimal. Cependant, pour des séries d’un grand nombre de mˆeme opérations, tous les messages ont une mˆeme taille, qui est fixée par l’application, et non par l’ordonnancement : par exemple dans le cas de tˆaches indé-pendantes, si un ordonnancement décide d’envoyer trois tˆaches sur un mˆeme lien, ces envois seront effectués de manière séquentielle, et la latence devra elle aussi ˆetre comptée trois fois. Dans ce cas, nous supposons que le coˆut ci,j de transmission d’un message sur cette arˆete prend déjà en compte cette latence. Comme nous supposons que la granularité des messages est fixée par l’application, nous pouvons rassembler les différents composants du coˆut de communication (latence, bande-passante) dans ce seul paramètre ci,j .
Autres modèles utilisés Nous utiliserons également le modèle multi-port borné dans le cha-pitre 5, que nous présenterons a` cette occasion. D’autre part, nous étudierons au chapitre 7 l’ordonnancement d’applications sur une plate-forme distribuée organisée comme une collection de grappes de calcul, et nous élaborerons a` cette occasion un modèle plus spécifique.

Contribution et résum´ des résultats obtenus

La principale contribution de cette thèse est le développement d’un cadre général d’étude pour l’ordonnancement en régime permanent sur plates-formes hétérogènes. Nous présentons ce schéma général en l’utilisant pour étudier diverses opérations de communications collectives (diffusion, multicast, distribution, réduction, calcul des préfixes) selon plusieurs modèles de communication (un-port mono- et bi-directionnel, multi-port borné). Nous avons pu d’une part établir la complexit´ des différentes primitives etudiés selon différents modèles de communi-cation, et d’autre part concevoir des algorithmes efficaces pour résoudre ces problèmes dans certains cas (modèle de communication un-port bidirectionnel).
Dans la suite de cette partie, nous résumons les différents résultats obtenus au cours de cette thèse.

Communication collectives en régime permanent

On s’intéresse ici aux communications induites par l’exécution d’une application distribuée sur une plate-forme de calcul hétérogène. Ces communications peuvent souvent ˆetre rassemblées sous la forme de primitives de communications collectives, comme par exemple la diffusion de données : une des machines transmet a` toutes les autres une copie d’une donnée qu’elle possède. Pour qu’une application ✓mérite✔d’ˆetre exécutée sur une plate-forme a` grande échelle, il est probable que le volume de données a` communiquer soit important. Pour effectuer ces transferts d’importants volumes de données, nous les découpons en une série d’un grand nombre de communications de taille plus modeste : la diffusion d’une donnée de grande taille sera alors transformée en une série d’un grand nombre de diffusion de messages de petite taille, que l’on cherche a` effectuer de fa¸con pipelinée.
Les différents schémas de communications collectives que nous étudions sont les suivants : Distribution de données Un processeur Psource distribue p données à un ensemble Vcibles de p processeurs, chacun recevant une donnée différente.
Diffusion de données La plus commune des opérations de communications collectives : un processeur Psource doit communiquer une mˆeme valeur a` tous les autres processeurs de la plate-forme.
Diffusion restreinte Plus générale que la précédente : un processeur Psource doit communiquer une mˆeme valeur a` un sous-ensemble Vcibles des processeurs de la plate-forme.
Réduction On définit un ensemble de processeurs participants R = {Pr1 , . . . , PrN }. Chaque processeur Pi de cet ensemble possède une valeur vi, obtenue par exemple comme résultat d’un calcul local. On cherche a` calculer la réduction v1 ⊕ v2 ⊕ • • • ⊕ vN , o`u ⊕ est une opération associative et non-commutative. Le résultat doit au final se trouver sur un seul processeur cible Pcible.
Calcul de préfixes Comme pour la réduction chaque processeur participant Pri ∈ R possède une valeur vi. On cherche à ce que chaque processeur Pri connaisse la réduction partielle v1 ⊕ v2 ⊕ • • • ⊕ vi (en particulier PrN doit connaˆıtre le résultat de la réduction totale). De mˆeme que pour la réduction, ⊕ est une opération associative et non-commutative.
Pour chacun de ces schémas de communication, nous nous intéressons à la version pipelinée du problème. Par exemple dans le problème ✓série de distributions de données✔, on considère que le processeur source possède N × p valeurs ai,j (i = 1 . . . p, j = 1 . . . N ), qu’il doit distri-buer de telle sorte que Pi re¸coive les valeurs ai,1, . . . ai,N . Dans notre étude, nous considérons que le nombre N d’opérations dans la série est grand, et nous nous intéresserons surtout au comportement asymptotique quand N tend vers l’infini.
D’autre part, comme nous considérons toujours le problème d’une série d’un mˆeme schéma de communication, nous ne préciserons plus ✓série de distribution de données✔, mais nous parlerons simplement du problème de distribution de données, de mˆeme pour les autres problèmes.
Les résultats obtenus pour l’étude des communications collectives pipelinées, présentés dans la première partie de ce manuscrit, sont les suivants :
– Pour les modèles un-port unidirectionnel et bidirectionnel, nous montrons qu’un ordon-nancement réalisant le débit optimal peut ˆetre décrit de fa¸con compacte, c’est-à-dire sous la forme d’un ensemble pondér´ de schémas d’allocation et d’un ensemble pondér´ de couplages de communications, et ce quelque soit le problème considéré (chapitres 2 et 3).
– Pour le modèle un-port unidirectionnel, nous montrons que la complexit´ des problèmes de diffusion, de distribution de données et de réduction est polynomiale (chapitre 3). Cette méthode s’appuyant sur la méthode d’optimisation d’un programme linéaire par la méthode des ellipso¨ıdes, elle ne fournit par pour autant d’algorithme efficace en pratique pour résoudre ces problèmes.
– Pour le modèle un-port bidirectionnel, nous proposons des algorithmes efficaces pour ré-soudre le problème de la diffusion, de la distribution de données, et de la réduction. Nous montrons également que la diffusion restreinte et le calcul parallèle des préfixes sont des problèmes NP-complets, et que ces résultats de NP-complétude s’étendent au modèle un-port unidirectionnel (chapitre 4).
– Nous avons illustré ces résultats par des simulations pour le problèmes de la réduction (partie 4.3 du chapitre 4), et par des expérimentations sur des plates-formes réelles pour la diffusion (chapitre 5).
Ces différents travaux sur les communications collectives ont fait l’objet des publications [1, 3, 5, 13, 15, 16, 17].

Tˆaches indépendantes et graphes de tˆaches en régime permanent

Nous avons également etudié des problèmes d’ordonnancement plus classiques sous l’angle de l’optimisation du débit en régime permanent. Nous avons en particulier etudié l’exécution de tˆaches indépendantes sur plate-forme hétérogène, pour lequel nous sommes également capables de calculer le débit optimal, et de décrire un ordonnancement réalisant ce débit.
Il était ensuite naturel de vouloir prendre en compte des tˆaches avec dépendances, c’est pourquoi nous nous sommes intéressés a` l’exécution d’une série de graphes de tˆaches. Nous avons montré que dans le cas général, le calcul du débit optimal pour ce problème est NP-complet. Cependant, pour le cas particulier des graphes de tˆaches avec une profondeur de dépendance bornée, nous sommes capables de calculer le débit optimal et de reconstruire un ordonnancement qui le réalise.
Ces travaux, sur les tˆaches indépendantes et les graphes de tˆaches, ont et´ réalisés en colla-boration avec Arnaud Legrand, et ont et´ présentés en détail dans son manuscrit de thèse [72], ainsi que dans l’Habilitation a` diriger des recherches d’Olivier Beaumont [15]. Nous ne repro-duirons donc pas ces résultats ici, préférant nous concentrer sur l’étude des communications collectives.
Ces travaux ont fait l’objet des publications [4, 6, 18, 20].

Extension aux applications multiples

Nous nous sommes également intéressés à l’ordonnancement pour des plates-formes de cal-cul distribuées à grande échelle. Les applications utilisant de telles plates-formes présentent en général un fort degr´ de parallélisme, demandent une grande puissance de calcul et un temps d’exécution assez long. Ce sont donc de très bons candidats pour la mise en pratique des tech-niques d’ordonnancement fondées sur l’optimisation du régime permanent. D’autre part, une caractéristique de ces plates-formes est que leur puissance est partagée entre plusieurs applica-tions concurrentes. Nous présentons deux études de cas pour l’ordonnancement d’applications multiples sur de telles plates-formes.
– Nous étudions dans un premier temps l’ordonnancement de plusieurs applications compo-sées de tˆaches indépendantes sur une plate-forme de type ✓maˆıtre-esclaves✔. Nous étudions l’éventualit´ d’un ordonnanceur centralisé, en montrant comment calculer le débit opti-mal et construire un ordonnancement périodique qui le réalise. Nous proposons également des méthodes heuristiques pour élaborer des ordonnanceurs décentralisés. Ces travaux, présentés au chapitre 6, font l’objet de la publication [12].
– Dans un second temps, nous abandonnons le modèle de plate-forme en ✓maˆıtre-esclaves✔ pour élaborer un modèle de plate-forme distribuée prenant en compte les spécificités des réseaux d’interconnexion des grilles de calcul. Sur ce modèle, nous étudions l’ordonnance-ment d’applications constituées de tˆaches divisibles. Après avoir montré que le problème d’ordonnancement correspondant est NP-complet, nous proposons des méthodes heuris-tiques pour le résoudre, que nous testons par simulation. Nous présentons ces travaux dans le chapitre 7, qui font également l’objet des publications [2, 7].

Autres problèmes d’ordonnancement abordés

Au cours de cette thèse, nous avons et´ amenés a` étudier d’autres problèmes d’ordonnance-ment. Comme ils s’écartent du thème principal de cette thèse, nous ne les détaillerons pas dans ce manuscrit.
Tˆaches indépendantes avec contraintes de mémoire Nous nous sommes intéressés à l’ordon-nancement de tˆaches indépendantes en présence de mémoire limitée : dans les travaux préc´-demment evoqués, nous supposons avoir à notre disposition sur chaque processeur une mémoire pouvant contenir une nombre illimité de tˆaches à traiter. Nous montrons que si cette hypo-thèse n’est pas vérifiée, alors un grand nombre de problèmes d’ordonnancement que l’on savait résoudre, en particulier l’optimisation du débit, deviennent NP-complets. Par contre, nous pré-sentons des résultats de simulation montrant que lorsqu’un seuil dans la taille de la mémoire est franchi, alors on peut espérer atteindre le débit optimal calculé sans contrainte de mémoire. Ces travaux font l’objet de la publication [14].
Tˆaches divisibles avec messages de retour Nous avons également apporté une contribution a` la théorie des tˆaches divisibles, en étudiant l’ordonnancement de telles tˆaches avec messages de retour. La plupart des études précédentes dans ce domaine prennent en compte les commu-nications impliquées par les données nécessaires aux calculs, mais pas les messages de retour contenant les résultats. Or il n’est pas rare que les résultats soient d’une taille comparable aux données, et doivent ˆetre rassemblés après le calcul. Nous montrons que prendre en compte les messages de retour rend les problèmes d’ordonnancement significativement plus difficiles. En particulier, nous exhibons le premier cas (à notre connaissance) d’ordonnancement optimal pour des tˆaches divisibles sous un modèle sans latence, o`u tous les processeurs ne prennent pas part au calcul.
Ces travaux font l’objet des publications [8, 10].
Ordonnancement pour les réseaux En collaboration avec l’équipe RESO du LIP, nous avons également etudié la réservation de ressources dans les réseaux d’interconnexion des grilles de calcul, en particulier pour les problèmes liés a` la contention des connexions au niveau de points d’entrée et de sortie du cœur du réseau. Nous montrons que le problème d’optimisation associé est NP-complet, et nous proposons des stratégies heuristiques pour le résoudre.
Ces travaux ont fait l’objet des publications [9, 11].
Pair-à-Pair En collaboration avec Anne-Marie Kermarrec et Etienne Rivière de l’IRISA, nous nous sommes intéressés à un tout autre sujet : l’élaboration d’un réseau pair-à-pair centr´ sur les objets, dans lequel chaque objet est décrit par un ensemble d’attributs. Les objets sont placés dans un espace euclidien. Ils sont liés de manière à ce que les objets avec des attributs proches soient eux-mˆemes proches dans le réseau. Ceci est réalisé par le calcul d’un diagramme de Vorono¨ı. De plus, des mécanismes de routage efficace de type ✓petit-monde✔généralisent le modèle de Kleinberg sur la grille à notre réseau. Cet ébauche de protocole est destinée à ˆetre le support de mécanismes de recherche complexes, comme des requˆtes par plage de valeurs.
Ces travaux ont fait l’objet de la publication [21].
En résumé, nous développerons dans ce manuscrit l’étude des communications collectives en régime permanent (de la partie 1.3.1), ainsi que l’étude de l’ordonnancement d’applications multiples (de la partie 1.3.3), en renvoyant aux publications pour les autres sujets abordés.

Table des matières

1 Introduction 
1.1 Ordonnancement en régime permanent
1.1.1 Routage de paquets
1.1.2 Intérˆet du régime permanent
1.2 Modèles et travaux précédents
1.2.1 Modèles homogènes
1.2.2 Modèles hétérogènes
1.2.3 Modèles multi-port
1.2.4 Autres travaux précédents
1.2.5 Choix d’un modèle
1.3 Contribution et résumé des résultats obtenus
1.3.1 Communication collectives en régime permanent
1.3.2 Tˆaches indépendantes et graphes de tˆaches en régime permanent
1.3.3 Extension aux applications multiples
1.3.4 Autres problèmes d’ordonnancement abordés
Première partie : Communications collectives 
2 Approche générale 
2.1 Structure des communications : schémas d’allocation
2.1.1 Pour la diffusion
2.1.2 Pour les autres primitives
2.2 Organisation des communications : schémas de communication
2.2.1 Contraintes pour les communications sous le modèle un-port unidirectionnel
2.2.2 Contraintes pour les communications sous le modèle un-port bidirectionnel
2.3 Construction d’un ordonnancement
2.3.1 Exemple de la diffusion sur une petite plate-forme
2.3.2 Généralisation
3 Méthodologie pour la résolution 
3.1 Résolution à base de programmation linéaire
3.1.1 Construction du programme linéaire
3.1.2 Existence d’une solution optimale compacte
3.1.3 Résolution à l’aide de la méthode de l’ellipso¨ıde
3.1.4 Application au différentes communications collectives
3.2 Découpler pour optimiser
3.2.1 Recherche de couplages sous le modèle bidirectionnel
3.2.2 Cas du un-port unidirectionnel
3.3 Conclusion
4 ´ Etude de cas pour le modèle un-port bidirectionnel 
4.1 Distribution de données
4.2 Diffusion
4.2.1 Recherche efficaces d’arbres de diffusion
4.2.2 Mise en oeuvre sur un petit exemple
4.3 Réduction
4.3.1 Programme linéaire
4.3.2 Extraction d’arbres de réduction
4.3.3 Expérimentations par simulation
4.4 Diffusion restreinte
4.4.1 Position du problème
4.4.2 Preuve de complexité
4.4.3 Extension au calcul des préfixes
4.5 Conclusion
5 Expérimentations : cas de la diffusion 
5.1 Adaptation pour le modèle multi-port
5.1.1 Modèles un-port et multi-port borné
5.1.2 Résolution pour le modèle multi-port
5.2 Heuristiques pour un arbre de diffusion
5.2.1 Heuristiques fondées sur des techniques de graphe
5.2.2 Heuristiques s’inspirant d’une solution du programme linéaire
5.3 Expérimentations
5.3.1 Méthodologie
5.3.2 Résultats et discussion
5.3.3 Poursuite des expérimentations
Seconde partie : Ordonnancement d’applications multiples 
6 Collections de tˆaches indépendantes en maˆıtre-esclaves 
6.1 Introduction
6.2 Modélisation de la plate-forme et des applications
6.3 Calcul de la solution optimale
6.3.1 Programme linéaire
6.3.2 Construction d’un ordonnancement périodique
6.3.3 Caractérisation pour une plate-forme en étoile
6.3.4 Prise en compte des messages de retour
6.4 Heuristiques décentralisées
6.4.1 Ordonnancement ✓à la demande✔
6.4.2 Heuristique ✓à la demande✔ reposant sur le programme linéaire (HPL)
6.4.3 Heuristique gloutonne simple (FIFO)
6.4.4 Heuristique mono-application à gros grain (MAGG)
6.4.5 Ordonnanceurs parallèles non-coopératifs (OPNC)
6.4.6 Heuristique décentralisée centrée sur les données (HDCD)
6.5 ´ Evaluation par simulation
6.5.1 Méthodologie
6.5.2 Résultats expérimentaux
6.6 Conclusion
7 Tˆaches divisibles pour plates-formes à grande échelle
7.1 Introduction
7.2 Modélisation de la plate-forme et des applications
7.2.1 Réseau d’interconnexion longue-distance
7.2.2 ´ Eléments de calcul
7.2.3 Applications
7.3 Solution optimale en régime permanent
7.3.1 Programme linéaire
7.3.2 Difficulté du problème d’optimisation
7.4 Heuristiques
7.4.1 Stratégie gloutonne par étapes (SGE)
7.4.2 Stratégies fondée sur le programme linéaire en rationnels
7.5 Simulations
7.5.1 Méthodologie
7.5.2 Résultats
7.6 Conclusion
8 Conclusion 
9 Bibliographie 
A Notations
B Liste des publications

Télécharger le rapport complet