Initialement con¸cu pour d'echarger le CPU des tˆaches de rendu graphique, le GPU estdevenu une architecture massivement parall'ele adapt'ee au traitement de donn'ees volumineuses.Alors qu'il occupe une part de march'e importante dans le Calcul Haute Performance, uned'emarche d'Ad'equation Algorithme Architecture est n'eanmoins requise pour impl'ementerefficacement un algorithme sur GPU.La contribution de cette th'ese est double. Dans un premier temps, nous pr'esentons legain significatif apport'e par l'impl'ementation optimis'ee d'un algorithme de granulom'etrie(l'ordre de grandeur passe de l'heure 'a la minute pour un volume de 10243 voxels). Un mod'eleanalytique permettant d''etablir les variations de performance de l'application de granulom'etriesur GPU a 'egalement 'et'e d'efini et pourrait ˆetre 'etendu 'a d'autres algorithmes r'eguliers.Dans un second temps, un outil facilitant le d'eploiement d'applications de Traitementdu Signal et de l'Image sur cluster multi-GPU a 'et'e d'evelopp'e. Pour cela, le champ d'actiondu programmeur est r'eduit au d'ecoupage du programme en tˆaches et 'a leur mapping sur les'el'ements de calcul (GPP ou GPU). L'am'elioration notable du d'ebit sortant d'une applicationstreaming de calcul de carte de saillence visuelle a d'emontr'e l'efficacit'e de notre outil pourl'impl'ementation d'une solution sur cluster multi-GPU. Afin de permettre un 'equilibrage decharge dynamique, une m'ethode de migration de tˆaches a 'egalement 'et'e incorpor'ee 'a l'outil.

En dépit du succès que les implantations optiques des applications de traitement d'images ont connu, le traitement optique de l'information suscite aujourd'hui moins d'intérêt que dans les années 80-90. Ceci est dû à l'encombrement des réalisations optiques, la qualité des images traitées et le coût des composants optiques. De plus, les réalisations optiques ont eu du mal à s'affranchir de l'avènement des circuits numériques. C'est dans ce cadre que s'inscrivent les travaux de cette thèse dont l'objectif est de proposer une implantation numérique des méthodes optiques de traitement d'images. Pour réaliser cette implantation nous avons choisi d'utiliser les FPGA et les GPU grâce aux bonnes performances de ces circuits en termes de rapidité. En outre, pour améliorer la productivité nous nous sommes focalisés à la réutilisation des blocs préconçus ou IP " Intellectual Properties ". Malgré que les IP commerciales existantes soient optimisées, ces dernières sont souvent payantes et dépendent de la famille de la carte utilisée. La première contribution est de proposer une implantation optimisée des IP pour le calcul de la transformée de Fourier FFT et de la DCT. En effet, le choix de ces deux transformations est justifié par l'utilisation massive de ces deux transformées (FFT et DCT), dans les algorithmes de reconnaissance de formes et de compression, respectivement. La deuxième contribution est de valider le fonctionnement des IP proposées par un banc de test et de mesure. Enfin, la troisième contribution est de concevoir sur FPGA et GPU des implantations numériques des applications de reconnaissance de formes et de compression. Un des résultats probant obtenu dans cette thèse consiste à avoir une rapidité de l'IP FFT proposée 3 fois meilleure que celle de l'IP FFT Xilinx et de pouvoir réaliser 4700 corrélations par seconde.

