Nous présentons dans cette thèse une étude sur des<br />algorithmes distribués asynchrones et déterministes de<br />contröle. Un système distribué consiste en un réseau<br />de sites (processeurs, ordinateurs ou réseaux locaux). Dans cette<br />thèse, nous ne considérons que des réseaux de sites<br />communicants n'ayant ni mémoire partagée ni horloge globale.<br />De nombreux problèmes de l'algorithmique distribuée sont<br />réductibles à la construction d'un Arbre Couvrant qui est la<br />structure de contrôle qui nous intéresse.<br /><br />Nous étudions deux types d'algorithmes~: ceux utilisant<br />la notion de phase logique et les autres qui ne considèrent aucun<br />mécanisme de synchronisation. Ces derniers ont des comportements<br />imprévisibles améliorant la tolérance aux fautes. Nous<br />présentons un nouvel algorithme de ce type associé à une<br />élection qui n'est pas une recherche d'extremum contrairement<br />à l'usage. Cet algorithme est comparable au meilleur<br />algorithme connu qui utilise des jetons et des phases logiques<br />induisant un comportement plus "séquentiel".<br /><br />D'autres algorithmes, construisant des AC contraints, sont<br />considérés. En particulier l'AC de Diamètre Minimum qui<br />est, à notre connaissance, un problème qui n'a jamais<br />été étudié dans ce domaine. Le diamètre d'un<br />graphe est la somme des poids des arêtes du plus long des plus<br />courts chemins. Si nous considérons la complexité temporelle,<br />cette contrainte est d'un intérêt &vident. Nous proposons<br />différents algorithmes suivant que la tolérance aux fautes est<br />nécessaire ou non.<br /><br />Finalement, l'étude pratique des algorithmes distribués sur<br />des réseaux de grande taille nous a conduit à la construction<br />d'un simulateur. Il permet l'exécution d'un même code source<br />sur des machines séquentielles ou parallèles.

L'idée de mettre en place un simulateur relativement général de la partie mécanique de l'usinage à l'échelle macroscopique est à l'origine de ce travail. <br />Le principal apport de ce travail est la prise en compte de pièces dont la zone concernée par l'usinage est flexible. Cette présence de déformations dans la pièce a nécessité une définition précise de l'enlèvement de matière. Cette définition se fonde sur une configuration dite matérielle, où la réalisation pratique de la simulation de l'usinage est effectuée. <br />Par ailleurs, les pièces flexibles étant généralement très minces, l'enlèvement de matière peut modifier de façon significative le comportement dynamique de la pièce (perte de masse et de raideur). Pour être fidèle, une simulation doit alors prendre en compte cette modification de façon régulière en cours d'usinage. Nous montrons que cette prise en compte ne peut dans certains cas être évitée, et nous proposons une stratégie limitant les coûts numériques induits par cette prise en compte. <br />Un autre apport du travail réalisé est l'utilisation d'un modèle géométrique différent de celui des approches précédentes du LMSP, pour représenter le volume occupé par la pièce. Avec le modèle géométrique de la pièce retenu dans les travaux précédents du LMSP (modèle B-Rep analogue aux modèles utilisés en CAO), de très nombreuses intersections de polyèdres conduisent à des facettes "dégénérées" dont la prise en compte dans les algorithmes d'intersection est loin d'être triviale et constitue actuellement un des points bloquants pour ce qui concerne la robustesse. La nouvelle technique adoptée est celle des Z-buffer où la pièce est modélisée par des dexels (ensemble de « bâtonnets » disposés sur une matrice régulière). Cette description permet de simplifier sensiblement les algorithmes d'intersection tout en les rendant plus robustes. Cette nouvelle description nous a conduit à revoir la démarche de modélisation de l'interaction outil/pièce et notamment la démarche de calcul des efforts de coupe. Cette modélisation s'intègre dans le logiciel Nessy du LMSP. Par les résultats obtenus, nous démontrons la faisabilité de notre approche et son potentiel d'analyse.

Dans ce mémoire, nous étudions les méthodes itératives de recherche dans le cadre de la résolution du problème d'ordonnancement de type jobshop<br /><br />Plus que les performances en elles-mêmes, nous nous intéressons tout particulièrement à la compréhension du fonctionnement des méthodes de résolution ainsi qu'à l'analyse de l'influence de la coopération de plusieurs méthodes de recherche sur la qualité des solutions engendrées.<br /> <br />Dans un premier temps, nous évaluons l'apport de critères secondaires intégrés dans la fonction coût. Nous utilisons des algorithmes itératifs de recherche pour étudier l'impact de l'intégration de ces critères sur le paysage adaptatif ainsi que sur la qualité des ordonnancements engendrés.<br /><br />Nous proposons ensuite quelques améliorations du schéma d'application des opérateurs dans les algorithmes génétiques. <br /><br />Finalement, nous étudions quelques modèles d'hybridation des méta-heuristiques basés sur la recherche tabou et les algorithmes évolutifs.

