Declarative Transformations in the Polyhedral Model

Transformations Déclaratives dans le Modèle Polyédrique

Oleksandr Zinenko (1) , Lorenzo Chelini (2, 3) , Tobias Grosser (4)

1 Parkas - Parallélisme de Kahn Synchrone
2 IBM Research Laboratory [Zurich]
3 TU/e - Eindhoven University of Technology [Eindhoven]
4 ETH Zürich - Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich]

Despite the availability of sophisticated automatic optimizers, performance-critical code sections are in practice still tuned by human experts. Pragma-based languages such as OpenMP or OpenACC are the standard interface to apply such transformations to large code bases and loop transformation pragmas would be a straightforward extension to provide fine-grained control over a compilers loop optimizer. However, the manual optimization of programs via explicit sequences of directives is unlikely to fully solve this problem as expressing complex optimization sequences explicitly results in difficult to read and non-performance-portable code. We address this problem by presenting a novel framework of composable program transformations based on the internal tree-like program representation of a polyhedral compiler. Based on a set of tree matchers and transformers, we describe an embedded transformation language which provides the foundation for the development of program optimization tactics. Using this language, we express core building blocks such as loop tiling, fusion, or data-layout-transformations, and compose them to higher-level transformations expressing algorithm-specific optimization strategies for stencils, dense linear-algebra, etc. We expect our approach to simplify the development of polyhedral optimizers and integration of polyhedral and syntactic approaches.

Malgré l’existence d’outils sophistiqués d’optimisation automatique, les parties des programmes dont la performance est cruciale sont toujours optimisées manuellement par des humains experts. Les langages basés sur des directives “pragma”, tels que OpenMP ou OpenACC, sont une interface typique pour exprimer les transformations sur des grandes bases de code source. Telles directives pour transformer des nids de boucles seraient une extension naturelle permettant de contrôler l’optimiseur de boucles d’une manière précise. Pourtant l’optimisation manuelle des programmes à travers les séquences des directives de transformation n’est pas toujours souhaitable car ces séquences longues et complexes produisent des programmes peu lisibles et ne bénéficiant pas de la portabilité de performance entre les différentes architectures matérielles. Nous proposons une nouvelle approche pour définir les transformations composables des programmes basée sur la représentation interne d’un compilateur polyédrique sous forme de l’arbre. Grâce à un ensemble des “motifs” et “transformateurs” des arbres, nous décrivons un langage de transformation sur lequel nous basons le développement des tactiques d’optimisation. Avec ce langage, il est possible d’exprimer les transformations basiques, telles que le tuilage, la fusion ou la transposition de données, ainsi que la composition de ces transformations afin de définir une stratégie d’optimisation pour les grandes classes des programmes, telles que les pochoirs, les contractions de tenseurs, etc. Notre approche pourrait simplifier le développement des optimiseurs polyédriques et l’intégration des transformations polyédriques et syntaxiques

Mots clés: Tree rewriting; Polyhedral model; Loop nest optimization

Mots clés: Modèle polyédrique; Transformations des nids de boucles; Réécriture des arbres

Domaines: Langage de programmation [cs.PL]; Intelligence artificielle [cs.AI]

Oleksandr Zinenko, Lorenzo Chelini, Tobias Grosser. Declarative Transformations in the Polyhedral Model. [Research Report] RR-9243, Inria; ENS Paris - Ecole Normale Supérieure de Paris; ETH Zurich; TU Delft; IBM Zürich. 2018. ⟨hal-01965599⟩