Optimisation orientée performance et précision des formats de données dans les codes numériques – PADOC

L'approche a été de se concentrer sur l'optimisation des programmes itératifs. Même si ils sont très présents dans les programmes de calculs numériques, peu d'outils automatiques ont été mis en place pour adapter le format des données et/ou instructions dans les routines itératives. Notre travail a alors été effectué dans deux directions.

(1) La première direction a eu pour objectif de mettre en place un outil permettant d’isoler rapidement les nids de vectorisation, c’est-à-dire, les zones d’un programme qui pourront bénéficier des instructions vectorielles, une fois ce programme compilé. Une fois ces nids de vectorisation isolés, cet outil permet de réduire le format de leurs instructions, augmentant par conséquent le facteur de vectorisation, pour ainsi améliorer les performances de l’application, sans contrainte de précision à cette étape.

(2) La deuxième direction est la direction majeure du projet. Elle s'intéresse à l'adaptation du format des instructions dans les programmes itératifs. Ce processus repose sur une première brique de base dont l'objectif est d'étudier l’impact de la transformation du format de certaines instructions sur la précision des résultats du programme d'entrée. Pour cela, nous avons développé un outil dans l’infrastructure de compilation LLVM, qui repose en particulier sur (1) l’outil fp2mp qui permet d’instrumenter un programme flottant avec des calculs en multi-précision utilisant MPFR, et (2) un loop splitter qui permet de découper une boucle en plusieurs sous-boucles itérant sur des espaces d’itérations réduits. Le premier module permet d’évaluer l’impact d’une modification de la précision de certaines instructions d’un programme, alors que le deuxième permet d’appliquer les transformations à certaines itérations d'une boucle, uniquement.

Nous avons enfin développer un outil d'optimisation basé sur l'algorithme de delta-debugging. Ce dernier permet d'isoler, dans un ensemble de transformations possibles, un sous-ensemble maximal permettant de garantir que le critère de précision sur le résultat final reste satisfait. Cet outil Python permet alors de choisir, pour un programme itératif donné, un format pour les instructions de chaque itération ou bloc d'itérations. Ceci est fait en découpant la boucle du programme en sous-boucles itérant sur des espaces d'itérations réduits, et en adaptant le format des instructions pour chaque sous-boucle. Nous avons alors pu illustrer l'intérêt de notre approche sur l'exemple de la multiplication de matrices sur architectures SIMD.

Ce projet a permis le développement de trois logiciels.

(1) Le premier outil, appelé vectoptim (~4000 lignes), a été développé dans l'infrastructure de compilation LLVM. Il permet d'isoler les instructions pouvant bénéficier des unités vectorielles, et de réduire leur format.

(2) Le deuxième outil est une infrastructure d'analyse de précision pour les programmes itératifs. Elle est composée de fp2mp et d'un loop splitter (~11000 lignes). Développée dans LLVM, également, elle permet d’analyser l’impact de la transformation du format de certaines données et/ou instructions d’un programme sur la précision de ses résultats, particulièrement dans le cas de programmes itératifs.

(3) Enfin, le troisième outil utilise notre infrastructure d'analyse pour adapter le format des instructions dans les programmes itératifs. Outil Python (~1000 lignes), reposant sur fp2mp, il utilise l'algorithme de delta-debugging pour décider les instructions dont le format peut être réduit sans trop dégrader la précision du résultat, et ainsi pour adapter le format de certaines instructions dans les programmes itératifs. Contrairement aux outils existants d'adaptation de la précision, il permet par exemple de réduire la précision de certaines instructions à certaines itérations d’une boucle uniquement, ou par bloc d’itérations.

Les objectifs initiaux du projet ont été ré-axés sur l'optimisation des programmes itératifs sur architectures vectorielles. Les perspectives du projet s'articulent alors autour des motivations initiales, et en particulier de deux axes principaux.

(1) Le premier axe concerne la robustesse de programmes aux données d'entrée. En effet, comme la plupart des outils existants, l'outil développé dans le cadre de ce projet permet l'optimisation du format des instructions valable pour un jeu de données. Une première perspective serait de proposer des optimisations valables non pas pour un seul jeu de données, mais pour plusieurs jeux de données, voire quel que soit le jeu de données d'entrée.

