Modèle stream du calcul et les architectures associées

Télécharger le fichier pdf d’un mémoire de fin d’études

Taxonomie des architectures

Pour pouvoir comprendre dans quel domaine se placent les algorithmes décrits dans les parties sui-vantes, il nous faut spécifier la classe des architectures du calcul appropriées. C’est pourquoi nous allons présenter les taxonomies – les systèmes de classification – des architectures parallèles.
Les différenciations suivantes gardent une très bonne généralisation par rapport au fonctionnement exact des machines parallèles ce qui nous permettra d’obtenir une protabilité entre différentes implémen-tations sur des architectures précises, soit existantes, soit des architectures à concevoir, et élargir ainsi le champ d’applications possibles de nos algorithmes.
Il existe plusieurs systèmes de classification des architectures existantes. Pour une liste exhaustive des travaux portant sur la caractérisation des architectures, parallèles ou séquentielles, nous recommandons un article comparatifBD93 des différentes taxonomies.

Taxonomie de Flynn

Parmi les diverses façons de caractériser les architectures, celle de FlynnFly66 détient une place privi-légiée car elle est toujours perçue comme une façon simple et presque intuitive de la description du mode de fonctionnement d’une machine. Elle caractérise les machines selon le type de flux d’instructions et de flux de données.
En dépit de cette simplicité, cette taxonomie n’est pas l’une des plus discriminatoires et présente ainsi de grands désavantagesCT93, principalement dues à l’absence de caractérisation du système de la mémoire. Malgré les travauxDun90, Ski98 essayant de compléter ce système de caractérisation, la taxo-nomie de Flynn reste toujours le premier outil de description dans un grand nombre de publications scientifiques. Nous la mentionnons pour pouvoir introduire et expliquer les termes qui seront utilisés par la suite.
La Taxonomie de Flynn classe les architectures en ces 4 catégories :
• architectures SISD et SISD confluant (Single Instruction (stream), Single Data (stream)) – à flux simple d’instructions et à flux simple de données,
• architectures SIMD (Single Instruction (stream), Multiple Data (stream)) – à flux simple d’instruc-tions et à flux multiple de données,
• architectures MISD (Multiple Instruction (stream), Single Data (stream)) – à flux multiple d’ins-tructions et à flux simple de données,
• architectures MIMD (Multiple Instruction (stream), Multiple Data) – à flux multiple d’instructions et à flux multiple de données.

Architecture SISD et SISD confluant

Dans ce type d’architectures, nous pouvons distinguer le mécanisme sériel de décodage d’instructions et, par conséquent, le traitement d’un seul flux d’instructions. Une seule donnée peut être traitée dans le laps de temps Δt , dérivé du cycle d’horloge et lié ainsi à la fréquence de l’architecture.

Le type d’architectures SISD a un fonctionnement séquentiel et n’est pas, en effet, explicitement parallèle. Mais il englobe également le traitement SISD confluant et inclut ainsi les architectures avec un pipeline dont la structure est illustrée sur la fig 3.1(a).

Un pipeline est utilisé pour maximiser l’usage des blocs d’exécution en divisant une opération d’une granularité donnée en une séquence sérielle des opérations de granularité plus fine. Le traitement est toujours effectué avec un seul flux d’instructions sur un seul flux de données. Seule une donnée peut être traitée par une unité de traitement distincte dans l’intervalle Δt . Avec cette structure, l’unité du calcul parvient à une augmentation de bande passante exprimée par le nombre d’instructions par seconde. Nous présentons un exemple pratique d’exécution en pipeline du processeur SH-5, q.v. fig 3.2.

Architecture SIMD

Dans ce type d’architectures, cf. fig 3.1(b), un seul flux d’instruction est utilisé pour contrôler le fonc-tionnement de plusieurs unités élémentaires du calcul. Ainsi, l’architecture est capable de traiter plusieurs données à la fois. Les données y arrivent comme un flux multiple, composé d’un certain nombre d’élé-ments de base. On classe dans cette catégorie également les machines vectorielles, les réseaux cellulaires et les réseaux systoliques.

– jusqu’à 3 phases d’exécution, fonction exacte (mémoire, calcul en entiers, en virgule flottante) dépend de l’instruction, WB (writeback) – écriture des résultats dans le registre

