Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
Architectures de processeurs parall`eles
Cette section presente´ les architectures paralleles` actuelles. En particulier, on en con-sidere` trois : les processeurs multi-coeurs avec unites´ vectorielles, le processeur Cell et les GPU. Ces trois plateformes sont les plus repandues´ actuellement et partagent un certain nombre de caracteristiques´ communes. Tout d’abord, elles disposent de plusieurs coeurs : elles sont paralleles`. Par ailleurs, elles ont toutes une memoire´ partagee,´ c’est-a`-dire une memoire´ centrale qui est accessible par tous les coeurs. Cependant et bien qu’elles soient toutes paralleles,` elles n’implementent´ pas le par-allelisme´ de la memeˆ maniere`. Ceci a pour consequence´ des caracteristiques´ tres` differentes,´ en termes de puissance de calcul et de transfert memoire,´ ce qui a de lourdes repercussions´ sur les performances globales.
Processeur multi-coeur (CPU)
Un processeur multi-coeur classique est compose´ de plusieurs coeurs, gen´eralement´ 2 a` 8. Chaque coeur est superscalaire, out-of-order (c’est-a`-dire que les instructions sont reordonn´ees´ pour etreˆ execut´ees´ dans un ordre favorisant les performances) et dispose d’un certain nombre d’unites´ de calcul vectoriel (Single Instruction Multiple Data ou SIMD), telles que celles pouvant etreˆ utilisees´ par l’intermediaire´ des jeux d’instructions AltiVec [48], SSE1 ou AVX2. D’un point de vue de calcul parallele,` les differences´ majeures entre les processeurs disponibles sont l’interconnexion entre les differents´ coeurs, la hierarchie´ de cache et la presence´ ou l’absence de controleurˆ memoire´ integr´e´.
La figure 2.1 montre une representation´ schematique´ des Intel Core 2 et Intel Core i7 dans leur configuration a` 4 coeurs.
Le processeur Intel Core 2 dispose de coeurs regroupes´ par 2 (ou cluster). Chaque coeur a son propre cache de niveau 1 (L1) et chaque groupe de 2 coeurs a un cache de niveau 2 (L2) partage´. Les 2 clusters de la version 4 coeurs du Core 2 (le Core 2 Quad) sont relies´ entre eux par le FSB par l’intermediaire´ du northbridge de la carte mere`. Ce dernier integre` le controleurˆ memoire,´ qui permet au processeur d’acceder´ a` la RAM. Comme le Core 2 Quad ne dispose pas de cache partage´ entre ses 4 coeurs et n’a pas de controleurˆ memoire´ integr´e,´ la coherence´ de cache est maintenue par l’intermediaire´ du northbridge de la carte mere` et du FSB. Cela implique des communications beaucoup plus lentes entre coeurs de clusters differents,´ ce qui se repercute´ tres` souvent sur les performance gen´erales´.
Au contraire, le processeur Intel Core i7 a un unique cluster pour ses 4 coeurs. De plus, il dispose d’un cache de niveau 3 (L3) partage´ entre ses 4 coeurs, en plus d’un cache prive´ de niveau 2 pour chacun de ses coeurs. Graceˆ au cache partage,´ une meilleure utilisation globale du cache apparaˆıt quand plusieurs threads travaillent sur les memesˆ donnees´. Le FSB est remplace´ par le QPI, une interconnexion point-a`-point, et le controleurˆ memoire´ est integr´e´ desormais´ au sein du processeur. Ceci permet non seulement de reduire´ la latence, mais aussi d’augmenter la bande passante. De plus, le Core i7 dispose de deux fonctionnalites´ qui ont des repercussions´ sur le calcul parallele` : le Turbo Boost (TB) et l’Hyper-Threading (HT). La premiere` consiste a` aug-menter dynamiquement la frequence´ au dela` de la frequence´ nominale du processeur pour les coeurs actifs quand d’autres coeurs sont inactifs. Quand cette fonctionnalite´ est activee,´ elle peut engendrer un biais dans les resultats´ experimentaux´. La seconde fonctionnalite,´ l’HT, permet au systeme` d’exploitation de voir 2 coeurs logiques par coeur physique (SMT 2 voies). Ceci peut permettre une meilleure utilisation des unites´ de calcul : comme 2 threads ont des suites d’instructions independantes,´ le pipeline du coeur peut etreˆ rempli plus efficacement et le moteur out-of-order peut donner de meilleurs resultats´. Cependant, gerer´ 2 threads par coeur peut aussi nuire aux performances comme cela accroˆıt la pression sur le cache (plus de defauts´ de cache), sur les unites´ de calcul, la RAM, etc.
Ces deux modeles` de processeurs permettent theoriquement´ d’atteindre 48 GFLOPS en double precision´ ou 96 GFLOPS en simple precision´ a` 3GHz.
Plusieurs possibilites´ existent pour ecrire´ du code parallele` dans le cadre classique d’architectures SMP (Symmetric Multiprocessing) : on peut par exemple utiliser les bibliotheques` pThread ou BOOST::Thread3 (cette derniere` ayant l’avantage d’etreˆ orientee´ objet). On peut aussi utiliser l’API OpenMP [35, 41] ou MPI [60]. Pour utiliser les unites´ vectorielles, il faut utiliser le jeu d’instructions correspondant, soit directement en assembleur, soit en passant par des fonctions intrinsics, qui permettent entre autres de s’affranchir de la gestion des registres au prix de performances plus modestes.
Cell Broadband Engine Architecture (CBEA ou Cell)
Le CBEA est une architecture developp´ee´ par Sony, Toshiba and IBM [107]. Celle-ci a et´e´ conc¸ue pour disposer de performances elev´ees,´ tout en ayant un bon rendement energ´etique´. En particulier, la bande passante dont dispose l’interconnexion entre les coeurs est tres` elev´ee´. La figure 2.2 represente´ l’architecture du processeur Cell.
Le Cell repose sur un coeur PowerPC 64 bits in-order (aussi appele´ Power Processing Element ou PPE) avec unite´ vectorielle AltiVec, qui controleˆ plusieurs coeurs vectoriels (appeles´ Synergistic Processing Element ou SPE). Un SPE est un coeur in-order qui regroupe une unite´ vectorielle (SIMD) de 128 bits et 256Ko de memoire´ locale. Les implementations´ actuelles de l’architecture CBEA ont jusqu’a` 8 SPE. Le PPE et les SPE sont relies´ entre eux par un bus en anneaux disposant d’une tres` grande bande passante (bus appele´ Element Interconnect Bus ou EIB). Comme un SPE dispose de seulement 256Ko de memoire´ locale, il est inevitable´ de devoir realiser´ un grand nombre de transferts a` travers l’EIB. Neanmoins,´ graceˆ a` sa bande passante tres` elev´ee,´ des calculs qui sont gen´eralement´ limites´ par la memoire,´ comme la multiplication matrice/vecteur, ne le sont pas sur Cell. Par consequent,´ un certain nombre de nouvelles operations´ peuvent etreˆ implement´ees´ efficacement de maniere` parallele` sur Cell [88]. Comme aucune unite´ scalaire n’est presente´ sur les SPE, il est particulierement` important de tirer profit au maximum de la vectorisation, sinon les unites´ de calcul seraient sous-exploitees´.
L’implementation´ la plus commune de l’architecture CBEA se retrouve dans la Playstation 3 (PS3) de Sony. En effet, celle-ci possede` un processeur Cell a` 3,2GHz qui dispose de 7 SPE et de 256Mo de RAM. Cependant, seuls 6 SPEs et 192Mo de RAM sont disponibles, le reste etant´ reserv´e´ au systeme` d’exploitation. Un SPE a` 3,2GHz dispose d’une puissance de calcul de 25,6 GFLOPS en simple precision´. Le Cell de la PS3 peut donc atteindre 153,6 GFLOPS en simple precision´ avec ses 6 SPE, c’est-a`-dire approximativement 50% de mieux qu’un processeur Intel 4 coeurs a` 3GHz. En ce qui concerne les performances en double precision,´ un SPE du Cell de la PS3 n’atteint que 1,6 GFLOPS, c’est-a`-dire 9,6 GFLOPS pour les 6 SPE. Cette sev´ere` limitation a et´e´ corrigee´ avec l’arrivee´ du PowerXCell 8i d’IBM qui, avec 8 SPE a` 3,2GHz, atteint 102,4 GFLOPS en double precision,´ c’est-a`-dire 12,8 GFLOPS par SPE (ou 204,8 GFLOPS en simple precision´ pour les 8 SPE). De plus, il faut noter que le Cell de la PS3 a un PPE qui atteint tout de memeˆ 6,4 GFLOPS en double precision´ (et 25,6 GFLOPS en simple precision)´. Comme les SPE du Cell ne disposent pas d’unite´ de calcul scalaire, ce processeur est beaucoup plus adapte´ au code vectoriel (SIMD). Enfin, les branchements conditionnels sont tres` couteuxˆ sur les SPE.
Les performances elev´ees´ du Cell viennent cependant au prix d’une program-mation tres` penible´ a` mettre en oeuvre, comme nous pouvons l’observer dans [56, 121]. En effet, dans le cadre de l’utilisation tres` classique de la bibliotheque` libSPE2 avec pThread developp´ee´ par IBM dans son SDK4, beaucoup d’operations´ usuelles sont assez complexes a` mettre en oeuvre. Par exemple les transferts DMA doivent etreˆ realis´es´ a` la main. Beaucoup d’efforts ont et´e´ faits pour ameliorer´ la facilite´ d’utilisation du Cell, notamment au travers d’implementations´ specifiques´ d’OpenMP [105] et de MPI [87].
Graphics Processing Unit (GPU)
Les GPU modernes (tels que ceux de NVIDIA) reposent sur un nombre consequent´ de processeurs de flux qui partagent une memoire´ commune [100]. Les GPU peuvent aussi etreˆ vus comme des clusters d’unites´ SIMD. Ces processeurs a` coeurs homogenes` ont initialement et´e´ conc¸us pour le rendu de graphismes en 3D, memeˆ si, au fur et a` mesure des nouvelles versions, de plus en plus de fonctionnalites´ sont orientees´ calcul scientifique. Notamment, la precision´ des calculs est devenue telle que les GPU peuvent etreˆ utilises´ dans ce nouveau cadre : le General-Purpose GPU (GPGPU) [106]. Il est toutefois a` noter que certains calculs n’ont pas la precision´ que l’on peut obtenir sur CPU, et que le support des flottants double precision´ demande un sacrifice tres` grand en termes de performances. Il faut aussi noter que les GPU ne fonctionnent pas de maniere` independante,´ comme c’est le cas pour les CPU ou le Cell. En effet, le GPU est obligatoirement pilote´ par un CPU. De plus, un memeˆ systeme` peut disposer de plusieurs GPU. Les architectures de GPU G80 et G200 de NVIDIA sont represent´ees´ dans la figure 2.3. Contrairement aux coeurs de CPU, les coeurs de GPU sont scalaires et correspondent plus a` des unites´ de calcul de CPU. Ils disposent tout de memeˆ d’une hierarchie´ de cache de plusieurs niveaux, mais tres` differente´ de ce qu’on peut retrouver sur CPU. En effet, les coeurs sont groupes´ en clusters (multiprocesseurs) qui disposent chacun d’un cache de niveau 1. Les clusters sont subdivises´ en groupes de 8 coeurs qui partagent une memoire´ locale. Ces 8 coeurs executent´ la memeˆ instruction sur des donnees´ differentes,´ d’ou` le cotˆe´ SIMD avec une instruction sur un vecteur de 8 el´ements,´ chacun ger´e´ par une unite´ scalaire (ici abusivement appelee´ coeur). Le nombre de coeurs par cluster peut varier suivant les modeles` : 16 coeurs sur l’architecture G80 et 24 sur G200, qui est une version amelior´ee´ du G80.
Graceˆ a` un bus dedi´e,´ les coeurs de GPU ont acces` a` une memoire´ de plusieurs centaines de Mo particulierement` rapide. En particulier, cette VRAM est beaucoup plus rapide que la RAM centrale. Cela permet d’utiliser efficacement la grande quantite´ d’unites´ de calcul qui sont particulierement` consommatrices en bande passante. La RAM centrale peut aussi etreˆ acced´ee´ par l’intermediaire´ du bus PCI Express. Neanmoins,´ les transferts entre la VRAM et RAM sont tres` couteux,ˆ comme la bande passante du bus PCI Express est limitee´. Ainsi, de tels transferts doivent etreˆ evit´es´ au maximum. Enfin, les branchements conditionnels sont tres` couteuxˆ sur GPU.
Graceˆ a` leur architecture radicalement differente,´ les GPU ont des performances theoriques´ qui sont un ordre de grandeur plus grandes que celles des CPU modernes. Par exemple, une carte graphique NVIDIA 8800 GTS (architecture G80) avec 96 coeurs a` 1,2GHz a une puissance de calcul de 345 GFLOPS en simple precision´ et une NVIDIA GTX 275 (architecture G200) avec 240 coeurs a` 1,4GHz a une puissance de 1010 GFLOPS (toujours en simple precision)´. Rappelons que les processeurs Intel a` 4 coeurs present´es´ prec´edemment´ ont une puissance de calcul de 96 GFLOPS en simple precision´ a` 3GHz.
Comme les GPU etaient´ initialement utilises´ pour des rendus 3D, ils ne pouvaient etreˆ acced´es´ qu’a` travers des bibliotheques` graphiques, telles que Microsoft Direct3D5 ou SGI OpenGL6. Dans le but de pouvoir implementer´ et executer´ des algorithmes numeriques´ sur GPU, NVIDIA a developp´e´ CUDA 7, qui repose sur un compilateur pour un langage sur-ensemble du C, ainsi qu’un ensemble d’outils et de bibliotheques`. NVIDIA a recemment´ fourni une implementation´ d’OpenCL pour ses GPU8.
Architectures d’ordinateurs parall`eles
Syst`eme multiprocesseur
Un systeme` multiprocesseur repose sur plusieurs processeurs au sein d’un memeˆ ordinateur. Chaque processeur peut etreˆ lui-memeˆ multi-coeur. Les processeurs sont relies´ entre eux par une interconnexion qui est differente´ suivant les modeles`. Par exemple, la figure 2.4 represente´ schematiquement´ un ordinateur a` base de 4 Opterons. Ici, les 4 Opterons sont relies´ par une connexion point-a`-point a` base de liens HyperTransport ou` chaque processeur est directement relie´ a` deux autres. Chaque processeur utilise donc deux liens HyperTransport dans le cadre des com-munications entre processeurs. Ainsi, quand un processeur A veut communiquer avec le processeur B, il peut realiser´ un ou deux sauts suivant le dit processeur B.
D’un point de vue du logiciel, les memesˆ outils que ceux utilises´ pour la program-mation de processeurs multi-coeurs peuvent etreˆ utilises´. Le lecteur peut donc se ref´erer´ a` la section 2.1.1 pour de plus amples details´.
Cluster
Un cluster, ou une grappe d’ordinateurs, regroupe plusieurs ordinateurs fonctionnant de concert. Chaque ordinateur est appele´ un noeud. Les noeuds sont relies´ entre eux par l’intermediaire´ d’un reseau´ (par exemple un reseau´ Ethernet classique). La memoire´ n’est donc plus ici partagee´ entre les differents´ processeurs mais privee´ a` chaque noeud. Nous sortons donc du cadre du calcul a` proprement dit parallele,` pour entrer dans celui du calcul distribu´e.
La figure 2.5 represente´ une configuration de cluster a` 16 noeuds.
Chaque noeud peut etreˆ lui-memeˆ un systeme` multiprocesseur ou` chaque pro-cesseur est multi-coeur, ainsi que multi-GPU, par exemple.
|
Table des matières
1 Introduction
1.1 Cadre g´en´eral
1.2 Motivations
1.3 Contributions
2 Eléments d’architectures et de programmation parallèles
2.1 Architectures de processeurs parall`eles
2.1.1 Processeur multi-coeur (CPU)
2.1.2 Cell Broadband Engine Architecture (CBEA ou Cell)
2.1.3 Graphics Processing Unit (GPU)
2.2 Architectures d’ordinateurs parall`eles
2.2.1 Syst`eme multiprocesseur
2.2.2 Cluster
2.3 Programmation parall`ele
2.3.1 Multithreading
2.3.2 Vectorisation
2.3.3 M´emoire
3 Mod´elisation de la factorisation enti`ere par PLNE
3.1 Description du probl`eme
3.2 Etat de l’art
3.3 Formulations en PLNE
3.3.1 Premi`ere formulation
3.3.2 Seconde formulation
3.4 Impl´ementation et exp´eriences
3.4.1 Impl´ementation
3.4.2 Exp´eriences
3.5 Conclusion
4 Compressive sensing – Approche par prog. lin´eaire
4.1 Description du probl`eme
4.2 D´ecomposition de Dantzig-Wolfe
4.2.1 Cas g´en´eral
4.2.2 Application au compressive sensing
4.3 D´ecomposition r´eduite
4.3.1 Pr´esentation de la d´ecomposition propos´ee
4.3.2 Equivalence avec le probl`eme original
4.3.3 Point de vue des co ˆ uts r´eduits
4.3.4 Cons´equences sur les r`egles de pivot
4.3.5 Coˆ uts calculatoires
4.4 Impl´ementation et exp´eriences
4.4.1 Impl´ementation
4.4.2 Exp´eriences
4.5 Conclusion
5 Compressive sensing – Approche par prog. convexe
5.1 Etat de l’art des r´esolutions approch´ees
5.2 Un algorithme bas´e sur le point proximal
5.2.1 R´egularisation de Moreau-Yosida
5.2.2 Preuve de convergence
5.2.3 Choix de l’op´erateur proximal
5.2.4 Algorithme propos´e
5.3 Impl´ementations et exp´eriences
5.3.1 Impl´ementations
5.3.2 Exp´eriences
5.4 Conclusion
6 V´erification approch´ee sur architecture parall`ele
6.1 Contexte
6.1.1 Probl`eme
6.1.2 Etat de l’art
6.1.3 M´ethode de r´esolution APMC
6.2 Architecture logicielle d’APMC 3.0
6.3 Utilisation du mod`ele BSP pour parall´elisation semi-automatique
6.3.1 Mod`ele BSP
6.3.2 Biblioth`eque BSP++
6.3.3 Support pour programmation hybride
6.3.4 Exp´eriences
6.4 Adaptation d’APMC `a l’architecture parall`ele Cell
6.4.1 Nouvelle impl´ementation : APMC-CA
6.4.2 Exp´eriences
6.5 Conclusion
7 Conclusion et perspectives
7.1 Bilan
7.2 Perspectives
A Annexe
A.1 R´esultats compl´ementaires pour le chapitre 3
A.2 R´esultats compl´ementaires pour le chapitre 4
Références bibliographiques
Télécharger le rapport complet
