Soutenance mémoire
Les Clusters
Pendant plusieurs années, les super-calculateurs s’imposèrent comme seule solution efficace aux problèmes de performances soulevés par de nombreux domaines. Néanmoins, le coût et l’infrastructure nécessaire au déploiement d’une telle machine rendaient la gestion de ces solutions relativement problématique. Dans les années 1990, l’idée d’abandonner les super-calculateurs commence à poindre avec la création de machines parallèles composées d’unités de calcul indépendantes et peu coûteuses : les clusters. Ces machines devinrent alors rapidement populaires du fait de leur très bon rapport performance/coût, comparées aux super-calculateurs propriétaires et de leur facilité de mise en œuvre. De manière synthétique, on définit un cluster [33] comme un système réalisant du calcul parallèle, qui consiste en un ensemble de calculateurs individuels interconnectés entre eux, et travaillant ensemble comme une unique ressource de calcul. Un noeud de calcul peut être un système monoprocesseur ou multiprocesseur comportant de la mémoire, des accès entrées/sorties, et un système d’exploitation. L’ensemble des noeuds de calcul apparaît alors comme un système unique du point de vue des applications. La figure 1.1 schématise cette définition. Un cluster est donc constitué des éléments suivants :
• Plusieurs machines individuelles (PC, station de travail ou machine SMP);
• un réseau d’interconnexion entre les différentes machines du cluster;
• un système d’exploitation sur chaque machine individuelle;
• un Middleware qui rend transparente la topologie du cluster;
• un environnement de programmation parallèle.
De très nombreux projets ont permis de mettre en avant les avantages de l’architecture cluster. Devant leur nombre, nous allons présenter ici les réalisations les plus marquantes historiquement et en terme de performances.
Beowulf
Le projet Beowulf [168, 167] a consisté en la réalisation d’une grappe de PCs sous LINUX inter-connectés par un réseau Ethernet et utilisant les protocoles de communication standards UNIX. Pour accroître les performances, plusieurs interfaces réseau sont utilisées simultanément. La principale innovation du projet Beowulf est son utilisation massive de composant standards , disponibles aisément. Parmi les différentes réalisations du projet Beowulf, on trouve la machine « theHIVE » [166] (fig.1.3). Mise en place par la NASA, « theHIVE » est un cluster composé de 1122 Pentium Pro bi-processeurs, 16 Pentium III Xeon bi-processeurs et 10 Pentium III Xeon quadri-processeurs. Ces 2316 processeurs sont répartis sur quatre sous-clusters et sont utilisés pour des applications de simulations physiques.
Les Clusters pour la vision
Le passage de la recherche à l’utilisation massive des clusters a été rendue possible par un certain nombre de facteurs [132, 169] comme l’amélioration rapide des performances de calcul des microprocesseurs, l’amélioration comparable de la bande passante mémoire disponible et l’émergence de réseaux très haut débit comme Myrinet, InfiniBand ou Ethernet GigaBit. Les clusters s’imposent désormais comme une alternative viable au super-calculateurs propriétaires. Dans le domaine de la vision par ordinateur, les clusters se démarquent notablement des architectures comme les GPU ou les FPGA[49]. Aussi pertinentes et ciblées que soient ces solutions, les grappes de calcul présentent en effet trois avantages :
• Rapport coût/performance : le coût total de la machine reste très inférieure à celui d’une machine dédiée de puissance équivalente notamment grâce à l’utilisation de matériel de type Commodity Off The Shelves.
• Extensibilité et résistance à l’obsolescence : une grappe étant construite à partir de machines individuelles interchangeables, la mise à jour d’un ou plusieurs noeuds d’une grappe reste une opération simple. De même,étendre la machine en lui ajoutant un ou plusieurs nœuds se fait facilement et à faible coût.
• Programmabilité : le développement sur un cluster se fait en utilisant des outils et méthodes standards, par opposition au outils et méthodes utilisés sur des architectures comme les FPGA ou les GPU (voir section 1.3 et 1.4). Ces avantages ont permis à de nombreux projets d’émerger et d’utiliser avec succès cette technologie. Les sections suivantes présentent de manière synthétique quelques travaux mettant en oeuvre une telle architecture pour l’implantation d’algorithme de vision artificielle.
GrImage
L’équipe PERCEPTION de l’INRIA Rhône Alpes a mis au point la plateforme GrImage [13], dont l’objectif est de fournir un outil d’expérimentation performant permettant d’acquérir de manière synchronisée un grand nombre de ux vidéo numériques, de traiter les données sur un cluster de PC et d’afficher les résultats en haute résolution. Elle est composé d’un cluster de 11 PC Dual Xeon et de 16 Dual Opteron reliés par un réseau ethernet Gigabit et d’un écran d’affichage de 2m par 2.7m composé de 16 vidéo projecteurs supportant une résolution de 4096×3072 pixels. Les applications de la plate-forme GrImage incluent la reconstruction 3D temps réel [80, 131] (fig. 1.7) et la réalité augmentée [12].
OSSIAN
Développée au LASMEA, la machine OSSIAN est un cluster conçu pour exécuter des algorithmes de vision et de traitement d’images dans un contexte embarqué [149]. Cette contrainte a fortement orienté le choix des éléments du cluster . OSSIAN était composée de quatre Apple G4 Cube — de faible encombrement —et était pourvue de deux bus de communications : un bus ethernet dédié aux communications et un bus FireWire 1394a dédié au transfert des données vidéos[91] en provenance d’une caméra numérique (fig. 1.11). Cette technique permet de limiter les temps de communication dus aux transferts des images entre le nœud recevant les données vidéos et les noeuds appliquant un algorithme sur ces données. Les PowerPC G4 étaient en outre équipés d’une unité de calcul SIMD intraprocesseur : l’extension AltiVec[142]. Cette extension SIMD permet d’obtenir des gains allant de 2 à 16 sur des opérations bas niveau. Au final, OSSIAN pouvait fournir des gains de l’ordre de 8 à 16 avec seulement quatre nœuds.
Réseaux logiques programmables
Les FPGA4 sont des circuits composés de nombreuses cellules logiques élémentaires configurables et composables par l’utilisateur. Celles-ci sont connectées de manière définitive ou réversible par programmation afin de réaliser la ou les fonctions voulues. L’intérêt étant qu’un même FPGA peut-être utilisé dans de nombreux systèmes électroniques différents. Cette architecture possède de nombreux avantages qui ont permis d’y développer des applications de traitement d’images [16, 60, 59] ou de vision [28]. En effet, étant entièrement configurables,les FPGA permettent aux développeurs de spécifier une architecture en complète adéquation avec les algorithmes de vision développés. Ils permettent aussi de réaliser de manière câblée un grand nombre d’opérations. Enfin, la possibilité d’utiliser des schémas de mémoire et d’instruction divers (module DSP, communication par bus ou point à point) permet rapidement d’exploiter plusieurs niveaux de parallélisme, en particulier le parallélisme de données régulier massif. Malheureusement, ces avancées n’ont pas permis de développer des systèmes à base de FPGA permettant d’exécuter des algorithmes de vision de très grande complexité. Bien que souples et performants, les FPGA restent limités par des soucis de programmabilité. En effet, à ce jour, la mise en oeuvre de programmes sur une plate-forme de type FPGA nécessite l’utilisation de langages de description comme VHDL, ce qui rend difficile l’utilisation généralisée de ces architectures.
|
Table des matières
Introduction
1 Architectures dédiées à la vision
1.1 Les Clusters
1.1.1 NOW : Networks Of Workstations
1.1.2 Beowulf
1.1.3 Blue Gene
1.2 Les Clusters pour la vision
1.2.1 Virtualized Reality – 3D ROOM
1.2.2 GrImage
1.2.3 ViROOM
1.2.4 Beobots
1.2.5 OSSIAN
1.3 Réseaux logiques programmables
1.4 Cartes d’accélération graphique
1.5 Conclusion
2 La machine BABYLON
2.1 Architecture matérielle
2.1.1 Noeud de calcul
2.1.2 Réseau de communication
2.1.3 Topologie des réseaux de communications
2.2 Synopsis général
2.2.1 Architecture du POWER PC G5
2.2.2 Spécification du processeur PPC 970
2.2.3 Spécifications de l’extension SIMD ALTIVEC
2.2.4 Conclusion
2.3 La bibliothèque d’acquisition vidéo C+FOX
2.3.1 Interface utilisateur
2.3.2 Gestion de la multi-diffusion
2.4 Outil de développement MIMD
2.4.1 Principes de MPI
2.4.2 Exemple d’utilisation
2.4.3 Conclusion
2.5 Outils de développement pour architectures SMP
2.5.1 MPI
2.5.2 Open MP
2.5.3 pThread
2.5.4 Conclusion
2.6 Outil de développement SIMD
2.6.1 Performances
2.6.2 Mise en oeuvre
2.6.3 Conclusion
2.7 Application : Stabilisation de ux vidéo
2.7.1 Description de l’algorithme
2.7.2 Implantation séquentielle
2.7.3 Stratégie de parallélisation
2.7.4 Performances
2.7.5 Conclusion
2.8 Modèle de performance
2.8.1 Loi d’Amdahl
2.8.2 Loi de Gustafson-Barsis
2.8.3 Modèle de performance hybride
2.8.4 Mise en oeuvre
2.9 Conclusion
3 Outils logiciels pour le calcul parallèle
3.1 Modèles et outils pour la programmation SIMD
3.1.1 L’Apple Accelerate.Framework
3.1.2 VAST
3.2 Modèles et outils pour la programmation MIMD
3.2.1 Les squelettes algorithmiques
3.2.2 Les Design Patterns
3.2.3 Autres approches
3.3 Discussion
3.3.1 Approches basées sur des nouveaux langages
3.3.2 Approches basées sur des générateurs de code
3.3.3 Approches basées sur des bibliothèques
3.3.4 Solution proposée
4 La bibliothèque E.V.E.
4.1 Modèle de programmation
4.1.1 Problématique de l’implantation orientée objet
4.2 Interface utilisateur
4.2.1 Les classes array et view
4.2.2 Choix des options d’optimisations
4.2.3 Fonctions disponibles
4.3 Implantation
4.3.1 L’évaluation partielle en C++
4.3.2 Les Expression Templates
4.3.3 Détermination de la «vectorisabilité» d’une expression
4.3.4 Optimisations spécifiques
4.4 Évaluations des performances
4.4.1 Accélération SIMD
4.4.2 Optimisation des compositions d’opérateurs
4.5 Étude de cas
4.5.1 Présentation de l’algorithme
4.5.2 Implantations séquentielles
4.5.3 Implantations optimisées
4.5.4 Discussion
4.6 Conclusion
5 La bibliothèque QUAFF
5.1 Modèle de programmation
5.1.1 Définition formelle d’une application
5.1.2 Squelettes dédiés au parallélisme de contrôle
5.1.3 Squelettes dédiés au parallélisme de données
5.1.4 Squelettes dédiés à la structuration de l’application
5.1.5 Exemple de mise en œuvre
5.2 Interface utilisateur
5.2.1 Définition des tâches séquentielles
5.2.2 Interfaces des squelettes
5.2.3 Définition des entrées/sorties
5.2.4 Définition d’une application QUAFF
5.3 Implantation
5.3.1 Manipulation des listes de fonctions
5.3.2 Mise en œuvre du parallèlisme
5.3.3 Gestion des communications
5.4 Validation
5.5 Conclusion
6 Applications à la stéréovision
6.1 Principe de la stéréo-vision
6.1.1 Modèle sténopé des caméras
6.1.2 Principes géométrique de la stéréo-vision
6.2 Reconstruction 3D temps réel
6.2.1 Implantation séquentielle
6.2.2 Implantation parallèle
6.2.3 Résultats
6.3 Détection et suivi 3D temps réel de piétons
6.3.1 Approche probabiliste du suivi d’objets
6.3.2 Le filtre à particules
6.3.3 Implantation séquentielle
6.3.4 Implantation parallèle
6.3.5 Résultats
6.4 Conclusion
Conclusion et perspectives
Annexes
I templates et méta-programmation
I.1 Définitions
I.1.1 Classe template
I.1.2 Fonction template
I.1.3 Spécialisation des templates
I.2 Principes de méta-programmation
I.2.1 Arithmétique statique
I.2.2 Structure de contrôle statique
I.2.3 Fonctions de manipulations de types
I.3 Méta-programmes usuels
I.3.1 Adaptateur valeur/type
I.3.2 Opérateurs logiques statiques
I.3.3 Test de conversion implicite
I.3.4 Levée d’erreurs à la compilation
I.4 Discussion
II prime_sieve par E. Unruh
III Exemple de fonction ALTIVEC complexe
IV Opérations sur les listes statiques de types
IV.1 Evaluation de la taille d’une liste de type
IV.2 Accés aléatoire aux éléments d’une liste de type
IV.3 Application d’une méta-fonction à une liste
IV.4 Retrait d’élément à une liste de type
IV.5 Ajout d’élément à une liste de type
IV.6 Extraction d’une sous-liste
IV.7 Accés à l’élément d’un tuple
Bibliographie
Télécharger le rapport complet
