Search

Task-based systems have gained popularity because of their promise of exploiting the computational power of complex heterogeneous systems. A common programming model is the so-called Sequential Task Flow (STF) model, which, unfortunately, has the intrinsic limitation of supporting static task graphs only. This leads to potential submission overhead and to a static task graph which is not necessarily adapted for execution on heterogeneous systems. A standard approach is to find a trade-off between the granularity needed by accelerator devices and the one required by CPU cores to achieve performance. To address these problems, we extend the STF model in the StarPU runtime system to enable tasks subgraphs at runtime. We refer to these tasks as hierarchical tasks. This approach allows for a more dynamic task graph. This extended model combined with an automatic data manager allows to dynamically adapt the granularity to meet the optimal size of the targeted computing resource. We show that the hierarchical task model is correct and we provide an early evaluation on shared memory heterogeneous systems, using the Chameleon dense linear algebra library, Les systèmes à base de tâches ont gagné en popularité du fait de leur capacité à exploiter pleinement la puissance de calcul des architectures hétérogènes complexes. Un modèle de programmation courant est le modèle de soumission séquentielle de tâches (Sequential Task Flow, STF) qui malheureusement ne peut manipuler que des graphes de tâches statiques. Ceci conduit potentiellement à un surcoût lors de la soumission, et le graphe de tâches statique n'est pas nécessairement adapté pour s'exécuter sur un système hétérogène. Une solution standard consiste à trouver un compromis entre la granularité permettant d'exploiter la puissance des accélérateurs et celle nécessaire à la bonne performance des CPUs. Pour répondre à ces problèmes, nous proposons d'étendre le modèle STF fourni par le support d'exécution StarPU en y ajoutant la possibilité de transformer certaines tâches en sous-graphe durant l'exécution. Nous appelons ces tâches des tâches hiérarchiques. Cette approche permet d'exprimer des graphes de tâche plus dynamiques. En combinant ce nouveau modèle à un gestionnaire automatique des données, il est possible d'adapter dynamiquement la granularité pour fournir une taille optimale aux différentes ressources de calcul ciblées. Nous montrons dans ce rapport que le modèle des tâches hiérarchiques est valide ainsi qu'une première évaluation de ses performances en utilisant la bibliothèque d'algèbre linéaire dense Chameleon.

Real-time systems must provide functionalities that need to produce their results within predefined time windows. Some of these functionalities may be critical: if they produce wrong results or produce good results too late, failures occur which, in some extreme case, may cause the loss of human lives.Intelligent transportation systems are a good example of real-time systems with critical functionalities. These vehicles embed complex features to enhance the driving experience, like the so-called Advanced Driver-Assistance Systems (ADAS). Such complex functionalities possess non-functional requirements, as the fact that they must produce results within precise time windows, or that must be robust to transient hardware faults. For example, the automatic obstacle detection feature assists the driver by alerting on obstacles on the vehicle path, so preventing accidents dues to inattention or fatigue: however the recognition of an obstacle must be performed in due time, otherwise the vehicle will harm someone or destroy itself.Thus, a precise analysis of the temporal behavior of these systems is required to guarantee that all the timing constraints are respected. For modern vehicles, the electronic boards chosen for these systems need to provide high performance, since there is a pressure to integrate all the critical and non-critical functionalities on the same board and reduce cost. Moreover, with the miniaturization of electronic components and with the reduction in voltage, systems may be subject to transient faults during their lifetime, provoking unexpected failures. Thus, there is a need to have analysis taking into account both reliability and the respect of the timing constraints. In this thesis, we have proposed a set of solutions that are positioned at two levels:1. We have developed models to analyze the execution time of real-time systems that integrate caches. The major scientific contribution of the thesis at this level is an improved analysis of the effect of preemptions on memory access times in a system scheduled by Earliest Deadline First.2. We have also designed techniques to increase the reliability of real-time systems integrating caches. Our approach is novel in the sense that we propose a method to protect tasks code from transient faults in the cache by adding protection mechanisms to the tasks code while respecting the timing constraints.As can be seen, our work is original in that it lies at the intersection of several areas:1. The domain of real-time critical systems;2. The field of processor system architectures in general and that of programmable embedded systems integrating caches in particular;3. The field of reliability and robustness of real-time critical systems.; Les systèmes temps réel implémentent des fonctionnalités qui doivent produire leurs résultats dans une fenêtre de temps donnée. Certaines de ces fonctionnalités peuvent être critiques. Si une fonctionnalité critique produit un résultat erroné ou produit un bon résultat au-delà d'une certaine limite temporelle, une défaillance se produit. Lorsqu'une défaillance se produit, des événements catastrophiques peuvent s'ensuivre, comme la perte d'une vie humaine. Les systèmes de transport intelligents sont un bon exemple de systèmes temps réel dotés de fonctionnalités critiques. Ces véhicules intègrent des fonctionnalités qui améliorent la conduite en aidant le conducteur, comme les systèmes avancés d'assistance au conducteur (ADAS). Ces fonctionnalités doivent produire de bons résultats dans une fenêtre de temps précise comme pour la détection d'objets pour éviter de blesser des usagers de la route. Une analyse précise du comportement de ces systèmes est par conséquent nécessaire pour garantir que les contraintes de temps sont respectées. Pour les véhicules modernes, les cartes électroniques choisies pour ces systèmes doivent être très performantes, et doivent intégrer toutes les fonctionnalités critiques et non critiques sur la même carte afin de réduire les coûts. Avec la miniaturisation des circuits électronique et la réduction de la tension électrique, les systèmes peuvent subir des fautes transitoires pendant leur durée de vie, provoquant des erreurs dans leurs comportements. Il est donc nécessaire d'avoir une analyse prenant en compte à la fois la fiabilité et le respect des contraintes temporelles. Dans cette thèse, nous avons proposé un ensemble de solutions qui se positionnent à deux niveaux :1. Nous avons mis au point des modèles d'analyse de temps d'exécution des systèmes temps-réels intégrants des mémoires caches. La contribution scientifique majeure de la thèse à ce niveau est une meilleure analyse de l'impact des préemptions entre les tâches sur les temps d'accès à la mémoire dans un système ordonnancé par Earliest Deadline First.2. Nous avons aussi conçu des techniques pour augmenter la fiabilité des systèmes temps-réel intégrant des mémoires caches. Notre approche est nouvelle dans le sens où nous proposons une méthode qui permet de protéger le code des tâches des fautes transitoires dans la mémoire cache en ajoutant des mécanismes de protection au code des tâches tout en respectant les contraintes temporelles.Comme on peut le voir, notre travail est original du fait qu'il se trouve à l'intersection de plusieurs domaines :1. Le domaine des systèmes temps-réel critiques;2. Le domaine des architectures de systèmes de processeurs en général et celui des systèmes embarqués programmables intégrant des mémoires caches en particulier;3. Le domaine de la fiabilité et de la robustesse des systèmes temps-réels critiques.

A real-time system is a system whose correctness depends not only on the correctness of the values it produces, but also on the time when it produces those values. The rate at which it must produce values is defined by the environment it operates in. When programming such a system, it is important that the programming language allows to reason about the constraints introduced by this context. Synchronous languages [14] are well-adapted to theprogramming of critical real-time systems thanks to their clean formal semantics and to their formally defined compilation process. In this work, we will present extensions to the synchronous language Prelude [67] to tackle two issues: Programming multicore systems predictably and handling system reconfiguration during execution.Multicore hardware platforms have the potential to increase the performance of real-time systems. However, their architecture, especially the shared central memory, is prone to hard-to-predict delays, outweighing the potential benefits. To address this issue, models such as PREM [71] and AER [32] have been proposed. Our first contribution aims at producing AER-compliant multicore C code from a high-level Prelude program. This shifts the responsibility of low-level implementation concerns related to task communications onto the compiler, saving tedious and error-prone development efforts.A multi-mode real-time system must respect different functional requirements during its execution. A mode of execution represents a possible system configurations, for an aircraft control system these may include take-off, cruise and landing. Mode change protocols define transitions to change safelyfrom one mode to another. Our second contribution proposes clock views to decouple the rate of tasks and transitions. The resulting multi-mode support is both formally defined and generic enough to allows programmers to choose the kind of protocol they need for their application. A clock calculus based on refinement typing [39, 83] infers and checks the consistency of rates and views.; Un système temps réel est un système dont la correction dépend non seulement de la correction des valeurs qu’il produit, mais aussi du temps quand il les produit. Le rythme de production de ces valeurs est défini par l’environnement dans lequel il opère. La programmation d’un tel système nécessite un langage de programmation permettant de résonner sur les contraintes introduites par ce contexte. Les langages synchrones [14] sont bien adaptés pourla programmation de systèmes critiques temps réel de part leur sémantique et leur processus de compilation formellement définis. Dans ce travail, nous présentons des extensions au langage synchrone Prelude [67] pour aborder deux problèmes : La programmation de systèmes multicœur prédictibleset la reconfiguration du système durant l’exécution.Les plateformes matérielles multicœurs possèdent un potentiel de performances accrues des systèmes temps réel. Cependant, leur architecture, en particulier la mémoire centrale partagée, est sujette à des délais difficiles à prédire, contrebalançant les gains potentiels. Les modèles tel que PREM [71] et AER [32] remédient à cette limitation. Notre première contribution permet de produire du code multicœur en accord avec le modèle AER à partir d’un programme haut-niveau Prelude. Ceci permet de transférer la responsabilité des problèmes bas niveau liés aux communications inter-tâches, évitantdes efforts de développement fastidieux et sujets aux erreurs. Les exigences fonctionnelles d’un système temps-réel multi-mode évoluent durant son exécution. Un mode d’exécution représente une configuration possible du système, par exemple décollage, croisière ou atterrissage pour un système de contrôle d’avion. Les protocoles de changement de mode définissent des transitions afin de changer de mode en sécurité. Notre seconde contribution propose les vues d’horloge pour découpler le rythme d’exécution des tâches de celui des transitions. Le mécanisme multi-mode résultant est à la fois formellement défini et générique afin de permettre de choisir le type de protocole approprié à application. Un calcul d’horloge basé sur le typage par raffinement [39, 83] infère et vérifie la cohérence des rythmes et vues.

