Les problématiques de sécurité sont aujourd’hui un facteur différentiateur clé dans le secteur aéronautique. Bien que certains systèmes d’assistance aux hélicoptères existent et qu’une partie de la connaissance associée aux situations d’urgence ait pu être identifiée, reste que les travaux antérieurs se limitent pour la plupart à une autonomie de bas niveau. Ainsi la génération d’un plan de vol sous fortes contraintes de temps représente à ce jour une voie d’exploration nouvelle, et un défi technologique essentiel pour l’hélicoptère de demain. A cet égard, AIRBUS HELICOPTERS accorde un fort intérêt à la conception d’un système décisionnel capable de générer des plans de vols en temps réel. L’enjeu de l’intelligence répartie au travers de systèmes décisionnels distribués constitue un axe de recherche fort, et un des contributeurs clés pour un positionnement leader d’AIRBUS HELICOPTERS sur la thématique sécurité. Aujourd’hui, l’étude des systèmes décisionnels embarqués dans les engins volants constitue un défi majeur pour divers groupes de travail académiques et industriels. En effet, la résolution de ce défi fait appel généralement à différentes compétences afin de maîtriser plusieurs aspects du système recouvrant les domaines d’acquisition, d’analyse et de traitement de données. Et ce dans le but de prendre des décisions en temps-réel en prenant en considération plusieurs paramètres contextuels et environnementaux. Les défis scientifiques à contourner dans la présente thèse s’articulent sur deux axes majeurs. Dans un premier temps, il faut proposer une approche complète pour une planification en temps réel d’un plan de vol d’hélicoptères. Permettant à cette dernière de faire face à d’éventuels événements dynamiques tel que l’apparition de nouveaux obstacles ou un changement de mission. Ensuite, nous nous intéressons à une implantation embarquée de la solution proposée sur une architecture hétérogène haute performance. / Security issues are today a key-differentiator in the aviation sector. Indeed, it comes to ensure the safety of expensive equipments but above all to save human lives. In this context, it is necessary to offer an important level of autonomy to helicopters. Although some studies have been carried out in this area, the dynamic generation of a sequence of maneuvers under hard time constraints in an unknown environment still represents a major challenge for many academic and industrial working groups. AIRBUS HELICOPTERS as a leader of helicopters manufacturing, looks forward to integrate an assistance system for mission re-planning in the next generation of aircrafts.The work conducted in this PhD thesis falls within a collaboration between AIRBUS HELICOPTERS and UNIVERSITE DE VALENCIENNES ET DU HAINAUTCAMBRESIS. One of the main purposes of this work is efficient flight plan generation. Indeed, for intelligent assistant systems we need to generate a new path planning inorder to face emergency events such as an equipment failure or adverse weather conditions. The second major objective of this work is the deployment of mission planning tasks onto a high performance architecture CPU/FPGA in order to meet real-time requirements for the dynamic optimization process. In the present work, we first studied efficient flight plan generation. Indeed, we developed efficient and effective algorithms for helicopter path planning. Then, in order to obtain a real-time system, we resolved the problem of scheduling optimization on a heterogeneous architecture CPU / FPGA by proposing several scheduling methods including exact approaches and heuristics.

