Ordonnancement d’E/S Transversal pour les Systèmes de Fichiers Parallèles : desApplications aux DispositifsCette thèse porte sur l’utilisation de l’ordonnancement d’Entrées/Sorties (E/S) pour atténuer leseffets d’interférence et améliorer la performance d’E/S des systèmes de fichiers parallèles. Ilest commun pour les plates-formes de calcul haute performance (HPC) de fournir une infrastructurede stockage partagée pour les applications qui y sont hébergées. Dans cette situation,où plusieurs applications accèdent simultanément au système de fichiers parallèle partagé, leursaccès vont souffrir de l’interférence, ce qui compromet l’efficacité des stratégies d’optimisationd’E/S.Nous avons évalué la performance de cinq algorithmes d’ordonnancement dans les serveurs dedonnées d’un système de fichiers parallèle. Ces tests ont été exécutés sur différentes platesformeset sous différents modèles d’accès. Les résultats indiquent que la performance des ordonnanceursest affectée par les modèles d’accès des applications, car il est important pouraméliorer la performance obtenue grâce à un algorithme d’ordonnancement de surpasser sessurcoûts. En même temps, les résultats des ordonnanceurs sont affectés par les caractéristiquesdu système d’E/S sous-jacent - en particulier par des dispositifs de stockage. Différents dispositifsprésentent des niveaux de sensibilité à la séquentialité et la taille des accès distincts, ce quipeut influencer sur le niveau d’amélioration de obtenue grâce à l’ordonnancement d’E/S.Pour ces raisons, l’objectif principal de cette thèse est de proposer un modèle d’ordonnancementd’E/S avec une double adaptabilité : aux applications et aux dispositifs. Nous avons extraitdes informations sur les modèles d’accès des applications en utilisant des fichiers de trace,obtenus à partir de leurs exécutions précédentes. Ensuite, nous avons utilisé de l’apprentissageautomatique pour construire un classificateur capable d’identifier la spatialité et la taille desaccès à partir du flux de demandes antérieures. En outre, nous avons proposé une approche pourobtenir efficacement le ratio de débit séquentiel et aléatoire pour les dispositifs de stockage enexécutant des benchmarks pour un sous-ensemble des paramètres et en estimant les restantsavec des régressions linéaires.Nous avons utilisé les informations sur les caractéristiques des applications et des dispositifsde stockage pour décider automatiquement l’algorithme d’ordonnancement le plus appropriéen utilisant des arbres de décision. Notre approche améliore les performances jusqu’à 75% parrapport à une approche qui utilise le même algorithme d’ordonnancement dans toutes les situations,sans capacité d’adaptation. De plus, notre approche améliore la performance dans 64%de scénarios en plus, et diminue les performances dans 89% moins de situations. Nos résultatsmontrent que les deux aspects - des applications et des dispositifs - sont essentiels pour faire desbons choix d’ordonnancement. En outre, malgré le fait qu’il n’y a pas d’algorithme d’ordonnancementqui fournit des gains de performance pour toutes les situations, nous montrons queavec la double adaptabilité il est possible d’appliquer des techniques d’ordonnancement d’E/Spour améliorer la performance, tout en évitant les situations où cela conduirait à une diminutionde performance. / This thesis focuses on I/O scheduling as a tool to improve I/O performance on parallel file systemsby alleviating interference effects. It is usual for High Performance Computing (HPC)systems to provide a shared storage infrastructure for applications. In this situation, when multipleapplications are concurrently accessing the shared parallel file system, their accesses willaffect each other, compromising I/O optimization techniques’ efficacy.We have conducted an extensive performance evaluation of five scheduling algorithms at aparallel file system’s data servers. Experiments were executed on different platforms and underdifferent access patterns. Results indicate that schedulers’ results are affected by applications’access patterns, since it is important for the performance improvement obtained througha scheduling algorithm to surpass its overhead. At the same time, schedulers’ results are affectedby the underlying I/O system characteristics - especially by storage devices. Differentdevices present different levels of sensitivity to accesses’ sequentiality and size, impacting onhow much performance is improved through I/O scheduling.For these reasons, this thesis main objective is to provide I/O scheduling with double adaptivity:to applications and devices. We obtain information about applications’ access patternsthrough trace files, obtained from previous executions. We have applied machine learning tobuild a classifier capable of identifying access patterns’ spatiality and requests size aspects fromstreams of previous requests. Furthermore, we proposed an approach to efficiently obtain thesequential to random throughput ratio metric for storage devices by running benchmarks for asubset of the parameters and estimating the remaining through linear regressions.We use this information on applications’ and storage devices’ characteristics to decide the bestfit in scheduling algorithm though a decision tree. Our approach improves performance byup to 75% over an approach that uses the same scheduling algorithm to all situations, withoutadaptability. Moreover, our approach improves performance for up to 64% more situations, anddecreases performance for up to 89% less situations. Our results evidence that both aspects- applications and storage devices - are essential for making good scheduling choices. Moreover,despite the fact that there is no scheduling algorithm able to provide performance gainsfor all situations, we show that through double adaptivity it is possible to apply I/O schedulingtechniques to improve performance, avoiding situations where it would lead to performanceimpairment. / Esta tese se concentra no escalonamento de operações de entrada e saída (E/S) como uma soluçãopara melhorar o desempenho de sistemas de arquivos paralelos, aleviando os efeitos dainterferência. É usual que sistemas de computação de alto desempenho (HPC) ofereçam umainfraestrutura compartilhada de armazenamento para as aplicações. Nessa situação, em quemúltiplas aplicações acessam o sistema de arquivos compartilhado de forma concorrente, osacessos das aplicações causarão interferência uns nos outros, comprometendo a eficácia de técnicaspara otimização de E/S.Uma avaliação extensiva de desempenho foi conduzida, abordando cinco algoritmos de escalonamentotrabalhando nos servidores de dados de um sistema de arquivos paralelo. Foramexecutados experimentos em diferentes plataformas e sob diferentes padrões de acesso. Osresultados indicam que os resultados obtidos pelos escalonadores são afetados pelo padrão deacesso das aplicações, já que é importante que o ganho de desempenho provido por um algoritmode escalonamento ultrapasse o seu sobrecusto. Ao mesmo tempo, os resultados doescalonamento são afetados pelas características do subsistema local de E/S - especialmentepelos dispositivos de armazenamento. Dispositivos diferentes apresentam variados níveis desensibilidade à sequencialidade dos acessos e ao seu tamanho, afetando o quanto técnicas deescalonamento de E/S são capazes de aumentar o desempenho.Por esses motivos, o principal objetivo desta tese é prover escalonamento de E/S com duplaadaptabilidade: às aplicações e aos dispositivos. Informações sobre o padrão de acesso dasaplicações são obtidas através de arquivos de rastro, vindos de execuções anteriores. Aprendizadode máquina foi aplicado para construir um classificador capaz de identificar os aspectosespacialidade e tamanho de requisição dos padrões de acesso através de fluxos de requisiçõesanteriores. Além disso, foi proposta uma técnica para obter eficientemente a razão entre acessossequenciais e aleatórios para dispositivos de armazenamento, executando testes para apenas umsubconjunto dos parâmetros e estimando os demais através de regressões lineares.Essas informações sobre características de aplicações e dispositivos de armazenamento são usadaspara decidir a melhor escolha em algoritmo de escalonamento através de uma árvore dedecisão. A abordagem proposta aumenta o desempenho em até 75% sobre uma abordagem queusa o mesmo algoritmo para todas as situações, sem adaptabilidade. Além disso, essa técnicamelhora o desempenho para até 64% mais situações, e causa perdas de desempenho em até 89%menos situações. Os resultados obtidos evidenciam que ambos aspectos - aplicações e dispositivosde armazenamento - são essenciais para boas decisões de escalonamento. Adicionalmente,apesar do fato de não haver algoritmo de escalonamento capaz de prover ganhos de desempenhopara todas as situações, esse trabalho mostra que através da dupla adaptabilidade é possívelaplicar técnicas de escalonamento de E/S para melhorar o desempenho, evitando situações emque essas técnicas prejudicariam o desempenho.

