PRODUIT : MATRICE – VECTEUR

DESA ANITS 2006 Calcul parallèleDESA ANITS 2006

PRODUIT :

MATRICE – VECTEUR

Exposé par :

M. Lamnii

M. Merzougui

A. Abbadi

CALCUL PARALLELE

10 pages

2DESA ANITS 2006 Calcul parallèleDESA ANITS 2006

PRODUIT MATRICE - VECTEUR

Soit A une matrice carré de taille n, et x un vecteur de taille n.

BUT :

Paralléliser le produit y = Ax , sur différents types de machines parallèles .

Analyse du problème

Programme séquentiel

Pour i ← 1 jusqu’à n

Y(i) ←0

Pour j ← 1 jusqu’à n

Y(i) ← Y(i) + A(i,j) * X(i)


1


PRODUIT MATRICE - VECTEURDépendance des calculs

Considérons un réseau de p processeurs.

la notion parallèle impose que chaque processeur dispose d’un nombre de données.

le calcul impose que chaque élément Aij rencontre xj . On considère une répartition équilibré ( p

divise n ) .

Pour simplifier :

Les élément de A sont rangés en lignes.

Nous examinons les cas :

Les élément de A sont rangés en colonnes.

2



Version par lignes

3

=

iL’organisation des calculs impose que la ième ligne du résultat Y soit placé dans le même processeur que la ième ligne de la matrice A

Dans ce cas chaque processeur contient le vecteur X et n/p lignes de la matrice A

P0

P1

P3

A00

A77



Algorithme

Coût de calcul

Pour tout processeur q de 0 à p-1 faire en parallèle

pour k ← 1 jusqu’à n/p

V(k) ← Produit scalaire de la ligne k de a et

le vecteur X.

On a exactement n/p produits scalaires nécessitant chacun 2n-1 opérations arithmétiques . si on note par a l’unité de calcul de base on a : (2n-1)*(n/p)* a Le coût en communication et celui d’un échange total dépend de la topologie du réseau 4



Version par colonnes

5

=

L’organisation des calculs impose que la jème colonne de A rencontre la jème composante du vecteur X.

Dans ce cas chaque processeur produit un vecteur résultat complet dont les composantes sont des sommes partielles. Cela revient à effectuer sur chaque processeur q des calculs locaux.

A00

A77

==

Po P1 P2


PRODUIT MATRICE - VECTEURAlgorithme

Coût de calcul


pour tout k ← 1 jusqu’à n/p faire

V- provisoire multiplication de la colonne k de a par la composante q+(k-1)p +1 du vecteur X.

On a exactement n/p calculs de n multiplications composante par composante, on y ajoute le coût de la sommation des sommes partielles sur tout le vecteur V, soit p sommes pour chacune des n/p composantes locales du vecteur V. Le coût en communication est de même ordre qu’un échange total sur toutes les topologies régulières. 6


PRODUIT MATRICE - VECTEURVersion par blocs

7

Solution intermédiaire entre la version par lignes et celle par colonnes permettant de réduire le coût en communication. Cette version suppose que chaque processeur ne possède qu’un bloc de la matrice formée d’une partie de lignes et une partie de colonnes.Pour simplifier :

P1

P3P2

PO

On suppose que n soit divisible par XA

Chaque processeur fait le calcul d’un morceau de vecteur résultat partielle qui correspond aux morceaux des colonnes de n/p composantes qu’il possède.


PRODUIT MATRICE - VECTEURAlgorithme

Coût de calcul


pour tout V partiel ← produit matrice–vecteur du bloc par le vecteur partielle X que l’on vient de recevoir.

On a exactement n/p calculs de n multiplications composante par composante, on y ajoute le coût de la sommation des sommes partielles sur tout le vecteur V, soit p sommes pour chacune des n/p composantes locales du vecteur V. Le coût en communication est de même ordre qu’un échange total sur toutes les topologies régulières. 8


PRODUIT MATRICE - VECTEURVersion Pipeline sur un anneau

9

Il présente une amélioration da la version par ligne,et se basé sur un pipeline de communications, sur un réseau de p processeur connectés en anneau. On considère :Les communications peuvent s’effectuer pendant que les processeurs calculent.

Chaque processeur a en mémoire r ligne de la matrice A rangé en matrice a de dimension rxn et r composantes du vecteur X

Distribution initiale



Principe du calcul

Première étape

La parallèlisation se déroule en p étapes. À chaque étape chaque processeur Pq fait le calcul en utilisant la partie de X qu’il contient en mémoire puis transmet cette partie au processeur P(q+1)mod p et reçoit une partie du processeur P(q-1+p)mod p

10

FIN

Documents

PRODUIT : MATRICE – VECTEUR