Bien que le développement actuel d'accélérateurs se concentre principalement sur la création de puces Multiprocesseurs (MPSoC) hétérogènes, c'est-à-dire composés de processeurs spécialisées, de nombreux acteurs de la microélectronique s'intéressent au développement d'un autre type de MPSoC, constitué d'une grille de processeurs identiques. Ces MPSoC homogènes, bien que composés de processeurs énergétiquement moins efficaces, possèdent une programmabilité et une flexibilité plus importante que les MPSoC hétérogènes, ce qui favorise notamment l'adaptation du système à la charge demandée, et offre un espace de solutions de configuration potentiellement plus vaste et plus simple à contrôler. C'est dans ce contexte que s'inscrit cette thèse, en exposant la création d'une architecture MPSoC homogène scalable (c'est-à-dire dont la mise à l'échelle des performances est linéaire), ainsi que le développement de différents systèmes d'adaptation et de programmation sur celle-ci.Cette architecture, constituée d'une grille de processeurs de type MicroBlaze, possédant chacun sa propre mémoire, au sein d'un Réseau sur Puce 2D, a été développée conjointement avec un système d'exploitation temps réel (RTOS) spécialisé et modulaire. Grâce à la création d'une pile de communication complexe, plusieurs mécanismes d'adaptation ont été mis en œuvre : une migration de tâche « avec redirection de données », permettant de diminuer l'impact de cette migration avec des applications de type flux de données, ainsi qu'un mécanisme dit « d'exécution distante ». Ce dernier consiste non plus à migrer le code instruction d'une mémoire à une autre, mais de conserver le code dans sa mémoire initiale et de le faire exécuter par un processeur distinct. Les différentes expériences réalisées avec ce mécanisme ont permis de souligner la meilleure réactivité de celui-ci face à la migration de tâche, tout en possédant des performances d'adaptation plus faible.Ce dernier mécanisme a conduit naturellement à la création d'un modèle de programmation de type « mémoire partagée » au sein de l'architecture. La mise en place de ce dernier nécessitait la création d'un mécanisme de cohérence mémoire, qui a été réalisé de façon matérielle/logicielle et scalable par l'intermédiaire du développement de la librairie PThread. Les performances ainsi obtenues mettent en évidence les avantages d'un MPSoC homogène tout en utilisant une programmation « classique » de type multiprocesseur. / Although the accelerators market is dominated by heterogeneous MultiProcessor Systems-on-Chip (MPSoC), i.e. with different specialized processors, a growing interest is put on another type of MPSoC, composed by an array of identical processors. Even if these processors achieved lower performance to power ratio, the better flexibility and programmability of these homogeneous MPSoC allow an easier adaptation to the load, and offer a wider space of configurations. In this context, this thesis exposes the development of a scalable homogeneous MPSoC – i.e. with linear performance scaling – and different kind of adaptive mechanisms and programming model on it.This architecture is based on an array of MicroBlaze-like processors, each having its own memory, and connected through a 2D NoC. A modular RTOS was build on top of it. Thanks to a complex communication stack, different adaptive mechanisms were made: a “redirected data” task migration mechanism, reducing the impact of the migration mechanism for data-flow applications, and a “remote execution” mechanism. Instead of migrate the instruction code from a memory to another, this last consists in only migrate the execution, keeping the code in its initial memory. The different experiments shows faster reactivity but lower performance of this mechanism compared to migration.This development naturally led to the creation of a shared memory programming model. To achieve this, a scalable hardware/software memory consistency and cache coherency mechanism has been made, through the PThread library development. Experiments show the advantage of using NoC based homogeneous MPSoC with a brand programming model.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse est consacrée a l'étude de l'implantation du langage Prolog sur les architectures parallèles Mimd sans mémoire commune. Nous présentons le modèle opéra qui exploite implicitement le parallélisme ou le Prolog pour repartir dynamiquement l'évaluation des programmes sur les différents nœuds du réseau de processeurs. Le système opéra est de type multisequentiel: il n'y a parallélisation que lorsqu'un processeur est inoccupé. Ce système se décompose en une partie operative chargée de l'évaluation du programme Prolog, et une partie contrôle chargée de l'allocation des travaux aux processeurs de la partie operative. Les principaux problèmes de ce type de systèmes sont d'une part le choix de représentation en mémoire de l'arbre ou ainsi que la gestion des liaisons multiples, et d'autre part, le contrôle de l'allocation des différentes branches de l'arbre aux machines abstraites qui effectuent des évaluations séquentielles. La technique de régulation de charge utilisée est fondée sur des méthodes heuristiques. L'ordonnanceur d'opera travaille sur une image approchée de l'état global du système obtenu par échantillonnage des états locaux de chaque unités de travail. Un prototype d'opera a été réalisé sur un réseau de transputers reconfigurable dynamiquement: le supernode. Cette propriété a ete mise a profit dans notre implantation pour réduire les couts de communication. Les communications sont effectuées en parallèle avec le calcul. Le prototype réalisé fournit des gains de performances importants et opera figure parmi les systèmes Prolog parallèles les plus efficaces a l'heure actuelle

