Accueil du site > Vie de la recherche > Prix et distinctions




Recherchez sur ce site


Mettre les données doubles sur les supercalculateurs

Dans le calcul parallèle, les opérations effectuées souffrent à la fois de défaillances externes, avec des pannes récurrentes de composants, et de problèmes internes, avec des cas d’inversion de bits qui faussent le résultat. Camille Coti du Laboratoire d’Informatique de Paris-Nord (LIPN - CNRS/Université Paris 13) vient d’obtenir un Best Paper Award à la conférence Distributed Computing and Applications to Business, Engineering and Science (DCABES 2016) pour des algorithmes de calcul matriciels qui tolèrent ces erreurs en exploitant des redondances existant dans le calcul lui-même.

Les supercalculateurs sont des machines composées d’un grand nombre de nœuds de calcul, relativement semblables aux ordinateurs que nous avons devant nous tous les jours, reliés par un réseau à haute vitesse. Ces nœuds de calcul participent ensemble, de façon collaborative, à la résolution d’un calcul : c’est le principe du calcul parallèle. Des parties du programme, appelées des processus, s’exécutent sur ces nœuds de calcul, et s’échangent des données en communiquant sur le réseau. Afin d’avoir un supercalculateur rapide, on agrège un grand nombre de nœuds de calcul, eux-mêmes composés de plusieurs processeurs multi-cœurs. Pour utiliser efficacement un grand nombre de cœurs (de l’ordre de centaines de milliers, voire de millions), des algorithmes efficaces sont utilisés.

Mais le calcul parallèle à grande échelle fait face à un problème : les défaillances matérielles. Les ordinateurs ne sont pas infaillibles, nous en avons tous déjà fait l’expérience douloureuse. Ces pannes peuvent avoir des causes variées : un ventilateur qui tombe en panne et entraîne la surchauffe d’un processeur, une alimentation qui grille… Pour évaluer la « durée de vie » d’un composant, on parle de temps moyen avant défaillance (Mean Time Between Failures ou MTBF). Statistiquement, le MTBF d’un supercalculateur dont les composants ont un MTBF individuel de dix millions d’heures (ce qui est très fiable) n’est que de quelques heures lorsqu’il est composé de centaines de milliers de composants. Lorsqu’un calcul est exécuté sur un supercalculateur à grande échelle, les pannes matérielles sont donc inévitables.

Les calculs s’exécutant sur de telles machines ont alors plusieurs façons de tolérer les pannes, c’est-à-dire de pouvoir continuer leur exécution malgré les pannes qui surviennent sur les nœuds de calcul. Généralement l’approche consiste à tolérer les pannes directement dans l’algorithme de calcul. En effet, lorsqu’un nœud de calcul tombe en panne, les processus qui s’exécutaient dessus meurent et les données qu’ils contenaient sont perdues. Il faut alors que ces données puissent être retrouvées ailleurs, et donc que l’algorithme s’assure de la redondance des données sous une forme ou une autre. Les algorithmes parallèles exploitent des propriétés algébriques des calculs effectués et des propriétés structurelles de l’algorithme lui-même pour insérer cette redondance à moindre coût : les algorithmes sont alors intrinsèquement tolérants aux pannes. L’objectif de ces algorithmes tolérants aux pannes est alors double : que l’introduction de cette redondance ait un impact le plus faible possible sur le temps d’exécution du calcul, et que la récupération du calcul une fois la panne survenue soit la plus rapide possible. Ce dernier point implique que les données soient non seulement redondées, mais que des calculs intermédiaires, au moins partiels, soient faits sur les données redondées pour qu’ils soient déjà prêts en cas de panne.

Cette approche, qui permet d’insérer de la redondance partielle sur des algorithmes parallèles, présente une autre propriété intéressante. En effet, les pannes ne sont pas les seules sources d’erreurs sur les calculs : il arrive que, lorsque les données sont dans la mémoire d’un processeur, elles soient touchées par une inversion de bit. Ces erreurs sont difficiles à détecter car le calcul semble bien se dérouler, mais le résultat numérique est faux. Les calculs redondants permettent donc de vérifier que deux processus ont bien obtenu le même résultat. Dans le cas contraire, le calcul est recommencé.

Le travail de Camille Coti dans sa publication récompensée à DCABES 2016 assure une redondance des calculs pour en garantir le résultat, tout en préservant la rapidité. Elle s’est intéressée en particulier à un calcul de factorisation matricielle qui suit un schéma de calcul et de communications arborescent. Comme évoqué, les parties du calcul sont divisées en 4 processus représentés dans cette illustration ci-contre. Habituellement, chaque processus calcule les données de sa partie, donc, sur cette illustration, de sa couleur. À la fin de la première étape, la moitié des processus envoient ce qu’ils viennent de calculer à un processus de l’autre moitié et s’arrêtent. Les processus qui ont reçu des données font un deuxième calcul pour poursuivre le travail, et la moitié de ces processus l’envoient à un processus de l’autre moitié, et ainsi de suite jusqu’à ce qu’il ne reste plus qu’un seul processus : celui qui détient le résultat final.

À chaque étape, la moitié des processus s’arrête donc de calculer. L’idée de Camille Coti est justement de les mettre à contribution ! À la fin de chaque calcul, au lieu que la moitié des processus se contente d’envoyer son résultat et de s’arrêter, les paires de processus peuvent échanger leurs résultats : chaque paire de processus détient alors les mêmes données. Ces données sont alors redondées, et les processus qui se seraient arrêtés font alors le même calcul que leur processus pair. Le calcul avance ainsi en parallèle sur deux processus en même temps. En cas de panne d’un processus, le résultat intermédiaire est déjà prêt à être récupéré. De plus, à chaque étape, le taux de redondance des données, et donc le nombre de pannes simultanées pouvant être tolérées, est doublé.

Ce nouvel algorithme tolérant aux pannes effectue ainsi peu de modifications sur le nombre d’opérations effectuées pour obtenir le résultat final : un envoi est remplacé par un échange. Les calculs redondants sont effectués sur des processus qui étaient inactifs dans l’algorithme d’origine. Le surcoût lié à la tolérance aux pannes est donc très faible et, en cas de panne, les résultats intermédiaires à récupérer sont déjà prêts.

Publication : Fault Tolerance Techniques for Distributed, Parallel Applications de Camille Coti (aperçu)