Afin de créer des productions toujours plus réalistes, les industries du jeu vidéo et du cinéma cherchent à générer des environnements de plus en plus larges et complexes. Cependant, la modélisation manuelle des objets 3D dans de tels décors se révèle très coûteuse. A l'inverse, les méthodes de génération procédurale permettent de créer facilement une grande variété d'objets, tels que les plantes et les bâtiments. La modélisation par règles de grammaire offre un outil de haut niveau pour décrire ces objets, mais utiliser correctement ces règles s'avère très souvent compliqué. De plus, aucune solution de modélisation basée grammaire ne supporte l'édition et la visualisation d'environnements massifs en temps interactif. Dans un tel scénario, les artistes doivent modifier les objets en dehors de la scène avant de voir le résultat intégré. Dans ces travaux de recherche, nous nous intéressons à la génération procédurale et au rendu d'environnements à grande échelle. Nous voulons aussi faciliter la tâche des artistes avec des outils intuitifs de contrôle de grammaires. Tout d'abord nous proposons un système permettant la génération procédurale en parallèle sur le GPU en temps interactif. Pour cela, nous adoptons une approche d'expansion indépendante par segment, permettant une amplification des données en parallèle. Nous étendons ce système pour générer des modèles basés sur une structure interne, tels que les toits. Nous présentons aussi une solution utilisant des contextes externes pour contrôler facilement les grammaires par le biais de surface ou de texture. Pour finir nous intégrons un système de niveaux de détails et des techniques d'optimisation permettant la génération, l'édition et la visualisation interactives d'environnements à grande échelle. Grâce à notre système il est possible de générer et d'afficher interactivement des scènes comprenant des milliers de bâtiments et d'arbres, représentant environ 2 teraoctets de données.

Ce mémoire présente un système de localisation par vision pour un robot mobile circulant dans un milieu urbain. Pour cela, une première phase d'apprentissage où le robot est conduit manuellement est réalisée pour enregistrer une séquence vidéo. Les images ainsi acquises sont ensuite utilisées dans une phase hors ligne pour construire une carte 3D de l'environnement. Par la suite, le véhicule peut se déplacer dans la zone, de manière autonome ou non, et l'image reçue par la caméra permet de le positionner dans la carte. Contrairement aux travaux précédents, la trajectoire suivie peut être différente de la trajectoire d'apprentissage. L'algorithme développé permet en effet de conserver la localisation malgré des changements de point de vue importants par rapport aux images acquises initialement. Le principe consiste à modéliser les points de repère sous forme de facettes localement planes, surnommées patchs plan, dont l'orientation est connue. Lorsque le véhicule se déplace, une prédiction de la position courante est réalisée et la déformation des facettes induite par le changement de point de vue est reproduite. De cette façon la recherche des amers revient à comparer des images pratiquement identiques, facilitant ainsi leur appariement. Lorsque les positions sur l'image de plusieurs amers sont connues, la connaissance de leur position 3D permet de déduire la position du robot. La transformation de ces patchs plan est complexe et demande un temps de calcul important, incompatible avec une utilisation temps-réel. Pour améliorer les performances de l'algorithme, la localisation a été implémentée sur une architecture GPU offrant de nombreux outils permettant d'utiliser cet algorithme avec des performances utilisables en temps-réel. Afin de prédire la position du robot de manière aussi précise que possible, un modèle de mouvement du robot a été mis en place. Il utilise, en plus de la caméra, les informations provenant des capteurs odométriques. Cela permet d'améliorer la prédiction et les expérimentations montrent que cela fournit une plus grande robustesse en cas de pertes d'images lors du traitement. Pour finir ce mémoire détaille les différentes performances de ce système à travers plusieurs expérimentations en conditions réelles. La précision de la position a été mesurée en comparant la localisation avec une référence enregistrée par un GPS différentiel.

Cette thèse se place dans le cadre de la synthèse d'images en temps réel. Le problème auquel elle s'attaque est celui du rendu efficace du détail visuel, principal élément du réalisme d'une image. Pour faire face à la complexité du détail visuel, il est nécessaire de disposer de représentations adaptées à la fois aux objets que l'on cherche à rendre ainsi qu'aux capacités des processeurs graphiques actuels. Le premier axe de recherche porte sur l'utilisation du relief pour représenter et rendre efficacement du détail géométrique. La représentation compacte et structurée du relief par une carte hauteur permet la conception d'algorithmes de rendu exacts et efficaces. Nous en proposons deux~: le premier permet de rendre des reliefs dynamiques, alors que le second s'adresse aux reliefs statiques en exploitant la possibilité d'effectuer un pré-traitement sur la carte de hauteur. Nous développons aussi une réflexion sur l'utilisation du relief pour la représentation de surfaces quelconques, et présentons une application au rendu réaliste et en temps réel de volumes d'eau. Le deuxième axe de recherche se concentre sur les représentations non surfaciques, nécessaires lorsque les représentations géométriques sont inadaptées voire inexistantes. C'est le cas notamment des objets lointains ou des objets à géométrie dense, comme par exemple le feuillage d'un arbre. Le problème ici est d'être capable de représenter l'apparence d'un objet, sans recourir à un modèle géométrique. Nous proposons une méthode permettant, à partir de la seule donnée du light-field d'un objet, de déterminer les paramètres optimaux d'une représentation adaptée pour le rendu.

