PhD defense : Methodology for code-optimization of memory data layouts by adaptation to high-performance-system architectures with complex memory hierarchies

Riyane Yacine Sid Lakhdar a soutenu sa thèse en décembre dernier, j’avais oublié d’en faire un billet. La soutenance a eu lieu en partie en ligne, le 11 décembre 2020, devant le jury composé de :

Photo de la soutenance et de l’écran de contrôle Zoom.

La thèse, rédigée en anglais, est référencée sur these.fr et le manuscrit est disponible sur archives ouvertes.

Le résumé en français :

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 complexité 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 spécifique. Modifier légèrement une
application optimisée ou la porter sur une nouvelle architecture
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 proposons 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éthode, 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émentation 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 données sur les mémoires singulières qui sont
explicitement adressés par le programmeur (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çues 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 processeur x86 implémentant un Intel
Xeon à trois niveaux de caches de données et (ii) un processeur
massivement parallele implémentant un Kalray Coolidge-80-30 à
mémoire scratchpad sur puce de 16K octets. Les expériences menées
sur des noyaux 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 structures 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.