The hardware complexity of modern machines makes the design of adequate programming models crucial for jointly ensuring performance, portability, and productivity in high-performance computing (HPC). Sequential task-based programming models paired with advanced runtime systems allow the programmer to write a sequential algorithm independently of the hardware architecture in a productive and portable manner, and let a third party software layer -the runtime system- deal with the burden of scheduling a correct, parallel execution of that algorithm to ensure performance. Many HPC algorithms have successfully been implemented following this paradigm, as a testimony of its effectiveness., Developing algorithms that specifically require fine-grained tasks along this model is still considered prohibitive, however, due to per-task management overhead [1], forcing the programmer to resort to a less abstract, and hence more complex "task+X" model. We thus investigate the possibility to offer a tailored execution model, trading dynamic mapping for efficiency by using a decentralized, conservative in-order execution of the task flow, while preserving the benefits of relying on the sequential taskbased programming model. We propose a formal specification of the execution model as well as a prototype implementation, which we assess on a shared-memory multicore architecture with several synthetic workloads. The results show that under the condition of a proper task mapping supplied by the programmer, the pressure on the runtime system is significantly reduced and the execution of fine-grained task flows is much more efficient.

The emergence of more powerful, but also more complex, multicore computers presents both an opportunity and new challenges for the integration of mixed criticality systems. These systems, which embed functionalities of different levels of importance, require the respect of temporal requirements. Indeed, the more critical a software is, the more catastrophic the consequences in case of a missed execution deadline. Consequently, mechanisms for operational safety must be put in place to prevent this risk. The use of multicore computers exacerbates this problem with the concurrent execution of tasks that can cause inter-task interference. This is due to the sharing of resources associated with the shared hardware platform. Memory, peripherals, access to buses and shared memory spaces are potential congestion points. This can lead to delays in the execution of critical tasks only due to the parallel execution of lower criticality tasks. Consequently, the risks of non-compliance with real-time requirements become even more prominent. The existing solutions to such a problem are done at the expense of other elements that are becoming equally necessary in the industry, including the maximization of computing resources use. Thus, our proposal seeks to address both the need for real-time guarantees on critical tasks while allowing a good use of the resources offered by multicore computers. This thesis work focuses on the study of critical tasks modeled as functional task chains to guarantee their response times. Each functionality of the system corresponds to a chain of different software components executed sequentially. With this more functional approach to software execution, we propose a Monitoring and Control mechanism that offers guarantees on a critical task chain, by anticipating risks of interference that could lead to a failure. The anticipation consist of pausing temporarily the noncritical tasks to control and mitigate interfer! ence. The objective is to obtain a guarantee of end-to-end response time of the task chain without missing deadlines, with a limitation of interference only when necessary, so that the rest of the time, all the tasks of the system can exploit the computing power and the available resources to the maximum. We propose along with such mechanism an implementation protocol and a first analysis with an experimental platform as a proof of concept to analyze the results obtained with such solution., L'émergence de calculateurs multicœurs plus puissants, mais aussi plus complexes, présente à la fois une opportunité et de nouveaux enjeux pour l'intégration de systèmes à criticité mixte. Ces systèmes, qui embarquent des fonctionnalités de différents niveaux d'importance, requièrent le respect d'exigences temporelles. En effet, plus un logiciel est critique, plus les conséquences en cas de dépassement d'échéance d'exécution peuvent être catastrophiques. Par conséquent, des mécanismes de sûreté de fonctionnement doivent être mis en place pour prévenir ce risque. L'usage de calculateurs multicœurs exacerbe cette problématique avec l'exécution concurrente de tâches qui peut provoquer des interférences inter-tâches. Cela est dû au partage de ressources associées à la plateforme matérielle partagée. La mémoire, les périphériques, les bus d'accès ainsi que les espaces mémoire partagés constituent ainsi des points de congestion potentielle. Cela peut alors mener à des retards dans l'exécution de tâches critiques uniquement du fait de l'exécution parallèle de tâches à plus faible niveau de criticité. En conséquence, les risques de non-respect des exigences temps-réel deviennent d'autant plus importants sur ces processeurs. De plus, la complexité croissante des architectures matérielle rend aussi plus difficile de complètement maîtriser et prévenir en amont tout risque d'interférences. Les solutions existantes à un tel problème se font au détriment d'autres éléments qui deviennent tout autant nécessaires dans l'industrie, dont notamment la maximisation d'usage des ressources de calcul. Ainsi, notre proposition cherche à répondre à la fois au besoin de garanties temps-réel sur les tâches critiques tout en permettant une bonne utilisation des ressources offertes par les calculateurs multicœurs. Dans ce cadre, ces travaux se focalisent sur l'étude des tâches critiques sous forme de chaînes de tâches fonctionnelles. De fait chaque fonctionnalité exécutée correspond à une chaîne de différents blocs logiciels exécutés séquentiellement. Avec cette approche, on propose un mécanisme de Surveillance et de Contrôle qui offre des garanties minimales sur une chaîne de tâche critique, par anticipation de risques d'interférences qui pourraient mener à une défaillance. L'! anticipation ayant pour moyen de neutralisation des interférences la mise en pause temporaire des tâches non critiques. L'objectif est d'obtenir une garantie d'exécution bout-en-bout de la chaîne de tâche sans dépassement d'échéance, avec une limitation des tâches non critiques uniquement quand nécessaire, de façon à ce que le reste du temps, on puisse exploiter au maximum la puissance de calcul et les ressources disponibles. Avec un tel mécanisme, nous proposons un protocole d'implémentation et de calibration, ainsi qu'une première analyse à partir d'une plateforme expérimentale dédiée.

To be held in conjunction with SC21; International audience; Processor architectures at exascale and beyond are expected to continue to suffer from nonuniform access issues to in-die and node-wide shared resources. Mapping applications onto these resource hierarchies is an on-going performance concern, requiring specific care for increasing locality and resource sharing but also for ensuing contention. Application-agnostic approaches to search efficient mappings are based on heuristics. Indeed, the size of the search space makes it impractical to find optimal solutions nowadays and will only worsen as the complexity of computing systems increases over time. In this paper we leverage the hierarchical structure of modern compute nodes to reduce the size of this search space. As a result, we facilitate the search for optimal mappings and improve the ability to evaluate existing heuristics.Using widely known benchmarks, we show that permuting thread and process placement per node of a hierarchical topology leads to similar performances. As a result, the mapping search space can be narrowed down by several orders of magnitude when performing exhaustive search. This reduced search space will enable the design of new approaches, including exhaustive search or automatic exploration. Moreover, it provides new insights into heuristic-based approaches, including better upper bounds and smaller solution space.

International audience; Multicore parallelism involve inter-tasks interferences leading to execution timing uncertainties. This is important for safety concerns in industrial applications (automotive for instance). Existing solutions limit significantly the use of available computing resources for low-criticality tasks to keep strong timing guarantees on high-criticality tasks. We propose a run-time monitoring and control approach for mixed-criticality systems to prevent temporal faults. Its objective is to guarantee a high-criticality function end-to-end deadline, even when interfered by low-criticality tasks parallel execution. Such approach aims at allowing better computing resource use with an additional guarantee for a given task chain end-to-end response time. We also propose an experimental protocol to characterise this task chain and calibrate the mechanism. Our approach has been implemented on a Linux-based experimental platform.

International audience; Allocation and scheduling of applications affect the timing response and system performance, particularly for Network-on-Chip (NoC) based multicore systems executing realtime applications. These systems with multitasking processors provide improved opportunity for parallel application execution. In dynamic scenarios, runtime task allocation improves the system resource utilization and adapts to varying application workload. In this work, we present an efficient hybrid strategy for unified allocation and scheduling of tasks at runtime. By considering multitasking capability of processors, communication cost and task timing characteristics, potential allocation solutions are obtained at design-time. These are adapted for dynamic mapping and scheduling of computation and communication workloads of real-time applications. Simulation results show that the proposed approach achieves 34.2% and 26% average reduction in network latency and communication cost of the allocated applications. Also, the deadline satisfaction of the tasks improves on average by 42.1% while reducing the allocation-time overhead by 32% when compared with existing techniques.

International audience; In modern server CPUs, individual cores can run at different frequencies, which allows for fine-grained control of the per-formance/energy tradeoff. Adjusting the frequency, however, incurs a high latency. We find that this can lead to a problem of frequency inversion, whereby the Linux scheduler places a newly active thread on an idle core that takes dozens to hundreds of milliseconds to reach a high frequency, just before another core already running at a high frequency becomes idle. In this paper, we first illustrate the significant performance overhead of repeated frequency inversion through a case study of scheduler behavior during the compilation of the Linux kernel on an 80-core Intel R Xeon-based machine. Following this, we propose two strategies to reduce the likelihood of frequency inversion in the Linux scheduler. When benchmarked over 60 diverse applications on the Intel R Xeon, the better performing strategy, S move , improves performance by more than 5% (at most 56% with no energy overhead) for 23 applications, and worsens performance by more than 5% (at most 8%) for only 3 applications. On a 4-core AMD Ryzen we obtain performance improvements up to 56%.

International audience; Modern microprocessors feature turbo mechanisms that adjust the clock frequency dynamically so as to maximize processor performance under power and temperature limits. However, the documentation for commercial chips rarely provides more than a superficial description of how turbo works. This paper highlights certains aspects of turbo that are not well known outside the industry and that distinguish it from dynamic thermal management. A plausible open-source turbo is proposed and described, extrapolating from the scarce and sparse information that has been disclosed so far.

International audience; Memory access duration on multicore architectures are highly variable, since concurrent accesses to resources by different cores induce time interferences. Consequently, critical software tasks may be delayed by non-critical ones, leading to deadline misses and possible catastrophic failures. We present an approach to tackle the implementation of mixed criticality work-loads on multicore chips, focusing on task chains, i.e., sequences of tasks with end-to-end deadlines. Our main contribution is a Monitoring & Control Agent able to stop non-critical software execution in order to prevent memory interference and guarantee that critical tasks deadlines are met. This paper describes our approach, and the associated experimental framework to conduct experiments to analyze attainable real-time guarantees on a multicore platform.