De plus en plus de cœurs sont maintenant intégrés sur une seule puce afin de satisfaire les exigences toujours croissantes des applications en matière de systèmes haute performance et basse consommation. Le nombre de cœurs ne cesse d'augmenter, tout comme le besoin en réseaux de communications à haute vitesse entre ces cœurs. A l’inverse des réseaux de communication traditionnels, les Networks-on-Chip (NoCs) ont émergé comme une alternative mature pour les architectures massivement multicœur du fait de leur meilleure passage à l'échelle et de leur efficacité énergétique accrue.Les routeurs de NoC typiques sont constitués de mémoires-tampons qui servent au stockage temporaire de données. Cependant, des études ont montré que ces mémoires-tampons sont souvent inutilisées, en particulier lors de l'exécution application avec des modèles de trafic non uniformes. Cela est dû au fait que la plupart des routeurs typiques consacrent ces bouts de mémoire à leurs ports d'entrée et/ou de sortie, et toute cette mémoire ne peut être exploitée que par un certain type de flux de données. Cela entraîne une dégradation significative des performances dans les cas non favorables. Par conséquent, les architectures de routeurs capables de maximiser l'utilisation des mémoires-tampons pour des gains de performance sont recherchées.Dans le but de maximiser l'utilisation des ressources, cette thèse propose un concept novateur de routeur pour réseau sur puce appelé Roundabout NoC (RiNoC) qui s'inspire des ronds-points à plusieurs voies que l'on retrouve dans la gestion du trafic routier. Contrairement aux approches existantes, RiNoC assure intrinsèquement une utilisation efficace des ressources. Cependant, les routeurs inspirés des ronds-points sont sujet aux interblocages à cause de leur forme en anneau. Le routeur "Rotary NoC" partage le même concept d'organisation en anneau que nous proposons, mais repose sur une d'évitement des interblocages qui introduit des surcoûts non négligeables en terme de surface et de consommation énergétique. A l'inverse, RiNoC empêche les interblocages et améliore les performances des réseaux sur puce sans compromettre la surface ou l'énergie du réseau. Cette thèse exploite en particulier l'architecture hautement paramétrique de RiNoC afin de produire différentes configurations de routeur avec des compromis topologiques variables pour différents gains de performance sans sacrifier la surface. / More computing cores are now being integrated on a single chip in order to meet the ever-growing application demands for high performance and low power computing systems. As the number of cores continues to grow, so is the demand for scalable on-chip communication networks that can deliver high-speed communication among the cores. Contrary to traditional on-chip networks, Networks-on-Chip (NoCs) have emerged as a mature alternative interconnect for manycore architectures since it provides enhanced scalability and power efficiency.Typical NoC routers consist of buffers which serve as temporary data storage. However, studies have shown that buffers are often unutilized (i.e. idle or underutilized) especially when executing applications with non-uniform traffic patterns or bursty behaviours. This is because most typical routers dedicate a set of buffers to their input and/or output ports and these buffers can only be exploited by data-flows using them, which leads to significant performance degradation. Therefore, router architectures capable of maximizing buffer utilization for performance gains are indispensable.In order to maximize buffer resource utilization, this thesis proposes a novel NoC router concept called Roundabout NoC (RiNoC) that is inspired by real-life multi-lanes traffic roundabout. Contrary to existing approaches, RiNoC provides intrinsic and effective resource utilization. However, roundabout-inspired routers are susceptible to deadlocks due to their ring-like architecture. The Rotary NoC router shares similar ring-like concept with propose but relies on a deadlock-free technique which introduces significant area/power overheads. Conversely, RiNoC achieves deadlock-freeness and enhanced network performance over typical NoCs without compromising network area/power. This thesis further exploits RiNoC highly parametric architecture in order to produce different router configurations with varying topological trade-offs for performance gains without sacrificing area.

