L'évolution constante des processeurs vers des architectures proposant des capacités superscalaires, de parallélisme au niveau des instructions, de prédiction, de spéculation et la multiplication des niveaux de hiérarchie mémoire donnent de plus en plus d'importance au travail du compilateur.<br />Dans cette thèse, nous nous intéressons aux transformations du programme source destinées à l'optimisation dans la chaîne de compilation, et plus particulièrement à une transformation appelée décalage d'instructions.<br />Cette transformation sert de base au pipeline logiciel, elle a une influence sur le parallélisme au niveau des instructions et l'utilisation des registres.<br />Elle intervient également comme composante des techniques de parallélisation de boucles par ordonnancement affine.<br />Nous avons voulu mieux comprendre les perspectives offertes par le décalage d'instructions, savoir quels objectifs il permettait d'atteindre mais aussi savoir quels problèmes de décalage restaient difficiles.<br />Pour cela nous avons étudié le décalage d'instructions dans plusieurs contextes plus ou moins proches, et apporté des contributions à chacun d'entre eux.<br /><br />Dans le cadre du pipeline logiciel, nous proposons un algorithme polynomial pour déterminer le décalage le plus à même de produire un maximum de parallélisme au niveau des instructions, et une étude expérimentale de l'efficacité absolue de la technique à l'aide de l'outil logiciel que nous avons réalisé dans ce but : PASTAGA (pour Plate-forme d'Analyse Statistique et de Tests d'Algorithmes sur Graphes Aléatoires).<br />Dans le cadre de l'utilisation des registres (stage scheduling), de la parallélisation de boucle et de la localité, nous apportons des réponses aux problèmes de décalage d'instructions associés~: complexité, solutions exactes, approximations.

Après un état de l'art sur l'ordonnancement en général et l'ordonnancement temps réel en particulier permetttant de préciser les notions utilisées par la suite et après avoir motivé l'intérêt d'une nouvelle contrainte temps réel de latence, nous proposons un modèle qui formalise les systèmes temps réel avec contraintes de précédences, de périodicités et de latences. Dans ce modèle, les précédences sont définies par un graphe orienté acyclique infiniment répété. Pour le cas monoprocesseur, on étudie trois problèmes d'ordonnancement : celui des systèmes avec contraintes de précédences et de périodicités, celui des systèmes avec contraintes de précédences et de latences et enfin celui des systèmes avec contraintes de précédences, de périodicités et de latences. Pour chaque problème on étudie la cohérence entre les différentes contraintes, on donne des conditions d'ordonnançabilité et on propose un algorithme prouvé optimal dans le sens où s'il y a un ordonnancement, l'algorithme le trouvera. On passe ensuite au cas multiprocesseur où l'architecture est définie par un graphe non-orienté. On étudie trois problèmes d'implantation (distribution et ordonnancement) dans les mêmes cas qu'en monoprocesseur en tenant compte des temps de communications. On prouve que ces trois problèmes sont NP-difficiles et on propose, donc, des heuristiques. Les performances de chaque heuristique sont comparées à celles d'algorithme exacte de type "branch and bound", en utilisant des simulations numériques.

L'évolution des besoins des logiciels entraîne la croissance de la complexité des environnements répartis. La recherche effectuée dans le domaine de la conception de ces environnements vise à réduire cette complexité. Un des principaux problèmes de la conception des infrastructures réparties concerne la composition des propriétés non fonctionnelles (également appelées services techniques). Les services interagissent entre eux. Nous avons identifié deux types d'interaction : les interactions de type structurel et les interactions de type comportemental.<br />Il existe actuellement de nombreuses approches (académiques et industrielles) qui permettent de concevoir ces infrastructures.<br />Dans un premier temps, nous exposons les concepts de la composition et nous étudions les mécanismes de composition mis en oeuvre dans ces approches de conception.<br />A partir de cette étude, nous proposons une nouvelle approche de composition appelée composition comportementale qui permet de supprimer un certain nombre de limites identifiées dans les autres approches. L'approche de composition comportementale utilise le modèle de composants Fractal et introduit un modèle d'automates qui permet de décrire les comportements des composants.<br />Les interactions de type structurel s'expriment à partir du modèle de composants et se matérialisent par des liaisons entre les interfaces des composants. Les interactions de type comportemental s'expriment à partir du modèle d'automate et se matérialisent par des contraintes d'ordonnancement. Les mécanismes de composition de notre approche mettent en oeuvre ces différents types d'interaction.<br />Nous avons réalisé un canevas logiciel qui implante le modèle de composant et le modèle de comportement. Le canevas a été conçu afin que les approches de conception puisse l'utiliser. L'implantation du canevas génère un environnement d'exécution basé sur le langage synchrone réactif Esterel.<br />Pour conclure, nous positionnons notre approche avec les autres approches de conception à partir de critères d'évaluation que nous avons définis. Quelques perspectives concernant l'approche sont données.

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.

