La migration vers la résolution HD de la plupart des applications multimédias visuelles a nécessité la création de nouveaux standards de compression vidéo tels que le H264/AVC (Advanced Video Coding) et le HEVC (High Efficiency Video Coding). Ces standards sont caractérisés par des hautes performances de codage en termes de taux de compression et qualité vidéo par rapport aux normes précédentes. Cependant, ces performances entraînent de grandes complexités de calcul ce qui rend difficile d'assurer un encodage en temps réel pour la résolution HD sur des processeurs monocœurs programmables qui sont les plus répandus. De plus, comme actuellement les systèmes embarqués sont de plus en plus utilisés dans diverses applications multimédias, concevoir une solution logicielle embarquée pour l'encodeur H264/AVC constitue ainsi un défit très difficile puisqu'il faut répondre aux exigences de l'embarqué au niveau des ressources matérielles comme la mémoire et de la consommation d'énergie. Les récents systèmes embarqués dotés de la technologie multicœur représentent une solution attractive pour surmonter ces problèmes. Dans ce contexte, cette thèse s'intéresse à exploiter la performance de la nouvelle génération de DSP multicœurs de Texas Instruments pour concevoir un encodeur H264/AVC embarqué de résolution HD fonctionnant en temps réel. Nous visons une solution logicielle, caractérisée par une forte flexibilité, par rapport aux IPs existants, qui permet de tout paramétrer (qualité, débit etc). Cette flexibilité logicielle permet aussi l'évolutivité de système en suivant les améliorations de codage comme la migration vers la nouvelle norme HEVC, partiellement abordée dans cette thèse. Nous présentons ainsi les diverses optimisations appliquées que ce soient algorithmiques, architecturales et structurelles afin d'améliorer la vitesse d'encodage sur un seul cœur DSP avant de passer à une implémentation multicœur. Ensuite, nous proposons des implémentations parallèles de l'encodeur H264/AVC sur différentes unités de calcul en exploitant le parallélisme potentiel au sein de la chaîne d'encodage afin de satisfaire la contrainte de temps réel tout en assurant une bonne performance de codage en termes de qualité vidéo et débit binaire. Nous étudions également le problème d'allocation des ressources (ressources de calcul, ressources mémoire, ressources de communication) avec de fortes contraintes temporelles d'exécution. Finalement, cette thèse ouvre la voie vers l'implémentation de la nouvelle norme de codage vidéo HEVC sur deux systèmes embarqués monocœurs dans le but de préparer une solution logicielle embarquée pour les futurs travaux de recherche / The trend toward HD resolution in most of visual multimedia applications has involved the emergence of a large number of video compression standards such as H.264/AVC (Advanced Video Coding) and HEVC (High Efficiency Video Coding). These standards are characterized by high coding performances in terms of compression ratio and video quality compared to previous standards. However, these performances come with large computational complexities which make it difficult to meet real-time encoding for HD resolution on the most common single-core programmable processors. Moreover, as embedded systems have become increasingly used in various multimedia applications, designing an embedded software solution for the H264/AVC encoder represents another difficult challenge since we have to meet the embedded requirements in terms of hardware resources such as memory and power consumption. The new embedded systems with multicore technology represent an attractive solution to overcome these problems. In this context, this thesis is interested in exploiting the performance of the new generation of Texas Instruments multicore DSPs to design an embedded real-time H264/AVC high definition video encoder. We aim a software solution, characterized by high flexibility that allows setting all parameters (quality, bitrate etc) compared to existing IPs. This software flexibility allows also the system scalability by following the coding enhancements as the migration to the newest HEVC standard. Thus, we present the algorithmic, architectural, and structural optimizations which are applied to improve the encoding speed on a single DSP core before moving to a multicore implementation. Then, we propose parallel implementations of the H264/AVC encoder exploiting the multicore architecture of our platform and the potential parallelism in the encoding chain in order to meet real-time constraints while ensuring a good performance in terms of bitrate and video quality. We also explore the problem of resources allocation (computing resources, storage resources, communication resources) with hard execution time constraints. Finally, this thesis opens the way towards the implementation of the new HEVC video coding standard on two embedded systems in order to prepare a software solution for future research

