Cette thèse présente les limites du mode s.i.m.d. Dans le cadre de la programmation parallèle d'algorithmes d'algèbre linéaire. Plus précisément, celles de la règle d'or du parallélisme massif: un élément de la matrice par processeur, sont développées. Des expérimentations sont effectuées sur une connection machine 2. Néanmoins, la première partie montre comment la création de procédures de communications écrites a partir d'un nouvel algorithme de construction d'arbres équilibres, et un placement de données judicieux permettent d'atteindre des performances proches de la puissance crête. Mais ce type de travail ne peut pas être effectue sur n'importe quel algorithme, et tout ne s'adapte pas aussi bien. Dans la deuxième partie, nous présentons les avantages de la décomposition en blas pour la construction d'algorithmes massivement parallèles. Elle met, dans le chapitre 4, en évidence la barrière de synchronisation pour la methode du gradient conjugue. Nous proposons dans ce cas particulier comme solution, une ancienne methode qui bien qu'elle soit, en séquentiel, de convergence plus lente, est plus rapide en parallèle. De plus, la structure des matrices est un facteur important. Elle permet d'accélérer les calculs et d'augmenter la dimension des problèmes a résoudre. L'architecture des machines actuelles en limite encore trop l'utilisation. La dernière partie est entièrement consacrée aux permutations, et aux communications qu'elles entrainent. Dans le cadre de l'algorithme de Burg, nous proposons une solution qui calcule a la fois les coefficients de réflexion et ceux d'autoregression sans cout supplémentaire

L'objet de cette thèse est l'étude de la parallélisation d'algorithmes du calcul scientifique et<br />leur implémentation sur des ordinateurs parallèles à mémoire partagée et sur des réseaux systoliques.<br /> Un accent particulier est mis sur l'obtention de résultats de complexité. La thèse est organisée autour<br /> d'articles et textes de conférences qui sont analysés et discutés dans une première partie de façon à <br />permettre de replacer les problèmes traités dans leur contexte.<br />Dans le premier chapitre, nous présentons les principaux résultats théoriques concernant <br />l'étude de complexité des algorithmes parallèles, ainsi qu'une description critique de l'architecture <br />de référence, qui est une machine de type MIMD à mémoire partagée. Le chapitre suivant est dédie" à <br />l'ensemble des résultats de complexité concernant les algorithmes de diagonalisation et <br />l'élimination de Gauss, il a pour but d'illustrer la méthodologie. Il existe en tout dix écritures possibles de la méthode de Gauss, qui conduisent principalement à deux grandes classes de graphes de précédente, conceptuellement différents : les graphes de type "glouton" et ceux du type "2 pas".<br />Ces types de graphes se rencontrent d'une manière plus générale dans d'autres problèmes <br />d'algèbre linéaire et même dans certaines méthodes non numériques de la théorie des graphes. <br />Nous développons les résultats de complexité concernant ces deux types de graphes sur les exemples<br /> les plus courant (versions kji et kij de Gauss en parallèle), puis nous montrons comment adapter<br /> l'étude en prenant en compte t'es temps de communication entre tes processeurs, ce qui rend le modèle<br /> théorique plus réaliste.<br />Le chapitre 6 est consacré aux architectures systoliques. Le problème du chemin algébrique permet <br />d'unifier plusieurs problèmes informatiques. Nous présentons un réseau résolvant ce problème en Sn-2 <br />pas sur un réseau de taille n(n+l ). De plus, quelques modifications permettent de calculer des projections<br /> en filtrage adaptatif en vu d'obtenir une solution en temps réel pour le traitement numérique des signaux.<br />Avant de conclure, nous présentons des résultats complémentaires de parallélisation effective sur d'autres<br /> types d'architectures : l'étude de l'algorithme du gradient conjugué sur des super calculateurs <br />(CRAY-XMP et IBM 3090-VF).