Cette thèse aborde le problème de la résolution des problèmes combinatoires à l'aide d'algorithmes génétiques. Ce type d'algorithme présente en effet nombres d'avantages. Cependant, ils sont généralement relativement lents. Cette thèse est donc centrée sur les algorithmes hybrides, c'est-à-dire des algorithmes construits à l'aide de plusieurs méthodes différentes. Dans notre cas, nous étudions les algorithmes qui réunissent algorithmes génétiques et heuristiques. Il existe deux méthodes pour générer de tels algorithmes qui sont la représentation directe et la représentation indirecte. Ces deux méthodes sont étudiés au travers de trois problèmes distincts : l'ordonnancement statique de programmes parallèles, le placement de composants électroniques et la planification de réseaux cellulaires. Pour chacun des trois problèmes, les algorithmes hybrides ont montrés leur efficacité. Pour le problème de la planification de réseaux cellulaires, une nouvelle modélisation a été faite. Cette modélisation permet d'effectuer en même temps le placement des émetteurs et l'allocation de fréquences.

Dans cette thèse, les mécanismes d'implantation efficace d'algorithmes d'ordonnancement dans des langages de programmation parallèle de haut niveau sont étudiés. Ces mécanismes sont basés sur les principes de dégénération séquentielle et distribuée. La dégénération séquentielle consiste à optimiser les coûts de création de tâches lorsqu'il n'est pas nécessaire de générer plus de parallélisme. La dégénération distribuée consiste à générer automatiquement une exécution distribuée aussi proche que possible de celle du programme équivalent écrit avec une bibliothèque de communication de type MPI. Dans l'objectif de proposer un couplage efficace de ces deux mécanismes, plusieurs protocoles de cohérence mémoire permettant d'implanter des couches de mémoire partagée distribuée sont comparés. Cette étude permet de valider l'efficacité du protocole "flot de données" que nous proposons lorsque le nombre de tâches déplacées lors de l'exécution du programme est faible. Un mécanisme de pile distribuée permettant l'implantation de ce protocole est proposé. Il est basé sur une gestion efficace du flot de données couplé avec un mécanisme d'allocation performant. Ces mécanismes sont finalement implantés dans le langage Athapascan et validés pour des applications de simulation et d'optimisation combintoire.

Ce travail propose une approche originale pour l'ordonnancement de tâches sous contraintes de temps et de ressources. Les méthodes et techniques développées s'inscrivent dans la problématique de l'"Analyse Sous Contraintes" (A.S.C.) des problèmes d'ordonnancement. Cette A.S.C. vise à caractériser les ordonnancements admissibles de manière à proposer au décideur un choix d'actions cohérentes vis-à-vis des contraintes, tout en lui offrant une certaine flexibilité face à des aléas éventuels. L'A.S.C. est décrite comme un processus d'inférence mettant en interaction une base de règles et une base de faits temporels et séquentiels représentant les caractéristiques des ordonnancements admissibles. Un logiciel (MASCOT) écrit en Prolog-II a été réalisé selon ce principe. Une nouvelle approche pour l'A.S.C. et plus particulièrement pour le raisonnement temporel sous contraintes de ressources a été développée. L'originalité de cette approche réside essentiellement dans la prise en compte du couplage temps/ressource à l'aide du concept d'intervalle temps-ressource qui conduit à utiliser un raisonnement énergétique. L'intervalle temps-ressource permet de représenter à la fois les tâches ou intervalles consommateurs et les intervalles de temps alloués sur lesquels des ressources sont disponibles, appelés intervalles fournisseurs. Le problème de l'ordonnancement de tâches amène à étudier l'interaction entre intervalles consommateurs et fournisseurs sur la base de considérations énergétiques. Le logiciel MASCOT met en jeu un processus de déduction symbolique. Ce type de déduction a été amélioré par la prise en compte de l'énergie obligatoirement consommée ou consommation obligatoire d'intervalles consommateurs sur un intervalle fournisseur. De nouvelles règles de déduction ont été écrites et intégrées dans MASCOT. D'autre part, un processus de déduction basé sur un raisonnement purement énergétique a été élaboré et implémenté (logiciel REPORT) en Prolog-II. Il utilise un autre type de déduction, la déduction numérique, qui permet d'affiner les bornes temporelles d'un intervalle fournisseur en considérant la consommation obligatoire des autres intervalles consommateurs. En d'autres termes, ces résultats consistent à actualiser des dates limites et correspondent à des conditions nécessaires d'admissibilité ; ils permettent ainsi de détecter des infaisabilités éventuelles. L'outil de modélisation utilisé est le graphe potentiels-bornes qui permet de représenter des contraintes numériques (sur la durée des tâches par exemple) et des contraintes symboliques entre intervalles. Il sert de support à un processus d'inférence par propagation numérique des contraintes.