Plus généralement, nous pouvons parler dans le même cadre d’une architecture SPMD (Single Pro-gram, Multiple Data) – architecture à un programme et à données multiples – qui a la même configuration mais les unités élémentaires du calcul exécutent d’une façon synchrone une même séquence d’instruc-tions ou un même programme plus complexe. La façon synchrone d’exécution est ici indispensable et constitue le lien avec la catégorie SIMD travaillant de la même façon au niveau d’instructions.

Architecture MISD

Dans ce type d’architectures, plusieurs instructions sont destinées à traiter la même donnée. Chaque unité reçoit une instruction spécifique.

Ce type inclut également le traitement en pipeline où la tâche est divisée en étapes distinctes et où nous ne pouvons pas identifier plusieurs unités du calcul qui seraient indépendantes, une dédiée à chaque étape. En contraste avec le pipeline classé sous SISD confluent où les blocs du pipeline étaient commandés tous par une même unité centrale et où ils formaient un seul macro-bloc fonctionnel, le pipeline du type MISD correspond à un enchaînement des macro-blocs, chacun ayant sa propre unité centrale, cf. 3.1(c).

Architecture MIMD

La catégorie MIMD est implicitement perçue comme asynchrone ce qui la diffèrencie grandement d’autres catégories de la taxonomie de Flynn.

Les architectures de ce type sont composées de plusieurs unités de calcul séparées qui peuvent exé-cuter différents flux d’instructions sur différents flux de données, indépendamment les unes des autres et en utilisant leurs propres données locales, cf. 3.1(d).

Cette catégorie n’exige explicitement aucune forme de synchronisation entre les unités. Dans la pra-tique, la synchronisation, si on en a besoin, est effectuée par l’intermédiaire d’une mémoire partagée ou par le biais de passage des messages par un réseau d’interconnexions.

Taxonomie de Duncan

La taxonomie de DuncanDun90 est plus récente (1990) que celle de Flynn (1966). Elle était conçue principalement pour surpasser le manque de précision de la taxonomie de Flynn et ainsi pouvoir distin-guer certains types d’architectures très proches dans leur fonctionnement.

La taxonomie de Duncan est basée sur la taxonomie de Flynn et reprend sa terminologie en incorpo-rant les classes SIMD et MIMD dans un système plus discriminatoire et hiérarchisé. De plus, elle exclut les classes qui, selon Duncan, ne décrivent que les mécanismes parallèles de bas niveau. Ces mécanismes sont courants dans les structures des architectures contemporaines mais nous ne pouvons pas les classer rigoureusement comme parallèles car si tel était le cas, la plupart des ordinateurs modernes appartien-Algorithmes de la morphologie mathématique pour les architectures orientées flux Jaromír BRAMBOR

draient aux architectures parallèles. Cette exclusion se présente par la non incorporation des classes SISD et MISD et par l’exclusion explicite des architectures ayant un pipeline au niveau des instructions.

En revanche, elle inclut les architectures vers lesquelles se porte notre attention. Il s’agit des archi-tectures vectorielles, systoliques, des architectures array à vague et des architectures à flux de données. La figure 3.3 présente les catégories de cette taxonomie comme un arbre hiérarchisé.

Architectures synchronesMIMDdu paradigme MIMD

Vectorielles SIMD Systoliques avec la avec la MIMD/SIMD À flux de données À réduction À vague

Architectures vectorielles

Les architectures de ce type sont caractérisées par plusieurs unités du calcul qui peuvent être chaînées et constituer ainsi un pipeline vectoriel. Leur grande différence par rapport aux architectures SIMD est le fait qu’elles sont conçues explicitement pour le calcul vectoriel et implémentent les fonctions spécifiques de ce calcul. Pour démontrer cette différence, nous pouvons citer l’exemple des instructions opérant entre les éléments d’un vecteur telles que la somme des éléments et qui ne sont pas en cohérence avec le modèle SIMD qui utilise l’application d’une seule et même instruction sur plusieurs unités et en principe indépendamment l’une de l’autre.

Architectures systoliques

Les architectures systoliques ont mérité également une place distincte dans la catégorie des archi-tectures synchrones. Elles se présentent par un certain nombre d’unités capables d’exécuter d’une façon synchrone soit une instruction, soit, et le plus souvent, une séquence ou un programme. La présence d’un réseau d’interconnexions dont la topologie est prédéfinie par le type de calcul et la présence du phénomène de pulsation ou de pompage lors du transfert des données d’une unité du calcul à l’autre sont d’autres caractéristiques propres aux architectures systoliques.

