Les architectures modulaires intégrées (IMA) sont une évolution majeure de l'architecture des systèmes avioniques. Elles permettent à plusieurs systèmes de se partager des ressources matérielles sans interférer dans leur fonctionnement grâce à un partitionnement spatial (zones mémoires prédéfinies) et temporel (ordonnancement statique) dans les processeurs ainsi qu'une réservation des ressources sur les réseaux empruntés. Ces allocations statiques permettent de vérifier le déterminisme général des différents systèmes: chaque système doit respecter des exigences de bout-en-bout dans une architecture asynchrone. Une étude pire cas permet d'évaluer les situations amenant aux limites du système et de vérifier que les exigences de bouten- bout sont satisfaites dans tous les cas. Les architectures IMA utilisés dans les avions centralisent physiquement des modules de calcul puissants dans des baies avioniques. Dans le cadre d'une étude de cas hélicoptère, ces baies ne sont pas envisageables pour des raisons d'encombrement: des processeurs moins puissants, utilisés à plus de 80%, composent ces architectures. Pour ajouter de nouvelles fonctionnalités ainsi que de nouveaux équipements, le souhait est de distribuer la puissance de traitement sur un plus grand nombre de processeurs dans le cadre d'une architecture globale asynchrone. Deux problématiques fortes ont été mises en avant tout au long de cette thèse. La première est la répartition des fonctions avioniques associée à une contrainte d'ordonnancement hors-ligne sur les différents processeurs. La deuxième est la satisfaction des exigences de communication de bout-en-bout, dépendantes de l'allocation et l'ordonnancement des fonctions ainsi que des latences de communication sur les réseaux. La contribution majeure de cette thèse est la recherche d'un compromis entre la distribution des architectures IMA sur un plus grand nombre de processeurs et la satisfaction des exigences de communication de bout-en-bout. Nous répondons à cet enjeu de la manière suivante: - Nous formalisons dans un premier temps un modèle de partitions communicantes tenant en compte des contraintes d'allocation et d'ordonnancement des partitions d'une part et des contraintes de communication de bout-en-bout entre partitions d'autre part. - Nous présentons dans un deuxième temps une recherche exhaustive des architectures valides. Nous proposons l'allocation successive des fonctions avioniques en considérant au même niveau la problématique d'ordonnancement et la satisfaction des exigences de bout-en-bout avec des latences de communication figées. Cette méthode itérative permet de construire des allocations de partitions partiellement valides. La construction des ordonnancements dans chacun des processeurs est cependant une démarche coûteuse dans le cadre d'une recherche exhaustive. - Nous avons conçu dans un troisième temps une heuristique gloutonne pour réduire l'espace de recherche associé aux ordonnancements. Elle permet de répondre aux enjeux de distribution d'une architecture IMA dans un contexte hélicoptère. - Nous nous intéressons dans un quatrième temps à l'impact des latences de communication de bout-en-bout sur des architectures distribuées données. Nous proposons pour celles-ci les choix de réseaux basés sur les latences de communication admissibles entre les différentes fonctions avioniques. Les méthodes que nous proposons répondent au besoin industriel de l'étude de cas hélicoptère, ainsi qu'à celui de systèmes de plus grande taille.

Les travaux de thèse s'intéressent à la problématique de contrôle et de communication dans le domaine de la conception des systèmes numériques embarqués pour les applications de télécommunication de quatrième génération. La complexité des applications couplée aux besoins de productivité croissants impose de repenser les méthodologies de conception et les architectures sous jacentes. Afin de lever ces verrous, nous proposons plusieurs contributions originales. En effet, une méthodologie d'exploration d'un espace de conception ainsi qu'une architecture basée sur des noeuds de traitements homogènes et flexibles interconnectés à travers un réseau sur silicium sont proposées. Chaque noeud de traitement possède plusieurs blocs visant à exécuter efficacement et dynamiquement les applications de télécommunication. Pour répondre aux contraintes de faible consommation, nous proposons plusieurs solutions innovantes afin de minimiser cette métrique notamment au travers de techniques de migration de tâches. / This PhD research aims to solve challenges about control and communication in the design of digital embedded systems for 4G telecom applications. The application complexity added to the increasing productivity gap force to think about new design methodologies and the underlying architectures. Several new research directions is proposed in this work. A methodology for design space exploration and a digital architecture based on homogeneous and flexible processing units interconnected by a Network-on-Chip is proposed. A processing unit is a cluster of DSPs controled by a MIPS processor to compute telecom applications. To meet low power constraints, we propose optimization techniques based on resource management including task migration.