Ce manuscrit expose notre travail dans le cadre du projet IWARD et détaille la couche de gestion et de décision du groupement de robots. Ce projet avait comme objectif d’assister le personnel médical dans leur travail, ceci est réalisé en utilisant des robots mobiles, reconfigurables, et rechargeables. Ces robots sont conçus pour effectuer des taches logistiques comme : Le transport de médicaments, le nettoyage, le guidage des patients, la surveillance et la téléconsultation. Dans la première partie de la thèse nous présenterons le problème stratégique qui consiste à déterminer les plannings de rechargement des robots, la configuration des robots opérationnels ainsi que la localisation des stations d’attentes des robots lorsqu’ils sont en état de veille. Différentes hiérarchies à plusieurs niveaux de décisions, sont formulées comme des programmes linéaires en nombres entiers. Des formulations utilisant l’approche de génération de colonnes sont aussi développées pour résoudre ces problèmes. Dans la deuxième partie, le problème tactique est exposé, ceci consiste à affecter les taches arrivantes aux différents robots et d’ordonnancer dynamiquement l’exécution ces missions. Deux approches sont inspectées une version centralisée utilisant les algorithmes évolutionnaires et une autre version distribuée utilisant les algorithmes d’enchères inversées. Afin de mettre à l épreuve ces deux approches, une simulation a événements discrets a été conçue et développée spécifiquement pour le projet, permettant ainsi d’évaluer ces deux approches. / Due to the expansion of the life duration and the shortage of medical personal in hospitals the EU funded IWARD project as part of the IFP6 program. The aims of this project were to assist the medical personnel in logistic and non medical tasks (transport, cleaning, environmental monitoring, guidance and tele-monitoring) through the usage of mobile, reconfigurable, rechargeable robots, thus letting the Medical staff to concentrate on medical aspects of their work.This thesis was part of this project, and our work consisted on developing a decision making framework for the team of robots.In the first part of the thesis, we address the strategic decisions essentially the: (i) the robots’ home station location problem, (ii) Robot‘s reconfiguration problems and (iii) Robots recharging scheduling. We formulate those problems as a linear problems and we propose to solve them using Mixed Integer Programming (MIP). We also present a formulation using a column generation approach to solve those problems.In the later part we address the tactical problems, mainly the mission assignment, the mission scheduling and rescheduling. We present two different approaches; a centralized decision finder implemented using genetic algorithms. And a decentralized approach using auction like and market based algorithms in order to provided collaborative decision making framework.Finally we compare those two approaches using a custom made discrete event simulation (DES).

