Architectures et Algorithmique Parallèles

op eration seectue sur une donn ee `a la fois (gure 2.1) ;

fois

" Ordinateur s quentiel

(non parall le)

" Un seul flux d'instructions, une

instruction la fois

" Une seule donn e la fois

" Ex cution d terministe

" Correspond au mod le

d'ordinateur le plus commun

E/S

FI

UC

FI

UT

FD

UM

Fig. 2.1 Architecture SISD. Lunit e de contr ole (UC), recevant son ot dinstruc-

tions (FI) de lunit e m emoire (UM), envoie les instructions `a lunit e de traitement

(UT), qui eectue ses op erations sur le ot de donn ees (FD) provenant de lunit e

m emoire.

20

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 xe, sont fortement synchronis es (gure 2.2) ;

12

Chapitre 2 - Architecture mat rielle

FI

E/S

UM

UC

FI

UT

UC

FI

UT

FD

FD

FD

UC

FI

UT

Fig. 2.2 Architecture MISD.

11

Mod le SISD...

Ex cution en mode SISD : D roulement,

performance

pour i de 1 n faire

v(i)=v1(i)+v2(i)

21

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

darchitectures, les processeurs sont fortement synchronis es, et ex ecutent au

m eme instant la m eme instruction, chacun sur des donn ees di erentes (-

gure 2.3). Des informations de contexte (bits de masquage) permettent din-

hiber lex ecution dune 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 dimages. Elles perdent en revanche

toute ecacit e lorsque les traitements `a eectuer 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

(gure 2.4), lensemble 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 dactivit e, positionn e en fonction des valeurs de leurs variables locales.

23

" Ex cution synchrone

d terministe

des branches.

14

Chacun des processeurs nex ecutera eectivement que les instructions de lune

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 dune 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 acces a

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

tiprocessor , gure 2.5), ou disposent chacun dune m emoire propre (MIMD

`a m emoire distribu ee, multicomputer , gure 2.6). Dans ce dernier cas, un

r eseau dinterconnexion est n ecessaire pour echanger les informations entre

processeurs.

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

vectorielles (quil faut ranger dans la cat egorie SISD et non pas SIMD, car elles ne

Cours darchitectures et systemes des calculateurs paralleles

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

An de d enir et comparer les architectures de machines, plusieurs classications

ont et e d evelopp ees.

2.1 Classication de Flynn

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

suivant leurs ots de donn ees et dinstructions, 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 seectue sur une donn ee `a la fois (gure 2.1) ;

FI

UT

FI

FD

UM

E/S

UC

Fig. 2.1 Architecture SISD. Lunit e de contr ole (UC), recevant son ot dinstruc-

tions (FI) de lunit e m emoire (UM), envoie les instructions `a lunit e de traitement

(UT), qui eectue ses op erations sur le ot de donn ees (FD) provenant de lunit 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 xe, sont fortement synchronis es (gure 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

Lop rateur pipeline est form de k tages, et le

temps de travers e dun 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 lop ration en 5 tapes

d codage de linstruction

calcul des adresses des op randes

chargement op rande 1 chargement op rande

2

ex cution de lop 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 =BC+DE, F =GH+IJ

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 : Cest 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 signicant 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 difcult.

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 specic 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 denition 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 ow which shares data with other threads via a global address

MIMD: M moire partag e...

Permet dacc der directement toute la

m moire de fa on transparente

Minimiser la latence

Limiter lextensibilit

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

NSud 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 signicantly.

1

2

P

P

increase the resulting program performance signicantly.

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 signicantly.

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) processormemory node with router, and (e) interconnection network in the form of a

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

mesh to connect the routers of the different processormemory nodes

mesh to connect the routers of the different processormemory 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) processormemory 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 processormemory 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.

C...