Soutenance mémoire
Depuis les débuts de l’informatique, les besoins en puissance de calcul n’ont cessé d’augmenter. Si des domaines aussi variés que la simulation météorologique, la dynamique des uides ou la modélisation en physique des particules ont su tout d’abord utiliser au mieux les ressources des premiers ordinateurs, leurs besoins en puissance ont rapidement excédé ce que les machines séquentielles étaient capables de fournir .
La vision arti cielle
Parmi les applications gourmandes en puissance de calcul, on trouve celles de la vision artificielle. La vision artificielle, ou «vision par ordinateur», est une discipline qui consiste à analyser une image ou un ux d’images afin d’en extraire des informations de haut niveau. Plus explicitement, un processus de reconnaissance [24, 75] similaire à celui opéré par l’être humain va identifier les objets contenus dans ces images par l’extraction et l’analyse de caractéristiques abstraites (comme des primitives géométriques) à partir des valeurs de chaque pixel. Les applications de la vision artificielle sont très nombreuses. On peut citer par exemple le contrôle de la qualité sur une chaîne de production, l’identification d’un individu par biométrie, le diagnostic médical, la classification de terrains à partir d’images satellites ou la commande de robots mobiles. Au regard de ces applications, on distingue deux types de contraintes.
Le volume de données traité
La quantité de données traitée par un algorithme de vision artificielle peut croître très rapidement. Si l’on considère un ux vidéo VGA cadencé à 25 images/secondes, il s’agit de traiter 3 × 640 × 480 octets toutes les 40 ms, soit un débit d’entrée/sortie de 22Mo par seconde. Si le traitement consiste à appliquer 500 opérations ottantes à chaque pixel de l’image la puissance de calcul nécessaire est de l’ordre de 10 GFLOPS; une puissance à comparer aux puissances maximales offerte par des architectures séquentielles classiques qui avoisinent les 3 GFLOPS.
La réactivité des applications
Les algorithmes de vision artificielle sont rarement utilisés seuls. Ils s’intègrent en général au sein d’un système qui utilise les informations qu’ils fournissent pour prendre une décision vis à vis de leur environnement proche. Ainsi, pour de nombreuses applications comme la robotique par exemple, le traitement «à la volée» des capteurs image devient une nécessité. Même si cette disposition n’implique pas forcément le traitement exhaustif de toutes les images issues des capteurs, elle soumet ce type de système à de fortes contraintes temporelles. Il devient nécessaire que l’intervalle de temps séparant l’acquisition de l’image et la réaction du système soit suffisamment court pour que l’environnement n’ait pas évolué de manière significative pour l’algorithme. Il est aussi important que ce temps de traitement soit déterministe. On se retrouve alors dans un contexte «temps réel», à savoir que l’algorithme de vision doit être exécuté à une cadence permettant de garantir la pertinence des informations générées vis à vis de l’environnement. Par exemple, une application de détection d’obstacle embarquée dans un véhicule se doit de répondre dans un intervalle de temps compatible avec l’intervalle de temps nécessaire à la réaction envisagée sur le véhicule.
Dans la plupart des cas «réalistes», ces deux facteurs – volume de données et réactivité – se combinent et augmentent d’autant la puissance de calcul nécessaire. Pour satisfaire ces besoins, plusieurs solutions sont envisageables. Les plus simples consistent soit à simplifier l’algorithme afin de limiter la quantité de calculs effectués ou à dégrader les images afin de réduire le volume de données à traiter. Ces solutions sont facilement applicables mais posent des problèmes de précision ou de robustesse qui peuvent rendre les algorithmes inutilisables. Une autre solution consiste à attendre la génération suivante de microprocesseurs. En effet, les progrès en terme d’intégration des transistors au sein des microprocesseurs ont longtemps garanti une évolution rapide de la puissance des ordinateurs. La loi de Moore [133] prévoyait en effet que, tous les 18 mois, le nombre de transistors par unité de surface au sein des processeurs doublerait. Mais deux phénomènes ont freiné cette évolution depuis le milieu des années 90 : les difficultés croissantes rencontrées par les technologies d’intégration [171] et le fait que les technologies des autres composants annexes des machines (mémoires vives, bus etc …) ne suivaient pas la même évolution. Ce ralentissement rend problématique le recours à des machines de type PC pour des applications de vision artificielle soumises à de fortes contraintes temporelles et demande à se tourner vers un autre type de solution.
Intérêt du parallélisme
Une de ces solutions est de faire travailler simultanément plusieurs unités de calculs et de coordonner leurs puissances pour résoudre un même problème : c’est à dire mettre en oeuvre une machine parallèle. De nombreuses applications de ce principe existent et diverses classifications de ce type de machines ont été proposées [162, 194]. Un premier niveau de classification consiste à distinguer les machines parallèles constituées de plusieurs ordinateurs reliés entre eux par un réseau de communications — on parle alors de multi-computer – et les machines parallèles constitué de plusieurs processeurs intégrés au sein d’une unique machine et se partageant une mémoire centrale — on parle alors de machine multi-processeurs ou SMP . Une classification plus synthétique est proposée par Flynn [77] et se base sur la quantification des ux de données et des ux d’instructions de la machine. On distingue alors quatre types de machine :
• SISD : Single Instruction, Single Data
Ces machines sont processeurs séquentiels conçus selon une architecture de Von Neumann [193] classique. Encore récemment, on incluait dans cette catégorie les processeurs équipant la plupart des machines personnelles. Depuis le milieu des années 90, la multiplication des unités de traitement annexes et des pipelines intra-processeurs au sein de ces machines a rendu oues les limites de cette classification.
• SIMD : Single Instruction, Multiple Data
Dans cette classe d’architecture, plusieurs unités de traitement exécutent simultanément un même ot d’instruction, issue d’une seule unité de contrôle sur des ots de données différents. Les machines de type CM-2 [98] datant des années 80 sont des exemples d’anciennes architectures SIMD. De nos jours, ce type de calculateur SIMD a été plus ou moins abandonné en raison de son manque de souplesse. Les techniques ainsi développées ont été remises au goût du jour dans des architectures plus exibles. Un exemple de ce recyclage sont les technologies de type SWAR3 qui ont permis le développement d’extension dites « vectorielles » ou « multimédia » comme MMX/SSE [146] d’Intel ou AltiVec [128, 142] de Motorola/IBM.
• MISD : Multiple Instruction, Single Data
Pour ces structures, les données transitent de processeur en processeur en subissant à chaque étape un traitement différent. Les calculateurs systoliques [48] sont de bons exemples de ces architectures. Ce type d’architecture reste néanmoins difficile à mettre en oeuvre et est souvent dédié à des tâches bien spécifiques.
• MIMD : Multiple Instruction, Multiple Data
Dans ces architectures, les processeurs effectuent simultanément des instructions différentes sur des données différentes. Cette forme de parallélisme est la plus répandue et a fait l’objet de nombreuses études. A titre d’exemple, on peut citer les calculateurs de type CRAY T3D [19], la CM5 [30] ainsi que les architectures de types cluster .
Cette classification ne rend néanmoins pas compte de la grande diversité des machines MIMD. Pour compléter cette classification, Johnson [105] a proposé une classification des machines MIMD basée sur la structure de leur mémoire — distribuée (DM) ou partagée (GM) — et sur les mécanismes utilisés pour les communications — variables partagées (SV) ou passage de message (MP). Ces deux classifications — Flynn et Johnson — se complètent et englobent ainsi une large partie du bestiaire des machines parallèles .
Les machines parallèles peuvent répondre aux besoins de puissance de certaines applications de vision artificielle. Néanmoins, plusieurs aspects spécifiques provenant aussi bien de l’aspect matériel que de l’aspect applicatif font de l’utilisation de ce type d’architecture dans ce cadre algorithmique un sujet relativement ouvert. Parmi l’ensemble des applications de la vision artificielle, nos travaux se focalisent sur le développement et la mise en œuvre d’une architecture parallèle dédiée à l’exécution d’algorithmes de vision opérant «à la volée» d’un ux vidéo.
L’architecture matérielle
La vision artificielle impose des contraintes différentes de celle des applications typiquement développées sur des machines parallèles classiques. La place prépondérante des capteurs vidéos et leur importance au sein du processus de calcul font que leur intégration au sein d’une machine parallèle nécessite d’adapter cette dernière afin de permettre un accès rapide et efficace aux données vidéos provenant de ces capteurs. En outre, les besoins de la vision artificielle nécessitent de concevoir une machine parallèle très performante.
L’environnement de développement
En sus de ces aspects architecturaux, il est important de garder à l’esprit que le développement d’applications parallèles est une tâche complexe. S’ajoute alors aux problèmes de performances une problématique de programmabilité. En effet, les développeurs de la communauté Vision ont à leur disposition un ensemble de modèles et de solutions logicielles éprouvés répondant aux problèmes récurrents de leur discipline. La programmation d’une machine parallèle peut s’avérer très différentes de ces modèles classiques et nécessiter une adaptation souvent problématique.
Architectures dédiées à la vision
« The hardest thing is to go to sleep at night, when there are so many urgent things needing to be done. A huge gap exists between what we know is possible with today’ s machines and what we have so far been able to nish» Donald Knuth .
De très nombreuses architectures ont été proposées pour résoudre les problèmatiques du calcul haute performance en général et de la vision artificielle en particulier. Devant la profusion des réalisations dans ce domaine [29, 145], il est bien entendu illusoire de vouloir dresser ici un panorama exhaustif. Nous allons donc nous limiter à présenter les grands types d’architectures qui sont actuellement exploitées : les clusters, les solutions à base de réseaux logiques programmables et celles à bases de processeurs graphiques.
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.
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.
NOW : Networks Of Workstations
Le projet NOW (Networks Of Workstations) [15] de l’Université de Berkeley, a consisté à utiliser un grand nombre de stations de travail individuelles (quelques centaines), à les raccorder par un réseau rapide, et à y installer une bibliothèque de communication performante, afin d’obtenir des performances analogues à celles d’une machine massivement parallèle, mais avec un coût réduit. L’expérimentation NOW à Berkeley a rassemblé 100 Ultra Sparc et 40 Sparc Stations Sun sous SUN Solaris, 35 PC sous Windows NT et Unix, 300 stations de travail HP, et entre 500 et 1000 disques, le tout connecté par un réseau de commutateurs Myrinet .
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 » . 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.
|
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
Conclusion
