Cette thèse introduit deux outils pour l'accès performant aux données d'un algorithme à front d'onde dans un contexte d'exécution out-of-core. Ces algorithmes sont facilement parallélisables en utilisant des techniques de macro-pipelining, qui permettent un recouvrement des calculs et des communications. Le premier outil part du constat que les performances des opérations de lecture/écriture dans une telle situation sont désastreuses: les données sont éclatées sur disque et leur rapatriement en mémoire est long et coûteux. Le nouvel agencement de données sur disque proposé permet de résoudre ces problèmes en accédant aux données uniquement de manière contiguë. Si ce premier outil décrit comment accéder aux données, le deuxième est un modèle de synchronisation qui décrit quand y accéder. En effet, l'exécution parallèle et concurrente des algorithmes à front d'onde nécessite un contrôle strict des temps d'accès et des temps d'attente. Le modèle présenté dans cette thèse remplit ce rôle, tout en donnant des garanties de propriétés intéressantes pour les applications itératives: verrouillage pro-actif, évolution sans interblocages, progression homogène des tâches. L'utilisation de ces deux outils a été intensivement testée sur un benchmark de référence et expérimentée sur des machines de la plate-forme Grid'5000.

L'utilisation d'algorithmes itératifs est aujourd'hui largement répandue dans tous les domaines du traitement du signal et des communications numériques. Dans les systèmes de communications modernes, les algorithmes itératifs sont utilisés dans le décodage des codes ''low-density parity-check'' (LDPC), qui sont une classe de codes correcteurs d'erreurs utilisés pour leurs performances exceptionnelles en terme de taux d'erreur. Dans un domaine plus récent qu'est le ''compressed sensing'', les algorithmes itératifs sont utilisés comme méthode de reconstruction afin de recouvrer un signal ''sparse'' à partir d'un ensemble d'équations linéaires, appelées observations. Cette thèse traite principalement du développement d'algorithmes itératifs à faible complexité pour les deux domaines mentionnés précédemment, à savoir le design d'algorithmes de décodage à faible complexité pour les codes LDPC, et le développement et l'analyse d'un algorithme de reconstruction à faible complexité, appelé ''Interval-Passing Algorithm (IPA)'', dans le cadre du ''compressed sensing''.Dans la première partie de cette thèse, nous traitons le cas des algorithmes de décodage des codes LDPC. Il est maintenu bien connu que les codes LDPC présentent un phénomène dit de ''plancher d'erreur'' en raison des échecs de décodage des algorithmes de décodage traditionnels du types propagation de croyances, et ce en dépit de leurs excellentes performances de décodage. Récemment, une nouvelle classe de décodeurs à faible complexité, appelés ''finite alphabet iterative decoders (FAIDs)'' ayant de meilleures performances dans la zone de plancher d'erreur, a été proposée. Dans ce manuscrit nous nous concentrons sur le problème de la sélection de bons décodeurs FAID pour le cas de codes LDPC ayant un poids colonne de 3 et le cas du canal binaire symétrique. Les méthodes traditionnelles pour la sélection des décodeurs s'appuient sur des techniques asymptotiques telles que l'évolution de densité, mais qui ne garantit en rien de bonnes performances sur un code de longueurs finies surtout dans la région de plancher d'erreur. C'est pourquoi nous proposons ici une méthode de sélection qui se base sur la connaissance des topologies néfastes au décodage pouvant être présente dans un code en utilisant le concept de ''trapping sets bruités''. Des résultats de simulation sur différents codes montrent que les décodeurs FAID sélectionnés grâce à cette méthode présentent de meilleures performance dans la zone de plancher d'erreur comparé au décodeur à propagation de croyances.Dans un second temps, nous traitons le sujet des algorithmes de reconstruction itératifs pour le compressed sensing. Des algorithmes itératifs ont été proposés pour ce domaine afin de réduire la complexité induite de la reconstruction par ''linear programming''. Dans cette thèse nous avons modifié et analysé un algorithme de reconstruction à faible complexité dénommé IPA utilisant les matrices creuses comme matrices de mesures. Parallèlement aux travaux réalisés dans la littérature dans la théorie du codage, nous analysons les échecs de reconstruction de l'IPA et établissons le lien entre les ''stopping sets'' de la représentation binaire des matrices de mesure creuses. Les performances de l'IPA en font un bon compromis entre la complexité de la reconstruction sous contrainte de minimisation de la norme $ell_1$ et le très simple algorithme dit de vérification.