Le système de fabrication des plaquettes de silicium (wafer) est la partie la plus complexe et la plus coûteuse du processus de fabrication des semi-conducteurs et son ordonnancement pour la production a un impact significatif sur la rentabilité économique. Le système d’outils Multi-cluster pour la fabrication de plaquettes est un système de type multi-boucles, largement utilisé dans la fabrication de plaquettes de 300 mm et 450 mm. Le problème d’ordonnancement dans ce système de production présente des caractéristiques pour les modèles de flux de plaquettes compliqué, des contraintes résidentielles strictes et des conflits de ressources à gérer, ce qui rend le problème très complexe. Dans cette thèse, l'outil multi-cluster est étudié et les recherches se concentrent principalement sur les caractéristiques des contraintes sur le temps de séjour, les contraintes sur les ressources utilisés et les flux plaquettes de silicium. Plus particulièrement, cette thèse traite trois problèmes d'ordonnancement: le problème d'ordonnancement cyclique unitaire pour un flux unique de plaquettes, le problème d'ordonnancement cyclique multi-unitaires dans un modèle de flux unique de plaquettes et le problème d'ordonnancement non-cyclique. Pour résoudre ces problèmes, des modèles robustes sont développés ainsi que certains algorithmes heuristiques efficaces sont construits pour atteindre les objectifs. L'objectif principal étant d'améliorer la performance des outils multi-cluster et d'augmenter le rendement des flux des plaquettes de silicium. Des tests de simulation et des analyses sont effectuées afin d’évaluer la performance des algorithmes proposés. Les résultats montrent la stabilité et l'efficacité de ces algorithmes. / Multi-cluster tool is a highly automated and costly wafer fabrication system with multi-loop coupling structure, and scheduling of such equipment directly affects the overall efficiency of semiconductor manufacturing enterprises. Multi-cluster tools scheduling problem has the features of large scale, complex wafer flow patterns, strict residency time constraints and intense resource conflict, which are significantly different from any other manufacturing system. Since the existing literatures have proved that most of the wafer fabrication systems scheduling problems are NP-hard, it’s difficult to obtain the optimal solution by using exact algorithms. Thus, how to develop an efficient heuristic algorithm to solve the multi-cluster tools scheduling problem attracts considerable attention both in academia and in industry. After reviewing the literatures, it is found that the research on the cyclic scheduling problem of multi-cluster tools rarely takes into account the characteristics of residency constraints. The scale of the object is limited to three single cluster tools, and the proposed scheduling methods are mostly mathematical programming and simple scheduling rules. Therefore, in this thesis, the multi-cluster tool is studied and our research mainly focuses on the characteristics of residency constraints, resource constraints and wafer flow patterns. Based on the descriptions of research domains, some solid models are developed for different scheduling problems and some efficient heuristic algorithms are constructed to realize the objectives. To deal with the problem, different approaches are proposed: A non-linear mixed-integer programming model, a two-stage = approximate-optimal scheduling algorithm, and a chaos-based particle swarm optimization-tabu search hybrid heuristic algorithm. Simulation experiments and analysis demonstrate the effectiveness of these algorithms. Results show the stability and efficiency of proposed algorithms.