Quelque-soit le multiprocesseur et son architecture, la facilité de leur programmation demeure une difficulté majeure. Une croyance bien installée est que l’exploitation correcte et efficace du parallélisme dans une application est une question pour les concepteurs d’outils de développement logiciel. Selon cette vision, nous avons besoin de techniques de compilation plus sophistiqués pour partitionner une application en threads simultanés. Mais de nombreux experts revendiquent que l'architecture joue un rôle tout aussi important: il faut opérer un changement fondamental dans l'architecture de processeurs avant que l’on puisse espérer des progrès importants au niveau de leur programmabilité. Notre approche favorise la convergence de ces points de vue. La convergence entre le calcul parallèle “en flot de données” avec l'architecture de von Neumann est porteuse de nombreuses promesses. En particulier en termes de tolérance à la latence, en termes d’exploitation d'un haut degré de parallélisme, le tout pour un très faible coût de changement de contexte entre threads. Les architectures à flot de données multithread exigent un haut degré de parallélisme pour tolérer la latence. D'autre part, le partitionnement d’un programme en un grand nombre de threads à grain fin est une source d'erreurs commune pour les développeurs. Pour reconcilier ces faits, nous nous efforçons de faire progresser l'état de l'art dans le partitionnement automatique de threads, conjointement avec le support du langage de programmation pour l’exploitation de parallélisme à plus gros grain, tout en préservant un concurrence déterministe. Cette thèse présente un algorithme général de partitionnement de threads, pour transformer du code séquentiel en un programme exprimant du parallélisme en flot de données. Notre algorithme fonctionne sur le Program Dependence Graph (PDG) et la forme en assignation unique statique (Static Single Assignment, SSA), pour extraire du parallélisme de tâche, pipeline, et de données, en présence de flot de contrôle arbitraire. Nous avons conçu une nouvelle représentation intermédiaire pour faciliter la génération de code, et son exécution parallèle en flot de données. Nous avons également mis en œuvre ces algorithmes dans un prototype fondé sur GCC, et contribué au développement d’une plateforme de simulation permettant d’explorer la parallélisation en flot de données à grande échelle. Ces extensions et l'architecture simulée permettent l'exploration de modèles innovants de mémoire pour le parallélisme en flot de données. Ces outils et modèles ont également été évalués sur des applications réalistes. / Across the wide range of multiprocessor architectures, all seem to share one common problem: they are hard to program. It is a general belief that parallelism is a software problem, and that perhaps we need more sophisticated compilation techniques to partition the application into concurrent threads. Many experts also make the point that the underlining architecture plays an equally important architecture before one may expect significant progress in the programmability of multiprocessors. Our approach favors a convergence of these viewpoints. The convergence of dataflow and von Neumann architecture promises latency tolerance, the exploitation of a high degree of parallelism, and light thread switching cost. Multithreaded dataflow architectures require a high degree of parallelism to tolerate latency. On the other hand, it is error-prone for programmers to partition the program into large number of fine grain threads. To reconcile these facts, we aim to advance the state of the art in automatic thread partitioning, in combination with programming language support for coarse-grain, functionally deterministic concurrency. This thesis presents a general thread partitioning algorithm for transforming sequential code into a parallel data-flow program targeting a multithreaded dataflow architecture. Our algorithm operates on the program dependence graph and on the static single assignment form, extracting task, pipeline, and data parallelism from arbitrary control flow, and coarsening its granularity using a generalized form of typed fusion. We design a new intermediate representation to ease code generation for an explicit token match dataflow execution model. We also implement a GCC-based prototype. We also evaluate coarse-grain dataflow extensions of OpenMP in the context of a large-scale 1024-core, simulated multithreaded dataflow architecture. These extension and simulated architecture allow the exploration of innovative memory models for dataflow computing. We evaluate these tools and models on realistic applications.

