Algorithmes de la morphologie mathématique pour les architectures orientées flux

Évolution en chiffres

Une étude des activités du secteur des circuits intégrés effectuée en 1965 par Gordon Moore lui a permis d’estimer l’évolution de ce secteur comme une tendance exponentielle. Moore se basait sur le nombre de composantes par circuit intégré et il a inclus dans son observation les circuits mis sur le marché pendant les années 1959-1965. Il a publié ensuite un articleMoo65 où il expliquait que les conditions pour l’évolution du secteur étaient favorables et a prévu, à l’horizon des 10 années suivantes, une croissance exponentielle par un facteur 2 chaque année. La formule présentée par Moore exprimait une approximation des données mesurées et essayait de les extrapoler dans le temps. Les années suivantes ont vérifié que Moore avait eu raison en ce qui concerne la croissance exponentielle du nombre de composantes par circuit mais ont également corrigé le facteur 2 prévu par Moore pour chaque année à un facteur 2 pour tous les 18 à 24 mois. Cette formule est devenue célèbre, elle s’est inscrite dans l’histoire de l’informatique d’une façon informelle comme la Loi de Moore et elle avait, comme elle l’a toujours, un grand succès non seulement parmi le public populaire mais également dans le cercle scientifique, citons comme preuve la réédition de l’article original de Moore en 1998Moo98 par l’organisation IEEE. Pour aller plus loin dans cette philosophie, divers auteurs déclinent cette loi sur d’autres types de données connexes aux processeurs. Il est courant d’utiliser les diagrammes de l’évolution de divers paramètres dépendant du temps. On parle ainsi de vecteurs de MooreGro02 et on les utilise pour démontrer les aspects plus détaillés de la production des processeurs tels que la lithographie, la consommation d’énergie, les performances, les chiffres d’affaires.

Processeurs à usage général – les GPP et les GPPMM

Sous le terme de processeurs à usage général nous comprenons les processeurs les plus universels possible qui sont capables d’exécuter plusieurs types de calcul différents. L’universalité de ces processeurs est gagnée au préjudice de la spécialisation et par conséquent de la performance, même si celle-ci doit rester raisonnable vis-à-vis de l’utilité applicative de ces processeurs. Pour se référer à un tel processeur par la suite, nous allons utiliser l’abréviation GPP, dérivée d’un terme anglais General Purpose Processor. Nous nous intéresserons aux processeurs de ce type, plus précisément à une catégorie de ces processeurs destinée principalement à l’usage des particuliers. C’est une catégorie très puissante en ce qui concerne le nombre d’unités vendues mais aussi une catégorie présentant certaines particularités. Notamment il s’agit de contraintes sur
• le prix qui doit être, pour des raisons économiques, plutôt en bas d’échelle,
• les dimensions qui ne doivent pas être excessives ou qui doivent être même les plus petites possible dans le cas où nous visons les produits portables,
• la consommation d’énergie qui est une contrainte imposée pour des raisons soit pratiques (besoin d’un système de refroidissement particulier ou non ?), soit financières (coût d’électricité) soit de durée d’autonomie de l’alimentation (produits portables). Nous trouvons ces processeurs commercialisés sur le marché de grand public au cœur des ordinateurs professionnels, personnels ou portables, incorporés dans les produits nomadiques. Cependant, nous pouvons les trouver aussi bien éloignés du grand public dans les solutions non destinées à l’usage personnel tels que les serveurs informatiques ou également les processeurs embarqués et dans des applications variées, industrielles, civiles ou militaires.

Processeurs graphiques – les GPU

Une place très particulière parmi les architectures des processeurs est détenue par les processeurs graphiques, les GPU (dérivé d’un terme anglais Graphic Processing Unit). Il s’agit des processeurs qui étaient initialement utilisés à l’accélération de la visualisation des scènes 3D, très exigeante en ce qui concerne le nombre d’opérations effectuées et la spécificité du calcul. Le calcul sur les GPU se distingue d’abord par l’utilisation d’un ensemble limité mais bien choisi d’un certain nombre de fonctions mathématiques (sin, cos, puissance, la racine carrée, produit scalaire, etc.), ensuite par le procédé de calcul qui utilise naturellement les types vectoriels (de 3 ou 4 composantes) et finalement par l’utilisation courante des opérations en virgule flottante. Tout cela est encore majoré par la contrainte du temps dans le cas de la visualisation 3D interactive et/ou en temps réel. Ce calcul spécifique, réuni  avec la masse d’informations traitées lors de ce calcul, était (et est toujours) inadapté aux architectures du calcul général, même si ces dernières auraient pu l’effectuer en dépit de la rapidité.

