| Optimisation des réductions polyédriques et leur utilisation dans la tolérance aux fautes basée sur les algorithmes (Optimizations of polyhedral reductions and their use in algorithm-based fault tolerance) | ||
Narmour, Louis - (2024-12-10) / Université de Rennes, Colorado State University (États-unis) - Optimisation des réductions polyédriques et leur utilisation dans la tolérance aux fautes basée sur les algorithmes Langue : Anglais Directeur de thèse: Derrien, Steven; Rajopadhye, Sanjay Laboratoire : INRIA-RENNES Ecole Doctorale : MATISSE Thématique : Informatique | ||
Mots-clés : amélioration algorithmique, compilation polyédrique, tolérance aux fautes, Tolérance aux fautes (informatique), Optimisation mathématique, Compilation (informatique) Résumé : Nous étendons les travaux antérieurs sur la simplification des réductions pour l'amélioration algorithmique et montrons comment traiter une classe de programmes strictement plus générale que celle supportée précédemment. Nous montrons également que la simplification permet de redécouvrir plusieurs résultats clés en matière d'amélioration algorithmique dans de nombreux domaines, qui n'étaient auparavant obtenus qu'au prix d'une analyse et d'efforts manuels intelligents de la part de l'homme. En outre, nous motivons le lien entre la simplification et les techniques de tolérance aux fautes en utilisant la tolérance aux fautes basée sur les algorithmes (ABFT). Les méthodes ABFT fonctionnent en ajoutant des calculs redondants sous la forme de sommes de contrôle invariantes (c'est-à-dire des réductions) qui, par définition, ne devraient pas changer au cours de l'exécution du programme. En calculant et en surveillant les sommes de contrôle, il est possible de détecter les erreurs en observant les différences entre les valeurs des sommes de contrôle. Toutefois, il s'agit d'un défi car il nécessite une analyse manuelle minutieuse du programme d'entrée, et il faut veiller à ce que les calculs des sommes de contrôle soient effectués de manière suffisamment efficace pour que cela en vaille la peine. Il s'agit du premier travail à proposer une telle analyse dans un compilateur. Résumé (anglais) : In this work, We study the optimization of reduction operations and motivate a deeper connection between techniques for algorithmic improvement and Algorithm-Based Fault Tolerance (ABFT). We extend prior work on reduction simplification and provide the first complete push-button implementation in a compiler. In doing so, we show how to handle a strictly more general class of programs than previously supported. We also show that simplification rediscovers several key results in algorithmic improvement across multiple domains, previously only obtained through clever manual human analysis and effort. Complementary, we study ABFT methods, which work by adding some redundant computation in the form of invariant checksums (i.e., reductions), which, by definition, should not change as the program executes. By computing and monitoring checksums, it is possible to detect errors by observing differences in the checksum values. However, this is challenging because it requires careful manual analysis of the input program, and care must be taken to subsequently carry out the checksum computations efficiently enough for it to be worth it. We propose automation techniques for a class of scientific codes called stencil computations and give methods to carry out this analysis at compile time. This is the first work to propose such an analysis in a compiler. Identifiant : rennes1-ori-wf-1-20473 | ||
| Exporter au format XML |