Soutenance mémoire
Génération de code assembleur
II y a plusieurs années, les gens du domaine de l’informatique pensaient qu’aujourd’hui l’optimisation ne serait plus aussi importante qu’elle l’était pour eux. Ils disaient que la quantité de mémoire et la puissance de calculs des processeurs ferait en sorte que le gain en temps ne vaudrait pas l’effort de programmation nécessaire pour programmer du code optimisé. Maintenant, nous savons que ce n’est pas le cas. Les processeurs ont certes eu un gain de performance important, mais les tâches qu’ils accomplissent nécessitent de plus en plus de puissance de calculs et de mémoire, Nous ne citerons que quelques exemples, qui n’étaient tout simplement pas imaginable voilà quelques années à peine: le traitement d’images à haute résolution en temps réel, le traitement de la voix et la simulation physique d’écoulement des fluides.
parallélisme
Pendant plusieurs années, le gain de performance provenait principalement de la cadence des processeurs. Maintenant le gain de performance provient principalement du parallélisme. La définition du parallélisme selon le dictionnaire Larousse est : « Technique d’accroissement des performances d’un système informatique fondée sur l’utilisation simultanée de plusieurs processeurs ». Selon ce même dictionnaire, la définition de processeur est : « Organe destiné, dans un ordinateur, à interpréter et exécuter des instructions », Dans cet ouvrage, nous désignerons un processeur comme une unité de traitement (UT). Le mot processeur quant à lui, désignera ce qui est généralement reconnu par tous comme étant la composante électrique complète avec toutes les unités de traitement qui le compose.
parallélisme de bit
Le parallélisme de bit consiste à traiter plusieurs bits simultanément dans une opération. Les premiers processeurs constitué de relais étaient de seulement 1 bit, C’est-àdire qu’ils ne traitaient qu’un seul bit à la fois. Avec l’avenue des transistors, les unités de traitement pouvant traiter plusieurs bits en simultanés sont apparus, doublant le nombre de leur prédécesseurs à chaque évolution. L’apparition des ordinateurs personnels s’est faite avec des unités de traitement à 8 bits pour la compagnie IBM et les ordinateurs compatibles. La compagnie Apple à utiliser des unités de traitement de 32 bits. Présentement, les unités de traitement de 32 bit utilisés dans les ordinateurs personnels laissent graduellement la place à ceux à 64 bits.
Lorsqu’un calcul nécessite plus de bits que ce que F unité de traitement en offre, il est nécessaire d’effectuer des calculs partiels et d’assembler les résultats partiels pour obtenir le résultat final désiré. Inutile de mentionner que ceci implique un coût en temps de calcul qui serait non nécessaire si l’unité de traitement possédait un nombre de bits suffisant pour effectuer le calcul en une seule opération.
Le parallélisme d’instructions
Une instruction est une commande donnée à un processeur. Une instruction peut résulter en une ou plusieurs opérations. Lors de l’exécution d’une opération, il y a plusieurs étapes impliquées dans le processeur. Le nombre d’étapes et Tordre de celles-ci dépend de l’architecture matérielle du processeur. Cependant, il est possible d’exécuter plusieurs de ces étapes en parallèle, c’est-à-dire en simultané, dans un pipeline. La taille du pipeline a atteint 31 étapes dans les processeurs Pentium D.
Le parallélisme de données
Dans plusieurs algorithmes, particulièrement les calculs vectoriels (basé sur des vecteurs), une instruction est appliquée à plusieurs données différentes. Historiquement, il était nécessaire d’appliquer la même instruction à chaque donnée. Lorsque la même instruction peut être appliquée pour effectuer le même travail sur plusieurs données, on effectue du parallélisme de données, ou data-parallélisme. Ceci réduit le nombre d’instructions par un facteur égal au nombre de données traités simultanément lorsque l’instruction data-parallèle est utilisée. Par exemple, une instruction data-parallèle qui traite quatre données en simultané réduit d’un facteur quatre le nombre d’instructions nécessaire, comparativement à une architecture qui nécessite une instruction pour chaque donnée.
Le parallélisme de tâches
Lorsque Ton parle de parallélisme, c’est naturellement celui auquel les gens pensent. Il consiste en l’accomplissement de plusieurs tâches distinctes simultanément. Par exemple, effectuer la compression d’un fichier, jouer de la musique et effectuer un téléchargement.
ALGORITHMES
Les logiciels, où applications, sont des ensembles d’algorithmes ordonnés de manière à effectuer une ou plusieurs tâches précises. Pour être en mesure d’améliorer la performance, il est nécessaire de comprendre et classifier ces algorithmes. Ceci, afin de mieux définir les instructions data-parallèles pertinentes et utiles.
Classification des algorithmes
Comme vu en 1.2, il existe plusieurs architectures matérielles. L’existence de ces architectures matérielles provient du fait que les algorithmes sont différents, et que certains sont plus simple à implémenté sur certaines architectures. On présente ici une classification des algorithmes qui se base sur la dépendance entre les données. Ceci nous permet de déterminé ceux qu’il est possible paralléliser sur l’architecture PC et de mieux les connaître. Pour définir le comportement des algorithmes, on utilise les termes bloc d’instructions et bloc de données. Un bloc d’instructions est un ensemble d’instructions ordonnées d’une manière précise pour effectuer une tâche. Un bloc d’instructions ne peut pas être divisé. Il doit être vu comme monolithique. Un bloc de données est constitué de plusieurs données, toutes traitées simultanément par un bloc d’instructions.
Algorithmes synchrones
Les algorithmes synchrones peuvent se composer d’un ou plusieurs blocs d’Instructions, Cependant, il n’y a qu’un seul chemin d’exécution possible. De plus, il ne doit pas y avoir de corrélation entre les données pour que chacun des blocs de données puissent être traités Indépendamment des autres. Lorsque l’architecture matérielle le permet, les blocs de données peuvent être traités de manière parallèle. Ces algorithmes sont des candidats parfaits pour un traitement via une architecture IUDM car ils peuvent être traités avec une séquence de blocs d’instructions.
Algorithmes asynchrones
Les algorithmes asynchrones ont comme caractéristique que leurs données ne sont pas indépendantes. Il faut donc avoir une connaissance particulière de l’algorithme pour synchroniser l’accès aux données et paralléliser les parties qui peuvent l’être.
Historiquement, tous les programmes sont traités comme des algorithmes asynchrones car les architectures matérielles n’avaient pas la possibilité d’améliorer les performances de manière automatique. Généralement, il n’y a pas de parallélisme mis de Pavant et un seul chemin d’exécution est actif à un temps précis. Ce sont les algorithmes que les programmeurs trouvent les plus simples à comprendre, concevoir, implanter et maintenir .
Instructions souhaitables
Pour être viables, les langages inclus dans le paradigme de programmation dataparallèles doivent supporter les instructions traditionnelles disponibles dans le paradigme de programmation impératif, mais ils doivent en plus offrir plusieurs instructions qui ne sont pas disponibles dans les autres paradigmes de programmations. Ces instructions sont des instructions qui traitent des données en parallèles. Ces instructions sont décrites dans les sections suivantes. Pour simplifier récriture, nous utiliserons la notion de groupe de données. Un groupe de données est soit un vecteur ou une matrice contenant les données. Toutes les données d’un groupe de donnée sont du même type.
Solution selon valarray
Valarray est le nom donné à un ensemble d’objets et fonctions faisant partie du standard C++. Il offre la possibilité d’effectuer plusieurs des opérations souhaitables directement en langage C++. Cependant, comme le montre le document (AFNOR, 2000), valarray n’est pas parfait du point de vue de la syntaxe. De plus il ne supporte pas les tableaux à plusieurs dimensions naturellement. Il est néanmoins utile de regarder comment il adresse chacune des instructions souhaitées pour la création, l’affectation et l’accès aux données, afin de s’en inspirer dans le cadre du travail.
Solution selon Blitz++
Blitz++ est également une librairie conçue pour le langage C++. Comme valarray, elle ajoute la possibilité d’effectuer les opérations souhaitables. Les opérations sont seulement au niveau de la syntaxe, et aucune optimisation n’est effectuée pour prendre en charge les possibilités offertes par le matériel, sauf ce que le compilateur réussira à optimiser, À l’instar de valarray, son étude est une bonne source d’inspiration pour la solution proposée. La classe sur laquelle est basée la librairie se nomme Array.
CONCLUSION
Ce travail se voulait une preuve qu’il était possible d*avoir un outil pour les programmeurs qui leurs permettrait d’utiliser la puissance offerte par les instructions dataparallèles de manières simple et efficace. Cet outil devrait utiliser les instructions dataparallèles partout où c’est pertinent et le programmeur ne devrait pas avoir à fournir d’effort supplémentaire pour ce faire. Le langage psC. initialement destiné à la programmation des FPGA, s’est avéré efficace pour la programmation des processeurs modernes et l’utilisation des instructions data-parallèles du processeur. L’utilisation d’un langage destiné à la programmation matérielle, pour la programmation data parallèle des processeurs est un concept unique.
|
Table des matières
1 INTRODUCTION
1.1 Parallélisme
1.1.1 Parallélisme de bit
1.1.2 Le parallélisme d’instructions
1.1.3 Le parallélisme de données
1.1.4 Le parallélisme de tâches
1.2 Architectures parallèles
1.2.1 Instruction unique donnée unique
1.2.2 Instructions multiples donnée unique
1.2.3 Instruction unique données multiples
1.2.4 Instructions multiples données multiples [IMDM]
1.3 Architecture des ordinateurs personnels
1.3.1 Jeu d’instruction MMX
1.3.2 Jeu d’instruction 3DNow
1.3.3 Jeux d’instructions SSE et successeurs
1.4 Programmation
1.4.1 Paradigme impératif
1.4.2 Paradigme événementiel
1.4.3 Paradigme data-parallèles
1.4.4 Paradigme fonctionnel
1.5 Problématique
1.5.1 Le langage assembleur
1.5.2 Les fonctions intrinsèques
1.5.3 Optimisation par le compilateur
1.5.4 Besoin
2 ALGORITHMES
2.1 Classification des algorithmes
2.1.1 Algorithmes synchrones
2.1.2 Algorithmes légèrement synchrones
2.1.3 Algorithmes asynchrones
2.2 Instructions souhaitables
2.2.1 Le type « index »
2.2.2 Instructions d’affectations
2.2.3 Instructions de sectionnement
2.2.4 Instructions conditionnelles
2.2.5 Instructions de réductions
2.2.6 Instructions vectorielles
2.3 Solution selon valarray
2.3.1 Contraction
2.3.2 Instructions d’affectation
2.3.3 Instructions de sectionnement
2.3.4 Instructions conditionnelles
2.3.5 Instructions de réductions
2.3.6 Instructions vectorielle
2.4 Solution selon Blitz++
2.4.1 Contraction
2.4.2 Affectation et extraction de valeurs
2.4.3 Instructions d’affectations
2.4.4 Instructions de sectionnement
2.4.5 Instructions conditionnelles
2.4.6 Instructions de réductions
2.4.7 Instructions vectorielles
2.5 Solution proposé
2.5.1 Contraction
2.5.2 Affectation et extraction de valeurs
2.5.3 Instructions de sectionnement
2.5.4 Instructions conditionnelles
2.5.5 Instructions de réduction
2.5.6 Instructions vectorielles
3 RÉALISATION
3.1 Choix du langage
3.2 Historique du langage psC
3.3 Description de la syntaxe du psC
3.3.1 Composant
3.3.2 Ports et signaux
3.3.3 Type
3.3.4 Fonctions
3.3.5 Fonctions intrinsèques
3.3.6 Opérateur
3.3.7 Transtypage
3.4 Ajout des instructions data-parallèles
3.4.1 Ajout de la grammaire data-parallèles sur les tableaux
3.4.2 Ajout du type index
3.4.3 Ajout de fonctions spécialisées data-parallèles
3.5 Compilation
3.5.1 Validation
3.6 Génération de code assembleur
3.6.1 Architecture MMX et SSE
3.6.2 Principe
3.6.3 Patron : index
3.6.4 Patron : chargement d’une donnée
3.6.5 Patron : chargement de données non-alignées
3.6.6 Patron : sauvegarde d’une donnée
3.6.7 Patron : minimum d’entiers de huit bits non signés
3.6.8 Patron : multiplication de points flottants à trente-deux bits
3.6.9 Patron : multiplication de points flottants à soixante-quatre bits
3.6.10 Patron : addition de points flottants à soixante-quatre bits
3.6.11 Patron : somme de points flottant trente-deux bits, résultats scalaire
3.6.12 Patron : multiplication matricielle de points flottant soixante-quatre bits
3.6.13 Patron : transformation d’un scalaire de huit bits non signé en un vecteur
4 RÉSULTAT
4.1 Présentation des tests
4.2 Filtre à réponse impulsionnelle finie
4.2.1 Implantation C
4.2.2 Implantation Assembleur
4.2.3 Implantation psC
4.2.4 Résultats
4.3 Saturation alpha
4.3.1 Implantation C
4.3.2 Implantation Assembleur
4.3.3 Implantation psC
43.4 Résultats
4.4 Multiplication matricielle
4.4.1 Implantation C
4.4.2 Implantation Assembleur
4.4.3 Implantation psC
4.4.4 Résultats
5 CONCLUSION
Télécharger le rapport complet
