Parallélisation de l'application Schur

et

Etude des méthodes de certi�cation

de résultats dans le cadre des

applications réparties

Arthur Guittet

22 août 2008

Table des matières

1 Présentation de l'environnement de stage : le LIPN 5

1.1 Présentation générale . . . . . . . . . . . . . . . . . . . . . . . 51.2 Les di�érentes équipes du LIPN . . . . . . . . . . . . . . . . . 51.3 L'équipe OCAD . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Introduction aux DesktopGrids et à BonjourGrid 7

2.1 Bref historique du développement informatique . . . . . . . . 72.1.1 L'évolution des technologies . . . . . . . . . . . . . . . 72.1.2 Les machines parallèles . . . . . . . . . . . . . . . . . . 8

2.2 Les grilles de calcul . . . . . . . . . . . . . . . . . . . . . . . . 82.2.1 Les di�érents modèles de déploiement . . . . . . . . . . 92.2.2 La plateforme BonjourGrid . . . . . . . . . . . . . . . 11

3 Portage d'une application : Schur 14

3.1 Le contexte mathématique : Fonctions de Schur et nombres deKotska . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.1.1 Diagrammes de Ferrer et tableaux de Young . . . . . . 143.1.2 Le calcul des nombres de Koskta par la méthode des

ruches . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Parallélisation de l'application . . . . . . . . . . . . . . . . . . 19

3.2.1 Présentation générale de l'algorithme . . . . . . . . . . 193.2.2 Mise en oeuvre des threads . . . . . . . . . . . . . . . . 20

4 Etude des méthodes de certi�cation de résultats dans le cadre

des applications réparties 24

4.1 La réplication de calculs . . . . . . . . . . . . . . . . . . . . . 254.1.1 Réplication et réputation . . . . . . . . . . . . . . . . . 254.1.2 Groupes de calcul et scheduling . . . . . . . . . . . . . 26

4.2 La réplication de calculs sur des machines �ables . . . . . . . . 274.3 L'intégration de quiz . . . . . . . . . . . . . . . . . . . . . . . 27

4.3.1 Principe théorique . . . . . . . . . . . . . . . . . . . . 27

1

4.3.2 Une méthode adaptative . . . . . . . . . . . . . . . . . 284.4 Intégration d'un service de certi�cation dans BonjourGrid . . 29

2

Table des �gures

2.1 Structure générale d'un réseau de type client-serveur. . . . . . 102.2 Structure générale d'un réseau de type Peer-to-Peer. . . . . . . 112.3 Schéma de fonctionnement général de BonjourGrid. . . . . . . 13

3.1 Augmentation du temps de calcul en fonction du facteur dedilatation et pour di�érentes partitions. Calcul réalisé sur unBi-AMD Opteron dual core cadencé à 2,8 GHz. . . . . . . . . 21

3.2 Evolution du temps d'exécution en fonction du nombre max-imum de threads autorisés, pour les deux ensembles de parti-tions : (λ = (5, 3, 2, 2, 1), µ = (4, 3, 2, 2, 1), ν = (7, 5, 4, 4, 3, 2))et (λ = (7, 6, 5, 4), µ = (7, 7, 7, 4), ν = (12, 8, 8, 7, 6, 4, 2)). . . . 23

3

Remerciements

Je souhaiterais remercier les personnes suivantes, qui m'ont guidé et soutenupendant toute la durée de mon stage :

Christophe Cérin,

Heithem Abbes,

Hazem Fkaier,

Jalila Sadki,

Hichem Kenniche.

4

Introduction

Les technologies informatiques ont évolué très rapidement dans les dixdernières années, donnant naissance à des machines de plus en plus perfor-mantes. L'apparition d'internet et la multiplication des machines connectéesà ce réseau a permi à de nouvelles méthodes de calcul d'apparaître : lescalculs distribués. Jusqu'alors réservées aux réseaux privés, ces méthodes segénéralisent et posent de nombreux problèmes qui sont autant de sujets derecherche, comme le prouvent les nombreux sujets abordés lors du WorkshopCollaborative tools and work environment [1], auquel j'ai assisté.

BonjourGrid est une plateforme en développement permettant de mettreen place des calculs distribués en utilisant le logiciel XtremWeb. Ce nou-vel outil a été présenté lors d'un Workshop organisé au LAL (Laboratoire del'Accélérateur Linéaire [2]) à Orsay, dans le cadre du projet européen EDGeS(Enabling Desktop Grids for e-Science [3]), auquel j'ai également assisté. Ceprojet vise à développer une infrastructure Desktop Grid au niveau européenqui permette de partager toutes les ressources disponibles pour la commu-nauté scienti�que.

La mise en place d'une telle plateforme pose de nombreux problèmes,parmis lesquels ceux que nous allons aborder. Après une brève présentation,dans le chapitre 2, de l'évolution des technologies et de l'avènement des grillesde calculs, nous étudierons, dans le chapitre 3, la possibilité d'adapter un pro-gramme de calcul des nombres de Kostka pour la plateforme BonjourGrid.Ce portage implique des modi�cations du programme, et notamment desaméliorations via l'utilisation de threads qui permettent un gain importantde performances. Nous nous pencherons ensuite, dans le chapitre 4, sur lessolutions disponibles pour instaurer une politique de certi�cation de résul-tats au sein de BonjourGrid et sur la manière dont ces solutions peuvent êtreintégrées à la plateforme.

Les problématiques liées à BonjourGrid abordées dans ce rapport et plusgénéralement par l'équipe du LIPN travaillant sur ce projet seront prochaine-ment concrétisées par un article rédigé par C. Cérin, H. Abbes, F. Butelle etmoi-même devant être publié dans le Journal of Grid Computing [4].

Les résultats du chapitre 3, traitant principalement de l'intégration dethreads au programme permettant le calcul des nombres de Kostka, sont trèspositifs puisque le temps de calcul est divisé par quatre pour une machinedisposant de quatre unités de traitements. Le chapitre 4, portant sur la cer-ti�cation de résultats, nous procure un catalogue des di�érentes solutionsdisponibles pour certi�er les résultats d'une application répartie, ainsi qu'unguide pour l'implémentation de ces solutions dans la plateforme Bonjour-Grid.

L'ensemble de mon travail s'inscrit dans le projet ANR de rechercheSAFESCALE (Security And Fault-tolerance to Exploit Safety ambient Com-puting in lArge scaLe Environments[5]) mené par le LIPN et ses partenaires(IMAG-ID et UJF de Grenoble, IRISA de Rennes et ENSTB de Brest).

5

Chapitre 1

Présentation de l'environnement

de stage : le LIPN

1.1 Présentation générale

Le Laboratoire d'Informatique de l'Université de Paris-Nord (LIPN [6])est associé au CNRS depuis janvier 1992 et a le statut d'UMR depuis janvier2001. Le LIPN poursuit ses recherches en automatisation du raisonnementautour de ses axes forts, l'Optimisation Combinatoire, l'Informatique Fon-