La demande croissante pour les services de cloud computing encourage les opérateurs à optimiser l’utilisation des ressources dans les grappes d’ordinateurs. Cela motive le développement de nouvelles technologies qui rendent plus flexible la gestion des ressources. Cependant, exploiter cette flexibilité pour réduire le nombre d’ordinateurs nécessite aussi des algorithmes de gestion des ressources efficaces et dont la performance est prédictible sous une demande stochastique. Dans cette thèse, nous concevons et analysons de tels algorithmes en utilisant le formalisme de la théorie des files d’attente.Notre abstraction du problème est une file multi-serveur avec plusieurs classes de clients. Les capacités des serveurs sont hétérogènes et les clients de chaque classe entrent dans la file selon un processus de Poisson indépendant. Chaque client peut être traité en parallèle par plusieurs serveurs, selon des contraintes de compatibilité décrites par un graphe biparti entre les classes et les serveurs, et chaque serveur applique la politique premier arrivé, premier servi aux clients qui lui sont affectés. Nous prouvons que, si la demande de service de chaque client suit une loi exponentielle indépendante de moyenne unitaire, alors la performance moyenne sous cette politique simple est la même que sous l’équité équilibrée, une extension de processor-sharing connue pour son insensibilité à la loi de la demande de service. Une forme plus générale de ce résultat, reliant les files order-independent aux réseaux de Whittle, est aussi prouvée. Enfin, nous développons de nouvelles formules pour calculer des métriques de performance.Ces résultats théoriques sont ensuite mis en pratique. Nous commençons par proposer un algorithme d’ordonnancement qui étend le principe de round-robin à une grappe où chaque requête est affectée à un groupe d’ordinateurs par lesquels elle peut ensuite être traitée en parallèle. Notre seconde proposition est un algorithme de répartition de charge à base de jetons pour des grappes où les requêtes ont des contraintes d’affectation. Ces deux algorithmes sont approximativement insensibles à la loi de la taille des requêtes et s’adaptent dynamiquement à la demande. Leur performance peut être prédite en appliquant les formules obtenues pour la file multi-serveur. / The growing demand for cloud-based services encourages operators to maximize resource efficiency within computer clusters. This motivates the development of new technologies that make resource management more flexible. However, exploiting this flexibility to reduce the number of computers also requires efficient resource-management algorithms that have a predictable performance under stochastic demand. In this thesis, we design and analyze such algorithms using the framework of queueing theory.Our abstraction of the problem is a multi-server queue with several customer classes. Servers have heterogeneous capacities and the customers of each class enter the queue according to an independent Poisson process. Each customer can be processed in parallel by several servers, depending on compatibility constraints described by a bipartite graph between classes and servers, and each server applies first-come-first-served policy to its compatible customers. We first prove that, if the service requirements are independent and exponentially distributed with unit mean, this simple policy yields the same average performance as balanced fairness, an extension to processor-sharing known to be insensitive to the distribution of the service requirements. A more general form of this result, relating order-independent queues to Whittle networks, is also proved. Lastly, we derive new formulas to compute performance metrics.These theoretical results are then put into practice. We first propose a scheduling algorithm that extends the principle of round-robin to a cluster where each incoming job is assigned to a pool of computers by which it can subsequently be processed in parallel. Our second proposal is a load-balancing algorithm based on tokens for clusters where jobs have assignment constraints. Both algorithms are approximately insensitive to the job size distribution and adapt dynamically to demand. Their performance can be predicted by applying the formulas derived for the multi-server queue.

La demande croissante pour les services de cloud computing encourage les opérateurs à optimiser l’utilisation des ressources dans les grappes d’ordinateurs. Cela motive le développement de nouvelles technologies qui rendent plus flexible la gestion des ressources. Cependant, exploiter cette flexibilité pour réduire le nombre d’ordinateurs nécessite aussi des algorithmes de gestion des ressources efficaces et dont la performance est prédictible sous une demande stochastique. Dans cette thèse, nous concevons et analysons de tels algorithmes en utilisant le formalisme de la théorie des files d’attente.Notre abstraction du problème est une file multi-serveur avec plusieurs classes de clients. Les capacités des serveurs sont hétérogènes et les clients de chaque classe entrent dans la file selon un processus de Poisson indépendant. Chaque client peut être traité en parallèle par plusieurs serveurs, selon des contraintes de compatibilité décrites par un graphe biparti entre les classes et les serveurs, et chaque serveur applique la politique premier arrivé, premier servi aux clients qui lui sont affectés. Nous prouvons que, si la demande de service de chaque client suit une loi exponentielle indépendante de moyenne unitaire, alors la performance moyenne sous cette politique simple est la même que sous l’équité équilibrée, une extension de processor-sharing connue pour son insensibilité à la loi de la demande de service. Une forme plus générale de ce résultat, reliant les files order-independent aux réseaux de Whittle, est aussi prouvée. Enfin, nous développons de nouvelles formules pour calculer des métriques de performance.Ces résultats théoriques sont ensuite mis en pratique. Nous commençons par proposer un algorithme d’ordonnancement qui étend le principe de round-robin à une grappe où chaque requête est affectée à un groupe d’ordinateurs par lesquels elle peut ensuite être traitée en parallèle. Notre seconde proposition est un algorithme de répartition de charge à base de jetons pour des grappes où les requêtes ont des contraintes d’affectation. Ces deux algorithmes sont approximativement insensibles à la loi de la taille des requêtes et s’adaptent dynamiquement à la demande. Leur performance peut être prédite en appliquant les formules obtenues pour la file multi-serveur. / The growing demand for cloud-based services encourages operators to maximize resource efficiency within computer clusters. This motivates the development of new technologies that make resource management more flexible. However, exploiting this flexibility to reduce the number of computers also requires efficient resource-management algorithms that have a predictable performance under stochastic demand. In this thesis, we design and analyze such algorithms using the framework of queueing theory.Our abstraction of the problem is a multi-server queue with several customer classes. Servers have heterogeneous capacities and the customers of each class enter the queue according to an independent Poisson process. Each customer can be processed in parallel by several servers, depending on compatibility constraints described by a bipartite graph between classes and servers, and each server applies first-come-first-served policy to its compatible customers. We first prove that, if the service requirements are independent and exponentially distributed with unit mean, this simple policy yields the same average performance as balanced fairness, an extension to processor-sharing known to be insensitive to the distribution of the service requirements. A more general form of this result, relating order-independent queues to Whittle networks, is also proved. Lastly, we derive new formulas to compute performance metrics.These theoretical results are then put into practice. We first propose a scheduling algorithm that extends the principle of round-robin to a cluster where each incoming job is assigned to a pool of computers by which it can subsequently be processed in parallel. Our second proposal is a load-balancing algorithm based on tokens for clusters where jobs have assignment constraints. Both algorithms are approximately insensitive to the job size distribution and adapt dynamically to demand. Their performance can be predicted by applying the formulas derived for the multi-server queue.

