Dans cette thèse, nous nous intéressons au calcul d'ordonnanceurs pour les systèmes hybrides. En fait, nous considérons deux sous-classes des systèmes hybrides, les systèmes temps-réels où des tâches doivent se partager l'accès à une ressource commune, et les systèmes à commutations où un choix doit être fait sur les dynamiques à choisir en fonction d'objectifs à atteindre. Dans la première partie de cette thèse, nous nous intéressons aux problèmes d'ordonnancement et prenons comme étude de cas l'ordonnancement de tâches périodiques sur des architectures multiprocesseurs. Nous nous intéressons plus particulièrement à déterminer si l'on peut modifier certaines valeur des paramètres du système tout en respectant les contraintes temporelles sans changer d'ordonnanceur. La méthode inverse permet de prouver de manière formelle la robustesse des systèmes temporisés paramétriques. Nous introduisons une méthode de réduction du nombre d'états nécessaire à la vérification. Cette réduction nous permet de traîter des études de cas intéressantes telle que celle proposée par Astrium EADS pour le lanceur Ariane 6. Nous montrons également comment la Cartographie Comportementale, une extension de la méthode inverse, permet de trouver la zone de l'espace des paramètres où l'on a l'existence d'un ordonnancement satisfaisant les contraintes temporelles. Nous comparons cette approche avec une méthode analytique pour montrer l'intérêt de notre approche. Dans la seconde partie de cette thèse, nous nous intéressons au contrôle de systèmes affines à commutation. Ces systèmes sont gouvernés par une famille d'équations différentielles linéaires et le contrôleur peut choisir laquelle va gouverner le système pendant le prochain pas de temps. Dans ce cadre, le contrôle peut être vu comme l'ordonnancement des dynamiques que le système va prendre. Le choix de la dynamique peut se faire pour des objectifs de stabilité ou d'accessibilité. Nous proposons une nouvelle méthode qui calcule un contrôleur dont la stratégie est la même pour des ensembles denses de points. Notre méthode utilise le calcul en avant, souvent préférable au calcul à rebours pour les systèmes contractants. Nous montrons que, sous certaines conditions, le système contrôlé évolue vers un comportement limite. Nous appliquons notre méthode sur plusieurs études de cas issues de la littérature ainsi qu'un exemple réel, un prototype de convertisseur de tension multiniveaux. Enfin, nous montrons que notre méthode s'étend aux systèmes comportant des perturbations ainsi qu'aux systèmes non linéaires. / In this thesis, we are interested in designing schedulers for hybrid systems. We consider two specific subclasses of hybrid systems, real-time systems where tasks are competing for the access to common resources, and sampled switched systems where a choice has to be made on dynamics of the system to reach goals. Scheduling consists in defining the order in which the tasks will be run on the processors in order to complete all the tasks before a given deadline. In the first part of this thesis, we are interested in the scheduling of periodic tasks on multiprocessor architectures. We are especially interested in the robustness of schedulers, i.e., to prove that some values of the system parameters can be modified, and until what value they can be extended while preserving the scheduling order and meeting the deadlines. The Inverse Method can be used to prove the robustness of parametric timed systems. In this thesis, we introduce a state space reduction technique which allows us to treat challenging case studies such as one provided by Astrium EADS for the launcher Ariane 6. We also present how an extension of the Inverse Method, the Behavioral Cartography, can solve the problem of schedulability, i.e., finding the area in the parametric space in which there exists a scheduler that satisfies all the deadlines. We compare this approach to an analytic method to illustrate the interest of our approach In the second part of this thesis, we are interested in the control of affine switched systems. These systems are governed by a finite family of affine differential equations. At each time step, a controller can choose which dynamics will govern the system for the next time step. Controlling in this sense can be seen as a scheduling on the order of dynamics the system will have to use. The objective for the controller can be to make the system stay in a given area of the state space (stability) or to reach a given region of the state space (reachability). In this thesis, we propose a novel approach that computes a scheduler where the strategy is uniform for dense subsets of the state space. Moreover, our approach only uses forward computation, which is better suited than backward computation for contractive systems. We show that our designed controllers, systems evolve to a limit cyclic behavior. We apply our method to several case studies from the literature and on a real-life prototype of a multilevel voltage converter. Moreover, we show that our approach can be extended to systems with perturbations and non-linear dynamics.

