The High Performance Computing community is constantly facing new challenges due to the ever growing demand for processing power from scientific applications that represent diverse areas of human knowledge. Parallel and distributed systems are the key to speed up the execution of these applications as many jobs can be executed concurrently. These systems are shared by many users who submit their jobs over time and expect a fair treatment by the scheduler. The work done in this thesis lies in this context: to analyze and develop fair and efficient algorithms for managing computing resources shared among multiple users. We analyze scenarios with many submissions issued from multiple users over time. These submissions contain several jobs and the set of submissions are organized in successive campaigns. In what we define as the Campaign Scheduling model, the jobs of a campaign do not start until all the jobs from the previous campaign are completed. Each user is interested in minimizing the flow times of their own campaigns. This is motivated by the user submission behavior whereas the execution of a new campaign can be tuned by the results of the previous campaign. In the first part of this work, we define a theoretical model for Campaign Scheduling under restrictive assumptions and we show that, in the general case, it is NP-hard. For the single-user case, we show that an approximation scheduling algorithm for the (classic) parallel job scheduling problem also delivers the same approximation ratio for the Campaign Scheduling problem. For the general case with multiple users, we establish a fairness criteria inspired by time sharing. Then, we propose a scheduling algorithm called FairCamp which uses campaign deadlines to achieve fairness among users between consecutive campaigns. The second part of this work explores a more relaxed and realistic Campaign Scheduling model, provided with dynamic features. To handle this setting, we propose a new algorithm called OStrich whose principle is to maintain a virtual time-sharing schedule in which the same amount of processors is assigned to each user. The completion times in the virtual schedule determine the execution order on the physical processors. Then, the campaigns are interleaved in a fair way. For independent sequential jobs, we show that OStrich guarantees the stretch of a campaign to be proportional to campaigns size and to the total number of users. The stretch is used for measuring by what factor a workload is slowed down relatively to the time it takes to be executed on an unloaded system. Finally, the third part of this work extends the capabilities of OStrich to handle parallel jobs. This new version executes campaigns using a greedy approach and uses an event-based resizing mechanism to shape the virtual time-sharing schedule according to the system utilization ratio. / La communauté de Calcul Haute Performance est constamment confrontée à de nouveaux défis en raison de la demande toujours croissante de la puissance de traitement provenant dapplications scientifiques diverses. Les systèmes parallèles et distribués sont la clé pour accélérer lexécution de ces applications, et atteindre les défis associés car de nombreux processus peuvent être exécutés simultanément. Ces systèmes sont partagés par de nombreux utilisateurs qui soumettent des tâches sur de longues périodes au fil du temps et qui attendent un traitement équitable par lordonnanceur. Le travail effectué dans cette thèse se situe dans ce contexte: analyser et développer des algorithmes équitables et efficaces pour la gestion des ressources informatiques partagés entre plusieurs utilisateurs. Nous analysons les scénarios avec de nombreux soumissions issues de plusieurs utilisateurs. Ces soumissions contiennent un ou plusieurs processus et lensemble des soumissions sont organisées dans des campagnes successives. Dans ce que nous appelons le modèle dordonnancement des campagnes les processus dune campagne ne commencent pas avant que tous les processus de la campagne précédente soient terminés. Chaque utilisateur est intéressé à minimiser la somme des temps dexécution de ses campagnes. Cela est motivé par le comportement de lutilisateur tandis que lexécution dune campagne peut être réglé par les résultats de la campagne précédente. Dans la première partie de ce travail, nous définissons un modèle théorique pour lordonnancement des campagnes sous des hypothèses restrictives et nous montrons que, dans le cas général, il est NP-difficile. Pour le cas mono-utilisateur, nous montrons que lalgorithme dapproximation pour le problème (classique) dordonnancement de processus parallèles fournit également le même rapport dapproximation pour lordonnancement des campagnes. Pour le cas général avec plusieurs utilisateurs, nous établissons un critère déquité inspiré par une situation idéalisée de partage des ressources. Ensuite, nous proposons un algorithme dordonnancement appelé FairCamp qui impose des dates limite pour les campagnes pour assurer léquité entre les utilisateurs entre les campagnes successives. La deuxième partie de ce travail explore un modèle dordonnancement de campagnes plus relâché et réaliste, avec des caractéristiques dynamiques. Pour gérer ce cadre, nous proposons un nouveau algorithme appelé OStrich dont le principe est de maintenir un ordonnancement partagé virtuel dans lequel le même nombre de processeurs est assigné à chaque utilisateur. Les temps dachèvement dans lordonnancement virtuel déterminent lordre dexécution sur le processeurs physiques. Ensuite, les campagnes sont entrelacées de manière équitable. Pour des travaux indépendants séquentiels, nous montrons que OStrich garantit le stretch dune campagne en étant proportionnel à la taille de la campagne et le nombre total dutilisateurs. Le stretch est utilisé pour mesurer le ralentissement par rapport au temps quil prendrait dans un système dédié. Enfin, la troisième partie de ce travail étend les capacités dOStrich pour gérer des tâches parallèles rigides. Cette nouvelle version exécute les campagnes utilisant une approche gourmande et se sert aussi dun mécanisme de redimensionnement basé sur les événements pour mettre à jour lordonnancement virtuel selon le ratio dutilisation du système.