Le problème de l'assimilation de données sous sa forme générale peut se formuler : "comment utiliser simultanément un modèle théorique et des observations pour obtenir la meilleure prévision météorologique ou océanographique ?", sa résolution est très coûteuse, pour la prochaine génération de modèles elle nécessitera une puissance de calcul de l'ordre de 10 Tflops. à l'heure actuelle, aucun calculateur n'est capable de fournir de telles performances mais cela devrait être possible dans quelques années, en particulier grâce aux ordinateurs parallèles à mémoire distribuée. Mais, la programmation de ces machines reste un processus compliqué et on ne connaît pas de méthode générale pour paralléliser de manière optimale un algorithme donné. Nous tenterons, de répondre au problème de la parallélisation de l'assimilation de données variationnelle, ce qui nous conduira à étudier la parallélisation d'algorithmes numériques d'optimisation assez généraux. Pour cela, nous étendrons la méthodologie de l'écriture des modèles adjoints au cas où le modèle direct est parallèle avec échanges de messages explicites. Nous étudierons les différentes approches possibles pour paralléliser la résolution du problème de l'assimilation de données : au niveau des modèles météorologiques direct et adjoints, au niveau de l'algorithme d'optimisation ou enfin au niveau du problème lui-même. Cela nous conduira à transformer un problème séquentiel d'optimisation sans contraintes en un ensemble de problèmes d'optimisation relativement indépendants qui pourront être résolus en parallèle. Nous étudierons plusieurs variantes de ces trois approches très générales et leur utilité dans le cadre du problème de l'assimilation de données. Nous terminerons par l'application des méthodes de parallélisation précédentes au modèle de Shallow Water et comparerons leurs performances. Nous présenterons également une parallélisation du modèle météorologique ARPS (Advanced Regional Prediction System).

Nous avons tous l'intuition qu'un travail peut être réalisé en beaucoup moins de temps s'il est réparti entre plusieurs personnes ou sur plusieurs machines. Cette notion se nomme le parallélisme qui peut se définir comme l'état de ce qui se développe dans la même direction ou en même temps. C'est naturellement que la notion de parallélisme a été appliquée aux ordinateurs. De ce fait, il a été possible de répondre aux besoins de puissance nécessaire à la réalisation de projets gourmands en temps de calculs et en taille mémoire. Le parallélisme combiné à une algorithmique performante permet de gagner du temps afin de répondre au mieux à d'importants besoins. Il rompt avec l'approche classique qui consiste à gagner de la vitesse en effectuant plus rapidement chaque opération, approche bornée par les lois de la physique. La notion de parallélisme a donc grandement contribué à la multiplication des modèles informatiques. <br /><br />Nous nous intéresserons au modèle systolique et au modèle parallèle à gros grains baptisé (Coarse Grained Multicomputers). Le modèle CGM a été proposé par F. Dehne et al. et il possède des propriétés qui le rendent très intéressant d'un point de vue pratique. Il est parfaitement adapté à la modélisation des architectures existantes pour lesquelles le nombre de processeurs peut être de plusieurs milliers et la taille des données peut atteindre plusieurs milliards d'octets. Un algorithme développé pour ce modèle est constitué de calculs locaux utilisant, si possible, des algorithmes séquentiels optimaux et de rondes de communication dont le nombre doit être indépendant de la taille des données à traiter. Le modèle CGM est donc très intéressant d'un point de vue économique. En effet, ce modèle est indépendant des architectures réelles et permet de réutiliser des algorithmes séquentiels efficaces, ce qui le rend très portable. <br /><br />Dans cette thèse nous nous intéressons à des problèmes d'algorithmique du texte. Ces problèmes peuvent améliorer la compression de données ou bien être utilisés en bio-informatique. Ainsi, nous proposons des solutions CGM aux problèmes de recherche de la plus longue sous-suite croissante, de la plus longue sous-suite commune à deux mots, du plus long suffixe répété en chaque caractère d'un mot et de répétitions. Pour cela, nous sommes partis de solutions systoliques existantes que nous avons adaptées au modèle CGM. Le but de ce travail est en fait double. D'une part, nous proposons pour la première fois des solutions CGM à ces quatre problèmes. D'autre part, nous montrons comment des solutions systoliques peuvent être dérivées en algorithmes CGM. En effet, de nombreux problèmes ont été étudiés sur des architectures systoliques, c'est à dire des machines dédiées, non réutilisables pour d'autres problèmes. Le modèle CGM quant à lui permet de travailler avec des machines peu coûteuses et réutilisables à souhaits. De plus, l'expérience acquise au cours de ces travaux nous permet d'avoir une bonne idée des solutions systoliques adaptables au modèle CGM. Ceci pourrait permettre de consolider le pont existant entre modèles à grains fins et modèles à gros grains. <br /><br />Nous finissons cette thèse par une discussion sur l'équilibrage de charge des solutions proposées et sur la prédictivité de l'adaptation d'autres solutions systoliques au modèle CGM.