Les architectures de ce type gagnent leur performance en éliminant les goulots d’étranglement issus de l’accès aux données dans la mémoire. Plutôt qu’être écrits dans la mémoire principale, les résultats du calcul issus de chaque unité exécutive sont stockés dans leurs registres internes et sont distribués, dans la phase suivante du calcul, via le réseau d’interconnexion directement vers les unités qui en auront besoin pour la poursuite du calcul.

Cette catégorie est très proche de la catégorie très générale MISD de la taxonomie de Flynn, cf. 3.1.1.3, page 33. Les architectures systoliques se spécifient, en contraste de MISD, par leur insistance sur l’exis-tence d’un réseau d’interconnexions complexes et sur la propagation des résultats à l’aide de ce dernier.

La structure systolique la plus souvent utilisée dans le traitement d’images est celle d’un array 2D des processeurs avec les interconnexions bidirectionnelles qui reflètent la définition du voisinage, cf. fig. 3.4(a). Nous pouvons en citer une réalisation intéressante destinée au traitement d’images qui intègre une architecture systolique directement sur la puce du capteur CMOS et dont les éléments exécutifs sont dotés des fonctionnalités SIMDGCRW+ 99.

Mais ce n’est qu’une des possibilités, un autre exemple de la configuration systolique avec la topo-logie adaptée pour la multiplication des matrices 2x2Dun90 est présenté sur la fig. 3.4(b) et un exemple

trivial d’une architecture systolique est un pipeline linéaire travaillant d’une façon synchrone et constitué des blocs fonctionnels distincts, q.v. fig. 3.4(c).

Architectures array à vague

Les architectures array qui n’utilisent pas en même temps tous les éléments pour le calcul et n’en stimulent qu’un certain nombre sont nommées architectures à vague. Comme c’était le cas pour les architectures systoliques desquelles elles sont très proches, les architectures à vague sont composées d’un certain nombre de processeurs et d’un réseau d’interconnexions. Mais elles diffèrent de ces dernières par la façon asynchrone de passage des données par le réseau d’interconnexions. La donnée résultante d’un élément du calcul est passée à travers le réseau seulement si son successeur est prêt pour travailler avec cette donnée et la demande. On distingue ainsi une communication entre les éléments, ce qui n’était pas le cas chez les architectures systoliques où seule la donnée était transférée à travers le réseau.
La figure 3.5 illustre le fonctionnement d’une architecture à vague sur trois itérations. Différentes unités du calcul sont activées dans chacune des étapes, la forme précise de cette activation dépend du calcul à effectuer.
Algorithmes de la morphologie mathématique pour les architectures orientées flux Jaromír BRAMBOR

Architectures à flux de données

Les architectures à flux de données sont basées sur la perception des données en tant que flux et sur le passage des données d’une unité du calcul à l’autre. La caractéristique cruciale est la possibilité du lancement immédiat d’une instruction ou d’un programme dès que leurs opérandes sont disponibles. Il s’agit des architectures asynchrones dont la topologie du réseau d’interconnexions est dictée par le calcul à effectuer. Les unités exécutives sont spécialisées et ne s’occupent pas du va-et-vient des données pour le traitement car leur passage est déterminé à l’avance par le réseau d’interconnexions. La séquence d’exécution est basée sur les dépendances entre les unités. Exploitant cette dépendance, ces architectures peuvent implémenter tous les types du parallélisme, que ce soit au niveau des instructions, des routines ou des tâches.
Nous présentons un exemple1 d’un graphe d’exécution de l’algorithme de filtrage morphologique des images en utilisant les nivellements et le masque d’intérêt, q.v. fig. 3.6. Ce graphe décrit directement la structure d’une architecture à flux de données qui pourrait être envisagée pour ce traitement. Dans ce cas précis, les blocs exécutifs, représentés par les ellipses, sont des routines qui implémentent les opérations morphologiques et les données transmises le long des crêtes du graphe sont les images entières.

Facteurs influant la performance