International audience; The aim of this paper is to present a high precision and event-versatile MBPTA framework that we have developed for the statistical timing analysis of multicore platforms. Its use satisfactorily allows the study of complex multicore platforms from the CPU point of view, without requiring hardware or software models. This gives us an accurate real view of the platform behavior for any specific situation without using extra tools. In addition, this measurement framework is directly portable to other multicore platforms with the same CPU version and easily portable to other CPU versions within the same manufacturer.The MBPTA framework directly uses coprocessors and the Performance Monitor Unit (PMU), i.e. Performance Monitor Hardware (PMH), instead of software profilers. Hardware performance counters provide low-overhead access to a considerable amount of performance information of numerous elements such as the CPU, caches or bus.The statistical timing analysis consists in proposing average and worst-case modeling by making use of the tool diagXtrm applied to measurement of task execution times.Measurements obtained from the PMH are used for analyzing and quantifying the interference that can happen within a multicore platform.The potential for measurements from coprocessor and PMU, as well as its potential for statistical analysis, is shown by using an heterogeneous multicore Texas Instrument system on chip. The interference we focus on are due to the shared memory of this platform.

International audience; Memory access duration on multicore architectures are highly variable, since concurrent accesses to resources by different cores induce time interferences. Consequently, critical software tasks may be delayed by non-critical ones, leading to deadline misses and possible catastrophic failures. We present an approach to tackle the implementation of mixed criticality work-loads on multicore chips, focusing on task chains, i.e., sequences of tasks with end-to-end deadlines. Our main contribution is a Monitoring & Control Agent able to stop non-critical software execution in order to prevent memory interference and guarantee that critical tasks deadlines are met. This paper describes our approach, and the associated experimental framework to conduct experiments to analyze attainable real-time guarantees on a multicore platform.

International audience; Memory access durations on multicore architectures are highly variable, since concurrent accesses to memory by different cores induce time interferences. Consequently, critical software tasks may be delayed by noncritical ones, leading to deadline misses and possible catastrophic failures. We present an approach to tackle the implementation of mixed criticality work-loads on multicore chips, focusing on task chains, i.e., sequences of tasks with end-to-end deadlines. Our main contribution is a Monitoring & Control System able to stop noncritical software execution in order to prevent memory interference and guarantee that critical tasks deadlines are met. This paper describes our approach, and the associated experimental framework to conduct experiments to analyze attainable real-time guarantees on a multicore platform.

International audience; With the advent of Internet of Things (IoT) and the increase of the Internet Services, more and more datacenters are needed to manage the Internet traffic. Energy consumption related to these infrastructures have already reached more than 2% of the global energy consumption and it is estimated to increase in the next years. Trends such as a billion more people coming online in developing countries, IoT, driverless cars, robots, and artificial intelligence (AI) are major drivers of unrelenting growth. Our work is intended to explore new distributed architectures to deploy datacenters in order to reduce their energy consumption and reach the energy proportionality. An effort in the use of Renewable Energy Sources (RES) and Energy Storage Systems (ESS) is done in order to approach the zero-carbon emission objective. In this sense, microgrid, nanogrid and smart grid structures are analyzed in terms of stability, architecture, control, communication and energy management.

International audience; Lucas-Kanade algorithm is a well-known optical flow estimator widely used in image processing for motion detection and object tracking. As a typical image processing algorithm, the procedure is a series of convolution masks followed by 22 linear systems for the optical flow vectors. Since we are dealing with a stencil computation for each stage of thealgorithm, the overhead from memory accesses is expected to stand as a serious scalability bottleneck, especially on a NUMA manycore configuration. The objective of this study is therefore to investigate an OpenMP parallelization of Lucas-kanade algorithm on a NUMA manycore, including the performance impact of NUMA-aware settings at runtime. Experimental results on a dual-socket INTEL Broadwell-E/EP is provided together with the corresponding technical discussions

Nowadays the evolution of High Performance Computing follows the needs of numerical simulations.These applications are executed on supercomputers which can offer several thousands of cores, split into a large number of computing nodes, which possess a relatively low number of cores.Each of these nodes consists of a shared memory architecture, in which the memory is physically split into several distinct blocks: this implies that the memory access time depends both on which data is accessed, and on which core tries to access it.These architectures are named NUMA (for Non Uniform Memory Access).The current way to exploit them tends to be through a tasks-based programming model, which can handle irregular applications beyond a simple loop-based parallelism.Efficient use of NUMA architectures is critical for the overall performance improvements of supercomputers.This thesis has been targetted at improving common techniques for their exploitation: it proposes an answer to the tradeoff that has to be made between data locality and load balancing, that are two critical aspects of applications scheduling.Contributions of this thesis can be split into two parts: the first part is dedicated to providing the programmer with means to understand, analyze, and better characterize the behavior of their applications' critical parts, and the second part is dedicated to several improvements made to the runtime systems.This last part has been evaluated on various applications, and has shown some significant performance gains.; L'évolution du calcul haute performance est aujourd'hui dirigée par les besoins des applications de simulation numérique.Ces applications sont exécutées sur des supercalculateurs qui peuvent proposer plusieurs milliers de cœurs, et qui sont découpés en un très grand nombre de nœuds de calcul ayant eux un nombre de cœurs beaucoup plus faible.Chacun de ces nœuds de calcul repose sur une architecture à mémoire partagée, dont la mémoire est découpée en plusieurs blocs physiques différents : cela implique un temps d'accès dépendant à la fois de la donnée accédée ainsi que du processeur y accédant.On appelle ce genre d'architectures NUMA (pour emph{Non Uniform Memory Access}).La manière actuelle de les exploiter tend vers l'utilisation d'un modèle de programmation à base de tâches, qui permet de traiter des programmes irréguliers au delà du simple parallélisme de boucle.L'exploitation efficace des machines NUMA est critique pour l'amélioration globale des performances des supercalculateurs.Cette thèse a été axée sur l'amélioration des techniques usuelles pour leur exploitation : elle propose une réponse au compromis qu'il faut faire entre localité des données et équilibrage de charge, qui sont deux points critiques dans l'ordonnancement d'applications.Les contributions de cette thèse peuvent se découper en deux parties : une partie dédiée à fournir au programmeur les moyens de comprendre, analyser, et mieux spécifier le comportement des parties critiques de son application, et une autre partie dédiée à différentes améliorations du support exécutif.Cette seconde partie a été évaluée sur différentes applications, ce qui a permis de montrer des gains de performances significatifs.

International audience; Three-dimensional Networks-on-Chips (3D-NoCs) have emerged as an alternative to further enhance the performance, functionality, and packaging density of 2D-NoCs. However, the increasing complexity of NoC routers, the continuous miniaturization of silicon technology, the lower operating voltages, and the higher operating frequencies have made the NoC increasingly vulnerable to soft errors. In particular, transient faults occurring in the route computation unit (RCU) can provoke misrouting which may lead to severe effects such as deadlocks or packet loss, corrupting the operation of the entire chip. By combining a reliable fault detection circuit leveraging circuit-level double-sampling, with a cost-effective rerouting mechanism, we develop a full fault-tolerance solution that can efficiently detect and correct such fatal errors before the affected packets leave the router. To validate the proposed solution, we also introduce a novel method for simulation-based fault -injection based on the NoC's gate-level netlist. Experimental results obtained from a partially and vertically connected 3D-NoC indicate that our solution can provide a high level of reliability in the presence of errors, at the expense of an area and power overhead of 4.1% and 6.8% respectively.

Multi- and many-core systems on chip provide an even share of opportunities and challenges regarding the design of modern embedded systems. The FORMUS 3 IC research group is dedicated to investigate these problems and provide novel holistic ideas and solutions for the design process of automotive andavionic applications alike.An extract on new concepts conceived in the context of this project regarding real-time systems and dependability is presented. Furthermore, follow up steps in the development process of these concepts are discussed.In the domain of scheduling, the application of a gang-based scheduling concept for real-time systems is proposed and discussed. This concept aims to allow multithreading in the context of real-time system.Regarding dependability, a fault-tolerance concept based on triple modular redundancy and arithmetic encoding is described. Furthermore, evaluation via fault injection is described and the conceptional work for the fault injection back-end is provided.

Software tasks are time constrained in real time computing systems. To ensure the safety of the critical systems that embeds the real time system, it is of paramount importance to safely estimate the worst-case execution time of each task. Modern commercial processors optimisation components enable to reduce in average the task execution time at the cost of a hard to determine task worst-case execution time.Many approaches for executing a task worst-case execution time exist but are usually segre-gated and hardly scalable, or by building very complex models. Measurement-based probabilistic timing analysis approaches are said to be easy and fast, but they suer from a lack of systematism and confidence in their estimates.This thesis studies the applicability of the extreme value theory to a sequence of execution time measurements for the estimation of the probabilistic worst-case execution time, leading to the development of the diagXtrm tool. Thanks to a large panel of sequences of measurements from dierent real time systems, capabilities and limits of the tool are enlightened. Finally, a couple of methods are provided for determining measurements conditions that foster the appli-cation of the theory and raise more confidence in the estimates., Dans les systèmes informatiques temps réel, les tâches logicielles sont contraintes par le temps. Pour garantir la sûreté du système critique controlé par le système temps réel, il est primordial d'estimer de manière sûre le pire temps d'exécution de chaque tâche. Les performances des processeurs actuels du commerce permettent de réduire en moyenne le temps d'exécution des tâches, mais la complexité des composants d'optimisation de la plateforme rendent difficile l'estimation du pire temps d'exécution. Il existe différentes approches d'estimation du pire temps d'exécution, souvent ségréguées et difficilement généralisables ou au prix de modèles coûteux. Les approches probabilistes basées mesures existantes sont vues comme étant rapides et simples à mettre en œuvre, mais souffrent d'un manque de systématisme et de confiance dans les estimations qu'elles fournissent. Les travaux de cette thèse étudient les conditions d'application de la théorie des valeurs extrêmes à une suite de mesures de temps d'exécution pour l'estimation du pire temps d'exécution probabiliste, et ont été implémentées dans l'outil \diagxtrm. Les capacités et les limites de l'outil ont été étudiées grâce à diverses suites de mesures issues de systèmes temps réel différents. Enfin, des méthodes sont proposées pour déterminer les conditions de mesure propices à l'application de la théorie des valeurs extrêmes et donner davantage de confiance dans les estimations.

