Cours 2 PP FR

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 22

Programmation parallèle

Dr El Hadji Bassirou TOURE


2021 - 2022

1
Architectures parallèles de processeurs
▪ La puce électronique d’un processeur est la composante clé des ordinateurs.
▪ Un important facteur de performance est la fréquence d’horloge d’un processeur.
▪ Un cycle d'horloge (simplement un « cycle ») est une seule impulsion électronique d'un CPU.
▪ Au cours de chaque cycle, une CPU peut effectuer une opération de base, telle que récupérer une
instruction, accéder à la mémoire ou écrire des données.
▪ En interne, une puce électronique d’un processeur est composée de transistors.
▪ L’augmentation du nombre de transistors et de la vitesse du cycle ont entrainé une augmentation
importante de la performance des ordinateurs.

▪ Conception architecturale (de microprocesseurs) orientée parallélisme :


▪ Parallélisme niveau bit
▪ Parallélisme par pipelining
▪ Parallélisme par de multiples unités fonctionnelles
▪ Parallélisme niveau processeur ou thread

Dr. E_H_B. TOURE / programmation parallèle 2


Petit détour (wikipédia) : Définitions
▪ Processeur :
▪ Un processeur (ou unité centrale de traitement, UCT ; en anglais central processing unit, CPU)
▪ Composant présent dans de nombreux dispositifs électroniques qui exécute les instructions machine des programmes
▪ Avec la mémoire, c'est notamment l'une des fonctions qui existent depuis les premiers ordinateurs.

▪ Microprocesseur :
▪ Un processeur construit en un seul circuit intégré est un microprocesseur.
▪ Un microprocesseur multi-cœur (multi-core en anglais) posséde plusieurs cœurs physiques fonctionnant simultanément.
▪ Un cœur (en anglais, core) est un ensemble de circuits capables d’exécuter des programmes de façon autonome.
▪ Toutes les fonctionnalités nécessaires à l’exécution d'un programme sont présentes dans ces cœurs : compteur ordinal,
registres, unités de calcul, etc.
▪ Il peut exister plusieurs niveaux de mémoires cache, certaines à l'intérieur de chaque cœur, d'autre partagées entre cœurs.

▪ Circuit intégré (ou puce électronique):


▪ Composant électronique, basé sur un semi-conducteur, reproduisant une ou plusieurs fonctions électroniques plus ou moins
complexes.

Dr. E_H_B. TOURE / programmation parallèle 3


Architectures parallèles de processeurs
▪ Parallélisme niveau bit
▪ Jusqu’en 1986, la taille des mots utilisés par les processeurs pour les opérations sont
passés de 4 à 32 bits.
▪ Un mot (mot machine) est une unité de base manipulée par un microprocesseur.
▪ La taille d'un mot s'exprime en bits. Souvent utilisée pour classer les microprocesseurs (32 bits, 64 bits, ...).
▪ Plus ses mots sont longs plus un microprocesseur est rapide
▪ Car les données qu'il traite à chaque cycle sont plus importantes
▪ Cette augmentation s’explique par la nécessité d’améliorer la précision des nombres à virgule
flottante et d’augmenter l’espace d’adressage.
▪ Le nombre à virgule flottante est une valeur numérique de la taille d'un mot, ou d'un multiple d'un mot.
▪ L'adresse contient un pointeur vers un emplacement de mémoire.
▪ La taille d’une adresse est souvent ajustée au mot, ou à une fraction de la taille d'un mot.
▪ Aujourd’hui la taille des mots de 64 bits est suffisante parce qu’elle satisfait
▪ La représentation de la précision des nombres à virgule flottante.
▪ Et couvre un espace d’adressage assez large de 264 bits.
Dr. E_H_B. TOURE / programmation parallèle 4
Architectures parallèles de processeurs
▪ Parallélisme niveau instruction
▪ L’exécution de chaque instruction est divisée en une séquence d’étapes (pipeline) :
▪ fetch: Récupérer de la mémoire la prochaine instruction à exécuter;
▪ decode : Décoder l’instruction récupérée à l’étape précédente;
▪ execute : Charger les opérandes spécifiés et exécuter l’instruction;
▪ Write back : Ecrire le résultat dans le régistre cible.

