English version
Il y a exactement 20 ans, jour pour jour, la première ligne de SCOTCH
était écrite...
20 ans après, jour pour jour, cette nouvelle version est publiée.
Comme les précédentes, elle est disponible en tant que logiciel libre
sous la licence CeCILL-C.
La version 6.0 offre beaucoup de nouvelles fonctionnalités:
repartitionnement séquentiel de graphes
partitionnement séquentiel de graphes avec sommets fixes
repartitionnement séquentiel de graphes avec sommets fixes
nouveaux algorithmes rapides pour le k-partitionnement et le k-placement
algorithmes multi-thread en mémoire partagée au sein de la partie (anciennement) séquentielle de la bibliothèque
publication dans l'interface de nombreuses routines de manipulation de graphes distribués
générateur pseudo-aléatoire embarqué pour une reproductibilité accrue
et plus encore...
La révision 5.1.10 de SCOTCH franchit la « barrière des 32 bits » en parallèle
La révision 5.1.10 est la première à pouvoir manipuler en parallèle
des graphes à plus de deux milliards de sommets (limite de
représentation des entiers signés à 32 bits). PT-SCOTCH a ainsi
pu bipartitionner, en 76 secondes, un graphe 3D de plus de 2,4
milliards de sommets et 7,3 milliards d'arêtes, distribué sur 2048
processeurs de la machine platine du
CCRT.
La bibliothèque séquentielle SCOTCH est elle aussi totalement capable de manipuler des valeurs codées sur 64 bits, et ce depuis la révision 5.1.8 pour l'intégralité de ses fonctions.
La version 5.1 de SCOTCH est disponible sous licence libre CeCILL-C
La version 5.1 est la première à inclure dans PT-SCOTCH les fonctionnalités de partitionnement parallèle de graphes.
La version 5.0 de SCOTCH est disponible sous licence libre CeCILL-C
La version 5.0 est la première à inclure PT-SCOTCH, la version parallèle de SCOTCH. Ses nouvelles fonctionnalités comprennent :
une structure de graphe distribuée, qui permet aux utilisateurs de manipuler dynamiquement de très grands graphes, au moyen de tableaux d'arêtes compacts ou bien disjoints. Les tableaux d'arêtes disjoints sont utiles pour gérer les graphes adaptatifs, car ils permettent de modifier les structures de graphes sans avoir besoin de recopier l'ensemble des tableaux de sommets et d'arêtes ;
un ensemble de routines permettant de distribuer des graphes SCOTCH centralisés, ou de centraliser des graphes distribués ;
des routines parallèles de renumérotation de graphes distribués ;
de nouvelles méthodes séquentielles de partitionnement de graphes, comprenant une méthode de diffusion permettant d'obtenir des interfaces plus lisses;
une bibliothèque de compatibilité avec les principales routines de la bibliothèque MeTiS, pour permettre aux utilisateurs de MeTiS de tester Scotch sans avoir besoin de modifier leur code source.
La version 4.0 de SCOTCH est disponible sous licence libre LGPL
La version 4.0 est la première distribution de SCOTCH en tant que logiciel libre. C'est une réécriture majeure de la version 3.4, qui inclut beaucoup de nouvelles fonctionnalités :
une structure de graphe améliorée, qui permet aux utilisateurs de disposer de tableaux d'arêtes compacts ou bien disjoints, sans surcoût ;
une structure de maillage native, qui permet de manipuler des maillages qui ne tiendraient pas en mémoire s'ils étaient représentés sous forme de graphes nodaux ;
une gestion efficace de la mémoire, pour traiter des graphes et maillages plus gros sans tomber à court de mémoire ;
un interpréteur de stratégies amélioré, pouvant évaluer dynamiquement des expressions arithmétiques portant sur les propriétés des graphes.
SCOTCH est un projet développé au sein de l'équipe Satanas du Laboratoire Bordelais de Recherche en Informatique (LaBRI). Il fait partie du projet ScAlApplix de l'INRIA Bordeaux - Sud-Ouest.
Son but est d'appliquer la théorie des graphes, avec une méthodologie de type diviser pour résoudre, à des problèmes d'informatique scientifique tels que le partitionnement de graphes et de maillages, le placement statique, et la renumérotation de matrices creuses, dans le cadre de domaines d'applications allant de la mécanique des structures aux systèmes d'exploitation ou à la biochimie.
La distribution SCOTCH est un ensemble de programmes séquentiels et parallèles et de bibliothèques qui implémentent les algorithmes de placement statique et de renumérotation de matrices creuses conçus au sein du projet SCOTCH.
SCOTCH possède de nombreuses caractéristiques intéressantes :
Ses fonctionnalités peuvent être mises en oeuvre par le biais d'un ensemble de programmes indépendants ou au moyen de la bibliothèque libSCOTCH, qui offre des interfaces pour les langages C et Fortran.
Il 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.
Il 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.
Il calcule des renumérotations de matrices creuses amalgamées par blocs, pour une résolution efficace au moyen de routines BLAS.
Son temps d'exécution est linéaire vis-à-vis du nombre d'arêtes du graphe source, et logarithmique vis-à-vis du nombre de sommets du graphe cible dans le cas du placement statique.
Il 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.
Il offre un support étendu des graphes et maillages adaptatifs par la gestion de tableaux d'arêtes disjoints.
Il est paramétrable dynamiquement, grâce à l'interprétation des chaînes de stratégie lors de l'exécution du programme.
Il utilise efficacement la mémoire disponible, pour traiter des graphes et maillages plus gros sans tomber à court de mémoire.
Il 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.
Il 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.
Il offre de nombreux outils pour construire, tester, et afficher des graphes.
Il 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.
La version 5.1 de SCOTCH est distribuée en tant que logiciel libre, selon les termes de la licence CeCILL-C. Veuillez vous reporter à la section des Ressources ci-dessous pour voir comment télécharger les dernières mises à jour des sources et de la documentation de SCOTCH.
SCOTCH peut aussi être distribué sous d'autres types de licences et conditions aux parties désireuses de l'enfouir au sein de logiciels fermés propriétaires. Veuillez nous contacter si vous envisagez cette option.
Pour faciliter le développement, la diffusion et la circulation d'informations relatives au projet SCOTCH, la plupart de ses ressources sont maintenant hébergées sur la plate-forme InriaGforge mise en oeuvre par l'INRIA. Cette forge offre de nombreux services aux personnes intéressées par le projet.
Les documents de travail relatifs à SCOTCH sont maintenant disponibles sur l'espace de documentation d'InriaGforge. Vous trouverez ci-dessous les autres documents, ainsi que les références bibliographiques de documents qui ne peuvent être mis en libre accès du fait de restrictions de droits d'éditeur / copyright.
François Pellegrini