Nous nous intéressons dans cette thèse à des problèmes d'optimisation liés au domaine des réseaux. Ces problèmes sont d'une part des problèmes d'optimisation ``classiques'' dans lesquels nous cherchons à pallier la NP-difficulté d'un problème en proposant des algorithmes approchés, le plus souvent avec garantie de performance. D'autre part, nous avons considéré des problèmes dans lesquels les utisateurs du réseau sont indépendants et individualistes. Chaque utilisateur souhaite alors optimiser sa propre fonction objectif, qui peut être très différente de la fonction objectif globale que, en tant que concepteurs d'un protocole, nous souhaitons optimiser. Nous nous plaçons alors dans le cadre de la théorie des jeux algorithmique et cherchons à optimiser cette fonction objectif globale en prenant en compte des contraintes supplémentaires dues au fait que les utilisateurs se comportent de façon individualiste. Les problémes que nous avons considérés sont des problémes d'ordonnancement et de routage.

Lors du développement d'un système contrôlé par ordinateur, il y a traditionnellement une séparation forte entre les conceptions de la loi de commande et de l'ordonnancement des tâches du calculateur. Dans les systèmes embarqués, où les ressources sont limitées et variables, cette séparation rigide conduit à une sous utilisation du processeur. Pour améliorer l'interaction commande/ordonnancement, nous proposons d'adapter les ressources nécessaires au calcul des lois de commande en agissant sur leur période. Nous présentons tout d'abord une structure d'ordonnancement régulé. La contribution principale concerne ensuite le développement d'une méthodologie de synthèse d'une loi de commande à période d'échantillonnage variable basée sur une approche de type Hinfini dédiée aux systèmes linéaires à paramètres variants. Les performances de cette loi de commande ainsi que son interaction avec l'ordonnancement sont illustrées en simulation et sur un procédé expérimental.

Ces travaux portent sur la validation de modèles de systèmes sur puce (SoC) au niveau transactionnel (TLM). Ces modèles servent notamment au développement du logiciel embarqué. Le matériel est intrinsèquement parallèle mais le simulateur utilise un seul processeur. Les principales entités parallèles du matériel (processeurs, DMA, arbitres de bus, ...) sont représentées en TLM par des processus asynchrones, qui doivent être ordonnancés lors des simulations. Cet ordonnancement est indéterministe afin de mieux représenter le parallélisme physique.<br /><br />Cela pose un problème pour la validation par simulations : il faut couvrir l'espace des ordonnancements en plus de celui des données. En effet, un ordonnanceur déterministe peut cacher des erreurs, car il ne montre qu'un comportement parmi d'autres. Des ordonnancements aléatoires permettent d'observer plus de comportements mais la couverture est incertaine. Un parcours exhaustif de tous les ordonnancements serait beaucoup trop long pour des tests réels.<br /><br />Nous présentons une solution pour couvrir efficacement l'espace des ordonnancements. Celle-ci est basée sur de la réduction d'ordre partiel dynamique. L'idée est d'observer l'influence de l'ordonnancement sur les communications entre processus, pour générer dynamiquement de nouveaux ordonnancements, menant très probablement à des états finaux différents. En itérant sur chaque nouvel ordonnancement, nous obtenons un jeu complet d'ordonnancements, qui garantit la détection, pour un jeu fixé de données, de toutes les erreurs locales et de tous les inter-blocages.<br /><br />Toujours avec l'objectif d'une meilleure représentativité du matériel, les développeurs ont ajouté du temps imprécis à leurs modèles TLM, sous forme de délais bornés. Pour la validation par simulations, cela oblige à couvrir aussi l'espace des temporisations. Nous présentons une extension à la réduction d'ordre partiel dynamique pour résoudre ce problème. Le nouvel algorithme et son prototype retournent un ensemble de jeux de durées, qui garantit de nouveau la détection complète des erreurs locales et inter-blocages pour des données fixées.<br /><br />Enfin, nous étudions comment paralléliser le simulateur SystemC afin de profiter des machines multiprocesseurs, tout en respectant la spécification de SystemC et les particularités des modèles TLM.

