Cette thèse se focalise sur le développement des algorithmes d’ordonnancement sous contrainte (m, k)-firm, ainsi que leurs applications pour la gestion de la qualité de service (QdS) dans les réseaux et systèmes temps réel distribués. L’objectif recherché est la garantie déterministe de la QdS tout en maintenant un fort taux d’utilisation des ressources. Les contributions sont (1) l’établissement d’une condition suffisante d’ordonnançabilité d'un ensemble de tâches sous l’algorithme « distance based priority »; (2) la définition de R-(m, k)-firm, un nouveau modèle qui relâche la contrainte (m, k)-firm et qui permet de modéliser de façon plus juste des exigences du temps réel souple; (3) le développement d’un algorithme efficace de dimensionnement de ressources sous contrainte (m, k)-firm relâchée; (4) la proposition de « Double Leaks Bucket » pour la gestion active de files d'attente permettant de maintenir une QdS en cas de surcharge des réseaux / This work focuses on the scheduling algorithms under (m,k)-firm constraint, as well as the applications for QoS (quality of service) management in the networks and distributed real-time system. The research aim is to achieve the deterministic guarantee of QoS with high resource utilization. The contributions in this thesis include (1) proposing a sufficient condition for determining the schedulability of a real-time task set under Distance Base Priority scheduling algorithm; (2) defining a novel real-time constraint which relaxes the (m,k)-firm constraint and provides a more suitable modelling of soft real-time; (3) developing an effective resource provisioning algorithm under this relaxed (m,k)-firm constraint; (4) proposing an active queue management mechanism, called Double Leaks Bucket, which can guarantee the QoS with dynamic dropping of the packets during the networks overload period

Cette thèse s'intéresse aux architectures contenant des FPGAs reconfigurables dynamiquement et partiellement. Dans ces architectures, la complexité et la difficulté de portage des applications sont principalement dues aux connections étroites entre la gestion de la reconfiguration et le calcul lui-même. Nous proposons 1) un nouveau niveau d'abstraction, appelé gestionnaire de composants matériels (HCM) et 2) un mécanisme de communication scalable (SCM), qui permettent une séparation claire entre l'allocation d'une fonction matérielle et la procédure de reconfiguration. Cela réduit l'impact de la gestion de la reconfiguration dynamique sur le code de l'application, ce qui simplifie grandement l'utilisation des plateformes FPGA. Les application utilisant le HCM et le SCM peuvent aussi être portées de manière transparentes à des systèmes multi-FPGA et/ou multi-utilisateurs. L'implémentation de cette couche HCM et du mécanisme SCM sur des plateformes réalistes de prototypage virtuel démontre leur capacité à faciliter la gestion du FPGA tout en préservant les performances d'une gestion manuelle, et en garantissant la protection des fonctions matérielles. L'implémentation du HCM et du mécanisme SCM ainsi que leur environnement de simulation sont open-source dans l'espoir d'une réutilisation par la communauté. / This thesis shows that in FPGA-based dynamic reconfigurable architectures, the complexity and low portability of application developments are mainly due to the tight connections between reconfiguration management and computation. By proposing 1) a new abstraction layer, called Hardware Component Manager (HCM) and 2) a Scalable Communication Mechanism (SCM), we clearly separate the allocation of a hardware function from the control of a reconfiguration procedure. This reduces the dynamic reconfiguration management impact on the application code, which greatly simplifies the use of FPGA platforms. Applications using the HCM and the SCM can also be transparently ported to multi-user and/or multi-FPGA systems. The implementation of this HCM layer and the SCM mechanism on realistic simulation platforms demonstrates their ability to ease the management of FPGA flexibility while preserving performance and ensuring hardware function protection. The HCM and SCM implementations and their simulation environment are open-source in the hope of reuse by the community.

Dans cette thèse nous développons de nouvelles techniques pour résoudre les problèmes d'optimisation multi-critère. Ces problèmes se posent naturellement dans de nombreux domaines d'application (sinon tous) où les choix sont évalués selon différents critères conflictuels (coûts et performance par exemple). Contrairement au cas de l'optimisation classique, de tels problèmes n'admettent pas en général un optimum unique mais un ensemble de solutions incomparables, aussi connu comme le front de Pareto, qui représente les meilleurs compromis possibles entre les objectifs conflictuels. La contribution majeure de la thèse est le développement d'algorithmes pour trouver ou approximer ces solutions de Pareto pour les problèmes combinatoires difficiles. Plusieurs problèmes de ce type se posent naturellement lors du processus de placement et d'ordonnancement d'une application logicielle sur une architecture multi-coeur comme P2012, qui est actuellement développé par STMicroelectronics. / In this thesis we develop new techniques for solving multi-criteria optimization problems. Such problems arise naturally in many (if not all) application domains where choices are evaluated according to two or more conflicting criteria such as price vs. performance. Unlike ordinary optimization, such problems typically do not admit a unique optimum but a set of incomparable solutions, also known as the Pareto Front, which represent the best possible trade-offs between the conflicting goals. The major contribution of the thesis is the development of algorithms for finding or approximating these Pareto solutions for hard combinatorial problems that arise naturally in the process of mapping and scheduling application software on multi-core architectures such as P2012 which is currently being developed by ST Microelectronics.