Corner detection is a key kernel for many image processing procedures including pattern recognition and motion detection. The latter, for instance, mainly relies on the corner points for which spatial analyses are performed, typically on (probably live) videos or temporal flows of images. Thus, highly efficient corner detection is essential to meet the real-time requirement of associated applications. In this paper, we consider the corner detection algorithm proposed by Harris, whose the main work-flow is a composition of basic operators represented by their approximations using 3 × 3 matrices. The corresponding data access patterns follow a stencil model, which is known to require careful memory organization and management. Cache misses and other additional hindering factors with NUMA architectures need to be skillfully addressed in order to reach an efficient scalable implementation. In addition, with an increasingly wide vector registers, an efficient SIMD version should be designed and explicitly implemented. In this paper, we study a direct and explicit implementation of common and novel optimization strategies, and provide a NUMA-aware parallelization. Experimental results on a dual-socket INTEL Bradwell-E/EP show a noticeably good scalability performance.

Many linear algebra libraries, such as the Intel MKL, Magma or Eigen, provide fast Cholesky factorization. These libraries are suited for big matrices but perform slowly on small ones. Even though State-of-the-Art studies begin to take an interest in small matrices, they usually feature a few hundreds rows. Fields like Computer Vision or High Energy Physics use tiny matrices. In this paper we show that it is possible to speed up the Cholesky factorization for tiny matrices by grouping them in batches and using highly specialized code. We provide High Level Transformations that accelerate the factorization for current multi-core and many-core SIMD architectures ( SSE, AVX 2, KNC, AVX512 , Neon, Altivec). We focus on the fact that, on some architectures, compilers are unable to vectorize and on other architectures, vectorizing compilers are not efficient. Thus hand-made SIMD ization is mandatory. We achieve with these transformations combined with SIMD a speedup from × 14 to × 28 for the whole resolution in single precision compared to the naive code on a AVX 2 machine and a speedup from × 6 to × 14 on double precision, both with a strong scalability.

International audience; We introduce a novel method revealing hidden bifurcations in the multispiral Chua attractorin the case where the parameter of bifurcation c which determines the number of spiral isdiscrete. This method is based on the core idea of the genuine Leonov and Kuznetsov methodfor searching hidden attractors (i.e. applying homotopy and numerical continuation) but used ina very different way. Such hidden bifurcations are governed by a homotopy parameter ε whereasc is maintained constant. This additional parameter which is absent from the initial problem isperfectly fitted to unfold the actual structure of the multispiral attractor. We study completelythe multispiral Chua attractor, generated via sine function, and check numerically our methodfor odd and even values of c from 1 to 12. In addition, we compare the shape of the attractorsobtained for the same value of parameter ε while varying the parameter c.

International audience; The emergence of accelerators as standard computing resources on supercomputers and the subsequent architectural complexity increase revived the need for high-level parallel programming paradigms. Sequential task-based programming model has been shown to efficiently meet this challenge on a single multicore node possibly enhanced with accelerators, which motivated its support in the OpenMP 4.0 standard. In this paper, we show that this paradigm can also be employed to achieve high performance on modern supercomputers composed of multiple such nodes, with extremely limited changes in the user code. To prove this claim, we have extended the StarPU runtime system with an advanced inter-node data management layer that supports this model by posting communications automatically. We illustrate our discussion with the task-based tile Cholesky algorithm that we implemented on top of this new runtime system layer. We show that it enables very high productivity while achieving a performance competitive with both the pure Message Passing Interface (MPI)-based ScaLAPACK Cholesky reference implementation and the DPLASMA Cholesky code, which implements another (non-sequential) task-based programming paradigm.

This paper is submitted for review to the Parallel Computing special issue for HCW and HeteroPar 16 workshops; International audience; Hybrid computing platforms are now commonplace, featuring a large number of CPU cores and accelerators. This trend makes balancing computations between these heterogeneous resources performance critical. In this paper we propose ag-gregating several CPU cores in order to execute larger parallel tasks and improve load balancing between CPUs and accelerators. Additionally, we present our approach to exploit internal parallelism within tasks, by combining two runtime system schedulers: a global runtime system to schedule the main task graph and a local one one to cope with internal task parallelism. We demonstrate the relevance of our approach in the context of the dense Cholesky factorization kernel implemented on top of the StarPU task-based runtime system. We present experimental results showing that our solution outperforms state of the art implementations on two architectures: a modern heterogeneous machine and the Intel Xeon Phi Knights Landing.

Cyber physical systems (CPS) and Internet of Objects (IoT) are generating an unprecedentedvolume and variety of data that needs to be collected and stored on the cloud before beingprocessed. By the time the data makes its way to the cloud for analysis, the opportunity totrigger a reply might be late.One approach to solve this problem is to analyze the most time-sensitive data at the net-work edge, close to where it is generated. Thus, only the pre-processed results are sent tothe cloud. This computation model is know as *Fog Computing* or *Edge computing*. Crit-ical CPS applications using the fog computing model may have real-time constraints becauseresults must be delivered in a pre-determined time window. Furthermore, in many relevantapplications of CPS, the processing can be parallelized by applying the same processing ondifferent sub-sets of data at the same time by the mean parallel programming techniques. Thisallow to achieve a shorter response time, and then, a larger slack time, which can be used toreduce energy consumption.In this thesis we focus on the problem of scheduling a set of parallel tasks on multicoreprocessors, with the goal of reducing the energy consumption while all deadlines are met. Wepropose several realistic task models on architectures with identical and heterogeneous cores,and we develop algorithms for allocating threads to processors, select the core frequencies, andperform schedulability analysis. The proposed task models can be realized by using OpenMP-like APIs.; Les systèmes cyber-physiques (CPS) et d’Internet des objets génèrent un volume et une variété des données sans précédant. Le temps que ces données parcourent le réseau dans son chemin vers le cloud, la possibilité de réagir à un événement critique pourrait être tardive. Pour résoudre ce problème, les traitements de données nécessitant une réponse rapide sont faits à proximité d’où les données sont collectées. Ainsi, seuls les résultats du pré-traitement sont envoyées au cloud et la réaction pourrai être déclenché suffisamment rapide pour préserver l’intégrité du système. Ce modèle de calcul est connu comme Fog Computing. Un large spectre d’applications de CPS ont des contraintes temporelle et peuvent être facilement parallélisées en distribuant les calculs sur différents sous-ensembles de données en même temps. Ceci peut permettre d’obtenir un temps de réponse plus court et un temps de creux plus large. Ainsi, on peut réduire la fréquence du processeur et/ou éteindre des parties du processeur afin de réduire la consommation d’énergie. Dans cette thèse, nous nous concentrons sur le problème d'ordonnancement d’un ensemble de taches temps-réels parallèles sur des architectures multi-coeurs dans l’objectif de réduire la consommation d’énergie en respectant toutes les contraintes temporelles. Nous proposons ainsi plusieurs modèles de tâches et des testes d'ordonnançabilité pour résoudre le problème d’allocation des threads aux processeurs. Nous proposons aussi des méthodes qui permettent de sélectionner les fréquences et les états des processeurs. Les modèles proposés peuvent être implantés comme des directives dans la même logique que OpenMP.

Cyber physical systems (CPS) and Internet of Objects (IoT) are generating an unprecedentedvolume and variety of data that needs to be collected and stored on the cloud before beingprocessed. By the time the data makes its way to the cloud for analysis, the opportunity totrigger a reply might be late.One approach to solve this problem is to analyze the most time-sensitive data at the net-work edge, close to where it is generated. Thus, only the pre-processed results are sent tothe cloud. This computation model is know as *Fog Computing* or *Edge computing*. Crit-ical CPS applications using the fog computing model may have real-time constraints becauseresults must be delivered in a pre-determined time window. Furthermore, in many relevantapplications of CPS, the processing can be parallelized by applying the same processing ondifferent sub-sets of data at the same time by the mean parallel programming techniques. Thisallow to achieve a shorter response time, and then, a larger slack time, which can be used toreduce energy consumption.In this thesis we focus on the problem of scheduling a set of parallel tasks on multicoreprocessors, with the goal of reducing the energy consumption while all deadlines are met. Wepropose several realistic task models on architectures with identical and heterogeneous cores,and we develop algorithms for allocating threads to processors, select the core frequencies, andperform schedulability analysis. The proposed task models can be realized by using OpenMP-like APIs.; Les systèmes cyber-physiques (CPS) et d’Internet des objets génèrent un volume et une variété des données sans précédant. Le temps que ces données parcourent le réseau dans son chemin vers le cloud, la possibilité de réagir à un événement critique pourrait être tardive. Pour résoudre ce problème, les traitements de données nécessitant une réponse rapide sont faits à proximité d’où les données sont collectées. Ainsi, seuls les résultats du pré-traitement sont envoyées au cloud et la réaction pourrai être déclenché suffisamment rapide pour préserver l’intégrité du système. Ce modèle de calcul est connu comme Fog Computing. Un large spectre d’applications de CPS ont des contraintes temporelle et peuvent être facilement parallélisées en distribuant les calculs sur différents sous-ensembles de données en même temps. Ceci peut permettre d’obtenir un temps de réponse plus court et un temps de creux plus large. Ainsi, on peut réduire la fréquence du processeur et/ou éteindre des parties du processeur afin de réduire la consommation d’énergie. Dans cette thèse, nous nous concentrons sur le problème d'ordonnancement d’un ensemble de taches temps-réels parallèles sur des architectures multi-coeurs dans l’objectif de réduire la consommation d’énergie en respectant toutes les contraintes temporelles. Nous proposons ainsi plusieurs modèles de tâches et des testes d'ordonnançabilité pour résoudre le problème d’allocation des threads aux processeurs. Nous proposons aussi des méthodes qui permettent de sélectionner les fréquences et les états des processeurs. Les modèles proposés peuvent être implantés comme des directives dans la même logique que OpenMP.