La technologie actuelle permet aux scientifiques de divers domaines d'obtenir des données de plus en plus précises et volumineuses, Afin de résoudre ces problèmes associés à l'obtention de ces données, les architectures de calcul évoluent, en fournissant toujours plus de ressources, notamment grâce à des machines plus puissantes et à leur mutualisation. Dans cette thèse, nous proposons d'étudier dans un premier temps le placement des tâches d'applications itératives asynchrones dans des environnements hétérogènes et volatils. Notre solution nous permet également de s'affranchir de l(hétérogénéité des machines hôtes tout en offrent une implantation facilitée de politiques de tolérance aux pannes, les expérimentations que nous avons menées sont encourageantes et montrent qu'il existe un réel potentiel quand à l'utilisation d'une telle plateforme pour l'exécution d'applications scientifiques.

En imagerie du petit animal par tomographie d'émission monophotonique (TEMP), la modélisation de la réponse physique du détecteur demande beaucoup de soin pour en contrebalancer la faible résolution intrinsèque. Les coupes du volume à reconstruire s'obtiennent ainsi à partir des projections, à la fois par une opération de rétroprojection et une déconvolution de la réponse impulsionnelle du détecteur. Nous optons dès lors pour des méthodes itératives de résolution d'un grand système linéaire qui fonctionnent indépendamment de la complexité du modèle.<br />Pour parvenir à des résultats exploitables, tant en terme de résolution spatiale que de temps de calcul chez le rat ou la souris, nous décrivons dans ce travail les choix de notre modélisation par une réponse impulsionnelle gaussienne, ajustée suivant des paramètres physiques et géométriques. Nous utilisons ensuite la symétrie de rotation inhérente au dispositif pour ramener le calcul de P opérateurs de projections au calcul d'un seul d'entre eux, par une discrétisation de l'espace compatible avec cette symétrie, tout en contrôlant la densité angulaire de voxels pour éviter un suréchantillonnage au centre du volume.<br />Enfin, nous proposons une nouvelle classe d'algorithmes adaptés à la fréquence qui permettent d'optimiser la reconstruction d'une gamme de fréquence spatiale donnée, évitant ainsi d'avoir à calculer de nombreuses itérations lorsque le spectre à reconstruire se retrouve surtout dans les hautes fréquences.

Dans cette thèse, nous nous sommes intéressée à la mise en oeuvre d'algorithmes itératifs sur des grappes hétérogènes. Ces algorithmes fonctionnent avec un volume important de données (calcul de matrices, traitement d'images, etc.), qui sera réparti sur l'ensemble des processeurs. À chaque itération, des calculs indépendants sont effectués en parallèle et certaines communications ont lieu. Il n'existe pas de raison a priori de réduire le partitionnement des données à une unique dimension et de ne l'appliquer que sur un anneau de processeurs unidimensionnel. Cependant, un tel partitionnement est très naturel et nous montrerons que trouver l'optimal est déjà très difficile. Après cette étude sur le placement et l'équilibrage de charge pour plates-formes hétérogènes, nous nous sommes intéressée à la redistribution de données sur ces mêmes plates-formes, lorsque que les caractéristiques de ces dernières changent. En ce qui concerne les anneaux de processeurs homogènes, nous avons totalement résolu le problème : nous avons obtenu des algorithmes optimaux et prouvé leur exactitude dans le cas homogène et dans le cas hétérogène. En ce qui concerne les anneaux hétérogènes, le cas unidirectionnel a été totalement résolu, alors que le cas bidirectionnel reste ouvert. Cependant, sous l'hypothèse de redistribution légère, nous sommes capable de résoudre le problème de manière optimale.

