L’objectif de cette thèse est d’étudier l’efficacité énergétique des stratégies basse consommation pour des plateformes représentatives. Principalement, nous nous intéresserons aux stratégies énergétiques pour des systèmes embarqués multicœur en étudiant le comportement de politiques logicielles qui permettent la réduction effective de l’énergie tout en répondant aux exigences applicatives. Le travail présenté dans ce mémoire vise à étudier des stratégies de gestion de la consommation pour des plateformes monoprocesseur puis multiprocesseur concrètes. L’approche utilisée pour cette étude fut basée sur des plateformes représentatives afin d’identifier les paramètres significatifs, aussi bien au niveau matériel qu’au niveau applicatif, à l’inverse de nombreux travaux dans lesquels ces paramètres sont assez peu pris en compte voir ignorés. Ce travail analyse et compare diverses expérimentations menées sur des politiques énergétiques basées sur des techniques DVFS (Dynamic Voltage and Frequency Scaling) et DPS (Dynamic Power Switching) et définit les conditions sous lesquelles ces stratégies sont efficaces. Ces expérimentations ont permis d’établir des conclusions remarquables qui peuvent servir de pré-requis lors de la définition de stratégies efficaces de gestion de la consommation. Ces résultats montrent également que pour obtenir des stratégies efficientes il est nécessaire de tenir compte du domaine applicatif. Enfin, il faut noter que les modèles de haut de niveau de consommation ont été définis sur la base des mesures effectuées et afin d’estimer les gains énergétiques dès les premières étapes d’un flot de conception. / The purpose of this study is to investigate how power management strategies can be efficiently exploited in actual platforms. Primarily, the challenges in multicore based embedded systems lies in managing the energy expenditure, determining the scheduling behavior and establishing methods to monitor power and energy, so as to meet the demands of the battery life and load requirements. The work presented in this dissertation is a study of low power-aware strategies in the practical world for single and multiprocessor platforms. The approach used for this study is based on representative multiprocessor platforms (real or virtual) to identify the most influential parameters, at hardware as well as application level, unlike many existing works in which these parameters are often underestimated or sometimes even ignored. The work analyzes and compares in detail various experimentations with different power policies based on Dynamic Voltage and Frequency Scaling (DVFS) and Dynamic Power Switching (DPS) techniques, and investigates the conditions at which these policies are effective in terms of energy savings. The results of these investigations reveal many interesting and notable conclusions that can serve as prerequisites for the efficient use of power management strategies. This work also shows the potential of advanced domain specific power strategies compared to real world available strategies that are general purpose based in their majority. Finally, some high level consumption models are derived from the different energy measurement results to let the estimation of power management benefits at early stages of a system development.

Les systèmes temps réel à contraintes temporelles strictes sont caractérisés par des ensembles de tâches pour lesquelles sont connus l'échéance, le modèle d'arrivée (fréquence) et la durée d'exécution pire cas (WCET). Nous nous intéressons à l'ordonnancement de ces systèmes sur plate-forme multiprocesseur. Garantir le respect des échéances pour un algorithme d'ordonnancement est l'une des problématiques majeures de cette thématique. Nous allons plus loin en nous intéressant à la sûreté temporelle, que nous caractérisons par les propriétés (i) de robustesse et (ii) de viabilité. La robustesse consiste à proposer un intervalle sur les augmentations(i-a) de WCET et (i-b) de fréquence tel que les échéances soient respectées. La viabilité consiste cette fois à garantir le respect des échéances lors du relâchement des contraintes (ii-a) de WCET (réduction), (ii-b) de fréquence (réduction) et (ii-c) d'échéance(augmentation). La robustesse revient alors à tolérer l'imprévu, tandis que la viabilité est la garantie que l'algorithme d'ordonnancement n'est pas sujet à des anomalies suite à un relâchement de contraintes. Nous considérons l'ordonnancement en priorités fixes, où chaque occurrence d'une tâche est ordonnancée avec la même priorité. Dans un premier temps, nous étudions la propriété de robustesse dans les approches d'ordonnancement hors-ligne et sans migration (partitionnement). Nous traitons le cas des tâches avec ou sans partage de ressources. Dans un second temps, nous étudions la propriété de viabilité d'une approche d'ordonnancement en ligne avec migrations restreintes et sans partage de ressources / The hard real-time systems are characterized by sets of tasks for which are known the deadline, the arrival model (frequency) and the Worst-Case Execution Time (WCET). We focus on the scheduling of these systems on multiprocessor platforms. One of the main issues of this topic is to ensure that all deadlines are met. We go further by focusing on the temporal safety which we characterized by the properties of (i) robustness and (ii) sustainability. The robustness consists in providing an interval on the increases of (i-a) WCET and (i-b) frequency in such a way that the deadlines are met. The sustainability consists in ensuring that no deadline is missed when the following constraints are relaxed : (ii-a) WCET (decreasing), (ii-b) frequency (decreasing) and (ii-c) deadline (increasing). The robustness amounts to tolerate unexpected behaviors while the sustainability is the guarantee that the scheduling algorithm does not suffer from anomalies because of a relaxation of constraints. We consider fixed-priority scheduling for which any job of a task is scheduled with the same priority. Firstly, we study the property of robustness in off-line scheduling approaches without migration (partitioning). We deal with the case of tasks with or without shared resources. Secondly, we study the property of sustainability of an online restricted-migration scheduling approach without shared resources

