Introduction au parallélisme

Un petit reader digest de ce que j'ai trouver sur le web.. wikipédia etc... les ref sont listées à la fin...

Vers le TP parallélisme sur HoMade

Pourquoi des architectures parallèles?

En informatique, le parallélisme consiste à mettre en œuvre des architectures d'électronique numérique permettant de traiter des informations de manière simultanée, ainsi que les algorithmes spécialisés pour celles-ci. Ces techniques ont pour but de réaliser le plus grand nombre d'opérations en un temps le plus petit possible.

Les architectures parallèles sont devenues le paradigme dominant pour tous les ordinateurs depuis les années 2000. En effet, la vitesse de traitement qui est liée à l'augmentation de la fréquence des processeurs connait des limites. La création de processeurs multi-cœurs, traitant plusieurs instructions en même temps au sein du même composant, résout ce dilemme pour les machines de bureau depuis le milieu des années 2000.

Des applications

Certains types de calculs se prêtent particulièrement bien à la parallélisation : la dynamique des fluides, les prédictions météorologique, la modélisation et simulation de problèmes de dimensions plus grandes, le traitement de l'information et l'exploration de données, le décryptage de messages, la recherche de mots de passe, le traitement d'images ou la fabrication d'images de synthèse, tels que le lancer de rayon, l'intelligence artificielle et la fabrication automatisée. Tout d'abord, c'est dans le domaine des supercalculateurs que le parallélisme a été utilisé, à des fins scientifiques.

La classification de Flynn

La taxonomie de Flynn est une classification des architectures d'ordinateur, proposée par Michael Flynn (en) en 19661,2. Les quatre catégories définies par Flynn sont classées selon le type d'organisation du flux de données et du flux d'instructions.

Type de classes