La résolution numérique de n’importe quelle discrétisation d’équations aux dérivées partielles non linéaires requiert le plus souvent un algorithme itératif. En général, la discrétisation des équations aux dérivées partielles donne lieu à des systèmes de grandes dimensions. Comme la résolution des grands systèmes est très coûteuse en terme de temps de calcul, une question importante se pose: afin d’obtenir une solution approchée de bonne qualité, quand est-ce qu’il faut arrêter l’itération afin d’éviter les itérations inutiles ? L’objectif de cette thèse est alors d’appliquer, à différentes équations, une méthode qui nous permet de diminuer le nombre d’itérations de la résolution des systèmes en gardant toujours une bonne précision de la méthode numérique. En d’autres termes, notre but est d’appliquer une nouvelle méthode qui fournira un gain remarquable en terme de temps de calcul. Tout d’abord, nous appliquons cette méthode pour un problème non linéaire modèle. Nous effectuons l’analyse a priori et a posteriori de la discrétisation par éléments finis de ce problème et nous proposons par la suite deux algorithmes de résolution itérative correspondants. Nous calculons les estimations d’erreur a posteriori de nos algorithmes itératifs proposés et nous présentons ensuite quelques résultats d’expérience numériques afin de comparer ces deux algorithmes. Nous appliquerons de même cette approche pour les équations de Navier-Stokes. Nous proposons un schéma itératif et nous étudions la convergence et l’analyse a priori et a posteriori correspondantes. Finalement, nous présentons des simulations numériques montrant l’efficacité de notre méthode. / The numerical resolution of any discretization of nonlinear PDEs most often requires an iterative algorithm. In general, the discretization of partial differential equations leads to large systems. As the resolution of large systems is very costly in terms of computation time, an important question arises. To obtain an approximate solution of good quality, when is it necessary to stop the iteration in order to avoid unnecessary iterations? A posteriori error indicators have been studied in recent years owing to their remarkable capacity to enhance both speed and accuracy in computing. This thesis deals with a posteriori error estimation for the finite element discretization of nonlinear problems. Our purpose is to apply a new method that allows us to reduce the number of iterations of the resolution system while keeping a good accuracy of the numerical method. In other words, our goal is to apply a new method that provides a remarkable gain in computation time. For a given nonlinear equation we propose a finite element discretization relying on the Galerkin method. We solve the discrete problem using two iterative methods involving some kind of linearization. For each of them, there are actually two sources of error, namely discretization and linearization. Balancing these two errors can be very important, since it avoids performing an excessive number of iterations. Our results lead to the construction of computable upper indicators for the full error. Similarly, we apply this approach to the Navier-Stokes equations. Several numerical tests are provided to evaluate the efficiency of our indicators.