La méthode multipôle permet d'accélérer les produits matrices-vecteurs, utilisés par les solveurs itératifs pour déterminer le comportement électromagnétique, d'un objet soumis à une onde incidente. Nos travaux ont pour but d'adapter cette méthode pour la rendre efficace sur les architectures hétérogènes contenant des GPU. Pour cela, nous utilisons une ordonnanceur dynamique, StarPU, qui effectuera la distribution des tâches de calcul au sein d'un nœud. Pour la parallélisation en mémoire distribuée, nous effectuerons un ordonnancement statique des boîtes, couplé à un ordonnancement dynamique des interactions proches. / The Fast Multipole Method can speed up matrix-vector products, found in iterative solvers in order to compute the electromagnetics response of an object subject to an incident wave. We have intended to adapt this method to make it effective on heterogeneous architectures with GPUs. For this purpose, we use a dynamic scheduler named StarPU, which distributes the tasks within a node. For the parallelization in distributed memory, we distribute the tasks statically but we distribute the near interactions dynamically..

La forte croissance du trafic dans les réseaux mobiles s'accompagne d'une augmentation de son hétérogénéité, tant dans l'espace qu'au cours du temps. Cette thèse porte sur des algorithmes d’ordonnancement adaptés à des trafics avec des zones à forte concentration et variables dans le temps. Nous proposons un mécanisme de prêt de la ressource spectrale d'une cellule en sous-charge à une voisine en surcharge combinée à un ordonnancement réactif au sein de chaque cellule. Nous nous intéressons aussi à l’architecture Cloud Radio Access Network qui sépare les têtes de transmission radio (Remote Radio Heads, RRHs) des unités de traitement en bande de base (Baseband Units, BBUs). L’interconnexion entre les BBUs et les RRHs se fait selon deux modes. Le premier est appelé association bi-univoque et consiste à allouer les unités de ressources de la trame radio d’une BBU à une seule RRH. Dans le second mode, appelé association multiple, une BBU peut gérer plusieurs RRHs. Nous proposons un mode d’association hybride dans lequel les unités de ressource de chaque trame sont réparties en deux tranches. La première constitue une tranche non partagée qui est allouée aux utilisateurs centraux selon l’association bi-univoque afin d’augmenter le débit notamment à haute charge de trafic. La deuxième tranche est constituée par une quantité d’unités de ressources partagées par un groupe de RRHs appartenant au même BBU. Cette tranche commune est configurée en association multiple et est allouée aux utilisateurs frontaliers et mobiles. Nous montrons que le mode hybride réduit les interférences intercellulaires, diminue le nombre de handover inter-BBU et améliore la consommation énergétique. / The exponential growth of traffic in mobile networks is accompanied by an increase in its heterogeneity, both in space and over time. This thesis deals with scheduling algorithms adapted to highly concentrated and time-varying traffic zones. We propose a spectrum borrowing mechanism from an under-loaded cell to an overloaded one combined with a reactive intra-cellular scheduling algorithm. We are also interested in the Cloud Radio Access Network architecture that separates the Radio Head(RRH) from the Baseband Unit (BBU). The BBU is connected to the RRU according to two modes. The first one is called a one-to-one association and consists in allocating the resource units of the BBU radio frame to a single RRH. In the second mode which is called multiple association, a BBU can handle multiple RRHs. We propose a hybrid association mode in which the resource units of each frame are divided into two slices. The first one constitutes an unshared slice and is allocated to central users according to the one-to-one association in order to increase the throughput, especially at high traffic load. The second slice contains a quantity of resource units that are shared by a group of RRHs belonging to the same BBU. This common slice is configured according to the multiple association mode and is allocated to the edge and mobile users. We show that the hybrid mode reduces the inter-cell interferences, decreases the number of inter-BBU handovers and improves the energy consumption.

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d’origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d’ordonnancement cumulatif. Un problème d’ordonnancement consiste à déterminer les dates de débuts et de fins d’un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l’on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l’on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l’aide d’algorithmes dédiés et de métaheuristiques. Par exemple, l’utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d’ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l’idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d’accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appelées à chaque nœud de l’arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d’un million de tâches et 64 ressources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes déplacement et d’ordonnancement. / Constraint programming is an approach often used to solve combinatorial problems in different application areas. In this thesis we focus on the cumulative scheduling problems. A scheduling problem is to determine the starting dates of a set of tasks while respecting capacity and precedence constraints. Capacity constraints affect both conventional cumulative constraints where the sum of the heights of tasks intersecting a given time point is limited, and colored cumulative constraints where the number of distinct colors assigned to the tasks intersecting a given time point is limited. A newly identified challenge for constraint programming is to deal with large problems, usually solved by dedicated algorithms and metaheuristics. For example, the increasing use of virtualized datacenters leads to multi dimensional placement problems of thousand of jobs. Scalability is achieved by using a synchronized sweep algorithm over the different cumulative and precedence constraints that allows to speed up convergence to the fix point. In addition, from these filtering algorithms we derive greedy procedures that can be called at each node of the search tree to find a solution more quickly. This approach allows to deal with scheduling problems involving more than one million jobs and 64 cumulative resources. These algorithms have been implemented within Choco and SICStussolvers and evaluated on a variety of placement and scheduling problems.