In this thesis, we present our contributions to APOLLO: an automatic parallelization compiler that combines polyhedral optimization with Thread-Level-Speculation, to optimize dynamic codes on-the-fly. Thanks to an online profiling phase and a speculation model about the target's code behavior, Apollo is able to select an optimization and to generate code based on it. During optimized code execution, Apollo constantly verifies the validity of the speculation model. The main contribution of this thesis is a code generation mechanism that is able to instantiate any polyhedral transformation, at runtime, without incurring a major time-overhead. This mechanism is currently in use inside Apollo. We called it Code-Bones. It provides significant performance benefits when compared to other approaches.; Dans cette thèse, nous présentons nos contributions à APOLLO : un compilateur de parallélisation automatique qui combine l'optimisation polyédrique et la parallélisation spéculative, afin d'optimiser des programmes dynamiques à la volée. Grâce à une phase de profilage en ligne et un modèle spéculatif du comportement mémoire du programme cible, Apollo est capable de sélectionner une optimisation et de générer le code résultant. Pendant l'exécution du programme optimisé, Apollo vérifie constamment la validité du modèle spéculatif. La contribution principale de cette thèse est un mécanisme de génération de code qui permet d'instancier toute transformation polyédrique, au cours de l'exécution du programme cible, sans engendrer de surcoût temporel majeur. Ce procédé est désormais utilisé dans Apollo. Nous l'appelons Code-Bones. Il procure des gains de performance significatifs par comparaison aux autres approches.

In this thesis, we present our contributions to APOLLO: an automatic parallelization compiler that combines polyhedral optimization with Thread-Level-Speculation, to optimize dynamic codes on-the-fly. Thanks to an online profiling phase and a speculation model about the target's code behavior, Apollo is able to select an optimization and to generate code based on it. During optimized code execution, Apollo constantly verifies the validity of the speculation model. The main contribution of this thesis is a code generation mechanism that is able to instantiate any polyhedral transformation, at runtime, without incurring a major time-overhead. This mechanism is currently in use inside Apollo. We called it Code-Bones. It provides significant performance benefits when compared to other approaches.; Dans cette thèse, nous présentons nos contributions à APOLLO: un compilateur de parallélisation automatique qui combine l'optimisation polyédrique et la parallélisation spéculative, afin d'optimiser des programmes dynamiques à la volée. Grâce à une phase de profilage en ligne et un modèle spéculatif du comportement mémoire du programme cible, Apollo est capable de sélectionner une optimisation et de générer le code résultant. Pendant l'exécution du programme optimisé, Apollo vérifie constamment la validité du modèle spéculatif. La contribution principale de cette thèse est un mécanisme de génération de code qui permet d'instancier toute transformation polyédrique, au cours de l'exécution du programme cible, sans engendrer de surcoût temporel majeur. Ce procédé est désormais utilisé dans Apollo. Nous l'appelons \textit{Code-Bones}. Il procure des gains de performance significatifs par comparaison aux autres approches.

International audience; Single-ISA heterogeneous multicore processors have gained increasing popularity with the introduction of recent technologies such as ARM big.LITTLE. These processors offer increased energy efficiency through combining low power in- order cores with high performance out-of-order cores. Efficiently exploiting this attractive feature requires careful management so as to meet the demands of targeted applications. In this paper, we explore the design of those architectures based on the ARM big.LITTLE technology by modeling performance and power in gem5 and McPAT frameworks. Our models are validated w.r.t. the Samsung Exynos 5 Octa (5422) chip. We show average errors of 20% in execution time, 13% for power consumption and 24% for energy-to-solution.

The emergence of accelerators as standard computing resources on supercomputers and the subsequent architectural complexity increase revived the need for high-level parallel programming paradigms. Sequential task-based programming model has been shown to efficiently meet this challenge on a single multicore node possibly enhanced with accelerators, which motivated its support in the OpenMP 4.0 standard. In this paper, we show that this paradigm can also be employed to achieve high performance on modern supercomputers composed of multiple such nodes, with extremely limited changes in the user code. To prove this claim, we have extended the StarPU runtime system with an advanced inter-node data management layer that supports this model by posting communications automatically. We illustrate our discussion with the task- based tile Cholesky algorithm that we implemented on top of this new runtime system layer. We show that it allows for very high productivity while achieving a performance competitive with both the pure Message Passing Interface (MPI)-based ScaLAPACK Cholesky reference implemen- tation and the DPLASMA Cholesky code, which implements another (non sequential) task-based programming paradigm.; L’émergence d’accélérateurs comme ressources de calcul standard sur les supercalculateurs et la complexification associée des architectures ressuscite le besoin de paradigmes de programmation de haut niveau. La programmation par tâches séquentielle a montré qu’elle pouvait efficacement répondre à ce besoin sur un seul nœud de calcul multicœur possiblement dotée d’accélérateurs, ce qui a motivé son intégration dans le standard OpenMP 4.0. Dans ce papier, nous montrons que ce paradigme peut également être utilisé pour obtenir de hautes performances sur les supercalculateurs modernes composés de plusieurs de ces nœuds de calcul, tout en limitant à au maximum les changements dans le code utilisateur. Afin de prouver cette affirmation, nous avons ajouté au support d’exécution StarPU une couche avancée de gestion des données inter-nœuds qui supporte ce modèle en émettant automatiquement les communications. Nous illustrons notre discussion avec une factorisation de Cholesky tuilée en tâches que nous avons implémentée sur cette nouvelle couche de support exécutif. Nous montrons que cette méthode permet une grande productivité tout en permettant d’obtenir des performances compétitives tant avec l’implémentation de référence ScaLAPACK de Cholesky, qui est basée purement sur l’Interface de Passage de Message (MPI), qu’avec le code Cholesky de DPLASMA, qui implémente un autre modèle de programmation par tâches (non séquentiel).

The emergence of accelerators as standard computing resources on supercomputers and the subsequent architectural complexity increase revived the need for high-level parallel programming paradigms. Sequential task-based programming model has been shown to efficiently meet this challenge on a single multicore node possibly enhanced with accelerators, which motivated its support in the OpenMP 4.0 standard. In this paper, we show that this paradigm can also be employed to achieve high performance on modern supercomputers composed of multiple such nodes, with extremely limited changes in the user code. To prove this claim, we have extended the StarPU runtime system with an advanced inter-node data management layer that supports this model by posting communications automatically. We illustrate our discussion with the task- based tile Cholesky algorithm that we implemented on top of this new runtime system layer. We show that it allows for very high productivity while achieving a performance competitive with both the pure Message Passing Interface (MPI)-based ScaLAPACK Cholesky reference implemen- tation and the DPLASMA Cholesky code, which implements another (non sequential) task-based programming paradigm.; L’émergence d’accélérateurs comme ressources de calcul standard sur les supercalculateurs et la complexification associée des architectures ressuscite le besoin de paradigmes de programmation de haut niveau. La programmation par tâches séquentielle a montré qu’elle pouvait efficacement répondre à ce besoin sur un seul nœud de calcul multicœur possiblement dotée d’accélérateurs, ce qui a motivé son intégration dans le standard OpenMP 4.0. Dans ce papier, nous montrons que ce paradigme peut également être utilisé pour obtenir de hautes performances sur les supercalculateurs modernes composés de plusieurs de ces nœuds de calcul, tout en limitant à au maximum les changements dans le code utilisateur. Afin de prouver cette affirmation, nous avons ajouté au support d’exécution StarPU une couche avancée de gestion des données inter-nœuds qui supporte ce modèle en émettant automatiquement les communications. Nous illustrons notre discussion avec une factorisation de Cholesky tuilée en tâches que nous avons implémentée sur cette nouvelle couche de support exécutif. Nous montrons que cette méthode permet une grande productivité tout en permettant d’obtenir des performances compétitives tant avec l’implémentation de référence ScaLAPACK de Cholesky, qui est basée purement sur l’Interface de Passage de Message (MPI), qu’avec le code Cholesky de DPLASMA, qui implémente un autre modèle de programmation par tâches (non séquentiel).

Heterogeneity is emerging as one of the most challenging characteristics of today’s parallel environments. However, not many fully-featured advanced numerical, scientific libraries have been ported on such architectures. In this paper, we propose to extend a sparse hybrid solver for handling distributed memory heterogeneous platforms. As in the original solver, we perform a domain decomposition and associate one subdomain with one MPI process. However, while each subdomain was processed sequentially (binded onto a single CPU core) in the original solver, the new solver instead relies on task-based local solvers, delegating tasks to available computing units. We show that this “MPI+task” design conveniently allows for exploiting distributed memory heterogeneous machines. Indeed, a subdomain can now be processed on multiple CPU cores (such as a whole multicore processor or a subset of the available cores) possibly enhanced with GPUs. We illustrate our discussion with the MaPHyS sparse hybrid solver relying on the PaStiX and Chameleon dense and sparse direct libraries, respectively. Interestingly, this two-level MPI+task design furthermore provides extra flexibility for controlling the number of subdomains, enhancing the numerical stability of the considered hybrid method. While the rise of heterogeneous computing has been strongly carried out by the theoretical community, this study aims at showing that it is now also possible to build complex software layers on top of runtime systems to exploit heterogeneous architectures.