SISD (unique flux d'instructions, unique flux de données)

Il s'agit d'un ordinateur séquentiel qui n'exploite aucun parallélisme, tant au niveau des instructions qu'au niveau de la mémoire. Cette catégorie correspond à l'architecture de von Neumann.

SIMD (unique flux d'instructions, multiples flux de données)

Il s'agit d'un ordinateur qui utilise le parallélisme au niveau de la mémoire, par exemple le processeur vectoriel ou des unités de calcul gérant le traitement du signal comme la vidéo ou le son.

. Les architectures massivement parallèles des années 90 en est aussi un exemple. On retrouve pas mal d'instructions SIMD dans des extensions de processeurs classiques.

MISD (multiples flux d'instructions, unique flux de données)

Il s'agit d'un ordinateur dans lequel une même donnée est traitée par plusieurs unités de calcul en parallèle. Il existe peu d'implémentations en pratique. Cette catégorie peut être utilisée dans le filtrage numérique et la vérification de redondance dans les systèmes critiques. L'architecture appelée Systolic array est un type d'architecture MISD.

MIMD (multiples flux d'instructions, multiples flux de données)

Dans ce cas, plusieurs unités de calcul traitent des données différentes, car chacune d'elles possède une mémoire distincte. Il s'agit de l'architecture parallèle la plus utilisée, dont les deux principales variantes rencontrées sont les suivantes :

MIMD à mémoire partagée

Les unités de calcul ont accès à la mémoire comme un espace d'adressage global. Tout changement dans une case mémoire est vu par les autres unités de calcul. La communication entre les unités de calcul est effectuée via la mémoire globale.

MIMD à mémoire distribuée

Chaque unité de calcul possède sa propre mémoire et son propre système d'exploitation. Ce second cas de figure nécessite un middleware pour la synchronisation et la communication.

Un système MIMD hybride est l'architecture la plus utilisée par les superordinateurs. Ces systèmes hybrides possèdent l'avantage d'être très extensibles, performants et à faible coût.

Diagramme de comparaison des classifications[modifier | modifier le code]

Les quatre types d'architectures sont illustrés ci-dessous.

Légende :

• • PU : unité de calcul (d'un processeur unicœur ou multicœur)

  • Instruction Pool : flux d'instructions

  • Data Pool : flux de données

Selon David A. Patterson et John L. Hennessy, « Certaines machines sont des hybrides de ces catégories, bien sûr, mais cette classification traditionnelle a survécu parce qu'elle est simple, facile à comprendre, et donne une bonne première approximation. C'est aussi, peut-être en raison de son intelligibilité, le schéma le plus utilisé. »

Cette approche montre clairement deux types de parallélismes différents : le parallélisme par flot d'instructions également nommé parallélisme de traitement ou de contrôle, où plusieurs instructions différentes sont exécutées simultanément, qui correspond au MIMD et le parallélisme de données, où les mêmes opérations sont répétées sur des données différentes, le SIMD.

Efficacité

De façon idéale, l'accélération due à la parallélisation devrait être linéaire : en doublant le nombre d'unités de calcul, on devrait réduire de moitié le temps d'exécution, et ainsi de suite. Malheureusement, très peu de programmes peuvent prétendre à de telles performances. Dans les années 1960, Gene Amdahl formula une loi empirique restée célèbre, à laquelle il donna son nom2. La loi d'Amdahl affirme que la petite partie du programme qui ne peut être parallélisée limite la vitesse globale du programme. Or tout programme contient nécessairement des parties parallélisables et des parties séquentielles non parallélisables. Cette loi prévoit qu'une fois optimisé, il existe au sein du programme une relation entre le ratio de code parallélisable et la vitesse globale d'exécution du programme. Dans la pratique, cette approximation est utilisée pour fixer une limite à la parallélisation des architectures matérielles ou à l'optimisation de la programmation pour résoudre un problème.

Représentation graphique de la loi d'Amdahl.

L'accélération du programme par la parallélisation est limitée par le nombre d'exécutions parallèles possible au sein de l'algorithme. Par exemple, si un programme peut être parallélisé à 90 %, l'accélération maximale théorique sera de x 10, quel que soit le nombre de processeurs utilisés.

La loi de Gustafson est assez analogue. Plus optimiste, elle prend quant à elle en compte le cas où il est possible d'augmenter la quantité de données sur lesquelles des calculs sont effectués en parallèle : une augmentation du nombre d'unités de calcul permet alors de traiter plus de données en un temps équivalent, alors que la loi d'Amdahl fixe une limite d'efficacité à quantité de données égale.

Architectures pipeline

Le pipeline est un concept s'inspirant du fonctionnement d'une ligne de montage. Considérons que l'assemblage d'un véhicule se compose en trois étapes (avec éventuellement des étapes intermédiaires) : 1. Installation du moteur. 2. Installation du capot. 3. Pose des pneumatiques.

Un véhicule dans cette ligne de montage ne peut se trouver que dans une seule position à la fois. Une fois le moteur installé, le véhicule Y continue pour une installation du capot, laissant le poste « installation moteur » disponible pour un prochain véhicule X. Le véhicule Z se fait installer ses pneumatiques (roues) tandis que le second (Y) est à l'étape d'installation du capot. Dans le même temps un véhicule X commence l'étape d'installation du moteur.

Si l'installation du moteur, du capot et des roues prennent respectivement 20, 5 et 10 minutes, la réalisation de trois véhicules prendra, s'ils occupent un à un toute la chaîne de production, 105 minutes = (20 + 5 + 10) × 3. Si on place un véhicule dans la chaîne de production dès que l'étage auquel le véhicule doit accéder est libre (principe du pipelining), le temps total pour réaliser les trois véhicules est de 75 minutes.

On peut facilement imaginer ce type de fonctionnement pour l 'exécution d'une instruction , on parle alors de pipeline d'instruction vous l'utilisez tous , parfois sans le savoir ;-)

Pour donner un exemple de pipeline, nous allons aborder un pipeline parmi les plus connus. Celui-ci s'appelle le Classic RISC pipeline. Il s'agit du pipeline créé par David Patterson, inventeur des processeurs RISC et du concept de pipeline. Ce pipeline est utilisé dans de nombreux documents (cours de David Patterson, notamment) comme une introduction au concept de pipeline.

Avec ce pipeline, 5 étapes sont nécessaires pour traiter une instruction2 :

• 1. IF (Instruction Fetch) charge l'instruction à exécuter dans le pipeline.

  2. ID (Instruction Decode) décode l'instruction et adresse les registres.

  3. EX (Execute) exécute l'instruction (par la ou les unités arithmétiques et logiques).

  4. MEM (Memory), dénote un transfert depuis un registre vers la mémoire dans le cas d'une instruction du type STORE (accès en écriture) et de la mémoire vers un registre dans le cas d'un LOAD (accès en lecture).

  5. WB (Write Back) stocke le résultat dans un registre. La source peut être la mémoire ou bien un registre.

En supposant que chaque étape met 1 cycle d'horloge pour s'exécuter, il faut normalement 5 cycles pour exécuter une instruction, 15 pour 3 instructions :

En utilisant la technique du pipeline, notre processeur peut alors contenir plusieurs instructions, chacune à une étape différente.

Les 5 instructions s'exécuteront en 9 cycles, et le processeur sera capable de terminer une instruction par cycle à partir de la cinquième, bien que chacune d'entre elles nécessite 5 cycles pour s'exécuter complètement. Au 5^e cycle, tous les étages sont en cours d'exécution.

SPMD çà existe....

En informatique , SPMD (programme unique, données multiples) est une technique utilisée pour spécifier du parallélisme ; il est une "sous - catégorie" de MIMD . Les tâches sont divisées et s'exécutent simultanément sur plusieurs processeurs avec des entrées différentes. SPMD est le modèle le plus commun de la programmation massivement parallèle. En SPMD, plusieurs processeurs autonomes exécutent simultanément le même programme à son propre rythme, à la différence du rythme unique que SIMD impose. Pour SPMD, les tâches peuvent être exécutées sur des CPU standards .

On retrouve ce modèles sur les deux types de mémoire:

Mémoire distribuée : SPMD se réfère généralement à la programmation par transmission de messages sur des architectures informatiques à distribués mémoire . Un ordinateur à mémoire distribuée est constituée d'un ensemble d'ordinateurs indépendants, appelés noeuds. Chaque noeud commence son propre programme et communique avec d' autres noeuds par l' envoi et la réception de messages, en appelant des routines envoyer / recevoir. Une barrière de synchronisation peut également être mise en œuvre par des messages ou avec une solution matérielle. De nos jours, le programmateur est libéré des détails du message en passant par des interfaces standard, telles que PVM et MPI .

Mémoire partagée : la machine (un ordinateur avec plusieurs processeurs qui accèdent au même espace mémoire), les messages peuvent être envoyés en déposant leur contenu dans une zone de mémoire partagée. Ceci est souvent le moyen le plus efficace pour programmer des ordinateurs de mémoire partagée avec un grand nombre de processeurs, en particulier sur desmachines NUMA , où la mémoire est locale aux processeurs élémentaires et l'accès à la mémoire d'un autre processeur prend alors plus de temps. SPMD sur une machine à mémoire partagée est généralement mis en œuvre par des processus . L'outil le plus répandu reste OpenMP même si ce modèle est beaucoup plus riche....

Maitre Esclave

Maître / esclave est un modèle de communication pour des entités matérielles où un dispositif a un contrôle unidirectionnel sur un ou plusieurs dispositifs. En bref, l'un est le maître et les autres sont des esclaves contrôlés par ce maître.

il pourrait être intéressant pour vous de regarder le modèle de calcul map reduce proposé par google avec Hadoop comme un exemple d'application.

Liste des références :

wikipedia

Flynn

Pipeline

Vers le TP parallélisme sur HoMade