Face au coût de la gestion locale des infrastructures informatiques, de nombreuses entreprises ont décidé de la faire gérer par des fournisseurs externes. Ces derniers, connus sous le nom de IaaS (Infrastructure as a Service), mettent des ressources à la disposition des entreprises sous forme de machine virtuelle (VM - Virtual Machine). Ainsi, les entreprises n'utilisent qu'un nombre limité de machines virtuelles capables de satisfaire leur besoin. Ce qui contribue à la réduction des coûts de l'infrastructure informatique des entreprises clientes. Cependant, cette externalisation soulève pour le fournisseur, les problèmes de respect d'accord de niveau de service (SLA - Service Layer Agreement) souscrit par le client et d'optimisation de la consommation énergétique de son infrastructure. Au regard de l'importance que revêt ces deux défis, de nombreux travaux de recherches se sont intéressés à cette problématique. Les solutions de gestion d'énergie proposées consistent à faire varier la vitesse d'exécution des périphériques concernés. Cette variation de vitesse est implémentée, soit de façon native parce que le périphérique dispose des mécaniques intégrés, soit par simulation à travers des regroupements (spatial et temporel) des traitements. Toutefois, cette variation de vitesse permet d'optimiser la consommation énergétique d'un périphérique mais, a pour effet de bord d'impacter le niveau de service des clients. Cette situation entraine une incompatibilité entre les politiques de variation de vitesse pour la baisse d'énergie et le respect de l'accord de niveau de service. Dans cette thèse, nous étudions la conception et l'implantation d'un gestionnaire de ressources "éco énergétique" dans un système virtualisé. Un tel gestionnaire doit permettre un partage équitable des ressources entre les machines virtuelles tout en assurant une utilisation optimale de l'énergie que consomment ces ressources. Nous illustrons notre étude avec un ordonnanceur de machines virtuelles. La politique de variation de vitesse est implantée par le DVFS (Dynamic Voltage Frequency Scaling) et l'allocation de la capacité CPU aux machines virtuelles l'accord de niveau de service à respecter. / Considering the cost of local management of the computing infrastructures, numerous companies decided to delegate theirs to providers. These latter are known as an Infrastructure as a Service (IaaS) and provide resources to companies in the form of virtual machine (VM). This decision to outsource contributes to lower the cost of IT infrastructure of the customer companies. However, it raises for the provider, the problems of the respect of the Service Layer agreement (SLA) of the customer and of the optimization of the energy consumption of his infrastructure. With regard to the importance of these two challenges, many research works have focused on this problem. The proposed energy management solutions consist in varying the execution speed of the affected devices. This variation of speed is implemented either natively because the device has integrated mechanics, or by simulation through a spatial or temporal batching requests. However, this variation of speed optimizes the energy consumption of a device but has the side effect of degrading the customers SLA. In this thesis, we study the design and the implementation of an energy-efficient resources manager in a virtualized system. Such a manager must ensure a fair share of resources among VMs while ensuring optimal use of the energy consumed by the resources. We illustrate our study thanks to a scheduler of VMs. The DVFS constitutes our energy management policy and the CPU capacity of the VMs the SLA to respect.

L'étude des systèmes en réseau supports d'applications collaboratives, distribuées et interconnectées par un réseau repose sur l'identification des exigences de fonctionnement de l'application appelées Qualité de Contrôle (QdC), et sur l'évaluation des performances du réseau pour obtenir son niveau de Qualité de Service (QdS). « Cette thématique comporte d'importants verrous de nature fondamentale relevant du domaine de l'automatique, de la robotique, des capteurs, de la théorie de l'information, des réseaux. Par souci de simplification, les travaux sur les systèmes en réseau se repartissent selon deux approches: la première compense les perturbations générées par les communications au niveau de l'application (« control over network »). La seconde adapte les performances du réseau en fonction des besoins applicatifs (« control of network »). L'objectif de nos travaux de thèse est donc de proposer un environnement de modélisation intégré permettant de représenter le comportement des SCRs. Nous avons choisi les Réseaux de Petri de haut niveau qui possède un fort pouvoir d'expression, de formalisation et dont la modularité permet d'ajouter et/ou de faire évoluer les modèles qui sont développés dans ce travail. Dans un premier temps, nous avons proposé un modèle Ethernet Commuté gérant des mécanismes d'ordonnancement. Le choix de ce réseau a été guidé par le fait qu'il est de plus en plus utilisé dans les SCRs. Ensuite, le modèle d'un SCR a été proposé, et modélisé par des Réseaux de Petri de haut de niveau, en intégrant au modèle Ethernet Commuté, l'environnement applicatif : Contrôleur, Process,.. Enfin, des stratégies pour commander le réseau de façon à adapter sa Qualité de Service en regard de la Qualité de Contrôle requise par l'application, ont été mises en oeuvre. Pour cela, des ordonnanceurs à priorité stricte et de type WRR sont utilisés. Les résultats de simulation montrent clairement que des dispositifs de compensation du réseau pour améliorer les performances du système de communication, permettent aussi d'améliorer les performances du système à commander.