La conception de prototypes de systèmes de vision en temps réel embarqué est sujet à de multiples contraintes sévères et fortement contradictoires. Dans le cas de capteurs dits "intelligents", il est nécessaire de fournir une puissance de traitement suffisante pour exécuter les algorithmes à la cadence des capteurs d'images avec un dispositif de taille minimale et consommant peu d'énergie. La conception d'un système monopuce (ou SoC) et l'implantation d'algorithmes de plus en plus complexes pose problème si on veut l'associer avec une approche de prototypage rapide d'applications scientifiques. Afin de réduire de manière significative le temps et les différents coûts de conception, le procédé de conception est fortement automatisé. La conception matérielle est basée sur la dérivation d'un modèle d'architecture multiprocesseur générique de manière à répondre aux besoins de capacité de traitement et de communication spécifiques à l'application visée. Les principales étapes manuelles se réduisent au choix et au paramétrage des différents composants matériels synthétisables disponibles. La conception logicielle consiste en la parallélisation des algorithmes, qui est facilitée par l'homogénéité et la régularité de l'architecture de traitement parallèle et la possibilité d'employer des outils d'aide à la parallélisation. Avec l'approche de conception sont présentés les premiers éléments constitutifs qui permettent de la mettre en oeuvre.Ceux ci portent essentiellement sur les aspects de conception matérielle. L'approche proposée est illustrée par l'implantation d'un traitement de stabilisation temps réel vidéo sur technologie SoPC

Nous étudions la mise en œuvre d'algorithmes parallèles sur des ordinateurs a mémoire distribuée. A travers plusieurs exemples issus de la programmation dynamique, de l'algèbre linéaire et du traitement d'images, nous exposons les problèmes lies a la programmation de ces machines: topologie d'interconnexion, stratégie d'allocation des données, équilibrage des calculs et minimisation du volume de communication inter-processeurs. Les exemples étudiés sont pour la plupart des algorithmes séquentiels couteux en temps de calcul et en place mémoire, et pour lesquels il est très intéressant d'avoir une parallélisation efficace. Nous avons choisi des problèmes dont l'implémentation sur des machines a mémoire distribuée n'est pas aisée, essentiellement a cause de la grande interdépendance entre les différentes taches composant les algorithmes

Les architectures parallèles hybrides constituées d'un grand nombre de noeuds de calcul multi-coeurs/GPU connectés en réseau offrent des performances théoriques très élevées, de l'ordre de quelque dizaines de TeraFlops. Mais la programmation efficace de ces machines reste un défi à cause de la complexité de l'architecture et de la multiplication des modèles de programmation utilisés. L'objectif de cette thèse est d'améliorer la programmation des applications scientifiques denses sur les architectures parallèles hybrides selon trois axes: réduction des temps d'exécution, traitement de données de très grande taille et facilité de programmation. Nous avons pour cela proposé un modèle de programmation à base de directives appelé DSTEP pour exprimer à la fois la distribution des données et des calculs. Dans ce modèle, plusieurs types de distribution de données sont exprimables de façon unifiée à l'aide d'une directive "dstep distribute" et une réplication de certains éléments distribués peut être exprimée par un "halo". La directive "dstep gridify" exprime à la fois la distribution des calculs ainsi que leurs contraintes d'ordonnancement. Nous avons ensuite défini un modèle de distribution et montré la correction de la transformation de code du domaine séquentiel au domaine distribué. À partir du modèle de distribution, nous avons dérivé un schéma de compilation pour la transformation de programmes annotés de directives DSTEP en des programmes parallèles hybrides. Nous avons implémenté notre solution sous la forme d'un compilateur intégré à la plateforme de compilation PIPS ainsi qu'une bibliothèque fournissant les fonctionnalités du support d'exécution, notamment les communications. Notre solution a été validée sur des programmes de calcul scientifiques standards tirés des NAS Parallel Benchmarks et des Polybenchs ainsi que sur une application industrielle. / Clusters of multicore/GPU nodes connected with a fast network offer very high therotical peak performances, reaching tens of TeraFlops. Unfortunately, the efficient programing of such architectures remains challenging because of their complexity and the diversity of the existing programming models. The purpose of this thesis is to improve the programmability of dense scientific applications on hybrid architectures in three ways: reducing the execution times, processing larger data sets and reducing the programming effort. We propose DSTEP, a directive-based programming model expressing both data and computation distribution. A large set of distribution types are unified in a "dstep distribute" directive and the replication of some distributed elements can be expressed using a "halo". The "dstep gridify" directive expresses both the computation distribution and the schedule constraints of loop iterations. We define a distribution model and demonstrate the correctness of the code transformation from the sequential domain to the parallel domain. From the distribution model, we derive a generic compilation scheme transforming DSTEP annotated input programs into parallel hybrid ones. We have implemented such a tool as a compiler integrated to the PIPS compilation workbench together with a library offering the runtime functionality, especially the communication. Our solution is validated on scientific programs from the NAS Parallel Benchmarks and the PolyBenchs as well as on an industrial signal procesing application.