Sistemas de Multiprocessados Embarcados são uma realidade, tanto no setor da indústria e quanto no setor acadêmico. Esses dispositivos oferecem capacidades de processamento paralelo objetivando cobrir requisitos cada vez maiores de aplicações complexas. A carga de trabalho subjacente das aplicações é suscetível a variação em tempo de execução o que, se não for tratada adequadamente, pode levar a degradação de eficiência em desempenho e energia. O aumento contínuo da complexidade da carga de trabalho das aplicações, bem como do tamanho dos sistemas multiprocessados emergentes, requer soluções de mapeamento dinâmicas e distribuídas. A maioria das técnicas de mapeamento propostas são implementações personalizadas, considerando um sistema operacional interno desenvolvido para uma arquitetura de processador específica. Essa prática restringe sua aplicação em outras plataformas, levando a um design extra, revalidação e, consequentemente, um custo oculto que pode ser um tanto quanto alto. Neste cenário, esta dissertação propõe a extensão do FreeRTOS para suportar mapeamento dinâmico e distribuído de tarefas em sistemas multiprocessados. O FreeRTOS tem portabilidade para mais de 30 arquiteturas de processadores embarcados, aumentando a portabilidade de software e reduzindo o tempo de desenvolvimento. A extensão proposta utiliza técnicas de mapeamento que permitem ao FreeRTOS atender a altas demandas de mapeamento de aplicações em tempo de execução. Outra contribuição deste trabalho é o desenvolvimento de um framework que permite a exploração de grandes sistemas fornecendo, simultaneamente, resultados para depuração. O framework proposto possibilita a geração automática de plataformas multiprocessadas considerando seu tamanho, a arquitetura do processador e um conjunto de aplicações. A descrição da plataforma resultante é altamente escalável permitindo extração de dados em tempo de execução e alta depuração. Estas características permitiram validar a extensão do FreeRTOS proposta em mais de uma arquitetura de processador da família ARM Cortex-M. Os casos de teste foram executados em plataformas de grande escala e em diferentes níveis de abstração com casos de mais de 120 aplicações incorporando mais de 600 tarefas processadas. Os resultados mostram que a extensão proposta apresenta resultados melhores ou iguais à literatura. / Embedded Multiprocessor systems are a reality, in both industry and academia sectors. Such devices offer parallel processing capabilities, aiming at covering the increasing requirements of complex applications. Underlying application workloads are susceptible to variation at runtime, which if not properly handled, may lead to the performance and power efficiency degradation. The continuous increase in the complexity of application workload and the size of emerging multiprocessor systems, calls for dynamic and distributed mapping solutions. The majority of the promoted mapping techniques are bespoke implementations, which consider an in-house operating system developed to a particular processor architecture. This practice restricts its adoption in other platforms, leading to extra design time, re-validation and, consequentially, a hidden cost that may well be quite high. In this scenario, this dissertation proposes a FreeRTOS extension that integrates the support to dynamic and distributed tasks mapping in multiprocessor systems. FreeRTOS is portable to more than 30 embedded processors architectures, increasing software portability and reducing development time. The proposed extension employs mapping techniques allowing FreeRTOS for handle high demands of application mapping in runtime. Another contribution of this work is the development of a framework, which enables the exploration of large systems while providing debugging facilities. The proposed framework provides the automatic generation of multiprocessor platforms, considering parameters of size, processor architecture, and an application set. The resulting platform description is high scalable while allows runtime data extraction and high debugging. These features allowed to validate the proposed FreeRTOS extension in more than one processor architecture from ARM Cortex-M family. Test cases were executed on large-scale platforms and at different levels of abstraction with cases of more than 120 applications incorporating more than 600 tasks processed. The results show that the proposed extension presents better or equal results to the literature.