▪ L’avantage est que différents pipelines peuvent opérer en parallèle


▪ S’il n’y a pas de dépendance de traitements ou données entre les instructions exécutées
▪ Le nombre d’étapes détermine le degré de parallélisme atteignable par une machine pipelinée.

Dr. E_H_B. TOURE / programmation parallèle 5


Architectures parallèles de processeurs
▪ Parallélisme par de multiples unités fonctionnelles :
▪ Beaucoup de processeurs sont multi-issues
▪ Ils utilisent plusieurs unités fonctionnelles comme des UAL (Unités Arithmétiques et Logiques), unités
de flottants, unités d’opérations load/store, etc.
▪ Ces unités peuvent travailler en parallèle :
▪ Des instructions indépendantes peuvent être exécutées en parallèle par différentes unités fonctionnelles.
▪ Le nombre d’unités fonctionnelles pouvant être utilisé est restreint
▪ Il est déterminé dynamiquement à l’exécution par le matériel.

Dr. E_H_B. TOURE / programmation parallèle 6


Architectures parallèles de processeurs
▪ Parallélisme niveau processus ou thread (processus léger):
▪ Les techniques précédentes utilisent un flux de traitement séquentiel déterminé par le
compilateur
▪ Le compilateur définit l’ordre d’exécution des instructions en cas de dépendance.
▪ Leur degré de parallélisme est limité.
▪ Aujourd’hui les puces électroniques contiennent plus de transistors
▪ Cela peut permettre d’intégrer de plus grands caches sur la puce.
▪ Ou de mettre plusieurs cores (processeur multi-core) sur une seule et même puce.
▪ Chacun des cores aura son propre flux de traitement
▪ Des techinques de programmation parallèles peuvent être utilisées.
▪ Les cores de la puce accèdent à la même mémoire et peuvent se partager des caches.
▪ L’accès des cores à la mémoire peut être coordonné.

Dr. E_H_B. TOURE / programmation parallèle 7


Taxonomy de Flynn
▪ Il y a différentes façons de classifier des machines parallèles
▪ La taxonomie de Flynn distingue plusieurs architectures de machines
multi-processeurs
▪ Les architectures sont classées selon le type d'organisation du flux de
données et du flux d'instructions.
▪ Single Instruction, Single Data (SISD)
▪ Single Instruction, Multiple Data (SIMD)
▪ Multiple Instruction, Single Data (MISD)
▪ Multiple Instruction, Multiple Data (MIMD)

Dr. E_H_B. TOURE / programmation parallèle 8


Taxonomy de Flynn
▪ Single Instruction, Single Data (SISD):
▪ Machines séquentielles (non parallèles)
▪ Single Instruction:
▪ Seulement une instruction activée par le CPU pendant un cycle d’horloge
▪ Single Data:
▪ Seulement une donnée est utilisée comme input pendant un cycle d’horloge
▪ Exécution déterministe
▪ La plus ancienne machine
▪ Les ordinateurs personnels jusqu'à la fin des années 1990.

Dr. E_H_B. TOURE / programmation parallèle 9


Taxonomy de Flynn
▪ Single Instruction, Multiple Data (SIMD):
▪ Un type de machine parallèle
▪ Single Instruction:
▪ Toutes les unités de traitement exécutent la même instruction à chaque cycle d’horloge
▪ Multiple Data:
▪ Chaque unité de traitement peut opérer sur un élément de donnée différente
▪ Synchrone et une exécution déterministe
▪ Très adapté pour les systèmes traitant de grandes quantités de données d'une manière uniforme

Dr. E_H_B. TOURE / programmation parallèle 10