L'utilisation d'algorithmes itératifs est aujourd'hui largement répandue dans tous les domaines du traitement du signal et des communications numériques. Dans les systèmes de communications modernes, les algorithmes itératifs sont utilisés dans le décodage des codes ``low-density parity-check`` (LDPC), qui sont une classe de codes correcteurs d'erreurs utilisés pour leurs performances exceptionnelles en terme de taux d'erreur. Dans un domaine plus récent qu'est le ``compressed sensing``, les algorithmes itératifs sont utilisés comme méthode de reconstruction afin de recouvrer un signal ''sparse`` à partir d'un ensemble d'équations linéaires, appelées observations. Cette thèse traite principalement du développement d'algorithmes itératifs à faible complexité pour les deux domaines mentionnés précédemment, à savoir le design d'algorithmes de décodage à faible complexité pour les codes LDPC, et le développement et l'analyse d'un algorithme de reconstruction à faible complexité, appelé ''Interval-Passing Algorithm (IPA)'', dans le cadre du ``compressed sensing``.Dans la première partie de cette thèse, nous traitons le cas des algorithmes de décodage des codes LDPC. Il est maintenu bien connu que les codes LDPC présentent un phénomène dit de ''plancher d'erreur`` en raison des échecs de décodage des algorithmes de décodage traditionnels du types propagation de croyances, et ce en dépit de leurs excellentes performances de décodage. Récemment, une nouvelle classe de décodeurs à faible complexité, appelés ''finite alphabet iterative decoders (FAIDs)'' ayant de meilleures performances dans la zone de plancher d'erreur, a été proposée. Dans ce manuscrit nous nous concentrons sur le problème de la sélection de bons décodeurs FAID pour le cas de codes LDPC ayant un poids colonne de 3 et le cas du canal binaire symétrique. Les méthodes traditionnelles pour la sélection des décodeurs s'appuient sur des techniques asymptotiques telles que l'évolution de densité, mais qui ne garantit en rien de bonnes performances sur un code de longueurs finies surtout dans la région de plancher d'erreur. C'est pourquoi nous proposons ici une méthode de sélection qui se base sur la connaissance des topologies néfastes au décodage pouvant être présente dans un code en utilisant le concept de ``trapping sets bruités''. Des résultats de simulation sur différents codes montrent que les décodeurs FAID sélectionnés grâce à cette méthode présentent de meilleures performance dans la zone de plancher d'erreur comparé au décodeur à propagation de croyances.Dans un second temps, nous traitons le sujet des algorithmes de reconstruction itératifs pour le compressed sensing. Des algorithmes itératifs ont été proposés pour ce domaine afin de réduire la complexité induite de la reconstruction par ``linear programming''. Dans cette thèse nous avons modifié et analysé un algorithme de reconstruction à faible complexité dénommé IPA utilisant les matrices creuses comme matrices de mesures. Parallèlement aux travaux réalisés dans la littérature dans la théorie du codage, nous analysons les échecs de reconstruction de l'IPA et établissons le lien entre les ``stopping sets'' de la représentation binaire des matrices de mesure creuses. Les performances de l'IPA en font un bon compromis entre la complexité de la reconstruction sous contrainte de minimisation de la norme $ell_1$ et le très simple algorithme dit de vérification. / Iterative algorithms are now widely used in all areas of signal processing and digital communications. In modern communication systems, iterative algorithms are used for decoding low-density parity-check (LDPC) codes, a popular class of error-correction codes that are now widely used for their exceptional error-rate performance. In a more recent field known as compressed sensing, iterative algorithms are used as a method of reconstruction to recover a sparse signal from a linear set of measurements. This thesis primarily deals with the development of low-complexity iterative algorithms for the two aforementioned fields, namely, the design of low-complexity decoding algorithms for LDPC codes, and the development and analysis of a low complexity reconstruction algorithm called Interval-Passing Algorithm (IPA) for compressed sensing.In the first part of this thesis, we address the area of decoding algorithms for LDPC codes. It is well-known that LDPC codes suffer from the error floor phenomenon in spite of their exceptional performance, where traditional iterative decoders based on the belief propagation (BP) fail for certain low-noise configurations. Recently, a novel class of decoders called ''finite alphabet iterative decoders (FAIDs)'' were proposed that are capable of surpassing BP in the error floor at much lower complexity. In this work, we focus on the problem of selection of particularly good FAIDs for column-weight-three codes over the Binary Symmetric channel (BSC). Traditional methods for decoder selection use asymptotic techniques such as the density evolution method, which do not guarantee a good performance on finite-length codes especially in theerror floor region. Instead, we propose a methodology for selection that relies on the knowledge of potentially harmful topologies that could be present in a code, using the concept of noisy trapping set. Numerical results are provided to show that FAIDs selected based on our methodology outperform BP in the error floor on several codes.In the second part of this thesis, we address the area of iterative reconstruction algorithms for compressed sensing. Iterative algorithms have been proposed for compressed sensing in order to tackle the complexity of the LP reconstruction method. In this work, we modify and analyze a low complexity reconstruction algorithm called the IPA which uses sparse matrices as measurement matrices. Similar to what has been done for decoding algorithms in the area of coding theory, we analyze the failures of the IPA and link them to the stopping sets of the binary representation of the sparse measurement matrices used. The performance of the IPA makes it a good trade-off between the complex L1-minimization reconstruction and the very simple verification decoding.

La technologie actuelle permet aux scientifiques de divers domaines d'obtenir des données de plus en plus précises et volumineuses, Afin de résoudre ces problèmes associés à l'obtention de ces données, les architectures de calcul évoluent, en fournissant toujours plus de ressources, notamment grâce à des machines plus puissantes et à leur mutualisation. Dans cette thèse, nous proposons d’étudier dans un premier temps le placement des tâches d'applications itératives asynchrones dans des environnements hétérogènes et volatils. Notre solution nous permet également de s'affranchir de l(hétérogénéité des machines hôtes tout en offrent une implantation facilitée de politiques de tolérance aux pannes, les expérimentations que nous avons menées sont encourageantes et montrent qu'il existe un réel potentiel quand à l'utilisation d'une telle plateforme pour l'exécution d'applications scientifiques. / The current technology allows scientists of several domains to obtain more precise and large data. In the same time, computing architectures evolve too, by providing even more computing resources, with more powerful machines and the pooling of them. In this thesis, in a first time we propose to study the problem of the mapping of asynchronous iterative applications tasks into heterogeneous and volatile environments. Our solution allows also to overcome the heterogeneity of host machines while offering an easier implementation of policies for fault tolerance. The experiments we have conducted are encouraging ad show that there is real potential for the use of such a platform for running scientific applications.