Les nouveaux supports d'exécution que sont les grilles de processeurs<br />apparaissent aujourd'hui comme une alternative économiquement viable aux grands systèmes de calcul centralisés. De grands projets nationaux comme GRID5000 sont basés sur ce concept de machines réparties. Ce changement du paysage du calcul parallèle haute performance a créé une nouvelle demande d'algorithmes spécifiques pour tirer le meilleur parti des ressources déployées. Pour concevoir ces algorithmes et démontrer leur efficacité, il faut s'appuyer sur des modèles qui tentent de décrire fidèlement le comportement réel des machines tout en restant suffisamment simples à manipuler. Dans cette thèse, nous avons étudié deux modèles parmi les plus importants pour ces nouveaux supports et nous avons fourni des algorithmes polynomiaux optimaux, des algorithmes d'approximations garantis, ou des preuves de NP-complètudes le cas échéant.

Le travail présenté dans cette thèse traite de l'extraction de connaissances à l'aide de métaheuristiques et de ses applications à des problématiques en génomique. Dans un premier temps, nous donnons un état de l'art des métaheuristiques utilisées pour l'extraction de connaissances et plus particulièrement de l'utilisation des algorithmes génétiques en orientant notre présentation sur trois aspects fondamentaux des métaheuristiques : la représentation d'une solution, la fonction d'évaluation et le choix des opérateurs. Nous présentons ensuite deux problématiques issues d'une collaboration avec l'Institut de Biologie de Lille autour de la recherche de facteurs génétiques de prédisposition à certaines maladies multifactorielles (diabète de type II, obésité). Nous proposons une modélisation de ces problèmes en problèmes d'extraction de connaissances. Nous traitons ensuite les différentes taches d'extraction de connaissances identifiées comme des problèmes d'optimisation et proposons un schéma d'algorithme génétique possédant des mécanismes avancés d'intensification et de diversification pour les résoudre. Les apports de ces mécanismes sont testés modulairement afin de montrer leurs performances. Nous intégrons également des connaissances du domaine biologique afin de répondre aux problématiques posées. Cette intégration s'effectue aussi bien au niveau des fonctions d'évaluation proposées qu'au niveau de certains mécanismes utilisés. Enfin, différents modèles de parallélisme sont utilisés.

