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.

L'objectif de cette thèse est d'offrir des outils d'aide à la certification aéronautique de processeurs COTS multi-cœurs. Ces architectures sont par nature parallèles et peuvent de ce fait largement améliorer les performances de calcul. Cependant elles souffrent d'un grand manque de prédictibilité, au sensoù calculer les pires d'exécution même pour des programmes simples est un problème complexe, voire impossible dans le cas général. En effet, les cœurs partagent l'accès à presque toutes les ressources ce qui provoque des conflits(qualifiés d'interférences) entrainant des variations non maîtrisées des temps d'exécutions. Parmi les mécanismes complexes d'un processeur multi-coeur se trouve la cohérence de caches. Celle-ci assure que tous les cœurs lisant ou écrivant dans un même bloc mémoire ne peuvent pas aveuglement ignorer les modifications appliquées par les autres. Afin de maintenir la cohérence de caches, le processeur suit un protocole pré-déterminé qui définit les messages à envoyer en fonction des actions d'un cœur ainsi que les actions à effectuer lors de la réception du message d'un autre cœur.Cette thèse porte sur l'identification des interférences générées par les mécanismes de cohérence de caches ainsi que sur les moyens de prédiction de leurs effets sur les applications en vue de réduire les effets négatifs temporels. La première contribution adresse les ambiguïtés dans la compréhension que les applicants ont de la cohérence de cache réellement présente dans l'architecture. En effet, la documentation des architectures ne fournit généralement pas suffisamment de détails sur les protocoles. Cette thèse propose une formalisation des protocoles standards, ainsi qu'une stratégie, reposant sur les micro-benchmarks, pour clarifier les choix d'implémentation du protocole de cohérence présent sur l'architecture. Cette stratégie a notamment été appliquée sur le NXP QorIQ T4240. Une fois le protocole correctement identifié, la seconde contribution consiste à réaliser une description bas-niveau de l'architecture en utilisant des automates temporisés afin de représenter convenablement les micro-comportements et comprendre clairement comment le protocole de cohérence de cache agit. Ainsi,un framework de génération de modèles génériques a été développé, capable de supporter plusieurs protocoles de cohérence de cache et de représenter différents agencements d'architectures afin de mieux correspondre à l'architecture choisie par le postulant. La troisième contribution explique comment utiliser cette représentation de l'architecture pour exhiber les interférences. Elle propose une stratégie pour détailler les causes et effets de chaque interférence liée à la cohérence de caches sur les programmes.Commençant par une simple analyse de temps d'exécution, les résultats descendent jusqu'au niveau des instructions pour indiquer comment chaque instruction génère et souffre des interférences. L'objectif étant alors de fournir suffisamment d'information à l'appliquant à la fois pour la certification, mais aussi pour définir une stratégie d'atténuation et de maîtrise des effets temporels.Ainsi, cette thèse fournit l'appliquant des outils pour comprendre les mécanismes de cohérence de cache présent sur une architecture donnée et pour exhiber les interférences associées. This thesis proposes tools to help in the certification of multi-coreprocessors for use in aeronautical systems. While the parallel nature of multi-core processors can greatly improve computation speeds, it also makesthem difficult to predict, preventing their use in critical environments. Indeed, in such processors, the cores share access to nearly all resources and this causes conflicts, or interference, which lead to seemingly randomvariation in the execution time. Among the complex mechanisms prone to interference is cache coherence, which ensures that cores that use a same atomic memory block cannot blindly override the modifications made by another core and that all cores are made aware of all modifications. To achieve cache coherence, the processor automatically follows a predetermined protocol which defines messages to be generated according to the actions of a core, as well as the actions to be performed when another core’s message is received.The focus of this thesis is to identify the interference generated by the cache coherence mechanisms and provide a way to predict their effects on the applications, as a first step toward their mitigation. The first contribution made is to address the ambiguities in the understanding applicants have of the coherence protocol implemented on their chosen architecture. Indeed,architecture documentation does not generally offer sufficient details on their cache coherence protocol. This thesis proposes a formalization of some standard cache protocols and a strategy relying on micro-benchmarks in order to clarify the implementation details of the architecture’s protocol. This approach is applied to the NXP QorIQ T4240 architecture. Once the protocol has been correctly identified, the second contribution consists in the making of alow-level description of the architecture using timed automata in order to adequately represent the micro-behaviors and understand clearly how the cache coherence protocol acts. In effect, a generic model generation framework has been developed, capable of handling cache coherence protocols as described by the applicant, and to support architectures with different configurations in order to better fit the applicant’s chosen architecture. The third contribution explains how to make use of the timed automata low-level representation of the architecture to expose interference. It proposes a strategy to detail the causes and effects of cache coherence interference on the given programs.Starting from a simple analysis of execution time, the results go down to instruction level, indicating how each instruction generates and suffers from interference. This is intended to provide sufficient information on cache coherence interference to the applicant, both for the purposes of certification and to form the base upon which a mitigation strategy can be started.In effect, this thesis provides the applicant with the means to understand the cache coherence mechanisms used by their chosen architecture and to expose the interference they generate.

Interference on the memory system can cause significant slowdowns to applications running in parallel on COTS multi-core processors. They are caused by concurrent accesses to shared hardware resources in the memory system. The magnitude of the delays caused by this phenomenom is difficult to predict, making interference a major obstacle to the adoption of COTS multi-core processors in real-time systems. This thesis is devoted to the characterization of the sensivity of an application to memory interferences based on a characterization of its behavior in isolation. The goal is to determine a priori if an application is sensitive to this problem or not. Using a set microbenchmarks that we have previously introduced, we show that a purely quantitative characterization of memory access behavior characterizes the sensivity to interference in a very imprecise way. In order to allow a more precise characterization of sensivity, we introduce different metrics to quantify quantitative and qualitative aspects of memory use. In order to measure the metrics, we implement a profiler prototype based on dynamic binary instrumentation approaches. In addition to allowing the measurement of qualitative aspects, this tool produces high-resolution profiles that clearly distinguish the different phases in application behaviors. Finally, we use data from our microbenchmarks to train a machine learning algorithm according to several characterizations. Experimental results show significant reductions in error reduction for the prediction of the delay undergone by applications of the MIBench and PARSEC suites., Les interférences du système mémoire peuvent entraîner d’importants ralentissements aux applications s’exécutant en parallèle sur les processeurs multi-coeurs COTS. Elles ont pour origine les accès concurrents aux ressources matérielles partagées du système mémoire. L’ampleur des retards causés par ce phénomène s’avère difficile à prédire, faisant des interférences un obstacle majeur à l’adoption des processeurs multi-cœurs COTS dans les systèmes temps-réels. Cette thèse est consacrée à la caractérisation de la sensibilité d’une application aux interférences mémoires à partir d’une caractérisation de son comportement exécutée seule. Le but étant de pouvoir déterminer à priori si une application est sensible à ce problème ou non. À l’aide d’un ensemble de microbenchmarks que nous avons préalablement introduit, nous montrons qu’une caractérisation purement quantitative du comportement d’accès à la mémoire caractérise la sensibilité aux interférences de façon très imprécise. Afin de permettre une caractérisation plus précise de la sensibilité, nous introduisons différentes métriques permettant de quantifier des aspects quantitatifs de l’utilisation de la mémoire. Afin de mesurer ces métriques, nous implémentons un prototype de profileur reposant sur des approches d’instrumentation binaire dynamique. En plus de permettre la mesure des aspects qualitatifs, cet outil produit des profils haute résolution permettant de distinguer clairement les différentes phases dans les comportements applicatifs. Enfin, nous utilisons les données issues de nos microbenchmarks pour entraîner un algorithme d’apprentissage automatique selon plusieurs caractérisations. Les résultats expérimentaux montrent des réductions significatives de réduction d’erreur pour la prédiction du retard subi par des applications des suites MIBENCH et PARSEC.

Discrete model resolution by numerical calculation benefits a dizzying number of industrial and general interest applications. It isalso necessary for heterogeneous machine evolutions to be exploited by calculation software. Thus, this thesis aims to explore theimpact of parallelism in modern architecture on geoscientific calculations. Consequently, this thesis work is particularly interestedin the categories of stencil resolution kernels and spectral finite elements. Work already carried out on these kernels consists instructuring, cutting and attacking the calculation in such a way as to exploit the resources of the machines in parallel. In addition,they also provide methods, models and tools for experimental analysis. Our approach consists in combining different parallelismcapacities for a given calculation kernel. Indeed, the latest Intel x86 processor developments have multiple superscalar, vector andmulti-core parallelism capabilities. The results of our work are consistent with those in the literature. First of all, we notice that theautomated vector optimizations of compilers are inefficient. In addition, the work of this thesis succeeds in refining the analysismodels. Thus, we observe an adequacy of the refined models with the experimental observations. In addition, the performanceachieved exceeds parallel reference implementations. These discoveries confirm the need to integrate these optimizations intocalculation abstraction solutions. Indeed, these solutions would better integrate the purpose of the calculations to be optimizedand can thus better couple them to the functioning of the target architectures., La résolution discrète de modèle par calcul numérique profite à un nombre vertigineux d’applications autant industrielles qued’intérêt général. Aussi, il est nécessaire que les évolutions hétérogènes des machines soient exploitées par les logiciels decalcul. Ainsi, cette thèse vise à explorer l’impact du parallélisme d’architecture moderne à destination des calculs géoscientifiques.Par conséquent, ces travaux de thèse s’intéressent tout particulièrement aux catégories de noyaux de résolution stencil etéléments finis spectraux. Des travaux déjà réalisés sur ces noyaux consistent à structurer, découper et attaquer le calcul de façonà exploiter en parallèle les ressources des machines. De plus, ils apportent également des méthodes, modèles et outils d’analyseexpérimentale. Notre approche consiste pour un noyau de calcul donné à y cumuler différentes capacités de parallélisme. Eneffet, les dernières évolutions de processeur Intel x86 disposent de multiples capacités de parallélisme superscalaire, vectoriel etmulti-coeurs. Les résultats de nos travaux concordent avec ceux de la littérature. Tout d’abord, on constate que les optimisationsvectorielles automatisées des compilateurs sont inefficaces. Par ailleurs, les travaux de cette thèse parviennent à affiner lesmodèles d’analyse. Ainsi, on observe une adéquation des modèles affinés avec les observations expérimentales. De plus,les performances atteintes dépassent des implémentations parallèles de références. Ces découvertes confortent la nécessitéd’intégrer ces optimisations à des solutions d’abstraction de calcul. En effet, ces solutions intègreraient davantage la finalité descalculs à optimiser et peuvent ainsi les coupler davantage au fonctionnement des architectures cibles.

International audience; The Phylog project aims at offering a model-based software-aided certification framework for aeronautical systems based on multi/many-core architectures. Certifying such platforms will entail fulfilling the high level objectives of the MCP-CRI / CAST-32A position paper. Among those, two types of analysis are required: interference and safety analyses. Because of the large size of the platforms and their complexity, those analyses can lead to combinatorial explosion and to some misinterpretation. To tackle these issues, we explore a service-based modelling approach that leads to a simplification of the analyses and to the highlighting of salient properties, making the adaptation of the certification argumentation efficient.

We investigate multi-criteria optimization and Pareto front generation. Given an application modeled as a Directed Acyclic Graph (DAG) of tasks and a multicore architecture, we produce a set of non-dominated (in the Pareto sense) static schedules of this DAG onto this multicore. The criteria we address are the execution time, reliability, power consumption, and peak temperature. These criteria exhibit complex antagonistic relations, which make the problem challenging. For instance, improving the reliability requires adding some redundancy in the schedule, which penalizes the execution time. To produce Pareto fronts in this 4-dimension space, we transform three of the four criteria into constraints (the reliability, the power consumption, and the peak temperature), and we minimize the fourth one (the execution time of the schedule) under these three constraints. By varying the thresholds used for the three constraints, we are able to produce a Pareto front of non-dominated solutions. We propose two algorithms to compute static schedules. The first is a ready list scheduling heuristic called ERPOT (Execution time, Reliability, POwer consumption and Temperature). ERPOT actively replicates the tasks to increase the reliability, uses Dynamic Voltage and Frequency Scaling to decrease the power consumption, and inserts cooling times to control the peak temperature. The second algorithm uses an Integer Linear Programming (ILP) program to compute an optimal schedule. However, because our multi-criteria scheduling problem is NP-complete, the ILP algorithm is limited to very small problem instances. Comparisons showed that the schedules produced by ERPOT are on average only 10% worse than the optimal schedules computed by the ILP program, and that ERPOT outperforms the PowerPerf-PET heuristic from the literature on average by 33%.; Nous nous attaquons à l’optimisation multi-critères et à la génération de fronts de Pareto. Etant données une application modélisée sous la forme d’un graphe orienté sans cycle (DAG) de tâches et une architecture multi-cœurs, nous calculons un ensemble d’ordonnancements statiques non dominés (au sens de Pareto) de ce DAG sur ce multi-cœurs. Les critères que nous considérons sont le temps d’exécution, la fiabilité, la puissance électrique et la température de crête. Ces critères présentent des relations complexes d’antagonisme, ce qui fait de notre problème d’ordonnancement un vrai défi. Par exemple, améliorer la fiabilité requiert d’ajouter de la redondance dans l’ordonnancement, ce qui pénalise le temps d’exécution. Afin de produire des fronts de Pareto dans cet espace à quatre dimensions, nous transformons trois de ces quatre critères en contraintes (la fiabilité, la puissance électrique et la température de crête) et nous minimisons le quatrième (le temps d’exécution) sous ces trois contraintes. En faisant varier les seuils utilisés pour les trois contraintes, nous sommes capables de produire un front de Pareto de solutions non-dominées. Nous proposons deux algorithmes pour calculer des ordonnancements statiques. Le premier est une heuristique de liste appelé ERPOT (Execution time, failure Rate, POwer consumption and Temperature). ERPOT réplique activement la tâches pour améliorer la fiabilité, utilise l’Ajustement Dynamique de la Fréquence et de la Tension (ADFT) pour réduire la puissance électrique, et insère des intervalles d’inactivité pour contrôler la température de crête. Le second algorithme repose sur un Programme Linéaire en Nombres Entiers (PLNE) pour construire un ordonnancement optimal. Toutefois, dans la mesure où notre problème d’ordonnancement multi-critères est NP-complet, l’algorithme PLNE est limité à des instances de très petite taille. Les comparaisons montrent que les ordonnancements produits par ERPOT sont en moyenne 10% moins bons que les ordonnancements optimaux calculés par l’algorithme PNLE, et que ERPOT améliore en moyenne de 33% les ordonnancements produit par l’heuristique PowerPerf-PET de la littérature.

Multi-core architectures using scratch pad memories are very attractive to execute embedded time-critical applications, because they offer a large computational power. However, ensuring that timing constraints are met on such platforms is challenging, because some hardware resources are shared between cores. When targeting the bus connecting cores and external memory, worst-case sharing scenarios are too pessimistic.This thesis propose strategies to reduce this pessimism. These strategies offer to both improve the accuracy of worst-case communication costs, and to exploit hardware parallel capacities by overlapping computations and communications. Moreover, fragmenting the latter allow to increase overlapping possibilities.; Les architectures multi-coeurs utilisant des mémoire bloc-notes sont des architectures attrayantes pour l’exécution des applications embarquées temps-réel, car elles offrent une grande capacité de calcul. Cependant, les systèmes temps-réel nécessitent de satisfaire des contraintes temporelles, ce qui peut être compliqué sur ce type d’architectures à cause notamment des ressources matérielles physiquement partagées entre les coeurs. Plus précisément, les scénarios de pire cas de partage du bus de communication entre les coeurs et la mémoire externe sont trop pessimistes.Cette thèse propose des stratégies pour réduire ce pessimisme lors de l’ordonnancement d’applications sur des architectures multi-coeurs. Tout d’abord, la précision du pire cas des coûts de communication est accrue grâce aux informations disponibles sur l’application et l’état de l’ordonnancement en cours. Ensuite, les capacités de parallélisation du matériel sont exploitées afin de superposer les calculs et les communications. De plus, les possibilités de superposition sont accrues par le morcellement de ces communications.

In this thesis, we are interested in solving the Vlasov–Poisson system of equations (useful in the domain of plasma physics, for example within the ITER project), thanks to classical Particle-in-Cell (PIC) and semi-Lagrangian methods. The main contribution of our thesis is an efficient implementation of the PIC method on multi-core architectures, written in C, called Pic-Vert. Our implementation (a) achieves close-to-minimal number of memory transfers with the main memory, (b) exploits SIMD instructions for numerical computations, and (c) exhibits a high degree of shared memory parallelism. To put our work in perspective with respect to the state-of-the-art, we propose a metric to compare the efficiency of different PIC implementations when using different multi-core architectures. Our implementation is 3 times faster than other recent implementations on the same architecture (Intel Haswell)., Cette thèse a pour contexte la résolution numérique du système de Vlasov–Poisson (modèle utilisé en physique des plasmas, par exemple dans le cadre du projet ITER) par les méthodes classiques particulaires (PIC pour "Particle-in-Cell") et semi-Lagrangiennes. La contribution principale de notre thèse est une implémentation efficace de la méthode PIC pour architectures multi-coeurs, écrite dans le langage C, dont le nom est Pic-Vert. Notre implémentation (a) atteint un nombre quasi-minimal de transferts mémoires avec la mémoire principale, (b) exploite les instructions vectorielles (SIMD) pour les calculs numériques, et (c) expose une quantité suffisante de parallélisme, en mémoire partagée. Pour mettre notre travail en perspective avec l'état de l'art, nous proposons une métrique permettant de comparer différentes implémentations sur différentes architectures. Notre implémentation est 3 fois plus rapide que d'autres implémentations récentes sur la même architecture (Intel Haswell).

In this thesis, we are interested in solving the Vlasov–Poisson system of equations (useful in the domain of plasma physics, for example within the ITER project), thanks to classical Particle-in-Cell (PIC) and semi-Lagrangian methods. The main contribution of our thesis is an efficient implementation of the PIC method on multi-core architectures, written in C, called Pic-Vert. Our implementation (a) achieves close-to-minimal number of memory transfers with the main memory, (b) exploits SIMD instructions for numerical computations, and (c) exhibits a high degree of shared memory parallelism. To put our work in perspective with respect to the state-of-the-art, we propose a metric to compare the efficiency of different PIC implementations when using different multi-core architectures. Our implementation is 3 times faster than other recent implementations on the same architecture (Intel Haswell).; Cette thèse a pour contexte la résolution numérique du système de Vlasov–Poisson (modèle utilisé en physique des plasmas, par exemple dans le cadre du projet ITER) par les méthodes classiques particulaires (PIC pour "Particle-in-Cell") et semi-Lagrangiennes. La contribution principale de notre thèse est une implémentation efficace de la méthode PIC pour architectures multi-coeurs, écrite dans le langage C, dont le nom est Pic-Vert. Notre implémentation (a) atteint un nombre quasi-minimal de transferts mémoires avec la mémoire principale, (b) exploite les instructions vectorielles (SIMD) pour les calculs numériques, et (c) expose une quantité suffisante de parallélisme, en mémoire partagée. Pour mettre notre travail en perspective avec l'état de l'art, nous proposons une métrique permettant de comparer différentes implémentations sur différentes architectures. Notre implémentation est 3 fois plus rapide que d'autres implémentations récentes sur la même architecture (Intel Haswell).

When designing complex cyber-physical systems, engineers have to integrate numerical models from different modeling environments in order to simulate the whole system and estimate its global performances. If some parts of the system are physically available, it is possible to connect these parts to the simulation in a Hardware-in-the-Loop (HiL) approach. In this case, the simulation has to be performed in real-time where models execution consists in periodically reacting to the real (physically available) components and providing periodic output updates. The increase of requirements on the simulation accuracy and its validity domain requires more complex models. Using such models, it becomes hard to ensure fast or real-time execution without using multiprocessor architectures. FMI (Functional Mocked-up Interface), an increasingly common standard for model exchange and co-simulation, offers new opportunities for multi-core execution of numerical models. One goal of this thesis is the extraction of potential parallelism in a set of interconnected multi-rate models. We build on the RCOSIM approach that has been previously developed at IFP Energies nouvelles and which allows the parallelization of FMI models on multi-core processors. It is based on representing the co-simulation by a dependence graph model. In the first part of the thesis, improvements have been proposed to overcome the limitations of RCOSIM. In particular, we propose new algorithms in order to allow handling models that exchange data at different rates and schedule them on multi-core processors. Also, the improvements allow handling specific constraints such as mutual exclusion and real-time constraints. Second, we propose algorithms for the allocation and non preemptive scheduling of the dependence graphs, taking into account their real-time, data dependence and allocation constraints. These algorithms aim at accelerating the execution of the co-simulation or ensuring its real-time execution in a HiL approach. The proposed solutions have been tested on randomly generated dependence graphs and validated against an industrial use case which is an internal combustion engine co-simulation. This thesis is part of a joint action IFP Energies nouvelles-Inria, in which Inria brings its real-time systems experience to the numerical simulation challenges of IFP Energies nouvelles.; Lors de la conception de systèmes cyber-physiques complexes, les ingénieurs doivent intégrer des modèles numériques issus de différents environnements de modalisation afin de simuler l’ensemble du système et estimer ses performances globales. Si certaines parties du système sont physiquement disponibles, il est possible de connecter ces parties à la simulation dans une approche Hardware-in-the-Loop (HiL). Dans ce cas, la simulation doit être effectuée en temps-réel l’exécution des modèles consiste à réagir périodiquement aux composants réels (physiquement disponibles) et fournir des mises à jour périodiques des valeurs de sortie. L’augmentation des exigences sur la précision de la simulation et son domaine de validité nécessite des modèles plus complexes. En utilisant de tels modèles, il devient difficile d’assurer une exécution rapide ou en temps réel sans utiliser d'architectures multiprocesseur. FMI (Functional Mocked-up Interface), un standard de plus en plus adopté pour l'échange de modèles et la co-simulation, offre de nouvelles possibilités d’éxécution multi-coeur des modèles numériques. L’un des objectifs de cette thèse est de permettre l’extraction du parallélisme potentiel dans un ensemble de modèles multi-rate interconnectés. Nous nous appuyons sur l’approche RCOSIM qui a été développée auparavant à IFP Energies nouvelles et qui permet la parallélisation de modèles FMI sur des processeurs multi-coeurs. Cette approche est basée sur la représentation de la co-simulation par un graphe de dépendance. Dans la première partie de la thèse, des améliorations sont proposées dans le but de surmonter les limitations de RCOSIM. En particulier, nous proposons de nouveaux algorithmes pour permettre la prise en charge de modèles échangeant des données à des rythmes différents (multi-rate) et les ordonnancer sur des processeurs multi-coeur. En outre, les améliorations permettent de gérer des contraintes spécifiques telles que l’exclusion mutuelle et les contraintes temps-réel. Deuxièmement, nous proposons des algorithmes pour l’allocation et l’ordonnancement non prémptif des graphes de dépendance, entenant compte de leur contraintes de dépendance, temps réel, et d’allocation. Ces algorithmes visent à accélérer l’exécution de la co-simulation ou assurer son exécution en temps-réel dans une approche HiL. Les solutions proposées sont testés sur des graphes de dépendance générés aléatoirement et validées sur un cas d’utilisation industriel qui est une co-simulation d’un moteur à combustion interne. Cette thèse est une partie d'une action conjointe entre IFP Energies nouvelle et Inria, Inria a apporté son expertise en temps réel aux challenges sur la simulation numérique auxquels participe IFP Energies nouvelles.

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

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

Nowadays, real-time applications are more compute-intensive as more functionalities are introduced. Multi-core platforms have been released to satisfy the computing demand while reducing the size, weight, and power requirements. The most significant challenge when deploying real-time systems on multi-core platforms is to guarantee the real-time constraints of hard real-time applications on such platforms. This is caused by interdependent problems, referred to as a chicken and egg situation, which is explained as follows. Due to the effect of multi-core hardware, such as local caches and shared hardware resources, the timing behavior of tasks are strongly influenced by their execution context (i.e., co-located tasks, concurrent tasks), which are determined by scheduling strategies. Symmetrically, scheduling algorithms require the Worst-Case Execution Time (WCET) of tasks as prior knowledge to determine their allocation and their execution order.Most schedulability analysis techniques for multi-core architectures assume a single WCET per task, which is valid in all execution conditions. This assumption is too pes- simistic for parallel applications running on multi-core architectures with local caches. In such architectures, the WCET of a task depends on the cache contents at the beginning of its execution, itself depending on the task that was executed before the task under study. In this thesis, we address the issue by proposing scheduling algorithms that take into account context-sensitive WCETs of tasks due to the effect of private caches.We propose two scheduling techniques for multi-core architectures equipped with local caches. The two techniques schedule a parallel application modeled as a task graph, and generate a static partitioned non-preemptive schedule. We propose an optimal method, using an Integer Linear Programming (ILP) formulation, as well as a heuristic method based on list scheduling. Experimental results show that by taking into account the effect of private caches on tasks’ WCETs, the length of generated schedules are significantly reduced as compared to schedules generated by cache-unaware scheduling methods.Furthermore, we perform the implementation of time-driven cache-conscious schedules on the Kalray MPPA-256 machine, a clustered many-core platform. We first identify the practical challenges arising when implementing time-driven cache-conscious schedules on the machine, including cache pollution caused by the scheduler, shared bus contention, delay to the start time of tasks, and the absence of data cache coherence. We then propose our strategies including an ILP formulation for adapting cache-conscious schedules to the identified practical factors, and a method for generating the code of applications to be executed on the machine. Experimental validation shows the functional and the temporal correctness of our implementation. Additionally, shared bus contention is observed to be the most impacting factor on the length of adapted cache-conscious schedules.; Les temps avancent et les applications temps-réel deviennent de plus en plus gourmandes en ressources. Les plateformes multi-cœurs sont apparues dans le but de satisfaire les demandes des applications en ressources, tout en réduisant la taille, le poids, et la consommation énergétique. Le challenge le plus pertinent, lors du déploiement d’un système temps-réel sur une plateforme multi-cœur, est de garantir les contraintes temporelles des applications temps réel strict s’exécutant sur de telles plateformes. La difficulté de ce challenge provient d’une interdépendance entre les analyses de prédictabilité temporelle. Cette interdépendance peut être figurativement liée au problème philosophique de l’œuf et de la poule, et expliqué comme suit. L’un des pré-requis des algorithmes d’ordonnancement est le Pire Temps d’Exécution (PTE) des tâches pour déterminer leur placement et leur ordre d’exécution. Mais ce PTE est lui aussi influencé par les décisions de l’ordonnanceur qui va déterminer quelles sont les tâches co-localisées ou concurrentes propageant des effets sur les caches locaux et les ressources physiquement partagées et donc le PTE.La plupart des méthodes d’analyse pour les architectures multi-cœurs supputent un seul PTE par tâche, lequel est valide pour toutes conditions d’exécutions confondues. Cette hypothèse est beaucoup trop pessimiste pour entrevoir un gain de performance sur des architectures dotées de caches locaux. Pour de telles architectures, le PTE d’une tâche est dépendant du contenu du cache au début de l’exécution de la dite tâche, qui est lui-même dépendant de la tâche exécutée avant et ainsi de suite. Dans cette thèse, nous proposons de prendre en compte des PTEs incluant les effets des caches privés sur le contexte d’éxecution de chaque tâche.Nous proposons dans cette thèse deux techniques d’ordonnancement ciblant des archi- tectures multi-cœurs équipées de caches locaux. Ces deux techniques ordonnancent une application parallèle modélisée par un graphe de tâches, et génèrent un planning statique partitionné et non-préemptif. Nous proposons une méthode optimale à base de Programma- tion Linéaire en Nombre Entier (PLNE), ainsi qu’une méthode de résolution par heuristique basée sur de l’ordonnancement par liste. Les résultats expérimentaux montrent que la prise en compte des effets des caches privés sur les PTE des tâches réduit significativement la longueur des ordonnancements générés, ce comparé à leur homologue ignorant les caches locaux.Afin de parfaire les résultats ainsi obtenus, nous avons réalisé l’implémentation de nos ordonnancements dirigés par le temps et conscients du cache pour un déploiement sur une machine Kalray MPPA-256, une plateforme multi-cœur en grappes (clusters). En premier lieu, nous avons identifé les challenges réels survenant lors de ce type d’implémentation, tel que la pollution des caches, la contention induite par le partage du bus, les délais de lancement d’une tâche introduits par la présence de l’ordonnanceur, et l’absence de cohérence des caches de données. En second lieu, nous proposons des stratégies adaptées et incluant, dans la formulation PLNE, les contraintes matérielles ; ainsi qu’une méthode permettant de générer le code final de l’application. Enfin, l’évaluation expérimentale valide la correction fonctionnelle et temporelle de notre implémentation pendant laquelle nous avons pu observé le facteur le plus impactant la longeur de l’ordonnancement: la contention.

Distributed systems are widely used in HPC (High Performance Computing). Owing to rising energy concerns, some chip manufacturers moved from multi-core CPUs to MPSoC (Multi-Processor System on Chip), which includes a distributed system on one chip.However distributed systems – with distributed memories – are hard to program compared to more friendly shared memory systems. A family of solutions called DSM (Distributed Shared Memory) systems has been developed to simplify the programming of distributed systems. DSM systems include NUMA architectures, PGAS languages, and distributed task runtimes. The common strategy of these systems is to create a global address space of some kind, and automate network transfers on accesses to global objects. DSM systems usually differ in their interfaces, capabilities, semantics on global objects, implementation levels (hardware / software), ...This thesis presents a new software DSM system called Givy. The motivation of Givy is to execute programs modeled as dynamic task graphs with data-flow dependencies on MPSoC architectures (MPPA). Contrary to many software DSM, the global address space of Givy is indexed by real pointers: raw C pointers are made global to the distributed system. Givy global objects are memory blocks returned by malloc(). Data is replicated across nodes, and all these copies are managed by a software cache coherence protocol called Owner Writable Memory. This protocol can relocate coherence metadata, and thus should help execute irregular applications efficiently. The programming model cuts the program into tasks which are annotated with memory accesses, and created dynamically. Memory annotations are used to drive coherence requests, and provide useful information for scheduling and load-balancing.The first contribution of this thesis is the overall design of the Givy runtime. A second contribution is the formalization of the Owner Writable Memory coherence protocol. A third contribution is its translation in a model checker language (Cubicle), and correctness validation attempts. The last contribution is the detailed allocator subsystem implementation: the choice of real pointers for global references requires a tight integration between memory allocator and coherence protocol.; Les architectures distribuées sont fréquemment utilisées pour le calcul haute performance (HPC). Afin de réduire la consommation énergétique, certains fabricants de processeurs sont passés d’architectures multi-cœurs en mémoire partagée aux MPSoC. Les MPSoC (Multi-Processor System On Chip) sont des architectures incluant un système distribué dans une puce.La programmation des architectures distribuées est plus difficile que pour les systèmes à mémoire partagée, principalement à cause de la nature distribuée de la mémoire. Une famille d’outils nommée DSM (Distributed Shared Memory) a été développée pour simplifier la programmation des architectures distribuées. Cette famille inclut les architectures NUMA, les langages PGAS, et les supports d’exécution distribués pour graphes de tâches. La stratégie utilisée par les DSM est de créer un espace d’adressage global pour les objets du programme, et de faire automatiquement les transferts réseaux nécessaires lorsque ces objets sont utilisés. Les systèmes DSM sont très variés, que ce soit par l’interface fournie, les fonctionnalités, la sémantique autour des objets globalement adressables, le type de support (matériel ou logiciel), ...Cette thèse présente un nouveau système DSM à support logiciel appelé Givy. Le but de Givy est d’exécuter sur des MPSoC (MPPA) des programmes sous la forme de graphes de tâches dynamiques, avec des dépendances de flot de données (data-flow ). L’espace d’adressage global (GAS) de Givy est indexé par des vrais pointeurs, contrairement à de nombreux autres systèmes DSM à support logiciel : les pointeurs bruts du langage C sont valides sur tout le système distribué. Dans Givy, les objets globaux sont les blocs de mémoire fournis par malloc(). Ces blocs sont répliqués entre les nœuds du système distribué, et sont gérés par un protocole de cohérence de cache logiciel nommé Owner Writable Memory. Le protocole est capable de déplacer ses propres métadonnées, ce qui devrait permettre l’exécution efficace de programmes irréguliers. Le modèle de programmation impose de découper le programme en tâches créées dynamiquement et annotées par leurs accès mémoire. Ces annotations sont utilisées pour générer les requêtes au protocole de cohérence, ainsi que pour fournir des informations à l’ordonnanceur de tâche (spatial et temporel).Le premier résultat de cette thèse est l’organisation globale de Givy. Une deuxième contribution est la formalisation du protocole Owner Writable Memory. Le troisième résultat est la traduction de cette formalisation dans le langage d’un model checker (Cubicle), et les essais de validation du protocole. Le dernier résultat est la réalisation et explication détaillée du sous-système d’allocation mémoire : le choix de pointeurs bruts en tant qu’index globaux nécessite une intégration forte entre l’allocateur mémoire et le protocole de cohérence de cache.

Networks-on-Chip (NoCs) have proven to be a fast and scalable replacement for buses in current and emerging many-core systems. They are today an actively researched topic and various solutions are being explored to meet the needs of emerging applications in terms of performance, quality of service, power consumption, and fault-tolerance. This thesis presents contributions in two important areas of Network-on-Chip research:- The design of ultra-flexible high-performance deadlock-free routing algorithms for any topology.- The design and implementation of parallel cycle-accurate Network-on-Chip simulators for a fast evaluation of new NoC architectures.While aggressive technology scaling has its benefits in terms of delay, area and power, it is also known to increase the vulnerability of circuits, suggesting the need for fault-tolerant designs. Fault-tolerance in NoCs is directly tied to the degree of flexibility of the routing algorithm. High routing flexibility is also required in some irregular topologies, as is the case for TSV-based 3D Network-on-Chips, wherein only a subset of the routers are connected using vertical connections. Unfortunately, routing freedom is often limited by the deadlock-avoidance method, which statically restricts the set of virtual channels that can be acquired by each packet.The first part of this thesis tackles this issue at the source and introduces a new topology-agnostic methodology for designing ultra-flexible routing algorithms for Networks-on-Chips. The theory relies on a novel low-restrictive sufficient condition of deadlock-freedom that is expressed using the local information available at each router during runtime, making it possible to verify the condition dynamically in a distributed manner.A significant gain in both performance and fault-tolerance when using our methodology compared to the existing static channel partitioning methods is reported. Moreover, hardware synthesis results show that the newly introduced mechanisms have a negligible impact on the overall router area.In the second part, a novel routing algorithm for vertically-partially-connected 3D Networks-on-Chips called First-Last is constructed using the previously presented methodology.Thanks to a unique distribution of virtual channels, our algorithm is the only one capable of guaranteeing full connectivity in the presence of one TSV pillar in an arbitrary position, while requiring a low number of extra buffers (1 extra VC in the East and North directions). This makes First-Last a highly appealing cost-effective alternative to the state-of-the-art Elevator-First algorithm.Finally, the third and last part of this work presents the first detailed and modular parallel NoC simulator design targeting Graphics Processing Units (GPUs). First, a flexible task decomposition approach, specifically geared towards high parallelization is proposed. Our approach makes it easy to adapt the granularity of parallelism to match the capabilities of the host GPU. Second, all the GPU-specific implementation issues are addressed and several optimizations are proposed. Our design is evaluated through a reference implementation, which is tested on an NVidia GTX980Ti graphics card and shown to speed up 4K-node NoC simulations by almost 280x., Grâce à une réduction considérable dans les dimensions des transistors, les systèmes informatiques sont aujourd'hui capables d'intégrer un très grand nombre de cœurs de calcul en une seule puce (System-on-Chip, SoC). Faire communiquer les composants au sein d'une puce est aujourd'hui assuré par un réseau de commutation de paquet intégré, communément appelé Network-on-Chip (NoC). Cependant, le passage à des technologies de plus en plus réduites rend les circuits plus vulnérables aux fautes et aux défauts de fabrication. Le réseau sur puce peut donc se retrouver avec des routeurs ou des liens non-opérationnels, qui ne peuvent plus être utilisés pour le routage de paquets. Par conséquent, le niveau de flexibilité offert par l'algorithme de routage n'a jamais été aussi important. La première partie de cette thèse consiste à proposer une méthodologie généralisée, permettant de concevoir des algorithmes de routage hautement flexibles, combinant tolérance aux fautes et hautes performances, et ce pour n'importe quelle topologie réseau. Cette méthodologie est basée sur une nouvelle condition suffisante pour l'absence d'interblocages (deadlocks) qui, contrairement aux méthodes existantes qui imposent des restrictions importantes sur l'utilisation des buffers, s'évalue de manière dynamique en fonction de chaque paquet et ne requiert pas un partitionnement stricte des canaux virtuels (virtual channels). Il est montré que ce degré élevé de liberté dans l'utilisation des buffers a un impact positif à la fois sur les performances et sur la robustesse du NoC, sans pour autant augmenter la complexité en termes d'implémentation matérielle. La seconde partie de la thèse s'intéresse à une problématique plus spécifique, qui est celle du routage dans des topologies tri-dimensionnelles partiellement connectées, qui vont vraisemblablement être en vigueur à cause du coût important des connexions verticales, réalisées en utilisant la technologie TSV (Through-Silicon Via). Cette thèse introduit un nouvel algorithme de routage pour ce type d'architectures nommé "First-Last". Grâce à un placement original des canaux virtuels, cet algorithme est le seul capable de garantir la connectivité totale du réseau en présence d'un seul pilier de TSVs de coordonnées arbitraires, tout en ne requérant de canaux virtuels que sur deux des ports du routeur. Contrairement à d'autres algorithmes qui utilisent le même nombre total de canaux virtuels, First-Last n'impose aucune règle sur la position des piliers, ni sur les piliers à sélectionner durant l'exécution. De plus, l'algorithme proposé ayant été construit en utilisant la méthode décrite dans la première partie de la thèse, il offre une utilisation optimisée des canaux virtuels ajoutés. L'implémentation d'un nouvel algorithme de routage implique souvent des changements considérables au niveau de la microarchitecture des routeurs. L'évaluation de ces nouvelles solutions requiert donc une plateforme capable de simuler précisément l'architecture matérielle du réseau au cycle près. De plus, il est essentiel de tester les nouvelles architectures sur des tailles de réseau significativement grandes, pour s'assurer de leur scalabilité et leur applicabilité aux technologies émergentes (e.g. intégration 3D). Malheureusement, les simulateurs de réseaux sur puce existants ne sont pas capables d'effectuer des simulations sur de grands réseaux (milliers de cœurs) assez vite, et souvent, la précision des simulations doit être sacrifiée afin d'obtenir des temps de simulation raisonnables. En réponse à ce problème, la troisième et dernière partie de cette thèse est consacrée à la conception et au développement d'un modèle de simulation générique, extensible et parallélisable, exploitant la puissance des processeurs graphiques modernes (GPU). L'outil développé modélise l'architecture d'un routeur de manière très précise et peut simuler de très grands réseaux en des temps record.

This paper deals with the efficient combination of software components and task-based models for HPC. Task-based models are known to greatly enhance performance and performance portability while component models ease the separation of concerns and thus improves modularity and adaptability. The paper describe the C OMET programming model, a component model for HPC extended with task concepts. We demonstrate its prototype implementation built on top of the task model of OpenMP and the low level component model L2C. We evaluate the approach on five synthetic use-cases representative of common patterns from HPC applications. Experimental results show that the approach is very efficient on the use-cases. On one hand, independent software codes can be easily composed. On the other hand, fine-grained composition supports very good performance. It sometimes even outperforms classical hand-written OpenMP implementations thank to better task interleaving.; Ce rapport traite de la combinaison de modèles à composants et de modèles d’ordonnancement de tâches pour le calcul haute-performance (HPC). Les modèles d’ordonnancement de tâches sont connu pour améliorer les performances et la portabilité des performance des codes HPC tandis que les modèles à composants facilite la séparation des préoccupation et donc améliorent la modularité et l’adaptation des codes. Le rapport décrit le modèle de programmationComet: un modèle à composant HPC étendu avec des concepts de tâches. Nous démontrons sa mise en oeuvre utilisant le modèle de tâche OpenMP ainsi que le modèle à composant de bas niveau L2C. Nous évaluons l’approche sur cinq cas d’utilisation synthétiques représentatif des patrons de codes issues des applications HPC. Les résultats expérimentaux montrent que l’approche se révèle être très efficace sur les cas d’utilisation présentés. D’une part, la composition de des codes indépendants est facilement réalisable. D’autre part, la composition à grain fin permetd’obtenir de très bonne performances. Les performance obtenue avec cette approche sont même parfois meilleures que celle obtenue avec un code OpenMP écrit à la main grâce à une exécution efficace entrelaçant l’exécution des tâches.

This paper deals with the efficient combination of software components and task-based models for HPC. Task-based models are known to greatly enhance performance and performance portability while component models ease the separation of concerns and thus improves modularity and adaptability. The paper describe the C OMET programming model, a component model for HPC extended with task concepts. We demonstrate its prototype implementation built on top of the task model of OpenMP and the low level component model L2C. We evaluate the approach on five synthetic use-cases representative of common patterns from HPC applications. Experimental results show that the approach is very efficient on the use-cases. On one hand, independent software codes can be easily composed. On the other hand, fine-grained composition supports very good performance. It sometimes even outperforms classical hand-written OpenMP implementations thank to better task interleaving.; Ce rapport traite de la combinaison de modèles à composants et de modèles d’ordonnancement de tâches pour le calcul haute-performance (HPC). Les modèles d’ordonnancement de tâches sont connu pour améliorer les performances et la portabilité des performance des codes HPC tandis que les modèles à composants facilite la séparation des préoccupation et donc améliorent la modularité et l’adaptation des codes. Le rapport décrit le modèle de programmationComet: un modèle à composant HPC étendu avec des concepts de tâches. Nous démontrons sa mise en oeuvre utilisant le modèle de tâche OpenMP ainsi que le modèle à composant de bas niveau L2C. Nous évaluons l’approche sur cinq cas d’utilisation synthétiques représentatif des patrons de codes issues des applications HPC. Les résultats expérimentaux montrent que l’approche se révèle être très efficace sur les cas d’utilisation présentés. D’une part, la composition de des codes indépendants est facilement réalisable. D’autre part, la composition à grain fin permetd’obtenir de très bonne performances. Les performance obtenue avec cette approche sont même parfois meilleures que celle obtenue avec un code OpenMP écrit à la main grâce à une exécution efficace entrelaçant l’exécution des tâches.

Complex embedded systems today commonly involve a mix of real-time and best-effort applications integrated on separate microcontrollers thus ensuring fault isolation and error containment. However, this solution multiplies hardware costs, power consumption and thermal dissipation.The recent emergence of low-cost multi-core processors raises the possibility of running both kinds of applications on a single machine, with virtualization ensuring isolation. Nevertheless, the memory hierarchy on such processors is shared between all cores. Memory accesses done by a real time application running on one dedicated core can be slowed down by concurrent memory accesses initiated by best effort applications running in parallels. Therefore real time applications can miss their deadlines.In this thesis, we propose a run-time software-regulation approach that aims to maximize parallelism between real-time and best-effort applications running on a single low-cost multicore ECU. Our approach uses an overhead estimation derived from offline profiling of the real-time application to estimate the slow down on the real-time application caused by memory interferences. When the estimated overhead reaches a predefined threshold, our approach suspends the best-effort applications, allowing the real-time task to continue executing without interferences. Suspended best-effort applications are resumed when the real-time application ends its current activation., Les systèmes embarqués dans les véhicules comportent un mélange d’applications temps réel et « best effort » déployées, pour des raisons d’isolation, sur des calculateurs séparés. L’ajout de nouvelles fonctionnalités dans les véhicules se traduit par un accroissement du nombre de calculateurs et ainsi par une augmentation des coûts, de la consommation électrique et de la dissipation thermique.L’émergence de nouvelles plate-formes multi-cœurs à bas coûts permet d’envisager le déploiement d’une nouvelle architecture dite « virtualisée » pour exécuter en parallèle sur un même calculateur les deux types d’applications. Néanmoins, la hiérarchie mémoire de tels calculateurs, reste partagée. Une application temps réel exécutée sur un cœur peut donc voir ses temps d’accès à la mémoire ralentis par les accès effectués par les applications « best effort » exécutées en parallèle entraînant ainsi la violation des échéances de la tâche temps réel.Dans cette thèse, nous proposons une nouvelle approche de gestion de la contention mémoire. Dans une première étape, hors ligne, nous générons un oracle capable d’estimer les ralentissements d’une tâche temps réel en fonction du trafic mémoire mesuré. Dans une deuxième étape, en ligne, les tâches temps réel sont exécutées en parallèle des applications « best effort ». Un mécanisme de régulation va surveiller la consommation mémoire et utiliser l’oracle généré précédemment pour estimer le ralentissement des tâches temps réel. Lorsque le ralentissement estimé est supérieur à celui fixé par le concepteur du système les applications « best effort » sont suspendues jusqu’à ce que l’application temps réel termine son activation.

National audience; The growing number of cores in a single chip goes along with an increase in communications. The variety of applications runing on the chip causes spatial and temporal heterogeneity of communications. To address these issues, we present in this paper a dynamically reconfigurable interconnect based on Radio Frequency (RF) for intra chip communications. The use of RF allows to increase the bandwidth while minimizing the latency. Dynamic reconfiguration of the interconnect allows to handle the heterogeneity of communications. We present the rationale for choosing RF over optics and 3D, the detailed architecture of the network and the chip implementing it, the evaluation of its feasibility and its performances. One advantage of this RF interconnect is the ability to broadcast without additional cost compared to point-topoint communications, opening new perspectives in terms of cache coherence.; La multiplication du nombre de cœurs de calcul présents sur une même puce va de pair avec une augmentation des besoins en communication. De plus, la variété des applications s’exécutant sur la puce provoque une hétérogénéité spatiale et temporelle des communications. C’est pour répondre à ces problématiques que nous présentons dans cet article un réseau d’interconnexion sur puce dynamiquement reconfigurable utilisant la Radio Fréquence (RF). L’utilisation de la RF permet d’avoir plus de bande passante en minimisant la latence. La possibilité de reconfigurer dynamiquement le réseau permet de s’adapter à la variabilité des communications. Nous présentons les raisons du choix de la RF par rapport aux autres nouvelles technologies du domaine que sont l’optique et la 3D, l’architecture détaillée de ce réseau et d’une puce le mettant en œuvre ainsi que l’évaluation de sa faisabilité et de ses performances. Un des avantages de ce réseau d’interconnexion RF est la possibilité de faire du broadcast sans surcoût par rapport aux communications point-à-point, ouvrant ainsi de nouvelles perspectives en termes de gestion de la cohérence mémoire notamment.

In the exascale race, supercomputer architectures are evolving towards massively multicore nodes with hierarchical memory structures and equipped with larger vectorization registers. These trends tend to make MPI-only applications less effective, and now require programmers to explicitly manage low-level elements to get decent performance.In the context of Molecular Dynamics (MD) applied to condensed matter physics, the need for a better understanding of materials behaviour under extreme conditions involves simulations of ever larger systems, on tens of thousands of cores. This will put molecular dynamics codes among software that are very likely to meet serious difficulties when it comes to fully exploit the performance of next generation processors.This thesis proposes the design and implementation of a high-performance, flexible and scalable framework dedicated to the simulation of large scale MD systems on future supercomputers. We managed to separate numerical modules from different expressions of parallelism, allowing developers not to care about optimizations and still obtain high levels of performance. Our architecture is organized in three levels of parallelism: domain decomposition using MPI, thread parallelization within each domain, and explicit vectorization. We also included a dynamic load balancing capability in order to equally share the workload among domains.Results on simple tests show excellent sequential performance and a quasi linear speedup on several thousands of cores on various architectures. When applied to production simulations, we report an acceleration up to a factor 30 compared to the code previously used by CEA’s researchers., Dans la course vers l’exascale, les architectures des supercalculateurs évoluent vers des nœuds massivement multicœurs, sur lesquels les accès mémoire sont non-uniformes et les registres de vectorisation toujours plus grands. Ces évolutions entraînent une baisse de l’efficacité des applications homogènes (MPI simple), et imposent aux développeurs l’utilisation de fonctionnalités de bas-niveau afin d’obtenir de bonnes performances.Dans le contexte de la dynamique moléculaire (DM) appliqué à la physique de la matière condensée, les études du comportement des matériaux dans des conditions extrêmes requièrent la simulation de systèmes toujours plus grands avec une physique de plus en plus complexe. L’adaptation des codes de DM aux architectures exaflopiques est donc un enjeu essentiel.Cette thèse propose la conception et l’implémentation d’une plateforme dédiée à la simulation de très grands systèmes de DM sur les futurs supercalculateurs. Notre architecture s’organise autour de trois niveaux de parallélisme: décomposition de domaine avec MPI, du multithreading massif sur chaque domaine et un système de vectorisation explicite. Nous avons également inclus une capacité d’équilibrage dynamique de charge de calcul. La conception orienté objet a été particulièrement étudiée afin de préserver un niveau de programmation utilisable par des physiciens sans altérer les performances.Les premiers résultats montrent d’excellentes performances séquentielles, ainsi qu’une accélération quasi-linéaire sur plusieurs dizaines de milliers de cœurs. En production, nous constatons une accélération jusqu’à un facteur 30 par rapport au code utilisé actuellement par les chercheurs du CEA.

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.

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.

Current supercomputer architectures are subject to memory related issues. For instance we can observe slowdowns induced by memory management mecanisms and their implementation. In this context, we focus on the management of large memory segments for multi-core and NUMA supercomputers similar to Tera 100 and Curie. We discuss our work in three parts.We first study several paging policies (page coloring, huge pages...) from multiple operating systems. We demonstrate an interference between those policies and layout decisions taken by userspace allocators. Such interactions can significantly reduce cache efficiency depending on the application, particularly on multi-core architectures. This study extends existing works by studying interactions between the operating system, the allocator and caches.Then, we discuss performance issues when large memory segments are allocated. To do so, we consider the interaction between the OS and userspace allocators. We show that we can significantly improve some application performances (up to 50%) by controling the memory exchange rate with the OS and by taking care of memory topologies.We finally study page fault extensibility in current Linux kernel implementation. We obsere a large impact due to page zeroing which is a security requirement. We propose an improvement on memory allocation semantic aimed at avoiding page zeroing. It shows a new interest for hugepages to improve paging scalability without changing too much kernel algorithms., L’évolution des architectures des calculateurs actuels est telle que la mémoire devient un problème majeur pour les performances. L’étude décrite dans ce document montre qu’il est déjà possible d’observer des pertes importantes imputables aux mécanismes de gestion de cette dernière. Dans ce contexte, nous nous sommes intéressés aux problèmes de gestion des gros segments mémoire sur les supercalculateurs multicoeurs NUMA de type Tera 100 et Curie. Notre travail est détaillé ici en suivant trois axes principaux. Nous analysons dans un premier temps les politiques de pagination de différents systèmes d’exploitation (coloration de pages, grosses pages...). Nous mettons ainsi en évidence l’existence d’interférences néfastes entre ces politiques et les décisions de placement de l’allocateur en espace utilisateur. Nous complétons donc les études cache/allocateur et cache/pagination par une analyse de l’interaction cumulée de ces composants. Nous abordons ensuite la problématique des performances d’allocation des grands segments mémoire en considérant les échanges entre le système et l’allocateur. Nous montrons ici qu’il est possible d’obtenir des gains significatifs (de l’ordre de 50% sur une grosse application) enlimitant ces échanges et en structurant l’allocateur pour un support explicite des architectures NUMA. La description de nos travaux s’achève sur une étude des problèmes d’extensibilité observés au niveau des fautes de pages du noyau Linux. Nous avons ainsi proposé une extension de la sémantique d’allocation afin d’éliminer la nécessité d’effectuer les coûteux effacements mémoire des pages au niveau système.

International audience; This paper presents an approach for hosting a representative avionic function on a distributed-memory mul-ticore COTS architecture. This approach was developed in collaboration by Thales and ONERA, in order to improve the performance of the function while enforcing its predictability. Once the target avionic function and the multicore architecture have been introduced, the execution model and the needed basic services are described and evaluated.

Among the various paradigms of parallelization, pipeline parallelism has the advantage of maintaining sequentiality of algorithms, thus being applicable in case of data dependencies. More over, the stream-computing extension for OpenMP proposed by Pop and Cohen allows to apply this form of parallelization without needing a complete rewrite of the code, by simply adding annotations to it. However, due to the *importance* of the communication needed between the cores, the performances obtained by following this paradigm depends very much on the communication algorithm used. Yet, the communication algorithm used in this extension relies on queues that can handle several producers and consumers while applications using pipeline parallelism mainly works with linear communication chains. To improve the performances of pipeline parallelism implemented by the stream-computing extension for OpenMP, this thesis propose to use, whenever possible, a more specialized communication algorithm called BatchQueue. By only handling the special case of a communication with one producer and one consumer, BatchQueue can reach throughput up to two time faster than existing algorithms. Furthermore, once integrated to the stream-computing extension for OpenMP, the evaluation shows that BatchQueue can improve speedup of application up to a factor 2 as well. The study thus shows that using a more efficient specialized communication algorithm can have a significant impact on overall performances of application implementing pipeline parallelism.; Parmi les différents paradigmes de programmation parallèle, le parallélisme de flux présente l'avantage de conserver la séquentialité des algorithmes et d'être ainsi applicable en présence de dépendances de données. De plus, l'extension de calcul par flux pour OpenMP proposée par Pop et Cohen permet de mettre en œuvre cette forme de parallélisme sans requérir de réécriture complète du code, en y ajoutant simplement des annotations. Cependant, en raison de l'importance de la communication nécessaire entre les cœurs de calcul, les performances obtenues en suivant ce paradigme sont très dépendantes de l'algorithme de communication utilisé. Or l'algorithme de communication utilisé dans cette extension repose sur des files gérant plusieurs producteurs et consommateurs alors que les applications mettant en œuvre le parallélisme de flux fonctionnent principalement avec des chaînes de communication linéaires. Afin d'améliorer les performances du parallélisme de flux mis en œuvre par l'extension de calcul par flux pour OpenMP, cette thèse propose d'utiliser, lorsque cela est possible, un algorithme de communication plus spécialisé nommé BatchQueue. En ne gérant que le cas particulier d'une communication avec un seul producteur et un seul consommateur, BatchQueue atteint des débits jusqu'à deux fois supérieurs à ceux des algorithmes existants. De plus, une fois intégré à l'extension de calcul par flux pour OpenMP, l'évaluation montre que BatchQueue permet d'améliorer l'accélération des applications jusqu'à un facteur 2 également. L'étude montre ainsi qu'utiliser des algorithmes de communication spécialisés plus efficaces peut avoir un impact significatif sur les performances générales des applications mettant en œuvre le parallélisme de flux.

In this thesis work, we have mainly worked on two topics of GPU performance analysis. First, we have developed an analytical method and a timing estimation tool (TEG) to predict CUDA application's performance for GT200 generation GPUs. TEG can predict GPU applications' performance in cycle-approximate level. Second, we have developed an approach to estimate GPU applications' performance upper bound based on application analysis and assembly code level benchmarking. With the performance upper bound of an application, we know how much optimization space is left and can decide the optimization effort. Also with the analysis we can understand which parameters are critical to the performance.; Durant cette thèse, nous avons principalement travaillé sur deux sujets liés à l'analyse de la performance GPU (Graphics Processing Unit - Processeur graphique). Dans un premier temps, nous avons développé une méthode analytique et un outil d'estimation temporel (TEG) pour prédire les performances d'applications CUDA s’exécutant sur des GPUs de la famille GT200. Cet outil peut prédire les performances avec une précision approchant celle des outils précis au cycle près. Dans un second temps, nous avons développé une approche pour estimer la borne supérieure des performances d'une application GPU, en se basant sur l'analyse de l'application et de son code assembleur. Avec cette borne, nous connaissons la marge d'optimisation restante, et nous pouvons décider des efforts d'optimisation à fournir. Grâce à cette analyse, nous pouvons aussi comprendre quels paramètres sont critiques à la performance.

In this thesis work, we have mainly worked on two topics of GPU performance analysis. First, we have developed an analytical method and a timing estimation tool (TEG) to predict CUDA application's performance for GT200 generation GPUs. TEG can predict GPU applications' performance in cycle-approximate level. Second, we have developed an approach to estimate GPU applications' performance upper bound based on application analysis and assembly code level benchmarking. With the performance upper bound of an application, we know how much optimization space is left and can decide the optimization effort. Also with the analysis we can understand which parameters are critical to the performance., Durant cette thèse, nous avons principalement travaillé sur deux sujets liés à l'analyse de la performance GPU (Graphics Processing Unit - Processeur graphique). Dans un premier temps, nous avons développé une méthode analytique et un outil d'estimation temporel (TEG) pour prédire les performances d'applications CUDA s’exécutant sur des GPUs de la famille GT200. Cet outil peut prédire les performances avec une précision approchant celle des outils précis au cycle près. Dans un second temps, nous avons développé une approche pour estimer la borne supérieure des performances d'une application GPU, en se basant sur l'analyse de l'application et de son code assembleur. Avec cette borne, nous connaissons la marge d'optimisation restante, et nous pouvons décider des efforts d'optimisation à fournir. Grâce à cette analyse, nous pouvons aussi comprendre quels paramètres sont critiques à la performance.

Software failures in hard real-time systems may have hazardous effects (industrial disasters, human lives endangering). The verification of timing constraints in a hard real-time system depends on the knowledge of the worst-case execution times (WCET) of the tasks accounting for the embedded program. Using multicore processors is a mean to improve embedded systems performances. However, determining worst-case execution times estimates on these architectures is made difficult by the sharing of some resources among cores, especially the interconnection bus that enables accesses to the shared memory. This document proposes a two-level arbitration scheme that makes it possible to improve executed tasks performances while complying with timing constraints. Described methods assess an optimal bus access priority level to each of the tasks. They also allow to find an optimal allocation of tasks to cores when tasks to execute are more numerous than available cores. Experimental results show a meaningful drop in worst-case execution times estimates and processor utilization.; Les défaillances des applications embarquées dans les systèmes temps-réel strict peuvent avoir des conséquences graves (catastrophes industrielles, mise en danger de vies humaines). La vérification des contraintes temporelles d'un système temps-réel strict dépend de la connaissance du temps d'exécution pire-cas des tâches constituant l'application embarquée. L'utilisation de processeurs multi-cœurs est l'un des moyens actuellement mis en œuvre afin d'améliorer le niveau de performances des systèmes embarqués. Cependant, la détermination du temps d'exécution pire-cas d'une tâche sur ce type d'architecture est rendue difficile par le partage de certaines ressources par les cœurs, et notamment le bus d'interconnexion permettant l'accès à la mémoire centrale. Ce document propose un nouveau mécanisme d'arbitrage de bus à deux niveaux permettant d'améliorer les performances des ensembles de tâches exécutés tout en garantissant le respect des contraintes temporelles. Les méthodes décrites permettent d'établir un niveau de priorité d'accès au bus optimal pour chacune des tâches exécutées. Elles permettent également de trouver une allocation optimale des tâches aux cœurs lorsqu'il y a plus de tâches à exécuter que de cœurs disponibles. Les résultats expérimentaux montrent une diminution significative des estimations de temps d'exécution pire-cas et de l'utilisation du processeur.

National audience; Les applications séquentielles peuvent tirer partie des systèmes multi-cœurs en utilisant le parallélisme pipeline pour accroître leur performance. Dans un tel schéma de parallélisme, l'accélération possible est limitée par le surcoût dû à la communication cœur à cœur. Ce papier présente l'algorithme BatchQueue, un système de communication rapide conçu pour optimiser l'utilisation du cache matériel, notamment au regard du pré-chargement. BatchQueue propose des performances améliorées d'un facteur 2 : il est capable d'envoyer un mot de données en 3,5 nanosecondes sur un système 64 bits, représentant un débit de 2 Gio/s.

The 3GPP Long Term Evolution (LTE) is a new terrestrial telecommunication standard which base stations, named eNodeB, necessitate much power to process the data transmitted and received by the LTE antennas. Digital Signal Processors (DSP) are commonly employed to compute physical layer algorithms in base stations. Modern DSPs are highly complex and heterogeneous systems. No ideal solution has been found to automatically assign application parts over the multiple cores contained in an eNodeB. In this thesis, we design a rapid prototyping and code generation framework that assists programmers of multi-core DSPs by automating the most complex design phases. As some algorithms of the LTE physical layer are too variable for static assignment, we present a simple adaptive scheduler that computes real-time assignment choices based on predicted execution times.; Le standard 3GPP LTE (Long Term Evolution) est un nouveau standard de télécommunication terrestre dont la couche physique des stations de base, appelées eNodeB, est particulièrement coûteuse. Les processeurs de traitement du signal (DSP) sont largement employés dans les stations de base pour calculer les algorithmes de la couche physique. Les DSPs de dernière génération sont des systèmes complexes et hétérogènes. Il n'existe pas actuellement de solution idéale pour distribuer les parties d'une application comme le LTE sur les différents cœurs contenus dans un eNodeB. Dans cette thèse, nous présentons une méthode de travail pour le prototypage rapide et la génération de code automatique. Certains algorithmes de la couche physique du LTE étant trop variables pour une distribution hors-ligne, nous présentons un distributeur adaptatif capable de faire des choix en temps réel sur la base de temps d'exécution prédits.

The 3GPP Long Term Evolution (LTE) is a new terrestrial telecommunication standard which base stations, named eNodeB, necessitate much power to process the data transmitted and received by the LTE antennas. Digital Signal Processors (DSP) are commonly employed to compute physical layer algorithms in base stations. Modern DSPs are highly complex and heterogeneous systems. No ideal solution has been found to automatically assign application parts over the multiple cores contained in an eNodeB. In this thesis, we design a rapid prototyping and code generation framework that assists programmers of multi-core DSPs by automating the most complex design phases. As some algorithms of the LTE physical layer are too variable for static assignment, we present a simple adaptive scheduler that computes real-time assignment choices based on predicted execution times.; Le standard 3GPP LTE (Long Term Evolution) est un nouveau standard de télécommunication terrestre dont la couche physique des stations de base, appelées eNodeB, est particulièrement coûteuse. Les processeurs de traitement du signal (DSP) sont largement employés dans les stations de base pour calculer les algorithmes de la couche physique. Les DSPs de dernière génération sont des systèmes complexes et hétérogènes. Il n'existe pas actuellement de solution idéale pour distribuer les parties d'une application comme le LTE sur les différents cœurs contenus dans un eNodeB. Dans cette thèse, nous présentons une méthode de travail pour le prototypage rapide et la génération de code automatique. Certains algorithmes de la couche physique du LTE étant trop variables pour une distribution hors-ligne, nous présentons un distributeur adaptatif capable de faire des choix en temps réel sur la base de temps d'exécution prédits.

Since applications such as video coding/decoding or digital communications with advanced features are becoming more complex, the need for computational power is rapidly increasing. In order to satisfy software requirements, the use of parallel architecture is a common answer. To reduce the software development effort for such architectures, it is necessary to provide the programmer with efficient tools capable of automatically solving communications and software partitioning/scheduling concerns. The Algorithm Architecture Matching methodology helps the programmer by providing automatic transformation, partitioning and scheduling of an application for a given architecture This methodology relies on an application model that allows to extract the available parallelism. The contributions of this thesis tackle both the problem of the model and the associated optimization for parallelism extraction. The Data flow model is indeed a natural representation for data-oriented applications since it represents data dependencies between the operations allowing to extract parallelism. In this model, the application is described as a graph in which nodes represent computations and edges carry the stream of data-tokens between operations. A restricted version of data-flow, termed synchronous data-flow (SDF), offers strong compile-time predictability properties, but has limited expressive power. In this thesis we propose a new type of hierarchy based on interfaces (Interface-based SDF) allowing more expressiveness while maintaining its predictability. This interface-based hierarchy gives the application designer more flexibility to apply iterative design approaches, and to make optimizing choices at the design level. This type of hierarchy is also closer to the host language semantics such as C because hierarchy levels can be interpreted as code closures (i.e., semantic boundaries), and allow one to design iterative patterns. One of the main problems with this hierarchical SDF model is the lack of trade-off between parallelism and network clustering. In this thesis we present a systematic method for applying an important class of loop transformation techniques in the context of interface-based SDF semantics. The resulting approach provides novel capabilities for integrating parallelism extraction properties of the targeted loop transformations with the useful modeling, analysis, and code reuse properties provided by SDF.; Face au défi que représente la programmation des architectures multi-cœurs/processeurs, il est devenu nécessaire de proposer aux développeurs des outils adaptés permettant d'abstraire les notions inhérentes au parallélisme et facilitant le portage d'une application sur différentes architectures. La méthodologie AAA (Adéquation Algorithme Architecture) propose au développeur d'automatiser les étapes de partitionnement, ordonnancement à partir d'une description haut niveau de l'application et de l'architecture. Cette méthodologie permet donc le prototypage rapide d'une application sur différentes architectures avec un minimum d'effort et un résultat approchant l'optimal. Les apports de cette thèse se situent à la fois au niveau du modèle de spécification et de ses optimisations relatives au contexte des architectures parallèles. Le modèle flux de données répond aux problèmes de modélisation des applications fortement synchronisées par les données. Le sous-ensemble SDF (Synchronous Data Flow), limite l'expressivité du modèle mais apporte un complément d'information permettant une optimisation efficace et garantissant l'intégrité du calcul dans tous les contextes. Les travaux développés dans ce mémoire introduisent un nouveau modèle de hiérarchie dans SDF afin d'améliorer l'expressivité tout en préservant les propriétés du modèle initial. Ce modèle basé sur des interfaces, permet une approche plus naturelle pour le développeur accoutumé au langage C. Ce nouveau modèle apportant un complément d'information, nous proposons également un ensemble de traitement améliorant la prise en charge des motifs de répétition imbriqués. En effet le modèle de hiérarchie introduit en première partie permet la spécification de motifs dit de " nids de boucles " pouvant masquer le parallélisme potentiel. Il est donc nécessaire d'associer au modèle des traitements permettant de révéler ce parallélisme tout en préservant l'aspect factorisé du calcul. Les méthodes présentées sont adaptées du contexte des compilateurs pour supercalculateurs et de l'univers des réseaux systoliques.

Since applications such as video coding/decoding or digital communications with advanced features are becoming more complex, the need for computational power is rapidly increasing. In order to satisfy software requirements, the use of parallel architecture is a common answer. To reduce the software development effort for such architectures, it is necessary to provide the programmer with efficient tools capable of automatically solving communications and software partitioning/scheduling concerns. The Algorithm Architecture Matching methodology helps the programmer by providing automatic transformation, partitioning and scheduling of an application for a given architecture This methodology relies on an application model that allows to extract the available parallelism. The contributions of this thesis tackle both the problem of the model and the associated optimization for parallelism extraction. The Data flow model is indeed a natural representation for data-oriented applications since it represents data dependencies between the operations allowing to extract parallelism. In this model, the application is described as a graph in which nodes represent computations and edges carry the stream of data-tokens between operations. A restricted version of data-flow, termed synchronous data-flow (SDF), offers strong compile-time predictability properties, but has limited expressive power. In this thesis we propose a new type of hierarchy based on interfaces (Interface-based SDF) allowing more expressiveness while maintaining its predictability. This interface-based hierarchy gives the application designer more flexibility to apply iterative design approaches, and to make optimizing choices at the design level. This type of hierarchy is also closer to the host language semantics such as C because hierarchy levels can be interpreted as code closures (i.e., semantic boundaries), and allow one to design iterative patterns. One of the main problems with this hierarchical SDF model is the lack of trade-off between parallelism and network clustering. In this thesis we present a systematic method for applying an important class of loop transformation techniques in the context of interface-based SDF semantics. The resulting approach provides novel capabilities for integrating parallelism extraction properties of the targeted loop transformations with the useful modeling, analysis, and code reuse properties provided by SDF.; Face au défi que représente la programmation des architectures multi-cœurs/processeurs, il est devenu nécessaire de proposer aux développeurs des outils adaptés permettant d'abstraire les notions inhérentes au parallélisme et facilitant le portage d'une application sur différentes architectures. La méthodologie AAA (Adéquation Algorithme Architecture) propose au développeur d'automatiser les étapes de partitionnement, ordonnancement à partir d'une description haut niveau de l'application et de l'architecture. Cette méthodologie permet donc le prototypage rapide d'une application sur différentes architectures avec un minimum d'effort et un résultat approchant l'optimal. Les apports de cette thèse se situent à la fois au niveau du modèle de spécification et de ses optimisations relatives au contexte des architectures parallèles. Le modèle flux de données répond aux problèmes de modélisation des applications fortement synchronisées par les données. Le sous-ensemble SDF (Synchronous Data Flow), limite l'expressivité du modèle mais apporte un complément d'information permettant une optimisation efficace et garantissant l'intégrité du calcul dans tous les contextes. Les travaux développés dans ce mémoire introduisent un nouveau modèle de hiérarchie dans SDF afin d'améliorer l'expressivité tout en préservant les propriétés du modèle initial. Ce modèle basé sur des interfaces, permet une approche plus naturelle pour le développeur accoutumé au langage C. Ce nouveau modèle apportant un complément d'information, nous proposons également un ensemble de traitement améliorant la prise en charge des motifs de répétition imbriqués. En effet le modèle de hiérarchie introduit en première partie permet la spécification de motifs dit de " nids de boucles " pouvant masquer le parallélisme potentiel. Il est donc nécessaire d'associer au modèle des traitements permettant de révéler ce parallélisme tout en préservant l'aspect factorisé du calcul. Les méthodes présentées sont adaptées du contexte des compilateurs pour supercalculateurs et de l'univers des réseaux systoliques.

Needs in computing power are increasing steadily. In order to meet those needs, new architectures have appeared. Computing grids and clusters are gathering the computing power of several machines, and multi-core processors are offering more computing power without the need to increase the frequency and electrical power usage. Nonetheless, The study of those new architectures is not an easy task. In order to study computing grids researchers have dedicated platforms. But the conduct of experiments on such platforms is a difficult process. In the case of multi-core processors, their behavior is not well known. In this thesis we put forward two tools dedicated to the study of new architectures. The first one, Expo, is an experiment management software for grid architectures. Expo allows for automated experiment conduct while still trying to guarantee its sound unrolling. Expo also provides a language to describe experiments on grid infrastructures. The second one, PaSTeL, is dedicated to the study of interactions between architectures and execution strategies. Highly tunable, it grants user with means to study in depth the behavior of a parallel solution running on a given architecture. Both tools have been validated during the development phase, but also during an experimental study of a work stealing engine on several multi-core architectures.; Les besoins en puissance de calcul ne cessent d'augmenter. Pour répondre à ces besoins, de nouvelles architectures sont apparues. Les grilles et grappes de calcul, qui permettent d'agréger la puissance de plusieurs machines et les processeurs multi-cœurs qui permettent d'offrir plus de puissance sans nécessité d'augmenter la fréquence et la consommation énergétique du processeur. Cependant, l'étude de ces nouvelles architectures n'est pas aisée. Pour l'étude des grilles de calcul, nous disposons de plates-formes dédiées. Néanmoins, la conduite d'expérience sur ces plates-formes complexe est une tâche difficile à mettre en œuvre. Dans le cas des processeurs multi-cœurs, leur comportement est mal connu. Dans cette thèse nous proposons deux outils dédiés à l'étude des nouvelles architectures. Le premier, Expo, est un logiciel de conduite d'expérience sur grille dédiée à l'expérimentation. Expo permet d'automatiser en partie la conduite d'une expérience, tout en essayant de garantir son bon déroulement. Expo propose également un langage concis de description d'expérience adapté à la problématique des grilles. Le second outil, PaSTeL, est dédié à l'étude de l'adéquation entre un support exécutif et une architecture. Hautement paramétrable, il permet d'étudier les ultiples facettes d'une solution de parallélisation s'exécutant sur une architecture donnée. Les deux outils ont été validés au cours de leur développement, mais également lors d'une campagne expérimentale visant à étudier le comportement d'un moteur de vol de travail sur différentes architectures multi-cœurs.

Since their invention more than half a century ago, computers have gone from being just an handful of expensive machines each filling an entire room, to being an integral part of almost every aspect of modern life. Nowadays computers are everywhere: in our planes, in our cars, on our desks, in our home appliances, and even in our pockets. This widespread adoption had a profound impact in our world and in our lives, so much that now we rely on them for many important aspects of everyday life, including work, communication, travel, entertainment, and even managing our money. Given our increased reliance on computers, their continuous and correct operation has become essential for modern society. However, individual computers can fail due to a variety of causes and, if nothing is done about it, these failures can easily lead to a disruption of the service provided by computer system. The field of fault tolerance studies this problem, more precisely, it studies how to enable a computer system to continue operation in spite of the failure of individual components. One of the most popular techniques of achieving fault tolerance is software replication, where a service is replicated on an ensemble of machines (replicas) such that if some of these machines fail, the others will continue providing the service. Software replication is widely used because of its generality (can be applied to most services) and its low cost (can use off-the-shelf hardware). This thesis studies a form of software replication, namely, state machine replication, where the service is modeled as a deterministic state machine whose state transitions consist of the execution of client requests. Although state machine replication was first proposed almost 30 years ago, the proliferation of online services during the last years has led to a renewed interest. Online services must be highly available and for that they frequently rely on state machine replication as part of their fault tolerance mechanisms. However, the unprecedented scale of these services, which frequently have hundreds of thousands or even millions of users, leads to a new set performance requirements on state machine replication. This thesis is organized in two parts. The goal of the first part is to study from a theoretical perspective the performance characteristics of the algorithms behind state machine replication and to propose improved variants of such algorithms. The second part looks at the problem from a practical perspective, proposing new techniques to achieve high-throughput and scalability. In the first part, we start with an analytical analysis of the performance of two consensus algorithms, one leader-free (an adaptation of the fast round of Fast Paxos) and another leader-based (an adaptation of classical Paxos). We express these algorithms in the Heard-Of round model and show that using this model it is fairly easy to determine analytically several interesting performance metrics. We then study the performance of round models in general. Round models are perceived as inefficient because in their typical implementation, the real-time duration of rounds is proportional to the (pessimistic) timeouts used on the underlying system. This contrasts with the failure detector or the partial synchronous system models, where algorithms usually progress at the speed of message reception. We show that there is no inherent gap in performance between the models, by proposing a round implementation that during stable periods advances at the speed of message reception. We conclude the first part by presenting a new leader election algorithm that chooses as leader a well-connected process, that is, a process whose time needed to perform a one-to-majority communication round is among the lowest in the system. This is useful mainly in systems where the latency between processes is not homogeneous, because the performance of leader-based algorithms is particularly sensitive to the performance and connectivity of the process acting as a leader. The second part of the thesis studies different approaches to achieve high-throughput with state machine replication. To support the experimental work done in this part, we have developed JPaxos, a fully-featured implementation of Paxos in Java. We start by looking at how to tune the batching and pipelining optimizations of Paxos; using an analytical model of the performance of Paxos we show how to derive good values for the bounds on the batch size and number of parallel instances. We then propose an architecture for implementing replicated state machines that is capable of leveraging multi-core CPUs to achieve very high-levels of performance. The final contribution of this thesis is based on the observation that most implementations of state machine replication have an unbalanced division of work among threads, with one replica, the leader, having a significantly higher workload than the other replicas. Naturally, the leader becomes the bottleneck of the system, while other replicas are only lightly loaded. We propose and evaluate S-Paxos, which evenly balances the workload among all replicas, and thus overcomes the leader bottleneck. The benefits are two-fold: S-Paxos achieves a higher throughput for a given number of replicas and its performance increases with the number of replicas (up to a reasonable number).

Solving large sparse linear system is an essential part of numerical simulations. These resolve can takeup to 80% of the total of the simulation time.An efficient parallelization of sparse linear kernels leads to better performances. In distributed memory,parallelization of these kernels is often done by changing the numerical scheme. Contrariwise, in sharedmemory, a more efficient parallelism can be used. It’s necessary to use two levels of parallelism, a first onebetween nodes of a cluster and a second inside a node.When using iterative methods in shared memory, task-based programming enables the possibility tonaturally describe the parallelism by using as granularity one line of the matrix for one task. Unfortunately,this granularity is too fine and doesn’t allow to obtain good performance.In this thesis, we study the granularity problem of the task-based parallelization. We offer to increasegrain size of computational tasks by creating aggregates of tasks which will become tasks themself. Thenew coarser task graph is composed by the set of these aggregates and the new dependencies betweenaggregates. Then a task scheduler schedules this new graph to obtain better performance. We use as examplethe Incomplete LU factorization of a sparse matrix and we show some improvements made by this method.Then, we focus on NUMA architecture computer. When we use a memory bandwidth limited algorithm onthis architecture, it is interesting to reduce NUMA effects. We show how to take into account these effects ina task-based runtime in order to improve performance of a parallel program., La résolution de grands systèmes linéaires creux est un élément essentiel des simulations numériques.Ces résolutions peuvent représenter jusqu’à 80% du temps de calcul des simulations.Une parallélisation efficace des noyaux d’algèbre linéaire creuse conduira donc à obtenir de meilleures performances. En mémoire distribuée, la parallélisation de ces noyaux se fait le plus souvent en modifiant leschéma numérique. Par contre, en mémoire partagée, un parallélisme plus efficace peut être utilisé. Il est doncimportant d’utiliser deux niveaux de parallélisme, un premier niveau entre les noeuds d’une grappe de serveuret un deuxième niveau à l’intérieur du noeud. Lors de l’utilisation de méthodes itératives en mémoire partagée,les graphes de tâches permettent de décrire naturellement le parallélisme en prenant comme granularité letravail sur une ligne de la matrice. Malheureusement, cette granularité est trop fine et ne permet pas d’obtenirde bonnes performances à cause du surcoût de l’ordonnanceur de tâches.Dans cette thèse, nous étudions le problème de la granularité pour la parallélisation par graphe detâches. Nous proposons d’augmenter la granularité des tâches de calcul en créant des agrégats de tâchesqui deviendront eux-mêmes des tâches. L’ensemble de ces agrégats et des nouvelles dépendances entre lesagrégats forme un graphe de granularité plus grossière. Ce graphe est ensuite utilisé par un ordonnanceur detâches pour obtenir de meilleurs résultats. Nous utilisons comme exemple la factorisation LU incomplète d’unematrice creuse et nous montrons les améliorations apportées par cette méthode. Puis, dans un second temps,nous nous concentrons sur les machines à architecture NUMA. Dans le cas de l’utilisation d’algorithmeslimités par la bande passante mémoire, il est intéressant de réduire les effets NUMA liés à cette architectureen plaçant soi-même les données. Nous montrons comment prendre en compte ces effets dans un intergiciel àbase de tâches pour ainsi améliorer les performances d’un programme parallèle.