La complexité croissante des systèmes multiprocesseurs sur puce (MPSoC) rend la vie plus difficile aux ingénieurs à cause des bugs et des inefficacités qui peuvent avoir un très large éventail de sources. L'interaction matériel / logiciel peut être l'une de ces sources, dont l'identification précoce et la résolution doivent être une priorité pour l'intégration rapide du système. Ainsi, en raison du grand nombre d'entrelacements d'exécution possibles, reproduire les conditions d'apparition d'une erreur ou d'un problème de performance est très difficile. Une approche de ce problème consiste à tracer une exécution et exploiter cette trace en faisant des analyses postérieures. L'obtention de traces à partir de vrai matériel va à l'encontre du processus de développement récent, désormais largement adoptés par l'industrie et l'académie, qui repose sur la simulation pour anticiper l'intégration matériel / logiciel. De nombreux systèmes multi-cœurs sur puce ont tendance à avoir des hiérarchies mémoire spécifiques, pour rendre le matériel plus simple et prévisible, au prix de voir percoler les contraintes matérielles vers les niveaux élevés de la pile logicielle. Malgré les efforts des ingénieurs, il est difficile d'assurer que toutes les mesures de prévention sont prises pour assurer une propriété donnée, comme l’absence de course lors de l'accès aux variables partagées ou la cohérence des données. Dans ce contexte, le processus de débogage est particulièrement pénible car il implique d'analyser des flux d'exécution parallèles. L'exécution d'un programme à plusieurs reprises est une partie intégrale du processus de débogage classique, mais le non-déterminisme du fait de l'exécution en parallèle conduit souvent à différents chemins d'exécution et donc des comportements différents.Cette thèse détaille les défis et les enjeux derrière la production et l'exploitation des traces "bien formés" dans un environnement de prototypage virtuel qui utilise la traduction binaire dynamique comme technique de simulation des processeurs. Ces traces contiennent des relations de causalité entre les événements qui permettent, d'une part, de simplifier l'analyse et, d'autre part, d'éviter de faire confiance à des horloges globales pour synchroniser les événements. Nous proposons un formalisme de définition des traces et détaillons sa mise en œuvre qui permet de rester non-intrusif aussi bien du point de vue matériel que logiciel. Nous utilisons ces traces pour aider à identifier et corriger les bugs sur les plateformes qui ont multiple cœurs. Nous présentons tout d'abord une méthode pour identifier les violations potentielles de cohérence de cache dans des plates-formes possédant des caches mais qui n'ont pas de matériel garantissant leur cohérence. Notre méthode identifie des violations potentielles qui peuvent apparaître au cours d'une exécution donnée en analysant les traces pour les deux stratégies d’écritures de cache: "write-through" et "write-back". Finalement, Nous nous intéressons à la simplification du processus de débogage des logiciels exécutés en parallèle sur MPSoC en utilisant les traces. Dans cet objectif, nous proposons un processus de débogage qui rejoue une exécution fautive en utilisant des traces. Nous détaillons une stratégie pour fournir des fonctionnalités d'exécution inverse pour éviter des temps de simulation élevé pendant une session de débogage.Nous avons mené des expériences en utilisant des applications parallèles s'exécutant sur acs{MPSoC} pour quantifier notre proposition et montrer que l'ensemble des stratégies d'analyse et de débogage complexes peuvent être mis en œvre par des traces, conduisant ainsi à des résultats déterministes en moins de temps que la simulation seule. / The increasing complexity of Multiprocessor System on Chip (MPSoC) makes the engineers' life harder as bugs and inefficiencies can have a very broad range of sources. Hardware/software interactions can be one of these sources, their early identification and resolution being a priority for rapid system integration. Thus, due to the huge number of possible execution interleavings, reproducing the conditions of occurrence of a given error/performance issue is very difficult. One solution to this problem consists of tracing an execution for later analysis. Obtaining the traces from real platforms goes against the recent development processes, now broadly adopted by industry and academy, which rely on simulation to anticipate hardware/software integration. Multi/many core systems on chip tend to have specific memory hierarchies, to make the hardware simpler and predictable, at the cost of having the hardware percolate towards the high levels of the software stack. Despite the developers efforts, it is hard to make sure all preventive measures are taken to ensure a given property, such as lack of race conditions or data coherency. In this context, the debugging process is particularly tedious as it involves analyzing parallel execution flows. Executing a program many times is an integral part of the process in conventional debugging, but the non-determinism due to parallel execution often leads to different execution paths and different behaviors.This thesis details the challenges and issues behind the production and exploitation of "well formed" traces in a transaction accurate virtual prototyping environment that uses dynamic binary translation as processor simulation technology. These traces contain causality relations among events, which allow firstly to simplify the analysis, and secondly to avoid relying on timestamps. We propose a formalism to define the traces and detail an implementation to produce them in a non-intrusive manner. We use these traces to help identify and correct bugs on multi/many-core platforms. We firstly introduce a method to identify the potential cache coherence violations in non-cache-coherent platforms. Our method identifies potential violations which may occur during a given execution for write-through and write-back cache policies by analyzing the traces.We secondly focus on easing the debugging process of parallel software running on MPSoC using traces. To that aim, we propose a debugging process which replays a faulty execution using traces. We detail a strategy for providing forward and reverse execution features to avoid long simulation times during a debug session.We conducted experiments on MPSoC using parallel applications to quantify our proposal, and overall show that complex analysis and debug strategies can be implemented over traces, leading to deterministic results in shorter time than simulation alone.

