Divergence Analysis

International audienceGrowing interest in graphics processing units has brought renewed attention to the Single Instruction Multiple Data (SIMD) execution model. SIMD machines give application developers tremendous computational power; however, programming them is still challenging. In particular, developers must deal with memory and control-flow divergences. These phenomena stem from a condition that we call data divergence, which occurs whenever two processing elements (PEs) see the same variable name holding different values. This article introduces divergence analysis, a static analysis that discovers data divergences. This analysis, currently deployed in an industrial quality compiler, is useful in several ways: it improves the translation of SIMD code to non-SIMD CPUs, it helps developers to manually improve their SIMD applications, and it also guides the automatic optimization of SIMD programs. We demonstrate this last point by introducing the notion of a divergence-aware register spiller. This spiller uses information from our analysis to either rematerialize or share common data between PEs. As a testimony of its effectiveness, we have tested it on a suite of 395 CUDA kernels from well-known benchmarks. The divergence-aware spiller produces GPU code that is 26.21% faster than the code produced by the register allocator used in the baseline compiler.L'intérêt croissant pour les processeurs graphiques a amené une attention nouvelle sur le modèle d'exécution SIMD (Single Instruction Multiple Data). Les machines SIMD fournissent au développeurs d'application une grande puissance de calcul. Cependant, leur programmation reste difficile. En particulier, les développeurs doivent faire face à la divergence mémoire et la divergence de contrôle. Ces phénomènes proviennent d'une condition que nous nommons divergence de données, qui advient lorsque deux éléments de calcul (PE) voient le même nom de variable contenir des valeurs différentes. Cet article introduit l'analyse de divergence, une analyse statique qui découvre les divergences de données. Cette analyse, actuellement déployée dans un compilateur de qualité industrielle, est utile de plusieurs manières : elle améliore la traduction automatique de code SIMD pour les processeurs non SIMD, elle aide les développeurs à améliorer manuellement leus applications SIMD, et elle guide aussi l'optimisation automatique de programmes SIMD. Nous démontrons ce dernier point en introduisant la notion d'allocateur de registre sensible à la divergence. Cet allocateur utilise l'information de notre analyse pour soit rematérialiser, soit partager des données communes entre les PE. Nous l'avons testé sur une suite de 395 noyaux de calcul CUDA de benchmarks connus. L'allocateur de registre sensible à la divergence produit du code GPU qui est 26% plus rapide que le code produit par l'allocateur du compilateur de base