Les systèmes pair-à-pair (P2P) sont aujourd'hui très populaires. Leur utilisation va de la messagerie instantanée au partage de fichiers, en passant par la sauvegarde et le stockage distribué ou encore le streaming video. Parmi les protocoles P2P, les protocoles basés sur le "gossip" sont une famille de protocoles qui a fait l'objet de nombreux travaux de recherche durant la dernière décennie. Les raisons de l'engouement pour les protocoles basés sur le "gossip" sont qu'ils sont considérés robustes, faciles à mettre en oeuvre et qu'ils ont des propriétés de passage à l'échelle intéressantes. Ce sont donc des candidats intéressants dès lors qu'il s'agit de réaliser des systèmes distribués dynamiques à large échelle. Cette thèse considère deux problématiques rencontrées lorsque l'on déploie des protocoles basé sur le "gossip" dans un environnement réel comme l'Internet. La première problématique est la prise en compte des pare-feux (NAT) dans le cadre des protocoles d'échantillonnage basés sur le "gossip". Ces protocoles font l'hypothèse que, a tout moment, chaque noeud est capable de communiquer avec n'importe quel noeud du réseau. Cette hypothèse est fausse dès lors que certains noeuds utilisent des NAT. Nous présentons Nylon, un protocole d'échantillonnage qui fonctionne malgré la présence de NAT. Nylon introduit un faible surcoût pour gérer les NAT et partage équitablement ce surcoût entre les noeuds possédant un NAT et les autres noeuds. La deuxième problématique que nous étudions est la possibilité de limiter la dissémination de messages de type "spam" dans les protocoles de dissémination basés sur le "gossip". Ces protocoles sont en effet des vecteurs idéaux pour diffuser les messages de type "spam" du fait qu'il n'y a pas d'autorité de contrôle permettant de filtrer les messages basés sur leur contenu. Nous proposons FireSpam, un protocole de dissémination basé sur le "gossip" qui permet de limiter la diffusion des messages de type "spam". FireSpam fonctionne par filtrage décentralisé (chaque noeud participe au filtrage). Par ailleurs, il fonctionne malgré la présence d'une fraction de noeuds malicieux (aussi appelés "Byzantins") et malgré la présence de noeuds dits “rationnels” (aussi appelés "égoïstes"). Ces derniers sont prêts à dévier du protocole s'ils ont un intérêt à le faire. / Peer-to-peer (P2P) systems are very popular today. Their usage goes from instant messaging to file sharing, from distributed backup and storage to even live-video streaming. Among P2P protocols, gossip-based protocols are a family of protocols which have been the object of several research works in the last decade. The reasons behind the interest in gossip-based protocols are that they are considered robust, easy to implement, and that they have interesting scalability properties. They are then appealing candidates for implementing dynamic and large-scale distributed systems. This thesis tackles two problems faced by gossip-based protocols when deployed on a practical scenario as the Internet. The first problem is coping with Network Address Translators (NATs) in the context of gossip-based peer sampling protocols. These protocols make the assumption that, at any moment, each node is able to communicate with any other node of the network. This assumption is false when some nodes use NATs. We present Nylon, a peer sampling protocol which works despite the presence of NATs. Nylon introduces a low overhead to cope with NATs and fairly balances this overhead among nodes using a NAT and those which do not. The second problem that we study is the possibility to limit the dissemination of “spam” messages in gossip-based dissemination protocols. These protocols are in fact ideal vectors to spread spam messages due to the fact that there is no central authority in charge of filtering messages based on their content. We propose FireSpam, a gossip-based dissemination protocol which allows limiting the dissemination of “spam” messages. FireSpam implements a decentralized filtering mechanism (each node participates to the filtering). Moreover, it works despite the presence of a fraction of malicious nodes (also called “Byzantine” nodes) and despite the presence of so called “rational” nodes (also called “selfish” nodes). These latters are willing to deviate from the protocol if they have an interest in doing so.