Afin d’accélérer les flux de produits, de réduire les niveaux de stocks et de faire des économies de transport, les entreprises de presque toutes les industries ont mis en place des centres de crossdock. Ces centres sont un point intermédiaire de consolidation dans une chaîne logistique. Les constructeurs automobiles Renault et Nissan s’appuient sur un réseau international de plateformes crossdock pour lier des fournisseurs de pièces de première monte avec des usines de production lointaines, généralement en outre-mer. Dans un cadre d’un partenariat académique-industriel entre le laboratoire LIMOS et Renault, cette thèse est focalisée sur la planification et l’ordonnancement des activités dans ces centres de crossdock. Des études de terrain menées chez Renault et Nissan nous ont permis d’identifier les caractéristiques, les contraintes et les inducteurs de coûts des plateformes de crossdock, ainsi que de cibler notre revue de la littérature. Sur ces bases, nous proposons une approche d’optimisation séquentielle, comprenant deux modèles en programmation linéaire en nombres entiers, implémentés dans CPLEX et testés sur des données industrielles de deux plateformes Renault. Les résultats des expérimentations obtenus sur le premier modèle (planification) ont montré une nette amélioration en termes de coûts, par rapport à la méthode Renault. Fort de ce constat, une implémentation industrielle a été faite, avec des résultats aussi probants. Le deuxième modèle (ordonnancement) s’avère pertinent pour des instances de moyenne taille. L’approche proposée permet de répondre à la configuration actuelle des AILN Renault et nous considérons qu’elle est adaptable à d’autres industries. / In order to accelerate product flow, reduce inventory levels and make economies in transportation, companies in almost all industries have set up cross-dock centres. These centres are an intermediate point of consolidation in a supply chain. Car manufacturers Renault and Nissan rely on an international network of crossdock platforms to link suppliers of OEM parts with overseas production plants. In a framework of an academic-industrial partnership between the LIMOS laboratory and Renault, this thesis focuses on the activity planning and scheduling at these crossdock centres.Field studies conducted at Renault and Nissan allowed us to identify the characteristics, constraints and cost drivers of crossdock platforms, as well as to target our review of the literature. Based on this, we propose a sequential optimization approach, comprising two integer linear programming models, implemented in CPLEX and tested on industrial data of two Renault platforms. Numerical experiments’ results obtained on the first model (planning) showed a significant improvement in cost, compared to the Renault method. In light of this results, an industrial implementation was made, with such convincing results. The second model (scheduling) proved to be relevant for medium-sized instances. The proposed approach fits to the current configuration of AILN Renault and we consider that it is adaptable to other industries.