La demande croissante pour les services de cloud computing encourage les opérateurs à optimiser l’utilisation des ressources dans les grappes d’ordinateurs. Cela motive le développement de nouvelles technologies qui rendent plus flexible la gestion des ressources. Cependant, exploiter cette flexibilité pour réduire le nombre d’ordinateurs nécessite aussi des algorithmes de gestion des ressources efficaces et dont la performance est prédictible sous une demande stochastique. Dans cette thèse, nous concevons et analysons de tels algorithmes en utilisant le formalisme de la théorie des files d’attente.Notre abstraction du problème est une file multi-serveur avec plusieurs classes de clients. Les capacités des serveurs sont hétérogènes et les clients de chaque classe entrent dans la file selon un processus de Poisson indépendant. Chaque client peut être traité en parallèle par plusieurs serveurs, selon des contraintes de compatibilité décrites par un graphe biparti entre les classes et les serveurs, et chaque serveur applique la politique premier arrivé, premier servi aux clients qui lui sont affectés. Nous prouvons que, si la demande de service de chaque client suit une loi exponentielle indépendante de moyenne unitaire, alors la performance moyenne sous cette politique simple est la même que sous l’équité équilibrée, une extension de processor-sharing connue pour son insensibilité à la loi de la demande de service. Une forme plus générale de ce résultat, reliant les files order-independent aux réseaux de Whittle, est aussi prouvée. Enfin, nous développons de nouvelles formules pour calculer des métriques de performance.Ces résultats théoriques sont ensuite mis en pratique. Nous commençons par proposer un algorithme d’ordonnancement qui étend le principe de round-robin à une grappe où chaque requête est affectée à un groupe d’ordinateurs par lesquels elle peut ensuite être traitée en parallèle. Notre seconde proposition est un algorithme de répartition de charge à base de jetons pour des grappes où les requêtes ont des contraintes d’affectation. Ces deux algorithmes sont approximativement insensibles à la loi de la taille des requêtes et s’adaptent dynamiquement à la demande. Leur performance peut être prédite en appliquant les formules obtenues pour la file multi-serveur. / The growing demand for cloud-based services encourages operators to maximize resource efficiency within computer clusters. This motivates the development of new technologies that make resource management more flexible. However, exploiting this flexibility to reduce the number of computers also requires efficient resource-management algorithms that have a predictable performance under stochastic demand. In this thesis, we design and analyze such algorithms using the framework of queueing theory.Our abstraction of the problem is a multi-server queue with several customer classes. Servers have heterogeneous capacities and the customers of each class enter the queue according to an independent Poisson process. Each customer can be processed in parallel by several servers, depending on compatibility constraints described by a bipartite graph between classes and servers, and each server applies first-come-first-served policy to its compatible customers. We first prove that, if the service requirements are independent and exponentially distributed with unit mean, this simple policy yields the same average performance as balanced fairness, an extension to processor-sharing known to be insensitive to the distribution of the service requirements. A more general form of this result, relating order-independent queues to Whittle networks, is also proved. Lastly, we derive new formulas to compute performance metrics.These theoretical results are then put into practice. We first propose a scheduling algorithm that extends the principle of round-robin to a cluster where each incoming job is assigned to a pool of computers by which it can subsequently be processed in parallel. Our second proposal is a load-balancing algorithm based on tokens for clusters where jobs have assignment constraints. Both algorithms are approximately insensitive to the job size distribution and adapt dynamically to demand. Their performance can be predicted by applying the formulas derived for the multi-server queue.