Les algorithmes présentés plus loin dans cette thèse décrivent des procédés spécialisés mais leurs définitions ont été généralisées tant que les modalités exactes de leur exécution ou les détails précis d’implémentation ne sont a priori pas donnés. Pourtant, la réalisation de ces algorithmes peut faire appel aux architectures qui ont des structures différentes et qui utilisent les fonctionnalités matérielles particu-lières. Regardons maintenant quels sont les facteurs majeurs qui influencent la performance finale d’un système ou d’une architecture informatique et qui sont relatifs à l’implémentation matérielle. Par la suite, nous discutons en détail des points suivants :
• Structure de l’architecture dans 3.2.1,
• Fréquence de(s) l’unité(s) de calcul dans 3.2.2,
• Structure, capacité et fréquence des mémoires dans 3.2.3,
• Parallélisation des données dans 3.2.4,
• Parallélisation d’exécution dans 3.2.5,
• Écartement et latence des instructions dans 3.2.6,
• Instructions spécialisées dans 3.2.7,
• Nombre de registres et leur désignation dans 3.2.8,
• Approche à l’implémentation des algorithmes dans 3.2.9,

Structure de l’architecture

La structure de l’architecture est cruciale et prédestine la performance finale et les scénarios d’utili-sation d’un processeur ou d’un ordinateur issus de cette architecture.
La structure la mieux adaptée pour notre cas serait celle qui implémenterait nos algorithmes directe-ment au niveau du matériel. Cette approche est courante dans la recherche et dans l’industrie spécialisée. C’est une démarche excellente pour la production et l’utilisation en masse. En revanche, elle peut s’avé-rer coûteuse pour les petites séries de produits, surtout à cause de la présence d’un long processus de développement et à cause d’un coût élevé de fabrication d’une série limitée. Les représentants apparents de cette approche sont les puces informatiques dédiées à une fin précise, les ASIC ou les architectures développées utilisant les FPGA.
Si on abandonne l’idée d’une architecture entièrement dédiée et si nous acceptons d’implémenter nos algorithmes sur des structures plus généralistes mais qui resteraient spéciales dans leur fonction-nement, on se retrouvera avec des architectures dédiées pleinement à un calcul sur les flux de données comme Imagine1. Ce type d’architectures peut constituer un bon compromis entre la performance et le coût de développement d’une application. Nous pouvons intégrer dans ce même groupe les processeurs graphiques programmables car malgré leur universalité marquée par la capacité de leur configuration lors d’exécution, leur architecture reste toujours dédiée.
De la façon la plus générique, nous parlons des architectures des processeurs généraux, des GPP. Pour notre travail – avec les flux de données – nous allons nous intéresser plutôt à leurs variantes ayant des capacités multimédia, GPPMM. Les avantages et les inconvénients sont intelligibles. Le prix est faible mais puisque la structure n’est pas nécessairement adaptée au travail que nous voudrions effectuer, la performance peut s’avérer inadaptée ou insuffisante.
Nous ne voudrions pas manquer de citer ici les exemples de structures très particulières que sont les consoles de jeux telles que Microsoft Xbox 360Wik06l ou Sony PlayStation 3Wik06i. Leurs structures sontdédiées à un but précis – visualisation interactive avec la sortie d’un flux vidéo. Elles combinent ainsi une partie largement spécialisée pour le travail sur les flux de données avec une partie générale qui assure le fonctionnement du moteur de l’application. Diverses applications sont possibles, e.g. un cluster du calcul scientifique a été construitCas03 à partir des consoles Sony PlayStation 2.

Fréquence de(s) l’unité(s) de calcul

La fréquence de l’unité du calcul est un paramètre cardinal car directement lié au débit d’exécution des instructions. Il est évident que si on augmentait la fréquence des unités du calcul, nous devrions nous attendre à une augmentation directe de la performance car nous allions, en théorie, traiter plus d’instructions par unité de temps. En pratique, il ne suffit pas d’augmenter uniquement la fréquence des unités du calcul mais nous devons ajuster aussi la fréquence de tous les systèmes subordonnés, notamment de la mémoire.
L’augmentation de la performance à travers augmentation de la fréquence des unités du calcul a été longtemps pourchassée et il faut noter que le défi de la conquête de la fréquence grandissante est toujours bien présent. Un autre point à souligner est le fait que la fréquence est directement liée, avec le voltage et la technologie de gravure, à la consommation et à la dissipation thermique. C’est une des raisons pour lesquelles nous ne voyons pas à présent de processeurs à faible consommation (moins de 10 W) et dont la fréquence dépasserait 500 MHz2. Pourtant, la fréquence ne devrait pas être la limitation principale car de nos jours on fabrique d’une façon industrielle les puces à 4 GHz. En revanche, ce que nous pouvons observer dans le secteur des puces à faible consommation c’est l’inclinaison vers les architectures VLIW3qui fonctionnent à une fréquence moindre mais qui augmentent la performance en multipliant les unités du calcul. Nous reparlerons de la consommation d’énergie dans la section 3.3.