Taxonomy de Flynn
▪ Multiple Instruction, Single Data (MISD):
▪ Un type de machine parallèle
▪ Multiple Instruction:
▪ Plusieurs unités de traitement effectuant chacune différentes instructions.
▪ Single Data:
▪ Une seule donnée est alimentée dans plusieurs unités de traitement.
▪ Beaucoup plus rarement utilisé,
▪ Semble adapté à certains problèmes comme les réseaux neuronaux et aux problèmes temps-réel liés.

Dr. E_H_B. TOURE / programmation parallèle 11


Taxonomy de Flynn
▪ Multiple Instruction, Multiple Data (MIMD):
▪ Les systèmes utilisant plusieurs processeurs ou un processeur multi-cœur sont pleinement
parallèles
▪ Multiple Instruction:
▪ Chaque processeur peut exécuter une instruction différente
▪ Multiple Data:
▪ Chaque processeur peut travailler sur une donnée différente
▪ L’exécution peut être synchrone ou asynchrone, déterministe ou non-déterministe
▪ Actuellement, la plus commune machine parallèle.
▪ La plupart des super-machines modernes actuelles.

Dr. E_H_B. TOURE / programmation parallèle 12


Organisation de la mémoire de machines parallèles
▪ Les machines parallèles à usage général sont basées sur le modèle MIMD.
▪ Elles peuvent être classées selon l’organisation de leur mémoire :
▪ L’organisation physique de la mémoire
▪ Machines avec une mémoire physique partagée (multi-processeurs)
▪ Machines avec une mémoire physique distribuée (multi-ordinateurs)
▪ La vue de la mémoire par le programmeur
▪ Machines avec un espace d’adressage distribué,
▪ Machines avec un espace d’adressage partagé.
▪ La vue de la mémoire n’a pas besoin d’être conforme à la mémoire physique.
▪ Une machine parallèle avec une mémoire physique distribuée
▪ Peut être vue par le programmeur comme une machine avec un espace d’adressage partagé

Dr. E_H_B. TOURE / programmation parallèle 13


Machines avec une mémoire distribuée (DMM)
▪ Machines à Mémoires Distribuées (Distributed Memory Machines - DMM).
▪ Composées
▪ D’un certain nombre d’éléments de traitement (noeuds – nodes)
▪ Un noeud est une unité indépendante composée
▪ D’un processeur
▪ D’une mémoire locale
▪ Et parfois d’éléments péripériques
▪ Et d’un réseau d’interconnexion
▪ Qui connecte les noeuds et gère des données entre noeuds.

Dr. E_H_B. TOURE / programmation parallèle 14


Machines DMM
▪ Données stockées dans la mémoire locale d’un ou plusieurs noeuds.
▪ Toutes les mémoires locales sont privées
▪ et seul le processeur local a un accès direct à la mémoire locale.
▪ Si un processeur a besoin d’une donnée stockée dans la mémoire locale d’un autre
noeud, un envoi de messages est effectué.
▪ Soient deux processus PA et PB dans deux noeuds A et B
▪ Si PB a besoin de données de la mémoire locale du noeud A :
▪ PA effectue une opération d’envoi contenant les données pour le processus PB
▪ PB effectue une opération de réception spécifiant un tampon de réception pour stocker les données
provenant du processus PA.

Dr. E_H_B. TOURE / programmation parallèle 15


Machines avec une Mémoire Partagée (SMM)
▪ Machines à Mémoires Partagées (Shared memory machines - SMMs)
▪ Machine à mémoire partagée (mémoire globale)
▪ Une SMM est composée :
▪ D’un certain nombre de processeurs ou cores,
▪ D’une mémoire physique partagée (mémoire globale)
▪ Et d’un réseau d’interconnexion pour connecter les processeurs à la mémoire.
▪ Les données peuvent être échangées entre les processeurs à travers la mémoire globale par lecture
ou écriture de variables partagées.
▪ Physiquement, la mémoire globale est composée de différentes zones mémoires fournissant un
espace d’adressage commun pouvant être accessible par tous les processeurs.

Dr. E_H_B. TOURE / programmation parallèle 16


