Structures des projets . Structures des projets . et .et .

FrançoisFrançois PELLEGRINIPELLEGRINI

INRIA Futurs & LaBRI, UMR CNRS INRIA Futurs & LaBRI, UMR CNRS 58005800

2© 2002 ScAlApplix

Le projet ScotchLe projet Scotch

Débuté en 1992 (thèse de F. Pellegrini)Débuté en 1992 (thèse de F. Pellegrini) Appliquer des méthodes de type « diviser pour Appliquer des méthodes de type « diviser pour

résoudre » à des problèmes d’algorithmique de résoudre » à des problèmes d’algorithmique de graphes utilisés pour la résolution parallèle de graphes utilisés pour la résolution parallèle de grands systèmes linéaires creux :grands systèmes linéaires creux : Partitionnement de graphesPartitionnement de graphes Placement statiquePlacement statique Renumérotation de matrices creusesRenumérotation de matrices creuses

Algorithmes basés uniquement sur la topologieAlgorithmes basés uniquement sur la topologie Étude de versions parallèles de ces algorithmesÉtude de versions parallèles de ces algorithmes

3© 2002 ScAlApplix

Le projet PaStiXLe projet PaStiX

Débuté en 1997 (thèses de P. Ramet, D. Débuté en 1997 (thèses de P. Ramet, D. Goudin, P. Hénon)Goudin, P. Hénon)

Réalisation d’une chaîne complète de Réalisation d’une chaîne complète de résolution parallèle par méthode directe par résolution parallèle par méthode directe par blocs de grands systèmes linéaires creux blocs de grands systèmes linéaires creux symétriques définis positifssymétriques définis positifs Renumérotation (Scotch)Renumérotation (Scotch) Factorisation symboliqueFactorisation symbolique Distribution des blocs (1D et/ou 2D)Distribution des blocs (1D et/ou 2D) Factorisation numériqueFactorisation numérique Descente/remontéeDescente/remontée

Structure de grapheStructure de graphe

5© 2002 ScAlApplix

Cahier des charges (1)Cahier des charges (1)

Possibilité de valuer les sommets et les arêtesPossibilité de valuer les sommets et les arêtes Mais pas obligation !Mais pas obligation ! Structures séparées pour les valuationsStructures séparées pour les valuations

Nécessité de connaître rapidement tous les Nécessité de connaître rapidement tous les voisins d’un sommet donnévoisins d’un sommet donné Liste de voisins pour chaque sommetListe de voisins pour chaque sommet Structure symétrique (graphes symétriques)Structure symétrique (graphes symétriques)

Facilement modifiableFacilement modifiable Possibilité d’ajouter, de supprimer des sommets, des Possibilité d’ajouter, de supprimer des sommets, des

arêtes, …arêtes, …

i j i adj(j) j adj(i)

6© 2002 ScAlApplix

Stockage des adjacences (1)Stockage des adjacences (1)

Nombre de sommets Nombre de sommets vertnbrvertnbr et nombre d’arcs et nombre d’arcs edgenbredgenbr

Tableaux donnant l’indice de début Tableaux donnant l’indice de début verttabverttab et et l’indice de fin l’indice de fin vendtabvendtab dans le tableau des dans le tableau des extrémités d’arcs extrémités d’arcs edgetabedgetab de taille maximale de taille maximale donnée donnée edgemaxedgemax Plage des numéros de sommets densePlage des numéros de sommets dense Tableau Tableau edgetabedgetab non nécessairement dense non nécessairement dense Sommets non nécessairement ordonnés dans Sommets non nécessairement ordonnés dans edgetabedgetab

Listes d’adjacence non triées dans Listes d’adjacence non triées dans edgetabedgetab ((vendtab[i]vendtab[i] –– verttab[i]verttab[i]) est le degré du sommet ) est le degré du sommet ii

7© 2002 ScAlApplix

Stockage des adjacences (2)Stockage des adjacences (2)

On parcourt la structure de la façon suivante :On parcourt la structure de la façon suivante :

2

3

1

4

14

4

edgemax

edgenbr

vertnbr

10

verttab

edgetab 2 3 . . 1 2 4 3 2 3 4 1 . .

1 10 5 8

vendtab 3 13 8 13

