Avec les récents progrès technologiques réalisés dans la collecte et le stockage des données, il est désormais facile de produire en peu de temps une masse importante de données. Ces volumes de données de plus en plus distribués, disséminent des connaisances potentiellement utiles pour des décideurs, mais leur vitesse de production et leur taille dépassent largement notre capacité à les analyser. Il est donc nécessaire de développer de nouveaux outils permettant de réduire et d’analyser ces données. Exploiter de telles masses de données nécessite le recours à des systèmes informatiques, permettant d’extraire de manière plus ou moins automatique ces informations. Ces systèmes se basent sur un processus de datamining qui englobe plusieurs techniques dérivées de différents domaines, tels que l’apprentissage automatique, l’intelligence artificielle, les bases de données et l’analyse de données. Comme type de connaissances générées par un tel processus, le plus connu est celui des règles associatives, qui permettent d’identifier des relations entre données d’une base de transactions.
D’un point de vue algorithmique, il existe toute une variété d’algorithmes en majorité sequentiels permettant d’extraire ce type de connaissance. Malgré leur efficacité, ces algorithmes voient leurs performances se dégrader lorsque la taille ou la dimension des données augmente. Pour maintenir les performances de ces algorithmes, le développement et l’utilisation de méthodes et d’outils parallèles et distribués apparaît comme une solution naturelle pouvant aider à accélérer la vitesse de traitement. En effet, les environnements de traitement parallèles et distribués augmentent grandement notre capacité à traiter les grandes masses de données dans la mesure où ils permettent d’exploiter toutes les ressources disponibles (processeurs, mémoire, etc.).
Aperçu sur le calcul haute performance
Calcul haute performance et parallélisme
Le parallélisme est une stratégie pour accélérer les temps d’exécution de tâches de grande taille. Les tâches sont initialement décomposées en sous-tâches de taille plus petite et celles-çi sont ensuite assignées à plusieurs processeurs qui les exécutent simultanément. Traditionnellement, les programmes informatiques étaient écrits pour des machines monoprocesseurs (machines de von Neumann) qui n’exécutent qu’une seule instruction à la fois et ceci tous les 9ns pour les plus rapides d’entre elles [1]. Cette vitesse d’exécution peut paraître élevée mais pour les applications qui nécessitent beaucoup de puissance de calcul, tels que problèmes de simulation et de modélisation de phénomènes naturels complexes, les problèmes nécessitant de grandes capacités de calcul et la manipulation de grandes quantités de données comme le datamining, le traitement d’image, etc. les performances exigées sont nettement plus élevées. Devant les limites physiques de la taille de la mémoire et de la vitesse de calcul des systèmes monoprocesseurs, le parallélisme apparaît comme une solution compétitive (excellent rapport coût/performance) pouvant répondre aux importants besoins en puissance de calcul (de l’ordre du Gflops et même du Tflops) et en espace mémoire (de l’ordre du To et même du Po) des classes de problèmes citées plus haut. Les machines parallèles permettent au programmeur de disposer d’un nombre important de processeurs. Ce nombre peut être modulable suivant la puissance de traitement nécessaire. D’autres avantages caractérisent ces systèmes tels que leur grande disponibilité, leur meilleure tolérance aux pannes, leur grande flexibilité et surtout, ils permettent de partager de nombreuses ressources (processeur, mémoire, disque etc.) à travers un réseau. L’utilisation des machines parallèles introduit cependant un certain nombre de problèmes comme celui de l’équilibrage de charge qui sera étudié dans le chapitre suivant, celui de la distribution des données, de la maîtrise du coût des communications entre processeurs, etc. Ces problèmes ont un grand impact sur les performances des systèmes parallèles qu’ils risquent de dégrader s’ils ne sont pas correctement pris en charge.
Taxonomie des architectures parallèles et distribuées
La multiplication des architectures comportant plusieurs processeurs entraîne une certaine confusion dans les terminologies utilisées dans la littérature particulièrement lorsqu’il s’agit de caractériser les systèmes distribués et parallèles. Assez souvent, la frontière entre un système distribué et système parallèle n’est pas très nette. Aussi nous donnons cette caractérisation :
– Un système parallèle est un système composé de plusieurs processeurs fortement couplés, localisés sur la même machine, connectés par des liens de communication point à point à base de switch (Hypercube, Crossbar, Omega, grid . . . ) et qui travaillent à la résolution d’une même problème. Les multiprocesseurs (UMA, NUMA) et les MPPs appartiennent à cette catégorie.
– Un système distribué est un système composé de plusieurs processeurs physiquement distribués et faiblement couplés, reliés entre eux par un réseau conventionnel de communication (ATM, FDDI, Token Ring, Ethernet etc.) et qui collaborent à la résolution d’un ou plusieurs problèmes. Internet, les intranets, les systémes embarqués, les systèmes mobiles et les systèmes de téléphonie appartiennent à cette catégorie.
Il existe de nombreuses méthodes de classification des architectures parallèles et distribuées dont celle de Flynn qui est sans doute la plus populaire d’entre elles. Dans cette classification [2] basée sur le flux d’instructions et le flux de données deux principales classes sont établies. Il s’agit des machines SIMD dont les processeurs exécutent la même opération de façon synchrone sur des données différentes et des machines MIMD dont chaque processeur est autonome et exécute son propre programme sur ses propres données. Aujourd’hui les machines SIMD sont abandonnées au profit des machines MIMD qui offrent la souplesse nécessaire à la résolution de certains problèmes. Une classification plus fine des machines MIMD essentiellement basée sur l’organisation de la mémoire et les types d’interconnexion permet de distinguer deux grandes familles : les multiprocesseurs et les multi ordinateurs [4].
Les multiprocesseurs
Un multiprocesseur est un système informatique dans lequel deux ou plusieurs processeurs partagent l’accès total à une mémoire commune [3]. Les processeurs, la mémoire et les périphériques d’entrée et sortie sont reliés par un réseau d’interconnexion pouvant prendre la forme d’un bus commun, d’un switch crossbar ou d’un réseau multi-étages. Il n’y a qu’une seule copie du système d’exploitation qui tourne sur ce type d’architecture. Les multiprocesseurs sont de deux types : Les machines UMA et les machines NUMA.
Les multiprocesseurs UMA
Dans cet archiecture, il existe une mémoire unique, partagée par tous les processeurs. La mémoire est équidistante de tous les processeurs qui ont ainsi le même temps d’accès sur une référence mémoire donnée. Tous les processeurs partagent les ressources globales disponibles (bus, mémoire, E/S) mais peuvent avoir des caches privées. Toute opération effectuée sur la mémoire est immédiatement visible par l’ensemble des autres processeurs. Les machines UMA ont l’avantage d’être faciles à programmer. En effet elles supportent le modèle de programmation à mémoire partagée qui est proche du modèle séquentiel, ce qui simplifie le portage du code séquentiel vers le parallèle. De plus, il est plus facile de concevoir un système d’exploitation qui utilise les processeurs de manière symétrique. Cependant ces systèmes sont peu scalables, car au-delà de quelques dizaines de processeurs il devient très difficile de maintenir la cohérence des caches et un temps d’accès uniforme à la mémoire.
Les multiprocesseurs NUMA
Les machines NUMA sont des systèmes à mémoire partagée. Cependant ils ont la particularité d’avoir une mémoire physiquement distribuée, ce qui fait varier le temps d’accès en fonction de l’emplacement mémoire. Chaque processeur dispose d’une mémoire locale . L’ensemble de toutes ces mémoires forme un espace d’adressage global et unique, accessible à tous les processeurs. Il est plus rapide d’accéder à une mémoire locale qu’à celles distantes à cause du délai de latence associé au réseau d’interconnexion. Les machines NUMA ont l’avantage de supporter efficacement le modèle de programmation à mémoire partagée et d’être facilement scalables. En effet, les performances restent bonnes même avec des centaines de processeurs. Un inconvénient de ces systèmes est la complexité rencontrée au niveau matériel ou logiciel pour garantir la cohérence des données et un espace d’adressage global.
Les multi-ordinateurs
Un système multi-ordinateur est constitué par un ensemble de machines indépendantes reliées entre elles par un réseau d’interconnexion. Chaque machine possède une mémoire privée à laquelle elle accède directement . Les mémoire distantes ne sont pas directement adressables et les données sont partagées en envoyant explicitement ou en recevant des messages. La nature du réseau d’interconnexion varie d’un multi-ordinateur à un autre. Certains utilisent un bus de type Ethernet, FDDI, ATM alors que d’autres utilisent un switch de type grid, cube ou hypercube. Il y a une copie séparée du système d’exploitation sur chaque nœud du système. Les multi-ordinateurs se repartissent en deux catégories : les multi ordinateurs homogènes et les multi-ordinateurs hétérogènes.
Les multi-ordinateurs homogènes
Parfois appelés MPPs, ils sont constitués de processeurs identiques reliés par un réseau d’interconnexion unique qui utilise la même technologie partout. Ces systèmes sont particulièrement scalables puisqu’ils ne demandent pas un dispositif logiciel ou matériel pour maintenir la cohérence des données. Cependant ils sont relativement difficiles à programmer à cause de la charge supplémentaire dûe au placement et au partitionnement des données entre les différents processeurs, ainsi que les latences élevées dans certains types de réseaux.
|
Table des matières
Introduction
1 Aperçu sur le calcul haute performance
1.1 Calcul haute performance et parallélisme
1.2 Taxonomie des architectures parallèles et distribuées
1.2.1 Les multiprocesseurs
1.2.1.1 Les multiprocesseurs UMA
1.2.1.2 Les multiprocesseurs NUMA
1.2.2 Les multi-ordinateurs
1.2.2.1 Les multi-ordinateurs homogènes
1.2.2.2 Les multi-ordinateurs hétérogènes
1.3 Les modèles de programmation parallèle
1.3.1 Le modèle à échange de messages
1.3.2 Le modèle à mémoire partagée
1.3.3 Le modèle du parallélisme de données
1.4 Conclusion
2 Équilibrage de charge dans les systèmes parallèles et distribuées
2.1 L’équilibrage de charge dans les systèmes distribués et parallèles : problématique
2.2 Classification des approches d’équilibrage de charge
2.2.1 Approche statique et approche dynamique
2.2.1.1 Approche statique
2.2.1.2 Approche dynamique
2.2.2 Approche centralisée et approche distribuée
2.2.2.1 Approche centralisée
2.2.2.2 Approche distribuée
2.2.3 Approche source-initiative, approche receveur-initiative et approche symétrique
2.2.3.1 Approche source-initiative
2.2.3.2 Approche receveur-initiative
2.2.3.3 Approche symétrique
2.2.4 Approche adaptative et approche non adaptative
2.2.5 Approche coopérative et approche non coopérative
2.3 Les politiques d’équilibrage de charge
2.3.1 La politique d’information
2.3.2 La politique de sélection
2.3.3 La politique de transfert
2.3.4 La politique de localisation
2.4 Algorithmes d’équilibrage de charge
2.4.1 L’algorithme Shortest Expected Delay (SED)
2.4.2 L’algorithme Never Queue (NQ)
2.4.3 L’algorithme Gradient Model (GM)
2.4.4 L’algorithme Average Neighbourhood (AN)
2.4.5 L’algorithme Asynchronous Round Robin (ARR)
2.4.6 La méthode d’équilibrage hiérarchique
2.4.7 Les méthodes génétiques d’équilibrage de charge
2.4.7.1 GCTA (Genetic Central Task Assigner)
2.4.7.2 CBLB (Classifier-Based Load Balancer)
2.4.8 Les modèles de comportement cognitifs
2.5 Conclusion
3 Équilibrage de charge dans les algorithmes d’extraction de règles associatives
3.1 Le datamining : motivations et techniques
3.1.1 L’extraction de règles associatives
3.1.2 La recherche de motifs séquentiels
3.1.3 La classification et la régression
3.1.4 Le groupement (clustering)
3.1.5 La recherche de similitudes
3.1.6 La détection d’écarts
3.2 Parallélisation de l’extraction de règles associatives
3.2.1 L’algorithme IDD (Intelligent Data Distribution)
3.2.2 L’algorithme HPA (Hash Partioned Apriori)
3.2.3 L’algorithme CCPD (Common Candidate Partitioned Database)
3.2.4 L’algorithme pFP-Growth (parallel FP-Growth)
3.3 Les mécanismes d’équilibrage de charge dans les algorithmes HPA, IDD, CCPD et pFP-Growth .
3.3.1 Équilibrage de charge statique
3.3.1.1 Le partitionnement dans CCPD
3.3.1.2 Le partitionnement dans IDD
3.3.2 Équilibrage de charge dynamique
3.3.2.1 L’équilibrage de charge dans HPA
3.3.2.2 L’équilibrage de charge dans pFP-Growth
3.4 Étude comparative
3.4.1 Analyse qualitative
3.4.2 Comparaison
3.5 Conclusion
Conclusion