International audience; The Space industry, as several other real-time industries , is assessing the use of multicore processors as their main computing platform. While multicore processors bring the potential of integrating several software (mixed-criticality) functions , their use also brings some challenges. In particular, tasks running in multicores may experience high contention delays when accessing multicores' shared resources. This makes that the load that a task puts on shared resources impacts the Execution Time Bounds (ETBs) derived for other corunning tasks. In this paper we focus on the Cobham Gaisler NGMP – acknowledged as one of the multicore processors currently assessed by the European Space Agency for its future missions – for which we propose a measurement-based approach to bound contention interference. Given a task τ , instead of providing ETBs for the highest contention that any set of corunners can generate – already shown to be potentially high – our approach provides bounds that factor in the number of requests contenders generate regardless of how they align with τ 's requests. This provides a good balance between ETBs accuracy and independence from the corunners, since our approach only requires controlling the number of requests each task makes to the shared resources.

In the context of this thesis, our focus is on numerical linear algebra, more precisely on solution of large sparse systems of linear equations. We focus on designing efficient parallel implementations of MaPHyS, an hybrid linear solver based on domain decomposition techniques. First we investigate the MPI+threads approach. In MaPHyS, the first level of parallelism arises from the independent treatment of the various subdomains. The second level is exploited thanks to the use of multi-threaded dense and sparse linear algebra kernels involved at the subdomain level. Such an hybrid implementation of an hybrid linear solver suitably matches the hierarchical structure of modern supercomputers and enables a trade-off between the numerical and parallel performances of the solver. We demonstrate the flexibility of our parallel implementation on a set of test examples. Secondly, we follow a more disruptive approach where the algorithms are described as sets of tasks with data inter-dependencies that leads to a directed acyclic graph (DAG) representation. The tasks are handled by a runtime system. We illustrate how a first task-based parallel implementation can be obtained by composing task-based parallel libraries within MPI processes throught a preliminary prototype implementation of our hybrid solver. We then show how a task-based approach fully abstracting the hardware architecture can successfully exploit a wide range of modern hardware architectures. We implemented a full task-based Conjugate Gradient algorithm and showed that the proposed approach leads to very high performance on multi-GPU, multicore and heterogeneous architectures.; Dans le contexte de cette thèse, nous nous focalisons sur des algorithmes pour l’algèbre linéaire numérique, plus précisément sur la résolution de grands systèmes linéaires creux. Nous mettons au point des méthodes de parallélisation pour le solveur linéaire hybride MaPHyS. Premièrement nous considerons l'aproche MPI+threads. Dans MaPHyS, le premier niveau de parallélisme consiste au traitement indépendant des sous-domaines. Le second niveau est exploité grâce à l’utilisation de noyaux multithreadés denses et creux au sein des sous-domaines. Une telle implémentation correspond bien à la structure hiérarchique des supercalculateurs modernes et permet un compromis entre les performances numériques et parallèles du solveur. Nous démontrons la flexibilité de notre implémentation parallèle sur un ensemble de cas tests. Deuxièmement nous considérons un approche plus innovante, où les algorithmes sont décrits comme des ensembles de tâches avec des inter-dépendances, i.e., un graphe de tâches orienté sans cycle (DAG). Nous illustrons d’abord comment une première parallélisation à base de tâches peut être obtenue en composant des librairies à base de tâches au sein des processus MPI illustrer par un prototype d’implémentation préliminaire de notre solveur hybride. Nous montrons ensuite comment une approche à base de tâches abstrayant entièrement le matériel peut exploiter avec succès une large gamme d’architectures matérielles. À cet effet, nous avons implanté une version à base de tâches de l’algorithme du Gradient Conjugué et nous montrons que l’approche proposée permet d’atteindre une très haute performance sur des architectures multi-GPU, multicoeur ainsi qu’hétérogène.

In the context of this thesis, our focus is on numerical linear algebra, more precisely on solution of large sparse systems of linear equations. We focus on designing efficient parallel implementations of MaPHyS, an hybrid linear solver based on domain decomposition techniques. First we investigate the MPI+threads approach. In MaPHyS, the first level of parallelism arises from the independent treatment of the various subdomains. The second level is exploited thanks to the use of multi-threaded dense and sparse linear algebra kernels involved at the subdomain level. Such an hybrid implementation of an hybrid linear solver suitably matches the hierarchical structure of modern supercomputers and enables a trade-off between the numerical and parallel performances of the solver. We demonstrate the flexibility of our parallel implementation on a set of test examples. Secondly, we follow a more disruptive approach where the algorithms are described as sets of tasks with data inter-dependencies that leads to a directed acyclic graph (DAG) representation. The tasks are handled by a runtime system. We illustrate how a first task-based parallel implementation can be obtained by composing task-based parallel libraries within MPI processes throught a preliminary prototype implementation of our hybrid solver. We then show how a task-based approach fully abstracting the hardware architecture can successfully exploit a wide range of modern hardware architectures. We implemented a full task-based Conjugate Gradient algorithm and showed that the proposed approach leads to very high performance on multi-GPU, multicore and heterogeneous architectures., Dans le contexte de cette thèse, nous nous focalisons sur des algorithmes pour l’algèbre linéaire numérique, plus précisément sur la résolution de grands systèmes linéaires creux. Nous mettons au point des méthodes de parallélisation pour le solveur linéaire hybride MaPHyS. Premièrement nous considerons l'aproche MPI+threads. Dans MaPHyS, le premier niveau de parallélisme consiste au traitement indépendant des sous-domaines. Le second niveau est exploité grâce à l’utilisation de noyaux multithreadés denses et creux au sein des sous-domaines. Une telle implémentation correspond bien à la structure hiérarchique des supercalculateurs modernes et permet un compromis entre les performances numériques et parallèles du solveur. Nous démontrons la flexibilité de notre implémentation parallèle sur un ensemble de cas tests. Deuxièmement nous considérons un approche plus innovante, où les algorithmes sont décrits comme des ensembles de tâches avec des inter-dépendances, i.e., un graphe de tâches orienté sans cycle (DAG). Nous illustrons d’abord comment une première parallélisation à base de tâches peut être obtenue en composant des librairies à base de tâches au sein des processus MPI illustrer par un prototype d’implémentation préliminaire de notre solveur hybride. Nous montrons ensuite comment une approche à base de tâches abstrayant entièrement le matériel peut exploiter avec succès une large gamme d’architectures matérielles. À cet effet, nous avons implanté une version à base de tâches de l’algorithme du Gradient Conjugué et nous montrons que l’approche proposée permet d’atteindre une très haute performance sur des architectures multi-GPU, multicoeur ainsi qu’hétérogène.

International audience; In this talk we will discuss our research activities on the design of parallel linear solvers for large scale problems that range from dense linear algebra, to parallel sparse direct solver and hybrid iterative-direct approaches. In particular we will describe the implementations designed on top of runtime systems that should provide both code and performance portabilities. Finally, we will present some preliminary results on the integration of h-matrice kernels in our sparse direct solver framework.

Today, the processing of large dataset is generally parallelised and performed on computers with many cores. However, locks can serialize the execution of these cores and hurt the latency and the processing throughput. Spotting theses lock contention issues in-vitro (i.e. during the development phase) is complex because it is difficult to reproduce a production environment, to create a realistic workload representative of the context of use of the software and to test every possible configuration of deployment where will be executed the software. This thesis introduces Free Lunch, a lock profiler that diagnoses phases of high lock contention due to locks in-vivo (i.e. during the operational phase). Free Lunch is designed around a new metric, the Critical Section Pressure (CSP), which aims to evaluate the impact of lock contention on overall thread progress. Free Lunch is integrated in Hotpost in order to minimize the overhead and regularly reports the CSP during the execution in order to detect temporary issues due to locks. Free Lunch is evaluated over 31 benchmarks from Dacapo 9.12, SpecJVM08 and SpecJBB2005, and over the Cassandra database. We were able to pinpoint the phases of lock contention in 6 applications for which some of these were not detected by existing profilers. With this information, we have improved the performance of Xalan by 15% just by rewriting one line of code and identified a phase of high lock contention in Cassandra during the replay of transactions after a crash of a node. Free Lunch has never degraded performance by more than 6%, which makes it suitable to be deployed continuously in an operational environment.; Aujourd’hui, le traitement de grands jeux de données est généralement parallélisé et effectué sur des machines multi-cœurs. Cependant, les verrous peuvent sérialiser l'exécution de ces coeurs et dégrader la latence et le débit du traitement. Détecter ces problèmes de contention de verrous in-vitro (i.e. pendant le développement du logiciel) est complexe car il est difficile de reproduire un environnement de production, de créer une charge de travail réaliste représentative du contexte d’utilisation du logiciel et de tester toutes les configurations de déploiement possibles où s'exécutera le logiciel. Cette thèse présente Free Lunch, un profiler permettant d'identifier les phases de contention dues aux verrous in-vivo (i.e. en production). Free Lunch intègre une nouvelle métrique appelée Critical Section Pressure (CSP) évaluant avec précision l'impact de la synchronisation sur le progrès des threads. Free Lunch est directement intégré dans la JVM Hotspot pour minimiser le surcoût d'exécution et reporte régulièrement la CSP afin de pouvoir détecter les problèmes transitoires dus aux verrous. Free Lunch est évalué sur 31 benchmarks issus de Dacapo 9.12, SpecJVM08 et SpecJBB2005, ainsi que sur la base de données Cassandra. Nous avons identifié des phases de contention dans 6 applications dont certaines n'étaient pas détectées par les profilers actuels. Grâce à ces informations, nous avons amélioré la performance de Xalan de 15% en modifiant une seule ligne de code et identifié une phase de haute contention dans Cassandra. Free Lunch n’a jamais dégradé les performances de plus de 6% ce qui le rend approprié pour être déployé continuellement dans un environnement de production.