Les réseaux logiciels (Software Defined Network - SDN) permettent la programmation du réseau et facilitent sa configuration. Bien qu'SDN améliore les performances, il reste confronté à de multiples défis. Dans cette thèse, nous avons développé des solutions qui constituent un premier pas vers les réseaux SDN de prochaine génération. D’abord, nous présentons MINNIE qui permet la scalabilité des commutateurs SDN, qui ne supportent que quelques milliers de règles dans leur coûteuse mémoire TCAM. MINNIE comprime dynamiquement les règles de routage installées dans la TCAM, augmentant ainsi le nombre de règles pouvant être installées. Ensuite, nous abordons le problème de la dégradation de performance des flux courts avec un prototype d’ordonnancement qui exploite les statistiques des commutateurs pour diminuer leur délai de bout-en-bout. Puis, nous visons à diminuer l’intervalle de protection de 50ms qui n’est plus adapté aux applications modernes et réduit leur qualité d’expérience. Notre solution PRoPHYS s’appuie sur les statistiques des commutateurs dans les réseaux hybrides pour découvrir les pannes de liens plus vite que les solutions existantes. Enfin, nous abordons le problème de l’efficacité énergétique qui souvent mène à une dégradation de performance. Nous présentons SENAtoR, qui exploite les nœuds SDN en réseaux hybrides pour éteindre les nœuds réseau sans entraver la performance. Également, nous présentons SEaMLESS qui convertit le service fourni par une machine virtuelle inactive en une fonction de réseaux virtuelle pour permettre à l’administrateur d’utiliser les ressources bloquées tout en maintenant la disponibilité du service. / Software Defined Networking (SDN) was created to provide network programmability and ease complex configuration. Though SDN enhances network performance, it still faces multiple limitations. In this thesis, we build solutions that form a first step towards creating next-generation SDN based networks. In the first part, we present MINNIE to scale the number of rules of SDN switches far beyond the few thousands rules commonly available in TCAM memory, which permits to handle typical data center traffic at very fine grain. To do so MINNIE dynamically compresses the routing rules installed in the TCAM, increasing the number of rules that can be installed. In the second part, we tackle the degraded performance of short flows and present a coarse grained scheduling prototype that leverages SDN switch statistics to decrease their end-to-end delay. Then, we aim at decreasing the 50ms failure protection interval which is not adapted to current broadband speeds and can lead to degraded Quality of Experience. Our solution PRoPHYS leverages the switch statistics in hybrid networks to anticipate link failures by drastically decreasing the number of packets lost. Finally, we tackle the greening problem where often energy efficiency comes at the cost of performance degradation. We present SENAtoR, our solution that leverages SDN nodes in hybrid networks to turn off network devices without hindering the network performance. Finally, we present SEaMLESS that converts idle virtual machines into virtual network functions (VNF) to enable the administrator to further consolidate the data center by turning off more physical servers and reuse resources (e.g. RAM) that are otherwise monopolized.