Les machines pétascale qui existent aujourd'hui ont un temps moyen entre pannes de plusieurs heures. Il est prévu que dans les futurs systèmes ce temps diminuera. Pour cette raison, les applications qui fonctionneront sur ces systèmes doivent être capables de tolérer des défaillances fréquentes. Aujourd'hui, le moyen le plus commun de le faire est d'utiliser le mécanisme de retour arrière global où l'application fait des sauvegardes périodiques à partir d’un point de reprise. Si un processus s'arrête à cause d'une défaillance, tous les processus reviennent en arrière et se relancent à partir du dernier point de reprise. Cependant, cette solution deviendra infaisable à grande échelle en raison des coûts de l'énergie et de l'utilisation inefficace des ressources. Dans le contexte des applications MPI, les protocoles de journalisation des messages offrent un meilleur confinement des défaillances car ils ne demandent que le redémarrage du processus qui a échoué, ou parfois d’un groupe de processus limité. Par contre, les protocoles existants ont souvent un surcoût important en l’absence de défaillances qui empêchent leur utilisation à grande échelle. Ce surcoût provient de la nécessité de sauvegarder de façon fiable tous les événements non-déterministes afin de pouvoir correctement restaurer l'état du processus en cas de défaillance. Ensuite, comme les journaux de messages sont généralement stockés dans la mémoire volatile, la journalisation risque de nécessiter une large utilisation de la mémoire. Une autre tendance importante dans le domaine des HPC est le passage des applications MPI simples aux nouveaux modèles de programmation hybrides tels que MPI + threads ou MPI + tâches en réponse au nombre croissant de cœurs par noeud. Cela offre l’opportunité de gérer les défaillances au niveau du thread / de la tâche contrairement à l'approche conventionnelle qui traite les défaillances au niveau du processus. Par conséquent, le travail de cette thèse se compose de trois parties. Tout d'abord, nous présentons un protocole de journalisation hiérarchique pour atténuer une défaillance de processus. Le protocole s'appelle Scalable Pattern-Based Checkpointing et il exploite un nouveau modèle déterministe appelé channel-determinism ainsi qu’une nouvelle relation always-happens-before utilisée pour mettre partiellement en ordre les événements de l'application. Le protocole est évolutif, son surcoût pendant l'exécution sans défaillance est limité, il n'exige l'enregistrement d'aucun évènement et, enfin, il a une reprise entièrement distribuée. Deuxièmement, afin de résoudre le problème de la limitation de la mémoire sur les nœuds de calcul, nous proposons d'utiliser des ressources dédiées supplémentaires, appelées logger nodes. Tous les messages qui ne rentrent pas dans la mémoire du nœud de calcul sont envoyés aux logger nodes et sauvegardés dans leur mémoire. À travers de nos expériences nous montrons que cette approche est réalisable et, associée avec un protocole de journalisation hiérarchique comme le SPBC, les logger nodes peuvent être une solution ultime au problème de mémoire limitée sur les nœuds de calcul. Troisièmement, nous présentons un protocole de tolérance aux défaillances pour des applications hybrides qui adoptent le modèle de programmation MPI + tâches. Ce protocole s'utilise pour tolérer des erreurs détectées non corrigées qui se produisent lors de l'exécution d'une tâche. Normalement, une telle erreur provoque une exception du système ce qui provoque un arrêt brutal de l'application. Dans ce cas, l'application doit redémarrer à partir du dernier point de reprise. Nous combinons la sauvegarde des données de la tâche avec une journalisation des messages afin d’aider à la reprise de la tâche qui a subi une défaillance. Ainsi, nous évitons le redémarrage au niveau du processus, plus coûteux. Nous démontrons les avantages de ce protocole avec l'exemple des applications hybrides MPI + OmpSs. / Existing petascale machines have a Mean Time Between Failures (MTBF) in the order of several hours. It is predicted that in the future systems the MTBF will decrease. Therefore, applications that will run on these systems need to be able to tolerate frequent failures. Currently, the most common way to do this is to use global application checkpoint/restart scheme: if some process fails the whole application rolls back the its last checkpointed state and re-executes from that point. This solution will become infeasible at large scale, due to its energy costs and inefficient resource usage. Therefore fine-grained failure containment is a strongly required feature for the fault tolerance techniques that target large-scale executions. In the context of message passing MPI applications, message logging fault tolerance protocols provide good failure containment as they require restart of only one process or, in some cases, a bounded number of processes. However, existing logging protocols experience a number of issues which prevent their usage at large scale. In particular, they tend to have high failure-free overhead because they usually need to store reliably any nondeterministic events happening during the execution of a process in order to correctly restore its state in recovery. Next, as message logs are usually stored in the volatile memory, logging may incur large memory footprint, especially in communication-intensive applications. This is particularly important because the future exascale systems expect to have less memory available per core. Another important trend in HPC is switching from MPI-only applications to hybrid programming models like MPI+threads and MPI+tasks in response to the increasing number of cores per node. This gives opportunities for employing fault tolerance solutions that handle faults on the level of threads/tasks. Such approach has even better failure containment compared to message logging protocols which handle failures on the level of processes. Thus, the work in these dissertation consists of three parts. First, we present a hierarchical log-based fault tolerance solution, called Scalable Pattern-Based Checkpointing (SPBC) for mitigating process fail-stop failures. The protocol leverages a new deterministic model called channel-determinism and a new always-happens-before relation for partial ordering of events in the application. The protocol is scalable, has low overhead in failure-free execution and does not require logging any events, provides perfect failure containment and has a fully distributed recovery. Second, to address the memory limitation problem on compute nodes, we propose to use additional dedicated resources, or logger nodes. All the logs that do not fit in the memory of compute nodes are sent to the logger nodes and kept in their memory. In a series of experiments we show that not only this approach is feasible, but, combined with a hierarchical logging scheme like the SPBC, logger nodes can be an ultimate solution to the problem of memory limitation for logging protocols. Third, we present a log-based fault tolerance protocol for hybrid applications adopting MPI+tasks programming model. The protocol is used to tolerate detected uncorrected errors (DUEs) that happen during execution of a task. Normally, a DUE caused the system to raise an exception which lead to an application crash. Then, the application has to restart from a checkpoint. In the proposed solution, we combine task checkpointing with message logging in order to support task re-execution. Such task-level failure containment can be beneficial in large-scale executions because it avoids the more expensive process-level restart. We demonstrate the advantages of this protocol on the example of hybrid MPI+OmpSs applications.