Ce document présente nos contributions aux algorithmes d'ordonnancement à criticité mixte pour multi-processeurs. La correction de l'exécution des applications temps réel critiques est assurée par l'utilisation d'un ordonnancement vérifié à la conception. Dans ce contexte, le dimensionnement des plate-formes d'exécution vise à minimiser le nombre de processeurs nécessaires pour assurer un ordonnancement correct. Ce dimensionnement est affecté par les exigences de sûreté de fonctionnement. Ces exigences poussent à surestimer le temps nécessaire garantissant l'exécution correcte des applications. Il en découle un dimensionnement assez coûteux. Les méthodes d'ordonnancement des systèmes à criticité mixte proposent des compromis sur les garanties d'exécution des applications améliorant le dimensionnement. Différents compromis ont été proposés mais tous reposent sur la notion de mode d'exécution. Les modes sont ordonnés, et les tâches voient leur temps d'exécution requis croître avec les modes. Cependant, afin de diminuer le dimensionnement du système, seul l'ordonnancement des tâches les plus critiques est garanti. Ce modèle est appelé "discarding". La majorité des algorithmes proposés se limitent à deux modes d'exécutions par simplicité. De plus, les algorithmes les plus efficaces pour multi-processeurs exhibent un nombre élevé de préemptions, ce qui constitue un frein à leur adoption. Finalement, ces algorithmes sont rarement généralisables. Pourtant, la prise en compte de plus de deux modes, ou de tâches aux périodes élastiques permettrait une adoption plus large par le milieu industriel. L'approche proposée repose sur la séparation des préoccupations entre la prise en compte des modes de fonctionnement, et l'ordonnancement des tâches sur multi-processeurs. Cette méthode permet de concevoir une politique d'ordonnancement efficace et adaptable à différents modèles de systèmes à criticité mixte. Notre approche consiste à transformer un lot de tâches à criticité mixte en un lot de tâches qui n'est plus à criticité mixte. Ceci nous permet d'utiliser un algorithme d'ordonnancement temps réel optimal engendrant peu de préemptions et de migrations, à savoir RUN. Cette approche, appliquée en premier pour le modèle discarding avec deux modes d'exécution, rempli son objectif d'efficacité. Nous illustrons sa généricité en utilisant le même principe pour ordonnancer des systèmes discarding avec plus de deux modes d'exécution. Enfin, une démarche reposant sur la décomposition de tâche permet de généraliser l'approche au cas des tâches élastiques. / This thesis focuses on the scheduling of mixed-criticality scheduling algorithms for multi-processors. The correctness of the execution of the real-time applications is ensured by a scheduler and is checked during the design phase. The execution platform sizing aims at minimising the number of processors required to ensure this correct scheduling. This sizing is impacted by the safety requirements. Indeed, these requirements tend to overestimate the execution times of the applications to ensure their correct executions. Consequently, the resulting sizing is costly. The mixed-criticality scheduling theory aims at proposing compromises on the guarantees of the execution of the applications to reduce this over-sizing. Several models of mixed-criticality systems offering different compromises have been proposed but all are based on the use of execution modes. Modes are ordered and tasks have non decreasing execution times in each mode. Yet, to reduce the sizing of the execution platform, only the execution of the most critical tasks is ensured. This model is called the discarding model. For simplicity reasons, most of the mixed-criticality scheduling algorithms are limited to this model. Besides, the most efficient scheduling policies for multi-processors entail too many preemptions and migrations to be actually used. Finally, they are rarely generalised to handle different models of mixed-criticality systems. However, the handling of more than two execution modes or of tasks with elastic periods would make such solutions more attractive for the industry. The approach proposed in this thesis is based on the separation of concerns between handling the execution modes and the scheduling of the tasks on the multi-processors. With this approach, we achieve to design an efficient scheduling policy that schedules different models of mixed-criticality systems. It consists in performing the transformation of a mixed-criticality task set into a non mixed-criticality one. We then schedule this task set by using an optimal hard real-time scheduling algorithm that entails few preemptions and migrations: RUN. We first apply our approach on the discarding model with two execution modes. The results show the efficiency of our approach for such model. Then, we demonstrate the versatility of our approach by scheduling systems of the discarding model with more than two execution modes. Finally, by using a method based on the decomposition of task execution, our approach can schedule systems based on elastic tasks.

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

