Exposé GT 24/10/2002 Dimitri Lecas. ScotchFaxBlendSopalin graphe sequentielparallele global local...

Exposé GT 24/10/2002

Dimitri Lecas

Scotch

PaStiX

Scotch Fax Blend Sopalin

graphe

sequentiel parallele

globallocal

symbolique numerique

noeud ddl

permutation symbolMatrixsolverMatrix distribuée

solverMatrixdistribuée etfactorisée

solutiondistribuée

element

Fax

Factorisation Symbolique

Blend

Scotch Fax Blend Sopalin

graphe

sequentiel parallele

globallocal

symbolique numerique

noeud ddl

permutation symbolMatrixsolverMatrix distribuée

solverMatrixdistribuée etfactorisée

solutiondistribuée

element

Repartitionnement et distribution des blocs

Gère le parallélisme induit par le creux (arbre d’élimination par blocs).

Découpe et distribue les blocs afin de prendre en compte le parallélisme potentiel induit par les calculs en plein .

Utilise la taille de bloc optimale pour les routines BLAS de niveau 3.

Arbre d’élimination par blocs

Repartitionnement de la matrice

Graphe de tâches

Matrice symboliquepar blocs

Modélisation coûts calcul et comm

Nombre de processeurs

Distribution et ordonnancement

Données locales Ordonnancement tâches

Schéma de communication

Factorisation et résolution //

Estimation du temps de calcul

Espace Mémoire nécessaire

Repartitionnement de la matrice

Graphe de tâches

Matrice symboliquepar blocs

Modélisation coûts calcul et comm

Nombre de processeurs

Distribution et ordonnancement

Données locales Ordonnancement tâches

Schéma de communication Limitation

mémoire

Réduction surcoût mémoireFactorisation

et résolution //

Nouveau schéma de communication

Repartitionnement de la matrice

Graphe de tâches

Matrice symboliquepar blocs

Modélisation coûts calcul et comm

Nombre de processeurs

Distribution et ordonnancement

Données locales Ordonnancement tâches

Schéma de communication

Factorisation et résolution //

OOC

Calcul d’un schéma I/O pour l’OOC

Limitation mémoire

Schéma I/O disque

Distribution mixte 1D/2D

• Le solveur gère une distribution 1D ou 2D des blocs

• 1D sur les petits supernodes -> efficacité BLAS

• 2D sur les plus gros supernodes -> scalabilité

Critère de basculement entre les 2 distributions

1D block distribution

2D block distribution

1 2 3 4 5 6 7 8

1 2 3 4 5 5 6 7 8

51 2 3 4 5 6 7 8

4 41 2 2 3 86 7

2

3216 7 7

Repartionnement et processeurs candidats

Sopalin

Scotch Fax Blend Sopalin

graphe

sequentiel parallele

globallocal

symbolique numerique

noeud ddl

permutation symbolMatrixsolverMatrix distribuée

solverMatrixdistribuée etfactorisée

solutiondistribuée

element

L’algorithme de factorisation parallèle

• A est Symétrique Définie Positive factorisation sans pivotage

• Algorithme supernodal de factorisation parallèle creuse L.Lt / L.D.Lt avec agrégation locale complète et distribution mixte 1D/2D.

BStruct(Lk*)

BStruct(L*k)

Repartitionnement de la matrice

Graphe de tâches

Matrice symboliquepar blocs

Modélisation coûts calcul et comm

Nombre de processeurs

Distribution et ordonnancement

Données locales Ordonnancement tâches

Schéma de communication Limitation

mémoire

Réduction surcoût mémoireFactorisation

et résolution //

Nouveau schéma de communication

Algorithme de la factorisation //

FACTOR(k): factoriser le bloc diagonal k

Factoriser Akk en LkkLtkk;

BDIV(j,k): mis-à-jour Ljk

Résoudre LkkLjkt = At

jk;

BMOD(i,j,k): calculer la contribution de Lik pour le bloc Lij Calculer Cj=LikLjk

t;

Si map(i,j) == p Alors Aij = Aij – Cj;

Sinon AUBij=AUBij + Cj;

k

Ljk

Lik Lij

j

Algorithme de la factorisation //

COMP1D(k): factoriser le bloc-colonne k et calculer toutes les contributions destinées aux blocs-colonnes de BCol(k)

Factoriser Akk en LkkLtkk;

Résoudre LkkLt* = At

*k ;

Pour j BCol(k) Faire

Calculer C[j]=L[j]kLjkt;

Si map([j],j) == p Alors A[j]j = A[j]j – C[j];

Sinon AUB[j]j=AUB[j]j + C[j];

Algorithme de la factorisation //Pour n = 1 à NTp Faire

Selon (le type de Kp[n]) Faire

COMP1D: Recevoir et ajouter tous les AUB[k]k dans A[k]k;COMP1D(k);Phase_Envoi();

FACTOR: Recevoir et ajouter tous les AUBkk dans Akk;FACTOR(k);

envoyer Lkk à tous les processeurs dans map([k], k);

BDIV: Recevoir Lkk et recevoir et ajouter les AUBij pour Ajk;BDIV(j,k);

envoyer Fjt à tous les processeurs dans map([j], k);

BMOD: Recevoir Ljkt

BMOD(i,j,k); Phase_Envoi();

