Polyhedral Code Generation: Reducing Overhead and Increasing Parallelism
Génération de code polyédrique efficace : vers plus de parallélisme et moins de contrôle
Résumé
This thesis proposes new extensions to the code generation phase in polyhedral compilers. The main focus of recent work on polyhedral compilation focus is the optimizations leveraged by polyhedral transformations while state-of-the-art code generation algorithms are considered satisfactory. We show that state-of-the-art polyhedral code generation can still be further improved. We explain how splitting polyhedra can reduce the control overhead introduced by polyhedra scanning in the code generated by a polyhedral compiler. Synchronizations in parallel code can drastically impede a program’s performance. We propose a method to detect and lift unnecessary synchronization barriers. Finally, we introduce pipelined multithreading, a transformation that introduces parallelism in a class of programs that was, until now, ignored by polyhedral parallelizers.
Cette thèse propose de nouvelles extensions à la phase de génération de code dans les compilateurs polyédriques. Une grande partie des travaux actuels dans le domaine du modèle polyédrique porte sur les transformations à appliquer et les optimisations ainsi permises. À l’inverse, la génération de code est délaissée car la littérature correspondante offre des algorithmes considérés comment étant suffisamment performants. Nous montrons dans cette thèse qu’il subsiste une nette marge d’amélioration vis-à-vis de l’état de l’art. Nous expliquons comment le coût du contrôle dû au parcours de plusieurs polyèdres dans le code généré par un compilateur polyédrique peut être diminué. Dans le cas de codes parallèles, les synchronisations peuvent limiter drastiquement la performance d’un programme. Nous donnons la méthode permettant de détecter et éliminer les barrières de synchronisation superflues. Enfin, nous proposons le pipelined multithreading, une transformation qui introduit du parallélisme sur une classe de programmes jusqu’à présent ignorée par les paralléliseurs polyédriques.