The Polyhedral Model Beyond Loops Recursion Optimization and Parallelization Through Polyhedral Modeling - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

The Polyhedral Model Beyond Loops Recursion Optimization and Parallelization Through Polyhedral Modeling

Résumé

There may be a huge gap between the statements outlined by programmers in a program source code and instructions that are actually performed by a given processor architecture when running the executable code. This gap is due to the way the input code has been interpreted, translated and transformed by the compiler and the final processor hardware. Thus, there is an opportunity for efficient optimization strategies, that are dedicated to specific control structures and memory access patterns, to apply as soon as the actual runtime behavior has been discovered, even if they could not have been applied on the original source code. In this paper, we develop this idea by identifying code extracts that behave as polyhedral-compliant loops at runtime, while not having been outlined at all as loops in the original source code. In particular, we are interested in recursive functions whose runtime behavior can be modeled as polyhedral loops. Therefore, the scope of this study exclusively includes recursive functions whose control flow and memory accesses exhibit an affine behavior, which means that there exists a semantically equivalent affine loop nest, candidate for poly-hedral optimizations. Accordingly, our approach is based on analyzing early executions of a recursive program using a Nested Loop Recognition (NLR) algorithm, performing the affine loop modeling of the original program runtime behavior , which is then used to generate an equivalent iterative program, finally optimized using the polyhedral compiler Polly. We present some preliminary results showing that this approach brings recursion optimization techniques into a higher level in addition to widening the scope of the polyhe-dral model to include originally non-loop programs.
Fichier principal
Vignette du fichier
IMPACT_2019_paper_5.pdf (558.53 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02059558 , version 1 (06-03-2019)

Identifiants

  • HAL Id : hal-02059558 , version 1

Citer

Salwa Kobeissi, Philippe Clauss. The Polyhedral Model Beyond Loops Recursion Optimization and Parallelization Through Polyhedral Modeling. IMPACT 2019 - 9th International Workshop on Polyhedral Compilation Techniques, In conjunction with HiPEAC 2019, Jan 2019, Valencia, Spain. ⟨hal-02059558⟩
224 Consultations
455 Téléchargements

Partager

Gmail Facebook X LinkedIn More