Pour répondre aux besoins de plus en plus hétérogènes des applications (puissance et efficacité énergétique), nous nous intéressons dans cette thèse aux architectures émergentes de type multi-cœur asymétrique en fonctionnalités (FAMP). Ces architectures sont caractérisées par une mise en œuvre non-uniforme des extensions matérielles dans les cœurs (ex. unitée de calculs à virgule flottante (FPU)). Les avantages en surface sont apparents, mais qu'en est-il de l'impact au niveau logiciel, énergétique et performance?Pour répondre à ces questions, la thèse explore la nature de l'utilisation des extensions dans des applications de l'état de l'art et compare différentes méthodes existantes. Pour optimiser le placement de tâches et ainsi augmenter l'efficacité, la thèse propose une solution dynamique au niveau ordonnanceur, appelée ordonnanceur relaxé.Les extensions matérielles sont intéressantes car elles permettent des accélérations difficilement atteignables par la parallélisation sur un multi-cœur. Néanmoins, leurs utilisations par les applications sont faibles et leur coût en termes de surface et consommation énergétique sont importants.En se basant sur ces observations, les points suivants ont été développés:Nous présentons une étude approfondie sur l'utilisation de l'extension vectorielle et FPU dans des applications de l'état de l'artNous comparons plusieurs solutions de gestion des extensions à différent niveaux de granularité temporelle d'action pour comprendre les limites de ces solutions et ainsi définir à quel niveau il faut agir. Peu d'études traitent la question de la granularité d'action pour gérer les extensions.Nous proposons une solution pour estimer en ligne la dégradation de performance à exécuter une tâche sur un cœur sans extension. Afin de permettre la mise à l'échelle des multi-cœurs, le système d'exploitation doit avoir de la flexibilité dans le placement de tâches. Placer une tâche sur un cœur sans extension peut avoir d'importantes conséquences en énergie et en performance. Or à ce jour, il n'existe pas de solution pour estimer cette potentielle dégradation.Nous proposons un ordonnanceur relaxé, basé notre modèle d'estimation de dégradation, qui place les tâches sur un ensemble de cœurs hétérogènes de manière efficace. Nous étudions la flexibilité gagnée ainsi que les conséquences aux niveaux performances et énergie.Les solutions existantes proposent des méthodes pour placer les tâches sur un ensemble de cœurs hétérogènes, or, celles-ci n'étudient pas le compromis entre qualité de service et gain en consommation pour les architectures FAMP.Nos expériences sur simulateur ont montré que l'ordonnanceur peut atteindre une flexibilité de placement significative avec une dégradation en performance de moins de 2%. Comparé à un multi-cœur symétrique, notre solution permet un gain énergétique moyen au niveau cœur de 11 %. Ces résultats sont très encourageant et contribuent au développement d'une plateforme complète FAMP. Cette thèse a fait l'objet d'un dépôt de brevet, de trois communications scientifiques internationales (plus une en soumission), et a contribué à deux projets européens. / To meet the increasingly heterogeneous needs of applications (in terms of power and efficiency), this thesis focus on the emerging functionally asymmetric multi-core processor (FAMP) architectures. These architectures are characterized by non-uniform implementation of hardware extensions in the cores (ex. Floating Point Unit (FPU)). The area savings are apparent, but what about the impact in software, energy and performance?To answer these questions, the thesis investigates the nature of the use of extensions in state-of-the-art's applications and compares various existing methods. To optimize the tasks mapping and increase efficiency, the thesis proposes a dynamic solution at scheduler level, called relaxed scheduler.Hardware extensions are valuable because they speed up part of code where the parallelization on multi-core isn't efficient. However, the hardware extensions are under-exploited by applications and their cost in terms of area and power consumption are important.Based on these observations, the following contributions have been proposed:We present a detailed study on the use of vector and FPU extensions in state-of-the-art's applicationsWe compare multiple extension management solutions at different levels of temporal granularity of action, to understand the limitations of these solutions and thus define at which level we must act. Few studies address the issue of the granularity of action to manage extensions.We offer a solution for estimating online performance degradation to run a task on a core without a given extension. To allow the scalability of multi-core, the operating system must have flexibility in the placement of tasks. Placing a task on a core with no extension can have important consequences for energy and performance. But to date, there is no way to estimate this potential degradation.We offer a relaxed scheduler, based on our degradation estimation model, which maps the tasks on a set of heterogeneous cores effectively. We study the flexibility gained and the implications for performance and energy levels. Existing solutions propose methods to map tasks on a heterogeneous set of cores, but they do not study the tradeoff between quality of service and consumption gain for FAMP architectures.Our experiments with simulators have shown that the scheduler can achieve a significantly higher mapping flexibility with a performance degradation of less than 2 %. Compared to a symmetrical multi-core, our solution enables an average energy gain at core level of 11 %. These results are very encouraging and contribute to the development of a comprehensive FAMP platform . This thesis has been the subject of a patent application, three international scientific communications (plus one submission), and contributes to two active european projects.