Nous abordons dans cette thèse des problèmes de flowshop de permutation soumis des contraintes de délais minimaux et maximaux avec deux types de travaux principaux : 1. Nous avons modélisé, en utilisant l'algèbre MaxPlus, des problèmes de flowshop de permutation m-machines soumis une famille de contraintes : de délais minimaux, de délais maximaux, de sans attente, de délais fixes, de temps de montage indé- pendant de la séquence, de temps de démontage indépendant de la séquence, de blocage, de dates de début au plus tæt ainsi que de durées de latence. Des matrices caractérisant complètement leurs travaux associés ont été élaborées. Nous avons fait apparaître un problème central soumis des contraintes de délais minimaux et maximaux. 2. Nous avons élaboré des bornes inférieures pour le makespan et pour la somme (pondérée ou non) des dates de fin. Ces bornes inférieures ont été incorporées dans des procédures par séparation et évaluation. Nous avons généralisé les bornes inférieures de Lageweg et al. pour des contraintes quelconques et amélioré une borne inférieure de la littérature. L'utilisation de chacune de ces bornes inférieures ainsi que de leurs combinaisons ont été testées. Une famille de bornes inférieures pour la somme (pondérée ou non) des dates de fin a été élaborée basée sur la résolution d'un problème une machine et sur la résolution d'un problème de voyageur de commerce. Une politique de sélection de bornes inférieures a été proposée pour combiner les bornes inférieures. Bien qu'il s'agisse d'un problème de NP-difficile, l'efficacité de ces bornes inférieures a été vérifiée l'aide de tests. / In this thesis, permutation flowshop problems with minimal and maximal delay constraints were considered through two following principal tasks were particularly tackled. 1. In the first task, m-machine permutation flowshop problems with a family of constraints (minimal delays, maximal delays, no-wait, fixed delays, sequence-independent setup times, sequence-independent removal times, blocking, ready dates, duration of latency) were modeled using MaxPlus algebra. Job associated matrices which totally characterize these jobs were elaborated. The modeling led to reveal a central problem with constraints of minimal and maximal delays. 2. In the second task, lower bounds for makespan and for total (weighted or unweighted) completion times were elaborated. These lower bounds were incorporated in branchand-bound procedures. The lower bounds of Lageweg et al. were generalized for any constraint and a existed lower bound was improved. The usage of each of these lower bounds as well as that of their combinations was tested. A family of lower bounds for total (weighted or non-weighted) completion times was elaborated thanks to the solution of a one-machine problem and the solution of a traveling salesman problem. A lower bound selection strategy was proposed in order to combine these lower bounds. Despite necessity to solve a NP-hard problem, the effectiveness of these lower bounds was verified by numerical tests.

La première partie de ce travail concerne la production cyclique pour l'optimisation du taux de production dans les flowshops robotisés, où un robot est chargé du transport des pièces. Les cellules robotisées peuvent être disposées de façon linéaire ou circulaire. Les principaux résultats théoriques concernant la disposition linéaire ne peuvent être étendus à la configuration circulaire. En particulier, trouver le meilleur cycle de production de une pièce (1-cycle) est un problème polynomial dans le cas des cellules linéaires additives, mais NP-difficile pour la configuration correspondante circulaire.Nous nous concentrons principalement sur le cas des cellules circulaires équilibrées, où le temps d'usinage est identique sur toutes les machines. Après avoir présentés des outils pour l'analyse cyclique dans les cellules circulaires, nous établissons des propriétés nécessaires des 1-cycles performants, ce qui permet de conclure sur le problème du meilleur 1-cycle jusqu'à 8 machines. Toutefois, nous fournissons un contre-exemple pour 6 machines à la conjecture classique des 1-cycles, toujours ouverte dans cette configuration.Ensuite, nous étudions la structure des 1-cycles performants pour des cellules circulaires équilibrées arbitrairement grandes. Nous définissons et étudions les propriétés d'une nouvelle famille de cycles basée sur cette structure et formulons une conjecture sur sa dominance sur les 1-cycles qui conduirait à un algorithme polynomial pour le problème du meilleur 1-cycle dans ce cas. Cette structure permet de déterminer le meilleur 1-cycle jusqu'à 11 machines.Dans la deuxième partie, nous présentons le travail réalisé sur un problème industriel proposé par la SNCF dans le cadre du challenge ROADEF/EURO. Nous proposons un algorithme glouton pour ce problème combinant divers aspects de la gestion des trains au sein d'une gare. / The first part of this work deals with cyclic production for throughput optimization in robotic flow-shops, where a robot is in charge of the material handling of parts. Robotic cells may have a linear or a circular layout. Most theoretical results for the linear layout do not hold for the circular layout. In particular, the problem of finding the best one part production cycle (1-cycle), which is a polynomial problem for linear additive cells, has been proved NP-hard for the corresponding circular configuration.We mainly focus on a special case of circular balanced cells, where the processing times are identical for all machines. After presenting tools for cyclic analysis in circular cells, we study necessary properties of efficient 1-cycles. These results allow to conclude on the best one part production cycle for any parameters in circular balanced cells up to 8 machines. However, we provide a counter-example to the classical 1-cycle conjecture, still open for this configuration.Then, we study the structure of efficient one part production cycles in arbitrarily large circular balanced cells. We introduce and study a new family of cycles based on this structure, and formulate a conjecture on its dominance over one part-production cycles, which would lead to a polynomial algorithm for finding the best 1-cycle for circular balanced cells. This structure allows to settle the best one part production cycle for cells with up to 11 machines.In a second part, we present work on an industrial problem of railway stock scheduling proposed by the French railway company in the context of the ROADEF/EURO competition. We propose a greedy algorithm for this problem combining the various aspects of trains handling inside a station.