Dans cette thèse, nous proposons et évaluons des algorithmes pour résoudre des problèmes d’ordonnancement en ligne. Pendant des décennies, les études en ordonnancement considèrent des modèles déterministes où toutes les informations nécessaires pour la définition du problème sont supposées connues à l’avance. Cette hypothèse n'est généralement pas réaliste. Ceci a motivé les études sur l’ordonnancement en ligne. Dans un problème d’ordonnancement en ligne, un algorithme doit prendre des décisions sans connaissance du futur. L’analyse compétitive est généralement la méthode utilisée pour évaluer les performances de tels algorithmes. Dans cette analyse, la performance d'un algorithme en ligne est mesurée par le ratio compétitif qui est le ratio dans le pire cas entre la performance de la solution obtenue et celle d’une solution optimale hors ligne. Nous considérons principalement deux paradigmes en ligne: celui où les tâches se présentent dans la liste et celui où les tâches arrivent au fur et à mesure. Sur la base de ces deux paradigmes, nous considérons différents modèles : une seule machine, deux machines identiques parallèles, deux machines uniformes parallèles, batch machines et open shop. Pour chacun des problèmes, nous démontrons une borne inférieure de ratios compétitifs et proposons des algorithmes en ligne. Ensuite, nous évaluons la performance de ces algorithmes à l’aide de l’analyse compétitive. Pour certains problèmes, nous montrons que les algorithmes proposés sont optimaux dans le sens où le ratio compétitif est égal à la borne inférieure. / This thesis proposes and evaluates some online algorithms for machine scheduling problems. Deterministic scheduling models have been extensively studied in the literature. One of the basic assumptions of these models is that all the information is known in advance. However, this assumption is usually not realistic. This observation promotes the emergence of online scheduling. In online scheduling problems, an online algorithm has to make decisions without future information. Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared with the performance of an a posteriori optimal solution where the sequence of requests is known. In the framework of competitive analysis, the performance of an online algorithm is measured by its competitive ratio. We mainly deal with two online paradigms: the one where jobs arrive over list and the one where jobs arrive over time. Based on these two paradigms, we consider different models: single machine, two identical parallel machines, two uniform parallel machines, batch processing machine and open shop. For each of the problems, we prove a lower bound of competitive ratios and propose online algorithms. Then we further measure the worst case performance of these algorithms. For some problems, we can show that the algorithms we proposed are optimal in the sense that their competitive ratios match the lower bounds.

Fournir les infrastructures de calcul nécessaires à la résolution des problèmescom-plexes de la société moderne constitue un défistratégique. Lesorganisations y répondent classiquement en mettant en place de largesinfrastructures de calcul parallèle et distribué. Les vendeurs de systèmes deCalcul Hautes Performances sont incités par la compétition à produire toujoursplus de puissance de calcul et de stockage, ce qui mène à des plateformes”Petascale“ spécifiques et sophistiquées, et bientôt à des machines”Exascale“. Ces systèmes sont gérés de manière centralisée à l’aide desolutions logicielles de gestion de jobs et de resources dédiées. Un problèmecrucial auquel répondent ces logiciels est le problème d’ordonnancement, pourlequel le gestionnaire de resources doit choisir quand, et sur quellesresources exécuter quelle tache calculatoire. Cette thèse fournit des solutionsà ce problème. Toutes les plateformes sont différentes. En effet, leurinfrastructure, le comportement de leurs utilisateurs et les objectifs del’organisation hôte varient. Nous soutenons donc que les politiquesd’ordonnancement doivent s’adapter au comportement des systèmes. Dans cemanuscrit, nous présentons plusieurs manières d’obtenir cette adaptativité. Atravers une approche expérimentale, nous étudions plusieurs compromis entre lacomplexité de l’approche, le gain potentiel, et les risques pris. / Providing the computational infrastucture needed to solve complex problemsarising in modern society is a strategic challenge. Organisations usuallyadress this problem by building extreme-scale parallel and distributedplatforms. High Performance Computing (HPC) vendors race for more computingpower and storage capacity, leading to sophisticated specific Petascaleplatforms, soon to be Exascale platforms. These systems are centrally managedusing dedicated software solutions called Resource and Job Management Systems(RJMS). A crucial problem adressed by this software layer is the job schedulingproblem, where the RJMS chooses when and on which resources computational taskswill be executed. This manuscript provides ways to adress this schedulingproblem. No two platforms are identical. Indeed, the infrastructure, userbehavior and organization's goals all change from one system to the other. Wetherefore argue that scheduling policies should be adaptative to the system'sbehavior. In this manuscript, we provide multiple ways to achieve thisadaptativity. Through an experimental approach, we study various tradeoffsbetween the complexity of the approach, the potential gain, and the riskstaken.