Dans cette thèse, nous nous intéressons aux modèles de calcul dans les réseaux d'objets à capacité restreinte, tels que les réseaux de capteurs sans fil. Nous nous focalisons sur les protocoles de population proposés par Angluin et al. Dans ce modèle, les objets sont représentés par des agents à états finis, passivement mobiles, communiquant entre paires et formant un réseau asynchrone et anonyme. Nous présentons deux études comparatives qui nous permettent par la suite de proposer une approche établissant le lien des protocoles de population avec deux autres modèles : le modèle des tâches avec les systèmes de réécritures de graphes, et le modèle asynchrone et anonyme d'échange de messages. Nous passons ensuite au problème d'ordonnancement dans les protocoles de population. Nous proposons un nouvel ordonnanceur probabiliste, 1-central, basé sur les rendez-vous randomisés et appelé HS Scheduler. Contrairement aux autres ordonnanceurs,il permet à plus d'une paire de communiquer à la fois. Nous prouvons qu'il est équitable avec probabilité 1. Nous analysons par la suite les termes Nous analysons par la suite les temps de stabilisation de certains protocoles s'exécutant sous le Random Scheduler ou le HS Scheduleret sur différentes topologies du graphe d'interaction. Nous prouvons que le HS Scheduler est équivalent en temps au Random Scheduler quand le graphe d'interaction est complet mais qu'il permet une stabilisation plus rapide quand le graphe est aléatoire. Par la suite,nous proposons un autre ordonnanceur qui prend en considération les états des agents et permet d'introduire la terminaison à certains protocoles : le Prorotol Aware HS Scheduler.Nous prouvons qu'il est équitable avec probabilité 1. Nous faisons l'analyse des temps de stabilisation de certains protocoles s'exécutant sous cet ordonnanceur en considérant différentes topologies du graphe d'interaction. Finalement, nous implémentons et simulons sur ViSiDiA l'ensemble des scénarios étudiés et validons nos résultats théoriques. / In this work, we consider computing models for networks of tiny objects suchas wireless sensor networks. We focus on the population protocols, a pairwise computationalmodel introduced by Angluin et al. where the tiny objects are represented byanonymous, passively mobile, finite state agents forming asynchronous networks. Weestablish two comparative studies between the population protocol model (and its extensions)and the two following ones: tasks with graph relabeling systems, and anonymousasynchronous message passing. These studies aim to establish possible mappings betweenthe population protocols and these two models. We then focus on the scheduling of thepairwise interactions in population protocols. We propose the HS Scheduler, a new probabilistic1-central scheduler based on randomized handshakes. Compared to the existingschedulers, this scheduler allows to more than one pair of agents to communicate simultaneously.We prove that this scheduler is fair with probability 1. We thereafter presentanalyses of the complexity of the stabilization time of some protocols running under thescheduling of the Random Scheduler and the HS Scheduler, and over different topologiesof the interaction graph. We prove that these two schedulers are time equivalent withComputing Models for Networks of Tiny Objects iiirespect to these protocols when the interaction graph is complete, however computationsunder the HS Scheduler stabilize faster when the interaction graph is random. We then introducethe Protocol Aware HS Scheduler, a slightly modifed version of the HS Schedulerthat takes into account the states of the agents and allows termination in some protocols.We also prove that this scheduler is fair with probability 1. We present analyses of thetime complexity of some protocols running under the scheduling of the Protocol AwareHS Scheduler and over dfferent structures of the interaction graph. We implement thedifferent scenarios in ViSiDiA, and validate through simulations our theoretical results.