Today, the processing of large dataset is generally parallelised and performed on computers with many cores. However, locks can serialize the execution of these cores and hurt the latency and the processing throughput. Spotting theses lock contention issues in-vitro (i.e. during the development phase) is complex because it is difficult to reproduce a production environment, to create a realistic workload representative of the context of use of the software and to test every possible configuration of deployment where will be executed the software. This thesis introduces Free Lunch, a lock profiler that diagnoses phases of high lock contention due to locks in-vivo (i.e. during the operational phase). Free Lunch is designed around a new metric, the Critical Section Pressure (CSP), which aims to evaluate the impact of lock contention on overall thread progress. Free Lunch is integrated in Hotpost in order to minimize the overhead and regularly reports the CSP during the execution in order to detect temporary issues due to locks. Free Lunch is evaluated over 31 benchmarks from Dacapo 9.12, SpecJVM08 and SpecJBB2005, and over the Cassandra database. We were able to pinpoint the phases of lock contention in 6 applications for which some of these were not detected by existing profilers. With this information, we have improved the performance of Xalan by 15% just by rewriting one line of code and identified a phase of high lock contention in Cassandra during the replay of transactions after a crash of a node. Free Lunch has never degraded performance by more than 6%, which makes it suitable to be deployed continuously in an operational environment.; Aujourd’hui, le traitement de grands jeux de données est généralement parallélisé et effectué sur des machines multi-cœurs. Cependant, les verrous peuvent sérialiser l'exécution de ces coeurs et dégrader la latence et le débit du traitement. Détecter ces problèmes de contention de verrous in-vitro (i.e. pendant le développement du logiciel) est complexe car il est difficile de reproduire un environnement de production, de créer une charge de travail réaliste représentative du contexte d’utilisation du logiciel et de tester toutes les configurations de déploiement possibles où s'exécutera le logiciel. Cette thèse présente Free Lunch, un profiler permettant d'identifier les phases de contention dues aux verrous in-vivo (i.e. en production). Free Lunch intègre une nouvelle métrique appelée Critical Section Pressure (CSP) évaluant avec précision l'impact de la synchronisation sur le progrès des threads. Free Lunch est directement intégré dans la JVM Hotspot pour minimiser le surcoût d'exécution et reporte régulièrement la CSP afin de pouvoir détecter les problèmes transitoires dus aux verrous. Free Lunch est évalué sur 31 benchmarks issus de Dacapo 9.12, SpecJVM08 et SpecJBB2005, ainsi que sur la base de données Cassandra. Nous avons identifié des phases de contention dans 6 applications dont certaines n'étaient pas détectées par les profilers actuels. Grâce à ces informations, nous avons amélioré la performance de Xalan de 15% en modifiant une seule ligne de code et identifié une phase de haute contention dans Cassandra. Free Lunch n’a jamais dégradé les performances de plus de 6% ce qui le rend approprié pour être déployé continuellement dans un environnement de production.

International audience; Computing eigenpairs of a symmetric matrix is a problem arising in many industrial applications, including quantum physics and finite-elements computation for automo-biles. A classical approach is to reduce the matrix to tridiagonal form before computing eigenpairs of the tridiagonal matrix. Then, a back-transformation allows one to obtain the final solution. Parallelism issues of the reduction stage have already been tackled in different shared-memory libraries. In this article, we focus on solving the tridiagonal eigenproblem, and we describe a novel implementation of the Divide and Conquer algorithm. The algorithm is expressed as a sequential task-flow, scheduled in an out-of-order fashion by a dynamic runtime which allows the programmer to play with tasks granularity. The resulting implementation is between two and five times faster than the equivalent routine from the INTEL MKL library, and outperforms the best MRRR implementation for many matrices.

International audience; The parallelism in shared-memory systems has increased significantly with the advent and evolution of multicore processors. Current systems include several multicore and multithreaded processors with Non-Uniform Memory Access (NUMA) characteristics. These architectures require the adoption of two strategies for the efficient execution of parallel applications: (i) threads sharing data should be placed in such a way in the memory hierarchy that they execute on shared caches; and (ii) a thread should have the data that it accesses placed on the NUMA node where it is executing. We refer to these techniques as thread and data mapping, respectively. Both strategies require knowledge of the application’s memory access behavior to identify the communication between threads and processes as well as their usage of memory pages.In this paper, we introduce a profiling method to establish the suitability of parallel applications for improved mappings that take the memory hierarchy into account, based on a mathematical description of their memory access behaviors. Experiments with a large set of parallel workloads that are based on a variety of parallel APIs (MPI, OpenMP, Pthreads, and MPI+OpenMP) show that most applications can benefit from improved mappings. We provide a mechanism to compute optimized thread and data mappings. Experimental results with this mechanism showed performance improvements of up to 54% (20% on average), as well as reductions of the energy consumption of up to 37% (11% on average), compared to the default mapping by the operating system. Furthermore, our results show that thread and data mapping have to be performed jointly in order to achieve optimal improvements.

International audience; In this talk we will discuss our research activities on the design of parallel linear solvers for large scale problems that range from dense linear algebra, to parallel sparse direct solver and hybrid iterative-direct approaches. In particular we will describe the implementations designed on top of runtime systems that should provide both code and performance portabilities. Finally, we will present some preliminary results on the integration of h-matrice kernels in our sparse direct solver framework.

International audience; On contemporary cache-coherent Non-Uniform Memory Access (ccNUMA) architectures, applications with a large memory footprint suffer from the cost of the garbage collector (GC), because, as the GC scans the reference graph, it makes many remote memory accesses, saturating the interconnect between memory nodes. We address this problem with NumaGiC, a GC with a mostly-distributed design. In order to maximise memory access locality during collection, a GC thread avoids accessing a different memory node, instead notifying a remote GC thread with a message; nonetheless, NumaGiC avoids the drawbacks of a pure distributed design, which tends to decrease parallelism. We compare NumaGiC with Parallel Scavenge and NAPS on two different ccNUMA architectures running on the Hotspot Java Virtual Machine of OpenJDK 7. On Spark and Neo4j, two industry-strength analytics applications, with heap sizes ranging from 160 GB to 350 GB, and on SPECjbb2013 and SPECjbb2005, Numa-GiC improves overall performance by up to 45% over NAPS (up to 94% over Parallel Scavenge), and increases the performance of the collector itself by up to 3.6× over NAPS (up to 5.4× over Parallel Scavenge).

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

Embedded system development is complex. This complexity has several sources. A firstone is embedded system own specificities (physical world measurement and control, executionon a physical resource-constrained platform, reliability, responsiveness, . . . ) that distinguishthemselves from software systems. Another one comes from industrial concerns about whomthese systems are subject to : product and development costs and delays, multidisciplinaryteams, system documentation and certification. To handle this complexity, few methods andlanguages have been proposed. They focus on a modeling of both application and platform partincluded in an embedded system. However, the notions of method and process model are barelyknown from the embedded system community and current methods do not capitalize on theknowledge acquired by other engineering domains like information systems. The goal of thisthesis is the definition, the formalization and the tooling of an embedded system developmentmethod. To do that, this work focuses on four main contributions : (1) the formalization ofa guided process and a language to ensure a consistent modeling of both the application andthe platform, (2) the composition of complex platforms to permit a progressive implementationof an application on its concrete platform, (3) the integration of a project management anda product traceability allowing the project manager to measure and monitor the developmentprogress, to organize his team and to parallelize the development, and (4) the development ofa tool designed to support the process, the language and the project management; Le développement des systèmes embarqués est complexe. Cette complexité a plusieurs origines.D’une part, elle provient des caractéristiques propres des systèmes embarqués (mesureet contrôle du monde physique, exécution sur une plate-forme physique limitée en ressources,autonomie, fiabilité, réactivité, . . . ) qui les distinguent des systèmes purement logiciels. D’autrepart, elle est due aux fortes contraintes industrielles auxquelles ces systèmes sont soumis : coûtset délais de développement et de fabrication, équipes pluri-disciplinaires, certification et documentationdes systèmes. Afin de maitriser cette complexité, un certain nombre de méthodeset de langages furent proposés. Ils mettent l’accent sur une modélisation de l’application etde la plate-forme constituant le système embarqué. Cependant, les notions de méthode et deprocessus de développement qui abordent le problème de description des activités à réaliserne sont pas bien connues dans le domaine de l’ingénierie des systèmes embarqués et les méthodesactuelles tirent peu parti de l’expérience capitalisée dans d’autres domaines d’ingénierietels que les systèmes d’information. L’enjeu de cette thèse est la définition, la formalisation etl’outillage d’une méthode couvrant le développement des systèmes embarqués. Pour ce faire,ces travaux ont été axés autour de quatre contributions majeures : (1) la formalisation d’unprocessus guidé et d’un langage permettant une modélisation homogène d’une application et desa plate-forme, (2) la composition de plates-formes complexes permettant une implémentationprogressive d’une application sur sa plate-forme réelle, (3) l’intégration de la gestion de projetet de la traçabilité couplées aux produits offrant au chef de projet un moyen de mesurer etde piloter l’avancement de progression, d’organiser son équipe et de paralléliser les développements,et (4) le développement d’un outil dédié aux supports du processus, du langage et de lagestion de projet.

Numerous algorithms have been proposed to address the scheduling of real-time tasks for multiprocessor architectures. Yet, new scheduling algorithms have been defined very recently. Therefore, and without any guarantee of completeness, we have identified more than fifty of them. This large diversity makes the comparison of their behavior and performance difficult. This research aims at allowing the study and the evaluation of key scheduling algorithms. The first contribution is SimSo, a new simulation tool dedicated to the evaluation of scheduling algorithms. Using this tool, we were able to compare the performance of twenty algorithms. The second contribution is the consideration, in the simulation, of temporal overheads related to the execution of the scheduler and the impact of memory caches on the computation time of the jobs. This is done by the introduction of statistical models evaluating the cache miss ratios.; De multiples algorithmes ont été proposés pour traiter de l’ordonnancement de tâches temps réel dans un contexte multiprocesseur. Encore très récemment de nouvelles politiques ont été définies. Ainsi, sans garantie d’exhaustivité, nous en avons recensé plus d’une cinquantaine. Cette grande diversité rend difficile une analyse comparée de leurs comportements et performances. L’objectif de ce travail de thèse est de permettre l’étude et l’évaluation des principales politiques d’ordonnancement existantes. La première contribution est SimSo, un nouvel outil de simulation dédié à l’évaluation des politiques. Grâce à cet outil, nous avons pu comparer les performances d’une vingtaine d’algorithmes. La seconde contribution est la prise en compte, dans la simulation, des surcoûts temporels liés à l’exécution du code de l’ordonnanceur et à l’influence des mémoires caches sur la durée d’exécution des travaux par l’introduction de modèles statistiques évaluant les échecs d’accès à ces mémoires.