Actuellement, l'accélération des opérations de traitement d'images est principalement obtenue par l'utilisation de calculateurs parallèles. De tels processeurs, a flot d'instructions unique et a flots de données multiples (simd), sont développés, mais s'ils s'avèrent efficaces pour les opérations de traitement d'images dites de bas niveau, ou la structure des données reste la même, ils se heurtent a de nombreux problèmes lorsqu'il s'agit des opérations de moyen et de haut niveau. Notamment lors des opérations de moyen niveau, une réorganisation aléatoire des données sur les processeurs doit être effectuée, tache difficilement exécutable sur les structures parallèles synchrones a mémoire distribuée. Le but de cette thèse était d'étendre les capacités d'un calculateur simd, afin qu'il puisse exécuter, efficacement, les opérations de traitement d'images de moyen niveau. L'étude des algorithmes représentatifs de cette classe d'opérations dégage les limites de ce calculateur que des modifications d'architecture permettent d'affranchir. C'est ainsi que Sympatix, le nouveau calculateur SIMD, a été proposé. Afin de le valider, son modèle comportemental décrit en VHDL langage de description de matériel a été élaboré. Grâce a ce modèle, les performances de la nouvelle structure sont ainsi directement mesurées, par simulations d'algorithmes de traitement d'images. L'approche par modélisation VHDL permet, de plus, d'effectuer la conception électronique descendante du système, ce qui, par ailleurs, offre un couplage aise entre les modifications architecturales du système et leur cout électronique. Les résultats obtenus montrent que Sympatix est adapte aux opérations de traitement d'images de bas et de moyen niveau, qu'il est ouvert a un calculateur de haut niveau, et qu'il est capable de supporter d'autres applications de vision. Ce manuscrit présente également, une méthodologie de conception descendante, basée sur le vhdl, et destinée aux architectes de systèmes électroniques

Onze approches pour structurer, écrire, controler des applications reparties à activites parallèles. Présentation des d-modules. Description d'un langage. Exemple: écriture d'un petit systeme.

Les systèmes temps réel à contraintes temporelles strictes sont caractérisés par des ensembles de tâches pour lesquelles sont connus l'échéance, le modèle d'arrivée (fréquence) et la durée d'exécution pire cas (WCET). Nous nous intéressons à l'ordonnancement de ces systèmes sur plate-forme multiprocesseur. Garantir le respect des échéances pour un algorithme d'ordonnancement est l'une des problématiques majeures de cette thématique. Nous allons plus loin en nous intéressant à la sûreté temporelle, que nous caractérisons par les propriétés (i) de robustesse et (ii) de viabilité. La robustesse consiste à proposer un intervalle sur les augmentations (i-a) de WCET et (i-b) de fréquence tel que les échéances soient respectées. La viabilité consiste cette fois à garantir le respect des échéances lors du relâchement des contraintes (ii-a) de WCET (réduction), (ii-b) de fréquence (réduction) et (ii-c) d'échéance (augmentation). La robustesse revient alors à tolérer l'imprévu, tandis que la viabilité est la garantie que l'algorithme d'ordonnancement n'est pas sujet à des anomalies suite à un relâchement de contraintes. Nous considérons l'ordonnancement en priorités fixes, où chaque occurrence d'une tâche est ordonnancée avec la même priorité. Dans un premier temps, nous étudions la propriété de robustesse dans les approches d'ordonnancement hors-ligne et sans migration (partitionnement). Nous traitons le cas des tâches avec ou sans partage de ressources. Dans un second temps, nous étudions la propriété de viabilité d'une approche d'ordonnancement en ligne avec migrations restreintes et sans partage de ressources.