La complexité des applications numériques de calcul scientifique ne cesse de croître. Cette difficulté revêt alors deux formes. La première est une complexité logicielle qui nécessite l'intégration de divers codes de calcul toujours plus sophistiqués et spécialisés à la simulation de phénomènes physiques complexes. La seconde forme de complexité est calculatoire où les composants de calcul nécessitent toujours plus de ressources et de capacité de stockage afin de modéliser, entre autres, les phénomènes au plus proche de la physique « réelle ».<br /><br />Dans le domaine de la simulation des procédés assistée par ordinateur, la complexité logicielle est masquée par le standard CAPE-OPEN qui répond aux besoins d'intégration de codes tiers. Il propose des spécifications d'interfaces, basées sur une approche par composants logiciels tels que DCOM ou CORBA. Cette thèse apporte une solution à la complexité calculatoire. Pour cela, nous étudions le problème de la distribution de la charge de calcul des simulations des procédés sur des architectures de type grappe de calcul dont les composants sont au standard CAPE-OPEN. Une exécution distribuée performante requiert la distribution des activités concurrentes de l'application tout en minimisant le volume de données à échanger via le support de communication.<br /><br />Dans ce contexte, nous présentons une analyse fine du schéma d'exécution des simulations de procédés qui conduit à la conception de deux environnements distribués d'exécution. Le premier nous a permis de quantifier le gain atteignable sur une grappe de calcul à travers la simulation de plusieurs cas tests métier. Toutefois, les contraintes technologiques industrielles se sont avérées peu propices à l'implémentation d'un environnement distribué visant à s'approcher de l'optimal. Par conséquent, la définition d'un second prototype basé sur le moteur exécutif KAAPI a été mené à bien. Afin de répondre à nos besoins, nous l'avons étendu aux techniques « statiques » d'exécution. Fort de cet environnement, nous avons entrepris d'étudier différentes politiques d'ordonnancement. L'environnement KAAPI couplé à notre extension ouvre de larges perspectives d'études dans le cadre plus large des applications numériques de calcul scientifique.

L'objet de cette thèse est l'étude d'un problème d'ordonnancement, dont le critère d'optimisation est la minimisation du nombre total de changements d'outils sur une machine flexible. Différents problèmes liés à l'outillage et pouvant constituer un obstacle au fonctionnement d'un atelier flexible sont brièvement examinés, (de la gestion de l'inventaire aux changements d'outils). Nous nous concentrons ensuite sur le problème d'ordonnancement avec gestion d'outils sur une seule machine: ce problème est NP-complet. Un premier aspect qui est la gestion off-line des outils est étudié: différents modèles sont proposés pour la minimisation des changements en fonction d'une séquence des tâches donnée. Dans ce cas, le problème est polynomial. Nous revenons ensuite au problème d'ordonnancement proprement dit, pour lequel plusieurs types de méthodes heuristiques sont décrites et comparées. La seconde partie du travail est consacrée à la gestion on-line des changements d'outils; elle se compose de deux chapitres: dans le premier, le modèle que nous allons utiliser est décrit en détail. Il s'agit de la modélisation des problèmes de k-serveurs. Le principe peut être résumé comme suit: sur un réseau de n clients potentiels, on dispose de k serveurs mobiles, avec lesquels on doit répondre on-line aux demandes unitaires et successives des clients, tout en optimisant les déplacements des serveurs. Ce problème est en étroite relation avec la gestion des mémoires en informatique. Dans le dernier chapitre, le modèle des k-serveurs «classique» est généralisé aux problèmes avec service par blocs de demandes, ce qui permet d'adapter l'algorithme de partitionnement, (fortement compétitif pour le service unitaire), au cas plus général des demandes groupées. Cet algorithme dont nous étudions les propriétés et la compétitivité est applicable à la gestion on-line des changements d'outils. Il sert de base à la construction d'une heuristique d'ordonnancement avec gestion d'outils. Cette dernière méthode se révèle très efficace comparée aux précédentes

Le projet CASCADE a pour objet l'étude et le développement d'un système intégré de CAO pour les circuits et systèmes logiques. Ce système comprend en particulier, et c'est le contexte de ce travail, un simulateur basé sur un langage de description multi-niveaux. Nous présentons d'abord une partie du travail réalisé : les mécanismes d'ordonnancement statique qui facilitent le séquencement de la simulation. Puis nous expliquons les mécanismes de simulations permettant de simuler un modèle hiérarchisé à l'aide de différents «modes de simulation». Ces mécanismes sont la base du simulateur multi-modes actuellement en fonctionnement au laboratoire ARTEMIS

Étude d'un modèle mathématique pour formaliser le comportement des systèmes parallèles et temps réel, à des fins de spécification de problèmes, de description, d'analyse et de preuve de réalisations. Construction, à partir des mêmes notions, d'un calcul formel conduisant à des méthodes systématiques d'analyse de systèmes logiques temporisés, au niveau algorithmique

