Titre: Les optimisations d’algorithmes de traitement de signal sur les architectures modernes parallèles et embarquées
Auteurs: Jean-Paul Perez-Seva
Ecole/Université: Université de Nice Sophia Antipolis
Résumé: Kontron Modular Computers SAS (KOM-SA) est une entreprise implantée sur le marché de l’embarqué et spécialisée dans la conception de cartes électroniques de calcul. Le marché de l’embarqué est un milieu exigeant où diverses notions opposées sont mises en jeu. La consommation et la dissipation thermique sont deux caractéristiques liées prises en considération dès la conception d’un système. Ainsi l’utilisation de chaque produit conçu par KOM-SA est certifiée suivant des contraintes de températures et de vibrations. Les performances de calcul est aussi déterminante dans la conception du système. Sur un processeur donné, la consommation et la dissipation augmentent avec la fréquence.
De même, les performances du processeur sont proportionnelles à la fréquence. Ce sont donc deux problèmes contraires qui imposent de faire un compromis entre dissipation et performances. C’est pourquoi on observe de manière générale un écart de performances en fréquence entre les processeurs destinés au marché de l’embarqué et ceux destinés au marché grand public et serveur. La puissance de calcul est néanmoins toute aussi omniprésente dans le domaine embarqué que la dissipation et la consommation. La détection RADAR ou SONAR sont deux exemples d’applications exigeantes où les latences de calcul sont très faibles et déterminantes. Ainsi les performances du processeur influent directement sur le nombre de calculateurs constituant le système et par conséquent sur le poids, la consommation totale, le prix et la compétitivité du système.
Le milieu des microprocesseurs est un marché en constante évolution. L’enjeu est de proposer toujours plus de puissance de calcul. Cette évolution est souvent représentée par les lois de Moore. La première loi de Moore, énoncée en 1965 par Gordon Moore, un des trois fondateurs d’Intel, voulait que la complexité des semi-conducteurs proposés en entrée de gamme double tous les ans à coût constant. Le circuit le plus performant de l’époque comportait alors 64 transistors. Cette loi fut une extrapolation empirique de l’observation de l’évolution des semi-conducteurs de l’époque. Elle fut ensuite réajustée, toujours par Gordon Moore en 1975, en proposant que le nombre de transistors des microprocesseurs sur une puce de silicium double tous les deux ans. Cette dernière s’est avérée étonnamment juste entre 1971 et 2001 où la densité des transistors a doublé tous les 1,96 années.
Depuis 2001, les différents fabricants de microprocesseurs ont éprouvé de nombreuses difficultés à faire croître leurs produits de façon à suivre cette loi de Moore. La plupart se sont heurtés à des courants de fuite de plus en plus conséquents, dus à la réduction de la taille des transistors de moins en moins maîtrisée, causant des consommations et des dissipations trop importantes. Si les lois de Moore sont aujourd’hui encore respectées, ceci est dû à un changement radical de philosophie dans le design des microprocesseurs. Un certain nombre de techniques d’accélération matérielle se sont vues intégrées dans les microprocesseurs afin de rattraper ce retard de montée en fréquence. Ces techniques, qui seront détaillées ultérieurement, sont effectivement des choix judicieux mais leur exploitation nécessite le plus souvent une connaissance plus poussée de l’architecture du processeur cible, soit parce qu’elles dépendent des choix faits par les constructeurs, soit parce qu’elles imposent l’usage de langages spécifiques qui suppriment tout l’intérêt d’un langage haut niveau tel que le langage C par exemple.
Jean-Paul Perez-Seva Ainsi, l’exploitation maximale des performances du processeur peut permettre à KOM-SA de réduire le nombre de calculateurs au minimum et de répondre de manière compétitive à chacun de ses clients. Ceci concerne essentiellement l’usage de bibliothèques constituées d’algorithmes optimisés de traitement de signal et d’image. L’optimisation d’un algorithme pour un processeur demande une forte connaissance de l’architecture ciblée. Il existe de nombreuses méthodes d’optimisation proposées par les différents processeurs. Ces méthodes vont de l’exploitation de la profondeur du pipeline à la multiplication du nombre de coeurs de calcul en passant par le parallélisme d’exécution interne. Leur exploitation exige une maîtrise approfondie du fonctionnement des microprocesseurs et l’usage d’une programmation de bas niveau proche de l’assembleur.
C’est donc un travail difficilement automatisable, long et minutieux qui nécessite l’apport d’un oeil expert. La prise en compte de paramètres bas niveau entraîne une dépendance entre l’architecture et les optimisations apportées à algorithme. La problématique de ce travail de recherche est donc de proposer une méthodologie d’optimisation d’algorithmes de traitement de signal sur les processeurs embarqués modernes. Afin d’être le plus exhaustif possible, ce document est structuré comme suit: Construit autour des trois notions clés de la problématique, un état de l’art abordera, dans un premier temps, le sujet des microprocesseurs embarqués actuels et futurs. Il présentera ensuite les méthodes d’optimisation existantes à ce jour pour finir sur les algorithmes de traitement de signal. À travers l’optimisation de la transformée de Fourier rapide sur PowerPC 970 FX, nous chercherons à mettre en évidence les enjeux et les techniques utilisés. La synthétisation de ce travail permettra de définir notre méthodologie d’optimisation. Le chapitre qui suit aura pour but de généraliser notre méthodologie d’optimisation sur l’aspect multi-architecture de la problématique. Enfin, avant de conclure, nous présenterons les résultats obtenus suite à ce travail de recherche.
Extrait du sommaire:
1.Introduction 13
2.Quelques notions importantes 15
2.1.Les nouvelles architectures microprocesseur 15
2.1.1.Modèles d’architectures processeurs 15
2.1.1.1.Modèle de Von Neumann 16
2.1.1.2.Le modèle à flux de données 16
2.1.2.Évolutions importantes des architectures processeurs 16
2.1.2.1.Le pipeline 16
2.1.2.2.Les architectures CISC / RISC 17
2.1.2.3.Les architectures superscalaires 18
2.1.2.4.Les architectures parallèles 21
2.1.2.5.Les architectures SAXPY 22
2.1.2.6.Les architectures Simultaneous Multi Threading 23
2.1.3.L’architecture PowerPC 26
2.1.3.1.PowerPC 750 (G3) 27
2.1.3.2.PowerPC 7448 (G4e) 28
2.1.3.3.PowerPC 970 (G5) 30
2.1.3.4.Freescale 8544 (e500) 31
2.1.3.5.Freescale 8641 (e600) 31
2.1.3.6.P.A. Semi PA6T 32
2.1.3.7.IBM CELL Broadband Engine 32
2.1.4.L’architecture Intel 35
2.1.4.1.Pentium M 36
2.1.4.2.Core Duo 37
2.1.4.3.Core 2 Duo 37
2.1.4.4.Nehalem 38
2.2.Compilation et aide à la programmation 39
2.2.1.Les compilateurs 39
2.2.2.Les logiciels d’aide au prototypage d’applications 40
2.3.Les algorithmes de traitement de signal 41
2.3.1.Le traitement de signal et ses algorithmes 41
2.3.2.La transformée de Fourier 43
2.3.3.La transformée de Fourier discrète 43
Table des matières
2.3.4.La transformée de Fourier rapide 44
2.3.5.L’algorithme FFT radix-2 à entrelacement temporel 44
2.3.6.L’algorithme FFT radix-2 à entrelacement fréquentiel 48
2.3.7.L’algorithme FFT radix-3 49
2.3.8.L’algorithme FFT radix-4 49
2.3.9.L’algorithme FFT Split-Radix 49
2.3.10.L’algorithme FFT de Winograd 50
2.3.11.L’algorithme FFT de Stockham 50
2.3.12.Le bit-reverse 51
2.3.13.Conclusions 52
3.Optimisation de la transformée de Fourier rapide 53
3.1.Les bibliothèques de traitement de signal 53
3.2.Etude d’adéquation algorithmes architectures 54
3.2.1.Algorithme FFT radix-2 à entrelacement temporel 55
3.2.2.L’algorithme FFT Radix-2 à entrelacement fréquentiel 57
3.2.3.L’algorithme FFT Radix-3 57
3.2.4.L’algorithme FFT Radix-4 58
3.2.5.L’algorithme FFT Split Radix 58
3.2.6.L’algorithme FFT de Stockham 59
3.2.7.Conclusion sur les algorithmes FFT 60
3.2.8.Optimisation de l’algorithme FFT radix-2 DIT sur PowerPC 970 FX 60
4.Génération de code optimisé multi-architectures 71
4.1.Les architectures processeurs embarqués 72
4.2.Le concept 73
4.3.Le langage universel 73
4.4.Le modèle d’exécution processeur 77
4.5.L’évaluation 85
4.6.L’optimisation 87
4.7.Application du générateur 90
4.7.1.Capacité d’optimisation du générateur 90
4.7.2.Génération multi-architecture 94
5.Conclusion et perspectives 97
6.Annexes 101
6.1.Algorithmes FFT 101
6.2.CELL Programming Guidelines 103
Télécharger le fichier PDF: Les optimisations d’algorithmes de traitement de signal sur les architectures modernes parallèles et embarquées