Tolérance aux pannes basée sur les applications pour l’algèbre linéaire numérique à grande échelle

The increasing size of supercomputers is allowing to compute solutions for various computational problems that, not so long ago, were consuming too much time and memory to be solved. However, at that scale, other challenges are arising. The optimal performance of dedicated algorithms running on these parallel and distributed architectures gets hampered by these new challenges. Large-scale systems involve their own challenges due to the total number of hardware and software components and the complexity of these components, including system reliability, availability, and scalability. In particular, hardware or software failures may occur at any moment during the execution of parallel applications that, therefore, cannot complete unless these failures are handled. Meanwhile, as high-performance systems have become larger, failures have become common and computation units are expected to fail during the execution of critical programs. As a consequence, fault tolerance has arisen as a major challenge in parallel and distributed computing, and parallel programs ought to rely on scalable algorithms that also ensure the correct completion of the program in spite of failures. In particular, parallel subroutines provided in libraries should be able to mitigate errors that occur in a call to these subroutines. For instance, linear algebra operations arebuilding blocks used by domain scientists to solve problems or to simulate scientific phenomena. They are usually provided in highly optimized libraries and are typically software components that ought to be fault tolerant. One way to make sure fault tolerant algorithms are robust and can tolerate any failure scenario consists in designing a formal model of the system and prove properties on this model. In this thesis, I am presenting a set of fault tolerant algorithms for QR, LU and Cholesky matrix factorizations. These algorithms rely on a the corresponding communication-avoiding algorithms, for tall-and-skinny matrices and for general matrices; communication-avoiding algorithms have given good performance on multiple architectures and have properties that make them scale well. Using a model, I am proving robustness properties of these algorithms and, in particular, that as long as enough processes survive (and this number decreases as the execution progresses), they can tolerate any failure scenario. My algorithms can tolerate crash-type failures, respawn new processes to replace the failed ones and take advantage of algebraic and algorithmic properties to implement a forward-recovery approach, i.e., the processes that replace the failed ones to not roll back to a previous state but are inserted at a point of the execution that was never reached by the failed processes. I am presenting an experimental evaluation of the overhead introduced by the fault tolerance mechanisms on failure-free executions and the cost of a failure. Both scenarios have a small overhead, meaning that the fault tolerance mechanisms have little impact on the critical path of the algorithms, and the post-failure restoration time is small.La taille croissante des supercalculateurs a permis de s'attaquer à des problèmes de calcul auparavant trop coûteux en temps et en mémoire pour être résolus. Cependant, d'autres problèmes apparaissent à cette échelle et la performance obtenue par les algorithmes parallèles et distribués conçus pour cette échelle est impactée. Les systèmes à grande échelle font face à des défis spécifiques du fait du grand nombre de composants matériels et logiciels dont ils sont composés, et parmi ces défis on compte la fiabilité du système, la disponibilité et le passage à l'échelle. En particulier, des défaillances matérielles et logicielles peuvent survenir à tout moment pendant l'exécution d'applications parallèles qui, par conséquent, ne peuvent pas s'exécuter intégralement et atteindre leur fin. Alors que la taille des systèmes parallèles augmente, les défaillances sont appelées à arriver fréquemment lors de l'exécution de programmes parallèles. Par conséquent, la tolérance aux défaillances est aujourd'hui un défi important pour le calcul parallèle distribué, et des programmes parallèles doivent se baser sur des algorithmes capables de passer à l'échelle mais aussi d'assurer la terminaison correcte du programme malgré les défaillances qui surviendraient. En particulier, des fonctions parallèles fournies dans des bibliothèques doivent être capables de tolérer des défaillances survenues dans les appels à ses fonctions. Les opérations d'algèbre linéaire sont des briques de base de calculs utilisés par les scientifiques pour résoudre des problèmes ou simuler des phénomènes scientifiques. Elles sont habituellement fournies dans des bibliothèques hautement optimisées et sont typiquement des composants logiciels qui devraient être capables de tolérer des défaillances. Une méthode pour s'assurer que des algorithmes tolérants aux défaillances sont robustes et peuvent tolérer n'importe quel scénario de défaillances consiste à concevoir un modèle formel du système et à prouver des propriétés sur ce modèle. Dans cette thèse, je présente un ensemble d'algorithmes tolérants aux pannes pour les factorisations LU, QR et de Cholesky. Ces algorithmes se basent sur les algorithmes à évitement de communications correspondants, pour matrices hautes et fines et pour matrices générales. Les algorithmes à évitement de communications ont montré de bonnes performances sur de multiples architectures contemporaines et ont des propriétés qui leur permettent de bien passer à l'échelle. En utilisant un modèle, je prouve des propriétés de robustesse de ces algorithmes et, en particulier, que tant que suffisamment de processus survivent (et leur nombre diminue au cours de l'exécution), ils peuvent tolérer n'importe quel scénario de défaillances. Ces algorithmes tolèrent des pannes de type crash, ou fail-stop, relancent des processus pour remplacer ceux atteints par des défaillances et exploitent des propriétés algorithmiques et algébriques pour mettre en place une approche de type retour en avançant, c'est-à-dire que les processus qui remplacent ceux touchés par les défaillances n'effectuent pas un retour en arrière mais sont insérés dans l'exécution à un point qui n'avait jamais été atteint par les processus touchés par les défaillances. Je présente une évaluation expérimentale du surcoût introduit par les mécanismes de tolérants aux défaillances sur l'exécution en l'absence de pannes et le coût d'une défaillance. Ces deux scenarii ont un surcoût faible, impliquant que les mécanismes de tolérance aux défaillance ont un impact faible sur le chemin critique des algorithmes, et le temps de restauration de l'état après une défaillance est faible