Architectures et Algorithmique Parallèles

Modèle SIMD : vectoriel

 Chaque processeur de cette architecture

exécute la même instruction à chaque cycle d'horloge, mais les données traitées sont différentes

 L'exécution est synchrone et déterministe sur

chaque processeur

22

12

CHAPITRE 2. MOD `ELES DE CALCULATEURS PARALL `ELES

– SIMD (« Single Instruction stream, Multiple Data stream »). Dans cette classe d’architectures, les processeurs sont fortement synchronis´es, et ex´ecutent au mˆeme instant la mˆeme instruction, chacun sur des donn´ees diff´erentes (fi- gure 2.3). Des informations de contexte (bits de masquage) permettent d’in- hiber l’ex´ecution d’une instruction sur une partie des processeurs.

Modèle SIMD...

FI

UC

E/S

FI

UT

UT

UT

FD

FD

FD

UM

UM

UM

FD

FD

FD

UM

Fig. 2.3 – Architecture SIMD.

• Ordinateur parallèle • Chaque processeur exécute la même instruction en

même temps

vectoriel

• Chaque processeur opère sur une donnée différente • Efficace surtout pour des

problèmes réguliers tels que le traitement d'image ou

Ces machines sont adapt´ees aux traitements r´eguliers, comme le calcul matri- ciel sur matrices pleines ou le traitement d’images. Elles perdent en revanche toute efficacit´e lorsque les traitements `a effectuer sont irr´eguliers et d´ependent fortement des donn´ees locales, car dans ce cas les processeurs sont inactifs la majorit´e du temps. Ainsi, pour ex´ecuter une instruction conditionnelle de type if. . . then. . . else (figure 2.4), l’ensemble des instructions des deux branches doit ˆetre pr´esent´e aux processeurs, qui d´ecident ou non de les ex´ecuter en fonction de leur bit local d’activit´e, positionn´e en fonction des valeurs de leurs variables locales.

23

• Exécution synchrone

déterministe

des branches.

14

Chacun des processeurs n’ex´ecutera effectivement que les instructions de l’une

Code source

Code compil´e

Chapitre 2 - Architecture matérielle

Ex´ecution,

cond=VRAI

Ex´ecution,

cond=FAUX

blocA

if (cond)

blocV;

else

blocA;

blocV;

blocF;

blocF;

blocB

blocB

ACTIF = (cond);

ACTIF = (cond);

ACTIF = (cond);

ACTIF = ~ACTIF;

ACTIF = ~ACTIF;

ACTIF = ~ACTIF;

ACTIF = VRAI

ACTIF = VRAI

ACTIF = VRAI

blocA;

blocV;

--

blocB

blocA;

--

blocF;

blocB

Fig. 2.4 – Ex´ecution d’une expression conditionnelle if. . . then. . . else sur une

architecture SIMD.

– MIMD (« Multiple Instruction stream, Multiple Data stream »). Cette classe

comprend les machines multi-processeurs, o`u chaque processeur ex´ecute son

propre code de mani`ere asynchrone et ind´ependante. On distingue habituel-

lement deux sous-classes, selon que les processeurs de la machine ont acc`es `a

une m´emoire commune (on parle alors de MIMD `a m´emoire partag´ee, « mul-

