Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Multicoeurs, Hyperthreading, parallélisme : qu'est- ce que c'est ? Par Guy Grav

Multicoeurs, Hyperthreading, parallélisme : qu'est- ce que c'est ? Par Guy Grave (Mewtow) www.siteduzero.com Licence Creative Commons BY-NC-ND 2.0 Dernière mise à jour le 29/09/2012 Sommaire 2 Sommaire ........................................................................................................................................... 2 Lire aussi ............................................................................................................................................ 4 Multicoeurs, Hyperthreading, parallélisme : qu'est-ce que c'est ? ...................................................... 5 Partie 1 : Le parallélisme : un peu de théorie ...................................................................................... 5 Les différentes architectures parallèles ............................................................................................................................ 5 Les différents types de parallélisme ............................................................................................................................................................................ 5 Parallélisme de Threads .............................................................................................................................................................................................. 5 Parallélisme d'instruction ............................................................................................................................................................................................. 6 Parallélisme de données ............................................................................................................................................................................................. 6 Taxonomie de Flynn .................................................................................................................................................................................................... 6 SISD ............................................................................................................................................................................................................................ 6 SIMD ........................................................................................................................................................................................................................... 7 MISD ........................................................................................................................................................................................................................... 8 MIMD ........................................................................................................................................................................................................................... 8 Résumé ....................................................................................................................................................................................................................... 8 Partage de la mémoire ................................................................................................................................................................................................ 8 SASM .......................................................................................................................................................................................................................... 9 DADM .......................................................................................................................................................................................................................... 10 SADM ........................................................................................................................................................................................................................ 11 Les limites théoriques ...................................................................................................................................................... 12 Loi d'Amdhal .............................................................................................................................................................................................................. 12 Hypothèses de base .................................................................................................................................................................................................. 13 Gain ........................................................................................................................................................................................................................... 13 Dérivation de la Loi d'Amdhal .................................................................................................................................................................................... 14 Ce que nous dit la loi d'Amdhal ................................................................................................................................................................................. 14 Parallélisons mieux ! ................................................................................................................................................................................................. 15 Nombre de processeurs ............................................................................................................................................................................................ 16 Code série ................................................................................................................................................................................................................. 16 Loi de Gustafson ....................................................................................................................................................................................................... 16 Parallélisme de données ........................................................................................................................................................................................... 17 Hypothèses de base .................................................................................................................................................................................................. 17 Gain ........................................................................................................................................................................................................................... 18 Que nous apprend Gustafson ? ................................................................................................................................................................................ 18 Partie 2 : Multi-processeurs, Multicoeurs et Hyperthreading ............................................................. 19 Hyperthreading et compagnie ......................................................................................................................................... 19 Du parallèlisme avec un seul processeur ................................................................................................................................................................. 19 Le pipeline fait des bulles ! ........................................................................................................................................................................................ 20 Types de super-threading matériel explicite .............................................................................................................................................................. 25 Processeurs superscalaires ...................................................................................................................................................................................... 26 Et dans le processeur ? ............................................................................................................................................................................................ 26 Cycle Fetch / Exécution ............................................................................................................................................................................................. 27 Niveau circuits ........................................................................................................................................................................................................... 30 Processeurs multicoeurs ................................................................................................................................................. 31 Processeurs multicœurs ........................................................................................................................................................................................... 31 Le multicœurs, c'est quoi ? ....................................................................................................................................................................................... 31 Multicœurs asymétrique ............................................................................................................................................................................................ 32 Cluster Multithreding ................................................................................................................................................................................................. 33 Le partage des caches .............................................................................................................................................................................................. 33 Caches dédiés versus caches partagés ................................................................................................................................................................... 35 La réalité .................................................................................................................................................................................................................... 36 Communication inter-processeurs ............................................................................................................................................................................ 37 L'exemple du x86 ...................................................................................................................................................................................................... 38 Partie 3 : Le partage de la mémoire .................................................................................................. 39 Cohérence mémoire ........................................................................................................................................................ 39 La cohérence : c'est quoi ? ....................................................................................................................................................................................... 40 Mécanismes de base ................................................................................................................................................................................................ 40 Politique d'écriture du cache ..................................................................................................................................................................................... 43 Caches partagés ....................................................................................................................................................................................................... 44 Direct Memory Acces ................................................................................................................................................................................................ 44 Conclusion ................................................................................................................................................................................................................ 44 Protocoles de cohérence des caches ....................................................................................................................................................................... 44 Protocole MSI ............................................................................................................................................................................................................ 46 Protocole MESI ......................................................................................................................................................................................................... 46 Protocole MOESI ....................................................................................................................................................................................................... 47 Implémentation .......................................................................................................................................................................................................... 47 Directory Protocol ...................................................................................................................................................................................................... 47 Snooping protocols ................................................................................................................................................................................................... 48 Write Invalidation et Write Broadcasting ................................................................................................................................................................... 50 Consistance mémoire ..................................................................................................................................................... 50 Problèmes ................................................................................................................................................................................................................. 50 Accès simultanés ...................................................................................................................................................................................................... 51 Memory Ordering ...................................................................................................................................................................................................... 51 Modèles de consistance ............................................................................................................................................................................................ 51 Séquential Consistency ............................................................................................................................................................................................. 2/97 www.siteduzero.com 51 Relaxed Consistency ................................................................................................................................................................................................. 52 Exemples .................................................................................................................................................................................................................. 53 Fences et Memory Barrier ......................................................................................................................................................................................... 53 Full Fence .................................................................................................................................................................................................................. 54 Load/Store Fences .................................................................................................................................................................................................... 54 Et pour le programmeur ? ......................................................................................................................................................................................... 56 Synchronisation entre Threads ....................................................................................................................................... 56 Sections Critiques ..................................................................................................................................................................................................... 56 Exclusion mutuelle .................................................................................................................................................................................................... 57 Instructions atomiques .............................................................................................................................................................................................. 58 Problèmes avec les verrous d'exclusion mutuelle .................................................................................................................................................... 58 Mémoire Transactionelle Matérielle ........................................................................................................................................................................... 58 Instructions LL/SC ..................................................................................................................................................................................................... 59 Versions évoluées ..................................................................................................................................................................................................... 59 Speculative Lock Elision ........................................................................................................................................................................................... 60 L'exemple avec le x86 ............................................................................................................................................................................................... 62 Partage des ressources .................................................................................................................................................. 62 Bus mémoire ............................................................................................................................................................................................................. 62 Bus Contention .......................................................................................................................................................................................................... 62 Prefetcher Contention ............................................................................................................................................................................................... 63 Mémoire cache .......................................................................................................................................................................................................... 63 Cache Contention ...................................................................................................................................................................................................... 64 False Cache Sharing ................................................................................................................................................................................................. 64 Solutions ................................................................................................................................................................................................................... 65 Partie 4 : Architectures NUMA et distribuées .................................................................................... 65 Architectures Distribuées ................................................................................................................................................ 65 C'est quoi ? ............................................................................................................................................................................................................... 66 Différents types ......................................................................................................................................................................................................... 66 Des besoins en terme de sureté ............................................................................................................................................................................... 67 Communication inter-processeur .............................................................................................................................................................................. 67 Message Passing ...................................................................................................................................................................................................... 67 Les réseaux inter-processeurs .................................................................................................................................................................................. 69 NUMA .............................................................................................................................................................................. 70 C'est quoi ? ............................................................................................................................................................................................................... 70 De quoi NUMA est-il ne nom ? .................................................................................................................................................................................. 70 Noeuds ...................................................................................................................................................................................................................... 71 Cohérence des caches, le retour ! ............................................................................................................................................................................ 71 Directory Protocol ...................................................................................................................................................................................................... 71 Organisation de base ................................................................................................................................................................................................ 72 Directory .................................................................................................................................................................................................................... 74 Partie 5 : Le parallèlisme de données ............................................................................................... 74 Instructions SIMD ............................................................................................................................................................ 74 Instructions SIMD ...................................................................................................................................................................................................... 75 Arithmétique saturée ................................................................................................................................................................................................. 76 Exemples : MMX, SSE et AVX .................................................................................................................................................................................. 76 MMX .......................................................................................................................................................................................................................... 78 SSE ........................................................................................................................................................................................................................... 80 AVX ........................................................................................................................................................................................................................... 80 Les processeurs vectoriels .............................................................................................................................................. 81 Architectures ............................................................................................................................................................................................................. 81 Processeur vectoriels Memory-Memory .................................................................................................................................................................... 81 Processeurs vectoriels Load-Store ........................................................................................................................................................................... 82 Pipelining ................................................................................................................................................................................................................... 83 Startup et Dead Time ................................................................................................................................................................................................ 84 Solutions ................................................................................................................................................................................................................... 85 Chaining .................................................................................................................................................................................................................... 85 Multiple Lanes ........................................................................................................................................................................................................... 85 Accès mémoires ........................................................................................................................................................................................................ 86 Pipelining des accès mémoires ................................................................................................................................................................................. 86 Patterns d'accès mémoire ......................................................................................................................................................................................... 88 Quelques registres utiles ........................................................................................................................................................................................... 88 Vector Length Register .............................................................................................................................................................................................. 89 Vector Mask Register ................................................................................................................................................................................................ 89 GPGPU et Streams Processors ...................................................................................................................................... 90 Architecture d'un GPU ............................................................................................................................................................................................... 90 Vieux GPUs ............................................................................................................................................................................................................... 90 Stream Processors .................................................................................................................................................................................................... 91 Hiérarchie mémoire ................................................................................................................................................................................................... 92 Pas de cache de données ......................................................................................................................................................................................... 92 Register Files ............................................................................................................................................................................................................ 93 Du coté de la RAM .................................................................................................................................................................................................... 94 Une histoire de latence ............................................................................................................................................................................................. 94 Jeu d'instruction ........................................................................................................................................................................................................ 95 Plusieurs ALU ............................................................................................................................................................................................................ 95 Prédication ................................................................................................................................................................................................................ Sommaire 3/97 www.siteduzero.com Multicoeurs, Hyperthreading, parallélisme : qu'est-ce que c'est ? Par Guy Grave (Mewtow) Mise à jour : 26/09/2012 Difficulté : Facile Durée d'étude : 1 mois, 3 jours, 3 heures, 7 minutes 2 020 visites depuis 7 jours, classé 69/792 De nos jours, avec l’avènement des architectures multicœurs, de nombreux programmeurs cherchent à utiliser au mieux la puissance fournie par les processeurs modernes. En effet, il n'est pas rare de posséder des processeurs contenant plusieurs cœurs. Cela fait quelques années que de tels processeurs ont étés mis sur le marché et sont accessibles à tout un chacun moyennant une certaine somme d'argent (très souvent trop assez conséquente). L'utilité de tels processeurs est très simple : la performance ! De tels processeurs permettent de faire exécuter des instructions indépendantes dans des processeurs séparés. Cette solution qui consiste à répartir des calculs sur plusieurs processeurs s'appelle le parallélisme. Mais les processeurs multicœurs ne sont pas les seuls processeurs permettant de faire ceci : de nombreux autres processeurs et architectures permettent d’exécuter plusieurs calculs simultanément. Entre les ordinateurs embarquant plusieurs processeurs, les architectures dataflow, les processeurs vectoriels et autres, il y a de quoi être perdu assez rapidement. Mais rassurez-vous : ce tutoriel est là ! Grâce à ce tutoriel, vous aurez un aperçu des différentes architectures parallèles et vous verrez leurs forces et leurs faiblesses. Nous parlerons aussi bien du fonctionnement de ces processeurs et ordinateurs que des interactions entre matériel et logiciel : préparez-vous, le monde du parallélisme vous attend. Sommaire 4/97 www.siteduzero.com Partie 1 : Le parallélisme : un peu de théorie Commençons par les bases et expliquons ce qu'est le parallélisme, pour commencer. Dans ce chapitre, nous verrons un peu quel est le but des différentes architectures que nous verrons dans ce tutoriel. Les différentes architectures parallèles Il existe différents types d'ordinateurs parallèles, tous plus bizarres que les autres. L'imagination des chercheurs en architectures de ordinateurs a en effet été mise à rude épreuve devant le défi que nous imposait la création des architectures parallèles et de nombreuses architectures ont étés inventées pour répondre à ce besoin. Si on devait se lancer sans chercher à organiser le tout, on serait rapidement perdu. Pour se faciliter la tâche, diverses classifications ont été inventées pour mettre un peu d'ordre dans tout ce foutoir. Les différents types de parallélisme Il faut savoir qu'il existe différentes formes de parallélisme, qui ne cherchent pas à paralléliser la même chose. Parallélisme de Threads La première solution, la plus évidente, consiste simplement à exécuter des calculs indépendants en parallèle. Pour cela, il suffit de découper notre programme en plusieurs sous-programmes indépendants qu'on peut faire éxecuter en parallèle. Ces sous- programmes indépendants sont ce qu'on appelle des Threads. Attention : j'utilise le terme thread non dans le sens thread logiciel, mais dans un sens plus général, largement utilisé dans la littérature sur l'architecture des ordinateurs parallèles. Quand je parlerai de threads, je parlerai de threads matériels. Je préfère prévenir tout de suite, vu que dans la suite du tutoriel, j'utiliserai le terme thread de cette façon, et particulièrement dans les chapitres sur les processeurs multithreadés un peu spéciaux. Pour le moment, considérez qu'un thread est simplement un morceau de programme, constitué d'une suite d'instructions à exécuter en série, et qui devra utiliser le processeur. Il suffit de faire exécuter chaque Thread sur un processeur séparé pour pouvoir paralléliser le tout. Les architectures permettant d’exécuter des threads en parallèle sont donc des architectures multiprocesseurs ou multicœurs, ainsi que quelques autres processeurs un peu spéciaux. Avec ce genre de parallélisme, le découpage d'un programme en threads est avant tout un problème logiciel. Ce découpage est donc dans ce cas du ressort du compilateur ou du programmeur : c'est à eux de modifier le programme pour le paralléliser. Nos langages de programmation disposent souvent de mécanismes permettant de découper notre programmes en threads logiciels, exécutables en parallèle si le matériel le permet. Dans certains cas, le compilateur peut s'en charger tout seul, bien que cela soit plus rare. Et enfin, plus étonnant, certains processeurs sont capables de découper un programme à l’exécution, éventuellement grâce à des indications fournies par le programme lui-même ! On peut ainsi, à partir d'un programme unique non-découpé en threads, utiliser plusieurs cœurs ou processeurs sans problèmes ! Le découpage en thread se fait alors à l’exécution, et ce de façon optimale en fonction du nombre de processeurs. Mais cela est tout de même uploads/Ingenierie_Lourd/ multicoeurs-hyperthreading-parallelisme-qu-est-ce-que-c-est.pdf