L'ordonnancement de tâches sur un système temps réel dur correspond à trouver une façon de choisir, à chaque instant, quelle tâche doit être exécutée sur le processeur pour que chacune ait le temps de terminer son travail avant son échéance. Ce problème, dans le contexte monoprocesseur, est déjà bien étudié et permet des applications sur des systèmes en production (aérospatiale, bourse etc.). Aujourd'hui, les plateformes multiprocesseur se sont généralisées et ont amené de nombreuses questions telles que l'utilisation efficace de tous les processeurs. Dans cette thèse, nous explorons les approches existantes pour résoudre ce problème. Nous étudions tout d'abord l'approche par partitionnement qui consiste à utiliser les recherches existantes en ramenant ce problème à plusieurs systèmes monoprocesseur. Ici, nous proposons un algorithme générique dont les paramètres sont adaptables en fonction de l'objectif à atteindre. Nous étudions ensuite l'approche par semi-partitionnement qui permet la migration d'un nombre restreint de tâches. Nous proposons une solution avec des migrations restreintes qui pourrait être assez simplement implémentée sur des systèmes concrets. Nous proposons ensuite une solution avec des migrations non restreintes qui offre de meilleurs résultats mais est plus difficile à implémenter. Enfin, les programmeurs utilisent de plus en plus le concept de tâches parallèles qui peuvent utiliser plusieurs processeurs en même temps. Ces tâches sont encore peu étudiées et nous proposons donc un nouveau modèle pour les représenter. Nous étudions les ordonnanceurs possibles et nous définissons une façon de garantir l'ordonnançabilité de ces tâches pour deux d'entre eux / The scheduling of tasks on a hard real-time system consists in finding a way to choose, at each time instant, which task should be executed on the processor so that each succeed to complete its work before its deadline. In the uniprocessor case, this problem is already well studied and enables us to do practical applications on real systems (aerospace, stock exchange etc.). Today, multiprocessor platforms are widespread and led to many issues such as the effective use of all processors. In this thesis, we explore the existing approaches to solve this problem. We first study the partitioning approach that reduces this problem to several uniprocessor systems and leverage existing research. For this one, we propose a generic partitioning algorithm whose parameters can be adapted according to different goals. We then study the semi-partitioning approach that allows migrations for a limited number of tasks. We propose a solution with restricted migration that could be implemented rather simply on real systems. We then propose a solution with unrestricted migration which provides better results but is more difficult to implement. Finally, programmers use more and more the concept of parallel tasks that can use multiple processors simultaneously. These tasks are still little studied and we propose a new model to represent them. We study the possible schedulers and define a way to ensure the schedulability of such tasks for two of them