tiprocessor », figure 2.5), ou disposent chacun d’une m´emoire propre (MIMD

`a m´emoire distribu´ee, « multicomputer », figure 2.6). Dans ce dernier cas, un

r´eseau d’interconnexion est n´ecessaire pour ´echanger les informations entre

processeurs.

Cette classification est trop simple, car elle ne prend en compte ni les machines

vectorielles (qu’il faut ranger dans la cat´egorie SISD et non pas SIMD, car elles ne

Cours d’architectures et syst`emes des calculateurs parall`eles

Modèle SIMD...

 Exécution en mode SIMD : Déroulement,

performance ?

 speed-up, gain, accélération=temps modèle de

base/temps nouveau modèle

24

Modèle MISD

 Il existe peu d'exemples de cette classe de

systèmes parallèles : pipeline?

 Elle correspond aux systèmes capables

d'exécuter plusieurs instructions sur la même données durant le même cycle d'horloge

25

Chapitre 2

Mod`eles de calculateurs

parall`eles

Afin de d´efinir et comparer les architectures de machines, plusieurs classifications

ont ´et´e d´evelopp´ees.

2.1 Classification de Flynn

La classification la plus connue est celle de Flynn [2], qui caract´erise les machines

suivant leurs flots de donn´ees et d’instructions, ce qui donne quatre cat´egories :

– SISD (« Single Instruction stream, Single Data stream »). Cette cat´egorie cor-

respond aux machines s´equentielles conventionnelles, pour lesquelles chaque

op´eration s’effectue sur une donn´ee `a la fois (figure 2.1) ;

FI

UT

FI

FD

UM

E/S

UC

Fig. 2.1 – Architecture SISD. L’unit´e de contrˆole (UC), recevant son flot d’instruc-

tions (FI) de l’unit´e m´emoire (UM), envoie les instructions `a l’unit´e de traitement (UT), qui effectue ses op´erations sur le flot de donn´ees (FD) provenant de l’unit´e m´emoire.

– MISD (« Multiple Instruction stream, Single Data stream »). Cette cat´egorie regroupe les machines sp´ecialis´ees de type « systolique », dont les processeurs, arrang´es selon une topologie fixe, sont fortement synchronis´es (figure 2.2) ;

Modèle MISD...

FI

FD

UM

E/S

UC FI

UT

FD

UC FI

UT

FD

UC FI

UT

Fig. 2.2 – Architecture MISD.

11

26

• un seul flux de données

est traité par de multiples

processeurs

• Chaque processeur opère sur chaque donnée via un flux distinct d'instructions • Architecture peu courante • Pourrait par exemple servir à tenter de déchiffrer un même message avec différents algorithmes

16

Chapitre 2 - Architecture matérielle

Modèle pipeline...

 Permet de cacher la latence des traitements

pour augmenter le débit

 L’opérateur pipeline est formé de k étages, et le

temps de traversée d’un étage dure t

 Le programme est composé de n instructions

 temps total ?

27

Modèle Pipeline...

 Traiter par pipeline une opération arithmétique à

deux opérandes v(1)+v(2)

 Décomposition de l’opération en 5 étapes  décodage de l’instruction  calcul des adresses des opérandes  chargement opérande 1 chargement opérande

2

 exécution de l’opération

28

Modèle Pipeline...

 Exécution en mode MISD : Déroulement,

performance

 ?

29

Modèle Pipeline: Étages de durées différentes

 Un autre exemple  Chaque instruction peut être découpée en

quatre sous-traitements : – le premier de durée 2t – le second de durée 3t – le troisième de durée t – le dernier de durée 4t

 Représentez le diagramme de Gantt  Temps ? accélération?  Amélioration ?

30

Modèle Pipeline: dépendance

 Un autre exemple  A =B*C+D*E, F =G*H+I*J  utilisation de deux registres et pipeline à 5 étages  Représentez le diagramme de Gantt  Temps ? accélération?  Amélioration ?

31

MIMD

 C'est dans cette catégorie que l'on trouve le

plus de systèmes parallèles

 A chaque cycle d'horloge, chaque processeur exécute une instruction différente sur une donnée différente

 Ces exécutions peuvent être synchrones ou

non, déterministes ou non

32

MIMD...

• Actuellement, type le plus commun

d'ordinateur parallèle ✓ Processeur multi-coeurs

✓ Colosse

• Chaque processeur peut exécuter

un programme différent et travailler sur des données

différentes

• l'exécution peut être synchrone, asynchrone, déterministe ou non déterministe

• Plusieurs ordinateurs MIMD incorporent un ou plusieurs composants SIMD

✓ par exemple, des GPGPUs

17

Chapitre 2 - Architecture matérielle

33

MIMD...

34

MIMD.... Exemple

 Exécution en mode MIMD : Déroulement,

performance ?

35

MIMD: Organisation de la mémoire

 Trois types d'organisation de la mémoire :

– la mémoire partagée; on parle de multi-processeurs

(SM)

– la mémoire distribuée; on parle de multi-ordinateurs

(DM)

– la mémoire hybride : C’est un mélange des deux premiers. Dans cette architecture, il y a plusieurs groupes de processeurs partageant de la mémoire qui communiquent grâce à un réseau

36

MIMD: Organisation de la Le Modèle MIMD: classification mémoire...

MIMD

Fortement couplés

Faiblement couplés

Multiprocesseurs (mémoire partagée)

Multicalculateurs (mémoire privée)

Bus

commutateur

Bus (LAN)

commutateur

37

Multiprocesseurs/ Multicalculateurs

MIMD: Organisation de la mémoire...

P

P

P

Réseau

M M

M

M

P

M M

P

P

Réseau

Mémoire partagée

Mémoire privée

38

MIMD: Mémoire partagée  Les processeurs accèdent à la même mémoire

partagée qui doit se comporter comme une mémoire à plusieurs ports

 La mémoire partagée est construite à partir de

plusieurs composants mémoire

 un réseau d'interconnexion relie les composants

mémoire et les processeurs

16

2 Parallel Computer Architecture



Fig. 2.4 Illustration of a computer with shared memory: (a) abstract view and (b) implementation of the shared memory with memory modules

(a)

P

P

(b)

P

P

interconnection network

interconnection network

shared memory

M

M

memory modules

• La mémoire distribuée implique le passage de messages of a number of processors or cores, a shared physical memory (global memory), and entre les processeurs, à travers une couche logicielle an interconnection network to connect the processors with the memory. The shared

39

✓ la couche logicielle augmente la latence

memory can be implemented as a set of memory modules. Data can be exchanged

between processors via the global memory by reading or writing shared variables.

• La mémoire partagée permet à chaque processeur

The cores of a multicore processor are an example for an SMM, see Sect. 2.4.2 for

d'accéder directement à toute la mémoire de façon

a more detailed description. Physically, the global memory usually consists of sep-

arate memory modules providing a common address space which can be accessed

matérielle (transparente)

by all processors, see Fig. 2.4 for an illustration.

A natural programming model for SMMs is the use of shared variables which

✓ permet de minimiser la latence, mais augmente les coûts et limite

can be accessed by all processors. Communication and cooperation between the

l'extensibilité

processors is organized by writing and reading shared variables that are stored in

the global memory. Accessing shared variables concurrently by several processors

should be avoided since race conditions with unpredictable effects can occur, see

Chapitre 2 - Architecture matérielle

21

also Chaps. 3 and 6.

The existence of a global memory is a significant advantage, since communi-

cation via shared variables is easy and since no data replication is necessary as is

sometimes the case for DMMs. But technically, the realization of SMMs requires

a larger effort, in particular because the interconnection network must provide fast

access to the global memory for each processor. This can be ensured for a small

number of processors, but scaling beyond a few dozen processors is difficult.

A special variant of SMMs are symmetric multiprocessors (SMPs). SMPs have

a single shared memory which provides a uniform access time from any processor

for all memory locations, i.e., all memory locations are equidistant to all processors

[35, 84]. SMPs usually have a small number of processors that are connected via a

central bus which also provides access to the shared memory. There are usually no

private memories of processors or specific I/O processors, but each processor has a

private cache hierarchy. As usual, access to a local cache is faster than access to the

global memory. In the spirit of the definition from above, each multicore processor

with several cores is an SMP system.

SMPs usually have only a small number of processors, since the central bus

provides a constant bandwidth which is shared by all processors. When too many

processors are connected, more and more access collisions may occur, thus increas-

ing the effective memory access time. This can be alleviated by the use of caches

and suitable cache coherence protocols, see Sect. 2.7.3. The maximum number of

processors used in bus-based SMPs typically lies between 32 and 64.

Parallel programs for SMMs are often based on the execution of threads. A thread

is a separate control flow which shares data with other threads via a global address

MIMD: Mémoire partagée...

 Permet d’accéder directement à toute la

mémoire de façon transparente

 Minimiser la latence  Limiter l’extensibilité



40

MIMD: Mémoire partagée

 travailler avec des variables globales

 économiser la mémoire en évitant les

réplications inutiles

 déployer des mécanismes de synchronisation

des accès à la mémoire



41

MIMD: Mémoire partagée (Bus)  Un certains nombre d'UC sont connectés à un

bus

 La lecture (ou l'écriture) se fait en mettant l'adresse du mot mémoire sur le bus et en déclenchant le signal approprié (Lecture ou Ecriture)



42

MIMD: Mémoire partagée (Bus...)

 Limite: surcharge du bus

 Solution: ajouter une mémoire cache entre l'UC

et le Bus: – le cache conserve les mots mémoire auxquels on a

récemment fait accès

– tous les accès mémoire passent par le cache



43

MIMD: Mémoire partagée (Commutateurs) – Construire 1 Multiprocesseur comportant plus de 64

Processeurs

– Diviser la mémoire en Modules que l ’on relie aux

processeurs (N):

 CROSSBAR switch: Matrice de commutateurs (NxN

noeuds de commutateurs);

 OMEGA: basé sur les commutateurs 2x2 (Log2(N)

commutateurs/étages)

44

MIMD: Mémoire partagée Multiprocesseurs à (Commutateurs...) commutateurs : Exemples

Nœud de commutation

Commutateur 2x2

P r o c e s s e u r s

P r o c e s s e u r s

M é m o i r e s

Mémoires

CROSSBAR

OMEGA

45

18

2 Parallel Computer Architecture

2 Parallel Computer Architecture

(a)

P

1

P

2

18

cache

ehcac

(b)

P1

2P

M 1

M 2

P

n

ehcac

(a)

P

1

P

2

cache

ehcac

memory

processing

elements

nP

P1

(b)

Mn

2P

interconnection network

M 1

M 2

P

n

ehcac

memory

processing

elements

nP

Mn

18

MIMD....Mémoire partagée

interconnection network

(c)

1P

2 Parallel Computer Architecture nP

2P

(c)

processing

(a)

P

1

P

2

cache

ehcac

1C

M 1

2C P n

ehcac

nC

1P

2P

elements

M 2

1C

M n

2C

nP

nC

processing

elements

M 1

M 2

M n

interconnection network

memory

interconnection network

(b)

P1

2P

M 1

M 2

(d)

Processor

nP

Cache

P

1

Mn C 1

interconnection network

processing P elements

2

C

2

(d)

P

Processor

C

Cache

n P

1

n C

1

processing P 2 elements C 2

P

n

C

n

processing

elements

interconnection network

interconnection network

(c)

1P

1C

Fig. 2.5 Illustration of the architecture of computers with shared memory: (a) SMP – symmet- ric multiprocessors, (b) NUMA – non-uniform memory access, (c) CC-NUMA – cache-coherent NUMA, and (d) COMA – cache-only memory access

Fig. 2.5 Illustration of the architecture of computers with shared memory: (a) SMP – symmet- ric multiprocessors, (b) NUMA – non-uniform memory access, (c) CC-NUMA – cache-coherent processing NUMA, and (d) COMA – cache-only memory access elements

nC

2C

nP

2P

23

M 1

M 2

M n

Chapitre 2 - Architecture matérielle

46

more and more important to get good performance results at program level. This is also true for parallel programs, in particular if a shared address space is used.

more and more important to get good performance results at program level. This is also true for parallel programs, in particular if a shared address space is used. Reducing the average latency observed by a processor when accessing memory can

interconnection network

(d)

Processor

Cache

Reducing the average latency observed by a processor when accessing memory can

increase the resulting program performance significantly.

1

2

P

P

increase the resulting program performance significantly.

Two important approaches have been considered to reduce the average latency

Two important approaches have been considered to reduce the average latency

for memory access [14]: the simulation of virtual processors by each physical

processing

for memory access [14]: the simulation of virtual processors by each physical

processor (multithreading) and the use of local caches to store data values that are

elements

accessed often. We give now a short overview of these approaches in the following.

processor (multithreading) and the use of local caches to store data values that are

C

C

P

C

n

n

1

2

accessed often. We give now a short overview of these approaches in the following.

interconnection network

Fig. 2.5 Illustration of the architecture of computers with shared memory: (a) SMP – symmet-

ric multiprocessors, (b) NUMA – non-uniform memory access, (c) CC-NUMA – cache-coherent

NUMA, and (d) COMA – cache-only memory access

more and more important to get good performance results at program level. This

is also true for parallel programs, in particular if a shared address space is used.

Reducing the average latency observed by a processor when accessing memory can

increase the resulting program performance significantly.

Two important approaches have been considered to reduce the average latency

for memory access [14]: the simulation of virtual processors by each physical

processor (multithreading) and the use of local caches to store data values that are

accessed often. We give now a short overview of these approaches in the following.

a) a)

a)

b) b) b)

b)

c)

c) c) c)

d)

d) d) d)

2.3 Memory Organization of Parallel Computers

13

2.3 Memory Organization of Parallel Computers

2.3 Memory Organization of Parallel Computers

13

13

a)

b)

interconnection network

P

P

MM

P

M

P = processor

a)

a)

interconnection network

interconnection network

M = local memory

P

P

P

P

MM

MM

P

P

M

M

P = processor

P = processor

M = local memory

M = local memory

node consisting of processor and local memory

b)

b)

node consisting of processor and local memory

node consisting of processor and local memory

computer with distributed memory with a hypercube as interconnection network

computer with distributed memory computer with distributed memory with a hypercube as with a hypercube as interconnection network interconnection network

2.3 Memory Organization of Parallel Computers

13

2.3 Memory Organization of Parallel Computers 2.3 Memory Organization of Parallel Computers 2.3 Memory Organization of Parallel Computers

interconnection network

a)

c)

MIMD: Mémoire distribuée

interconnection network

c) c)

13

P = processor

DMA (direct memory access) DMA (direct memory access) with DMA connections with DMA connections to the network to the network

13 13

DMA (direct memory access) interconnection network interconnection network with DMA connections to the network DMA DMA

DMA DMA

M M

P P

M M

P P

interconnection network interconnection network interconnection network P P MM P P P P MM P P MM MM

P M

P M

M

DMA

M = local memory P = processor DMA P = processor M P P = processor M = local memory M = local memory

M = local memory

P

P M P d) M node consisting of processor and local memory

d) d)

M

P

node consisting of processor and local memory node consisting of processor and local memory computer with distributed memory ... ... external node consisting of processor and local memory Router computer with distributed memory computer with distributed memory input channels with a hypercube as with a hypercube as computer with distributed memory with a hypercube as interconnection network interconnection network with a hypercube as interconnection network N N N interconnection network

e) e)

e)

. . .

. . .

external external input channels input channels

. . . . . .

external output channels

N N

R R

N N

R R

interconnection network

interconnection network interconnection network interconnection network DMA DMA

R

R

N

M

DMA P DMA

DMA

P

P P

M M M

M

N P

DMA

P DMA M P M R DMA M P P M

R

R

N

DMA (direct memory access) with DMA connections to the network

DMA (direct memory access) DMA (direct memory access) N with DMA connections DMA (direct memory access) with DMA connections to the network with DMA connections to the network N to the network

R = Router N N R R N = node consisting of processor and local memory R R

N N

N N

N N

R R

N

R R

R

R

P P

M M

... ... ... ... Router Router

. . . . . .

external external output channels output channels

R = Router R = Router

N = node consisting of N = node consisting of processor and processor and local memory local memory

N N

N N

N N

R R

R R

R R

R

R

Fig. 2.3 Illustration of computers with distributed memory: (a) abstract structure, (b) computer Fig. 2.3 Illustration of computers with distributed memory: (a) abstract structure, (b) computer with distributed memory and hypercube as interconnection structure, (c) DMA (direct memory with distributed memory and hypercube as interconnection structure, (c) DMA (direct memory access), (d) processor–memory node with router, and (e) interconnection network in the form of a access), (d) processor–memory node with router, and (e) interconnection network in the form of a mesh to connect the routers of the different processor–memory nodes mesh to connect the routers of the different processor–memory nodes

external input channels external external input channels external input channels input channels N R

. . .

N

Fig. 2.3 Illustration of computers with distributed memory: (a) abstract structure, (b) computer with distributed memory and hypercube as interconnection structure, (c) DMA (direct memory M P M P ... ... access), (d) processor–memory node with router, and (e) interconnection network in the form of a external Router M P output channels mesh to connect the routers of the different processor–memory nodes ... ... ... ... external external Router ... ... output channels Router output channels external Router output channels

. . .

. . .

. . .

. . .

. . .

. . .

. . .

20 e)

N

e)

e)

e)

R

R

R

N

R

R

R

N

R

R

R

R

R

R

47 Program data is stored in the local memory of one or several nodes. All local Program data is stored in the local memory of one or several nodes. All local memory is private and only the local processor can access the local memory directly. memory is private and only the local processor can access the local memory directly. Chapitre 2 - Architecture matérielle When a processor needs data from the local memory of other nodes to perform When a processor needs data from the local memory of other nodes to perform local computations, message-passing has to be performed via the interconnection local computations, message-passing has to be performed via the interconnection

Program data is stored in the local memory of one or several nodes. All local R memory is private and only the local processor can access the local memory directly.

N

N

N

N

R = Router

R

R

N

R

N

N

When a processor needs data from the local memory of other nodes to perform

network. Therefore, distributed memory machines are strongly connected with the

network. Therefore, distributed memory machines are strongly connected with the

N = node consisting of

local computations, message-passing has to be performed via the interconnection

message-passing programming model which is based on communication between

message-passing programming model which is based on communication between

network. Therefore, distributed memory machines are strongly connected with the

cooperating sequential processes and which will be considered in more detail in

cooperating sequential processes and which will be considered in more detail in

N = node consisting of

processor and

R = Router

local memory

R = Router

R = Router

R

N

N

R

N

N

N

R

N

N

message-passing programming model which is based on communication between

cooperating sequential processes and which will be considered in more detail in

processor and

N = node consisting of

N = node consisting of

processor and

processor and

local memory

N

N

N

N

N

N

R

R

N

R

R

N

R

R

R

R

R

R

R

R

R

R

N

N

R

Fig. 2.3 Illustration of computers with distributed memory: (a) abstract structure, (b) computer

local memory

local memory

N

N

with distributed memory and hypercube as interconnection structure, (c) DMA (direct memory

N

N

R

N

N

N

access), (d) processor–memory node with router, and (e) interconnection network in the form of a

mesh to connect the routers of the different processor–memory nodes

Fig. 2.3 Illustration of computers with distributed memory: (a) abstract structure, (b) computer

with distributed memory and hypercube as interconnection structure, (c) DMA (direct memory

Fig. 2.3 Illustration of computers with distributed memory: (a) abstract structure, (b) computer

Fig. 2.3 Illustration of computers with distributed memory: (a) abstract structure, (b) computer

access), (d) processor–memory node with router, and (e) interconnection network in the form of a

with distributed memory and hypercube as interconnection structure, (c) DMA (direct memory

with distributed memory and hypercube as interconnection structure, (c) DMA (direct memory

Program data is stored in the local memory of one or several nodes. All local

access), (d) processor–memory node with router, and (e) interconnection network in the form of a

mesh to connect the routers of the different processor–memory nodes

access), (d) processor–memory node with router, and (e) interconnection network in the form of a

memory is private and only the local processor can access the local memory directly.

mesh to connect the routers of the different processor–memory nodes

mesh to connect the routers of the different processor–memory nodes

When a processor needs data from the local memory of other nodes to perform

local computations, message-passing has to be performed via the interconnection

Program data is stored in the local memory of one or several nodes. All local

network. Therefore, distributed memory machines are strongly connected with the

memory is private and only the local processor can access the local memory directly.

Program data is stored in the local memory of one or several nodes. All loc