Les architectures multiprocesseurs de systèmes sur puce permettent de réaliser un nombre croissant de fonctions en logiciel, ce qui multiplie le nombre d'interfaces entre le logiciel et le matériel. Cette interface est représentée de différentes façons au sein des modèles, selon leur niveau d'abstraction : à haut niveau, un canal abstrait est utilisé ; plus près de l'implémentation, plusieurs composants d'adaptation et de communication composent l'interface. La conception assistée des systèmes multiprocesseurs repose donc sur la maîtrise de l'interface logiciel-matériel à plusieurs niveaux d'abstraction. Dans cette thèse, le concept de service est utilisé pour abstraire les caractéristiques de communication et de performance des interfaces. Une structure de données permet de capturer ces caractéristiques et de développer des outils d'analyse et de génération d'interfaces. Une étude de cas illustre l'exploration d'architecture par la génération de prototypes virtuels en SystemC.

Différentes analyses de la méthode de Givens en parallèle sur une architecture à mémoire partagée sont examinées. Présentation de résultats de complexité et d'algorithmes asymptotiquement optimaux. Dans une deuxième partie, consacrée aux architectures à mémoire distribuée, les couts de communication sont pris en compte. Une analyse macroscopique montre l'influence de l'architecture sur la complexité des décompositions de Givens et de Householder s'exécutant sur différents réseaux de processeurs fonctionnant par échange de messages

L'étude des principaux domaines d'application et des techniques essentielles du traitement d'images permet de dégager des interrogations directes pour le concepteur d'architectures d'ordinateurs. Quelques unes des voies possibles pour leurs solutions matérielles sont ensuite présentées dans leurs principes et a l'aide d'exemples. Présentation de deux études : la machine ROMULARD (multi-microprocesseur) pour la saisie et le traitement d'images et le systeme KIDS, architecture plus ambitieuse alliant les aspects logiciels et matériels.

L'accroissement d'efficacité des réseaux d'interconnexion et la vulgarisation des machines multiprocesseurs permettent la réalisation de machines parallèles à mémoire distribuée de faible coût: les grappes de multiprocesseurs. Elles nécessitent l'exploitation à la fois du parallélisme à grain fin, interne à un multiprocesseur offert par la multiprogrammation légère, et du parallélisme à gros grain entre les différents multiprocesseurs. L'exploitation simultanée de ces deux types de parallélisme exige une méthode de communication entre les processus légers qui ne partagent pas le même espace d'adressage. Le travail de cette thèse porte sur le problème de l'intégration de la multiprogrammation légère et des communications sur grappes de multiprocesseurssymétriques (SMP). Il porte plus précisément sur l'évaluation et le réglage dunoyau exécutif ATHAPASCAN-0 sur ce type d'architecture. ATHAPASCAN-0 est un noyau exécutif,portable, développé au sein du projet APACHE (CNRS-INPG-INRIA-UJF), qui combinela multiprogrammation légère et la communication par échange de messages. La portabilité est assurée par une organisation en couches basée sur les standards POSIX threads et MPI largement répandus. ATHAPASCAN-0 étend le modèle de réseaustatique de processus «lourds» communicants tel que MPI, PVM, etc, à celui d'un réseau dynamique de processus légers communicants. La technique de base est la multiprogrammation légère des communications et des calculs. La progression des communications exige la scrutation de l'état du réseau et l'enchaînement des opérations de transferts. L'efficacité repose sur la minimisation de ces opérations. De plus, l'emploi de multiprocesseurs ajoute des problèmes spécifiques dus à l'apparition d'un parallélisme réel entre calcul et communication. Ces problèmes sont présentés et des solutions sont proposées pour l'environnement ATHAPASCAN-0. Ces solutions sont évaluées sur des grappes de multiprocesseurs.