Puisque ni les GPP, ni leurs successeurs GPPMM, ne pouvaient satisfaire la demande importante pour la visualisation devenue de plus en plus exigeante, une nouvelle catégorie de processeurs dédiés a vu le jour, la catégorie des processeurs graphiques destinés à l’accélération du calcul pour la visualisation 3D. Ces processeurs étaient et sont toujours des accélérateurs, c’est-à-dire des processeurs secondaires dédiés, qui restent fortement liés aux processeurs principaux (GPP). En effet, la cohabitation GPP-GPU a donné ce que l’on en avait espéré. On a séparé la problématique de la visualisation à deux parties : la partie de haut niveau est représentée par le GPP et on l’utilise pour l’exécution de l’application de la visualisation. La deuxième partie de niveau bas est représentée par ces accélérateurs dédiés et spécialisés qui s’occupent du calcul intensif. Toutes les architectures actuelles des ordinateurs personnels utilisent les accélérateurs graphiques ou, au moins, des sous-systèmes graphiques si on ne peut pas les classer dans la catégorie des accélérateurs au vrai sens du mot.

Au-delà de l’horizon

Nous avons utilisé la leçon de l’histoire concernant la Loi de Moore pour bien souligner le dynamisme exponentiel d’évolution des performances des puces électroniques durant les 40 dernières années. Ce dynamisme n’a pas cessé depuis, au contraire, et nous pouvons déjà entrevoir les grands changements qui nous attendent dans les années à venir. Il est quasiment inutile de remarquer que ce que nous pouvons fabriquer aujourd’hui est loin de ce que pouvaient espérer les membres de l’équipe de Bell Labs quand ils ont découvert l’effet de transistor en 1947. La question que nous pouvons nous poser est si dans 40 ans nos successeurs, eux aussi, considéreront notre époque de la même manière que nous regardons aujourd’hui l’époque de Moore. Nous pouvons nous demander si l’idée exprimée par Moore en 1965 pour le nombre des transistors par une seule puce électronique peut encore résister aux innovations technologiques et aux nouvelles tendances dans le design d’architectures. Moore lui-même la critiquait avec le résultat plutôt optimiste en 2003 dans son articleMoo03a, Moo03b intitulé No exponential is forever : But « Forever » Can Be Delayed !

En effet, l’avenir proche est assez prévisibleFH05. Comme  l’indique International Technology Road map for SemiconductorsITR, le dynamisme de la croissance exponentielle pourrait ralentir dans les années à venir et être égal à 3 années pour le doublement du nombre des transistors. Il devrait persister sous cette forme pendant au moins 10 années. Autour de 2020, quand on atteindra les contraintes physiques de fonctionnement de la technologie basée sur les charges électriques, d’autres approches qui ne seraient pas limitées par ces contraintes pourraient rallonger la durée de la Loi de Moore. En même temps, les approches parallèles commencent à se présenter comme un phénomène quotidien. Les processeurs existants avec plusieurs cœurs destinés aux applications parallèles et d’autres solutions variées qui suivent cette philosophie et sont étudiées par les chercheurs en sont la preuve. Il est fort probable que dans un avenir très proche nous allons nous retrouver couramment aux prises avec les solutions du grand public composées de plusieurs processeurs physiques, eux-mêmes déjà dotés d’une structure parallèle à l’intérieur.

En ce qui concerne les GPU, nous pouvons constater qu’ils se sont transformés en processeurs programmables, très adaptés à certains types du calcul et qu’ils commencent à être sérieusement utilisés même pour les tâches qui ne leur étaient pas destinées à l’origine. Les chances pour une future utilisation plus massive des GPU dans l’avenir semblent très bonnes. Ce qui parle dans leur intérêt c’est la façon implicitement parallèle de programmation et d’exécution, propres à ces processeurs. Leur architecture est adaptée à ce travail et peut être facilement élargie au niveau de la puce sans contredire la philosophie de la structure.

Table des matières

