Soutenance mémoire
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 (Figure I.1b) 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 .
Ce premier énoncé part du constat que la complexité entre 1959 et 1965 des semiconducteurs a doublé chaque année à coût constant, et de cette observation, il postule la poursuite empirique de cette évolution. En considérant le nombre de transistors par circuits intégrés (1 en 1959, 64 en 1965), nous vérifions bien le doublement (I.1) tous les ans de la complexité des circuits intégrés. En extrapolant à l’aide de cette même formule le nombre de transistors que l’on pouvait espérer avoir en 1975 (I.2), nous obtenons 65536 transistors par circuits intégrés, ce qui est cohérent avec l’énoncé précédent de la loi de Moore.
2 (1965−1959) ∗ 1 = 64 (I.1)
2 (1975−1965) ∗ 64 = 65536 ≈ 65000 (I.2)
Dans l’intégralité de son article, il s’intéresse principalement à l’équilibre, lors de la miniaturisation des composants, entre gains (tant en termes de performance que de consommation) et coûts : il est surtout question de la rentabilité des semi conducteurs, d’un point de vue industriel.
En 1975, Gordon E. Moore reprend sa première loi, et l’applique au nombre de transistors par microprocesseurs (et non plus par simples circuits intégrés), et il en modifie le ratio d’évolution : le nombre de transistors sur une puce de silicium est alors censé doubler tous les deux ans. C’est cet énoncé corrigé qui est retenu comme la deuxième loi de Moore. Ces lois, qui sont les seules réellement énoncées par Gordon E. Moore, sont empiriques, et la seconde a été, durant toutes ces années, une précieuse feuille de route pour la recherche et le développement dans le domaine des semi-conducteurs. L’objectif principal était de permettre aux industriels de définir et de maîtriser le modèle économique du domaine en autolimitant les évolutions technologiques à l’aide de la loi de Moore.
Dans les années 90, la promesse d’une croissance régulière des performances moyennes des semi-conducteurs a entraîné l’utilisation de mémoires de taille toujours plus importante, et a impliqué la complexification des jeux d’instructions. Simultanément, portés par l’explosion du nombre de transistors disponibles grâce à la miniaturisation, les contrôleurs d’instructions devenaient de plus en plus complexes, exploitant toujours plus le parallélisme d’instructions (Instruction-Level Parallelism) (ILP) pour augmenter la performance des architectures. Mais, la principale force du parallélisme d’instruction en est aussi son principal inconvénient. En effet, la performance du parallélisme d’instructions s’appuie sur différents mécanismes, comme l’ordonnancement dynamique [Tomasulo, 1967], les instructions vectorielles, l’exécution multi-flot, ou encore la prédiction de branchement [Smith, 1981], [Jimenez and Lin, 2001], [Seznec, 2006]. Ce dernier consiste à tenter de prédire le résultat d’un branchement, ce qui a pour conséquence de rendre le pipeline d’instructions plus efficace en cas de réussite, mais rajoute un surcoût, tant au niveau de la consommation, qu’au niveau des performances en cas d’échec. Aussi, augmenter la taille d’un pipeline d’instructions entraîne une difficulté croissante à garantir un taux d’échec faible sur les prédictions de branchement, ce qui diminue l’efficacité générale d’une architecture donnée. À partir de la suite de benchmark SPECint, des chercheurs ont quantifié, pour une série d’algorithmes [Limaye and Adegbija, 2018], qu’un Processeur Central (CPU) Intel Xeon E5-2650L avait en moyenne 19% d’instructions gâchées à cause de prédictions erronées. En plus de la limitation du parallélisme d’instructions vers le milieu des années 2000, une autre difficulté est venue ralentir l’augmentation des performances des semiconducteurs : la fin de la règle de Dennard. En 1974, Robert H. Dennard observe que la tension et le courant électrique sont proportionnels à la dimension linéaire d’un transistor [Bohr, 2007]. Ainsi, à mesure que la taille des transistors diminue, ces valeurs baissent, et il en extrapole que le rapport entre la densité et la puissance reste constant à mesure de l’évolution de la miniaturisation. Cet énoncé, mis en parallèle avec la loi de Moore, semblait permettre une évolution rapide à coût et consommation électrique constante des architectures informatiques [Frank et al., 2001]. Mais, depuis 2004, les difficultés à maîtriser la dissipation thermique des architectures ont donné un coup d’arrêt à cette règle, qui n’est dorénavant plus d’actualité. En conséquence, les contraintes technologiques des architectures informatiques, liées à la baisse de performances du parallélisme d’instruction, ont conduit les industriels à s’intéresser aux architectures multi-coeurs. Si nous examinons ces architectures du point de vue des performances, leur croissance a été prolifique dans les années 2000, mais il ne faut pas oublier qu’augmenter le nombre de cœurs d’une architecture n’augmente pas de manière proportionnelle le parallélisme correspondant. La corrélation entre ces deux facteurs est donné par la Loi d’Amdhal [Mark D. Hill and Michael R. Marty, 2008], et souligne le fait qu’un programme est limité par sa partie séquentielle, quelle que soit l’architecture sous jacente. En observant l’allure générale de l’évolution des performances présentée à la Figure I.2, l’accumulation des obstacles énoncés précédemment a comme conséquence directe un essoufflement de la croissance du secteur des semi conducteurs. Si nous examinons les performances obtenues dans ce domaine, suivre la cadence énoncée par la loi de Moore s’est avéré ces dernières années complexe, voire impossible comme nous allons l’illustrer avec l’exemple d’Intel. L’entreprise avait annoncé en 2013 pouvoir produire des puces de 10nm de finesse de gravure pour 2015, avant de repousser ce délai à 2016, puis à fin 2017. En décembre 2018, Dr. Venkata Renduchintala, PDG d’Intel Corporation, annonçait que leurs recherches concernant les processeurs 10 nm avaient dû être revues de fond en comble, mais que la nouvelle direction donnée au projet était désormais assurée. Finalement, début 2019, au CES2019 Las Vegas, Intel a annoncé la disponibilité des puces en 10 nm pour la fin d’année 2019. Ce délai pourrat-il être respecté, ces retards successifs ne seraient-ils pas justement le symbole des difficultés à accroître les performances du domaine ?
Mais ces derniers ont déjà réussi à graver des puces en 10 nm, et arrivent même aujourd’hui à produire des puces mobiles en 7 nm, voire en 5 nm. Le danger pour Intel est donc d’avoir des puces rivales qui, en termes de densité et de performances, soient équivalentes voire meilleures que ses propres puces, bloquées à 14 nm de finesse de gravure et dont l’entreprise n’arrive plus à tirer de gain de performances significatif. Cette difficulté à miniaturiser les puces de la part du plus grand fabricant mondial de semi-conducteurs est un indicateur puissant du problème auquel est confronté le domaine dans sa globalité. Certes, la miniaturisation permet d’augmenter les performances des puces, de réduire leur coût unitaire, et également d’amoindrir le délai entre les fils et les transistors ainsi que la consommation locale d’énergie. Mais, la nécessité de réduire la tension d’alimentation des transistors pour mieux contrôler la dissipation d’énergie implique que les charges de ces derniers sont plus facilement perdues. À cela s’ajoute qu’au fur et à mesure, les composants deviennent de plus en plus fragiles. Aussi, une augmentation de la densité des semi conducteurs implique d’augmenter le ratio des transistors utilisés pour la redondance des informations, ce qui en réduit d’autant le gain en performances. Le constat est donc clair : en approchant de la limite physique possible de la taille des transistors, la miniaturisation des architectures traditionnelles n’est plus viable sur le long terme. Aussi, l’Association des Industriels des Semi-conducteurs (SIA), composée des grands industriels du domaine (comme AMD, IBM, Intel, ARM, Qualcomm, Xilinx, Texas Instruments, . . . ) a annoncé la fin effective de la loi de Moore pour 2021 [lec, 2015]. Cette annonce clôture cinquante-six années d’évolution qui ont vu les puces en silicium passer de 2300 transistors par microprocesseur (Intel 4004 [Aspray, 1997]) en 1971 à plus de 19 milliards de transistors en 2017 pour le SoC d’AMD Epyc intégrant 32 cœurs. En conséquence, il apparaît clairement que l’amélioration des performances par la miniaturisation des architectures traditionnelles est limitée. Pourtant, il existe de nombreux axes de croissance possibles pour cette industrie que nous allons évoquer ci-après.
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 .
Hétérogénéité des architectures traditionnelles et adéquation algorithme architecture
Des remarques précédentes, il découle que les avancées technologiques traditionnelles sont vouées à atteindre un palier de performances difficilement franchissable, d’où l’idée d’utiliser et de concevoir des architectures qui s’adaptent aux spécificités d’une classe d’algorithmes, au lieu d’utiliser une architecture polyvalente comme un CPU pour effectuer toutes les tâches d’un programme donné. Cette démarche d’adéquation algorithme architecture, qui peut bien sûr être implémentée en parallèle de n’importe quel autre relais de croissance, est donc la solution la plus logique à adopter. Impulsée par le domaine de la téléphonie mobile, nous assistons à la démocratisation des puces hétérogènes. Par exemple, la puce A11 d’Apple [Dilger, 2017], présente notamment dans les iPhones 8, 8 Plus, et X, intègre de nombreux composants spécialisés (Figure I.5). Elle est constituée d’un CPU ARM à 6 cœurs , d’un Processeur Graphique (Graphical Processing Unit) (GPU), mais également d’un processeur pour le traitement d’images, tels que les estimations de luminosité par exemple, ou encore l’atténuation du grain en temps réel sur les photos par exemple.
|
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
Conclusion