Nowadays, computer systems are everywhere. From simple portable devices such as watches and MP3 players to large stationary installations that control nuclear power plants, computer systems are now present in all aspects of our modern and every-day life. In about only 70 years, they have completely perturbed our way of life and they reached a so high degree of sophistication that they will be soon capable of driving our cars and cleaning our houses without any human intervention. As computer systems gain in responsibilities, it becomes essential that they provide both safety and reliability. Indeed, a failure in systems such as the anti-lock braking system (ABS) in cars could threaten human lives and generate catastrophic and irreversible consequences. Hence, for many years, researchers have addressed these emerging problems of system safety and reliability which come along with this fulgurant evolution. This thesis provides a general overview of embedded real-time computer systems, i.e., a particular kind of computer system whose number grows daily. We provide the reader with some preliminary knowledge and a good understanding of the concepts that underlie this emerging technology. We focus especially on the theoretical problems related to the real-time issue and briefly summarizes the main solutions, together with their advantages and drawbacks. This brings the reader through all the conceptual layers constituting a computer system, from the software level---the logical part---that specifies both the system behavior and requirements to the hardware level---the physical part---that actually performs the expected treatments and reacts to the environment. In the meanwhile, we introduce the theoretical models that allow researchers for theoretical analyses which ensure that all the system requirements are fulfilled. Finally, we address the energy consumption problem in embedded systems. We describe the various factors of power dissipation in modern technologies and we introduce different solutions to reduce this consumption./Cette thèse se focalise sur un type de systèmes informatiques bien précis appelés “systèmes embarqués temps réel”. Un système est dit “embarqué” lorsqu’il est développé afin de servir un but bien précis. Un téléphone portable est un parfait exemple de système embarqué étant donné que toutes ses fonctionnalités sont rigoureusement définies avant même sa conception. Au contraire, un ordinateur personnel n’est généralement pas considéré comme un système embarqué, les concepteurs ne sachant pas à l’avance à quelles fins il sera utilisé. Une grande partie de ces systèmes embarqués ont des contraintes temporelles très fortes, ce qui les distingue encore plus des ordinateurs grand public. A titre d’exemple, lorsqu’un conducteur de voiture freine brusquement, l’ordinateur de bord déclenche l’application ABS et il est primordial que cette application soit traitée endéans une courte échéance. Autrement dit, cette fonctionnalité ABS doit être traitée prioritairement par rapport aux autres fonctionnalités du véhicule. Ce type de système embarqué est alors dit “temps réel”, dû à ces notions de temps et de priorités entre les applications. La problèmatique posée par les systèmes temps réel est la suivante. Comment déterminer, à tout moment, un ordre d’exécution des différentes fonctionnalités de telle sorte qu’elles soient toutes exécutées entièrement endéans leur échéance ? De plus, avec l’apparition récente des systèmes multiprocesseurs, cette problématique s’est fortement complexifiée, vu que le système doit à présent déterminer quelle fonctionnalité s’exécute à quel moment sur quel processeur afin que toutes les contraintes temporelles soient respectées. Pour finir, ces systèmes embarqués temp réel multiprocesseurs se sont rapidement retrouvés confrontés à un problème de consommation d’énergie. Leur demande en terme de performance (et donc en terme d’énergie) à évolué beaucoup plus rapidement que la capacité des batteries qui les alimentent. Ce problème est actuellement rencontré par de nombreux systèmes, tels que les téléphones portables par exemple. L’objectif de cette thèse est de parcourir les différents composants de tels système embarqués et de proposer des solutions afin de réduire leur consommation d’énergie.