La simulation haute-fidélité des coeurs de réacteurs nucléaires nécessite une évaluation précise du flux neutronique dans le coeur du réacteur. Ce flux est modélisé par l’équation de Boltzmann ou équation du transport neutronique. Dans cette thèse, on s’intéresse à la résolution de cette équation par la méthode des ordonnées discrètes (SN) sur des géométries cartésiennes. Cette méthode fait intervenir un schéma d’itérations à source, incluant un algorithme de balayage sur le domaine spatial qui regroupe l’essentiel des calculs effectués. Compte tenu du très grand volume de calcul requis par la résolution de l’équation de Boltzmann, de nombreux travaux antérieurs ont été consacrés à l’utilisation du calcul parallèle pour la résolution de cette équation. Jusqu’ici, ces algorithmes de résolution parallèles de l’équation du transport neutronique ont été conçus en considérant la machine cible comme une collection de processeurs mono-coeurs indépendants, et ne tirent donc pas explicitement profit de la hiérarchie mémoire et du parallélisme multi-niveaux présents sur les super-calculateurs modernes. Ainsi, la première contribution de cette thèse concerne l’étude et la mise en oeuvre de l’algorithme de balayage sur les super-calculateurs massivement parallèles modernes. Notre approche combine à la fois la vectorisation par des techniques de la programmation générique en C++, et la programmation hybride par l’utilisation d’un support d’exécution à base de tâches: PaRSEC. Nous avons démontré l’intérêt de cette approche grâce à des modèles de performances théoriques, permettant également de prédire le partitionnement optimal. Par ailleurs, dans le cas de la simulation des milieux très diffusifs tels que le coeur d’un REP, la convergence du schéma d’itérations à source est très lente. Afin d’accélérer sa convergence, nous avons implémenté un nouvel algorithme (PDSA), adapté à notre implémentation hybride. La combinaison de ces techniques nous a permis de concevoir une version massivement parallèle du solveur SN Domino. Les performances de la partie Sweep du solveur atteignent 33.9% de la performance crête théorique d’un super-calculateur à 768 cores. De plus, un calcul critique d’un réacteur de type REP 900MW à 26 groupes d’énergie mettant en jeu 1012 DDLs a été résolu en 46 minutes sur 1536 coeurs. / High-fidelity nuclear reactor core simulations require a precise knowledge of the neutron flux inside the reactor core. This flux is modeled by the linear Boltzmann equation also called neutron transport equation. In this thesis, we focus on solving this equation using the discrete ordinates method (SN) on Cartesian mesh. This method involves a source iteration scheme including a sweep over the spatial mesh and gathering the vast majority of computations in the SN method. Due to the large amount of computations performed in the resolution of the Boltzmann equation, numerous research works were focused on the optimization of the time to solution by developing parallel algorithms for solving the transport equation. However, these algorithms were designed by considering a super-computer as a collection of independent cores, and therefore do not explicitly take into account the memory hierarchy and multi-level parallelism available inside modern super-computers. Therefore, we first proposed a strategy for designing an efficient parallel implementation of the sweep operation on modern architectures by combining the use of the SIMD paradigm thanks to C++ generic programming techniques and an emerging task-based runtime system: PaRSEC. We demonstrated the need for such an approach using theoretical performance models predicting optimal partitionings. Then we studied the challenge of converging the source iterations scheme in highly diffusive media such as the PWR cores. We have implemented and studied the convergence of a new acceleration scheme (PDSA) that naturally suits our Hybrid parallel implementation. The combination of all these techniques have enabled us to develop a massively parallel version of the SN Domino solver. It is capable of tackling the challenges posed by the neutron transport simulations and compares favorably with state-of-the-art solvers such as Denovo. The performance of the PaRSEC implementation of the sweep operation reaches 6.1 Tflop/s on 768 cores corresponding to 33.9% of the theoretical peak performance of this set of computational resources. For a typical 26-group PWR calculations involving 1.02×1012 DoFs, the time to solution required by the Domino solver is 46 min using 1536 cores.

