Chapitre III Systèmes multiprocesseurs · 2 c31+=a32b21, c32+=a32b22, c33+=a32b23 3 c31+=a33b31, c32+=a33b32, c33+=a33b33 10. Architectures parallèles, M. Eleuldj, Département

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, octobre 2014

Chapitre IIISystèmes multiprocesseurs

• Réseaux d’interconnexions• Classifications• Programmation• Routage

• Algorithmes parallèles• Sommes partielles• Multiplication matricielle• Transformée de Fourier

1


Réseaux d’interconnexions

A1

Réseau d’interconnexionA2

An

Ai : Téléphone, Processeur, Module mémoire, Ordinateur, Capteurs, …Exemples : Réseau local, Internet, Réseau d’interconnexion d’un multiprocesseurs,…

A1

A2

Am

2


Classifications

• Topologie : statique ou dynamique (reconfigurable)• Commutation : par circuit (TCP/IP) ou par paquet (UDP/IP)• Contrôle : centralisé ou distribué• Mode d’opération : synchrone ou asynchrone

3


Topologies statiques

Définition:dimension(réseau) : longueur maximale pour lier 2 nœudsconnexions(réseau) : nombre de liens du réseau

dimension(bus) = n-1dimension(graphe complet) = 1connexion(bus) = n-1connexion(graphe complet) = n(n-1)/2

4


Topologies dynamiques

Exemple : réseau Baseline nxn

n/2 x n/2

n/2 x n/2

0123

n-1n-2n-3n-4

.

.

.

.

0123

n-2n-3n-4

.

.

.

.

état 0

état 1

5


Routage du Baseline n=8

0 1 2 3 4 5 6 71 7 3 5 0 4 6 2p=( )

01

23

45

67

01

23

45

67

6


Exercice

Considérons un réseau baseline nxn :

a) Quel est le nombre des étages d’un réseau baseline nxn ?

b) Quel est le nombre total des cellules de base ?

c) Peut-on programmer n’importe quelle permutation ?

d) Comment peut on implémenter le contrôle ?

7


Sommes partielles

Problème : Calcul de S(k) = 0≤i≤k a(i) pour k = 0,1,...,n-1

Solution 1 : calcul direct → n(n- 1)/2 additionspour k = 0 à n-1 faire

somme = a(0)pour i = 1 à k faire

somme = somme + a(i)S(k) = somme

Solution 2 : Calcul non répétitif → (n – 1) additionsS(0) = a(0)pour k = 1 à n-1 faire

S(k) = S(k-1) + a(k)

Solution 3 : Tableau de processeurs (MIMD) → log n additions8

S(0)

S(1)

S(2)

S(3)

S(4)

S(5)

S(6)

S(7)

ET0

ET1

ET2

ET3

ET4

ET5

ET6

ET7Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, octobre 2014

Calcul MIMD des sommes partiellest3a0

a0+a1

a0+…+a2

a0+…+a3

a0+…+a4

a0+…+a5

a0+…+a6

a0+…+a7

t1a0

a0+a1

a1+a2

a2+a3

a3+a4

a4+a5

a5+a6

a6+a7

t2a0

a0+a1

a0+…+a2

a0+…+a3

a2+…+a5

a3+…+a6

a1+…+a4

a4+…+a7

t0

a1

a2

a3

a4

a5

a6

a7

a0

9


Produit matriciel (1/2)

a11a21a31b11b21b31c11c21c31

M2

a12a22a32b12b22b32c12c22c32

M3

a13a23a33b13b23b33c13c23c33

M1

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

A

B

C

i j En parallèle1 c11=0, c12=0, c13=0

1 c11+=a11b11, c12+=a11b12, c13+=a11b132 c11+=a12b21, c12+=a12b22, c13+=a12b233 c11+=a13b31, c12+=a13b32, c13+=a13b33

2 c21=0, c22=0, c23=01 c21+=a21b11, c22+=a21b12, c23+=a21b132 c21+=a22b21, c22+=a22b21, c23+=a22b233 c21+=a23b31, c22+=a23b32, c23+=a23b33

3 c31=0, c32=0, c33=01 c31+=a31b11, c32+=a31b12, c33+=a31b132 c31+=a32b21, c32+=a32b22, c33+=a32b233 c31+=a33b31, c32+=a33b32, c33+=a33b33

10


Produit matriciel (2/2)

pour i = 1 à n fairePar pour j = 1 à n faire cij = 0pour j = 1 à n faire

Par pour k = 1 à n fairecik = cik + aij*bjk

pour i = 1 à n fairepour j = 1 à n faire

cij = 0pour k = 1 à n faire

cij = cij + aij*bjk

SISD MIMD

Exercice : trouver le nombre de processeurs et le temps d’exécution.

11


Transformée de Fourier

Soit a = (a0,a1,…an-1)p(x) = an-1xn-1 + an-2xn-2 + … + a1x + a0Fw(a) = (p(1),p(w),…,p(wn-1))

A

B

X = A+B

k Y = (A-B)wk

Elément de base12

Documents

Chapitre III Systèmes multiprocesseurs · 2 c31+=a32b21, c32+=a32b22, c33+=a32b23 3 c31+=a33b31, c32+=a33b32, c33+=a33b33 10. Architectures parallèles, M. Eleuldj, Département