We outline a multiprocessor architecture that uses modular arithmetic to implement numerical computation with 900 bits of intermediate precision. A proposed prototype, to be implemented with off-the-shelf parts, will perform high-precision arithmetic as fast as some workstations and mini- computers can perform IEEE double-precision arithmetic. We discuss how the structure of modular arithmetic conveniently maps into a simple, pipelined multiprocessor architecture. We present techniques we developed to overcome a few classical drawbacks of modular arithmetic. Our architecture is suitable to and essential for the study of chaotic dynamical systems.

Medical devices processing images or audio or executing complex AI algorithms are able to run more efficiently and meet real time requirements if the parallelism in those algorithms is exploited. In this research a methodology is proposed to exploit the flexibility and short design cycle of FPGAs (Field Programmable Gate Arrays) in order to achieve this target. Hardware/software co-design and dynamic partitioning allow the optimization of the multiprocessor platform design parameters and software code targeting each core to meet real time constraints. This is practically demonstrated by building a real life driver vigilance monitoring system based on visual cues extraction and evaluation. The application drives the whole design process to prove its effectiveness. An algorithm was built to achieve the goal of detecting the eye state of the driver (open or closed) and it is applied on captured consecutive frames to evaluate the vigilance state of the driver. Vigilance state is measured depending on duration of eye closure. This video processing application is then targeted to run on a multi-core FPGA based processing platform using the proposed methodology. Results obtained were very good using the Grimace Face Database and when operating the system on one’s face. On operating the device, a false positive of eye closure must take place two consecutive times in order to get an alarm, which decreases the probability of failure. The timing analysis applied proved the importance of using the concept of parallelism to achieve performance constraints. FPGA technology proved to be a very powerful prototyping tool for complex multiprocessor systems design. The flexible FPGA technology coupled with hardware/software co-design provided means to explore the design space and reach decisions that satisfy the design constraints with minimum time investment and cost.

The purpose of this study is to investigate how power management strategies can be efficiently exploited in actual platforms. Primarily, the challenges in multicore based embedded systems lies in managing the energy expenditure, determining the scheduling behavior and establishing methods to monitor power and energy, so as to meet the demands of the battery life and load requirements. The work presented in this dissertation is a study of low power-aware strategies in the practical world for single and multiprocessor platforms. The approach used for this study is based on representative multiprocessor platforms (real or virtual) to identify the most influential parameters, at hardware as well as application level, unlike many existing works in which these parameters are often underestimated or sometimes even ignored. The work analyzes and compares in detail various experimentations with different power policies based on Dynamic Voltage and Frequency Scaling (DVFS) and Dynamic Power Switching (DPS) techniques, and investigates the conditions at which these policies are effective in terms of energy savings. The results of these investigations reveal many interesting and notable conclusions that can serve as prerequisites for the efficient use of power management strategies. This work also shows the potential of advanced domain specific power strategies compared to real world available strategies that are general purpose based in their majority. Finally, some high level consumption models are derived from the different energy measurement results to let the estimation of power management benefits at early stages of a system development.

The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer.In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time.We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space.A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.

The multiprocessor task graph scheduling problem has been extensively studied asacademic optimization problem which occurs in optimizing the execution time of parallelalgorithm with parallel computer. The problem is already being known as one of the NPhardproblems. There are many good approaches made with many optimizing algorithmto find out the optimum solution for this problem with less computational time. One ofthem is branch and bound algorithm.In this paper, we propose a branch and bound algorithm for the multiprocessor schedulingproblem. We investigate the algorithm by comparing two different lower bounds withtheir computational costs and the size of the pruned tree.Several experiments are made with small set of problems and results are compared indifferent sections.