Il s'agit d'une étude menée sur les systèmes cyber-physiques sur trois aspects principaux: la vérification de la stabilité, l'ordonnancement et la synthèse des paramètres. Les systèmes de contrôle embarqués (ECS) agissant dans le cadre de contrats temporels sont la classe considérée de systèmes cyber-physiques dans la thèse. ECS fait référence à des intégrations d'un dispositif informatique avec le système physique. En ce qui concerne les contrats temporels, ils sont des contraintes de temps sur les instants où se produisent certains événements tels que l'échantillonnage, l'actionnement et le calcul. Ces contrats sont utilisés pour modéliser les problèmes qui se posent dans les systèmes de contrôle modernes: incertitudes sur les retards d'actionnement, les périodes d'échantillonnage incertaines et l'interaction de plusieurs systèmes physiques avec des ressources informatiques partagées (CPUs). Maintenant, compte tenu d'un ECS et d'un contrat temporel, nous reformulons le système de manière impulsionnelle et vérifions la stabilité du système, sous toutes les incertitudes bornées et données par le contrat, en utilisant des techniques d'approximation convexe et de nouveaux résultats généralisés pour le problème sur une classe de systèmes modélisés dans le cadre des inclusions différentielles. Deuxièmement, compte tenu d'un ensemble de contrôleurs implémentés sur une plate-forme de calcul commune (CPUs), dont chacun est soumis à un contrat de synchronisation, et à son meilleur et son plus mauvais cas d'exécution dans chaque CPU, nous synthétisons une politique d’ordonnancement dynamique qui garantit que chaque contrat temporel est satisfait et que chacun des CPU partagés est attribué à au plus un contrôleur à tout moment. L'approche est basée sur une reformulation qui nous permet d'écrire le problème d’ordonnancement comme un jeu temporelle avec spécification de sureté. Ensuite, en utilisant l'outil UPPAAL-TIGA, une solution au jeu fournit une politique d’ordonnancement appropriée. En outre, nous fournissons une nouvelle condition nécessaire et suffisante pour l’ordonnancement des tâches de contrôle en fonction d’un jeu temporisé simplifiés. Enfin, nous résolvons un problème de synthèse de paramètres qui consiste à synthétiser une sous-approximation de l'ensemble des contrats de synchronisation qui garantissent en même temps l’ordonnancement et la stabilité des contrôleurs intégrés. La synthèse est basée sur un nouveau paramétrage du contrat temporel pour les rendre monotones, puis sur un échantillonnage à plusieurs reprises de l'espace des paramètres jusqu'à atteindre une précision d'approximation prédéfinie. / This is a study conducted on cyber-physical systems on three main aspects: stability verification, scheduling, and parameter synthesis. Embedded control systems (ECS) acting under timing contracts are the considered class of cyber-physical systems in the thesis. ECS refers to integrations of a computing device with the physical system. As for timing contracts they are time constraints on the instants where some events happen such as sampling, actuation, and computation. These contracts are used to model issues that arise in modern embedded control systems: uncertain sampling to actuation delays, uncertain sampling periods, and interaction of several physical systems with shared computational resources (CPUs). Now given an ECS and a timing contract we reformulate the system into an impulsive one and verifies stability of the system, under all possible bounded uncertainties given by the contract, using safe convex approximation techniques and new generalized results for the problem on a class of systems modeled in the framework of difference inclusions. Second given a set of controllers implemented on a common computational platform (CPUs), each of which is subject to a timing contract, and best and worst case execution times on each CPU, we synthesize a dynamic scheduling policy, which guarantees that each timing contract is satisfied and that each of the shared CPUs are allocated to at most one embedded controller at any time. The approach is based on a timed game formulation that allows us to write the scheduling problem as a timed safety game. Then using the tool UPPAAL-TIGA, a solution to the safety game provides a suitable scheduling policy. In addition, we provide a novel necessary and sufficient condition for schedulability of the control tasks based on a simplified timed game automaton. Last, we solve a parameter synthesis problem which consists of synthesizing an under-approximation of the set of timing contracts that guarantee at the same time the schedulability and stability of the embedded controllers. The synthesis is based on a re-parameterization of the timing contract to make them monotonic, and then on a repeatedly sampling of the parameter space until reaching a predefined precision of approximation.