Structure, capacité et fréquence des mémoires

Indispensable pour le traitement, l’accès rapide à la mémoire est aussi important que la performance de l’unité centrale. Dans la plupart des cas aujourd’hui, les mémoires sont hiérarchisées selon la capacité et selon le temps d’accès qui est lié à la fréquence de la mémoire. Cette hiérarchisation est généralement dictée par le prix du produit. On se trouve ainsi avec un système composé de la mémoire principale et un certain nombre (1, 2, 3, voir plus) de mémoires dites caches qui sont plus rapides que la mémoire principale et dont la rapidité diminue et dont la capacité augmente à mesure que l’on s’éloigne de l’unité exécutive. Ces mémoires sont utilisées pour stocker les copies de travail des données. Ainsi, l’accès aux données durant le calcul est rendu plus rapide. Pour plus de précisions, notamment sur les types et le fonctionnement détaillé de la mémoire cache, nous adressons le lecteur à la littératureLM99, Str04.
Idéalement, les données sont présentes dans la mémoire la plus rapide au moment où on en a besoin pour le calcul. Si tel était le cas, nous aurions une situation optimale. Pour y arriver et placer la donnée de la mémoire principale à la mémoire cache la plus rapide, diverses stratégies sont appliquées. On parle du préchargement de la donnée (angl. prefetch). Ce préchargement est implémenté soit au niveau du matériel et on parle ainsi du préchargement automatique de données, soit au niveau du logiciel en utilisant les instructions spécialisées dédiées au travail avec la mémoire cache dans le cas où notre matériel ne dispose pas du préchargement automatique. Tel est le cas, par exemple, pour le travail avec le processeur SH-5BHM+ 00.
Car, dans le cas où nous n’aurions pas effectué manuellement le préchargement et où la donnée ne serait pas présente dans la mémoire la plus rapide, l’architecture procéderait automatiquement au mécanisme du chargement instantané ce qui aurait ralenti ou stoppé l’exécution du programme jusqu’à ce que la donnée ait été transférée dans cette mémoire. Et ce qui causerait, bien sûr, de graves implications sur la performance.
Nous présentons un exemple pratique de cette situation pour le processeur SH-5, q.v. fig. 3.7. À remarquer notamment la façon d’exécution des instructions LD.Q et LDX.Q (cf. moitié supérieure de la fig. 3.7) qui, ne pouvant pas accéder aux données dans la mémoire cache (cf. cache miss dans la moitié inférieure de la fig. 3.7), déclenchent le chargement des données à partir de la mémoire principale. Pendant la durée de ce chargement (cf. total bubble dans la moitié inférieure de la fig. 3.7), le processeur ne peut pas poursuivre l’exécution et le temps est perdu inutilement avec une grande répercussion sur la performance – ici 10 cycles supplémentaires pour chaque instruction LD.Q ou LDX.Q. Pour comparer : si les donnés étaient présentes dans la mémoire cache, ces instructions auraient pris 1 cycle chacune.

Parallélisation des données

Une catégorie de méthodes dans le traitement des images, incluant la morphologie mathématique, sont les traitements sur les données ayant le parallélisme implicite. Cette propriété, si elle est bien ex-ploitée, peut rendre le calcul plus rapide et cela d’une façon importante.
C’est, en effet, la manière la plus simple d’augmentation de la performance. Plutôt que de traiter une donnée à la fois, nous multiplions nos moyens matériels pour en traiter plusieurs en même temps. La manière précise de cette multiplication peut différer. Si on parle de traitements SIMD, nous utiliserons la même instruction pour commander d’une façon synchrone plusieurs unités de calcul qui peuvent traiter ainsi plusieurs données du même type. Si on parle de la parallélisation au niveau des blocs capables d’exécuter chacun une procédure ou un programme d’une façon asynchrone, nous allons nous référer le plus souvent aux traitements MIMD.
Les données utilisées dans la morphologie mathématique sont de ce type. S’il s’agit d’un signal 1D, d’une image 2D, 3D ou de données multispectrales, la présence d’un grand nombre de données régulières du même type est la première à pointer pour le traitement sur les données en parallèle.