(2) Le second axe concerne le passage à l'échelle. L'outil développé permet de traiter des routines simples de calcul. Mais les méthodes utilisées ne permettent pas de traiter des programmes de calcul complets. Une seconde perspective serait d'améliorer l'approche proposée pour permettre de traiter des programmes numériques plus conséquents, comme les programmes de simulation numérique issus de la physique, comme prévu initialement dans le projet.

Ces deux axes représentent encore aujourd'hui les deux défis majeurs des outils d'adaptation des formats de données dans les programmes de calcul numérique.

Le développement de codes numériques efficaces et précis est une tâche
difficile. En effet elle requiert de connaître parfaitement la
micro-architecture cible, le comportement de ses unités de calcul et son jeu
d'instructions. Mais elle requiert également d'analyser soigneusement les
contraintes de précision sur toutes les données du code et la précision de
calcul afin d'atteindre une précision de sortie donnée. Généralement, ces deux
critères sont traités de manière séparée. Et nous constatons que les données de
calcul sont souvent sur-dimensionnées, principalement dû au manque d'expertise
des développeurs. Les codes ne profitent alors pas pleinement des capacités de
la micro-architecture.

Pour améliorer la performance des applications et réduire leur temps
d'exécution, une approche consiste à diminuer la précision de certaines données
bien choisies du code. Ceci permet d'exploiter le parallélisme fourni par
certaines architectures modernes, grâce à l'utilisation d'instructions
vectorielles. Toutefois décider quelles données peuvent être adaptées, sans trop
dégrader la précision du résultat, est une tâche compliquée, même pour les
experts en logiciels numériques. Et cette difficulté augmente avec la taille des
applications.

L'objectif du projet PADOC consiste à concevoir des outils pour aider les
développeurs à adapter automatiquement le format des données flottantes dans un
code numérique. L'intérêt est d'exploiter au mieux les unités de calcul de
l'architecture cible, et ainsi améliorer les performances du code, tout en
garantissant une certaine précision sur le résultat. Des outils existent déjà
pour résoudre ce problème. Cependant ils ont les inconvénients suivants :
Premièrement ils dépendent d'un jeu de données, non suffisamment représentatif
des données sur lesquelles le code sera utilisé. Ainsi les transformations
peuvent ne plus être valides pour d'autres données. Deuxièmement, ils ne
prennent pas en compte les caractéristiques de la micro-architecture lors de la
transformation. Les codes fournis peuvent alors ne pas profiter pleinement de
ses capacités. Troisièmement, l'optimisation est effectuée sur toutes les
données du code, même celles pour lesquelles la transformation ne sera pas
pertinente. Pour un grand nombre de données, la combinatoire est très grande, ce
qui entraîne un ralentissement du temps d'optimisation. Par conséquent, notre
objectif est de concevoir des outils d'optimisation pour produire des codes
robustes aux données et optimisés pour une micro-architecture. Mais avant tout,
nous souhaitons accélérer la phase d'adaptation en isolant les données les plus
pertinentes, réduisant alors la combinatoire.

Le flot de conception du projet PADOC prend en entrée un code et renvoie un code
optimisé. Nous souhaitons ici travailler autour de trois axes. Le premier axe
consiste à étudier l'impact de l'adaptation des formats de données sur la
performance. Plus particulièrement, l'objectif est d'isoler dans le code
certaines parties pour lesquelles abaisser la précision des données peut
entraîner une amélioration importante en terme de performance. Le deuxième axe
est d'étudier l'impact de cette adaptation sur la précision du résultat, et la
robustesse aux données des codes optimisés. L'objectif est d'isoler les données
du code dont la précision souffre plus ou moins de l'adaptation de la
précision. Ainsi, nous pourrons décider quelle partie est la plus pertinente
pour le processus d'adaptation. L'objectif du troisième axe est de développer
l'outil d'optimisation globale, et de le valider sur des applications de
simulation, comme CORSIKA. L'idée principale est d'utiliser les connaissances en
termes de précision et de performance des étapes précédentes, afin de
discriminer entre les différentes parties du code. La transformation se fera sur
les parties les plus pertinentes, réduisant ainsi la combinatoire. Nous espérons
alors obtenir une réduction du temps d'adaptation pour les codes numériques.