L’évolution courante des machines montre une croissance importante dans le nombre et l’hétérogénéité des unités de calcul. Les développeurs doivent alors trouver des alternatives aux modèles de programmation habituels permettant de produire des codes de calcul à la fois performants et portables. PaStiX est un solveur parallèle de système linéaire creux par méthodes directe. Il utilise un ordonnanceur de tâche dynamique pour être efficaces sur les machines modernes multi-coeurs à mémoires hiérarchiques. Dans cette thèse, nous étudions les bénéfices et les limites que peut nous apporter le remplacement de l’ordonnanceur interne, très spécialisé, du solveur PaStiX par deux systèmes d’exécution génériques : PaRSEC et StarPU. Pour cela l’algorithme doit être décrit sous la forme d’un graphe de tâches qui est fournit aux systèmes d’exécution qui peuvent alors calculer une exécution optimisée de celui-ci pour maximiser l’efficacité de l’algorithme sur la machine de calcul visée. Une étude comparativedes performances de PaStiX utilisant ordonnanceur interne, PaRSEC, et StarPU a été menée sur différentes machines et est présentée ici. L’analyse met en évidence les performances comparables des versions utilisant les systèmes d’exécution par rapport à l’ordonnanceur embarqué optimisé pour PaStiX. De plus ces implémentations permettent d’obtenir une accélération notable sur les machines hétérogènes en utilisant lesaccélérateurs tout en masquant la complexité de leur utilisation au développeur. Dans cette thèse nous étudions également la possibilité d’obtenir un solveur distribué de système linéaire creux par méthodes directes efficace sur les machines parallèles hétérogènes en utilisant les systèmes d’exécution à base de tâche. Afin de pouvoir utiliser ces travaux de manière efficace dans des codes parallèles de simulations, nous présentons également une interface distribuée, orientée éléments finis, permettant d’obtenir un assemblage optimisé de la matrice distribuée tout en masquant la complexité liée à la distribution des données à l’utilisateur. / The ongoing hardware evolution exhibits an escalation in the number, as well as in the heterogeneity, of computing resources. The pressure to maintain reasonable levels of performance and portability forces application developers to leave the traditional programming paradigms and explore alternative solutions. PaStiX is a parallel sparse direct solver, based on a dynamic scheduler for modern hierarchical manycore architectures. In this thesis, we study the benefits and the limits of replacing the highly specialized internal scheduler of the PaStiX solver by two generic runtime systems: PaRSEC and StarPU. Thus, we have to describe the factorization algorithm as a tasks graph that we provide to the runtime system. Then it can decide how to process and optimize the graph traversal in order to maximize the algorithm efficiency for thetargeted hardware platform. A comparative study of the performance of the PaStiX solver on top of its original internal scheduler, PaRSEC, and StarPU frameworks is performed. The analysis highlights that these generic task-based runtimes achieve comparable results to the application-optimized embedded scheduler on homogeneous platforms. Furthermore, they are able to significantly speed up the solver on heterogeneous environments by taking advantage of the accelerators while hiding the complexity of their efficient manipulation from the programmer. In this thesis, we also study the possibilities to build a distributed sparse linear solver on top of task-based runtime systems to target heterogeneous clusters. To permit an efficient and easy usage of these developments in parallel simulations, we also present an optimized distributed interfaceaiming at hiding the complexity of the construction of a distributed matrix to the user.