Cette thèse présente ANDES, une technique de modélisation quantitative d'algorithmes et de programmes parallèles. Le modèle est un graphe orienté et valué sans circuit composé de noeuds de calcul. Les arcs modélisent la précédence. Par le moyen de logiques d'entrée et de sortie, il est possible de modéliser le flot de données. ANDES prévoit la modélisation de certaines caractéristiques non-déterministes des algorithmes (e.g. branchement). Un support pour la description hiérarchique et regulière est aussi prevu. Des exemples de modèles ANDES sont présentés. La description du modèle est faite à partir d'une étude des autres techniques disponibles dans la littérature (e.g., GMB). La bibliothèque ANDES-C est utilisé pour la description de modèles ANDES. Avec cette bibliothèque, un modèle ANDES est décrit comme un programme C. L'avantage de cette représentation textuelle est, entre autres, la possibilité de décrire, de façon compacte, de modèles avec de milliers de noeuds de calcul. Le modèle ANDES peut être utilisé dans différents contextes d'évaluation de performances, principalement comme une forme de modélisation d'une charge de travail. Ce modèle de la charge de travail peut être donné, par exemple, à un simulateur ou à un modèle analytique (e.g., un système de files d'attente). Dans ce travail, nous utilisons ANDES afin de générer, à partir des modèles, des charges synthétiques exécutées par une vraie machine parallèle. Cet environnement de transformation et d'exécution d'une charge synthétique est appelé ANDES-Synth. A part le modèle de la charge de travail, il est possible de modéliser aussi une machine parallèle qui est "émulée" par la machine parallèle cible. ANDES-Synth est utilisé, dans ce travail de thèse, pour l'évaluation de stratégies de placement statique (quatre heuristiques gloutonnes et deux itératives). Un algorithme de regroupement (utilisé dans l'outil Pyrros) est utilisé afin de permettre l'application des stratégies de placement aux modèles ANDES.

Le but de ce memoire est d'étudier les voies possibles pour minimiser le sur-coût des communications consécutif à la parallélisation d'algorithmes numériques sur machines parallèles à mémoire distribuée. La première voie explorée consiste à optimiser les schémas de communication des données et résultats mis en oeuvre dans les versions parallèles de noyaux de calcul. Nous proposons notamment de nouveaux algorithmes pour réaliser une transposition de matrices carrées allouées par blocs, sur différentes topologies de réseaux d'interconnexion. Nous avons également étudié le problème de l'échange total. Ce schéma de communication se retrouve fréquemment dans les versions parallèles d'algorithmes numériques (comme dans l'algorithme du gradient conjugué). Nous proposons des algorithmes efficaces d'échange total pour des topologies toriques. La deuxième voie qui a été explorée consiste à recouvrir les communications par du calcul. Nous avons étudié quelques principes algorithmiques de base permettant de masquer au mieux les communications. Ceux-ci sont basés, notamment, sur des techniques d'enchainement de phases de calcul et de communication, ainsi que sur le re-ordonnancement local de tâches afin d'optimiser le recouvrement. Ces techniques sont illustrées sur des algorithmes parallèles de calcul de transformée de Fourier. Les différentes implantations de ces algorithmes sur de nombreuses machines parallèles à mémoire distribuée (T3D de Cray, SP2 d'IBM, iPSC-860 et Paragon d'Intel) montrent le gain en temps d'exécution apporté par ces méthodes.

Cette thèse se concentre sur l'évaluation des performances des mécanismes d'équilibrage de charge. Pour l'utilisation efficace d'une architecture parallèle, il est nécessaire de développer des techniques de régulation de charge appropriées. Nous étudions en détail le problème de l'ordonnancement dynamique d'une application parallèle. Les fonctionnalités d'un ordonnanceur générique sont analysées et son implémentation dans le système Athapascan est décrit. Athapascan est un environnement de programmation pour les applications parallèles irrégulières. La structure de l'ordonnanceur permet l'implémentation de différents algorithmes d'équilibrage de charge. Pour étudier les différentes stratégies d'équilibrage et comparer leurs performances nous proposons une méthodologie. Nous avons construit des modèles de programmes synthétiques avec un caractère dynamique et aléatoire, à partir desquels nous avons établi un jeu d'essai. Nous avons choisi d'étudier les effets simultanés des différents paramètres des ordonnanceurs et de la charge synthétique. Une planification factorielle a été choisie parce qu'elle permet une vision globale de l'influence des différents paramètres. Les tests sont effectués sur une machine SP1-IBM. Deux méthodes d'analyse de données multivariée sont utilisées, l'analyse en composantes principales et la régression multiple. L'interprétation des modèles linéaires obtenus permet de comprendre le comportement de chaque ordonnanceur et l'influence de ses paramètres par rapport à la charge applicative.

Dans cette thèse, nous traitons de l'optimisation du taux de décroissance exponentielle uniforme de l'équation des ondes sur un domaine W mono ou bidimensionnel. L'amortissement se fait à l'aide d'un feedback en vitesse égal à une certaine constante k sur un sous domaine w. Ce taux de décroissance est lié à l'abscisse spectrale m de l'opérateur associé au problème et à une quantité géométrique g, introduite par Bardos, Lebeau et Rauch dans le cas bidimensionnel. On montre que l'abscisse spectrale est dérivable par rapport à k à l'origine, et on étudie cette dérivée J pour approximer m par le produit de k et J. Dans la première partie de la thèse, nous étudions de façon théorique les fonctionnelles J et g. Nous caractérisons les géométries optimales dans le cas d'un intervalle ou d'un carré pour des valeurs particulières de la contrainte d'aire. Dans le cas du carré, nous concevons un algorithme de calcul exact de la quantité géométrique dans le cas où w est un réunion de carrés basé sur un nouveau théorème d'interversion de limites. La seconde partie est dédiée à l'optimisation numérique des quantités J et g à l'aide de différents algorithmes génétiques. Les résultats obtenus ne sont pas intuitifs.

Ce travail concerne les fluides eulériens compressibles constitués de plusieurs espèces, qui peuvent être mélangées ou séparées par des interfaces. Le mémoire est composé de trois parties. La première partie est consacrée à la résolution numérique de problèmes modèles : équation d'advection, équation de Burgers, équations d'Euler, en dimensions un et deux. L'accent est mis sur la précision des méthodes (en particulier pour des données initiales discontinues), et des algorithmes non dissipatifs sont développés. Ils sont basés sur un décentrage aval des flux (de type volumes finis) sous des contraintes de stabilité. La seconde partie traite de la modélisation mathématique des mélanges de fluides. Nous y construisons et analysons une classe de modèles entropiques, symétrisables, hyperboliques, non forcément conservatifs. Ce sont des modèles à plusieurs températures et plusieurs pressions. Dans la troisième partie, nous utilisons les idées introduites dans la première partie (décentrage aval et schémas non dissipatifs) pour la résolution numérique des problèmes aux dérivées partielles construits dans la deuxième partie. Nous présentons des résultats numériques en dimensions un et deux.