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

Salwa Kobeissi 1, 2 Philippe Clauss 1, 2
1 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/hal-02059558
Contributor : Philippe Clauss <>
Submitted on : Wednesday, March 6, 2019 - 5:09:50 PM
Last modification on : Tuesday, April 2, 2019 - 1:39:11 AM
Long-term archiving on : Friday, June 7, 2019 - 5:29:41 PM

File

IMPACT_2019_paper_5.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02059558, version 1

Citation

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⟩

Share

Metrics

Record views

67

Files downloads

203