De part leur capacité de reconfiguration et les performances qu’ils offrent, les FPGAs sont de bons candidats pour accélérer des applications dans le Cloud. Cependant, les FPGAs présentent certaines caractéristiques qui font obstacle à leur utilisation dans le Cloud et leur adoption par les clients : premièrement, la programmation des FPGAs se fait à bas niveau et demande une certaine expertise, que n’ont pas nécessairement les clients habituels du Cloud. Deuxièmement, les FPGAs ne présentent pas de mécanismes natifs permettant leur intégration dans le modèle de gestion dynamique d’une infrastructure Cloud.Dans ce travail, nous proposons d’utiliser des architectures overlay afin de faciliter l’adoption, l’intégration et l’exploitation de FPGAs dans le Cloud. Les overlays sont des architectures reconfigurables elles-mêmes implémentée sur FPGA. En tant que couche d’abstraction matérielle placée entre le FPGA et les applications, les overlays permettent de monter le niveau d’abstraction du modèle d’exécution présenté aux applications et aux utilisateurs, ainsi que d’implémenter des mécanismes facilitant leur intégration et leur exploitation dans une infrastructure Cloud.Ce travail présente une approche verticale adressant tous les aspects de la mise en œuvre d’overlays dans le Cloud en tant qu’accélérateurs reconfigurables par les clients : de la conception et l’implémentation des overlays, leur intégration sur des plateformes FPGA commerciales, la mise en place de leurs mécanismes d’exploitation, jusqu’à la réalisationde leurs outils de programmation. L’environnement réalisé est complet, modulaire et extensible, il repose en partie sur différents outils existants, et démontre la faisabilité de notre approche. / Due to their reconfigurable capability and the performance they offer, FPGAs are good candidates for accelerating applications in the cloud. However, FPGAs have some features that hinder their use in the Cloud as well as their adoption by customers : first, FPGA programming is done at low level and requires some expertise that usual Cloud clients do not necessarily have. Secondly, FPGAs do not have native mechanisms allowing them to easily fit in the dynamic execution model of the Cloud.In this work, we propose to use overlay architectures to facilitate FPGA adoption, integration, and operation in the Cloud. Overlays are reconfigurable architectures synthesized on FPGA. As hardware abstraction layers placed between the FPGA and applications, overlays allow to raise the abstraction level of the execution model presented to applications and users, as well as to implement mechanisms making them fit in a Cloud infrastructure.This work presents a vertical approach addressing all aspects of overlay operation in the Cloud as reconfigurable accelerators programmable by tenants : from designing and implementing overlays, integrating them on commercial FPGA platforms, setting up their operating mechanisms, to developping their programming tools. The environment developped in this work is complete, modular and extensible, it is partially based on several existing tools, and demonstrate the feasibility of our approach.

