Polyhedral code generation : reducing overhead and increasing parallelism

This thesis proposes new extensions to the code generation phase in polyhedral compilers. The main focus of recent work on polyhedral compilation 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 travauex actuels dans le domaine du modèle polé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 comme é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 ysnchronisations peuvent limiter dreastiquement la performance du 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’à present ignorée par les paralléliseurs polyédriques