for (vertnum = 0; vertnum < vertnbr; vertnum ++) { for (edgenum = verttab[vertnum]; edgenum < vendtab[vertnum]; edgenum ++) { vertend = edgetab[edgenum]; … }}

8© 2002 ScAlApplix

Stockage compact des sommetsStockage compact des sommets

Si toutes les adjacences sont stockées de Si toutes les adjacences sont stockées de façon dense et ordonnée dans façon dense et ordonnée dans edgetabedgetab, on , on n’a plus besoin d’allouer qu’un seul tableau n’a plus besoin d’allouer qu’un seul tableau d’index, de taille (d’index, de taille (vertnbrvertnbr ++ 11)) vendtabvendtab pointe sur ( pointe sur (verttabverttab ++ 11))

2

3

1

4

10

4

edgemax

edgenbr

vertnbr

10

verttab 111 3 6 9

vendtab

edgetab 2 3 3 4 1 1 2 4 3 2

9© 2002 ScAlApplix

Valeur de base des index (1)Valeur de base des index (1)

Selon que l’on adresse les tableaux à partir Selon que l’on adresse les tableaux à partir de C ou de FORTRAN, les valeurs d’index de C ou de FORTRAN, les valeurs d’index diffèrentdiffèrent Commencent à zéro en CCommencent à zéro en C Commencent à un en FORTRANCommencent à un en FORTRAN

Problème d’indexation double, du type :Problème d’indexation double, du type : edgetaedgetabb[verttab[vertnum]][verttab[vertnum]]