Les problèmes d'ordonnancement constituent une classe importante des problèmes d'optimisation combinatoire. La plupart des travaux dans ce domaine considèrent des problèmes statiques pour lesquels toutes les données (activités, ressources, contraintes) sont connues à l'avance. En réalité, ce type de problèmes est très souvent soumis aux aléas (matières premières livrées en retard, arrivées de nouvelles commandes, pannes de machines, etc.). Aussi, l'ordonnancement se déroule rarement comme prévu. On a alors affaire à un problème d'ordonnancement dit dynamique. Dans cette thèse, nous considérons un problème d'ordonnancement très général, appelé RCPSP (Resource Constrained Project Scheduling Problem), et proposons un système permettant de résoudre le cas dynamique. Bien que beaucoup de travaux concernent le RCPSP statique, seules quelques méthodes sont proposées pour le cas dynamique. De plus ces méthodes ne sont pas satisfaisantes. La méthode que nous proposons applique au RCPSP une des techniques utilisées pour résoudre les problèmes de satisfaction de contraintes dynamiques : les explications. Une explication est un ensemble de contraintes (un sous-ensemble du système de contraintes courant) qui justifie le résultat de la recherche (déduction de nouvelles contraintes, contradiction aboutissant à un échec, etc.). Ces explications sont une trace explicite du comportement de la propagation. Elles permettent de défaire efficacement les effets passés d'une contrainte et ainsi d'ajouter et retirer dynamiquement des contraintes. Nous avons ainsi développé une recherche arborescente (inspirée d'une recherche arborescente de la littérature) qui en chaque noeud propage les contraintes temporelles et de ressources (en utilisant les techniques de core-times, task-interval et resource-histogram) tout en conservant des explications. Nous utilisons de plus une notion de distance (écart entre la fin d'une activité et le début d'une autre) permettant d'exprimer toutes les contraintes temporelles dans un cadre unique. Notre système est ainsi capable de résoudre de manière efficace (i.e. sans repartir à zéro et dans un temps raisonnable) des instances de RCPSP dynamiques (i.e. ajouts/retraits de contraintes de précédence, ajouts/retraits d'activités et de ressources). De plus, notre système étant très générique, il permet de traiter des extensions du RCPSP dynamique (précédences/disjonctions/chevauchements généralises, et variation des disponibilités des ressources).

En quelques dizaines d'années, l'informatique a vu naître et se développer des machines fonctionnant avec plusieurs processeurs. Les difficultés techniques rencontrées pour la conception de ces ordinateurs ont été surmontées et l'un des défis majeur d'aujourd'hui est de fournir une plateforme pour la programmation parallèle. Ce travail de thèse s'inscrit dans le cadre du projet IMAG APACHE qui a pour but la conception d'un tel environnement. Le modèle de graphes que nous manipulons est un graphe de tâches orienté sans cycle. Le processus consistant à paralléliser une application est découpé en trois phases principales, avec l'ordonnancement et le placement des différentes parties de l'application comme étape centrale. Dans ce contexte, nous avons concentrés nos efforts sur la recherche de stratégies d'ordonnancement présentant de réelles qualités de robustesse et d'efficacité pour des graphes de différentes granularités, et pour des ensembles d'hypothèses d'exécution différents. A partir d'un algorithme produisant des ordonnancements optimaux dans le cas de graphes à structure arborescente formés de tàches de durées unitaires et de communications unitaires, nous avons montré qu'il était possible d'obtenir des ordonnancements, dont l'écart par rapport à l'optimal est borné, pour des arbres de granularité différente. Nous avons montré également que ce même algorithme permettait d'obtenir dans certains cas des ordonnancements optimaux pour un modèle d'exécution totalement différent de celui pour lequel il avait été originellement conçu. Cette étude sur deux processeurs a été mené pour un nombre supérieur de processeurs identiques et pour deux processeurs uniformes. Enfin, une partie de ce travail est dédiée à la recherche de stratégies d'ordonnancement pour des graphes générés par l'environnement Athapascan (projet APACHE) qui présentent la particularité de permettre l'adaptation de la granularité en fonction de la machine cible.