Scotch

Fiche dév Ens Sup - Recherche
  • Création ou MAJ importante : 23/12/09
  • Correction mineure : 31/03/10
Mots-clés

Scotch : partitionneur de graphes et renuméroteur de matrices creuses, séquentiel et parallèle

Ce logiciel a été développé (ou est en cours de développement) dans la communauté de l'Enseignement Supérieur et de la Recherche. Son état peut être variable (cf champs ci-dessous) donc sans garantie de bon fonctionnement.
  • Site web
  • Système : UNIX-like, Windows, MacOS X
  • Version actuelle : 5.1 - 08/09/2008
  • Licence(s) : CeCILL-C
  • Etat : validé (au sens PLUME), diffusé, stable
  • Support : maintenu, développement en cours
  • Concepteur(s) : François PELLEGRINI
  • Contact concepteur(s) : pelegrin@labri.fr
  • Laboratoire(s), service(s)... : INRIA Bordeaux, LABRI

 

Une fiche logiciel décrit plus en détail ce développement, consultez la pour plus d’informations : Scotch
Fonctionnalités générales du logiciel

La distribution SCOTCH est un ensemble de programmes séquentiels et parallèles et de bibliothèques pour le partitionnement de graphes, le placement statique et la renumérotation de matrices creuses. Ces fonctionnalités sont accessibles au moyen de programmes en ligne de commande, ou bien par l'appel de fonctions de la bibliothèque libSCOTCH, disposant de prototypes en C et en FORTRAN.

SCOTCH :

  • fournit des algorithmes pour partitionner des structures de graphes, ainsi que des structures de maillages définies comme des graphes bipartis noeuds/éléments et qui peuvent aussi représenter des hypergraphes ;
  • peut placer tout type de graphe source sur tout type de graphe cible. Les graphes source et cible peuvent être de topologies quelconques, et leurs sommets et arêtes peuvent être valués. Qui plus est, ces graphes peuvent même être déconnectés. Cette fonctionnalité permet le placement de programmes sur des sous-parties disjointes d'une architecture parallèle constituée de processeurs et de liens de communication hétérogènes ;
  • calcule des renumérotations de matrices creuses amalgamées par blocs, pour une résolution efficace au moyen de routines BLAS ;
  • peut manipuler indifféremment des structures de graphes et de maillages créées au sein de programmes C ou FORTRAN, avec des indices de tableaux commençant à 0 ou à 1 ;
  • offre un support étendu des graphes et maillages adaptatifs par la gestion de tableaux d'arêtes disjoints ;
  • est paramétrable dynamiquement, grâce à l'interprétation des chaînes de stratégie lors de l'exécution du programme ;
  • est très fortement modulaire et documenté. Comme il est maintenant disponible sous la licence libre CeCILL-C, il peut être utilisé comme banc de test pour le développement rapide et le test de nouvelles méthodes de partitionnement ou de renumérotation ;
  • peut être facilement interfacé avec d'autre programmes. Les programmes du projet SCOTCH ont été conçus pour fonctionner en mode ligne de commande sans sollicitations de l'utilisateur, afin qu'ils puissent être appelés facilement à partir d'autres programmes au moyen d'appels system() ou popen(), ou bien être combinés sur une seule ligne de commande au moyen de pipes. De plus, les fonctionnalités d'étiquetage des sommets permettent une renumérotation facile de ceux-ci ;
  • offre de nombreux outils pour construire, tester, et afficher des graphes ;
  • est écrit en C ANSI et utilise l'interface POSIX, ce qui le rend très portable. PT-SCOTCH utilise l'interface MPI, et optionnellement les threads POSIX.
Contexte d’utilisation du logiciel

SCOTCH est utilisé au sein d'applications de calcul scientifique, en particulier les solveurs linéaires et non-linéaires.

Pour les méthodes itératives de résolution, ses capacités de partitionneur et de placeur servent à allouer les noeuds des maillages sur les processeurs.

Pour les méthodes directes de résolution de grands systèmes linéaires creux, ses capacités de renuméroteur servent à minimiser le remplissage de la matrice factorisée.

Publications liées au logiciel
Distillating knowledge about SCOTCH.
Combinatorial Scientific Computing, numéro 09061, Dagstuhl Seminar Proceedings, juillet 2009.
F. Pellegrini.



PT-SCOTCH : a tool for efficient parallel graph ordering.
Parallel Computing, 34(6-8), pp 318-331, 2008.
C. Chevalier et F. Pellegrini.



SCOTCH 5.1 User's guide.

Rapport technique, LaBRI, septembre 2008.
F. Pellegrini.



PT-SCOTCH 5.1 User's guide.

Rapport technique, LaBRI, septembre 2008.
F. Pellegrini.



Conception et mise en oeuvre d'outils efficaces pour le partitionnement et la distribution parallèles de problèmes numériques de très grande taille.
Thèse de doctorat, LaBRI, Université Bordeaux 1, septembre 2007.
C. Chevalier.



A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries.
EuroPar, août 2007, Rennes.
© Springer-Verlag, publié dans les LNCS series,
LNCS 4641, pp 191-200.
F. Pellegrini.