Certaines applications industrielles nécessitent des délais de collecte déterministes et bornés, nous nous concentrons sur l'allocation conjointe de slots temporels et de canaux sans conflit qui minimisent la durée de collecte. Cette allocation permet aux noeuds de dormir dans n'importe quel slot où ils ne sont pas impliqués dans des transmissions. Nous calculons le nombre minimal de slots temporels nécessaire pour compléter la collecte de données brute pour un puits équipé de plusieurs interfaces radio et des demandes de trafic hétérogènes. Nous donnons également des ordonnancements optimaux qui permettent d'atteindre ces bornes optimales. Nous proposons ensuite MODESA, un algorithme centralisé d'allocation conjointe de slots et de canaux. Nous montrons l'optimalité de MODESA dans des topologies particulières. Par les simulations, nous montrons que MODESA surpasse TMCP , un ordonnancement centralisé à base de sous-arbre. Nous améliorons MODESA avec différentes stratégies d'allocation de canaux. En outre , nous montrons que le recours à un routage multi-chemins réduit le délai de collecte.Néanmoins, l'allocation conjointe de slot et de canaux doit être capable de s'adapter aux changements des demandes des noeuds (des alarmes, des demandes de trafic supplémentaires temporaires). Nous proposons AMSA , une solution d'assignation conjointe de slots et de canaux basée sur une technique incrémentale. Pour aborder la question du passage à l'échelle, nous proposons, WAVE , une solution d'allocation conjointe de slots et de canaux qui fonctionne en mode centralisé ou distribué. Nous montrons l'équivalence des ordonnancements fournis par les deux modes. / Some industrial applications require deterministic and bounded gathering delays. We focus on the joint time slots and channel assignment that minimizes the time of data collection and provides conflict-free schedules. This assignment allows nodes to sleep in any slot where they are not involved in transmissions. Hence, these schedules save the energy budjet of sensors. We calculate the minimum number of time slots needed to complete raw data convergecast for a sink equipped with multiple radio interfaces and heterogeneous nodes traffic. We also give optimal schedules that achieve the optimal bounds. We then propose MODESA, a centralized joint slots and channels assignment algorithm. We prove the optimality of MODESA in specific topologies. Through simulations, we show that MODESA is better than TMCP, a centralized subtree based scheduling algorithm. We improve MODESA with different strategies for channels allocation. In addition, we show that the use of a multi-path routing reduces the time of data collection .Nevertheless, the joint time slot and channels assignment must be able to adapt to changing traffic demands of the nodes ( alarms, additional requests for temporary traffic ) . We propose AMSA , an adaptive joint time slots and channel assignment based on incremental technical solution. To address the issue of scalability, we propose, WAVE, a distributed scheduling algorithm for convergecat that operates in centralized or distributed mode. We show the equivalence of schedules provided by the two modes.

La complexité croissante des applications embarquées dans les voitures modernes augmente le besoin de puissance de calcul. Pour répondre à ce besoin, le standard automobile AUTOSAR introduit l'utilisation de plates-formes multi-cœurs. Cependant, l'utilisation du multi-cœurs pour des applications temps-réel critique automobile soulève plusieurs problématiques. Notamment, il faut respecter la spécification fonctionnelle et garantir de manière déterministe les échanges de données entre cœurs. Dans cette thèse, nous considérons des systèmes multi-périodiques spécifiés et validés fonctionnellement avec des modèles Matlab/Simulink. Ainsi, nous avons développé un framework pour déployer des applications Matlab/Simulink sur AUTOSAR multi-cœurs afin de garantir le déterminisme fonctionnel et temporel tout en exploitant au mieux le parallélisme. Notre contribution a porté sur trois axes. Premièrement nous avons identifié les mécanismes d'échanges de données imposés dans le modèle fonctionnel Matlab/Simulink. Nous avons montré que ces mécanismes pouvaient s'exprimer en utilisant le formalisme des Synchronous Dataflow Graph (SDFG). Ce modèle est un excellent outil d'analyse pour exploiter le parallélisme car il est très populaire dans la littérature et largement étudié pour le déploiement d'applications flow de données sur plateforme multi/many-cœurs. Par la suite, nous avons développé des méthodes pour réaliser le flux de données exprimés par le SDFG dans un ordonnancement temps-réel préemptif. Ces méthodes utilisent des résultats théoriques sur les SDFGs pour garantir les contraintes de précédence de manière déterministe sans utiliser des mécanismes de synchronisation bloquants. De cette sorte, nous garantissons à la fois le déterminisme fonctionnel et temporel des applications. Finalement, nous caractérisons l'impact des contraintes de flux de données sur l'ordonnancement des tâches. Nous proposons une technique de partitionnement qui minimise cet impact. Nous montrons alors que cette technique favorise la construction d'un partitionnement et d'un ordonnancement lorsqu'elle est utilisée pour initialiser des algorithmes de recherche et d'optimisation heuristiques. / The increasing complexity of embedded applications in modern cars has increased the need of computing power. To meet this need, the European automotive standard AUTOSAR has introduced the use of \multicore platforms. However, \multicore platform for critical automotive applications raises several issues. In particular, it is necessary to respect the functional specification and to guarantee deterministically the data exchanges between cores. In this thesis, we consider multi-periodic systems specified and validated with \mat. So, we developed a framework to deploy \mat applications on AUTOSAR \multicore. This framework guarantees the functional and temporal determinism and exploits the parallelism. Our contribution is threefold. First, we identify the communication mechanisms in \mat. Then, we prove that the dataflow in a multi-periodic \mat system is modeled by a SDFG. The SDFG formalism is an excellent analysis tool to exploit the parallelism. In fact, it is very popular in the literature and it is widely studied for the deployment of dataflow applications on multi/many-core. Then, we develop methods to realize the dataflow expressed by the SDFG in a preemptive \rt scheduling. These methods use theoretical results on SDFGs to guarantee deterministic precedence constraints without using blocking synchronization mechanisms. As such, both the functional and temporal determinism are guaranteed. Finally, we characterize the impact of dataflow requirements on tasks. We propose a partitioning technique that minimizes this impact. We show that this technique promotes the construction of a partitioning and a feasible scheduling when it is used to initiate multi-objective research and optimization algorithms. %As such, we reduce the number of design iterations and shorten the design time.