damentale et l'Intelligence Arti�cielle en s'appuyant sur les compétences deses membres, en particulier en Algorithmique, Logique, Langage Naturel,Apprentissage. Ces recherches sont e�ectuées dans quatre équipes par 57chercheurs et enseignants-chercheurs permanents, en poste pour la plupartà l'université Paris 13 (sur l'Institut Galilée, dans les IUT de Villetaneuseet de Bobigny). Au-delà de ces chercheurs et enseignants-chercheurs perma-nents, c'est en fait une centaine de personnes qui participent aux activitésdu laboratoire.

1.2 Les di�érentes équipes du LIPN

Le LIPN est structuré en quatre équipes dont les sujets de recherchesprésentent de nombreux points de rencontre :

• "Apprentissage Arti�ciel et Applications" (A3), qui développent desméthodes d'apprentissage innovantes en réponse à de nombreux besoinsapplicatifs. Les méthodes utilisées sont symboliques, numériques outransversales.

• "Logique, Calcul et Raisonnement" (LCR), dont les intérêts se sontrecentrés essentiellement sur la logique linéaire et ses applications en

6

informatique, les spéci�cations de systèmes et l'aide à la modélisation,et la combinatoire algébrique.

• "Optimisation Combinatoire et Algorithmique Distribuée" (OCAD),où sont abordés des problèmes liés à l'optimisation en nombres entiers,la satisfaction et l'optimisation des systèmes de contraintes, la combi-natoire et l'algorithmique pour les systèmes parallèles et distribués.

• "Représentation de Connaissances et Langage Naturel" (RCLN), quia pour objectif d'améliorer les techniques de représentation de la sé-mantique des langes à la fois pour obtenir une meilleure adéquationdes modèles formels et pour développer des outils e�caces d'accès àl'information textuelle ; son approche pluridisciplinaire lui confère uneplace sgni�cative dans le développement actuel des Sciences Cognitives.

1.3 L'équipe OCAD

L'informatique dé�nit, étudie et manipule des structures �nies ou dis-crètes à travers des algorithmes. L'objectif de l'équie OCAD (OptimisationCombinatoire (OC) et Algorithmique Distribuée (AD)) est l'analyse et l'opti-misation �nies de systèmes complexes discrets, séquentiels ou parallèles, pou-vant présenter une forte composante aléatoire. C'est au sein de cette équipeque le projet de mettre en place une grille de calcul distribué décentralisée avu le jour.

L'utilisation de grilles de calculs ouvre la voie à de nouvelles thématiquesde recherche, parmi lesquelles se trouvent le test de la plateforme développéeet la validation, ou certi�cation, des résultats obtenus, qui sont traités ci-dessous.

7

Chapitre 2

Introduction aux DesktopGrids et

à BonjourGrid

2.1 Bref historique du développement informa-

tique

2.1.1 L'évolution des technologies

Les premières machines à calculer inventées par l'homme furent dévelop-pées entre le XVIIe et le XVIIIe siècle. La première véritable machine àcalculer est attribuée à Blaise Pascal en 1642.

Cepdendant, l'informatique moderne, telle que nous la connaissons au-jourd'hui, est réellement apparue pendant la Seconde Guerre mondiale, aveccomme objectif de casser les codes Enigma. Grâce aux dévloppements théoriquesd'Allan Turing et à l'évolution des technologies (avènements des tubes àvide, des condensateurs, des circuits électroniques ...), la première machineentièrement électronique reconnue comme un ordinateur universel (premierordinateur Turing-Complet) fut créée en 1946. L'ENIAC (Electronic Numer-ical Integrator Analyser and Computer) contenait environ 18000 tubes à videpour un poids de 30 tonnes et une surface de 167 mètres carrés. Sa puissancede calcul était de 50 �ops (�oating-point operation per second) environ.

La deuxième gén¯ation d'ordinateurs (1956-1963) repose sur l'inventiondu transistor en 1947. Grâce à ce nouveau composant, les lampes à vide,fragiles (la plus longue période de calcul de l'ENIAC, atteinte en 1954, estde 116 heures seulement) et encombrantes sont remplacées et permettent laconstruction de machines plus �ables et plus puissantes. Un exemple typique

8

est l'IBM 7090, d'une puissance de calcul d'environ 33 K�ops pour un prixde 2,9 millions de dollars.

La troisième génération d'ordinateurs (1963-1974) repose sur l'avènementdu circuit intégré, qui permet de concentrer les transistors sur un seul circuitélectronique. La quatrième génération d'ordinateurs correspond aux ordina-teurs de bureau tels que nous les connaissons aujourd'hui. L'apparition desmicroprocesseurs permet de réduire la taille des ordinateurs, et l'avènementde l'architecture x86 d'Intel (en 1978 avec le 8086) marque le début des ar-chitectures informatiques actuelles.

2.1.2 Les machines parallèles

Actuellement, les processeurs ont une moyenne de puissance de calculque l'on peut évaluer à environ 8 G�ops. Cependant, les applications util-isées requièrent bien souvent une puissance de calcul bien supérieure pourêtre e�ectuées en un temps raisonable. Le �lm "Monstres & Compagnie" parexemple a nécessité environ 2, 7 ∗ 1010 G�ops, soit environ 107 années decalculs environ sur un ordinateur grand public. Pour e�ectuer de telles appli-cations, des architectures parallèles sont employées. On distingue plusieurstypes de parallèlismes.

Les systèmes répartis qui utilisent un parallèlisme par fédération

des ressources connectées par réseau

Ces systèmes, en pleine expansion depuis les années 1990, sont plus con-nus sous le nom de systèmes de calcul distribué ou réparti. Ils reposent surl'utilisation d'un grand nombre d'ordinateurs disponibles sur un réseau. Cetype de structure est di�érent des supercalculateurs car les ordinateurs quie�ectuent les calculs ne sont pas typiquement dédiés au calcul distribué etsont très hétérogènes (systèmes d'exploitation, de �chier, architecture).

2.2 Les grilles de calcul

Une grille informatique ou grid est une infrastructure virtuelle consti-tué d'un ensemble de ressources informatiques :

9

• Partagées : elles sont mises à la disposition des di�érents consomma-teurs de la grille et éventuellement pour di�érents usages applicatifs.

• Distribuées : elles sont situées dans des lieux géographiques di�érents.

• Hétérogènes : elles sont de toute nature, di�érant par exemple par lesystème d'exploitation ou le système de gestion des �chiers.

• Coordonnées : les ressources sont organisées, connectées et gérées enfonction de besoins (objectifs) et contraintes (environnements). Ces dis-positions sont souvent assurées par un ou plusieurs agents, qu'ils soientcentralisés ou répartis.

• Non-contrôlées (ou autonomes) : les ressources ne sont pas contrôléespar une unité commune. Contrairement à un cluster, les ressources sonthors de la portée d'un moniteur de contrôle.

• Délocalisées : les ressources peuvent appartenir à plusieurs sites, organ-isations, réseaux et se situer à di�érents endroits géographiques.

2.2.1 Les di�érents modèles de déploiement