Parcours en C d’un graphe créé en FORTRAN :Parcours en C d’un graphe créé en FORTRAN :for (vertnum = 0; vertnum < vertnbr; vertnum ++) { for (edgenum = verttab[vertnum]; // Valide edgenum < vendtab[vertnum]; edgenum ++) { vertend = edgetab[edgenum]; // Invalide ! … }}

10© 2002 ScAlApplix

Valeur de base des index (2)Valeur de base des index (2)

La structure de graphe conserve la valeur de La structure de graphe conserve la valeur de base des index de ses tableaux, base des index de ses tableaux, basevalbaseval

Les accès basés se font à travers des Les accès basés se font à travers des références basées aux tableaux références basées aux tableaux verttaxverttax, , vendtaxvendtax, , edgetaxedgetax verttaxverttax vau vautt ( (verttabverttab -- basevalbaseval)) vendtaxvendtax vau vautt ( (vendtabvendtab -- basevalbaseval)) edgetaxedgetax vau vautt ( (edgetabedgetab -- basevalbaseval))

La valeur La valeur vertnndvertnnd vaut ( vaut (vertnbrvertnbr ++ basevalbaseval))

11© 2002 ScAlApplix

Valeur de base des index (3)Valeur de base des index (3)

for (vertnum = 0; vertnum < vertnbr; vertnum ++) { // Non basé for (edgenum = verttab[vertnum]; edgenum < vendtab[vertnum]; edgenum ++) { // Non basé vertend = edgetax[edgenum]; // Basé …

for (vertnum = baseval; vertnum < vertnnd; vertnum ++) { // Basé for (edgenum = verttax[vertnum]; edgenum < vendtax[vertnum]; edgenum ++) { // Basé vertend = edgetax[edgenum]; // Basé …

2

3

1

4

10

4

edgemax

edgenbr

vertnbr

10

verttab 111 3 6 9

vendtab

edgetab 2 3 3 4 1 1 2 4 3 2

1baseval

5vertnnd

verttaxvendtax

12© 2002 ScAlApplix

Structure de donnéesStructure de données

typedef struct Graph_ { INT baseval; // Base value for numberings INT vertnbr; // Number of vertices INT edgenbr; // Number of edges (arcs) INT edgemax; // Size of edgetab INT * restrict verttab; // Array of neighbor indexes INT * restrict verttax; // Based access to verttab INT * restrict vendtab; // Array of neighbor indexes INT * restrict vendtax; // Based access to vendtab INT * restrict velotab; // Array of vertex loads INT * restrict velotax; // Based access to velotab INT veloval; // Vertex load if (velotab == NULL) INT * restrict edgetab; // Array of adjacency lists INT * restrict edgetax; // Based access to edgetab INT * restrict edlotab; // Array of edge loads INT * restrict edlotax; // Based access to edlotab INT degrmax; // Maximum degree of graph vertices} Graph;

Permutation par blocsPermutation par blocs

14© 2002 ScAlApplix

Cahier des chargesCahier des charges

Spécifier de façon compacte une permutation Spécifier de façon compacte une permutation par blocs des sommets d’un graphe, par blocs des sommets d’un graphe, représentant la renumérotation de ses sommetsreprésentant la renumérotation de ses sommets Numérotation dépendant de l’index de base du Numérotation dépendant de l’index de base du

graphegraphe La permutation inverse est plus intéressante La permutation inverse est plus intéressante

que la permutation directeque la permutation directe Zone continue d’indices pour tout sous-graphe à Zone continue d’indices pour tout sous-graphe à

renuméroterrenuméroter Favorise donc la localité des données et le cacheFavorise donc la localité des données et le cache Permet d’exprimer les blocs de la renumérotation Permet d’exprimer les blocs de la renumérotation

comme des plages continues d’indicescomme des plages continues d’indices

15© 2002 ScAlApplix

Permutation par blocsPermutation par blocs

La permutation inverse est contenue dans un La permutation inverse est contenue dans un tableau basé, tableau basé, peritaxperitax On peut en déduire la permutation directe, On peut en déduire la permutation directe, permtaxpermtax

Les Les rangnbrrangnbr plages de numérotation sont plages de numérotation sont stockées au moyen du tableau compact stockées au moyen du tableau compact rangtaxrangtax, de taille (, de taille (rangnbrrangnbr ++ 11), contenant ), contenant les indices de début de chaque plage, et les indices de début de chaque plage, et terminé par terminé par vertnndvertnnd ((rangtax[i+1]rangtax[i+1] –– rangtax[i]rangtax[i]) est la taille de la ) est la taille de la

plage plage ii

16© 2002 ScAlApplix

Structure de donnéesStructure de données

typedef struct Order_ { INT baseval; // Base value for numberings INT rangnbr; // Number of permuted vertex ranges INT * restrict rangtax; // Array of permuted vertex ranges INT * restrict peritax; // Inverse permutation INT * restrict permtax; // Direct permutation} Order;

Matrice symétrique factorisée Matrice symétrique factorisée symboliquement par blocssymboliquement par blocs

18© 2002 ScAlApplix

Cahier des chargesCahier des charges

Représenter de façon compacte une matrice Représenter de façon compacte une matrice symétrique factorisée symboliquement par symétrique factorisée symboliquement par blocsblocs Numérotation dépendant de l’index de base du Numérotation dépendant de l’index de base du

graphegraphe Structure servant de support à la structure Structure servant de support à la structure

distribuée de matrice factorisée numériquement distribuée de matrice factorisée numériquement par blocspar blocs

19© 2002 ScAlApplix

Blocs colonnes et blocs (1)Blocs colonnes et blocs (1)

Les plages de la renumérotation définissent Les plages de la renumérotation définissent des blocs colonnesdes blocs colonnes cblknbrcblknbr est le nombre de blocs colonnes est le nombre de blocs colonnes Stockage compact dans un tableau unique Stockage compact dans un tableau unique

((cblktabcblktab) de taille () de taille (cblknbrcblknbr ++ 11)) Les bornes de la colonne sont (Les bornes de la colonne sont (fcolnumfcolnum, , lcolnumlcolnum)) ((cblktax[i+1].bloknumcblktax[i+1].bloknum –– cblktax[i].bloknumcblktax[i].bloknum) )

est le nombre de blocs contenus dans le bloc est le nombre de blocs contenus dans le bloc colonne colonne ii

20© 2002 ScAlApplix

Blocs colonnes et blocs (2)Blocs colonnes et blocs (2)

Dans chaque bloc colonne, les blocs sont Dans chaque bloc colonne, les blocs sont définis par leurs indices de ligne (définis par leurs indices de ligne (frownumfrownum, , lrownumlrownum) et le numéro global du bloc colonne ) et le numéro global du bloc colonne en regard (en regard (cblknumcblknum) ) bloknbrbloknbr est le nombre de blocs colonnes est le nombre de blocs colonnes Stockage compact dans un tableau unique Stockage compact dans un tableau unique

((bloktabbloktab) de taille ) de taille bloknbrbloknbr

21© 2002 ScAlApplix

Structure de donnéesStructure de données

typedef 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;