Numerous algorithms have been proposed to address the scheduling of real-time tasks for multiprocessor architectures. Yet, new scheduling algorithms have been defined very recently. Therefore, and without any guarantee of completeness, we have identified more than fifty of them. This large diversity makes the comparison of their behavior and performance difficult. This research aims at allowing the study and the evaluation of key scheduling algorithms. The first contribution is SimSo, a new simulation tool dedicated to the evaluation of scheduling algorithms. Using this tool, we were able to compare the performance of twenty algorithms. The second contribution is the consideration, in the simulation, of temporal overheads related to the execution of the scheduler and the impact of memory caches on the computation time of the jobs. This is done by the introduction of statistical models evaluating the cache miss ratios.; De multiples algorithmes ont été proposés pour traiter de l’ordonnancement de tâches temps réel dans un contexte multiprocesseur. Encore très récemment de nouvelles politiques ont été définies. Ainsi, sans garantie d’exhaustivité, nous en avons recensé plus d’une cinquantaine. Cette grande diversité rend difficile une analyse comparée de leurs comportements et performances. L’objectif de ce travail de thèse est de permettre l’étude et l’évaluation des principales politiques d’ordonnancement existantes. La première contribution est SimSo, un nouvel outil de simulation dédié à l’évaluation des politiques. Grâce à cet outil, nous avons pu comparer les performances d’une vingtaine d’algorithmes. La seconde contribution est la prise en compte, dans la simulation, des surcoûts temporels liés à l’exécution du code de l’ordonnanceur et à l’influence des mémoires caches sur la durée d’exécution des travaux par l’introduction de modèles statistiques évaluant les échecs d’accès à ces mémoires.

Embedded system development is complex. This complexity has several sources. A firstone is embedded system own specificities (physical world measurement and control, executionon a physical resource-constrained platform, reliability, responsiveness, . . . ) that distinguishthemselves from software systems. Another one comes from industrial concerns about whomthese systems are subject to : product and development costs and delays, multidisciplinaryteams, system documentation and certification. To handle this complexity, few methods andlanguages have been proposed. They focus on a modeling of both application and platform partincluded in an embedded system. However, the notions of method and process model are barelyknown from the embedded system community and current methods do not capitalize on theknowledge acquired by other engineering domains like information systems. The goal of thisthesis is the definition, the formalization and the tooling of an embedded system developmentmethod. To do that, this work focuses on four main contributions : (1) the formalization ofa guided process and a language to ensure a consistent modeling of both the application andthe platform, (2) the composition of complex platforms to permit a progressive implementationof an application on its concrete platform, (3) the integration of a project management anda product traceability allowing the project manager to measure and monitor the developmentprogress, to organize his team and to parallelize the development, and (4) the development ofa tool designed to support the process, the language and the project management; Le développement des systèmes embarqués est complexe. Cette complexité a plusieurs origines.D’une part, elle provient des caractéristiques propres des systèmes embarqués (mesureet contrôle du monde physique, exécution sur une plate-forme physique limitée en ressources,autonomie, fiabilité, réactivité, . . . ) qui les distinguent des systèmes purement logiciels. D’autrepart, elle est due aux fortes contraintes industrielles auxquelles ces systèmes sont soumis : coûtset délais de développement et de fabrication, équipes pluri-disciplinaires, certification et documentationdes systèmes. Afin de maitriser cette complexité, un certain nombre de méthodeset de langages furent proposés. Ils mettent l’accent sur une modélisation de l’application etde la plate-forme constituant le système embarqué. Cependant, les notions de méthode et deprocessus de développement qui abordent le problème de description des activités à réaliserne sont pas bien connues dans le domaine de l’ingénierie des systèmes embarqués et les méthodesactuelles tirent peu parti de l’expérience capitalisée dans d’autres domaines d’ingénierietels que les systèmes d’information. L’enjeu de cette thèse est la définition, la formalisation etl’outillage d’une méthode couvrant le développement des systèmes embarqués. Pour ce faire,ces travaux ont été axés autour de quatre contributions majeures : (1) la formalisation d’unprocessus guidé et d’un langage permettant une modélisation homogène d’une application et desa plate-forme, (2) la composition de plates-formes complexes permettant une implémentationprogressive d’une application sur sa plate-forme réelle, (3) l’intégration de la gestion de projetet de la traçabilité couplées aux produits offrant au chef de projet un moyen de mesurer etde piloter l’avancement de progression, d’organiser son équipe et de paralléliser les développements,et (4) le développement d’un outil dédié aux supports du processus, du langage et de lagestion de projet.

The amount of smartphone sales recently surpassed the desktop computer ones. This is mainly due to the smart integration of many functionalities in the same architecture. This is also due to the wide variety of supported applications like augmented reality, video conferencing and video games. The support of these applications is made by heterogeneous computing resources specialized to support each application type thus allowing to meet required performance and power consumption. For example, multimedia applications are accelerated by hardware modules that help video encoding and decoding and video game 3D rendering is accelerated by specialized processors (GPU). However, applications become more and more complicated. As an example, augmented reality requires image processing, 3D rendering and computing the information to display. This complexity often comes with a variation of the computing load, which dynamically changes application performance requirements. When this application is implemented in parallel, the way parallelism is chosen for a specific workload, becomes inefficient for a different one. This leads to a waste in computing resources and our objective is to optimize the usage of all available computing resources at runtime. The selected use case is a graphic rendering pipeline application because it is a dynamic application, which is also widely used in mobile devices. This application has been implemented and parallelized on a multicore architecture simulator. The profiling shows that the dynamicity of the application, the time and the amount of data needed to compute vary. The profiling also shows that the best balance of the parallelism depends on the rendered scene; a dynamic load balancing is therefore required for this application. These studies brought us about defining a system allowing to dynamically adapt the application parallelism depending on a prediction of its computing requirements, which can be performed by monitoring the data exchanges between the application tasks. Then the new parallelism is calculated for each stage by a central controller that manages the whole application. This system has been implemented in a Timed-TLM simulator in order to estimate performance improvements allowed by the dynamic adaptation. An architecture allowing to accelerate mobile applications, such as general-purpose and 3D applications, has been defined and compared to other multicore architectures. The hardware complexity and the performance of the architecture have also been estimated. For an increased complexity lower that 1,5%, we demonstrate performance improvements up to 20% compared with static parallelisms. We also demonstrated the ability to support a variable amount of resources.; Le nombre de smartphones vendus a récemment dépassé celui des ordinateurs. Ces appareils tendent à regrouper de plus en plus de fonctions, ceci grâce à des applications de plus en plus variées telles que la vidéo conférence, la réalité augmentée, ou encore les jeux vidéo. Le support de ces applications est assuré par des ressources de calculs hétérogènes qui sont spécifiques aux différents types de traitements et qui respectent les performances requises et les contraintes de consommation du système. Les applications graphiques, telles que les jeux vidéo, sont par exemple accélérées par un processeur graphique. Cependant les applications deviennent de plus en plus complexes. Une application de réalité augmentée va par exemple nécessiter du traitement d'image, du rendu graphique et un traitement des informations à afficher. Cette complexité induit souvent une variation de la charge de travail qui impacte les performances et donc les besoins en puissance de calcul de l'application. Ainsi, la parallélisation de l'application, généralement prévue pour une certaine charge, devient inappropriée. Ceci induit un gaspillage des ressources de calcul qui pourraient être exploitées par d'autres applications ou par d'autres étages de l'application. Un pipeline de rendu graphique a été choisi comme cas d'utilisation car c'est une application dynamique et qui est de plus en plus répandu dans les appareils mobiles. Cette application a été implémentée et parallélisée sur un simulateur d'architecture multi-cœurs. Un profilage a confirmé l'aspect dynamique, le temps de calcul de chaque donnée ainsi que le nombre d'objets à calculer variant de manière significative dans le temps et que la meilleure répartition du parallélisme évolue en fonction de la scène rendue. Ceci nous a amenés à définir un système permettant d'adapter, au fil de l'exécution, le parallélisme d'une application en fonction d'une prédiction faite de ses besoins. Le choix d'un nouveau parallélisme nécessite de connaître les besoins en puissance de calcul des différents étages, en surveillant les transferts de données entre les étages de l'application. Enfin, l'adaptation du parallélisme implique une nouvelle répartition des tâches en fonction des besoins des différents étages qui est effectuée grâce à un contrôleur central. Le système a été implémenté dans un simulateur précis au niveau TTLM afin d'estimer les gains de performances permis par l'adaptation dynamique. Une architecture permettant l'accélération de différents types d'applications que ce soit généralistes ou graphiques a été définie et comparée à d'autres architectures multi-cœurs. Le coût matériel de cette architecture a de plus été quantifié. Ainsi, pour un support matériel dont la complexité est inférieure à 1,5 % du design complet, on démontre des gains de performance allant jusqu'à 20 % par rapport à certains déploiements statiques, ainsi que la capacité à gérer dynamiquement un nombre de ressources de calcul variable.

International audience; This article presents a two-level strategy for scheduling large workloads of parallel applications in multicore distributed systems, taking into account the minimization of both the total computation time and the energy consumption of solutions. Nowadays, energy efficiency is of major concern when using large computing systems such as cluster, grid, and cloud computing facilities. In the approach proposed in this article, a combination of higher-level (i.e., between distributed systems) and lower-level (i.e., within each data-center) schedulers are studied for finding efficient mappings of workflows into the resources in order to maximize the quality of service, while reducing the energy required to compute them. The experimental evaluation demonstrates that accurate schedules are computed by using combined list scheduling heuristics (accounting for both problem objectives) in the higher level, and ad-hoc scheduling techniques to take advantage of multicore infrastructures in the lower level. Solutions are also evaluated with two user- and administrator-oriented metrics. Significant improvements are reported on the two problem objectives when compared with traditional load-balancing and round-robin techniques.