La physique actuelle cherche, à côté des expériences, à vérifier et déduire les lois de la nature en simulant les modèles physiques sur d'énormes ordinateurs. Cette thèse explore comment accélérer ces simulations en améliorant les programmes qui les font tourner. L'application de référence est la chromodynamique quantique sur réseaux (LQCD pour "Lattice Quantum Chromodynamics"), une branche de la théorie quantique des champs, tournant sur le plus récent des supercalculateurs d'IBM, le Blue Gene/Q.Dans un premier temps, on améliore le code source de tmLQCD, un programme de LQCD, dont l'opération clef pour la performance est un stencil à 8 points en dimension 4. On étudie deux stratégies d'optimisation différentes: la première se donne comme priorité d'améliorer la localité spatiale et temporelle; la seconde utilise le préchargement matériel de flux de données. Sur le Blue Gene/Q, la première stratégie permet d'atteindre 20% de la performance crête théorique. La seconde, avec jusqu'à 54% de la performance crête est bien meilleure mais utilise 4 fois plus de mémoire car elle stocke les résultats dans l'ordre où les utilise le stencil suivant, ce qui requiert de dupliquer des données. Les autres techniques exploitées sont la programmation directe du système de communication (appelé MUSPI chez IBM), un mécanisme allégé de gestion des threads, le préchargement explicite de certaines données (à l'aide de l'instruction dcbt) et la vectorisation manuelle (en utilisant les instructions SIMD de largeur 4; appelé QPX par IBM). Le préchargement de liste et la mémoire transactionnelle - deux nouveaux mécanismes du Blue Gene/Q - n'améliorent pas les performances.Dans un second temps, on présente la réalisation d'une extension appelé Molly au compilateur LLVM, pour optimiser automatiquement le programme, et plus précisément la distribution des données et des calculs entre les nœuds d'un cluster tel que le Blue Gene/Q. Molly représente les tableaux par des polyèdres entiers et utilise l'extension existante Polly qui représente les boucles et les instructions par des polyèdres. Partant de la spécification de la distribution des données et de l'emplacement des calculs, Molly ajoute le code qui gère les flots de données entre les nœuds de calcul. Molly peut aussi permuter l'ordre des données en mémoire. La tâche principale de Molly est d'agréger les données dans des ensembles qui sont envoyés dans le même tampon au même destinataire, pour éviter l'overhead des transferts trop petits. Nous présentons un algorithme qui minimise le nombre de transferts pour des boucles non-paramétrées, basé sur les antichaînes du flot des données. De plus, nous implémentons une heuristique qui tient compte de la manière dont le programmeur a écrit son code. Les primitives de communication asynchrone sont insérées juste après que les données soient disponibles - respectivement juste avant qu'elles soient utilisées. Une bibliothèque runtime implémente ces primitives en utilisant MPI. Molly gère la distribution pour tout code représentable dans le modèle polyédrique, mais fonctionne mieux pour du code à stencil tel LQCD. Compilé avec Molly, le code LQCD atteint 2,5% de la performance crête. L'écart de performance est surtout dû au fait que les autres optimisations ne sont pas faites, par exemple la vectorisation. Les versions futures de Molly pourraient aussi gérer efficacement les codes non à stencil et exploiter les autres optimisations qui ont rendu le code LQCD optimisé à la main si rapide. / Motivated by modern day physics which in addition to experiments also tries to verify and deduce laws of nature by simulating the state-of-the-art physical models using oversized computers, this thesis explores means of accelerating such simulations by improving the simulation programs they run. The primary focus is Lattice Quantum Chromodynamics (QCD), a branch of quantum field theory, running on IBM newest supercomputer, the Blue Gene/Q.In a first approach, the source code of tmLQCD, a Lattice QCD program, is improved to run faster on the Blue Gene machine. Its most performance-relevant operation is a 8-point stencil in 4 dimensional space. Two different optimization strategies are perused: One with the priority of improving spatial and temporal locality, and a second making use of the hardware's data stream prefetcher. On Blue Gene/Q the first strategy reaches up to 20% of the peak theoretical floating point operation performance of that machine. The second strategy with up to 54% of peak is much faster at the cost of using 4 times more memory by storing the data in the order they will be used in the next stencil operation, duplicating data where necessary.Other techniques exploited are direct programming of the messaging hardware (called MUSPI by IBM), a low-overhead work distribution mechanism for threads, explicit data prefetching of data (using dcbt instruction) and manual vectorization (using QPX; width-4 SIMD instructions). Hardware-based list prefetching and transactional memory - both distinct and novel features of the Blue Gene/Q system -- did not improve the program's performance.The second approach is the newly-written LLVM compiler extension called Molly which optimizes the program itself, specifically the distribution of data and work between the nodes of a cluster machine such as Blue Gene/Q. Molly represents arrays using integer polyhedra and uses another already existing compiler extension Polly which represents statements and loops using polyhedra. When Molly knows how data is distributed among the nodes and where statements are executed, it adds code that manages the data flow between the nodes. Molly can also permute the order of data in memory. Molly's main task is to cluster data into sets that are sent to the same target into the same buffer because single transfers involve a massive overhead. We present an algorithm that minimizes the number of transfers for unparametrized loops using anti-chains of data flows. In addition, we implement a heuristic that takes into account how the programmer wrote the code. Asynchronous communication primitives are inserted right after the data is available respectively just before it is used. A runtime library implements these primitives using MPI.Molly manages to distribute any code that is representable by the polyhedral model, but does so best for stencils codes such as Lattice QCD. Compiled using Molly, the Lattice QCD stencil reaches 2.5% of the theoretical peak performance. The performance gap is mostly because all the other optimizations are missing, such as vectorization. Future versions of Molly may also effectively handle non-stencil codes and use make use of all the optimizations that make the manually optimized Lattice QCD stencil so fast.

