Méthodologie pour l'optimisation logicielle de structures de données pour les architectures hautes performances à mémoires complexes

With the rising impact of the memory wall, selecting the adequate data-structure implementation for a given kernel has become a performance-critical issue. The complexity of solving efficiently this Data-Layout-Decision (DLD) problem is dra- matically increased by the concurrence of complex, heterogeneous and application- specific hardware memories. Slightly modifying an optimized application or porting it to a new hardware architecture requires an important time and engineering effort. It also requires a deep knowledge of the host hardware platform.In this thesis, we plot a first step toward automatic software-adaptation to hard- ware. We present an iterative data-mining-related software-optimization approach based on the detection and the exploration of the most influential parameters linked to the hardware, operating system and software. We also propose a custom data- cache-miss modeling algorithm designed to be used as fully-parameterized perfor- mance evaluation. The proposed approach is designed to be embedded within a general-purpose compiler.In order to explore the parameters related to the data-layout implementation, we propose HARDSI, a custom patented method to solve the DLD problem. We also propose to apply our method using a custom domain-specific language and computation framework. The HARDSI method allows to choose, from a custom base of knowledge, an optimized data-layout implementation with regards to the memory-pattern followed to access the considered data-structure. The generated solutions are also specifically adapted to the properties of the host hardware-memory.Meanwhile, we consider the singular resolution of the DLD problem on memories that are explicitly addressed by the programmer (such as embedded scratchpad memories or GPUs). The problem that we address is to find an optimized memory- placement in order to maximize the amount of frequently-accessed data to be stored within this fast yet narrow memory. In this context, we propose DDLGS, a custom patented method designed to generate a dynamic data-layout with regards to the followed memory-access pattern. The generated implementations encompass the specific load and store routines as well as the granularity attributed to each data transferred. These implementations are also able to adapt, at run time, to the input of the considered source-code.Aiming to evaluate our implementations on different hardware environments, we have considered two different processor and memory architectures: (i) An x86 pro- cessor implementing an Intel Xeon with three levels of data-caches utilizing the least recently used replacement policy and a (ii) Massively Parallel Processor Array im- plementing a Kalray Coolidge-80-30 with a 16KBytes on-chip scratchpad memory. Experiments on linear algebra, artificial intelligence and image processing bench- marks show that our method accurately determines an optimized data-structure implementation. These implementations allow reaching an execution-time speed-up up to 48.9x on the Xeon processor and 54.2x on the Coolidge processor.La sélection d’une implémentation adéquate de structure de données pour un noyau de calcul donné est un problème critique pour les performances logicielles. La com- plexité de la résolution efficace de ce problème est exacerbée par la concurrence de mémoires matérielles complexes, hétérogènes et dédiées à une application specifique. Modifier légèrement une application optimisée ou la porter sur une nouvelle archi- tecture matérielle nécessite un temps et un effort d’ingénierie considérable. Cela nécessite également une connaissance approfondie de la plateforme matérielle hôte.Au cours de cette thèse, nous franchissons une première étape vers l’optimisation par l’adaptation automatique du logiciel au matériel. Nous présentons une approche itérative d’optimisation basée sur la détection et l’exploration des paramètres les plus influents liés au matériel, au système d’exploitation et au logiciel. La méthode proposée est conçue pour être intégrée dans un compilateur à usage général. Dans ce contexte, nous proposons un algorithme de génération de modèles (entièrement paramétrées) de mémoires caches. Les modèles de performance générés sont conçus pour être utilisé dans le cadre d’évaluations de performances et d’optimisation.Afin d’explorer les paramètres liés à aux structures de données, nous pro- posons HARDSI, une méthode brevetée permettant la résolution du problème de l’agencement des données pour logiciel donné. Dans le but d’appliquer notre méth- ode, nous proposons également un langage dédié (basé sur le langage C/C++) ainsi que son environnement logiciel de compilation et d’exécution. La méthode HARDSI permet de choisir, à partir d’une base de connaissances spécialisée, une implémen- tation optimisée de l’agencement des données en fonction de la géométrie d’accès à la structure de données. Les solutions générées sont également spécifiquement adaptées aux caractéristiques matérielles de la mémoire hôte considérée.De même, nous considérons la résolution du problème de l’agencement des don- nées sur les mémoires singulières qui sont explicitement adressés par le program- meur (tel que les mémoires de type "scratchpad" ou GPU). Le problème que nous abordons est de trouver un emplacement mémoire optimisé afin de maximiser la quantité de données fréquemment accédées et à stocker dans ce type de mémoires rapides bien qu’étroites. Dans ce contexte, nous proposons DDLGS, une méthode brevetée conçue pour générer une implémentation dynamique des données sur mé- moires scratchpad. Ces implémentations sont conçus par DDLGS en considérant le schéma d’accès à la mémoire spécifiquement suivi par le code a optimiser.Dans le but d’évaluer nos implémentations sur différents environnements matériels, nous considérons deux processeurs et mémoires différents: (i) un pro- cesseur x86 implémentant un Intel Xeon à trois niveaux de caches de données et (ii) un processeur massivement parallel implémentant un Kalray Coolidge-80-30 à mé- moire scratchpad sur puce de 16K octets. Les expériences menées sur des noyeaux d’algèbre linéaire, d’intelligence artificielle et de traitement d’images montrent que notre méthode détermine avec précision une implémentation optimisée des struc- tures de données. Ces implémentations permettent d’atteindre une accélération du temps d’exécution jusqu’à 48,9x sur le processeur Xeon et 54,2x sur le Coolidge