Les architectures ''Heterogeneous Many Cores'' (HMC) qui mélangent beaucoup de petits/simples cœurs avec quelques cœurs larges/complexes, fournissent de bonnes performances pour des applications séquentielles et permettent une économie d'énergie pour les applications parallèles. Les petits cœurs des HMC peuvent être utilisés comme des cœurs auxiliaires pour accélérer les applications séquentielles gourmandes en mémoire qui s'exécutent sur le cœur principal. Cependant, le surcoût pour accéder aux petits cœurs limite leur utilisation comme cœurs auxiliaires. En raison de la disparité de performance entre le cœur principal et les petits cœurs, on ne sait pas encore si les petits cœurs sont adaptés pour exécuter des threads auxiliaires pour faire du prefetching pour un cœur plus puissant. Dans cette thèse, nous présentons une architecture hardware/software appelée « core-tethering », pour supporter efficacement l'exécution de threads auxiliaires sur les systèmes HMC. Cette architecture permet au cœur principal de pouvoir lancer et contrôler directement l'exécution des threads auxiliaires, et de transférer efficacement le contexte des applications nécessaire à l'exécution des threads auxiliaires. Sur un ensemble de programmes ayant une utilisation intensive de la mémoire, les threads auxiliaires s'exécutant sur des cœurs relativement petits, peuvent apporter une accélération significative par rapport à du prefetching matériel seul. Et les petits cœurs fournissent un bon compromis par rapport à l'utilisation d'un seul cœur puissant pour exécuter les threads auxiliaires. En résumé, malgré le surcoût lié à la latence d'accès aux lignes de cache chargées par le prefetching depuis le cache L3 partagé, le prefetching par les threads auxiliaires sur les petits cœurs semble être une manière prometteuse d'améliorer la performance des codes séquentiels pour des applications ayant une utilisation intensive de la mémoire sur les systèmes HMC. / Heterogeneous Many Cores (HMC) architectures that mix many simple/small cores with a few complex/large cores are emerging as a design alternative that can provide both fast sequential performance for single threaded workloads and power-efficient execution for through-put oriented parallel workloads. The availability of many small cores in a HMC presents an opportunity to utilize them as low-power helper cores to accelerate memory-intensive sequential programs mapped to a large core. However, the latency overhead of accessing small cores in a loosely coupled system limits their utility as helper cores. Also, it is not clear if small cores can execute helper threads sufficiently in advance to benefit applications running on a larger, much powerful, core. In this thesis, we present a hardware/software framework called core-tethering to support efficient helper threading on heterogeneous many-cores. Core-tethering provides a co-processor like interface to the small cores that (a) enables a large core to directly initiate and control helper execution on the helper core and (b) allows efficient transfer of execution context between the cores, thereby reducing the performance overhead of accessing small cores for helper execution. Our evaluation on a set of memory intensive programs chosen from the standard benchmark suites show that, helper threads using moderately sized small cores can significantly accelerate a larger core compared to using a hardware prefetcher alone. We also find that a small core provides a good trade-off against using an equivalent large core to run helper threads in a HMC. In summary, despite the latency overheads of accessing prefetched cache lines from the shared L3 cache, helper thread based prefetching on small cores looks as a promising way to improve single thread performance on memory intensive workloads in HMC architectures.

La complexité des systèmes sur puce s'accentue pour supporter les nouvelles applications dans le domaine des télécommunications et du multimédia. La tendance actuelle des nouvelles architectures matérielles converge vers des plateformes multi-cœurs à plusieurs unités de calcul (processeurs, DSP, IP) interconnectées par un réseau sur puce qui peut être configurable au niveau de ses interfaces réseau. Pour ce genre d'architectures, les environnements de génération de code classiques ne sont plus adaptés. Cette thèse propose un flot de génération de code de configuration pour le déploiement des applications de type flots de données sur les architectures à base d'IPs interconnectés à travers un réseau sur puce configurable. Le flot commence par un modèle de haut niveau de l'application et de l'architecture et propose une méthodologie de partitionnement des ressources. Le processus de génération de code passe par plusieurs étapes modélisées par diverses représentations intermédiaires du système. Le flot a été développé par la suite dans un environnement basé sur le standard IEEE 1685 (IP-XACT). Le flot proposé a été appliqué pour la génération et la validation du code de configuration en vue de déployer une application 3GPP-LTE de télécommunication sur la plateforme Magali. Le flot a ensuite été généralisé pour supporter, en plus de la génération du code de configuration, la génération du code logiciel exécutable par les processeurs.

