Calcul distribué
On cherche toujours à exécuter une unique tâche coupée en parties, mais on ne précise plus si ces dernières s’exécutent sur des processeurs ou des machines à part entière, on ne fait plus référence, en fait, à une architecture (bien que dans le domaine des systèmes distribués on sous-entend quasiment toujours l’existence d’un réseau de machines), le terme computing entity pouvant identifier un processeur comme une machine.
La méthode développée dans cette thèse se veut indépendante d’une architecture donnée, c’est pourquoi nous parlerons par la suite de ressource de calcul pour toute entité capable d’exécuter les instructions d’un programme séquentiellement, et ceci, que la ressource de calcul soit au sein d’un supercalculateur, d’un cluster, ou autres.
C’est pourquoi on ne prendra pas en compte les architectures d’interconnexion de ces ressources de calcul, ainsi que les interconnexions avec d’autres types de ressources (mémoire, stockage, etc.).
D’ailleurs, les systèmes distribués se détachent le plus souvent de cette architecture d’interconnexion, et évoluent de plus en plus vers une configuration en grille. Ce terme désigne des systèmes hétérogènes, dans lesquels on utilise diverses ressources de calcul et de stockage en fonction de leur disponibilité. Parfois les grilles sont dédiées, mais souvent il s’agit de machines dont on a décidé qu’elles pouvaient faire partie d’une grille et qui fournissent des cycles de calcul aux applications lorsqu’elles ne sont pas chargées. Le terme anglo-saxon grid computing est principalement utilisé, et n’a pas encore de traduction généralisée en France.
Le système distribué matériel
Le parallélisme concerne toutes les approches visant à accélérer un calcul en le coupant en parties pour l’exécuter sur diverses ressources de calcul. Ceci peut être fait sur des machines centralisées tels des supercalculateurs massivement parallèles, ou sur des systèmes répartis. Ces derniers peuvent alors se scinder en deux groupes, les clusters dédiés, physiquement localisés en des points précis, connus et administrés de manière globale, et les grilles qui représentent un cluster virtuel, physiquement réparti couvrant plusieurs domaines administratifs.
En ne prenant pas explicitement en compte l’architecture du système informatique sur lequel nos applications seront distribuées, nous pouvons donc considérer un modèle physique très simple : chaque ressource de calcul peut communiquer avec n’importe quelle autre via un réseau dont la topologie est inconnue, en un mot le réseau de ressource de calcul physique est connexe ; les ressources de calcul peuvent apparaître ou disparaître naturellement au sein de ce réseau pendant que l’application s’exécute ;
si une ressource disparaît à la suite d’une panne, on se repose sur un mécanisme de duplication des parties logicielles s’y exécutant, ceci afin de maintenir la connexité du réseau ; les ressources de calcul sont hétérogènes, de puissance différente, et ayant accès à des ressources différentes.
Parallélisme et réseaux d’interaction
La modélisation par graphe d’entités en interaction est commune. Le parallélisme utilise des graphes d’entités afin de réaliser :
des ordonnancements, si le graphe est orienté, c’est-à-dire si des tâches dépendent d’autres ; des placements si les tâches sont indépendantes.
Cependant, ici, nous nous intéresserons uniquement au placement en considérant des entités dont la durée d’exécution n’est pas connue à l’avance. Nous verrons que les interactions sont importantes et considérées, non pas sous l’angle direct de la dépendance entre tâches avec un algorithme prenant des entrées et ayant des sorties, mais plutôt sous l’angle d’entités en communication, c’est-à-dire avec de très nombreuses entrées et sorties, au début de leur exécution, à la fin, mais aussi durant toute leur durée de vie.
On ne peut placer en parallèle que les tâches indépendantes les unes des autres. L’approche est souvent fonctionnelle, avec une tâche par processeur, chaque tâche étant une fonction, et les données sont communiquées d’une tâche à l’autre au début et à la fin de leur exécution. La figure montre à la fois le graphe de dépendance et un diagramme temporel de communication où chaque tâche est représentée par un rectangle dont la hauteur correspond à sa durée.
D’un autre côté on modélise l’application par un graphe de tâches communicant continuellement, sans dépendance. L’approche est souvent objet, avec les données encapsulées avec le traitement, et les objets évoluant souvent en parallèle dans des threads, à plusieurs sur une ressource de calcul, lorsqu’il y a besoin d’information (une autre forme de dépendance), les objets communiquent, et ceci peut se produire plusieurs fois au cours de leur exécution.
Il faut noter que le second modèle contient le premier qui en est une spécialisation. Ainsi une méthode capable de prendre en compte le second modèle sera à même de s’appliquer au premier, même s’il est possible qu’elle soit légèrement moins efficace qu’une méthode dédiée.
Modèles et simulations
Roger Bacon (1214-1294), a été un des premiers à formaliser les étapes de la démarche scientifique. Elle peut être décomposée ainsi:
observation du phénomène et caractérisation de ce dernier ; formulation d’hypothèses sur le fonctionnement de ce dernier souvent au travers d’un ou plusieurs modèles; prédictions, fondées sur ces hypothèses ; vérification par l’expérience ; évaluation, et remise en cause en fonction des résultats ; communication à la communauté ;
Suivant cette démarche on crée un modèle du phénomène observé sur lequel on fait ensuite des expériences. L’un des moyens de mener à bien ces expériences est la simulation. On utilise la simulation parce que parfois :
il n’est pas possible de réaliser l’expérience sur le phénomène lui-même en situation pour des raisons pratiques ; l’observateur perturberait l’expérience ; l’expérience serait contraire à l’éthique. On peut donc voir deux raisons majeures à l’utilisation de simulations dans les sciences : comprendre et expliquer un phénomène réel ou abstrait, parce que l’on ne peut pas pour des raisons pratiques expérimenter sur le modèle lui-même ; prévoir un phénomène réel ou abstrait afin d’en connaître le comportement à venir en fonction de différentes conditions initiales, afin d’en prédire l’évolution.
Les simulations sont donc le processus de calcul que l’on applique à un modèle. On utilise le modèle pour reproduire des phénomènes réels observés à travers ce dernier.
Nous donnerons une définition plus précise des simulations par la suite, mais avant il est nécessaire de décrire plus précisément ce que l’on entend et désigne par le terme modèle.
Les modèles individu-centrés (IBM)
L’acronyme anglo-saxon IBM signifie Individual-Based Models, que l’on traduit le plus souvent en français par modèles individu-centrés. Ces modèles, comme leur nom l’indique, reposent sur la modélisation explicite de certaines parties du phénomène, nommés individus, et l’expression elle aussi explicite de leurs interactions.
Au lieu de modéliser globalement le phénomène en représentant la dynamique générale de son évolution, on représente localement certaines parties significatives du phénomène en modélisant leur comportement propre. Ces parties peuvent être des éléments déjà perçus comme distincts dans le phénomène (des fourmis dans une fourmilière) ou bien des éléments abstraits qui n’ont d’utilité que par rapport au modèle (ensemble de particules numériques formant des méta-particules dans un flux, aucune meta-particule n’existe, ni même les particules numériques de base qui sont l’information numérique modélisant le flux). On dit aussi de ces modèles qu’ils sont «à base de règles», les règles définissant le comportement des différentes parties du phénomène modélisé. Ce type de modèle met en avant les interactions entre les parties du modèle. En effet, au contraire des modèles analytiques où les équations du système dépendent des mêmes variables, les modèles IBM définissent explicitement les relations entre les éléments du modèle sous forme d’interactions.
Table des matières
I Concepts
1 Introduction
1.1 Le problème
1.2 Organisation du document
1.3 Cadre général
1.4 Une autre vue du manuscrit
2 Distribution
2.1 La partie physique d’un système distribué
2.1.1 Parallélisme
2.1.2 Calcul distribué
2.1.3 Le système distribué matériel
2.2 La partie logicielle d’un système distribué
2.2.1 Composants d’un système distribué
2.2.2 Adressage
2.2.3 Migration
2.2.4 Interactions
2.2.5 Parallélisme et réseaux d’interaction
2.2.6 Parallélisme et mode d’exécution
2.2.7 Le système distribué logiciel
2.3 Le système distribué dans son ensemble
2.4 Le coût de la distribution
3 Simulations
3.1 Modèles et simulations
3.1.1 Modèles
3.1.2 Simulations
3.1.3 Modèles continus et modèles discrets
3.1.4 La flèche du temps
3.1.5 Aléatoire et imprévisibilité
3.1.6 Distribution
3.2 Modèles computables
3.2.1 Les modèles analytiques
3.2.2 Les modèles individu-centrés (IBM)
3.3 Réseaux d’interaction
3.3.1 Structures et organisations
3.3.2 Réseaux d’interaction, sémantique et graphes
3.3.3 Dynamique
4 Approches Collectives
4.1 Intelligence en Essaim
4.2 Définition
4.3 Organisation et Auto-Organisation
4.3.1 Organisations
4.3.2 Auto-Organisation
4.3.3 Les mécanismes de l’auto-organisation
4.3.4 La loge royale des termites (suite et fin)
4.3.5 Émergence
4.3.6 Stochastique et auto-organisation
4.4 Vision Globale et Vision Décentralisée
4.5 Essaim de particules et Optimisation
4.5.1 Boids
4.5.2 PSO
5 Fourmis numériques
5.1 Fourragement et Stigmergie
5.1.1 Dans la nature
5.1.2 Expériences
5.2 Modèles de fourragement, et applications
5.2.1 Simulation
5.2.2 Applications
II État de l’art
6 Le problème
6.1 Objectifs
6.2 Le problème
6.3 Propriétés pour un algorithme de distribution dynamique adaptative
6.3.1 Dynamique
6.3.2 Temps réel au sens large
6.3.3 Gestion de charges
6.4 Mesures de qualité
7 Méthodes de distribution statiques
7.1 Partitionnement de graphe
7.2 Bissection récursive
7.3 Partitionnement «glouton»
7.4 Kernighan et Lin
7.5 Partitionnement spectral
7.6 Approches multiniveau
7.7 Algorithmes génétiques
7.8 Colonisation émergente
7.9 Clustering par colonie de fourmis pour le partitionnement
8 Méthodes de distribution dynamiques
8.1 Algorithmes de diffusion
8.2 Approche particulaire
III Modèle
9 AntCO2
9.1 Présentation et Spécificités
9.1.1 Fourmis et phéromones colorées : collaboration et compétition
9.1.2 Le graphe en tant qu’environnement et solution
9.1.3 Distribution par détection d’organisations
9.1.4 Modèle d’exécution
9.2 Modèle
9.2.1 Graphe et Environnement
9.2.2 Fourmis et Comportement
9.2.3 Gestion de Population et démographie
9.2.4 Conditions initiales
9.2.5 Ajouts de couleurs
9.2.6 Gestion de conditions particulières et Mécanismes Supplémentaires
9.3 Architecture
9.3.1 Modèle en Couches
9.3.2 Comment Distribuer AntCO2 Lui-même
9.3.3 Synchronisme et Asynchronisme
9.4 Paramètres
10 Améliorations de la méthode
10.1 Réglage automatique de paramètres avec PSO
10.1.1 Principe
10.1.2 Application au réglage de paramètres
10.1.3 Quelques résultats préliminaires
10.2 Programmation génétique
10.2.1 Principe
10.2.2 Adaptation à notre modèle
IV Expérimentations et travaux connexes
11 Graphes statiques
11.1 Grilles
11.1.1 Grille avec pondération uniforme
11.1.2 Grille pondérée
11.2 Graphes aléatoires
11.3 Graphes Complets
11.4 Graphes invariants d’échelle
11.5 Archive de partitionnements de graphes
12 Graphes dynamiques
12.1 Dynamique dans les ressources de calcul
12.2 Divers graphes dynamiques
12.3 Écosystème marin
12.3.1 Simulation
12.3.2 Mode de distribution
12.3.3 Résultats
13 Implantation
13.1 Première Implantation : Distribution Simulée
13.2 Seconde Implantation : Prototype Distribué
14 Modifications du modèle
14.1 Système d’aide à la décision pour le trafic routier
14.1.1 Principe
14.1.2 L’algorithme
14.1.3 Premières expérimentations
14.2 Recherche de communautés dans les réseaux
Bilan et perspectives
Index des notations
Bibliographie
Publications