L'informatique moderne n'est plus uniquement composée de machines personnelles et de super calculateurs. De nombreux supports de calcul sont maintenant disponibles et chacun pose des contraintes particulières amenant à de nombreux objectifs. Ainsi, la notion de performance d'une application est devenue multi-dimensionnelle. Par exemple, ordonnancer optimalement (en temps) une application sur une grille de calcul est inutile si elle ne fournit pas de résultat parce qu'une machine tombe en panne. Fournir une solution à ces problèmes est un défi algorithmique actuel. Dans ce manuscrit, nous étudions l'ordonnancement multi-objectif à l'aide des outils de la théorie de l'approximation. Nous traitons ainsi quatre problèmes. Les deux premiers sont inspirés des systèmes embarqués, tandis que les deux derniers sont inspirés des problématiques que l'on retrouve sur les grilles et les \textit{clusters}. Le premier problème étudié est l'optimisation des performances d'une application sur une machine disposant de peu de mémoire de stockage. Nous montrons que l'utilisation de l'optimisation multi-objectif permet de fournir une solution et des informations sur le problème que la théorie mono-objectif de l'approximation ne pouvait pas obtenir. Les deux problèmes suivants concernent l'optimisation des performances d'une application lorsque les machines ne sont pas entièrement fiables. Les différents modèles de défaillances amènent à des problèmes d'optimisation radicalement différents. C'est pourquoi le deuxième problème traite de la sûreté de fonctionnement des systèmes embarqués alors que le troisième considère la fiabilité des grilles et \textit{clusters}. Le dernier problème concerne l'utilisation simultanée d'une plate-forme de calcul parallèle par de nombreux utilisateurs. Nous montrons comment l'utilisation de l'optimisation multi-objectif peut permettre de prendre en compte les besoins utilisateurs au sein du processus d'optimisation.

Cette habilitation décrit mes travaux en tomographie discrète, calcul quantique et ordonnancement.

L'objectif général de cette thèse, suggéré par le contrôle des radars de combat, consiste à intercaler en temps réel une tâche aléatoire dans un ordonnancement existant tout en limitant autant que possible l'augmentation de la valeur du critère. Dans notre cas, le critère que nous considérons est la somme des dépassements des délais des tâches déjà ordonnancées. Ces délais sont supposés quelconques : cette contrainte est plus dure que dans le cas des radars de combat où un certain nombre de tâches de surveillance doivent être effectuées de manière répétitive au cours d'une période donnée à l'intérieur de laquelle leur ordonnancement est libre, ce qui équivaut à un délai unique pour l'ensemble des tâches. La tâche à intercaler apparaît à un instant quelconque (c'est l'instant que nous considérons comme l'instant zéro). Sa durée n'est connue qu'au moment de son apparition. Il en est de même de son délai, qui est impératif. Nous considérons d'abord le cas d'une tâche aléatoire unique, puis le cas d'une tâche aléatoire composée de deux sous-tâches séparées par une période donnée. Enfin, nous proposons une amélioration de l'approche actuellement utilisée dans ce domaine.