Les réseaux complexes sont des ensembles constitués d’un grand nombre d’entités interconnectées par des liens. Ils sont modélisés par des graphes dans lesquels les noeuds représentent les entités et les arêtes entre les noeuds représentent les liens entre ces entités. Ces graphes se caractérisent par un très grand nombre de sommets et une très faible densité de liens. Les réseaux sociaux sont des exemples de réseaux complexes où les entités sont des individus et les liens sont les relations (d’amitié, d’échange de messages) entre ces individus.L’analyse des réseaux complexes est généralement basée sur l’exploration locale du graphe sous-jacent : après avoir traité un nœud u, les prochains noeuds auxquels l’application fait référence appartiennent au voisinage de u. Étant donné que le graphe sous-jacent est habituellement non structuré, les séquences d’accès aux données en mémoire tendent à avoir une faible localité lorsque qu’on utilise par exemple le stockage de Yale qui est l’un des meilleurs connus. En plus, dans les applications basées sur l’analyse des réseaux le nombre de calculs requis pour chaque noeud peut être très variable, ce qui, dans les mises en œuvre parallèles (multithreadées), se traduit par un déséquilibre de charges entre les threads.Le travail réalisé dans cette thèse était lié au développement d’applications d’analyse des réseaux sociaux, qui soient à la fois faciles à écrire et efficaces. A cet effet, deux pistes ont été explorées: a)L’exploitation de la structure en communautés pour définir des techniques de stockage qui réduisent les défauts de cache lors de l’analyse des réseaux sociaux; b)La prise en compte de l’hétérogénéité des degrés des noeuds pour optimiser la mise en oeuvre parallèle.La première contribution de cette thèse met en évidence l'exploitation de la structure en communautés des réseaux complexes pour la conception des algorithmes de numérotation des graphes (NumBaCo, CN-order) permettant la réduction des défauts de cache des applications tournant dans ces graphes.Les résultats expérimentaux en mode séquentiel sur plusieurs architectures (comme Numa4) ont montré que les défauts de cache et ensuite le temps d'exécution étaient effectivement réduits; et que CN-order se sert bien des avantages des autres heuristiques de numérotation (Gorder, Rabbit, NumBaCo) pour produire les meilleurs résultats.La deuxième contribution de cette thèse a considéré le cas des applications multi-threadées. Dans ce cas, la réduction des défauts de cache n'est pas suffisante pour assurer la diminution du temps d'exécution; l'équilibre des charges entre les threads doit être assuré pour éviter que certains threads prennent du retard et ralentissent ainsi toute l'application. Dans ce sens, nous nous sommes servis de la propriéte de l'hétérogénéité des dégrés des noeuds pour développer l'heuristique Deg-scheduling. Les résultats expérimentaux avec plusieurs threads sur l'architecture Numa4 montrent que Deg-scheduling combiné aux heuristiques de numérotation permet d'obtenir de meilleur résultats.La dernière contribution de cette thèse porte sur l'intégration des deux catégories d'heuristiques développées dans les DSLs parallèles d'analyse des graphes. Par exemple, avec le DSL Green-Marl, les performances sont améliorées à la fois grâce aux heuristiques de numérotation et grâce aux heuristiques d’ordonnancement (temps réduit de 35% grâce aux heuristiques). Mais avec le DSL Galois, les performances sont améliorées uniquement grâce aux heuristiques de numérotation (réduction de 48%). / A complex network is a set of entities in a relationship, modeled by a graph where nodes represent entities and edges between nodes represent relationships. Graph algorithms have inherent characteristics, including data-driven computations and poor locality. These characteristics expose graph algorithms to several challenges, because most well studied (parallel) abstractions and implementation are not suitable for them. The main question in this thesis is how to develop graph analysis applications that are both --easy to write (implementation challenge), -- and efficient (performance challenge)? We answer this question with parallelism (parallel DSLs) and also with knowledge that we have on complex networks (complex networks properties such as community structure and heterogeneity of node degree).The first contribution of this thesis shows the exploitation of community structure in order to design community-aware graph ordering for cache misses reduction. We proposed NumBaCo and compared it with Gorder and Rabbit (which appeared in the literature at the same period NumBaCo was proposed). This comparison allowed to design Cn-order, another heuristic that combines advantages of the three algorithms (Gorder, Rabbit and NumBaCo) to solve the problem of complex-network ordering for cache misses reduction. Experimental results with one thread on Core2, Numa4 and Numa24 (with Pagerank and livejournal for example) showed that Cn-order uses well the advantages of the other orders and outperforms them.The second contribution of this thesis considered the case of multiple threads applications. In that case, cache misses reduction was not sufficient to ensure execution time reduction; one should also take into account load balancing among threads. In that way, heterogeneity of node degree was used in order to design Deg-scheduling, a heuristic to solve degree-aware scheduling problem. Deg-scheduling was combined to Cn-order, NumBaCo, Rabbit, and Gorder to form respectively Comm-deg-scheduling, Numb-deg-scheduling, Rab-deg-scheduling and Gor-deg-scheduling. Experimental results with many threads on Numa4 showed that Degree-aware scheduling heuristics (Comm-deg-scheduling, Numb-deg-scheduling, Rab-deg-scheduling and Gor-deg-scheduling) outperform their homologous graph ordering heuristics (Cn-order, NumBaCo, Rabbit, and Gorder) when they are compared two by two.The last contribution was the integration of graph ordering heuristics and degree-aware scheduling heuristics in graph DSLs and particularly Galois and Green-Marl DSLs. We showed that with Green-Marl, performances are increased by both graph ordering heuristics and degree-aware scheduling heuristics (time was reduced by 35% due to heuristics). But with Galois, performances are increased only with graph ordering heuristics (time was reduced by 48% due to heuristics).In perspective, instead of using complex networks properties to design heuristics, one can imagine to use machine learning. Another perspective concerns the theoretical aspect of this thesis. We showed that graph ordering for cache misses reduction and degree-aware scheduling for load balancing problems are NP-complete. We provided heuristics to solve them. But we didn't show how far these heuristics are to the optimal solutions. It is good to know it in the future.

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. / 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.