The past decade has seen a transition of Graphics Processing Units (GPUs) from special purpose graphics processors, to general purpose computational accelerators. GPUs have been investigated to utilize their highly parallel architecture to accelerate the computation of the Transmission Line Matrix (TLM) methods in two and three dimensions. The design utilizes two GPU programming languages, Compute Unified Device Architecture (CUDA) and Open Computing Language (OpenCL), to code the TLM methods for NVIDIA GPUs. The GPU accelerated two-dimensional shunt node TLM method (2D-TLM) achieves 340 million nodes per second (MNodes/sec) of performance which is 25 times faster than a commercially available 2D-TLM solver. Initial attempts to adapt the three-dimensional Symmetrical Condensed Node (3D-SCN) TLM method resulted in a peak performance of 47 MNodes/sec or7 times in speed-up. Further efforts to improve the 3D-SCN TLM algorithm, as well as investigating advanced GPU optimization strategies resulted in performances accelerated to 530 MNodes/sec, or 120 times speed-up compared to a commercially available 3D-SCN TLM solver.

The past decade has seen a transition of Graphics Processing Units (GPUs) from special purpose graphics processors, to general purpose computational accelerators. GPUs have been investigated to utilize their highly parallel architecture to accelerate the computation of the Transmission Line Matrix (TLM) methods in two and three dimensions. The design utilizes two GPU programming languages, Compute Unified Device Architecture (CUDA) and Open Computing Language (OpenCL), to code the TLM methods for NVIDIA GPUs. The GPU accelerated two-dimensional shunt node TLM method (2D-TLM) achieves 340 million nodes per second (MNodes/sec) of performance which is 25 times faster than a commercially available 2D-TLM solver. Initial attempts to adapt the three-dimensional Symmetrical Condensed Node (3D-SCN) TLM method resulted in a peak performance of 47 MNodes/sec or7 times in speed-up. Further efforts to improve the 3D-SCN TLM algorithm, as well as investigating advanced GPU optimization strategies resulted in performances accelerated to 530 MNodes/sec, or 120 times speed-up compared to a commercially available 3D-SCN TLM solver.