La gestion d’une plate-forme selon une stratégie de cross dock est un processus logistique efficace et dynamique qui vise à transférer directement les produits d'un fournisseur à un client. Cette thèse aborde les problèmes d'affectation aux portes et de gestion des ressources sous contraintes de fenêtres du temps dans un cross dock spécifique. Les problèmes sont formulés comme des modèles de programmation mathématique mixte (MIP). L’objectif est de minimiser la somme de la distance parcourue dans l’entrepôt et du coût qui contient les coûts liés aux ressources et un coût de pénalité. Une heuristique basée sur les algorithmes génétiques est proposée pour résoudre ce problème. Deux méthodes de réparation des gènes sont décrites pour rendre les solutions irréalisables réalisables. Les résultats montrent que l’algorithme génétique surpasse la résolution du modèle MIP à l’aide du solveur CPLEX en un temps donné, pour des instances de taille moyenne et de grande taille. Afin de décrire le comportement et de recueillir des informations pertinentes sur la gestion en cross docks, nous proposons un modèle basé sur réseau de Pétri. Un modèle par réseau de Pétri est construit et la simulation est réalisée avec le logiciel Tina. Par simulation, avec différents nombres de ressources, nous obtenons des temps pertinents pour améliorer les fenêtres de temps originales, le makespan de chacun des postes de travail, l'intervalle de temps libre dans le cross dock et la quantité de ressources disponible à chaque période de temps, ce qui peut fournir des conseils utiles à la gestion des ressources. A partir des résultats de la simulation, la formulation MIP est améliorée. / Cross docking is an efficient and dynamic logistic process that directly transfers goods from a supplier to a customer. This thesis addresses the door assignment and resource management problem with truck time windows constraints for a specific cross dock. The problems are formulated as mixed integer programming (MIP) models. The objective is to minimize the weighted sum of the total travel distance and cost which includes labor cost and penalty cost. A heuristic based on genetic algorithm (GA) is developed to solve the problems. Two gene repair methods are proposed to repair infeasible solutions. The computational results show that genetic algorithms outperforms the solution of MIP model with CPLEX in a given CPU time, for medium and large size instances, and that the second gene repair method outperforms the first one. In order to describe the behavior and gather information on the cross dock, a model based on Petri net is built to study the cross docks and simulations are carried out with Tina. The simulation results for different resource number lead us to obtain the relevant times to improve the original time windows, the makespan at each work station, the free time interval in the cross dock and the free resource number at each time period, which provide relevant information on the resource management. Besides, according to the simulation results, the original MIP formulations are improved. Then we propose a new MIP formulation, which determine not only door assignment, but also resources at each time period at each work station. Computational results reveal that the new MIP model control resources in cross dock more efficiently and outperforms the first model.