Lors de la conception de systèmes cyber-physiques, des modèles issus de différents environnements de modélisation doivent être intégrés afin de simuler l'ensemble du système et estimer ses performances. Si certaines parties du système sont disponibles, il est possible de connecter ces parties à la simulation dans une approche Hardware-in-the-Loop (HiL). La simulation doit alors être effectuée en temps réel où les modèles réagissent périodiquement aux composants réels. En utilisant des modèles complexes, il devient difficile d'assurer une exécution rapide ou en temps réel sans utiliser des architectures multiprocesseurs. FMI (Functional Mocked-up Interface), un standard pour l'échange de modèles et la co-simulation, offre de nouvelles possibilités d'exécution multi-cœurs des modèles. L'un des objectifs de cette thèse est de permettre l'extraction du parallélisme potentiel dans une co-simulation multi-rate. Nous nous appuyons sur l'approche RCOSIM qui permet la parallélisation de modèles FMI. Des améliorations sont proposées dans le but de surmonter les limitations de RCOSIM. Nous proposons de nouveaux algorithmes pour permettre la prise en charge de modèles multi-rate. Les améliorations permettent de gérer des contraintes spécifiques telles que l'exclusion mutuelle et les contraintes temps réel. Nous proposons des algorithmes pour l'ordonnancement des co-simulations, en tenant compte de différentes contraintes. Ces algorithmes visent à accélérer la co-simulation ou assurer son exécution temps réel dans une approche HiL. Les solutions proposées sont testées sur des co-simulations synthétiques et validées sur un cas industriel. / When designing cyber-physical systems, engineers have to integrate models from different modeling environments in order to simulate the whole system and estimate its global performances. If some parts of the system are 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 periodically react to the real components. 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), a standard for model exchange and co-simulation, offers new opportunities for multi-core execution of 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 which allows the parallelization of FMI models. In the first part of the thesis, improvements have been proposed to overcome the limitations of RCOSIM. We propose new algorithms in order to allow handling multi-rate models and schedule them on multi-core processors. The improvements allow handling specific constraints such as mutual exclusion and real-time constraints. Second, we propose algorithms for the allocation and scheduling of co-simulations, taking into account different 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 synthetic co-simulations and validated against an industrial use case.

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.