Introduction
1 Motivation
1.1 Évolution en chiffres
1.2 Processeurs à usage général – les GPP et les GPPMM
1.3 Processeurs graphiques – les GPU
1.4 Au-delà de l’horizon
2 État de l’art
3 Architectures
3.1 Taxonomie des architectures
3.1.1 Taxonomie de Flynn
3.1.2 Taxonomie de Duncan
3.2 Facteurs influant la performance
3.2.1 Structure de l’architecture
3.2.2 Fréquence de(s) l’unité(s) de calcul
3.2.3 Structure, capacité et fréquence des mémoires
3.2.4 Parallélisation des données
3.2.5 Parallélisation d’exécution
3.2.6 Écartement et latence des instructions
3.2.7 Instructions spécialisées
3.2.8 Nombre de registres et leur désignation
3.2.9 Approche à l’implémentation des algorithmes
3.3 Consommation d’énergie
3.4 Modèle stream du calcul et les architectures associées
3.4.1 Calcul sur les streams
3.4.2 Architectures stream
3.4.3 Architecture de von Neumann et ses successeurs utilisés pour le calcul stream
3.4.4 Calcul stream sur les architectures SWAR à plusieurs fils
3.4.5 Pipeline graphique et les GPUs
3.4.6 Calcul sur les flux de données avec les GPU
4 Formalisme fonctionnel adopté pour la morphologie mathématique
4.1 Approche fonctionnelle et impérative
4.2 Haskell et les bases des langages fonctionnels
4.2.1 Syntaxe du Haskell
4.2.2 Fonctions de base du Haskell
4.3 Primitives de stockage et de représentation des données
4.3.1 Types de base
4.4 Primitives du calcul comme skeletons algorithmiques
4.4.1 Primitives du calcul séquentiel
4.4.2 Primitives du calcul parallèle
4.4.3 Paquetage et dépaquetage des arrays pour le traitement SIMD
4.4.4 Sens du parcours, passage d’un array à un flux de données et vice versa
4.4.5 Concept des « superpixels »
4.5 Modèle formel du traitement en pipeline graphique
4.5.1 Types de données utilisés dans le modèle
4.5.2 Primitive de calcul avec le pipeline graphique
4.5.3 Modèle du pipeline graphique des GPU
4.6 Primitives de la morphologique mathématique
4.6.1 Images dans la morphologie mathématique
4.6.2 Grilles et voisinages
4.6.3 Éléments structurants
4.6.4 Extraction du voisinage
4.6.5 Kernels de la morphologie mathématique travaillant sur le voisinage local
4.6.6 Opérations du voisinage local avec un masque
4.6.7 Travail sur le voisinage avec les superpixels et les skeletons algorithmiques
5 Algorithmes de voisinage non dépendants du sens du parcours
5.1 Algorithmes élémentaires pour les GPP
5.1.1 Approche naïve à l’implémentation des opérations sur le voisinage
5.1.2 Division du problème en traitement de l’intérieur et en traitement du bord
5.1.3 Généralisation du travail sur le voisinage
5.1.4 Approche des superpixels, algorithmes aux kernels complexes qui exploitent la localité des données
5.2 Algorithmes élémentaires pour les GPPMM
5.2.1 Skeletons algorithmiques GPPMM de base
5.2.2 Algorithmes concrets GPPMM de base de la morphologie mathématique
5.2.3 Algorithmes SIMD basés sur l’approche des superpixels
5.3 Algorithmes géodésiques pour les GPP/GPPMM
5.3.1 Idée de base
5.3.2 Itérations, fin de propagation
5.3.3 Note sur le travail géodésique avec les superpixels
5.3.4 Travail SIMD avec les vecteurs paquetés
5.4 Algorithmes pour les GPU
5.4.1 Traitement des bords de la texture sur les GPU
5.4.2 Approche utilisant les opérations de Minkowski
5.4.3 Approche utilisant l’échantillonnage complexe des textures dans l’unité de traitement des fragments
5.4.4 Approche utilisant les point sprites
5.4.5 Description des algorithmes pour les processeurs graphiques par le formalisme
fonctionnel
5.5 Résultats expérimentaux
5.6 Récapitulation
6 Permutation SIMD des arrays appliquée au changement de stockage des données vectorielles
6.1 Transpositions et rotations des arrays
6.1.1 Définitions des transpositions et des rotations
6.2 Approche macro blocs aux transpositions et rotations
6.2.1 Découpage des arrays en macro blocs et leur recollage
6.2.2 L’algorithme générique travaillant sur les macro blocs
6.3 Algorithmes rapides SIMD de transposition et de rotation
6.3.1 Fonctions shuffle
6.3.2 Découpage sur les macro blocs et leur recollage sur les architectures SWAR
6.3.3 Shuffles utilisés pour les transpositions et rotations d’un macro bloc
6.3.4 Algorithme complet pour les transpositions et les rotations par SIMD
6.4 Notes sur l’implémentation, résultats expérimentaux
6.5 Récapitulation, perspectives
7 Algorithmes de voisinage dépendant du sens prédéfini de parcours de l’image
7.1 Particularité du sens du parcours pour le traitement SIMD du voisinage
7.2 Skeletons applico-réductifs pour la propagation
7.3 Skeleton algorithmique de la propagation SIMD en 4-voisinage
7.3.1 Propagation à l’intérieur d’un macro bloc
7.3.2 Phase généralisée de la propagation
7.3.3 Propagations SIMD sur l’image entière pour le 4-voisinage et la grille carrée
7.3.4 Calcul de la fonction distance
7.3.5 Calcul des nivellements
7.4 Approche utilisant les macro blocs avec la transposition directe
7.5 Notes sur l’implémentation, résultats expérimentaux
7.6 Récapitulation
Conclusion

Télécharger le rapport complet