Les logiciels sont devenus une partie importante de notre vie quotidienne, car ils sont maintenant utilisés dans de nombreux périphériques hétérogènes, tels que nos téléphones, nos voitures, nos appareils ménagers, etc. Ces périphériques sont parsemés d’un certain nombre de logiciels intégrés, chacun gérant une tâche spécifique. Ces logiciels intégrés sont conçus pour fonctionner à l’intérieur de systèmes plus vastes avec un matériel varié et hétérogène et des ressources limitées. L'utilisation de logiciels embarqués est motivée par la flexibilité et la simplicité que ces logiciels peuvent garantir, ainsi que par la réduction des coûts. Les Cyber-Physical System (CPS) sont des logiciels utilisés pour contrôler des systèmes physiques. Les CPS sont souvent intégrés et s'exécutent en temps réel, ce qui signifie qu'ils doivent réagir aux événements externes. Un CPS complexe peut contenir de nombreux systèmes en temps réel. Le fait que ces systèmes puissent être utilisés dans des domaines critiques tels que la médecine ou les transports exige un haut niveau de sécurité pour ces systèmes. Les systèmes temps réel (RTS), par définition, sont des systèmes informatiques de traitement qui doivent répondre à des entrées générées de manière externe. Ils sont appelés temps réel car leur réponse doit respecter des contraintes de temps strictes. Par conséquent, l'exactitude de ces systèmes ne dépend pas seulement de l'exactitude des résultats de leur traitement, mais également du moment auquel ces résultats sont donnés. Le principal problème lié à l'utilisation de systèmes temps réel est la difficulté de vérifier leurs contraintes de synchronisation. Un moyen de vérifier les contraintes de temps peut consister à utiliser la théorie de la planification, stratégie utilisée pour partager les ressources système entre ses différents composants. Outre les contraintes de temps, il convient de prendre en compte d'autres contraintes, telles que la consommation d'énergie ou la sécurité. Plusieurs méthodes de vérification ont été utilisées au cours des dernières années, mais avec la complexité croissante des logiciels embarqués, ces méthodes atteignent leurs limites. C'est pourquoi les chercheurs se concentrent maintenant sur la recherche de nouvelles méthodes et de nouveaux formalismes capables de vérifier l'exactitude des systèmes les plus complexes. Aujourd'hui, une classe de méthodes de vérification bien utilisées est les techniques basées sur des modèles. Ces techniques décrivent le comportement du système considéré à l'aide de formalismes mathématiques, puis, à l'aide de méthodes appropriées, permettent d'évaluer l'efficacité du système par rapport à un ensemble de propriétés. Dans ce manuscrit, nous nous concentrons sur l'utilisation de techniques basées sur des modèles pour développer de nouvelles techniques de planification afin d'analyser et de valider la satisfiabilité d'un certain nombre de propriétés sur des systèmes temps réel. L'idée principale est d'exploiter la théorie de l'ordonnancement pour proposer ces nouvelles techniques. Pour ce faire, nous proposons un certain nombre de nouveaux modèles afin de vérifier la satisfiabilité d'un certain nombre de propriétés telles que l'ordonnancement, la consommation d'énergie ou la fuite d'informations. / Software’s become an important part of our daily life as they are now used in many heterogeneous devices, such as our phones, our cars, our home appliances … etc. These devices are dotted with a number of embedded software’s, each handling a specific task. These embedded software’s are designed to run inside larger systems with various and heterogeneous hardware and limited resources. The use of embedded software is motivated by the flexibility and the simplicity that these software can guarantee, and to minimize the cost. Cyber-Physical System (CPS) are software used to control physical systems. CPS are often embedded and run in real-time, which means that they must react to external events. A complex CPS can contains many real-time systems. The fact that these systems can be used in critical domains like medicine or transport requires a high level of safety for these systems. Real-Time Systems (RTS) by definition are processing information systems that have to respond to externally generated inputs, and they are called real-time because their response must respect a strict timing constraints. Therefore, the correctness of these systems does not depend only on the correctness of their treatment results, but it also depends on the timings at which these results are given. The main problem with using real-time systems is the difficulty to verify their timing constraints. A way to verify timing constraints can be to use Scheduling theory which is a strategy used in order to share the system resources between its different components. In addition to the timing constraints, other constraints should be taken in consideration, like energy consumption or security. Several verification methods have been used in the last years, but with the increasing complexity of the embedded software these methods reach their limitation. That is why researchers are now focusing their works on finding new methods and formalisms capable of verifying the correctness of the most complex systems. Today, a well-used class of verification methods are model-based techniques. These techniques describe the behavior of the system under consideration using mathematical formalisms, then using appropriate methods they give the possibility to evaluate the correctness of the system with respect to a set of properties. In this manuscript we focus on using model-based techniques to develop new scheduling techniques in order to analyze and validate the satisfiability of a number of properties on real-time systems. The main idea is to exploit scheduling theory to propose these new techniques. To do that, we propose a number of new models in order to verify the satisfiability of a number of properties as schedulability, energy consumption or information leakage.