Réduire la consommation énergétique des systèmes temps réel embarqués multiprocesseurs est devenu un enjeu important notammentpour augmenter leur autonomie. Nous réduisons la consommation statique des processeurs en exploitant leurs états basseconsommation. Dans un état basse-consommation, la consommation énergétique est fortement réduite mais un délai de transition et une pénalité sont nécessaires pour revenir à l'état actif. Nous proposons dans cette thèse les premiers algorithmes d'ordonnancement tempsréel multiprocesseurs optimaux pour réduire la consommation énergétique des systèmes temps réel dur et des systèmes temps réel àcriticité mixte. Ces algorithmes d'ordonnancement permettent d'activer les état basse-consommation les plus économes en énergie.Chaque algorithme d'ordonnancement est divisé en deux parties. La première partie hors-ligne génère un ordonnancement en utilisant laprogrammation linéaire en nombres entiers pour minimiser la consommation énergétique. La seconde partie est en-ligne et augmente lataille des périodes d'inactivité les tâches terminent leur exécution plus tôt que prévu. Dans le cadre des systèmes temps réel à criticitémixte, nous profitons du fait que les tâches de plus faible criticité peuvent tolérer des dépassements d'échéances pour être plus agressifhors-ligne afin de réduire davantage la consommation énergétique. Les résultats montrent que les algorithmes proposés utilisent demanière plus efficace les états basse-consommation. La consommation énergétique lorsque ceux-ci sont activés est en effet jusqu'à dix fois plus faible qu'avec les algorithmes d'ordonnancement multiprocesseurs existants. / Reducing the energy consumption of multiprocessor real-time embedded systems is a growing concern to increase their autonomy. In thisthesis, we aim to reduce the energy consumption of the processors, it includes both static and dynamic consumption and it is nowdominated by static consumption as the semiconductor technology moves to deep sub-micron scale. Existing solutions mainly focused ondynamic consumption. On the other hand, we target static consumption by efficiently using the low-power states of the processors. In alow-power state, the processor is not active and the deeper the low-power state is, the lower is the energy consumption but the higher isthe transition delay to come back to the active state. In this thesis, we propose the first optimal multiprocessor real-time schedulingalgorithms minimizing the static energy consumption. They optimize the duration of the idle periods to activate the most appropriate lowpowerstates. We target hard real-time systems with periodic tasks and also mixed-criticality systems where tasks with lower criticalitiescan tolerate deadline misses, therefore allowing us to be more aggressive while trying to reduce the energy consumption. We use anadditional task to model the idle time and mixed integer linear programming to compute offline a schedule minimizing the energyconsumption. Evaluations have been performed using existing optimal multiprocessor real-time scheduling algorithms. Results show thatthe energy consumption while processors are idle is up to ten times reduced with our solutions compared to the existing multiprocessor real-time scheduling algorithms.