Parallélisation d’exécution

Un autre phénomène entre en jeu. On l’appelle la parallélisation des tâches ou la parallélisation d’exécution. Il ne suffit pas d’avoir une grande quantité de données pour pouvoir calculer en parallèle, il faut également que le calcul à effectuer (les tâches) puisse être exécuté sur plusieurs données en même temps.
Les procédés de traitement dans le domaine de la morphologie mathématique sont souvent de ce type.
On identifie assez facilement les parties des algorithmes pouvant être parallélisées dans leur exécution.
Il s’agit des prescriptions du genre « pour tous fait… », « pour tous les pixels effectue… », etc.
Un exemple intéressant de parallélisme au niveau des instructions concerne les architectures VLIW. Nous présentons ici le listing du code du processeur ST200Bag02, q.v. fig. 3.8. L’exécution se poursuit par
blocs délimités par double point-virgule ( » ; ; ») et les instructions de chacun de ces blocs sont exécutées en même temps. Dans la figure présentée, nous avons encadré trois de ces blocs, chacun ayant la durée d’exécution de 1 cycle d’horloge et chacun exécutant 4 instructions à la fois. La planification de la parallélisation d’exécution est accomplie par le compilateur au moment de compilation. Ainsi, elle est explicitement présente dans le code du programme. L’influence de cette approche sur la performance est évidente, comme son impact sur la structure de l’architecture où la parallélisation ne concerne que les unités exécutives. L’unité de préparation des instructions reste une seule et commune car elle décode une seule large instruction.

Écartement et latence des instructions

Les instructions exécutées par un ordinateur, que ce soit un ordinateur d’une architecture RISC ou CISC, ont un comportement temporel décrit par deux paramètres. Il s’agit de l’écartement (angl. pitch) et de la latence (angl. latency) des instructions. Ces paramètres sont exprimés en cycles et ils sont d’une importance cruciale sur les architectures avec un pipeline d’exécution.
Le premier paramètre, l’écartement d’une instruction, nous indique le temps, mesuré en cycles d’hor-loge, qui doit passer entre le lancement de l’instruction A et le lancement de l’instruction suivante B si les opérandes de l’instruction B ne dépendent pas des résultats de l’instruction A. Le temps exact diffère suivant les architectures, il est égal à au moins 1 cycle sur les architectures à lancement simple des ins-tructions, telles que SH-5. Nous pouvons citer les architectures superscalaires comme un exemple non trivial où la définition de l’écartement n’est pas évidente car ces architectures peuvent assurer l’exécution de 2 instructions et plus en même temps.
Le deuxième paramètre, la latence d’une instruction, nous indique le temps, mesuré en cycles d’hor-loge, qui doit passer entre le lancement de l’instruction A et le lancement de l’instruction B si l’ins-truction B utilise comme opérande un des résultats de l’instruction A. Dans ce cas, la préparation de lancement de l’instruction B est suspendue jusqu’à ce que la latence exigée soit assurée.
C’est le compilateur qui devrait assurer la disparition des temps morts issus des latences des instruc-tions. Cette disparition est réalisée, si réalisable, en changeant l’ordre d’exécution des instructions et en plaçant une instruction à longue latence dans une séquence d’instructions à latence faible ou sans latence.

Instructions spécialisées

Un jeu d’instructions bien choisi incluant des instructions spécialisées peut rendre, s’il est bien utilisé, une architecture très performante.
Nous pouvons mentionner, par exemple, le jeu d’instructions multimédia sur les architectures GPPMM pour le calcul sur les données multiples. Nous pouvons mentionner également le jeu d’instructions ma-thématiques spécialisés sur les GPU.
Les algorithmes du domaine de la morphologie mathématique travaillent avec l’approche ensembliste de traitement d’images et utilisent donc abondamment les fonctions logiques, fonctions de comparaison et pour le travail en niveaux de gris les fonctions mathématiques max et min. Les constructions du type if-else sont également très courantes mais ne sont pas adaptées à certaines architectures car elles sont traduites et exécutées comme les sauts qui peuvent rendre difficile l’exploitation du pipeline et la gestion des mémoires caches. On les transforme facilement en une séquence non conditionnelle en utilisant les instructions de comparaison et de déplacement conditionnel.
Nous allons viser les architectures qui ont ces fonctions incorporées nativement dans leurs jeux d’ins-truction. Soulignons que le choix même de l’architecture matérielle ayant les instructions désirées ne suffit pas. Un choix de la même importance est celui du compilateur pour cette architecture et surtout sa qualité. Nous avons beau avoir une architecture puissante, c’est le compilateur qui la valorise pour l’utilisation et pour l’exécution des programmes.