Machines avec une Mémoire Partagée (SMM)
▪ Physiquement, la mémoire globale est composée de différentes zones
mémoires fournissant un espace d’adressage commun pouvant être accessible
par tous les processeurs.
▪ Les SMMs utilisent des variables partagées accessibles par tous les processeurs.
▪ La communication et la coopération entre les processeurs sont effectuées via l’écriture et la lecture
de variables partagées stockées dans la mémoire globale.
▪ L’accés concurrent à ces variables partagées doit être évité vu qu’une situation de compétition (race
condition = « situation de course ») avec un résultat non prédictable peuvent se produire
▪ Race conditions (wikipédia) :
▪ Situation de compétition (ou situation de concurrence, accès concurrent, concurrence critique, course
critique, séquencement critique),
▪ Une situation de compétition peut survenir dès que plusieurs acteurs tentent d'accéder au même moment
à une ressource partagée (fichier, imprimante, etc.)
▪ Et qu'au moins l'un d'entre eux est susceptible de modifier son état.

Dr. E_H_B. TOURE / programmation parallèle 17


Partagée vs Distribuée
▪ DMMs:
▪ + : Techniquement simples à mettre en place
▪ Les ordinateurs standards peuvent être utilisés comme des noeuds.
▪ - : La programmation de DMMs nécessite une bonne représentation des données
▪ puisque chaque processeur n’accède directement qu’à ses données locales.

▪ SMMs :
▪ + : La communication à travers les variables partagées est simple
▪ donc pas nécessaire de dupliquer les données (comme c’est le cas pour les DMMs).
▪ - : Techniquement difficiles à mettre en place,
▪ Le réseau d’interconnexion doit fournir un accès rapide à la mémoire globale pour chaque
processeur.

Dr. E_H_B. TOURE / programmation parallèle 18


Réduction du temps d’accès mémoire
▪ Le temps d’accès mémoire joue un rôle important sur la performance.
▪ C’est aussi le cas pour des systèmes avec un espace d’adressage partagé.
▪ Pour l’évaluation de la performance, la latence et la bande passante (cadence)
▪ La latence est le temps total de terminaison d’une opération d’accès mémoire.
▪ Mesurée en microsecondes ou nanosecondes.
▪ La bande passante définit le nombre de données pouvant être lu par unité de temps.
▪ Mesurée en megabytes per second (MB/s) ou gigabytes par second (GB/s).

Dr. E_H_B. TOURE / programmation parallèle 19


Réduction du temps d’accès mémoire
▪ Multithreading
▪ Cacher la latence de l’accès mémoire en simulatn un nombre fixe de processeurs
virtuels pour chaque processeur.
▪ Après l’exécution d’une instruction machine, un switch implicite vers le prochain
processeur virtuel est effectué
▪ La latence de la mémoire est cachée en exécutant des instructions d’autres processeurs
virtuels
▪ Inconvénients
▪ La programmation doit être basée sur un grand nombre de processeurs virtuels.
▪ Les processeurs physiques doivent être conçus pour supporter la simulation de processeurs virtuels.

Dr. E_H_B. TOURE / programmation parallèle 20


Réduction du temps d’accès mémoire
▪ Cache
▪ Petit mais rapide mémoire entre le processeur et la mémoire principale.
▪ Utilisé pour stocker des données qui sont souvent accessibles par le processeur
▪ Evitant des accès couteux à la mémoire principale.
▪ Les données stockées dans le cache sont toujours un sous-ensemble de la mémoire principale
▪ La gestion des données dans le cache est assurée par le matériel.
▪ Pour chaque accès mémoire effectué par le processeur, le matériel vérifie en premier si l’adresse
mémoire spécifiée ne réside pas actuellement dans le cache.
▪ Le cas échéant, les données sont chargées à partir du cache et aucun accès mémoire n’est nécessaire.
▪ Les accès mémoires à partir d’un cache sont significativement plus rapides
▪ que ceux qui nécessitent un chargement à partir de la mémoire principale.

Dr. E_H_B. TOURE / programmation parallèle 21


Programmation parallèle

Dr El Hadji Bassirou TOURE


2021 - 2022

22

Vous aimerez peut-être aussi