En informatique, la notion de processus léger ou thread est désormais omniprésente. En effet, les threads permettent à un programme d'une part d'exploiter pleinement les ordinateurs multiprocesseurs et d'autre part d'exprimer son parallélisme intrinsèque. Dans le domaine du calcul hautes performances, les threads permettent de recouvrir des communications ou plus généralement des entrées/sorties avec du calcul. Ils permettent aussi aux divers composants de l'application de progresser indépendamment les uns des autres, ce qui est nécessaire avec l'utilisation d'environnements de programmation toujours plus complexes comme MPI ou Corba.<br /><br />Mes travaux avaient pour objectif principal d'aboutir à la conception d'une bibliothèque de threads performante sur une vaste gamme d'architectures (machines mono ou multiprocesseurs, technologie "multithreading simultané", ...) et capable d'offrir les fonctionnalités demandées par les programmes de calcul hautes performances. Dans un premier temps, j'ai proposé une extension du modèle des Scheduler Activations pour le noyau Linux permettant d'être réactif aux interruptions dans une bibliothèque de threads utilisateurs. J'ai ensuite étendu ce mécanisme de manière à unifier la gestion des interruptions et des scrutations dans un environnement multithreadé. Enfin, j'ai proposé un mécanisme de prise de traces permettant de reconstituer précisément le déroulement d'un programme multithreadé, y compris lorsque l'ordonnancement est à deux niveaux.<br /><br />Ces travaux ont été implémentés au sein du logiciel PM2. La bibliothèque Marcel offre des threads performants sur une vaste gamme de processeurs et de systèmes en restant suffisamment flexible pour permettre aux applications qui le nécessitent de diriger précisément l'ordonnancement de leurs threads. Les applications peuvent être tracées de manière à pouvoir reconstituer et observer leur comportement précis. La trace obtenue peut être convertie au format du logiciel Pajé qui permet alors de visualiser graphiquement le déroulement de l'application.

Nous étudions des stratégies d'ordonnancement et d'équilibrage de charge pour des plates-formes hétérogènes distribuées. Notre problème est d'ordonnancer un ensemble de tâches indépendantes afin d'en réduire le temps total d'exécution. Ces tâches utilisent des données d'entrée qui peuvent être partagées : chaque tâche peut utiliser plusieurs données, et chaque donnée peut être utilisée par plusieurs tâches. Les tâches ont des durées d'exécution différentes, et les données ont des tailles différentes. Toute la difficulté est de réussir à placer sur un même processeur des tâches partageant des données, tout en conservant un bon équilibrage de la charge des différents processeurs. Notre étude comporte trois parties généralisant progressivement le problème. Nous nous limitons dans un premier temps au cas simple où il n'y a pas de partage de données, où les tailles des tâches et des données sont homogènes, et où la plate-forme est de type maître-esclave. Le partage des données est introduit dans la deuxième partie, ainsi que l'hétérogénéité pour les tailles des tâches et des données. Dans la dernière partie nous généralisons le modèle de plate-forme à un ensemble décentralisé de serveurs reliés entre eux par un réseau d'interconnexion quelconque. La complexité théorique du problème est étudiée. Pour les cas simples, des algorithmes calculant une solution optimale sont proposés, puis validés par des résultats expérimentaux avec une application scientifique réelle. Pour les cas plus complexes, nous proposons de nouvelles heuristiques pour résoudre le problème d'ordonnancement. Ces nouvelles heuristiques, ainsi que des heuristiques classiques comme min-min et sufferage, sont comparées entre elles à l'aide de nombreuses simulations. Nous montrons ainsi que nos nouvelles heuristiques réussissent à obtenir des performances aussi bonnes que les heuristiques classiques, tout en ayant une complexité algorithmique d'un ordre de grandeur plus faible.

Dans cette thèse, notre objectif est de présenter une nouvelle approche de résolution pour des problèmes d'ordonnancement de type job-shop. Les problèmes traités sont de grande taille, ce qui, du fait de la complexité du problème, ne permet d'envisager que l'utilisation d'heuristiques. Cette approche propose une alternative aux algorithmes basés sur des règles de priorité, généralement utilisés. Le principe de l'approche est de construire une succession d'ordonnancements partiels, en agrégeant les jobs les uns après les autres. L'agrégation consiste à insérer toutes les opérations du job à agréger sans changer l'ordre des opérations dans l'ordonnancement partiel précédent. Dans un premier temps, des méthodes issues de l'approche sont proposées pour résoudre le problème classique du job-shop. Ensuite, ces méthodes sont étendues pour traiter des problèmes de job-shop généralisé, ou l'affectation des opérations aux machines n'est pas fixée au départ. Pour finir, des problèmes de job-shop dynamiques et réactifs sont abordés. Dans ceux-ci, l'arrivée aléatoire de jobs et l'arrêt de machines sont pris en compte. Les méthodes agrégatives sont particulièrement bien adaptées à la résolution de ce type de problème.