Une multitude d'algorithmes d'exclusion mutuelle ont été conçus au cours des vingt cinq dernières années, dans le but d'améliorer les performances liées à l'exécution de sections critiques et aux verrous.Malheureusement, il n'existe actuellement pas d'étude générale et complète au sujet du comportement de ces algorithmes d'exclusion mutuelle sur des applications réalistes (par opposition à des applications synthétiques) qui considère plusieurs métriques de performances, telles que l'efficacité énergétique ou la latence.Dans cette thèse, nous effectuons une analyse pragmatique des mécanismes d'exclusion mutuelle, dans le but de proposer aux développeurs logiciels assez d'informations pour leur permettre de concevoir et/ou d'utiliser des mécanismes rapides, qui passent à l'échelle et efficaces énergétiquement.Premièrement, nous effectuons une étude de performances de 28 algorithmes d'exclusion mutuelle faisant partie de l'état de l'art, en considérant 40 applications et quatre machines multicœurs différentes.Nous considérons non seulement le débit (la métrique de performance traditionnellement considérée), mais aussi l'efficacité énergétique et la latence, deux facteurs qui deviennent de plus en plus importants.Deuxièmement, nous présentons une analyse en profondeur de nos résultats.Plus particulièrement, nous décrivons neufs problèmes de performance liés aux verrous et proposons six recommandations aidant les développeurs logiciels dans le choix d'un algorithme d'exclusion mutuelle, se basant sur les caractéristiques de leur application ainsi que les propriétés des différents algorithmes.A partir de notre analyse détaillée, nous faisons plusieurs observations relatives à l'interaction des verrous et des applications, dont plusieurs d'entre elles sont à notre connaissance originales:(i) les applications sollicitent fortement les primitives lock/unlock mais aussi l'ensemble des primitives de synchronisation liées à l'exclusion mutuelle (ex. trylocks, variables de conditions),(ii) l'empreinte mémoire d'un verrou peut directement impacter les performances de l'application,(iii) pour beaucoup d'applications, l'interaction entre les verrous et l'ordonnanceur du système d'exploitation est un facteur primordial de performance,(iv) la latence d'acquisition d'un verrou a un impact très variable sur la latence d'une application,(v) aucun verrou n'est systématiquement le meilleur,(vi) choisir le meilleur verrou est difficile, et(vii) l'efficacité énergétique et le débit vont de pair dans le contexte des algorithmes d'exclusion mutuelle.Ces découvertes mettent en avant le fait que la synchronisation à base de verrou ne se résume pas seulement à la simple interface "lock - unlock".En conséquence, ces résultats appellent à plus de recherche dans le but de concevoir des algorithmes d'exclusion mutuelle avec une empreinte mémoire faible, adaptatifs et qui implémentent l'ensemble des primitives de synchronisation liées à l'exclusion mutuelle.De plus, ces algorithmes ne doivent pas seulement avoir de bonnes performances d'un point de vue du débit, mais aussi considérer la latence ainsi que l'efficacité énergétique. / A plethora of optimized mutual exclusion lock algorithms have been designed over the past 25 years to mitigate performance bottlenecks related to critical sections and synchronization.Unfortunately, there is currently no broad study of the behavior of these optimized lock algorithms on realistic applications that consider different performance metrics, such as energy efficiency and tail latency.In this thesis, we perform a thorough and practical analysis, with the goal of providing software developers with enough information to achieve fast, scalable and energy-efficient synchronization in their systems.First, we provide a performance study of 28 state-of-the-art mutex lock algorithms, on 40 applications, and four different multicore machines.We not only consider throughput (traditionally the main performance metric), but also energy efficiency and tail latency, which are becoming increasingly important.Second, we present an in-depth analysis in which we summarize our findings for all the studied applications.In particular, we describe nine different lock-related performance bottlenecks, and propose six guidelines helping software developers with their choice of a lock algorithm according to the different lock properties and the application characteristics.From our detailed analysis, we make a number of observations regarding locking algorithms and application behaviors, several of which have not been previously discovered:(i) applications not only stress the lock/unlock interface, but also the full locking API (e.g., trylocks, condition variables),(ii) the memory footprint of a lock can directly affect the application performance,(iii) for many applications, the interaction between locks and scheduling is an important application performance factor,(iv) lock tail latencies may or may not affect application tail latency,(v) no single lock is systematically the best,(vi) choosing the best lock is difficult (as it depends on many factors such as the workload and the machine), and(vii) energy efficiency and throughput go hand in hand in the context of lock algorithms.These findings highlight that locking involves more considerations than the simple "lock - unlock" interface and call for further research on designing low-memory footprint adaptive locks that fully and efficiently support the full lock interface, and consider all performance metrics.