De nombreuses techniques de codage de canal sont spécifiées dans les nouvelles normes de communications numériques, chacune adaptée à des besoins applicatifs spécifiques (taille de trame, type de canal de transmission, rapport signal-à-bruit, bande-passante, etc.). Si l'on considère les applications naissantes multi-mode et multi-standard, ainsi que l'intérêt croissant pour la radio logicielle et la radio cognitive, la combinaison de plusieurs techniques de correction d'erreur devient incontournable. Néanmoins, des solutions optimales en termes de performance, de consommation d'énergie et de surface sont encore à inventer et ne doivent pas être négligées au profit de la flexibilité. Dans ce contexte, ce travail de thèse a exploré le modèle d'architecture multi-ASIP dans le but d¿unifier l'approche orientée sur la flexibilité et celle orientée sur l'optimalité dans la conception de décodeurs de canal flexibles. En considérant principalement les applications exigeantes de décodage itératif des turbocodes et des codes LDPC, des architectures multi-ASIP de décodeurs de canal sont proposées ciblant une grande flexibilité combinée à une haute efficacité architecturale en termes de bits/cycle/iteration/mm2. Différentes solutions architecturales et différentes approches de conception sont explorées pour proposer trois contributions originales. La première contribution concerne la conception d'un décodeur LDPC/Turbo multi-ASIP extensible, flexible et haut débit. Plusieurs objectifs de conception sont atteints en termes d'extensibilité, de partage de ressources, et de vitesse de configuration. Le décodeur proposé, nommé DecASIP, supporte le décodage des codes LDPC et turbocodes spécifiés dans les normes WiFi, WiMAX et LTE. L'extensibilité apportée par l'approche multi-ASIP basée sur des réseaux sur puces (NoC) permet d'atteindre les besoins en haut débit des normes actuelles et futures. La deuxième contribution concerne la conception d'un ASIP paramétré pour le turbo-décodage (TDecASIP). L'objectif étant d'étudier l'efficacité maximale atteignable pour un turbo décodeur basé sur le concept ASIP en maximisant l¿exploitation du parallélisme de sous-blocs. En outre, avec cette architecture nous avons démontré la possibilité de concevoir des c¿urs de traitement paramétrables et dédiés à l¿application en utilisant le flot de conception ASIP existant. La troisième contribution correspond à la conception d'un ASIP optimisé pour le décodage des codes LDPC (LDecASIP). Comme pour TDecASIP, l'objectif étant d'étudier l'efficacité maximale atteignable pour un décodeur de codes LDPC basé sur le concept ASIP en augmentant le degré de parallélisme et la bande passante des mémoires. Une quatrième contribution principale de cette thèse porte sur le prototypage matériel. Une plateforme de communication complète intégrant 4-DecASIP pour le décodage de canal a été prototypé sur une carte à base de circuits FPGA. À notre connaissance, c'est le premier prototype FPGA publié de décodeur de canal flexible supportant le décodage des turbocodes et des codes LDPC avec une architecture multi-ASIP intégrant des NoC. De plus, une intégration ASIC de ce décodeur a été réalisée par le CEA-LETI dans la puce MAG3D visant des applications de communications pour la 4G. Ces résultats démontrent le cycle de conception rapide et l'efficacité offerte par l'approche de conception basée sur le concept ASIP dans ce domaine d'application, permettant ainsi d¿affiner les compromis de conception par rapport aux divers objectifs ciblés.