Les grilles de calcul peuvent fonctionner suivant plusieurs modèles, enfonction de la manière dont sont réparties les tâches. On distinguera ici 2types d'architectures pour les grilles de calcul : "client-serveur" et "Peer-to-Peer", le Peer-to-Peer pouvant être centralisé ou autogéré.

L'architecture "client-serveur"

Dans les architectures de type "client-serveur", le serveur est chargé de lacoordination des clients e�ectuant les calculs (�gure 2.2.1). C'est le serveurqui distribue les di�érentes tâches en se chargeant de leur ordonnancement,et c'est également le serveur qui collecte les résultats et les synthétise.

Ce type d'architecture présente l'avantage d'une mise en place très facileet d'une synchronisation entre les di�érentes tâches facilitée (le serveur a ene�et un accès direct à tous les paramètres du réseau).

Cependant, cette architecture sou�re de lourds handicaps théroriques.Elle est ainsi très vulnérable aux pannes et aux montées en charge. Toutela gestion étant réalisée par une seule machine (ou bien un nombre �niéventuellement), si les ressources "serveur" ne sont plus disponibles l'inté-gralité de la structure de calcul devient inutilisable. De la même manière, lacommunication avec les clients nécessite une liaison �able. Si trop d'informa-tion transite, la connexion peut jouer le rôle d'un goulet d'étranglement et

10

Fig. 2.1 � Structure générale d'un réseau de type client-serveur.

ralentir drastiquement le système. Ces caractéristiques font de cette archi-tecture un modèle sensible aux attaques et de taille intrinsèquement limitée.C'est cependant ce modèle qui est le plus utilisé actuellement.

L'architecture "Peer-to-Peer"