Avec les avancées récentes en microélectronique, en traitement numérique et en technologie de communication, les noeuds de réseau de capteurs sans fil (noeud RCSF) deviennent de moins en moins encombrants et coûteux. De ce fait la technologie de RCSF est utilisée dans de larges domaines d’application. Comme les noeuds RCSF sont limités en taille et en coût, ils sont en général équipés d’un petit microcontrôleur de faible puissance de calcul et de mémoire etc. De plus ils sont alimentés par une batterie donc son énergie disponible est limitée. A cause de ces contraintes, la plateforme logicielle d’un RCSF doit consommer peu de mémoire, d’énergie, et doit être efficace en calcul. Toutes ces contraintes rendent les développements de logiciels dédiés au RCSF très compliqués. Aujourd’hui le développement d’un système d’exploitation dédié à la technologie RCSF est un sujet important. En effet avec un système d’exploitation efficient, les ressources matérielles d’une plateforme RCSF peuvent être utilisées efficacement. De plus, un ensemble de services système disponibles permet de simplifier le développement d’une application. Actuellement beaucoup de travaux de recherche ont été menés pour développer des systèmes d’exploitation pour le RCSF tels que TinyOS, Contiki, SOS, openWSN, mantisOS et simpleRTJ. Cependant plusieurs défis restent à relever dans le domaine de système d’exploitation pour le RCSF. Le premier des défis est le développement d’un système d’exploitation temps réel à faible empreinte mémoire dédié au RCSF. Le second défi est de développer un mécanisme permettant d’utiliser efficacement la mémoire et l’énergie disponible d’un RCSF. De plus, comment fournir un développement d’application pour le RCSF reste une question ouverte. Dans cette thèse, un nouveau système d’exploitation hybride, temps réel à énergie efficiente et à faible empreinte mémoire nommé MIROS dédié au RCSF a été développé. Dans MIROS, un ordonnanceur hybride a été adopté ; les deux ordonnanceurs évènementiel et multithread ont été implémentés. Avec cet ordonnanceur hybride, le nombre de threads de MIROS peut être diminué d’une façon importante. En conséquence, les avantages d’un système d’exploitation évènementiel qui consomme peu de ressource mémoire et la performance temps réel d’un système d’exploitation multithread ont été obtenues. De plus, l’allocation dynamique de la mémoire a été aussi réalisée dans MIROS. La technique d’allocation mémoire de MIROS permet l’augmentation de la zone mémoire allouée et le réassemblage des fragments de mémoire. De ce fait, l’allocation de mémoire de MIROS devient plus flexible et la ressource mémoire d’un noeud RCSF peut être utilisée efficacement. Comme l’énergie d’un noeud RCSF est une ressource à forte contrainte, le mécanisme de conservation d’énergie a été implanté dans MIROS. Contrairement aux autres systèmes d’exploitation pour RCSF où la conservation d’énergie a été prise en compte seulement en logiciel, dans MIROS la conservation d’énergie a été prise en compte à la fois en logiciel et en matériel. Enfin, pour fournir un environnement de développement convivial aux utilisateurs, un nouveau intergiciel nommé EMIDE a été développé et intégré dans MIROS. EMIDE permet le découplage d’une application de système. Donc le programme d’application est plus simple et la reprogrammation à distance est plus performante, car seulement les codes de l’application seront reprogrammés. Les évaluations de performance de MIROS montrent que MIROS est un système temps réel à faible empreinte mémoire et efficace pour son exécution. De ce fait, MIROS peut être utilisé dans plusieurs plateformes telles que BTnode, IMote, SenseNode, TelosB et T-Mote Sky. Enfin, MIROS peut être utilisé pour les plateformes RCSF à fortes contraintes de ressources. / With the recent advances in microelectronic, computing and communication technologies, wireless sensor network (WSN) nodes have become physically smaller and more inexpensive. As a result, WSN technology has become increasingly popular in widespread application domains. Since WSN nodes are minimized in physical size and cost, they are mostly restricted to platform resources such as processor computation ability, memory resources and energy supply. The constrained platform resources and diverse application requirements make software development on the WSN platform complicated. On the one hand, the software running on the WSN platform should be small in the memory footprint, low in energy consumption and high in execution efficiency. On the other hand, the diverse application development requirements, such as the real-time guarantee and the high reprogramming performance, should be met by the WSN software. The operating system (OS) technology is significant for the WSN proliferation. An outstanding WSN OS can not only utilize the constrained WSN platform resources efficiently, but also serve the WSN applications soundly. Currently, a set of WSN OSes have been developed, such as the TinyOS, the Contiki, the SOS, the openWSN and the mantisOS. However, many OS development challenges still exist, such as the development of a WSN OS which is high in real-time performance yet low in memory footprint; the improvement of the utilization efficiency to the memory and energy resources on the WSN platforms, and the providing of a user-friendly application development environment to the WSN users. In this thesis, a new hybrid, real-time, energy-efficient, memory-efficient, fault-tolerant and user-friendly WSN OS MIROS is developed. MIROS uses the hybrid scheduling to combine the advantages of the event-driven system's low memory consumption and the multithreaded system's high real-time performance. By so doing, the real-time scheduling can be achieved on the severely resource-constrained WSN platforms. In addition to the hybrid scheduling, the dynamic memory allocators are also realized in MIROS. Differing from the other dynamic allocation approaches, the memory heap in MIROS can be extended and the memory fragments in the MIROS can be defragmented. As a result, MIROS allocators become flexible and the memory resources can be utilized more efficiently. Besides the above mechanisms, the energy conservation mechanism is also implemented in MIROS. Different from most other WSN OSes in which the energy resource is conserved only from the software aspect, the energy conservation in MIROS is achieved from both the software aspect and the multi-core hardware aspect. With this conservation mechanism, the energy cost reduced significantly, and the lifetime of the WSN nodes prolonged. Furthermore, MIROS implements the new middleware software EMIDE in order to provide a user-friendly application development environment to the WSN users. With EMIDE, the WSN application space can be decoupled from the low-level system space. Consequently, the application programming can be simplified as the users only need to focus on the application space. Moreover, the application reprogramming performance can be improved as only the application image other than the monolithic image needs to be updated during the reprogramming process. The performance evaluation works to the MIROS prove that MIROS is a real-time OS which has small memory footprint, low energy cost and high execution efficiency. Thus, it is suitable to be used on many WSN platforms including the BTnode, IMote, SenseNode, TelosB, T-Mote Sky, etc. The performance evaluation to EMIDE proves that EMIDE has less memory cost and low energy consumption. Moreover, it supports small-size application code. Therefore, it can be used on the high resource-constrained WSN platforms to provide a user-friendly development environment to the WSN users.