Cette thèse explore les problèmes liés à l'ordonnancement concurrent dans le contexte des applications massivement parallèle, de deux points de vue: le coté mémoire (en particulier la mémoire cache) et le coté tolérance aux fautes.Avec l'avènement récent des architectures dites many-core, tels que les récents processeurs multi-coeurs, le nombre d'unités de traitement augmente de manière importante.Dans ce contexte, les avantages fournis par les techniques d'ordonnancements concurrents ont été démontrés à travers de nombreuses études.L'ordonnancement concurrent, aussi appelé co-ordonnancement, consiste à exécuter les applications de manière concurrente plutôt que les unes après les autres, dans le but d'améliorer le débit global de la plateforme.Mais le partage des ressources peut souvent générer des interférences.Une des solutions pour réduire de manière importante ces interférences est le partitionnement de cache.À travers un modèle théorique, des simulations et des expériences sur une plateforme existante, nous montrons l'utilité et l'importance du co-ordonnancement quand nos stratégies de partitionnement de cache sont utilisées.De plus, avec ce nombre croissant de processeurs, la probabilité d'une panne augmente également.L'efficacité des techniques de co-ordonnancement a été démontrée dans un contexte sans pannes, mais les plateformes massivement parallèles sont confrontées à des pannes fréquentes, et des techniques de tolérance aux fautes doivent être mise en place pour améliorer l'efficacité de ces plateformes.Nous étudions la complexité du problème avec un modèle théorique, nous concevons des heuristiques et nous effectuons un ensemble complet de simulations avec un simulateur de pannes, qui démontre l'efficacité des heuristiques proposées. / This thesis explores co-scheduling problems in the context of large-scale applications with two main focus: the memory side, in particular the cache memory and the resilience side.With the recent advent of many-core architectures such as chip multiprocessors (CMP), the number of processing units is increasing.In this context, the benefits of co-scheduling techniques have been demonstrated. Recall that, the main idea behind co-scheduling is to execute applications concurrently rather than in sequence in order to improve the global throughput of the platform.But sharing resources often generates interferences.With the arising number of processing units accessing to the same last-level cache, those interferences among co-scheduled applications becomes critical.In addition, with that increasing number of processors the probability of a failure increases too.Resiliency aspects must be taking into account, specially for co-scheduling because failure-prone resources might be shared between applications.On the memory side, we focus on the interferences in the last-level cache, one solution used to reduce these interferences is the cache partitioning.Extensive simulations demonstrate the usefulness of co-scheduling when our efficient cache partitioning strategies are deployed.We also investigate the same problem on a real cache partitioned chip multiprocessors, using the Cache Allocation Technology recently provided by Intel.In a second time, still on the memory side, we study how to model and schedule task graphs on the new many-core architectures, such as Knights Landing architecture.These architectures offer a new level in the memory hierarchy through a new on-packagehigh-bandwidth memory. Current approaches usually do not take intoaccount this new memory level, however new scheduling algorithms anddata partitioning schemes are needed to take advantage of this deepmemory hierarchy.On the resilience, we explore the impact on failures on co-scheduling performance.The co-scheduling approach has been demonstrated in a fault-free context, but large-scale computer systems are confronted by frequent failures, and resilience techniques must be employed for large applications to execute efficiently. Indeed, failures may create severe imbalance between applications, and significantly degrade performance.We aim at minimizing the expected completion time of a set of co-scheduled applications in a failure-prone context by redistributing processors.