Le principe du Peer-to-Peer, souvent écrit P2P (ou, d'après la traduc-tion française, pair à pair), est de mettre directement en relation une machinedemandant l'exécution d'un calcul et une machine proposant ses services (�g-ure 2.2.1). Ainsi, le goulot d'étranglement que peut constituer le serveur estcourcicuité.

Parmi les réseaux de type P2P, on peut distinguer les architectures quiconservent une centralisation des informations sur les clients connectés auréseau et ceux qui sont auto-administrés. Les réseaux P2P centralisés présen-tent l'avantage d'éviter la saturation de la connexion au niveau du serveurpuisque les clients sont mis en relation directe pour des échanges de données.Par contre, le risque d'une paralysation du réseau suite à une panne per-siste. De très nombreux réseaux fonctionnent suivant ce modèle (eDonkey,Gnutella, XtremWeb, Seti@Home ...).

11

Fig. 2.2 � Structure générale d'un réseau de type Peer-to-Peer.

Les réseaux auto-administrés sont moins répandus car plus contraignantà mettre en place. Le principe de tels réseaux est de supprimer totallementla dépendance à un système central. C'est ce type de réseau que nous allonsutiliser à travers la plateforme BonjourGrid.

2.2.2 La plateforme BonjourGrid

BonjourGrid est un logiciel qui a pour but de mettre en place des grillesde calcul basées sur le Peer-to-Peer et de manière décentralisée [8]. Il permetde fournir à des logiciels déjà existant tels que BOINC [9] ou XtremWeb [10]un environnement de travail. BonjourGrid est basé sur le protocole Bonjouret permet de structurer des environnement de calcul.

Bonjour : une implémentation du protocole ZeroConf

Bonjour [11] est une implémentation du protocole ZeroConf par Apple[12]. L'objectif de ce protocole est de faire fonctionner un réseau IP sansmettre en place d'infrastructure du type serveur DHCP ou DNS. Bonjour re-pose sur trois fonctionnalités principales : l'allocation dynamique d'adresses,la résolution des noms et des adresses IP et la recherche de services sansl'intermédiaire de serveur.

12

Bonjour permet donc de mettre en réseau des machines et de partagerdes services de manière automatisée et sans nécessité de con�guration, ce quiest important pour l'utilisateur �nal.

Fonctionnement de BonjourGrid

Le principe de BonjourGrid est de créer les structures de calcul à lademande au lieu de se contenter d'exploiter des structures �gées. Pour fairecela, les machines raccordées au réseau peuvent avoir trois états distincts (enréutilisant les dénominations XtremWeb) :

• idle : la machine n'est pas impliquée dans un calcul,

• worker : la machine participe à un calcul en temps que noeud de calcul,

• master : la machine participe à un calcul en temps qu'organisatrice.

Lorsqu'un utilisateur "idle" veut soumettre un calcul à la grille, sa ma-chine change d'état et devient "master". Son poste est alors chargé de con-struire un sous-réseau pour e�ectuer le calcul demandé. Des requêtes sont en-voyées aux postes voisins. Les machines jusqu'alors "idle" passent dans l'état"worker" et mettent leur puissance de calcul libre à disposition du "master"(voir �gure 2.2.2). Une fois le sous-réseau construit, le calcul est distribuéaux di�érents "worker" qui ont rejoint le sous-réseau. Lorsque le calcul estterminé, tous les noeuds repassent dans le mode "idle", se remettant ainsi àla disposition de la grille pour de nouveaux calculs.

Le fonctionnement décrit ci-dessus permet d'établir une grille robuste(résistante aux pannes) et e�cace (l'utilisation des ressources s'équilibrenaturellement). Comme dit précédemment, une fois que le sous-réseau estcréé, le calcul est distribué aux "worker" via un middleware déjà existant telque BOINC [9] ou XtremWeb [10]. L'utilisateur désirant e�ectuer un calculdoit donc fournir le code implémantant son application ainsi que le graphede tâches précisant l'ordre dans lequel les di�érentes étapes du programmedoivent être exécutées.

13

Fig. 2.3 � Schéma de fonctionnement général de BonjourGrid.

14

Chapitre 3

Portage d'une application : Schur

Les nombres de kostka sont très utiles dans le domaine de la théorie desnombres pour la décomposition de fonctions symmétriques. Leur calcul estdi�cile car lié à un problème d'énumération dont la taille croît vite. Schur[13] est un logiciel permettant de réaliser de nombreux calculs mathéma-tiques en théorie des nombres. Nous en avons extrait la partie permettant decalculer les nombres de kostka de manière à l'optimiser en répartissant lescalculs e�ectués sur plusieurs processeurs.

La répartition du calcul peut se faire sur deux niveaux : localement dansle cas d'une machine possédant plusieurs unités de traitement, et à distancedans le cas de machines connectées à un même réseau. Seule la partie localea été traitée ici.

3.1 Le contexte mathématique : Fonctions de

Schur et nombres de Kotska

3.1.1 Diagrammes de Ferrer et tableaux de Young

Pour tout entier positif n, on appelle partition de n toute décompositionde n en une somme d'entiers positifs décroissants. Ainsi, λ = (4, 2, 2, 1) etµ = (2, 1) sont des partitions respectivement de n = 9 et n′ = 3. Onnotera par la suite λ ` n et µ ` n′, ou encore |λ| = n et |µ| = n′.

Un diagramme de Ferrer d'une partition λ, noté F λ, est une représenta-tion graphique de la partition λ. C'est un diagramme constitué d'un ensemblede l(λ) = p cases. Le diagramme est aligné à gauche, et le nombre de casesde chaque ligne correspond aux éléments de la partition associée. Si F λ con-

15

tient F µ, on appelle semi-tableau1 et on note F λ/µ le tableau obtenu ensoustrayant les éléments de µ á λ. Pour les partitions λ = (4, 2, 2, 1) etµ = (2, 1), on obtient les diagrammes de Ferrer F λ, F µ et F λ/µ suivants :

· ··

Un tableau de Young semi-standard à valeur dans [m] est un diagrammede Young dont les cases sont remplies par des entiers compris entre 1 et m,avec la contrainte que les nombres doivent être croissants selon les colonnes(de gauche à droite) et strictement croissants selon les lignes (de haut enbas). La partition associée au diagramme sous-jacent s'appelle la forme

du tableau. On parle donc de tableau de Young semi-standard de formeλ (SSY T λ). Si toutes les entrées du tableau sont di�érentes (pas de numéro-tation redondante), on parle alors de tableau de Young standard de formeλ (SY T λ). On a ainsi les exemples suivants de tableaux de Young semi-standard et standard :

1 2 2 5

1 4

3 6

5

1 3 4 9

2 6

5 8

7

Une fonction symétrique est une fonction invariante par permutation deses variables :

f(xσ(1), xσ(2), ..., xσ(n)) = f(x1, x2, ..., x3)

où σ est une permutation quelconque de [|1..n|]. La fonction de Schur sλest la fonction symétrique dé�nie par :

sλ =∑

SSY Tλ

xm11 xm2

2 ... xmnn

avec |λ| = n et mi le nombre d'entrées des tableaux de Young semi-standards de forme λ pour i = 1, 2, ..., n. Pour µ = (2, 1) par exemple, ily a 8 tableaux de Young semi-standards de forme µ :

1Cette appellation n'est pas standard et est utilisée ici pour traduire le terme anglais

skew diagram

16

1 1

2

1 1

3

1 2

2

1 2

3

1 3

2

1 3

4

2 2

3

2 3

3

La fonction de Schur associée, sµ(x) s'écrit alors :

s12(x) = x21x2 + x2

1x3 + x1x22 + x1x2x3 + x1x2x3 + x1x

23 + x2

2x3 + x2x23

Les coe�cients de Littlewood-Richardson, notés cνλµ, sont dé�nis commeles coe�cients de la décomposition du produit des fonctions de Schur sλ etsµ sur la base des fonctions de Schur sν telles que, pour λ ` n et µ ` m,ν ` n+m :

sλ sµ =∑

ν ` n+m

cνλµ cν

Les coe�cients de Littlewood-Richardson sont également dé�nis commeles coe�cients de la décomposition de la fonction de Schur sν/λ sur la basedes fonctions de Schur :

sν/λ =∑µ

cνλµ sµ

Les nombres de Kostka Kλµ correspondent au nombre de tableaux deYoung semi-standards disctincts de forme λ et de poids µ, soit avec µi en-trées de valeur i pour i = 1, 2, ..., l(µ). Pour les partitions λ = (3, 2) etµ = (2, 2, 1), on peut construire deux tableaux de Young semi-standards deforme λ et de poids µ :

1 1 2

2 3

1 1 3

2 2

On obtient ainsi K32,221 = 2.

Les nombres de Kostka sont très utiles pour exprimer les fonctions deSchur comme combinaison linéaire des fonctions symétriques monomiales,ainsi que pour exprimer des fonctions symétriques quelconques en fonctiondes fonctions de Schur [14] :

sλ =∑

µ ` |λ| Kλµ mµ et hµ =∑

λ ` |µ| Kλµ sλ

17

3.1.2 Le calcul des nombres de Koskta par la méthode

des ruches

Par la suite, on appellera coe�cient de dilatation ou facteur de di-latation un coe�cient multiplicateur entier naturel appliqué à une partition.Par exmple 5× (4, 4, 3, 1) = (20, 20, 15, 5).

Les coe�cients de Littlewood-Richardson cνλµ croissent de manière poly-nomiale avec le facteur de dilatation N :

cNνNλ,Nµ = P νλµ(N) ; P ν

λµ(0) = 1 (3.1)

où P νλµ est un polynôme en N à coe�cients rationels positifs dépendants

de λ, µ et ν [15]. Ces polynômes sont obtenus par la méthode dite des ruches2. Une n-ruche à coe�cients entiers 3 est un tableau triangulaire d'entierspositifs aji avec 0 ≤ i, j ≤ n dont les maillages sont de trois types distinctsrespectant chacun une contrainte.

ba

c

b d

cd

R1 : R2 : R3 :

a

a

b

d

c

La condition associée à chaque �gure, en respectant les notations misesen place, sont :

b+ c ≥ a+ d (3.2)

Une LR-ruche [15] est une ruche satifaisant la condition précédente (3.2)pour tous ses constituants de type R1, R2 et R3, et dont les bords sontdéterminés par les partitions λ, µ et ν de telle sorte que :

a0

0 = 0 ; a0j = λ1 + λ2 + ...+ λj pour j = 1, 2, ..., n

a0i = ν1 + ν2 + ...+ νi pour i = 1, 2, ..., nakn−k = a0

n + µ1 + µ2 + ...+ µk pour k = 1, 2, ..., n(3.3)

avec l(λ), l(µ), l(ν) ≤ n et |λ|+ |µ| = |ν|.

Par exemple, pour n = 4, la LR-ruche correspondante est :

2traduction de "hives model" en anglais3"n-integer-hive" en anglais

18

λ1

λ1 + λ2

|ν| |ν| − µ4 |λ|+ µ2 |λ|+ µ1|λ|

|λ| − λ4

ν1

ν1 + ν2

|ν| − ν4

0

a11

a21 a1

2

Les coe�cients de Littlewood-Richardson cνλµ correspondent au nombrede LR-ruches donc les bords sont numérotés comme ci-dessus par les parti-tions λ, µ et ν. Dans le cas représenté, cνλµ est le nombre de triplets (a1

1, a21, a

12)

satisfaisant la condition (3.2) pour tous les éléments R1, R2 et R3. C'est doncle nombre de solutions du système d'inéquations obtenu en écrivant la con-dition (3.2) pour tous les éléments de la ruche. Il s'agit donc de résoudre unsystème d'équations, ou d'énumérer les solutions potentielles du système pourles tester une à une. Cependant à chaque nouvelle valeur �xée d'un noeudinterne, les équations peuvent être réajustées, faisant varier de manière im-prévisible le sous espace des solutions admissibles exploré.

Le degré du polynôme P νλµ est majoré par le nombre de points intérieurs à

la ruche, soit (n−1)(n−2)/2. Cependant, si une des partitions λ, µ ou ν a desparties redondantes, le degré du polynôme est inférieur à la borne précédente.

Les nombres de Kostka peuvent être perçus comme des coe�cients deLittlewood-Richardson particuliers. En e�et, Kλµ = cτσλ avec :

{τi = µi + µi+1 + ... pour i = 1, 2, ..., l(µ)σi = µi+1 + µi+2 + ... pour i = 1, 2, ..., l(µ)− 1

(3.4)

Par exemple si λ = (3, 2) et µ = (2, 2, 1), alors τ = (5, 3, 1) et σ = (3, 1).En calculant le coe�cient cτσλ avec la règle de Littlewood-Richardson, onobtient les diagrammes suivants :

× 1 1 1

2 2→ ... +

1 1

1 2

2

1 1

2 2

1

On a donc K32,221 = c53161,32 = 2.

19

Une K-ruche [15] est une ruche á coe�cients entiers satifaisant la condi-tion (3.2) pour tous ses constituants de types R1 et R2, mais pas forcémentpour ceux de type R3, et dont les bords sont numérotés par les partitions λ,µ et ν de telle sorte que :

ai0 = 0 pour i = 1, 2, ..., na0j = λ1 + λ2 + ...+ λj pour j = 1, 2, ..., nakn−k = µ1 + µ2 + ...+ µk pour k = 1, 2, ..., n

(3.5)

avec l(λ), l(µ) ≤ n et |λ| = |µ|.

3.2 Parallélisation de l'application

3.2.1 Présentation générale de l'algorithme

L'algorithme mis en oeuvre dans le programme "Schur" est l'algorithmedes ruches présenté précédemment. Pour calculer un polynôme de Kostka as-socié á un jeu de partition (λ, µ, ν), les coe�cients de Littlewood-Richardsonsont calculés pour des coe�cients de dilatation N croissants. A chaque nou-veau coe�cient calculé, le polynôme interpolant les couples (N, cτσλ) est déter-miné. On construit ainsi une suite de polynômes :

(Piνλµ)i∈N = P1

νλµ(N), P2

νλµ(N), ..., Pk

νλµ(N), ... (3.6)

Dès lors que deux polynômes calculés successivement sont égaux, la suiteest stationnaire. Le calcul des coe�cients de Littlewood-Richardson s'arrètedonc l'égalité entre deux polynômes est obtenue.

Le calcul de chaque coe�cient se fait en deux étapes, suivant la méth-ode des ruches. A partir des partitions fournies au programme, la ruche estgénérée. Grâce aux inégalités que doivent respecter tous les constituants de laruche (3.2), les valeurs que peuvent prendre les points intérieurs du maillagessont restreintes et on obtient ainsi un jeu d'intervalles Ik. On détermine ainsil'espace de solutions admissibles, qui est de la forme

∏k Ik. Il faut ensuite

tester toutes les valeurs de cet espace et véri�er que les inégalité (3.2) sontrespectées. Ainsi, on calcule le nombre de solutions pour la LR-ruche, quin'est autre que le coe�cient de Littlewood-Richardson recherché : cτσλ. Cetteénumération est imprévisible car l'espace exploré est a�né à chaque nouvellevaleur �xée, sans contrôle possible de la taille du sous espace résultant decette optimisation.

20

La seconde étape (l'exploration de l'espae des solutions admissibles) né-cessite un temps important et sa complexité est de la forme :

c(N) =m∏k=1

card(Ik) Nm (3.7)

où m est le nombre de points intérieurs à la ruche (qui est fonction despartitions choisies). Le nombre d'opérations nécessaires pour déterminer uncoe�cient de Littlewood-Richardson croît donc de manière polynomiale, maisavec un degré le plus souvent élevé (nombre de points intérieurs N impor-tant). On observe ainsi sur les graphiques de la �gure 3.2.1 l'augmentationdu temps de calcul en fonction du facteur de dilatation utilisé. De manière àaccélérer le processus d'énumération, à chaque fois qu'une valeur est choisiepour un point, les valeurs possibles pour les points qui n'ont pas encore été�xés sont recalculées. Ceci permet en pratique d'améliorer grandement lesperformances du programme.

Nous allons procéder à la répartition du calcul menant à la déterminationdes polynômes de Kostka sur deux niveaux. Tout d'abord, au niveau "local",nous allons accélérer le calcul en exploitant les structures multicoeurs très ré-pandues dans l'informatique actuelle. Ensuite, le calcul pourra être distribuésur les di�érentes machine d'un réseau.

3.2.2 Mise en oeuvre des threads

La plupart des ordinateurs actuels contiennent plusieurs coeurs, et mêmeparfois plusieurs processeurs, et ont donc plusieurs unités de traitment à leurdisposition. Dans le but d'exploiter les ressources disponibles au mieux, desbibliothèques permettant l'utilisation de threads ont été développées par lesconstructeurs. Dans le but de simpli�er l'utilisation des threads pour l'utilisa-teur et d'assurer la portabilité des programmes, un standard a été développé :la norme IEEE POSIX 1003.1c, donnant naissance aux pthreads. C'est cetteAPI qui a été utilisée ici.

Intégration des threads

La répartition du calcul aux di�érentes unités de traitement est réalisée aumoment de l'exploration de l'espace des solutions admissibles. L'énumérationest initialisée sur le premier intervalle (qui est fourni par l'étape précédentede détermination de l'espace admissible). Si le nombre de threads n autorisés

21

Fig. 3.1 � Augmentation du temps de calcul en fonction du facteur de di-latation et pour di�érentes partitions. Calcul réalisé sur un Bi-AMD Opterondual core cadencé à 2,8 GHz.

pour le programme est supérieur à la taille t de cet intervalle, alors t threadssont lancés, chacun explorant l'espace admissible associé à la valeur qui luia été con�ée pour le point correspondant au premier intervalle. Si le nombrede threads disponibles est inférieur à t, l'intervalle est découpé en n partségales et chaque thread explore une partie de l'intervalle.

La répartition du calcul se fait uniquement au niveau du premier in-tervalle pour des problèmes d'implémentation. En e�et, la synchronisationdes threads pour produire une équirépartition des valeurs à tester entre lesthreads est un problème compliqué qui n'a pas été traité ici. Ce choix peutde plus être justi�é par le fait que les calculs les plus lourds sont associés àdes facteurs de dilatation élevés, et donc à des intervalles relativement grands(au moins 10 valeurs). Pour un nombre de threads raisonnable et dans cesconditions, l'utilisation de threads sur plusieurs niveaux n'est pas utile.

Chaque thread procède comme décrit dans la partie précédente pour l'-

22

exploration de l'espace admissible qui lui est attribué. Le temps nécessairepour l'exploration d'un sous espace admissible par un thread est imprévisibledu fait que le sous espace est, comme précisé précédemment, a�né à chaqueétape.

Analyse des résultats

En pratique, l'utilisation de threads permet un gain considérable de temps,qui dépend néanmoins de plusieurs facteurs. Des benchmarks ont été réaliséspour di�érentes partitions, di�érentes limites du nombre de threads autoriséspour le processus, et di�érents facteurs de dilatation. La machine utiliséepour ces test est un "Bi-AMD Opteron dual core" cadencé à 2,8 GHz. Qua-tre unités de traitement sont donc disponibles pour les calculs.

On pourrait s'attendre à ce que le temps de calcul soit divisé par environdeux pour une limite de deux threads, environ trois pour une limite de troisthreads et environ quatre pour une limite du nombre de threads supérieure àquatre. Cependant, le gain de temps dépend également de la "géométrie" del'espace admissible. En e�et, comme expliqué précédemment, pour gagner dutemps l'espace n'est pas énuméré intégralement : les intervalles admissiblesdes points non �xés sont recalculés constamment. De ce fait, suivant la partiede l'intervalle de départ reçue par le thread, le temps de calcul est plus oumoins important.

C'est ainsi que l'on observe, sur le premier diagramme de la �gure 3.2.2,une stabilisation du temps d'exécution pour un nombre maximum de threadsupérieur à 10. Ce facteur est di�cile à anticiper, et n'a pas fait l'objet d'ap-profondissement. En e�et, le gain de temps est déjà signi�catif.

Malgré le trouble amené par cette observation, l'utilisation des threadspermet d'améliorer nettement les performances du programme. Tous les casétudiés aboutissent à une stabilisation du temps de calcul avec l'augmenta-tion du nombre de threads à environ un quart du temps de calcul avec unseul thread.

23

Fig. 3.2 � Evolution du temps d'exécution en fonction du nom-bre maximum de threads autorisés, pour les deux ensembles departitions : (λ = (5, 3, 2, 2, 1), µ = (4, 3, 2, 2, 1), ν = (7, 5, 4, 4, 3, 2)) et(λ = (7, 6, 5, 4), µ = (7, 7, 7, 4), ν = (12, 8, 8, 7, 6, 4, 2)).

24

Chapitre 4

Etude des méthodes de

certi�cation de résultats dans le

cadre des applications réparties

Nous allons aborder ici le problème de la certi�cation, ou validation, desrésultats produits par des calculs e�ectués à distance. Les calculs étant réal-isés sur des machines disponibles sur un réseau et non contrôlées, les résultatsobtenus peuvent être faussés. Des exemples de tricheries ont ainsi déjà étéobservés sur des applications réparties telles que SETI@home. Le but pour lapersonne falsi�ant les résultats est d'améliorer son classement en fournissantdes résultats rapidement.

Les fraudeurs peuvent être répartis en trois types :

• Les tricheurs permanents, qui retournent toujours un résultat faussé,

• Les tricheurs occasionnels, qui retournent un résultat faux avec uneprobabilité �xée (la catégorie précédente étant un cas extrême dont laprobabilité associée est 1),

• Les tricheurs qui retournent des résultats corrects pendant une certainepériode puis retournent des résultats faussés avec une probabilité �xe.

Les tricheurs peuvent de plus former des coallitions de manière à con-tourner la réplication de calculs : si plusieurs hôtes produisent la même valeurpour un même calcul, celle-ci a une forte probabilité d'être bonne. Cepen-dant, si les tricheurs se sont organisés, ils peuvent tous produire la mêmefausse valeur.

Pour véri�er la validité de résultats réceptionnés, deux types de méthodessont envisageables : la réplication des calculs [16, 17] et l'intégration de quiz

25

[18] cachés dans les calculs e�ectués. Dans les deux cas, un ordonnanceur(ou scheduler) adapté doit être développé.

4.1 La réplication de calculs

L'idée générale de la réplication de calculs est d'e�ectuer le même cal-cul sur plusieurs hôtes distincts et de comparer les résultats obtenus. Si lesrésultats coïncident, la valeur a une forte probabilité d'être correcte.

4.1.1 Réplication et réputation

L'inconvénient majeur de cette méthode est l'utilisation de plusieurs ressourcesdu réseau pour e�ectuer le même calcul, ce qui représente une perte de tempsconsidérable. Si le nombre d'hôtes retournant un résultat identique n'est passu�samment élevé, le calcul doit être refait entièrement. De manière à min-imiser le nombre de calculs reprogrammés, un système de réputation peutêtre mis en place.

Lorqu'un groupe su�samment nombreux d'hôtes retourne un résultatidentique, celui-ci peut être estimé correct. La réputation des hôtes en ques-tion est alors accrue, alors que celle des hôtes n'ayant pas retourné de résultatou ayant retourné un résultat faux est diminuée. Les modi�cateurs de répu-tation peuvent être ajustés en fonction du réseau exploité [18]. Il ne serontpas traités ici.

La réputation associée aux hôtes peut être gérée de trois manières dif-férentes :

• localement : chaque hôte maintient son propre �chier de réputationfondé sur ses transactions avec les autres hôtes.

• avec un partage partiel : les hôtes partagent leur �chier de réputationavec leurs voisins (par exemple avec les hôtes situés sur le même sous-réseau).

• globalement : un �chier commun à tous les hôtes est actualisé constam-ment et contient la réputation associée à chaque hôte.

Pour a�ner le modèle de réputation, des listes noires peuvent égalementêtre créées. L'utilisation de celles-ci dépend de la politique de gestion de laréputation choisie.

Pour chaque catégorie de gestion des listes de réputation, des ra�nementssont possibles. En pratique, les systèmes consistant à prendre en compte un

26

maximum d'information sont plus performant que ceux consistant à exploiteruniquement les expériences locales.

4.1.2 Groupes de calcul et scheduling

Les listes de réputations peuvent être utilisées pour minimiser le nombrede calculs reprogrammés. Comme expliqué précédemment, les calculs sont ef-fectués en parallèle sur plusieurs hôtes distincts. Ceux-ci forment des groupesde calcul. Les groupes de calcul peuvent être constitués en utilisant les �chiersde réputation.

L'idée générale est de former un maximum de groupes ayant chacun un de-gré de con�ance supérieur à une borne �xée [16] . Ainsi, le nombre de calculsaboutissant à un résultat correct peut être maximisé. Di�érentes politiquespeuvent être employées pour former ces groupes. On peut distinguer troisméthodes.

• La formation de groupes de réputation la plus élevée possible. Pour cefaire, les hôtes sont classés de manière décroissante en fonction de leurréputation. Les groupes de calculs sont ensuite formés en prenant leshôtes dans cet ordre.

• La formation de groupes de manière à être le plus proche possible duseuil de con�ance choisi. Pour chaque groupe, on tente de sélectionnerun nombre de participant inférieur au nombre maximum de participantspossible, et excédant la borne de con�ance du minimum possible.

• La formation de groupes de manière aléatoire. Les hôtes sont ajoutés demanière aléatoire à chaque groupe jusqu'à ce que la con�ance associéeau groupe dépasse le seuil �xé ou que le nombre de participants augroupe dépasse le maximum autorisé.

Dans les trois cas, le nombre minimum de participants à un groupe decalcul est �xe de manière à toujours exploiter le principe de réplication descalculs. Dans l'absence de redondance, et sans mettre en oeuvre d'autre méth-ode, aucun résultat ne peut être certi�é. On peut également choisir de �xerun nombre maximum de participants à un groupe de manière à toujours avoirplusieurs calculs e�ectués simultanément.

27

4.2 La réplication de calculs sur des machines

�ables

Dans le cas où le nombre de tâches à exécuter est élevé, la réplicationde calculs telle qu'exposée précédemment n'est pas exploitable. Le tempsnécessaire pour mener à bien l'application devient en e�et beaucoup tropimportant. Une autre solution consistant à répliquer seulement une partie decalculs peut alors être mise en place [19].

L'objectif est de sélectionner aléatoirement des tâches et de les répliquersur une machine �able. Le nombre de tâches dupliquées est ainsi drastique-ment réduit. Pour mener â bien cette méthode, il est nécessaire d'avoir àdisposition une (ou plusieurs) machine dédiée à la réplication et totalement�able. Ces machines sont habituellement appelées des oracles.

Le pourcentage de tâches répliquées peut être adapté en fonction duréseau utilisé (de sa taille, de la con�ance moyenne attribuée aux hôtes de ceréseau). Plus la proportion de tâches répliquées est élevée, plus la probabilitéque le résultat �nal de l'application soit correct est importante, mais plus letemps de calcul nécessaire pour obtenir ce résultat est important. Il s'agitdonc de trouver un compromis entre temps d'exécution et pourcentage dechances que le résultat �nal soit correct, compromis pouvant être a�né parun raisonnement de tests d'hypothèses [19]. Cependant, cette étude dépendprincipalement du réseau employé, et nous ne la pousserons pas plus loin ici.

4.3 L'intégration de quiz

4.3.1 Principe théorique

Un quiz [18] est ici un petit questionnaire permettant de tester un hôte.Il est constitué de petits calculs dont on connait les résultats (ou dont lesrésultats sont facilement reproductibles). Le principe de cette méthode estd'intégrer un ensemble de quiz aux tâches soumises à un hôte. Si l'hôte re-tourne des résultats corrects pour les quiz, la probabilité que les résultatsretournés pour les autres calculs soient également corrects est élevée.

Les quiz doivent être des calculs légers pour ne pas capitaliser inutilementdes ressources du système pendant une longue période et pour être facilementreproductibles. Ils ne doivent être utilisés qu'une seule fois pour contrecarerd'éventuels tricheurs s'adaptant aux quiz.

28

4.3.2 Une méthode adaptative

L'utilisation de quiz présente un inconvénient majeur : la présence decalculs inutiles. En e�et, les quiz servent uniquement à la véri�cation de lavalidité des résultats, et n'ont aucun rôle dans l'obtention du résultat �nal.Ils occupent donc des ressources du système qui pourraient être employéespour la résolution du problème traité. C'est pour cela qu'il faut minimiser lenombre de quiz envoyés à chaque hôte.

Pour minimiser le nombre de quiz e�ectués, un système de réputationanalogue à celui mis en place précédemment pour la réplication peut êtreemployé. Si un hôte répond correctement à plusieurs quiz, son degré de con-�ance est accru et il devient moins important de le contrôler. On dé�nit laproportion de quiz dans un ensemble de calculs soumis à un hôte comme lenombre de quiz sur le nombre de tâches. Si l'hôte possède une réputationélevée, ce ratio peut être diminué. L'hôte produira alors un plus grand nom-bre de résultats "utiles". Si l'hôte possède une réputation faible, le nombrede quiz à lui soumettre est plus élevé car il est plus important de véri�erl'exactitude des résultats retournés.

Il faut cependant noter que même pour des hôtes dont la réputation esttrès élevée, il faut toujours maintenir un ratio minimum de quiz. Il faut ene�et être en mesure de repérer les hôtes malicieux (décidant de fausser lesrésultats à partir d'un moment donné).

En pratique, l'utilisation de quiz permet un gain de temps non négligeablepar rapport à la réplication [18]. En l'absence de coalition des tricheurs, lepourcentage de résultats corrects est similaire d'une méthode à l'autre, maisle temps nécessaire à la formation des groupes de calculs donne l'avantageà la méthode des quiz. En revanche, lorsque les tricheurs sont organisés,l'utilisation de quiz est largement justi�ée car la réplication suppose qu'unrésultat apparaissant un grand nombre de fois chez di�érents participants ade fortes chances d'être correct.

29

4.4 Intégration d'un service de certi�cation dans

BonjourGrid

La gestion des ressources d'une grille a progressivement évolué au �l desans depuis la recherche manuelle de ressources et la soumission manuelle detâches vers des solutions de courtage (brokering solution) évoluées, c'est àdire automatiques. L'idée est que l'utilisateur décrive les propriétés de saressource et le manager de ressources, qui est un composant de l'intergiciel,apprend à l'intégrer.

Deux problèmes importants doivent être ensivagés dans notre cas. Pre-mièrement, si la boite à outils de certi�cation est � vissée �dans l'intergi-ciel BonjourGrid ou XtremWeb, alors il ne sera pas possible de la réutiliserailleurs � on perd l'idée de service réutilisable. Il convient donc de prévoirun service générique, réutilisable. Deuxièmement, il faut aussi développer unmodule qui permet à ce service de communiquer avec BonjourGrid et doncl'interface doit être simple à utiliser et que la spéci�cation de l'interface devraimpacter le moins possible BonjourGrid : une ré-écriture lourde de Bonjour-Grid n'est pas souhaitable.

L'architecture SOKU permet plus de �exibilité, d'adaptativité et proposedes interfaces avancées, assurant ainsi une interopérabilité importante. S'in-scrivant dans cette perspective, des travaux ont envisagé le développementde WWG (World Wide Grid) comme la prochaine génération de grilles, dela même manière qu'est né internet.

On peut penser que notre problème est un problème d'ordonnancementpuisqu'il faut allouer des tâches sur des noeuds sûrs et aussi sur des noeudspas sûrs. Ainsi, l'étude des �Scheduling Description Language� se justi�e.Parmi ces langages, nous pouvons citer GSA-RG de l'OGF (https ://forge.gridforum.org/projects/gsa-rg) qui vise à faire interagir des schedulers de grilles,le Koala Grid Scheduler (http ://www.st.ewi.tudelft.nl/koala). Un des ob-jectifs principaux de ces projets est de faire en sorte que le meta-schedulerpasse la main au scheduler le moins chargé par exemple. Il s'agit d'optimiserle temps de complétion. Dans notre cas, nous pouvons imaginer N > 1 in-stances d'XtremWeb demandant chacune une certi�cation.

Ici nous pouvons aussi décider qu'il n'y aura qu'un seul � serveur �de cer-ti�cation mais les projets ci-dessus laissent à penser que l'on peut envisagerune distribution de la certi�cation sur plusieurs � serveurs �sûrs.

30

Nous pouvons aussi citer Gridway (http ://www.gridway.org/) commeune autre technologie pour réaliser des méta-ordonnanceurs. Gridway est unprojet Globus et à ce titre nous pouvons penser qu'il sera bientôt largementutilisé... c'est déjà un peu le cas.

Dans tous les cas, le composant de certi�cation devra faire appel à desstandards et reposer sur les vues suivantes [20] :

• JDL - Job Description Language : le service de certi�cation devanto�rir un service uniforme à di�érents types de grilles, il doit disposerd'un format standard pour permettre aux utilisateurs de décrire leurtâches.

• CDL - Capability Description Language : le module de certi�ca-tion doit disposer d'un format permettant de décrire ses capacités pourêtre compatibles avec d'autres modules qui fourniraient des servicesdi�érents (et utiliseraient le même CDL).

• Scheduling : il est indispensable d'avoir un service d'ordonnancement.Ce service prend en charge la répartition des tâches demandées parl'utilisateur en prenant se basant sur les méthodes décrites dans lesparagraphes précédants.

• GJI - Global Job Identi�ers : il est essentiel que chaque tâche(ou job) ait un identi�ant unique de manière à pouvoir contrôler sonévolution dans le système.

• SM - Security Management : un service d'authenti�cation permetde contrôler les accès à la plateforme, par exemple grâce à des certi�catsou à des serveurs proxys.

• Accounting Mechanism : on peut envisager de mettre en place unsystème d'accomptes pour faciliter la gestion de la réputation. Ce mod-ule est cependant, dans un premier temps, optionnel.

• Agreements Mechanism : un service permettant de prendre en compteles caractéristiques des hôtes et leurs exigences peut aider l'ordon-nanceur dans ses choix. Comme le module précédant, ce module estoptionnel.

• Monitoring Mechanism : pour fournir des services avec un degré decon�ance su�sant, il est nécessaire de s'assurer de leur bon fonction-nement régulièrement. Il faut donc contrôler l'état des divers servicesainsi que l'état du réseau. Un système robuste doit prévoir de palier àtout malfonctionnement.

31

• Prediction Mechanism : ce module peut aider l'ordonnancementdes tâches en exploitant le module de monitoring et l'ordonnanceur.Il peut ainsi faire des prévisions et guider les choix de l'ordonnanceur.C'est un module utile pour gérer les grilles qui sont des structures trèsdynamiques.

• Addressing and Noti�cation Mechanism : ce module est respons-able de la communication avec les hôtes et les autres modules. Il permetde gérer l'état des tâches.

En conclusion, la discussion précédente permet de �xer les directions detravail pour intégrer un service de certi�cation de résultats à l'aide de tech-nologies pré-existantes. Il ne s'agira pas, bien entendu, de réinventer la rouemais de s'appuyer sur des solutions existantes permettant à BonjourGridd'o�rir un service sans pareil et utile pour obtenir plus de con�ance dans lestechnologies de Grilles.

32

Conclusion

A travers ce document, nous nous sommes intéressés à deux problèmesrelatifs au développement de la plateforme BonjourGrid. Dans le chapitre3, nous avons étudié le portage d'un application de calcul des nombres deKostka (extraite de Schur) pour la plateforme BonjourGrid. En prélude auportage lui-même, nous avons amélioré le code pour prendre en compte laprésence de plusieurs unités de traitement dans les machines actuelles. Il ré-sulte de cette optimisation un gain de temps considérable puisque le tempsde calcul sur une machine disposant de quatre unités de traitement est divisépar quatre. Des tests de l'applications sur BonjourGrid ont été e�ectués àpetite échelle. Cependant, de vrais tests à grande échelle n'ont pas étés menésà bien et doivent être réalisés prochainement pour renforcer la validation dela plateforme BonjourGrid.

Le chapitre 4 nous a permis d'aborder un second problème lié au développe-ment de BonjourGrid : la certi�cation des résultats produits. Après un cat-alogue des diverses méthodes disponibles, nous avons envisagé les moyensd'intégrer un module de certi�cation au sein de BonjourGrid. Il s'est avéréque la réalisation d'un module totalement indépendant de BonjourGrid, cequi était le but initial, pose de nombreuses di�cultés. L'ordonnanceur doiten e�et être au centre du logiciel. Malgré ce problème, l'intégration d'unmodule de certi�cation à la plateforme BonjourGrid est maintenant assezbien cadré. La prochaine étape consiste donc à implémenter les descriptionsfournies dans le chapitre 4 à BonjourGrid.

Le développement de BonjourGrid et tous les points présentés dans cerapport s'inscrivent dans un projet plus vaste : SAFESCALE [5] qui a pourobjectif de produire des outils de type Desktop Grid �ables et présentant desgaranties sur la validité des résultats.

33

Bibliographie

[1] http ://www.aristote.asso.fr/Secretariat/actes.html

[2] http ://www.lal.in2p3.fr/

[3] http ://www.edges-grid.eu/

[4] http ://www.springerlink.com/content/111140/

[5] https ://www-lipn.univ-paris13.fr/safescale/

[6] http ://www-lipn.univ-paris13.fr

[7] www.top500.org

[8] H. Abbes, C. Cérin, J.-C. Dubacq, M. Jemni, BonjourGrid : A Decen-

tralized Community Desktop Grid.

[9] boinc.berkeley.edu

[10] www.xtremweb.net

[11] La technologie Bonjour : http ://devel-oper.apple.com/networking/bonjour

[12] D. Steinberg et S. Cheshire, Zero Con�guration Networking : The De�ni-tive Guide. O'Reilly Media, Inc., première édition, décembre 2005.

[13] sourceforge.net/projects/schur

[14] I.G. MacDonald, Symmetric functions and Hall Polynomials, 2nd ed.,Clarendon Press, Oxford Science Publication, 1995.

[15] R. C. King, C. Tollu, and F. Toumazet, Stretched Littlewood-Richardsonand Kostka coe�cients, CRM Proceedings and Lecture Notes, Vol. 34,Amer. Math. Soc, 2004, pp99-112.

[16] J. Sonnek, A. Chandra, J. B. Weissman, Adaptative Reputation-Based

Scheduling on Unreliable Distributed Infrastructures, IEEE transactionson parallel and distributed systems, vlo. 18, no. 11, Novembre 2007.

[17] K. Budati, J. Sonnek, A. Chandra, J. Weissman, RIDGE : Combining

Reliability and Performance in Open Grid Platforms, HPDC'07, Juin2007.

34

[18] S. Zhao, V. Lo, C. GauthierDickey, Result Veri�cation and Trust-based

Scheduling in Peer-to-Peer Grids, Proceedings of the �fth IEEE Inter-national Conference on Peer-to-Peer Computing (P2P'05).

[19] S. Varrette, Sécurité des Architectures de Calcul Distribué : Authen-

ti�cation et Certi�cation de Résultats, thèse en cotutelle internationalepour obtenir le grade de Docteur de l'INP de Grenoble et de l'Universitédu Luxembourg, Sept. 2007.

[20] A. Kertész, I. Rodero, F. Guim, Meta-Brokering Solutions for Expanding

Grid Middleware Limitations

35