Cours: Algo. & Archi. ParallËles

Description

master, Supérieur, Master

• mémoire - matière potentielle : distribuée
• mémoire - matière potentielle : globale
• mémoire - matière potentielle : selon deux critères
• mémoire

1Cours:Algo. & Archi. Parallèles République Algérienne Démocratique et Populaire Ministère de l'Enseignement Supérieur et de la Recherche Scientifique Centre universitaire d'EL-OUED Enseignant : Saci MEDILEH Département d'informatique 1re année master Année universitaire : 2010/2011 Chapitre I: Introduction aux architectures parallèles (suite…) 14/11/2010 Cours: Algo. & Archi. Parallèles 2 Plan  Introduction  Historiques  Définitions  Classification  Les sources du parallélisme

• sources de parallélisme limites
• définitions 
• parallèle
• parallèles
• parallélisme de données
• populaire ministère de l'enseignement supérieur et de la recherche scientifique

Sujets

• Mémoire
• Neumann
• Donnée
• Parallélisme
• Source
• Enseignement
• Recherche (homonymie)

Informations

• Publié par: zeap
• Nombre de lectures: 66
• Langue: Français

Extrait

République Algérienne Démocratique et Populaire
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Centre universitaire d EL-OUED
Cours:
Algo. & Archi. Parallèles
Chapitre I:
Introduction aux architectures
parallèles (suite &)
Enseignant : Saci MEDILEH
Département d informatique
re1 année master
Année universitaire : 2010/2011
Plan
ðl Introduction
ðl Historiques
ðl Définitions
ðl Classification
ðl Les sources du parallélisme
14/11/2010 Cours: Algo. & Archi. Parallèles 2
1Classification
1. Classification de Flynn (1966) : Le plus connue!!!
ðl Caractérise les machines suivants leurs flots de
données et d instructions.
ðl Quatre catégories:
ðl SISD
𧫠Single Instruction stream, Single Data stream »
ðl MISD
𧫠Multiple Instruction stream, Single Data stream »
ðl SIMD
𧫠Single Instruction stream, Multiple Data stream »
ðl MIMD
𧫠Multiple Instruction stream, Multiple Data stream »
14/11/2010 Cours: Algo. & Archi. Parallèles 3
Classification
1. Classification de Flynn (1966) : Le plus connue!!!
ðl SISD
ðl Cette catégorie correspond aux machines
séquentielles conventionnelles, pour lesquelles chaque
opération s'effectue sur une donnée a la fois.
ðl N'exploite aucun parallélisme.
ðl Correspond à l'architecture de Von Neumann.
14/11/2010 Cours: Algo. & Archi. Parallèles 4
2Classification
1. Classification de Flynn (1966) : Le plus connue!!!
ðl MISD
ðl Il s'agit d'un ordinateur dans lequel une même donnée
est traitée par plusieurs processeurs en parallèle.
ðl Machines spécialisées de type « systolique »
ðl les processeurs, arranges selon une topologie fixe,
sont fortement synchronises.
14/11/2010 Cours: Algo. & Archi. Parallèles 5
Classification
1. Classification de Flynn (1966) : Le plus connue!!!
ðl SIMD
ðl Il s'agit d'un ordinateur qui utilise le parallélisme au
niveau de la mémoire, par exemple le processeur
vectoriel.
ðl les processeurs sont fortement synchronises, et
exécutent au même instant la même instruction,
chacun sur des données différentes.
14/11/2010 Cours: Algo. & Archi. Parallèles 6
3Classification
1. Classification de Flynn (1966) : Le plus connue!!!
ðl MIMD
ðl plusieurs processeurs traitent des données
différentes.
ðl MIMD à mémoire partagée:
ð§Les processeurs ont accès à la mémoire comme un espace
d'adressage global.
ð§Tout changement dans une case mémoire est vu par les autres
CPU.
ð§La communication inter-CPU est effectuée via la mémoire
globale.
14/11/2010 Cours: Algo. & Archi. Parallèles 7
Classification
1. Classification de Flynn (1966) : Le plus connue!!!
ðl MIMD
ðl plusieurs processeurs traitent des données
différentes.
ðl MIMD à mémoire partagée, multiprocesseurs
14/11/2010 Cours: Algo. & Archi. Parallèles 8
4Classification
1. Classification de Flynn (1966) : Le plus connue!!!
ðl MIMD
ðl MIMD à mémoire distribuée, multi-computer
ð§Chaque CPU a sa propre mémoire
ð§Un réseau d'interconnexion est nécessaire pour échanger les
informations entre processeurs.
14/11/2010 Cours: Algo. & Archi. Parallèles 9
Classification
1. Classification de Raina
ðl Une sous-classification étendue des machines MIMD,
due à Raina
ðl Classification par mémoire selon deux critères:
ðl L espace d adressage
ðl SASM « Single Address space, Shared Memory » : mémoire
partagée ;
ðl DADM « Distributed Address space, Distributed Memory » :
mémoire distribuée, L'échange de données entre
processeurs s'effectué nécessairement par passage de
messages, au moyen d'un réseau de communication ;
ðl SADM « Single Address space, Distributed Memory »:
mémoire distribuée, avec espace d'adressage global,
autorisant éventuellement l'accès aux données situées sur
d'autres processeurs.
14/11/2010 Cours: Algo. & Archi. Parallèles 10
5Classification
1. Classification de Raina
ðl Classification par mémoire selon deux critères:
ðl Le type d'accès mémoire mis en S uvre :
ðl NORMA « No Remote Memory Access » : pas de
moyen d'accès aux données distantes, nécessitant le
passage de messages ;
ðl UMA « Uniform Memory Access » : accès symétrique à
la mémoire, de coût identique pour tous les
processeurs ;
ðl NUMA « Non-Uniform Memory Access » : les
performances d'accès dépendent de la localisation des
données ;
14/11/2010 Cours: Algo. & Archi. Parallèles 11
Plan
ðl Introduction
ðl Historiques
ðl Définitions
ðl Classification
ðl Les sources du parallélisme
14/11/2010 Cours: Algo. & Archi. Parallèles 12
6Les sources de parallélisme
On peut avoir différentes sources de parallélisme :
ðl le parallélisme de données : la même opération
est effectuée par chaque processeur sur des
données différentes.
!Ò diviser ces grands volumes de données en
morceaux qui seront traités par différentes
unités de calcul.
Typiquement: les ordinateurs vectoriels
14/11/2010 Cours: Algo. & Archi. Parallèles 13
Les sources de parallélisme
On peut avoir différentes sources de parallélisme :
ðl Le parallélisme de contrôle : des opérations
sont réalisées simultanément sur plusieurs
processeurs. Le programme présente des
séquences d'opérations indépendantes qui
peuvent être exécutées en parallèle.
ðl Exemple : (x+3)*(a+b)-(e-f)
Calculer:
ðl (x+3) et (a+b) et (e-f)
ðl puis (x+3)*(a+b) (noté z)
ðl puis z-(e-f)
!Ò 3 processeurs
3 unités de temps
14/11/2010 Cours: Algo. & Archi. Parallèles 14
7Les sources de parallélisme
On peut avoir différentes sources de parallélisme :
ðl le parallélisme de flux : Les opérations sur un
même flux de données peuvent être enchaînées
(pipeline)
Principe:
ðl fonctionnement selon le schéma du travail à la
chaîne.
14/11/2010 Cours: Algo. & Archi. Parallèles 15
Les sources de parallélisme
Limites de parallélisme
ðl Dépendance de données :
!Ò les instructions doivent être indépendantes :
- exécuter dans un ordre quelconque
- simultanément
14/11/2010 Cours: Algo. & Archi. Parallèles 16
8-
-
-
-
Les sources de parallélisme
Limites de parallélisme?!!
ðl Dépendances de contrôle :
Exemple:
I1: a=b+c; I1 et I4 sont à priori indépendantes
I2: if (a<0) mais selon la valeur de la variable 'a'
I3: {d=e+f;} I3 peut être exécuté ou non
I4: g=d+h; entraînant une dépendance entre I3 et I4
14/11/2010 Cours: Algo. & Archi. Parallèles 17
Les sources de parallélisme
Limites de parallélisme?!!
ðl les dépendances de ressources : nombre
insuffisant de processeurs pour effectuer les
instructions en parallèle alors qu'elles sont
indépendantes les unes des autres.
ðl Rapport temps de communication / temps de
calcul : Il n'est pas toujours avantageux de
paralléliser une application. Les communications
peuvent dans certain cas augmenter le temps
d'exécution.
14/11/2010 Cours: Algo. & Archi. Parallèles 18
9