Cette thèse est consacrée à l'étude de l'ordonnancement des tâches d'un programme parallèle en prenant en compte l'impact des communications. Sur les machines à mémoire distribuée telles que les grappes de PC, les temps de communications peuvent être importants. Les objectifs de cette thèse sont l'étude de modèles permettant de prendre en compte efficacement ces communications et l'étude des problèmes d'ordonnancement sous ces modèles. Nous nous sommes interessés au modèle à grand délai de communications qui est basé sur une prise en compte explicite des communications et au modèle des tâches malléables dans lequel les tâches sont elles-mêmes des activités parallèles pouvant s'exécuter sur un nombre variable de processeurs. Outre l'étude de la pertinance de ces modèles, les contributions obtenues vont dans les trois directions suivantes. Pour l'ordonnancement de tâches malléables avec contraintes de précédence nous avons proposé des algorithmes d'approximation constante (algorithmes polynômiaux offrant des garanties relativement à une solution optimale), pour le cas des arbres et pour le cas d'un graphe de précedence arbitraire. Une heuristique originale pour le problème du regroupement (ordonnancement sur un nombre non borné de processeurs) est proposée. Elle est basée sur une décomposition récursive du graphe de précédence et elle est validée par des simulations sur des graphes d'applications réelles. Enfin nous nous sommes intéressés au problème d'ordonnancement sous le modèle à grand délai de communication en considérant la possibilité de dupliquer des tâches. Dans ce cadre nous avons obtenu un algorithme polyôomial offrant une garantie logarithmique en fonction du délai de communication, améliorant ainsi la meilleure garantie connue (linéaire).

On considère le problème d'ordonnancement des systèmes temps-réel. On commence par la modelisation d'une certaine classe de programmes Java, avec des processus concurrents constitués d'une séquence de tâches temps-réel qui se synchronisent et peuvent accéder aux ressources communes. Pour ce modèle on analyse l'ordonnancement en proposant un algorithme d'attribution de priorités fixes; le problème de deadlock est aussi analysé grace à une technique de détection. A partir de ce problème, on aborde l'ordonnancement dans une approache plus générale basée sur le modèle des automates temporsés; on propose de techniques pour décider le problème d'ordonnancement qui réposent sur des procédures d'analyse symbolique d'accessibilité dans differents modèles: LIFO one-préemption, EDF one-préemption, General Scheduling. Pour chaque modèle on donne une serie de proprietés, notamment la preuve d'accessibilité. On conclut par donner une methode complète d'ordonnancement

La répartition des calculs et des données est le problème majeur à résoudre pour réaliser une application parallèle, son efficacité dépendant de la date et du lieu d'exécution des calculs sur l'ensemble des ressources, processeurs et mémoire, de la machine. Nous nous attachons à résoudre ce "problème d'ordonnancement". Nous utilisons pour cela un modèle proposé récemment : les tâches malléables. Après une introduction au domaine du parallélisme, nous présentons les principaux défauts d'autres modèles d'exécution, notamment leur modélisation fine du comportement des échanges de données, ce qui rend leur manipulation complexe. Les problèmes d'ordonnancement qui en résultent nous semblent difficiles à résoudre efficacement. Le modèle des tâches malléables considère une application comme un ensemble de tâches parallèles, chacune étant exécutée simultanément par plusieurs processeurs. La modélisation d'une application reste classique, en graphe de tâches, mais les communications ne sont prises en compte que de manière implicite, dans le temps d'exécution de chaque tâche malléable. Nous pensons que cette approche simplifie le problème d'ordonnancement à la fois théorique et pratique. Dans ce mémoire, nous abordons d'abord l'ordonnancement de tâches malléables indépendantes. Nous présentons quelques travaux déjà connus dont nous analysons les déficiences. Nous proposons un algorithme en deux étagères avec une meilleure garantie de performance de 3/2. Une comparaison en moyenne des différents algorithmes est également présentée. Pour les problèmes incluant des contraintes de précédences, nous présentons d'abord les résultats existants dans des modèles proches avant de proposer une première étude du problème des chaînes de tâches malléables. Enfin, après une introduction au domaine de la simulation adaptative de courants océaniques, l'utilisation pratique du modèle pour l'ordonnancement d'une simulation est également présentée.

Les travaux menés dans cette thèse concernent les problèmes d'ordonnancement sur des plates-formes de calcul dynamiques et hétérogènes et s'appuient sur le modèle de communication "multi-port" pour les communications. Nous avons considéré le problème de l'ordonnancement des tâches indépendantes sur des plates-formes maîtres-esclaves, dans les contextes statique et dynamique. Nous nous sommes également intéressé au problème de la redistribution de fichiers répliqués dans le cadre de l'équilibrage de charge. Enfin, nous avons étudié l'importance des mécanismes de partage de bande passante pour obtenir une meilleure efficacité du système.