Structure de donnéestypedef struct SymbolCblk_ { INT fcolnum; // First column index INT lcolnum; // Last column index (inclusive) INT bloknum; // First block in column (diag.)} SymbolCblk;

typedef struct SymbolBlok_ { INT frownum; // First row index INT lrownum; // Last row index (inclusive) INT cblknum; // Facing column block INT levfval; // Level-of-fill value} SymbolBlok;

typedef struct SymbolMatrix_ { INT baseval; // Base value for numberings INT cblknbr; // Number of column blocks INT bloknbr; // Number of blocks SymbolCblk * restrict cblktab; // Array of column blocks SymbolBlok * restrict bloktab; // Array of blocks INT nodenbr; // Number of nodes in matrix} SymbolMatrix;

Structure de données

typedef struct SolverMatrix_ { SymbolMatrix symbmtx; SolverCblk * restrict cblktab; SolverBlok * restrict bloktab; INT coefnbr; INT ftgtnbr; FLOAT * restrict coeftab; FanInTarget * restrict ftgttab; int procnum; int procnbr; BlockTarget * restrict btagtab; INT btagnbr; BlockCoeff * restrict bcoftab; INT bcofnbr; Task * restrict tasktab; INT tasknbr; Ooc * restrict oocstr; UpDownVector updovct;} SolverMatrix;

typedef struct SolverCblk_ { INT stride; INT procdiag; INT cblkdiag;} SolverCblk;

typedef struct SolverBlok_ { INT coefind;} SolverBlok;

Structure de données#define COMP_1D 0#define DIAG 1#define E1 2#define E2 3#define DRUNK 4

typedef struct Task_ { INT taskid; INT prionum; INT cblknum; INT bloknum; INT ctrbcnt; BlockTarget * btagptr; INT indnum; INT tasknext;} Task;

Structure de donnéestypedef enum { FTGT_CTRBNBR = 0, FTGT_CTRBCNT, FTGT_PROCDST, FTGT_TASKDST, FTGT_BLOKDST, FTGT_PRIONUM, FTGT_FCOLNUM, FTGT_LCOLNUM, FTGT_FROWNUM, FTGT_LROWNUM, MAXINFO} FanInInfo;

typedef struct FanInTarget_ { INT infotab[MAXINFO]; FLOAT * coeftab;} FanInTarget;

Factorisation LU

Stockage de la partie U

Lk*

U*kLkk

Ukk

Lk*

Lkk

k*U

kkU

Transposition

Structure de données

typedef struct SolverMatrix_ { SymbolMatrix symbmtx; SolverCblk * restrict cblktab; SolverBlok * restrict bloktab; INT coefnbr; INT ftgtnbr; FLOAT * restrict coeftab; FLOAT * restrict ucoeftab; FanInTarget * restrict ftgttab; int procnum; int procnbr; BlockTarget * restrict btagtab; INT btagnbr; BlockCoeff * restrict bcoftab; INT bcofnbr; Task * restrict tasktab; INT tasknbr; Ooc * restrict oocstr; UpDownVector updovct;} SolverMatrix;

typedef struct SolverCblk_ { INT stride; INT procdiag; INT cblkdiag;} SolverCblk;

typedef struct SolverBlok_ { INT coefind;} SolverBlok;

Algorithme de la factorisation // FACTOR(k): factoriser le bloc diagonal k

Factoriser Akk en LkkUkk;

BDIV(j,k): mis-à-jour Ljk et Uik

Résoudre LkkUki = Aki;

Résoudre Ukk Lik = Aik;BMOD(i,j,k): calculer la contribution

de Lik pour le bloc Lij Calculer Cj=LikUkj;

Calculer Dj=LjkUki;Si map(i,j) == p Alors Aij = Aij – Cj;

Aji = Aji – Dj;Sinon AUBij=AUBij + Cj;

AUBji=AUBji + Dj;

k

Ljk

Lik Lij

j

Ukj

Algorithme de la factorisation //

COMP1D(k): factoriser le bloc-colonne k et calculer toutes les contributions destinées aux blocs-colonnes de BCol(k)

Factoriser Akk en LkkUkk;

Résoudre LkkUk* = Ak* ;

Résoudre L*kUkk = A*k ;

Pour j BCol(k) Faire

Calculer C[j]=L[j]kUkj;

Calculer D[j]=LjkUk[j];

Si map([j],j) == p Alors A[j]j = A[j]j – C[j]; Aj[j]=Aj[j]-D[j];

Sinon AUB[j]j=AUB[j]j + C[j]; AUBj[j]=AUBj[j] + D[j];

Pour n = 1 à NTp Faire

Selon (le type de Kp[n]) Faire

COMP1D: Recevoir et ajouter tous les AUB[k]k dans A[k]k; Recevoir et ajouter tous les AUBk[k] dans Ak[k];

COMP1D(k);Phase_Envoi();

FACTOR: Recevoir et ajouter tous les AUBkk dans Akk;FACTOR(k);

envoyer Lkk et Ukk à tous les processeurs dans map([k], k);

BDIV: Recevoir Lkk et Ukk et recevoir et ajouter les AUBij pour Ajk et Aki;

BDIV(j,k);

envoyer Fjt à tous les processeurs dans map([j], k);

BMOD: Recevoir Uki et Lik

BMOD(i,j,k); Phase_Envoi();

Pivotage StatiqueFactorisation A=LU avec contrôle de l’amplitude de la diagonale

Si (|aii|) < 1Aε

Alors aii = 1Aε

Resoudre LUx = b

Iterer: xAbr

rdxLU :Resoudre

i

ii )bxA(

rmaxberr

inerSinon term

reitereret berr lastberret dx x xalors

lastberr)2

1berret ε(berr Si

Perspectives

• Interface externe

• Portabilité