Afin de s'adapter aux architectures multicoeurs et aux machines de plus en plus complexes, les modèles de programmations basés sur un parallélisme de tâche ont gagné en popularité dans la communauté du calcul scientifique haute performance. Les moteurs d'exécution fournissent une interface de programmation qui correspond à ce paradigme ainsi que des outils pour l'ordonnancement des tâches qui définissent l'application. Dans cette étude, nous explorons la conception de solveurs directes creux à base de tâches, qui représentent une charge de travail extrêmement irrégulière, avec des tâches de granularités et de caractéristiques différentes ainsi qu'une consommation mémoire variable, au-dessus d'un moteur d'exécution. Dans le cadre du solveur qr mumps, nous montrons dans un premier temps la viabilité et l'efficacité de notre approche avec l'implémentation d'une méthode multifrontale pour la factorisation de matrices creuses, en se basant sur le modèle de programmation parallèle appelé "flux de tâches séquentielles" (Sequential Task Flow). Cette approche, nous a ensuite permis de développer des fonctionnalités telles que l'intégration de noyaux dense de factorisation de type "minimisation de cAfin de s'adapter aux architectures multicoeurs et aux machines de plus en plus complexes, les modèles de programmations basés sur un parallélisme de tâche ont gagné en popularité dans la communauté du calcul scientifique haute performance. Les moteurs d'exécution fournissent une interface de programmation qui correspond à ce paradigme ainsi que des outils pour l'ordonnancement des tâches qui définissent l'application. Dans cette étude, nous explorons la conception de solveurs directes creux à base de tâches, qui représentent une charge de travail extrêmement irrégulière, avec des tâches de granularités et de caractéristiques différentes ainsi qu'une consommation mémoire variable, au-dessus d'un moteur d'exécution. Dans le cadre du solveur qr mumps, nous montrons dans un premier temps la viabilité et l'efficacité de notre approche avec l'implémentation d'une méthode multifrontale pour la factorisation de matrices creuses, en se basant sur le modèle de programmation parallèle appelé "flux de tâches séquentielles" (Sequential Task Flow). Cette approche, nous a ensuite permis de développer des fonctionnalités telles que l'intégration de noyaux dense de factorisation de type "minimisation de cAfin de s'adapter aux architectures multicoeurs et aux machines de plus en plus complexes, les modèles de programmations basés sur un parallélisme de tâche ont gagné en popularité dans la communauté du calcul scientifique haute performance. Les moteurs d'exécution fournissent une interface de programmation qui correspond à ce paradigme ainsi que des outils pour l'ordonnancement des tâches qui définissent l'application. / To face the advent of multicore processors and the ever increasing complexity of hardware architectures, programming models based on DAG parallelism regained popularity in the high performance, scientific computing community. Modern runtime systems offer a programming interface that complies with this paradigm and powerful engines for scheduling the tasks into which the application is decomposed. These tools have already proved their effectiveness on a number of dense linear algebra applications. In this study we investigate the design of task-based sparse direct solvers which constitute extremely irregular workloads, with tasks of different granularities and characteristics with variable memory consumption on top of runtime systems. In the context of the qr mumps solver, we prove the usability and effectiveness of our approach with the implementation of a sparse matrix multifrontal factorization based on a Sequential Task Flow parallel programming model. Using this programming model, we developed features such as the integration of dense 2D Communication Avoiding algorithms in the multifrontal method allowing for better scalability compared to the original approach used in qr mumps. In addition we introduced a memory-aware algorithm to control the memory behaviour of our solver and show, in the context of multicore architectures, an important reduction of the memory footprint for the multifrontal QR factorization with a small impact on performance. Following this approach, we move to heterogeneous architectures where task granularity and scheduling strategies are critical to achieve performance. We present, for the multifrontal method, a hierarchical strategy for data partitioning and a scheduling algorithm capable of handling the heterogeneity of resources. Finally we present a study on the reproducibility of executions and the use of alternative programming models for the implementation of the multifrontal method. All the experimental results presented in this study are evaluated with a detailed performance analysis measuring the impact of several identified effects on the performance and scalability. Thanks to this original analysis, presented in the first part of this study, we are capable of fully understanding the results obtained with our solver.

Dans cette thèse de doctorat, nous étudions des algorithmes et des implémentations pour accélérer la résolution de systèmes linéaires denses en utilisant des architectures composées de processeurs multicœurs et d'accélérateurs. Nous nous concentrons sur des méthodes basées sur la factorisation LU. Le développement de notre code s'est fait dans le contexte de la bibliothèque MAGMA. Tout d'abord nous étudions différents solveurs CPU/GPU hybrides basés sur la factorisation LU. Ceux-ci visent à réduire le surcoût de communication dû au pivotage. Le premier est basé sur une stratégie de pivotage dite "communication avoiding" (CALU) alors que le deuxième utilise un préconditionnement aléatoire du système original pour éviter de pivoter (RBT). Nous montrons que ces deux méthodes surpassent le solveur utilisant la factorisation LU avec pivotage partiel quand elles sont utilisées sur des architectures hybrides multicœurs/GPUs. Ensuite nous développons des solveurs utilisant des techniques de randomisation appliquées sur des architectures hybrides utilisant des GPU Nvidia ou des coprocesseurs Intel Xeon Phi. Avec cette méthode, nous pouvons éviter l'important surcoût du pivotage tout en restant stable numériquement dans la plupart des cas. L'architecture hautement parallèle de ces accélérateurs nous permet d'effectuer la randomisation de notre système linéaire à un coût de calcul très faible par rapport à la durée de la factorisation. Finalement, nous étudions l'impact d'accès mémoire non uniformes (NUMA) sur la résolution de systèmes linéaires denses en utilisant un algorithme de factorisation LU. En particulier, nous illustrons comment un placement approprié des processus légers et des données sur une architecture NUMA peut améliorer les performances pour la factorisation du panel et accélérer de manière conséquente la factorisation LU globale. Nous montrons comment ces placements peuvent améliorer les performances quand ils sont appliqués à des solveurs hybrides multicœurs/GPU. / In this PhD thesis, we study algorithms and implementations to accelerate the solution of dense linear systems by using hybrid architectures with multicore processors and accelerators. We focus on methods based on the LU factorization and our code development takes place in the context of the MAGMA library. We study different hybrid CPU/GPU solvers based on the LU factorization which aim at reducing the communication overhead due to pivoting. The first one is based on a communication avoiding strategy of pivoting (CALU) while the second uses a random preconditioning of the original system to avoid pivoting (RBT). We show that both of these methods outperform the solver using LU factorization with partial pivoting when implemented on hybrid multicore/GPUs architectures. We also present new solvers based on randomization for hybrid architectures for Nvidia GPU or Intel Xeon Phi coprocessor. With this method, we can avoid the high cost of pivoting while remaining numerically stable in most cases. The highly parallel architecture of these accelerators allow us to perform the randomization of our linear system at a very low computational cost compared to the time of the factorization. Finally we investigate the impact of non-uniform memory accesses (NUMA) on the solution of dense general linear systems using an LU factorization algorithm. In particular we illustrate how an appropriate placement of the threads and data on a NUMA architecture can improve the performance of the panel factorization and consequently accelerate the global LU factorization. We show how these placements can improve the performance when applied to hybrid multicore/GPU solvers.