Dans le cadre de son offre de serveurs haut de gamme, la société Bull conçoit des multiprocesseurs à mémoire distribuée partagée avec un protocole de cohérence de cache CC-DSM (Cache-Coherent Distibuted Shared Memory), et fournit une implémentation de la bibliothèque MPI (Message Passing Interface) pour la programmation parallèle. L'évaluation des performances de cette implémentation permettra, d'une part, de faire les bons choix d'architecture matérielle et de la couche logicielle au moment de la conception et, d'autre part, fournira des éléments d'analyse nécessaires pour comprendre les mesures faites au moment de la validation de la machine réelle. Nous proposons et mettons en œuvre dans ce travail de thèse une méthodologie permettant d'évaluer les performances des algorithmes de la bibliothèque MPI (ping-pong et barrières) en tenant compte de l'architecture matérielle. Cette approche est basée sur l'utilisation des méthodes formelles, elle consiste en 3 étapes principales : 1) la modélisation en langage LOTOS des aspects matériels (topologie d'interconnexion et protocole de cohérence de cache) et logiciels (algorithmes MPI) ; 2) la vérification formelle de la correction fonctionnelle du modèle obtenu ; 3) l'évaluation des performances après l'extension du modèle par des informations quantitatives (latences des transferts des données) en utilisant des méthodes numériques et de la simulation.

Les systèmes multiprocesseurs sur puce, tel que le processeur CELL ou plus récemment Platform 2012, sont des architectures multicœurs hétérogènes constitués d'un processeur host et d'une fabric de calcul qui consiste en plusieurs petits cœurs dont le rôle est d'agir comme un accélérateur programmable. Les parties parallélisable d'une application, qui initialement est supposé etre executé par le host, et dont le calcul est intensif sont envoyés a la fabric multicœurs pour être exécutés. Ces applications sont en général des applications qui manipulent des tableaux trés larges de données, ces données sont stockées dans une memoire distante hors puce (off-chip memory) dont l 'accès est 100 fois plus lent que l 'accès par un cœur a une mémoire locale. Accéder ces données dans la mémoire off-chip devient donc un problème majeur pour les performances. une characteristiques principale de ces plateformes est une mémoire local géré par le software, au lieu d un mechanisme de cache, tel que les mouvements de données dans la hiérarchie mémoire sont explicitement gérés par le software. Dans cette thèse, l 'objectif est d'optimiser ces transfert de données dans le but de reduire/cacher la latence de la mémoire off-chip . / Multiprocessor system on chip (MPSoC) such as the CELL processor or the more recent Platform2012 are heterogeneous multi-core architectures, with a powerful host processor and a computation fabric, consisting of several smaller cores, whose intended role is to act as a general purpose programmable accelerator. Therefore computation-intensive (and parallelizable) parts of the application initially intended to be executed by the host processor are offloaded to the multi-cores for execution. These parts of the application are often data intensive, operating on large arrays of data initially stored in a remote off-chip memory whose access time is about 100 times slower than that of the cores local memory. Accessing data in the off-chip memory becomes then a main bottleneck for performance. A major characteristic of these platforms is a software controlled local memory storage rather than a hidden cache mechanism where data movement in the memory hierarchy, typically performed using a DMA (Direct Memory Access) engine, are explicitely managed by the software. In this thesis, we attempt to optimize such data transfers in order to reduce/hide the off-chip memory latency.

Une séparation existe de longue date entre les domaines de la compilation et de l'ordonnancement temps-réel. Si ces deux domaines ont le même objectif - la construction d'implantations correctes - la séparation se justifie historiquement par des différences significatives entre les modèles et les méthodes utilisés. Cependant, avec la complexification des applications et du materiel qui les exécute, les problèmes étudiés dans ces deux domaines se confondent désormais largement. Dans cette thèse, nous nous concentrons sur la génération automatique de code pour des systèmes de contrôle embarqué incluant des contraintes complexes (notamment temps-réel). A ces fins, nous défendons l'idée qu'il est profitable de fournir un effort commun de recherche entre ces deux communautés. En adaptant une technique de compilation au problème d'ordonnancement temps réel d'applications sur des architectures multiprocessurs, nous montrons à la fois les difficultés inhérentes à cet effort commun, mais aussi les possibles avancées qu'il porte. En effet, nous montrons que l'adaptation de techniques d'optimisation à de nouveaux objectifs, dans un contexte différent facilite le développement de systèmes de meilleure qualité. Nous proposons d'utiliser les formalismes et langages synchrones comme base formelle commune dans ce travail d'adaptation. Ceux-cis étendent naturellement les modèles classiques utilisés pour l'ordonnancement temps réel (graphes de tâches dépendentes) et la compilation (SSA et graphes de dépendence de données), et fournissent également des techniques efficaces pour la manipulation de structures de contrôle complexes. Nous avons implanté nos résultats dans le compilateur LoPhT. / There is a long standing separation between the fields of compiler construction and real-time scheduling. While both fields have the same objective - the construction of correct implementations – the separation was historically justified by significant differences in the models and methods that were used. Nevertheless, with the ongoing complexification of applications and of the hardware of the execution platforms, the objects and problems studied in these two fields are now largely overlapping. In this thesis, we focus on the automatic code generation for embedded control systems with complex constraints, including hard real-time requirements. To this purpose, we advocate the need for a reconciled research effort between the communities of compilation and real-time systems. By adapting a technique usually used in compilers (software pipelining) to the system-level problem of multiprocessor scheduling of hard real-time applications, we shed light on the difficulties of this unified research effort, but also show how it can lead to real advances. Indeed we explain how adapting techniques for the optimization of new objectives, in a different context, allows us to develop more easily systems of better quality than what was done until now. In this adaptation process, we propose to use synchronous formalisms and languages as a common formal ground. These can be naturally seen as extensions of classical models coming from both real-time scheduling (dependent task graphs) and compilation (single static assignment and data dependency graphs), but also provide powerful techniques for manipulating complex control structures. We implemented our results in the LoPhT compiler.

La Radio Logicielle (SDR : Software Defined Radio) et la Radio Cognitive (CR : Cognitive Radio) deviennent d'un usage courant car elles répondent à plusieurs enjeux technico-économiques majeurs dans le domaine des télécommunications. Ces systèmes radio permettent de combler l'écart de développement technologique qui existe entre la partie matérielle et la partie logicielle des systèmes de communication, en permettant la gestion optimale des bandes de fréquences sous-utilisées par la commutation en temps réel d'une configuration radio à une autre. Dans ce cadre, cette thèse présente la mise en œuvre d'une chaîne de traitements Radio Logicielle (appelée SDR waveform) dans un Système Multiprocesseurs sur Puce (MPSoC) à usage général (implémenté dans un FPGA de type Xilinx Virtex-4). Cette plateforme est basée autour d'un Réseau sur Puce (NoC) interconnectant 16 processeurs élémentaires (appelés PE) disposant de quatre blocs-mémoires externes DDR2. Nous avons proposé des implémentations temps réel et embarquées sur MPSoC de différentes briques de traitements d'une chaîne SDR, en concevant une stratégie efficace de parallélisation et de synchronisation pour chaque composante élémentaire de la « waveform ». Nous avons amélioré la fonctionnalité de la chaîne de traitement Radio Logicielle, en intégrant un Transceiver reconfigurable basé sur différents modèles de Réseaux de Neurones Artificiels (RNA) : les Cartes Auto-Organisatrices (SOM), les Réseaux de Neurones Compétitifs (LVQ) et enfin les Réseaux Multi-Couches de Perceptrons (MLP). Ces trois RNA permettent la reconnaissance de la norme spécifique basée sur les paramètres d'entrée extraits du signal et la reconfiguration du Transceiver de CR. La solution adaptative que nous avons proposée commute vers le RNA le plus approprié en fonction des caractéristiques du signal d'entrée détecté. Il est important de pouvoir prendre en compte des signaux complexes et multi-porteuses. Dans ce cadre, nous avons adressé le cas d'un signal complexe composé de plusieurs porteuses, ainsi en divisant les PEs en différents groupes indépendants, nous affectons chaque groupe de PEs au traitement d'une nouvelle porteuse. Nous avons conçu une stratégie efficace de synchronisation et de parallélisation de ces trois RNA pour CR Transceiver. Nous l'avons appliquée, par la suite pour l'implantation de nos algorithmes sur le MPSoC déjà cité. L'accélération que nous obtenons pour la SDR waveform et pour les algorithmes de Transceiver de CR démontre que les MPSoC à usage général sont une réponse pertinente, entre autres, aux contraintes de performances sur une telle plateforme. Le système que nous proposons apporte une réponse aux défis technico-économiques des grandes entreprises qui investissent ou prévoient d'investir dans des équipements basés sur des SDR ou des CR, puisqu'il permet d'éviter de recourir à des équipements d'accélération coûteux. Nous avons, par la suite, ajouté d'autres fonctionnalités à notre waveform avec un « CR Transceiver multinormes », en proposant une nouvelle approche pour la gestion du spectre radio. Ceci étant l'aspect le plus important de CR. Nous rendons ainsi notre waveform spectralement efficace en modélisant les caractéristiques radiofréquences (RF) du signal utilisateur primaire sous la forme d'une série temporelle multi-variée. Cette série temporelle est ensuite fournie comme entrée dans un Réseau de Neurones Récurrent d'Elman (ERNN) qui prédit l'évolution de la série temporelle de RF pour déterminer si l'utilisateur secondaire peut exploiter la bande de fréquences. Nous avons exploité la cyclo-stationnarité inhérente des signaux primaires pour la Modélisation Non-Linéaire Autorégressive Exogène (NARX : Non-linear AutoRegressive Exogenous) des séries temporelles des caractéristiques RF, car la prédiction d'une caractéristique RF demande d'abord de connaître les autres caractéristiques radios pertinentes. Nous avons observé une tendance similaire pour les valeurs prédites et observées. En résumé, nous avons proposé des algorithmes pour SDR waveform à efficacité spectrale avec un Transceiver Universel, ainsi que leurs implantations parallèles sur MPSoC. Notre conception de waveform répond aux exigences en performances et aux contraintes de ressources embarquées des applications dans le domaine / Software Defined Radio (SDR) and Cognitive Radio (CR) are entering mainstream. These high performance and high adaptability requiring devices with agile frequency operations hold promise to :1. address the inconsistency between hardware and software advancements, 2. real time mode switching from one radio configuration to another and3. efficient spectrum management in under-utilized spectrum bands. Framed within this statement, in this thesis we have implemented a SDR waveform on 16 Processing Element (PE) Network on chip (NoC) based general purpose Multiprocessors System on chip (MPSoC), with access to four external DDR2 memory banks, which is implemented on a single chip Xilinx Virtex-4 FPGA. We shifted short term development of a waveform into software domain by designing an efficient parallelization and synchronization strategy for each waveform component, individually. We enhance our designed waveform functionality by proposing and implementing three Artificial Neural Networks Schemes : Self Organizing Maps, Linear Vector Quantization and Multi-Layer Perceptrons as effective techniques for reconfiguring CR Transceiver after recognizing the specific standard based on input parameters, pertaining to different layers, extracted from the signal. Our proposed adaptive solution switches to appropriate Artificial Neural Network, based on the features of input signal sensed. We designed an efficient synchronization and parallelization strategy to implement the Artificial Neural Networks based CR Transceiver Algorithms on the aforementioned MPSoC chip. The speed up we obtained for our SDR waveform and CR Transceiver algorithms demonstrated that the general purpose MPSoC devices are the most efficient answer to the acquisition challenge for major organizations that invest or plan to invest in SDR and CR based devices, thereby allowing us to avoid expensive hardware accelerators. We address the case of a complex signal composed of many modulated carriers by dividing the PEs in individual groups, thus received signal with more than one Standard is processed efficiently. We add further functionality in our designed Multi-standard CR Transceiver possessing SDR Waveform by proposing a new approach for radio spectrum management, perhaps the most important aspect of CR. We make our designed waveform Spectrum efficient by modelling the primary user signal Radio Frequency features as a multivariate time series, which is then given as input to Elman Recurrent Neural Network that predicts the evolution of Radio Frequency Time Series to decide if the secondary user can exploit the Spectrum band. We exploit the inherent cyclostationary in primary signals for Non-linear Autoregressive Exogenous Time Series Modeling of Radio Frequency features, as predicting one RF feature needs the previous knowledge of other relevant RF features. We observe a similar trend between predicted and actual values. Ensemble, our designed Spectrum Efficient SDR waveform with a Universal Multi-standard Transceiver answers the SDR and CR performance requirements under resource constraints by efficient algorithm design and implementation using lateral thinking that seeks a greater cross-domain interaction

Les applications de simulation numérique nécessitant la résolution de problèmes d'Équations aux Dérivées Partielles (EDP) sont souvent parallélisées à l'aide d'une méthode de décomposition de domaine. Ces méthodes mathématiques sont naturellement ouvertes au parallélisme, cependant leur exploitation efficace sur les machines parallèles devient difficile lorsque les applications ont un comportement irrégulier. C'est le cas par exemple lorsque les problèmes mathématiques sont résolus dans des domaines géométriques complexes ou lorsque l'on utilise des techniques d'adaptation de maillage. Une technique de programmation se prêtant bien à la mise en oeuvre d'applications irrégulières est la multiprogrammation basée sur des réseaux de processus légers communicants. Dans cette thèse nous réalisons une étude approfondie de l'apport de ce paradigme de programmation à la résolution de problèmes d'EDP par des méthodes de décomposition de domaine et nous montrons qu'il existe une écriture algorithmique générique de celles-ci. Une de nos principales contributions réside dans la conception et réalisation d'un harnais informatique, appelé Ahpik, permettant une programmation aisée d'applications reposant sur les méthodes de décomposition de domaine. Ce harnais fournit un support générique adaptable à de nombreuses méthodes mathématiques, qu'elles soient synchrones ou asynchrones, avec ou sans recouvrement. Une conception orientée objet permet d'encapsuler les détails de gestion des processus légers et des communications, ce qui facilite l'implantation de nouvelles méthodes. Nous avons utilisé l'environnement Ahpik dans le cadre de la résolution de problèmes d'EDP classiques et notamment pour un problème en mécanique de fluides de grande taille.

L'évolution de la technologie VLSI permet aux systèmes sur puce (SoCs) d'intégrer de nombreuses fonctions hétérogènes dans une seule puce et demande, en raison de contraintes économiques, une unique mémoire externe partagée (SDRAM). Par conséquent, la conception du système de mémoire principale, et plus particulièrement l'architecture du contrôleur de mémoire, est devenu un facteur très important dans la détermination de la performance globale du système. Le choix d'un contrôleur de mémoire qui répond aux besoins de l'ensemble du système est une question complexe. Cela nécessite l'exploration de l'architecture du contrôleur de mémoire, puis la validation de chaque configuration par simulation. Bien que l'exploration de l'architecture du contrôleur de mémoire soit un facteur clé pour une conception réussite d'un système, l'état de l'art sur les contrôleurs de mémoire ne présente pas des architectures aussi flexibles que nécessaire pour cette tâche. Même si certaines d'entre elles sont configurables, l'exploration est restreinte à des ensembles limités de paramètres tels que la profondeur des tampons, la taille du bus de données, le niveau de la qualité de service et la distribution de la bande passante. Plusieurs classes de trafic coexistent dans les applications réelles, comme le trafic de service au mieux et le trafic de service garanti qui accèdent à la mémoire partagée d'une manière concurrente. En conséquence, la considération de l'interaction entre le système de mémoire et la structur d'interconnexion est devenue vitale dans les SoCs actuels. Beaucoup de réseaux sur puce (NoCs) fournissent des services aux classes de trafic pour répondre aux exigences des applications. Cependant, très peu d'études considèrent l'accès à la SDRAM avec une approche système, et prennent en compte la spécificité de l'accès à la SDRAM dans les systèmes sur puce à base de réseaux intégrés. Cette thèse aborde le sujet de l'accès à la mémoire dynamique SDRAM dans les systèmes sur puce à base de réseaux intégrés. Nous introduisons une architecture de contrôleur de mémoire totalement configurable basée sur des blocs fonctionnels configurables, et proposons un modèle de simulation associé relativement précis temporellement et à haut niveau d'abstraction. Ceci permet l'exploration du sous-système de mémoire grâce à la facilité de configuration de l'architecture du contrôleur de mémoire. En raison de la discontinuité de services entre le réseau sur puce et le contrôleur de mémoire, nous proposons également dans le cadre de cette thèse un protocole de contrôle de flux de bout en bout pour accéder à la mémoire à travers un contrôleur de mémoire multiports. L'idée, simple sur le principe mais novatrice car jamais proposée à notre connaissance, se base sur l'exploitation des informations sur l'état du contrôleur de mémoire dans le réseau intégré. Les résultats expérimentaux montrent qu'en contrôlant l'injection du trafic de service au mieux dans le réseau intégré, notre protocole augmente les performances du trafic de service garanti en termes de bande passante et de latence, tout en préservant la bande passante moyenne du trafic de service au mieux.