Nombre de registres et leur désignation

Lors d’un traitement multimédia qui travaille avec un grand nombre de données originale et de résul-tats partiels en même temps, le nombre suffisant de registres qui seraient directement les arguments d’entrée d’une instruction arithmétique ou logique est indispensable. Ce besoin est accen-tué encore plus lors de traitement multimédia de données par l’approche qui découpe l’image aux macro blocs où nous avons besoin de manipuler un volume important de données vectorielles en même temps. La table 3.1 présente une liste des types et de nombre de registres pour les architectures multimédia les plus représentatives pour les applications grand public.
Notons que l’architecture Intel IA-32 emploi un autre modèle de fonctionnement qui utilise abon-damment le travail avec la mémoire cache et où nous avons la possibilité d’utiliser une donnée stockée dans la mémoire directement comme argument d’une instruction arithmétique. Donc, cette architecture compense le nombre relativement petit (si on le compare avec l’architecture Intel IA-64) de registres par un accès rapide aux données stockées dans la mémoire cache L1 qui est, généralement, intégrée sur la puce et cadencée, généralement, à la même fréquence que celle du processeur.

Approche à l’implémentation des algorithmes

Lors du développement d’une application qui devrait inclure les instructions spécialisées et qui vise la performance maximale sur une architecture donnée, c’est-à-dire qui vise la rapidité maximale d’exé-cution d’un programme sur cette architecture, au moins trois approches sont possibles :
• La première approche consiste en l’utilisation des fonctions déjà prêtes et écrites spécifiquement pour l’architecture cible par des professionnels. Nous pouvons citer les bibliothèques des fonc-tions telles qu’IPPInt06b d’Intel, une bibliothèque des primitives optimisées. Le gain de temps est évident, on épargne le développement du code spécialisé. En revanche, ces bibliothèques ne four-nissent pas, en général, un ensemble complet des fonctions dont on aurait besoin dans l’application. Dans les applications plus complexes et plus compliquées, on ne peut pas se contenter seulement de ces bibliothèques et on est obligé de créer nos propres fonctions spécialisées. Nous pouvons citer l’exemple de l’outil de recherche MorphoMediaBra05, développé au Centre de Morphologie Mathématique à Fontainebleau au cours du projet de cette thèse.
• La deuxième approche consiste à faire confiance au compilateur et en sa qualité en espérant qu’il reconnaîtra automatiquement les constructions complexes qui peuvent être présentes dans les pro-grammes écrits manuellement par les programmeurs. C’est l’approche a priori la plus rapide en temps de programmation de nos propres fonctions mais elle ne garantit pas nécessairement le ré-sultat attendu. Pour éviter les problèmes liés au temps d’exécution à l’échéance d’un projet de développement informatique, il faut adopter dès son début un style de programmation propre aux exigences et à la compréhension du compilateur. Cela implique un petit surplus de temps utilisé pour comprendre les détails de fonctionnement du compilateur. Il s’agit le plus souvent des op-tions de compilation non standards et des directives du compilateurs incorporées directement dans le code. Par exemple, dans le langage C++ il s’agit des directives #pragma.
• La troisième approche consiste en programmation de très bas niveau et en une utilisation directe des instructions d’assembleur de la machine. C’est l’approche la plus coûteuse en temps de dé-veloppement mais elle est la plus proche de l’architecture et elle peut exploiter au maximum ses particularités. En contraste avec les approches précédentes, elle exige du personnel connaissant les détails et les points spéciaux de l’architecture.
La portabilité d’un programme qui utilise les instructions spécialisées à une autre architecture est un autre sujet à discuter. Le code écrit pour une architecture particulière qui, de plus, s’en sert couramment, est difficile à porter à une autre architecture. Le grand avantage des instructions multimédia des architec-tures GPPMM est que pour quasiment tous les représentants existants des GPPMM nous trouvons, dans leurs jeux d’instructions, les instructions multimédia qui assurent des fonctionnalités identiques ou très similaires.
De ce point de vue, la solution de portage peut être réalisée à l’aide de la couche d’abstraction du matériel, HAL, une couche intermédiaire au niveau du logiciel qui encapsule les différences des codes assembleurs de différentes architectures et n’exporte qu’un interface unifié et généralisé. Tel est le cas pour l’outil de recherche MorphoMediaBra05. Les GPU, eux aussi, sont dotés de la couche HAL présentée par le pipeline graphique abstrait au niveau du logiciel.

