Soutenance mémoire
Les performances des architectures informatiques traditionnelles peinent à suivre le rythme de croissance soutenue de la transformation numérique de notre société. À mesure que l’on se rapproche de la limite atomique des transistors, la miniaturisation des circuits électroniques devient de plus en plus complexe, notamment à cause de la difficulté à maîtriser la dissipation énergétique des puces. La recherche de nouveaux relais de croissance pour améliorer la performance des architectures, et l’optimisation logicielle des programmes a motivé notre méthodologie d’approche haut niveau pour l’accélération d’algorithmes sur des architectures hétérogènes CPU/GPU/FPGA, que nous avons appliquée à la reconstruction tomographique et à la qualification des radars et des systèmes d’écoute électromagnétique au sein des laboratoires L2S et SATIE ainsi qu’au sein de la Direction Technique de l’entreprise Thales DMS France.
L’efficacité énergétique et la modularité des architectures Circuits logiques reprogrammables (FPGAs – Field-Programmable Gate Arrays), semi-conducteurs constitués de blocs reprogrammables rendent leur utilisation attractive pour de nombreux systèmes embarqués, ou comme solution de prototypage de fonctions spécialisées. Aujourd’hui, bénéficiant des avancées du domaine des semi conducteurs, ces architectures ont vu croître leurs performances. Leur utilisation dans des serveurs de calculs s’est avérée pertinente comme concurrents aux CPUs. De ces premières constatations émerge l’idée d’utiliser ces architectures pour notre démarche d’Adéquation Algorithme Architecture (AAA), en tant que plateforme susceptible de s’adapter aux spécificités d’une classe d’algorithmes. Nous nous attacherons donc à comparer leurs performances et celles des architectures CPU/GPU pour motiver notre choix.
L’un des principaux freins à une adoption plus large de cette technologie pour l’optimisation des algorithmes est l’apprentissage du savoir-faire nécessaire à leur utilisation. De nombreuses initiatives tant académiques que commerciales ont eu, dès les années 90, pour objectif d’augmenter le niveau d’abstraction de la programmation de ces plateformes, en proposant des langages haut niveau permettant de s’affranchir d’une partie de la complexité de mise en place d’algorithmes sur FPGAs. Plus récemment, les principaux acteurs du marché, Xilinx et Intel, sont allés encore plus loin en proposant des outils basés sur le langage OpenCL, pour l’utilisation des FPGAs comme co-processeur de calculs. Néanmoins, s’il est souvent aisé d’implémenter un algorithme fonctionnel sur FPGA avec ces solutions OpenCL, le doter d’un niveau de performances comparable à celles obtenues avec une description matérielle requiert de la part d’un ingénieur logiciel, un niveau d’expertise quasiment comparable à celle d’un ingénieur matériel. Pour pallier cette difficulté, un des objectifs de notre thèse a été de mettre en place avec le langage OpenCL, des concepts d’optimisation pertinents, pour accélérer les performances d’algorithmes dédiés au traitement du signal.
État de l’art sur l’accélération des calculs
Evolution et relais de croissance des technologies à base de semi-conducteurs
Limites des performances des architectures traditionnelles
Depuis l’apparition des premiers outils jusqu’au développement des communications à distance et des ordinateurs, l’homme a développé théories et techniques pour transférer son intelligence à des mécanismes visant à améliorer son efficacité, et ce faisant, il a repoussé les limites de sa connaissance et étendu son domaine d’action. Mais, chaque avancée théorique se doit d’être déclinée en application réelle, sans quoi elle n’aurait pas d’impact mesurable. Dans le domaine de l’informatique notamment, alors que les bases de la programmation étaient établies dès le 18ème siècle, il faudra attendre le 20ème siècle pour arriver à une utilisation généralisée de celle-ci. En effet, dès 1725, Basile Bouchon, fils d’un fabricant d’orgues, adapte certains principes de l’horlogerie de l’époque au domaine du tissage, et crée un système d’aiguilles à tisser, programmées par la lecture d’un ruban perforé.
Repris et amélioré par Joseph-Marie Jacquard en 1801, ce qui devient la Machine Jacquard est en quelque sorte la plus ancienne machine programmable connue complètement automatique. En 1834, Charles Babbage eut l’idée de reprendre le principe des cartes perforées du métier Jacquard pour la conception de sa machine à calculer, ou machine analytique [Babbage, Charles, 1851]. Prouesse conceptuelle et technologique pour l’époque, sa contribution majeure fut, en s’intéressant aux méthodes d’automatisation des calculs, de définir les principaux concepts que nous retrouvons dans les ordinateurs actuels. En effet, ses machines avaient des cartes perforées de formats différents suivant qu’il s’agissait de données ou d’instructions, les unités de contrôles pouvaient faire des sauts conditionnels, et les entrées/sorties étaient séparées. Le premier algorithme était lui inventé par une femme, Ada Lovelace [Cellania, 2015] (qui donnera son nom au langage de programmation ADA). Première programmeuse de l’histoire, elle explique que la machine au-delà des traitements numériques sera amenée à traiter des symboles et à effectuer un traitement analytique. Mais il faudra attendre un siècle pour que la découverte technologique des transistors, véritable clef de voûte du matériel informatique actuel, permette l’évolution des architectures informatiques.
En décembre 1947, John Bardeen, William Shockley, et Walter Brattain inventent le premier transistor [Bardeen et al., 1948], devançant de peu les chercheurs Herbert Mataré et Heinrich Welker de la Compagnie des Freins et Signaux à Paris, qui présentent leur version indépendante du transistor [Herbert Mataré and Heinrich Welker, 1948] en juin 1948. Depuis lors, les évolutions technologiques et théoriques se succéderont à un rythme soutenu, pour nous amener en un quart de siècle, avec l’évolution conjointe des communications à distance, aux ordinateurs actuels. En s’intéressant à l’évolution du coût des puces électroniques, Gordon Earle Moore, co fondateur d’Intel, énonce en 1965 dans un article publié dans le journal Electronics [Gordon Earle Moore, 1965] ce qui est désormais connu sous le nom de la première loi de Moore :
« The complexity for minimum component costs has increased at a rate of roughly a factor of two per year…. Certainly over the short term this rate can be expected to continue, if not to increase. Over the longer term, the rate of increase is a bit more uncertain, although there is no reason to believe it will not remain nearly constant for at least 10 years. That means by 1975, the number of components per integrated circuit for minimum cost will be 65,000. I believe that such a large circuit can be built on a single wafer. » Moore, 1965 .
Relais de croissance de l’industrie des semi-conducteurs
Dans le domaine des composants, les fondeurs poursuivent toujours leurs recherches pour miniaturiser les transistors jusqu’à leur taille limite, en s’intéressant par exemple à des procédés de lithographie novateurs comme l’Extreme Ultra Violet [Christian Wagner and Noreen Harned, 2010], mais l’inéluctable barrière atomique contraint les acteurs du domaine à trouver d’autres relais de croissance pour pousser les performances des architectures informatiques toujours plus loin. C’est pourquoi nous assistons également à l’émergence de nouveaux concepts d’ordinateurs, comme les ordinateurs optiques et quantiques. Ces thématiques très présentes dans les communautés scientifiques commencent à porter leurs fruits, notamment par la démonstration de prototypes fonctionnels et prometteurs [DeBenedictis et al., 2018], à l’image d’IBM qui a dévoilé au CES2019 le premier système d’ordinateur quantique à usage scientifique et commercial [IBM, 2019].
Dans le cas des ordinateurs quantiques, leur principe repose sur l’exploitation du comportement probabiliste des atomes, sortant ainsi de la physique traditionnelle pour aborder le domaine de la physique quantique. Cette transformation laisse entrevoir un certain nombre d’avantages, comme une précision plus importante des calculs, ou encore la possibilité d’avoir des simulations physiques à l’échelle atomique. Néanmoins, cette puissance promise amène également son lot de problématiques. En effet, ces ordinateurs seront en théorie capables d’effectuer des factorisations entières en un temps polynomial au lieu d’un temps exponentiel pour les ordinateurs non quantiques, ce qui aura comme conséquence directe de casser certaines techniques de cryptage traditionnelles comme le RSA, qui est notamment utilisé pour les certificats SSL. Il a été démontré [Craig Gidney and Martin Ekerå, 2019], qu’il ne faudrait que 8 heures à un ordinateur quantique avec un nombre suffisant de qubits pour venir à bout d’un chiffrement RSA 2048 bits, au lieu d’une vingtaine d’années actuellement en utilisant les architectures classiques. Ces résultats théoriques, bien qu’aujourd’hui limités par la capacité à gérer un certain nombre de qubits en parallèle, montrent bien que toute solution technologique se doit d’être suffisamment quantifiée afin de préparer en amont les transformations majeures du domaine.
Un autre relais de croissance consiste à faire évoluer la géométrie des puces, en s’émancipant des puces en deux dimensions par l’exploration de l’empilement 3D des transistors. Bien que les progrès dans cet axe technologique aient été relativement lents, notamment à cause de la surchauffe induite par l’empilement des modules, Intel a révélé fin 2018 l’architecture Foveros Une des applications pratiques de l’exploitation de cette verticalité est de pouvoir créer des architectures hybrides avec des cœurs basse consommation (gamme des CPUs Atom) d’un côté et des cœurs haute performance (gamme des CPUs Core), avec des composants pouvant communiquer plus rapidement et avec un meilleur débit entre eux.
|
Table des matières
Introduction
Partie 1 État de l’art sur l’accélération des calculs
I Evolution et relais de croissance des technologies à base de semiconducteurs
I.1 Limites des performances des architectures traditionnelles
I.2 Relais de croissance de l’industrie des semi-conducteurs
I.3 Hétérogénéité des architectures traditionnelles et adéquation algorithme architecture
II Architectures CPU/GPU/FPGA
II.1 Architectures et langages dédiés
II.2 Architectures des circuits logiques
II.3 CPU : architecture de référence
II.3.1 Principe
II.3.2 Types de parallélisme
II.3.2.1 Parallélisme d’instructions
II.3.2.2 Parallélisme de données
II.3.2.3 Parallélisme de threads
II.3.3 Performances théoriques
II.3.4 Évolution future : RISC-V
II.4 GPU : parallélisme massif
II.4.1 Principe
II.4.2 Architecture
II.4.3 Performances théoriques
II.4.4 Langages de programmation
II.5 FPGAs : plateforme reprogrammable
II.5.1 Historique et évolution
II.5.2 Architecture usuelle des FPGAs
II.5.2.1 Vue d’ensemble
II.5.2.2 Les blocs logiques reconfigurables (CLBs)
II.5.2.3 Autres blocs
II.5.3 Flots de conception FPGA
II.6 Standard de programmation OpenCL
II.6.1 Architecture générale
II.6.2 Types de kernels
II.6.3 Architecture mémoire
II.7 Conclusion
Partie 2 Méthodologie AAA pour le co-processing sur FPGA en OpenCL
Remarques introductives
III Modélisation d’un FPGA : Roofline et métriques
III.1 Choix de l’architecture
III.2 Modélisation d’un FPGA en co-processing
III.2.1 Système global CPU hôte + FPGA
III.2.2 Pipeline de calcul
III.2.2.1 Paramètre de performance
III.2.2.2 Nombre de cycles d’un pipeline de calcul
III.2.2.3 Temps d’exécution du pipeline de calcul
III.2.3 Pipeline élémentaire
III.2.3.1 Composition
III.2.3.2 Nombre de cycles
III.2.4 Réplication du pipeline élémentaire – modèle roofline
III.2.4.1 Roofline simplifié
III.2.4.2 Roofline étendu
III.2.4.3 Notre application du modèle roofline aux FPGAs
III.2.4.3.a Reprise d’un modèle existant
III.2.4.3.b Limites de cette approche
III.3 Modèle proposé de prédiction du temps d’exécution d’une application sur FPGA
IV Optimisations OpenCL proposées
IV.1 Optimisation du pipeline de calcul
IV.1.1 Représentation des données et opérations
IV.1.1.1 Types
IV.1.1.2 Structures
IV.1.1.3 Opérations
IV.1.2 Cas des boucles
IV.1.2.1 Pipeline d’une boucle
IV.1.2.2 Déroulage de boucle
IV.1.2.3 Tests conditionnels et accès mémoire
IV.1.2.4 Boucles imbriquées
IV.1.2.5 Dépendances à l’intérieur d’une boucle
IV.1.2.6 Accumulateurs (SWIK, Intel)
IV.1.3 Types de kernel
IV.1.4 Fréquence et intervalle d’initialisation
IV.2 Pipeline élémentaire
IV.2.1 Vectorisation
IV.2.1.1 Vectorisation des work-items (NDRK, Intel)
IV.2.1.2 Vectorisation des paramètres d’entrées
IV.2.1.3 Conditions appropriées d’utilisation
IV.2.2 Réplication (NDRK)
IV.2.3 Mémoires locales
IV.2.3.1 Partition et découpage des objets
IV.2.3.2 Registre à décalage (SWIK)
IV.3 Mémoire globale et interface avec l’hôte
IV.3.1 Types de mémoires
IV.3.2 Partition et répartition des objets sur différentes banques mémoires
IV.3.3 Communication entre kernels (pipes et channels)
IV.4 Caractérisation des leviers d’optimisation
V Exploration du champ des optimisations
V.1 Solutions de Pareto : optimalité locale sous contraintes
V.1.1 Introduction des notions utiles
V.1.2 Application à la démarche d’optimisation
V.1.3 Caractérisation d’une “bonne” optimisation
V.1.4 Exploration des optimisations et sous-optimalité temporaire
V.1.5 Limites du critère et conséquences pour la méthodologie
V.2 Mise en forme de la méthodologie d’accélération d’algorithmes en OpenCL sur FPGA
V.2.1 Description de la stratégie générale
V.2.2 Processus itératif général
V.2.3 Noyau d’Optimisation (contribution majoritaire)
V.2.3.1 Choix de la zone mémoire adéquate
V.2.3.2 Types de parallélisme
V.3 Manuel d’utilisation de notre méthodologie d’accélération
Partie 3 Application et évaluation de la méthodologie
Remarques introductives
Brève chronologie
Architectures de calculs utilisées
Outils utilisés
Démarche de mise en œuvre des résultats et notations
VI Reconstruction tomographique : accélération d’un opérateur de rétroprojection (Intel)
VI.1 Présentation du cas d’étude et enjeux
VI.1.1 Reconstruction pour la tomographie aux Rayons X
VI.1.2 Modèle de référence de l’algorithme de rétroprojection
VI.1.3 Analyse de l’algorithme et protocole de test
VI.2 Exploration des optimisations FPGA
VI.2.1 Implémentation OpenCL : version initiale et levier 1
VI.2.2 Optimisation de l’accès au sinogramme (Levier 2)
VI.2.2.1 Choix parmi les zones mémoires existantes
VI.2.2.2 Implémentation manuelle d’un cache
VI.2.2.3 Résultats et choix
VI.2.3 Type de parallélisme (Levier 3)
VI.2.3.1 Approche SWIK
VI.2.3.2 Approche NDRK
VI.2.3.3 Résultats et choix
VI.2.4 Accès aux tableaux α et β (Levier 4)
VI.2.4.1 Politique de copie
VI.2.4.2 Structure mémoire
VI.2.4.3 Résultats et choix
VI.2.5 Optimisations fines (Levier 5)
VI.2.5.1 Fusion des boucles
VI.2.5.2 Équilibrage des test conditionnels
VI.2.5.3 Résultats et choix
VI.3 Bilan
VI.3.1 Implémentation OpenCL : version finale
VI.3.2 Comparaison de la consommation et des performances sur CPU – GPU – FPGA
VI.3.3 Conclusions
VII Radar et systèmes d’écoute électromagnétique (Xilinx)
VII.1 Vers une évolution régulière des différents niveaux de modélisation
VII.2 Simulateur d’environnements synthétiques : accélération d’un modèle de brouilleur radar
VII.2.1 Présentation du cas d’étude et enjeux
VII.2.1.1 Radar : concepts préliminaires
VII.2.1.2 Simulateur d’Environnements Numériques
VII.2.1.3 Modèle de brouillage aéroporté dans un environnement simulé
VII.2.1.4 Analyse de l’algorithme et protocole de test
VII.2.2 Exploration des optimisations sur FPGA
VII.2.2.1 Implémentation de la FFT (V1)
VII.2.2.2 Choix de la localisation mémoire
VII.2.2.2.a Mémoire d’interface (V2, V3)
VII.2.2.2.b Mise en cache locale manuelle (V4)
VII.2.2.3 Choix du parallélisme (V5-8)
VII.2.2.4 Conclusion des implémentations FPGA
VII.2.3 Bilan : CPU, GPU, FPGA
VII.2.3.1 Implémentations GPU
VII.2.3.2 Comparaison détaillée des temps d’exécution
VII.2.3.3 Efficacité énergétique
VII.2.3.4 Conclusion sur la démarche d’optimisation
VII.3 Implémentation d’un modèle de référence pour la génération de signaux numériques superhétérodynes
VII.3.1 Présentation du cas d’étude et enjeux
VII.3.1.1 Synoptique du projet
VII.3.1.2 Analyse de l’algorithme et protocole de test
VII.3.2 Exploration des optimisations sur FPGA
VII.3.2.1 Implémentation OpenCL : version initiale (V1)
VII.3.2.2 Expression du parallélisme – déroulage des boucles (V2)
VII.3.2.3 Équilibrage des tests conditionnels et communication inter-kernels (V3)
VII.3.3 Bilan : résultats et comparaison CPU/GPU/FPGA
VII.3.3.1 Optimisations FPGA
VII.3.3.2 Comparaison CPU/GPU/FPGA et conclusions
VIII Algorithmes généraux – Benchmark (Intel)
VIII.1 Remarques introductives
VIII.2 K-nearest Neighbors (Rodinia)
VIII.2.1 Description
VIII.2.2 Caractérisation
VIII.2.3 Application de la méthodologie
VIII.3 Needleman-Wunsch (Rodinia)
VIII.3.1 Description
VIII.3.2 Caractérisation
VIII.3.3 Application de la méthodologie
VIII.4 Bilan
VIII.4.1 Notion d’optimisation efficace sur FPGA
VIII.4.2 Résultats et comparaison avec les GPUs
Conclusion générale