Dans le contexte du développement de systèmes embarqués alliant hautes performances et basse consommation, la recherche de l'efficacité énergétique optimale des processeurs est devenue un défi majeur. Les solutions architecturales se sont positionnées durant les dernières décennies comme d'importantes contributrices à ce challenge. Ces solutions, permettant la gestion du compromis performance de calcul/consommation, se sont dans un premier temps développées pour les circuits mono-processeurs. Elles évoluent aujourd'hui pour s'adapter aux contraintes de circuits MPSoCs de plus en plus complexes et sensibles aux déviations des procédés de fabrication, aux variations de tension et de température. Cette variabilité limite aujourd'hui drastiquement l'efficacité énergétique de chacune des unités de calcul qui composent une architecture MPSoC, car des marges pessimistes de fonctionnement sont généralement prises en compte. De grandes améliorations peuvent être attendues de la diminution de ces marges de fonctionnement en surveillant dynamiquement et localement la variabilité de chaque unité de calcul afin de réajuster ses paramètres de fonctionnement tension/fréquence. Ce travail s'insère dans une solution architecturale bas-coût nommée AVFS, basée sur une optimisation des techniques de gestion locales DVFS, permettant de réduire les marges de conception afin d'améliorer l'efficacité énergétique des MPSoCs, tout en minimisant l'impact de la solution proposée sur la surface de silicium et l'énergie consommée. Le développement d'un système de surveillance des variations locales et dynamiques de la tension et de la température à partir d'un capteur bas coût a été proposé. Une première méthode permet d'estimer conjointement la tension et la température à l'aide de tests statistiques. Une seconde permet d'accélérer l'estimation de la tension. Enfin, une méthode de calibration associée aux deux méthodes précédentes a été développée. Ce système de surveillance a été validé sur une plateforme matérielle afin d'en démontrer le caractère opérationnel. En prenant en compte les estimées de tension et de température, des politiques visant à réajuster dynamiquement les consignes des actionneurs locaux de tension et de fréquence ont été proposées. Finalement, la consommation additionnelle due à l'intégration des éléments constitutifs de l'architecture AVFS a été évaluée et comparée aux réductions de consommation atteignables grâce aux réductions des marges de fonctionnement. Ces résultats ont montré que la solution AVFS permet de réaliser des gains en consommation substantiels par rapport à une solution DVFS classique. / Nowadays, embedded systems requiring high performance and low power, the search for the optimal efficiency of the processors has become a major challenge. Architectural solutions have positioned themselves in recent decades as one of the main contributors to this challenge. These solutions enable the management of the trade-off between performance / power consumption, initially developed for single -processor systems. Today, they evolve to be adapted to the constraints of circuits MPSoCs increasingly complex and sensitive to process, voltage and temperature variations. This PVT variability limits drastically the energy efficiency of each of the processing units of a MPSoC architecture, taking into account pessimistic operating margins. Significant improvements can be expected from the reduction of the operating margins by dynamically monitoring and local variability of each resource and by adjusting its voltage / frequency operating point. This work is part of a low-cost architectural solution called AVFS, based on local DVFS optimization technique, to reduce design margins and improve the energy efficiency of MPSoCs, while minimizing the silicon surface and the energy additional cost. The development of a monitoring system of local and dynamic voltage and temperature variations using a low-cost sensor has been proposed. A first method estimates jointly voltage and temperature using statistical tests. A second one speeds up estimation of the voltage. Finally, a calibration method associated with the two previous methods has been developed. This monitoring system has been validated on a hardware platform to demonstrate its operational nature. Taking into account the estimation of voltage and temperature values, policies to dynamically adjust the set point of the local voltage and frequency actuators have been proposed. Finally, the additional power consumption due to the integration of the components of the architecture AVFS was evaluated and compared with reductions achievable through reductions in operating margins consumption. These results showed that the AVFS solution can achieve substantial power savings compared to conventional DVFS solution.

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. / 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.

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. / 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.