Consommation d’énergie

Un paramètre important pour le choix d’une architecture et qui est étroitement lié à la performance que l’on vient de discuter dans 3.2, est la consommation de l’énergie. Pour certaines applications, la consommation ne joue pas un rôle important et le seul facteur limitant pourrait être le coût de l’électri-cité. Pour d’autres, la consommation d’énergie est le facteur majeur du choix du matériel, surtout pour les applications portables et nomadiques où l’équipement matériel n’est pas toujours connecté à une ali-mentation fixe et où ont doit gérer la consommation, d’une façon ou l’autre. Cela est assuré souvent par l’utilisation des régimes économiques qui changent la fréquence du processeur selon les besoins actuels de performance ou qui arrêtent partiellement ou complètement le fonctionnement en cas d’inactivité. Dans ces cas précis, le taux consommation/performance est celui qui oriente le choix d’un processeur plutôt que d’un autre.
La table 3.2 présente une liste non exhaustive des processeurs issus des architectures que nous ci-blons dans cette thèse. Le premier groupe présente la consommation de processeurs GPP/GPPMM. Le deuxième groupe, en contraste avec le premier, présente les GPP/GPPMM mobiles ou à basse consom-mation. Le troisième groupe présente la consommation des GPU. Le tableau finit par présenter la consom-mation des consoles de jeux, c’est-à-dire d’autres architectures spécialisées qui peuvent être visées par les algorithmes décrits dans cette thèse.
Ce qui nous intéresse quant aux processeurs dans ce tableau, c’est la consommation d’énergie. Pour l’information, nous y présentons également les valeurs de MIPS et de FLOPS que nous avons pu collecter pour que le lecteur se fasse une idée des performances liées à la consommation. Tout en sachant que ces descripteurs ne sont pas les meilleurs que l’on puisse trouver pour évaluer la performance mais ils nous permettent de comparer, au moins au niveau de l’ordre, les performances d’architectures aussi différentes que, par exemple, SH-5 et AMD Athlon™64 FX-60 avec deux cœurs.
Le premier regard sur les données dans le tableau 3.2 nous révèle que la consommation des GPPMM, des GPU et des consoles de jeux est de même ordre. Comme les vainqueurs sortent de cette comparaison les consoles de jeux car si on voulait obtenir l’équivalent d’une telle solution à partir des GPP et GPU, nous devrions additionner la consommation d’un GPP choisi avec la consommation d’un GPU choisi ce qui donnerait à l’estime une somme deux fois supérieure à celle des consoles de jeux. Dans une telle logique, le ratio performance-consommation est plus favorable aux consoles de jeux.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Guide de thèse
I Introduction, bases théoriques et appareil mathématique
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
II Algorithmes 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
8 Algorithmes de la dilatation/érosion pour les éléments structurants de la forme d’un segment
8.1 Approche itérative
8.2 Approche employant les algorithmes à réutilisation des valeurs
8.2.1 Principe de l’algorithme de van Herk-Gil-Werman
8.2.2 Parallélisation pour les architectures SIMD
8.3 Résultats expérimentaux
8.4 Récapitulation
9 Algorithmes et complexité
9.1 Définition d’un algorithme
9.2 Complexité d’un algorithme
9.2.1 Définition de la complexité
9.2.2 Les mesures de la croissance
9.3 Modélisation des performances
9.4 Estimation de la complexité et des performances pour les GPP/GPPMM
9.4.1 Idée générale
9.4.2 Estimation pratique pour les GPPMM
9.5 Exemple d’estimation pratique de la complexité des algorithmes de voisinage
9.6 Estimation de la complexité et des performances pour les GPU
9.6.1 Transfert de données
9.6.2 Influence du système d’exploitation et de l’API
9.7 Récapitulation
Conclusion et perspectives
Annexe
Listes
Liste des termes et des abréviations
Liste des figures
Liste des tableaux
Bibliographie 21