Bien que de nombreux appareils numériques soient aujourd'hui capables de lire des contenus vidéo en temps réel et d'offrir une restitution de grande qualité, le décodage vidéo dans les systèmes embarqués n'en est pas pour autant devenu une opération anodine. En effet, les codecs récents tels que H.264 et HEVC sont d'une complexité telle que le recours à des architectures mixtes logiciel/matériel est presque incontournable. Or les plateformes de ce type sont notoirement difficiles à programmer efficacement. Cette thèse relève le défi du développement d'applications à flux de données pour les cibles embarquées hybrides et de leur exécution efficace, et propose plusieurs contributions. La première est une extension des heuristiques d'ordonnancement de liste pour tenir compte des contraintes mémorielles. La seconde est un modèle d'exécution à flot de données compatible avec la plupart des modèles existants et avec une large classe de plateformes matérielles, ainsi qu'un ordonnanceur dynamique. Enfin, de nombreux développements ont été menés sur une architecture réelle de STMicroelectronics pour démontrer la faisabilité de l'approche. / Although numerous electronic devices are nowadays able to play video contents in real time and offer high-quality reproduction, video decoding in embedded systems has not become a trivial process yet. As a mater of fact, recent codecs such as H.264 and HEVC exhibit such a complexity that resorting to mixed sofware-hardware architecture is almost unavoidable. However, programming efficiently this kind of platforms is well-known to be tricky. This thesis addresses the issue of developing streaming applications for hybrid embedded targets and executing them efficiently, and proposes several contributions. The first one is an extension of the classical list-scheduling heuristics to take memory constraints into account. Te second one is a datafow execution model compatible with most existing models and with a large set of hardware platforms, as well as a dynamic scheduler. Lastly, numerous developments have been carried out on a real-world architecture from STMicroelectronics so as to demonstrate the feasibility of the approach.

Au cours des dernières décennies, de grands efforts en recherche et développement ont été faits pour développer et promouvoir les véhicules électriques (VEs). La plupart de ces recherches portent essentiellement sur le développement des moteurs électriques de ces véhicules et des technologies de batteries de recharge. Cependant, un des obstacles majeurs pour le déploiement des VEs à grande échelle réside dans l'incertitude d’assister et de guider les conducteurs de ce type de véhicule d’une façon appropriée pour atteindre les stations de recharge tout en satisfaisant leurs souhaits (points de recharge disponibles, moins d’attente possible, proposition d’autres points d’intérêts : restaurant, shopping, etc.). Afin de remédier à ce manque, nous proposons dans ce travail de thèse une approche distribuée et adaptative orientée modèles pour la gestion de l'énergie pour la recharge des VEs. Pour ce faire, nous nous somme focalisés sur la modélisation des processus de recharge en utilisant une approche formelle basée sur des outils de systèmes à événements discrets, à savoir l'algèbre (max, +) et les réseaux de Petri. Les modèles développés ont permis d’étudier, d’analyser et d’évaluer le comportement du système de recharge. De plus, une approche d'optimisation basée sur la programmation linéaire est proposée afin d’affecter et d’orienter d'une façon optimale les VEs vers les stations de recharge appropriées et ordonnancer leurs opérations de recharge. Afin de prédire le taux et la durée de recharge moyens des VEs compte tenu des dates d’arrivée des demandes de recharge et l'état de recharge de chaque véhicule, une approche dédiée basée sur une fonction prédictive est proposée. En utilisant cette approche, les opérations de recharge pourraient être planifiées en minimisant les temps d'attente des VEs au sein des stations de recharge et en assurant un taux de recharge acceptable pour chaque demande. Les résultats d’analyse et de simulations obtenus ont montré que les approches de modélisation, d’optimisation et de prédiction proposées permettent d’affecter de façon adéquate et optimale les VEs aux stations de recharge tout en satisfaisant toutes les contraintes du processus de recharge. / In the last decades, very great research and development efforts have been made to develop and promote electric vehicles (EVs). Most efforts have been made to further develop the power engine of these vehicles and batteries technologies. However, one of the major obstacles to the large deployment of EVs is the uncertainty of drivers to get a suitable and vacant place at a charging station (CS). In this manuscript, we focus on the charging process modelling using formal approaches based on discrete event system tools namely (max,+) algebra and Petri nets. In addition, an optimization approach based on linear programming is proposed to optimally assign and reroute EVs to the suitable CSs and schedule their charging operations. In order to predict, manage and handle charging needs of EVs, a dedicated model based on a predictive function is introduced. The aim is to predict the average charging rate and time while considering the inter-arrival of charging requests and the state of charging of EVs. Using this approach, charging operations could be planned while minimizing waiting times of EVs and avoiding queuing situations within CSs. Simulation results showed that the proposed approaches allow assigning adequately and optimally EVs to CSs while satisfying all process constraints.