Sites Inria

English version

Logiciel

Françoise Breton – Technoscope - 21/12/2012

Organiser le calcul sur les machines parallèles

Partitionnement d'un maillage de pièce mécanique en 16 parties

Le logiciel Scotch, développé par François Pellegrini chez Inria Bordeaux – Sud-Ouest, fête en décembre ses 20 ans d’existence. Ce logiciel est utilisé pour organiser les calculs de manière efficace et robuste sur les ordinateurs parallèles. Il rencontre aujourd’hui un succès croissant. Il faut dire qu’il est le seul au monde à fonctionner sur des architectures parallèles hiérarchiques comprenant des dizaines de milliers de processeurs. Entretien avec François Pellegrini, professeur à l'université Bordeaux 1, membre de l’équipe Bacchus d'Inria Bordeaux – Sud-Ouest et membre du LaBRI.

À quoi sert le logiciel Scotch ?

Dès que l’on a à faire à des calculs de taille très importante, il n’est pas possible de les réaliser sur un seul ordinateur. La mémoire n’est pas suffisante et les calculs prendraient un temps considérable. C’est le cas, par exemple, lorsque l’on veut calculer la structure d’une voiture, l'aérodynamisme d’un avion ou bien faire de la prévision en météorologie. On utilise alors plusieurs ordinateurs ou plusieurs processeurs simultanément, c’est-à-dire en parallèle. La question qui se pose alors est de savoir comment répartir les tâches à réaliser entre ces différents processeurs de façon à être le plus efficace possible. Comme dans une organisation de bureau, il s’agit d'effectuer une répartition équilibrée, de sorte que chacun termine sa tâche à peu près au même moment. Il s’agit aussi de faire en sorte que les échanges d'informations nécessaires à l’accomplissement d’une tâche soient les plus rapides possible, c’est-à-dire qu’il ne soit pas nécessaire de se déplacer à l’autre bout du service toutes les 5 mn pour obtenir l’information nécessaire pour avancer. Le logiciel Scotch permet de faire cette répartition de façon à utiliser au mieux les capacités d'un ordinateur parallèle constitué de nombreux processeurs. Scotch est un "partitionneur de graphes" car l'ensemble des tâches de calcul à placer peut être vu comme un graphe, dont les sommets représentent les différents calculs et les arêtes qui les relient, les dépendances entre ces calculs. Trouver une bonne répartition des tâches revient à découper ce graphe en parties contenant approximativement le même nombre de sommets, et de façon à ce que le nombre d'arêtes entre les différentes parties soit le plus petit possible.

Quelles sont les grandes évolutions du logiciel depuis 20 ans ?

Si l'idée de faire travailler plusieurs processeurs en parallèle est ancienne, c'est au milieu des années quatre-vingts que l'on a commencé à construire des architectures parallèles utilisables de façon industrielle. Même si la taille des calculs à cette époque était très petite par rapport à ce que l’on est amené à traiter aujourd’hui, elle nécessitait néanmoins un traitement en parallèle du fait des faibles performances des processeurs de l'époque. Néanmoins, les graphes représentant les problèmes étaient de taille suffisamment réduite pour être traités sur un seul ordinateur. Le calcul du partitionnement pouvait donc s’effectuer au moyen d'algorithmes séquentiels sur un seul ordinateur. L’objectif était de trouver de bons algorithmes séquentiels pour partitionner ces graphes.
Dix ans plus tard, les problèmes scientifiques ont atteint une taille telle que le graphe lui-même ne tient plus dans la mémoire d’un seul ordinateur. Sa partition doit elle-même être calculée en parallèle. Le défi était donc de développer de bons algorithmes pour partitionner en parallèle.

Y a-t-il d’autres défis à relever aujourd’hui pour Scotch ?

Comme la taille des problèmes à résoudre continue de croître, le nombre de processeurs des ordinateurs augmente en conséquence. Le nombre de processeurs nécessaire au traitement des plus gros problèmes considérés à l'heure actuelle dépasse aujourd’hui la dizaine de milliers, et l'on construit actuellement des systèmes contenant des millions de processeurs ! Il n’est plus possible dans ces conditions de fonctionner de façon uniforme, c’est-à-dire en faisant communiquer de manière identique chaque processeur avec tous les autres. On adopte une organisation - une architecture - hiérarchique. Pour reprendre mon analogie avec une administration par exemple, les agents effectuant les traitements vont être répartis en départements, eux-mêmes découpés en services, puis en bureaux. La communication entre bureaux de départements distincts passe obligatoirement par la voie hiérarchique. L’objectif est donc toujours de répartir le travail de façon équitable, mais en tenant compte de l’architecture du système pour que la plupart des échanges de données se fassent localement. On parle alors plutôt dans ce cadre de "placement" de tâches plutôt que de "partitionnement".

Êtes-vous impliqué dans cette recherche ?

C’est une recherche que l’on entame actuellement. Nous avons une longueur d’avance sur nos compétiteurs car les premiers algorithmes que nous avons développés dans les années 1990 étaient conçus pour des machines parallèles hiérarchiques, appelées aussi "non uniformes" ou "hétérogènes". À cette époque en effet, on ne savait pas faire de machines parallèles uniformes au-delà de 32 processeurs. Puis très vite les progrès technologiques ont permis de faire des machines à architecture uniforme jusqu’à 512 puis 1024 processeurs. Les fonctionnalités pour l’hétérogénéité de Scotch n’ont que très peu servi, mais elles existent ! Ainsi, Scotch sait placer des tâches sur systèmes hétérogènes, même si Scotch lui-même n’a pas été conçu pour fonctionner de façon optimale sur ces architectures. Le placement coûte plus en temps calcul que ce qu’il devrait mais, pour des architectures d'environ 80 000 processeurs, le placement effectué peut permettre de gagner 10 à 15% du temps calcul par rapport à un partitionneur de graphes pour architecture uniforme !

Est-ce l’originalité de Scotch par rapport à des compétiteurs comme MeTiS, très utilisé aux États-Unis ?

Scotch est en effet le seul partitionneur capable de faire du placement de tâches sur des architectures parallèles hétérogènes. Pour le moment, ce placement s’effectue en séquentiel mais nous avons déjà un prototype capable de faire du placement parallèle pour ce type d’architecture. Par ailleurs, nous avons été les premiers à offrir une version sur 64 bits permettant de traiter des maillages de très grandes tailles. Scotch sera vraisemblablement le premier logiciel à permettre de placer des graphes de plusieurs milliards de sommets sur des centaines de milliers de processeurs en gérant l’hétérogénéité de l’architecture. Katie Lewis chercheuse au Lawrence Livermore National Laboratory , par exemple, qui est une utilisatrice travaillant sur ce type de très gros problèmes, espère ainsi gagner 30% de temps de calcul…

Scotch est un logiciel libre mais cela n’a pas toujours été le cas. Pour quelles raisons ?

Scotch est distribué sous licence libre CeCill-C depuis la version 4.0, datée de 2006. C’était devenu indispensable pour assurer la bonne diffusion de ce logiciel qui, jusqu’alors, n’était utilisé que par un petit nombre de partenaires, dont le CEA, alors qu’il peut rendre service à de très nombreuses personnes. Depuis, cette version a été téléchargée plus de 2500 fois et a été intégrée dans d’autres logiciels comme le module Zoltan du logiciel Trilinos développé par les laboratoires du Département de l’énergie américain, ou le solveur MUMPS développé conjointement entre des équipes de Lyon, Toulouse et Bordeaux.

Haut de page

Suivez Inria tout au long de son 50e anniversaire et au-delà !