Cette recherche en ergonomie porte sur le travail d’articulation des dimensions sociales et économiques des entreprises sous-tendant la conception d’ordonnancements du personnel robustes dans un contexte social sensible.Le plus souvent considérée comme un levier de flexibilité par les entreprises, les apports croisés de la littérature en GRH et en ergonomie a permis de considérer l’ordonnancement comme une activité de management de ressources « distribué », soulevant ainsi des enjeux liés à la fois aux dimensions économiques et sociales des entreprises (santé, compétences, formation, satisfaction des agents). L’objectif de ce travail de recherche est d’apporter des éléments de compréhension sur ce travail multifacette d’articulation et sur son évaluation, et ce faisant de définir la robustesse des ordonnancements.Pour appréhender cette activité, répartie entre trois niveaux différents (stratégique, tactique, opérationnel), six types de recueils de données ont été réalisés : des entretiens semi-directifs, des observations de l’activité des ordonnanceurs du niveau tactique, des groupes de travail métiers et inter-métiers, ainsi que des entretiens d’auto-confrontation outillés par des plannings réalisés.Les résultats mettent en évidence une construction dynamique de la robustesse, comme étant le résultat des stratégies mises en œuvre par les ordonnanceurs des différents niveaux. A partir de la gestion de contraintes de nature humaine et opérationnelle, les stratégies de construction de la robustesse reposent sur les connaissances qu’ont les ordonnanceurs de la réglementation, du processus, des autres ordonnanceurs et des agents commerciaux. Les ordonnancements robustes prennent différentes formes (stable ou flexible, immédiate ou différée) et doivent permettre de résister aux aléas mais aussi de construire de marges de manœuvre pour le futur.Les retombées de notre recherche portent sur la définition de la robustesse dans le champ de l’ordonnancement du personnel, sur l’activité de conception distribuée inter-métiers et à l’identification des conditions favorables à la conception de tels ordonnancements. / This research in ergonomics focuses on the design of robust personnel schedules in a sensitive social context, based on the articulation work between the social and economic dimensions of companies .it is often seen as a lever for flexibility by companies. Research in ergonomics and human resources management shows that it possible to consider scheduling as a "distributed" resource management activity, which raises issues related to both the economic and social dimensions of companies (health, skills, training, agent satisfaction). Our objectives are to understand how schedulers articulate theses dimensions, evaluate this work, and to define the robustness on scheduling.To understand this activity, divided between three different levels (strategic, tactical, operational), six types of data collection were carried out: semi-directive interviews, observations of the activity of planners at the tactical level, business and inter-business working groups, as well as self-confrontation interviews based on achieved schedules.The robustness is dynamically built from the constraint management strategies of schedulers. These are based on the schedulers’ knowledge : of regulations, of process, of other schedulers and commercial agents. Robustness takes different forms (stable or flexible, immediate or delayed) and must make it possible to resist disruptions but also to build room for manœuvre for the future.The impact of our research is related to the definition of robustness on personnel scheduling, to the joint collective activity and to the identification of the conditions in favour of robustness’ construction.

Les logiciels embarqués critiques de contrôle-commande sont soumis à des contraintes fortes englobant le déterminisme, la correction logique et la correction temporelle. Nous supposons que les spécifications sont exprimées à l'aide du langage formel de description d'architectures logicielles temps réel multipériodiques Prelude. L'objectif de cette thèse est, à partir d'un programme Prelude ou d'un ensemble de tâches temps réel dépendantes, de générer un code multithreadé exécutable sur une architecture multicœur tout en respectant la sémantique initiale. Pour cela, nous avons développé une boîte à outil, SchedMCore,permettant : - d'une part, la vérification formelle de l'ordonnançabilité. La vérification proposée est basée sur le parcours exhaustif du comportement avec pas de temps discret. Il est alors possible d'analyser des politiques en-ligne (FP, gEDF, gLLF et LLREF) mais également de calculer une affectation de priorité fixe valide et une séquence valide hors-ligne.- d'autre part, l'exécution multithreadée sur une cible multicœur. L'exécutif encode les politiques proposées étudiées dans la partie d'analyse d'ordonnançabilité, à savoir les quatre politiques en-ligne ainsi que les séquences valides générées. L'exécutif permet 3 modes d'utilisation, allant de la simulation temporelle à l'exécution temps précis des comportements des tâches. Il est compatible Posix et facilement portable sur divers OS. / A real-time control-command embedded system is subject to strong constraints such as determinism, logical and temporal correctness. We assume that the specifications are expressed using the formal software architecture description language Prelude, dedicated to real-time multiperiodic applications. The goal of this thesis is, given a Prelude program or dependent real-time taskset, to generate amultithreaded executable code over a multicore architecture while respecting the original semantic. To do so we have developed a toolbox, SchedMcore, that allows: - the formal verification of schedulability. The verification is based on the exhaustive exploration of the behaviour with a discret time frame. It is possible to analyse on-line policies (FP, gEDF, gLLF et LLREF), as well as to compute a fixed valid priority assignment and a valid off-line sequence.- the multithreaded execution over a multicore target. The framework encodes the same policies as those studied in the first part (the four on-line policies and the generated sequences). The framework provides three usage modes, from temporal simulation to time accurate execution. The executive is compatible with Posix and easily portable on several OS.