Cette thèse CIFRE s’inscrit dans le cadre d’une collaboration entre Acta-Mobilier, fabricant de façades laquées haut de gamme, et le Centre de Recherche en Automatique Nancy. L’idée est de tirer parti du concept de Système Contrôlé par le Produit dans un environnement industriel perturbé par de nombreuses boucles de production et par un taux de reprises (non-qualités) non négligeable engendrant des pertes de pièces, le non-respect des délais, des charges de travail instables, etc… le lien impossible entre le produit et un identifiant infotronique rendant en plus la traçabilité difficile. Les travaux sur l’ordonnancement et son optimisation sont freinés par ces perturbations sur la chaîne de production qui rendent les plannings intenables. Le traitement prioritaire des pièces défectueuses permet d’assurer un taux de service qui reste remarquable au regard du pourcentage de pièces à réparer. Mais cela engendre aussi des pertes de pièces qui empêchent la livraison complète de la commande. La problématique scientifique s’articule autour du pilotage des flux dans un contexte de production perturbé par les reprises et de la maîtrise de la qualité en évaluant son impact sur l’engorgement. L’enjeu de maîtrise de la qualité a été abordé à l’aide de réseaux de neurones capables de prévoir l’apparition du défaut auquel ils sont dédiés en fonction des paramètres de production et environnementaux. Cette anticipation permet de proposer une alternative de programme à utiliser ou à reporter la planification de la tâche. L’adaptation du modèle de prévision aux dérives du modèle physique au comportement considéré comme nerveux est réalisée « en-ligne » à l’aide de cartes de contrôle qui permettent de détecter la dérive et sa date de début. Malgré cette simplification des flux, le pilotage reste complexe en raison des boucles normales de production et des non qualités résiduelles. Il existe différents états de saturation du système pour lesquels la règle de pilotage la plus adaptée n’est pas toujours la même. Cette analyse est présentée sous forme de cartographie en deux dimensions dont chacun des axes présente un indicateur clé du taux de non-qualité et/ou de la perturbation des flux. Même si, contrairement aux algorithmes, la règle de pilotage la mieux adaptée ne sera pas toujours mise en évidence, cette cartographie présente d’autres avantages tels que la simplification du pilotage, la possibilité pour tous les utilisateurs d’avoir l’information importante sur l’état de l’atelier en un coup d’oeil, ou encore la nécessité d’homogénéisation sur la globalité de l’unité de production. Dans ce contexte, le container intelligent offre des perspectives intéressantes avec la volonté de tracer un groupe de produits ayant la même gamme de fabrication plutôt que des produits un à un, de partager des informations telles que sa date de livraison, son degré d’urgence, de connaître quels chemins ils doivent emprunter dans l’atelier et quelles sont les alternatives possibles ou encore de communiquer avec les machines et les autres systèmes dont celui de prévision de la qualité et retenir des informations au fil de la fabrication des produits. Le système proposé est donc interactif ou le conteneur est au coeur de la décision. Il signale sa présence au système d’ordonnancement seulement si les conditions qualité sont réunies, permettant ainsi de simplifier son travail autorisant alors un simple algorithme traditionnel de programmation linéaire à réaliser cette tâche particulièrement compliquée au premier abord. C’est en revanche à la charge de l’ordonnanceur de s’assurer de la règle de pilotage à utiliser et de demander les informations correspondantes aux lots disponibles. La contribution de cette thèse est donc une méthodologie de simplification de problèmes complexes par une répartition des tâches entre différents sous-systèmes acteurs appliquée au cas d’une entreprise de fabrication de façades de cuisine laquées haut de gamme / Centre de Recherche en Automatique de Nancy. The idea is to take advantage of Product Driven System in an industrial environment disturbed by many loops and a rework rate (non quality) causing significant loss of products, non-compliance deadlines, unstable workloads, etc ... impossible link between the product and identifying infotronic lead to more difficult traceability. Work on scheduling and optimization are hampered by these disturbances on the production line that make them untenable schedules. Priority processing on defective products ensures a service rate that remains outstanding compared to the percentage of products to repair. But it also leads to loss of products that prevent the full delivery of the order. The scientific problem revolves around the control of flow in a production context disturbed by the loops and the quality level by assessing its impact on congestion. The quality-control issue has been addressed by using neural networks that can predict the occurrence of the defect to which they are dedicated from production and environmental parameters. This anticipation allows us to offer a program alternative to use or to plan to postpone the task. The adaptation of the forecasting model to the drift of the physical model with a behavior regarded as nervous is made "on line" using control charts that detect drift and its start date. Despite this simplification of flows, the flow control remains complex due to normal production loops and residual nonqualities. There are different system saturation states for which the most suitable control rule is not always the same. This analysis is presented in a two-dimensional mapping which each axis has a key indicator on non-quality rate and / or disruption of flows. Although, unlike algorithms, the most suitable control rule will not always be highlighted, this mapping has other advantages such as the simplification of the control, the ability for all users to have important information about the workshop state, or the need for homogenization of the global state of the production unit. In this context, the intelligent container offers interesting perspectives with the will to trace a group of products with the same rooting sheet rather than products one by one, to share information such as its delivery date, the urgency degree, to know what paths they should take and what are the possible alternatives or to communicate with other machines and systems including the quality forecasting system and retain information over the manufacture of the products. The proposed system is so interactive where container is at the heart of the decision. It reported his presence to scheduling system only if the quality system requirements are met, and simplify this work while allowing a traditional linear algorithm to achieve this task seen as particularly complicated at first. It is however the responsibility of the scheduler to ensure the pilot rule to use and request the relevant information available to the lots. The contribution of this thesis is a methodology to simplify complex problems by a division of work between different subsystems actors applied to the case of a manufacturer of high-finished lacquered panels