&
![[ENGLISH]](../images/flag_gb.gif)
English version
Cette version majeure (nom de code « Sankara »), fruit de six ans de développement, apporte de nombreuses améliorations majeures. Notamment :
La gestion des threads est maintenant totalement dynamique : Scotch s'adapte automatiquement au nombre de cœurs disponibles. Un ensemble de threads existant peut être importé d'un logiciel appelant, pour ne pas créer de threads redondantes et améliorer la localité des calculs ;
De nombreux algorithmes ont été réécrits pour bénéficier du parallélisme à mémoire partagée, y compris certains algorithmes de PT-Scotch, qui bénéficient maintenant d'un parallélisme hybride « MPI+threads » ;
Les options d'exécution, telles que le fait de choisir entre des algorithmes déterministes permettant la reproductibilité des résultats ou bien des algorithmes non-déterministes plus rapides, peuvent également être définies de manière dynamique et non plus à la compilation ;
Une nouvelle classe d'objets est disponible : les contextes d'exécution. Ces contextes permettent aux utilisateurs d'encapsuler un ensemble de threads, des options d'exécution et un générateur pseudo-aléatoire, de façon à pouvoir exécuter en parallèle (et de façon totalement reproductible) des calculs (placement, partitionnement, renumérotation, etc.) sur le même graphe ou bien sur des graphes distincts ;
Pour faciliter la migration depuis le logiciel MeTiS, deux versions distinctes de la bibliothèque de compatibilité sont fournies simultanément : v3 et v5 ;
L'outil de compilation CMake est maintenant supporté ;
Et bien plus encore...
Grande nouvelle : à l'occasion des 30 ans de Scotch, Un consortium est en cours de montage. Un projet de texte décrivant le consortium est disponible. Un sondage pour connaître la communauté des utilisateurs de Scotch a également été mis en ligne.
SCOTCH est disponible sur le dépôt GitLab d'Inria.
Suite à l'arrêt du service Gforge d'Inria, le dépôt GitLab d'Inria devient la seule source officielle du logiciel SCOTCH. Veuillez mettre à jour vos références de téléchargement.
Remerciements à tous les utilisateurs qui accordent leur confiance à notre logiciel, qui a été le sixième logiciel le plus téléchargé à partir de la Gforge d'Inria.
La version 6.1 de SCOTCH est sortie !
Comme les précédentes, elle est disponible en tant que logiciel libre sous la licence CeCILL-C.
Exactement 20 ans après, jour pour jour, que la première ligne de SCOTCH a été écrite, la version 6.0 de SCOTCH, alias « le SCOTCH de 20 ans d'âge », est publiée. Cette version 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 du département de recherche Satanas du Laboratoire Bordelais de Recherche en Informatique (LaBRI). Il fait partie des projets de l'équipe TADaaM d'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.
La bibliothèque SCOTCH tire parti dynamiquement des threads POSIX pour accélérer ses calculs. La bibliothèque PT-SCOTCH, utilisée pour gérer de très grands graphes distribués sur les nœuds d'un ordinateur parallèle, utilise l'interface MPI et les threads POSIX.
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.
Les versions actuelles de SCOTCH sont distribuées 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 GitLab d'Inria. Cette forge offre de nombreux services aux personnes intéressées par le projet.
L'ancienne instance Gforge (voir ci-dessous) sera maintenue concurremment, jusqu'à l'arrêt définitif de cette plateforme.
Auparavant, la plupart des ressources du projet SCOTCH étaient hébergées sur la plate-forme InriaGforge.
François Pellegrini