Cette thèse porte sur le partitionnement parallèle de graphes et essentiellement sur son application à la renumérotation de matrices creuses.<br />Nous utilisons pour résoudre ce problème un schéma multi-niveaux dont nous avons parallélisé les phases de contraction et d'expansion.<br />Nous avons ainsi introduit pour la phase de contraction un nouvel algorithme de gestion des conflits d'appariements distants, tout en améliorant les algorithmes déjà existants en leur associant une phase de sélection des communications les plus utiles.<br />Concernant la phase de d'expansion, nous avons introduit la notion de graphe bande qui permet de diminuer de manière très conséquente la taille du problème à traiter par les algorithmes de raffinement. Nous avons généralisé l'utilisation de ce graphe bande aux implantations séquentielles et parallèles de notre outil de partitionnement Scotch.<br />Grâce à la présence du graphe bande, nous avons proposé une utilisation nouvelle des algorithmes génétiques dans le cadre de l'expansion en les utilisant comme heuristiques parallèles de raffinement de la partition.

Différents résultats de complexité sont présentés pour les communications et le calcul sur des machines à mémoire distribuée. Les topologies concernées sont le réseau linéaire, l'anneau, la grille, l'hypercube et le réseau complet. Un réseau systolique est présenté pour l'algorithme de diagonalisation de Jordan. Une étude sur l'accélération et une étude de l'allocation des données sont formulées dans le contexte des mémoires distribuées

Cette thèse porte sur le partitionnement parallèle de graphes et essentiellement sur son application à la renumérotation de matrices<br />creuses.<br /><br />Nous utilisons pour résoudre ce problème un schéma multi-niveaux dont nous avons parallélisé les phases de contraction et d'expansion.<br /><br />Nous avons ainsi introduit pour la phase de contraction un nouvel algorithme de gestion des conflits d'appariements distants, tout en<br />améliorant les algorithmes déjà existants en leur associant une phase<br />de sélection des communications les plus utiles.<br /><br />Concernant la phase d'expansion, nous avons introduit la notion de graphe bande qui permet de diminuer de manière très conséquente la taille du problème à traiter par les algorithmes de raffinement. Nous avons généralisé l'utilisation de ce graphe bande aux implantations séquentielles et parallèles de notre outil de partitionnement Scotch.<br /><br />Grâce à la présence du graphe bande, nous avons proposé une utilisation nouvelle des algorithmes génétiques dans le cadre de<br />l'expansion en les utilisant comme heuristiques parallèles de raffinement de la partition.