Dans cette thèse de doctorat, nous abordons trois défis auxquels sont confrontés les solveurs d'algèbres linéaires dans la perspective des futurs systèmes exascale: accélérer la convergence en utilisant des techniques innovantes au niveau algorithmique, en profitant des accélérateurs GPU (Graphics Processing Units) pour améliorer le calcul sur plusieurs systèmes, en évaluant l'impact des erreurs due à l'augmentation du parallélisme dans les superordinateurs. Nous nous intéressons à l'étude des méthodes permettant d'accélérer la convergence et le temps d'exécution des solveurs itératifs pour les grands systèmes linéaires creux. Le solveur plus spécifiquement considéré dans ce travail est le “parallel Algebraic Recursive Multilevel Solver (pARMS)” qui est un soldeur parallèle sur mémoire distribuée basé sur les méthodes de sous-espace de Krylov.Tout d'abord, nous proposons d'intégrer une technique de randomisation appelée “Random Butterfly Transformations (RBT)” qui a été proposée avec succès pour éliminer le coût du pivotage dans la résolution des systèmes linéaires denses. Notre objectif est d'appliquer cette technique dans le préconditionneur ARMS de pARMS pour résoudre plus efficacement le dernier système Complément de Schur dans l'application du processus à multi-niveaux récursif. En raison de l'importance considérable du dernier Complément de Schur pour certains problèmes de test, nous proposons également d'utiliser une variante creux de RBT suivie d'un solveur direct creux (SuperLU). Les résultats expérimentaux sur certaines matrices de la collection de Davis montrent une amélioration de la convergence et de la précision par rapport aux implémentations existantes.Ensuite, nous illustrons comment une approche non intrusive peut être appliquée pour implémenter des calculs GPU dans le solveur pARMS, plus particulièrement pour la phase de préconditionnement locale qui représente une partie importante du temps pour la résolution. Nous comparons les solveurs purement CPU avec les solveurs hybrides CPU / GPU sur plusieurs problèmes de test issus d'applications physiques. Les résultats de performance du solveur hybride CPU / GPU utilisant le préconditionnement ARMS combiné avec RBT, ou le préconditionnement ILU(0), montrent un gain de performance jusqu'à 30% sur les problèmes de test considérés dans nos expériences.Enfin, nous étudions l'effet des défaillances logicielles variable sur la convergence de la méthode itérative flexible GMRES (FGMRES) qui est couramment utilisée pour résoudre le système préconditionné dans pARMS. Le problème ciblé dans nos expériences est un problème elliptique PDE sur une grille régulière. Nous considérons deux types de préconditionneurs: une factorisation LU incomplète à double seuil (ILUT) et le préconditionneur ARMS combiné avec randomisation RBT. Nous considérons deux modèle de fautes logicielles différentes où nous perturbons la multiplication du vecteur matriciel et la phase de préconditionnement, et nous comparons leur impact potentiel sur la convergence. / In this PhD thesis, we address three challenges faced by linear algebra solvers in the perspective of future exascale systems: accelerating convergence using innovative techniques at the algorithm level, taking advantage of GPU (Graphics Processing Units) accelerators to enhance the performance of computations on hybrid CPU/GPU systems, evaluating the impact of errors in the context of an increasing level of parallelism in supercomputers. We are interested in studying methods that enable us to accelerate convergence and execution time of iterative solvers for large sparse linear systems. The solver specifically considered in this work is the parallel Algebraic Recursive Multilevel Solver (pARMS), which is a distributed-memory parallel solver based on Krylov subspace methods.First we integrate a randomization technique referred to as Random Butterfly Transformations (RBT) that has been successfully applied to remove the cost of pivoting in the solution of dense linear systems. Our objective is to apply this method in the ARMS preconditioner to solve more efficiently the last Schur complement system in the application of the recursive multilevel process in pARMS. The experimental results show an improvement of the convergence and the accuracy. Due to memory concerns for some test problems, we also propose to use a sparse variant of RBT followed by a sparse direct solver (SuperLU), resulting in an improvement of the execution time.Then we explain how a non intrusive approach can be applied to implement GPU computing into the pARMS solver, more especially for the local preconditioning phase that represents a significant part of the time to compute the solution. We compare the CPU-only and hybrid CPU/GPU variant of the solver on several test problems coming from physical applications. The performance results of the hybrid CPU/GPU solver using the ARMS preconditioning combined with RBT, or the ILU(0) preconditioning, show a performance gain of up to 30% on the test problems considered in our experiments.Finally we study the effect of soft fault errors on the convergence of the commonly used flexible GMRES (FGMRES) algorithm which is also used to solve the preconditioned system in pARMS. The test problem in our experiments is an elliptical PDE problem on a regular grid. We consider two types of preconditioners: an incomplete LU factorization with dual threshold (ILUT), and the ARMS preconditioner combined with RBT randomization. We consider two soft fault error modeling approaches where we perturb the matrix-vector multiplication and the application of the preconditioner, and we compare their potential impact on the convergence of the solver.