The Polyhedral Model Beyond Loops Recursion Optimization and Parallelization Through Polyhedral Modeling - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1, 2) , (1, 2)
1
2

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.
Fichier principal
Vignette du fichier
IMPACT_2019_paper_5.pdf (558.53 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : hal-02059558 , version 1

Cite

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⟩
212 View
384 Download

Share

Gmail Facebook Twitter LinkedIn More