Multi-core processors have become the dominant processor architecture with 2, 4, and 8 cores on a chip being widely available and an increasing number of cores predicted for the future. In addition, the decreasing costs and increasing programmability of Graphic Processing Units (GPUs) have made these an accessible source of parallel processing power in general purpose computing. Among the many research challenges that this scenario has raised are the fundamental problems related to theoretical modeling of computation in these architectures. In this thesis we study several aspects of computation in modern parallel architectures, from modeling of computation in multi-cores and heterogeneous platforms, to multi-core cache management strategies, through the proposal of an architecture that exploits bit-parallelism on thousands of bits. Observing that in practice multi-cores have a small number of cores, we propose a model for low-degree parallelism for these architectures. We argue that assuming a small number of processors (logarithmic in a problem's input size) simplifies the design of parallel algorithms. We show that in this model a large class of divide-and-conquer and dynamic programming algorithms can be parallelized with simple modifications to sequential programs, while achieving optimal parallel speedups. We further explore low-degree-parallelism in computation, providing evidence of fundamental differences in practice and theory between systems with a sublinear and linear number of processors, and suggesting a sharp theoretical gap between the classes of problems that are efficiently parallelizable in each case. Efficient strategies to manage shared caches play a crucial role in multi-core performance. We propose a model for paging in multi-core shared caches, which extends classical paging to a setting in which several threads share the cache. We show that in this setting traditional cache management policies perform poorly, and that any effective strategy must partition the cache among threads, with a partition that adapts dynamically to the demands of each thread. Inspired by the shared cache setting, we introduce the minimum cache usage problem, an extension to classical sequential paging in which algorithms must account for the amount of cache they use. This cache-aware model seeks algorithms with good performance in terms of faults and the amount of cache used, and has applications in energy efficient caching and in shared cache scenarios. The wide availability of GPUs has added to the parallel power of multi-cores, however, most applications underutilize the available resources. We propose a model for hybrid computation in heterogeneous systems with multi-cores and GPU, and describe strategies for generic parallelization and efficient scheduling of a large class of divide-and-conquer algorithms. Lastly, we introduce the Ultra-Wide Word architecture and model, an extension of the word-RAM model, that allows for constant time operations on thousands of bits in parallel. We show that a large class of existing algorithms can be implemented in the Ultra-Wide Word model, achieving speedups comparable to those of multi-threaded computations, while avoiding the more difficult aspects of parallel programming.

Les machines multicœurs équipées d'accélérateurs deviennent de plus en plus populaires dans le domaine du Calcul Haute Performance. Les architectures hybrides réduisent la consommation énergétique de manière significative et sont donc amenées à se généraliser dans l'ère du manycœur. Cependant, la complexité induite par ces architectures a un impact direct sur leur programmabilité. Il est donc indispensable de fournir des abstractions portables afin de tirer pleinement parti de ces machines. Les approches qui consistent à exécuter une application sur des processeurs généralistes et à ne déporter que certaines parties prédéterminées du calcul sur des accélérateurs ne sont pas suffisantes. Le véritable défi consiste donc à concevoir des environnements où les applications sont réparties sur l'intégralité de la machine, c'est-à-dire où les différents calculs sont ordonnancés dynamiquement sur la totalité des unités de calcul disponibles. Dans cette thèse, nous proposons donc un nouveau modèle de support exécutif fondé sur une abstraction de tâche et spécifiquement conçu pour répondre aux nombreux défis en termes d'ordonnancement de tâches et de gestion de données. La plate-forme StarPU a été conçue lors de cette thèse afin de démontrer la pertinence de ce modèle. StarPU propose une interface expressive permettant d'accéder à un ordonnancement flexible, fortement couplé à une gestion de données efficace. À l'aide de cet environnement et en associant les différentes tâches avec des modèles de performance auto-calibrés, il devient par exemple très simple de concevoir des stratégies d'ordonnancement prenant en compte les temps de calcul et les surcoûts liés aux mouvements de données. Nous montrons que notre modèle fondé sur un paradigme de tâche est suffisamment puissant pour exploiter les grappes de calcul d'une part, et les architectures manycœurs hybrides d'autre part. Nous analysons les performances obtenues non seulement grâce à des tests synthétiques, mais aussi à l'aide d'applications réelles. Nous obtenons ainsi des accélérations substantielles, ainsi qu'une très bonne efficacité parallèle sur différents types de plates-formes multicœurs, dotées d'accélérateurs.

The computational requirements of scientific research are constantly growing. In the field of radio astronomy, observations have evolved from using single telescopes, to interferometer arrays of many telescopes, and there are currently arrays of massive scale under development. These interferometers use signal and image processing to produce data that is useful to radio astronomy, and the amount of processing required scales quadratically with the scale of the array. Traditional computational approaches are unable to meet this demand in the near future. This thesis explores the use of heterogeneous parallel processing to meet the computational demands of radio astronomy. In heterogeneous computing, multiple hardware architectures are used for processing. In this work, the Graphics Processing Unit (GPU) is used as a co-processor along with the Central Processing Unit (CPU) for the computation of signal processing algorithms. Specifically, the suitability of the GPU to accelerate the correlator algorithms used in radio astronomy is investigated. This work first implemented a FX correlator on the GPU, with a performance increase of one to two orders of magnitude over a serial CPU approach. The FX correlator algorithm combines pairs of telescope signals in the Fourier domain. Given N telescope signals from the interferometer array, N2 conjugate multiplications must be calculated in the algorithm. For extremely large arrays (N >> 30), this is a huge computational requirement. Testing will show that the GPU correlator produces results equivalent to that of a software correlator implemented on the CPU. However, the algorithm itself is adapted in order to take advantage of the processing power of the GPU. Research examined how correlator parameters, in particular the number of telescope signals and the Fast Fourier Transform (FFT) length, affected the results.