Nous présentons les bases de Grobner, leur utilisation et la parallélisation des algorithmes qui les calculent dans le cas de polynômes booléens. Une première partie est consacrée à la présentation théorique des bases de Grobner dans le cas général. Cette présentation se veut accessible a des non-spécialistes. Une étude bibliographique de la complexité est faite. Une deuxième partie concerne les applications des bases de Grobner booléennes en calcul propositionnel et en preuve de circuits combinatoires. Nous proposons un algorithme de preuve formelle de circuits combinatoires hiérarchisés. Dans la troisième partie nous adaptons l'algorithme séquentiel au cas booléen et nous étudions plus en détail la normalisation. Nous proposons deux méthodes de parallélisation a granularité différentes. Nous analysons et comparons plusieurs implantations parallèles et présentons des résultats expérimentaux. Les algorithmes sont généralisables au cas des polynômes a coefficients rationnels. Nous soulignons l'influence de la répartition des données sur le temps d'exécution. Nous présentons une methode de répartition des polynômes basée sur la recherche de chemins de longueur donnée dans un graphe oriente. Cette répartition nous permet d'obtenir des résultats interpretables et de conclure sur les différents algorithmes

Présentation d'une méthodologie de simulation du fonctionnement logique du coprocesseur arithmétique FELIN. Étude des méthodes de Durand-Kerner et d'Ehrlich pour la recherche simultanée de toutes les racines d'un polynôme à coefficients complexes. Elles sont ensuite comparées à cinq variantes algorithmiques. Une étude comparative est proposée. L'étude expérimentale de ces différentes méthodes est menée sur une architecture vectorielle

Les travaux présentés dans cette thèse concernent l'ordonnancement<br />pour les plates-formes hétérogènes à grande échelle. Nous nous<br />intéressons principalement aux opérations de communications<br />collectives comme la diffusion de données, la distribution de données<br />ou la réduction. Nous étudions ces problèmes dans le cadre de leur<br />régime permanent, en optimisant le débit d'une série d'opérations de<br />communications, en vue d'obtenir un ordonnancement asymptotiquement<br />optimal du point de vue du temps d'exécution total. Après avoir<br />présenté un cadre général d'étude qui nous permet de connaître la<br />complexité du problème pour chaque primitive, nous développons, pour<br />le modèle de communication un-port bidirectionnel, une méthode de<br />résolution pratique fondée sur la résolution d'un programme linéaire<br />en rationnels. Cette étude du régime permanent est illustrée par des<br />expérimentations sur Grid5000 et se prolonge vers l'ordonnancement<br />d'applications multiples sur des grilles de calcul.

Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.

Différents résultats de complexité sont présentés pour les communications et le calcul sur des machines à mémoire distribuée. Les topologies concernées sont le réseau linéaire, l'anneau, la grille, l'hypercube et le réseau complet. Un réseau systolique est présenté pour l'algorithme de diagonalisation de Jordan. Une étude sur l'accélération et une étude de l'allocation des données sont formulées dans le contexte des mémoires distribuées

La SNCF utilise plusieurs engins spécialisés pour ausculter les fissures internes du rail. La fréquence d’auscultation de chaque rail est fonction du tonnage cumulé qui passe dessus. La programmation des engins d’auscultations ultrasonores est aujourd’hui décentralisée. Dans le cadre d’une étude de réorganisation, la SNCF souhaite étudier la faisabilité de l’optimisation de certaines tournées d’inspection. Dans le cadre de cette thèse de doctorat, l’optimisation de la programmation des engins d’auscultation à ultrasons est étudiée.Une modélisation mathématique sous forme de problème de tournées sur arcs généralisant plusieurs problèmes académiques est proposées. Une méthode de résolution exacte, appliquant la décomposition de Benders, est détaillée. À partir de cette approche, une heuristique de génération de colonnes et de contraintes est présentée et analysée numériquement sur des données réelles de 2009. Enfin, un logiciel industriel développé autour de cette approche est présenté / SNCF is using specialised rolling stock units to inspect internal defects in rails. Rail’s inspection frequency is defined by the cumulative weight of the trains which are going through. In2009, the scheduling of these train units is decentralised. SNCF is studying the centralisation of this process. In this Ph.D. thesis, a new problem, the Railroad Track Inspection SchedulingProblem is studied.A mathematical formulation, based on the generalization of classical arc routing models,is proposed. An exact solving approach, based on Benders’ decomposition scheme, is detailed.From this approach, a column and cut generation heuristic is developed, implemented, andtested on real datasets for 2009. The industrial software developed around this heuristic is presented.