polytope model
≈ 3 min read
Names in other languages
- eohiperpluredra modelo
- Русскиймодель политопа
- slpolitopni model
- Englishpolytope model
- DeutschPolytopmodell
- فارسیمدل پولیتوپ
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of operations -- too large to be explicitly enumerated -- thereby requiring a compact representation. Nested loop programs are the typical, but not the only example, and the most common use of the model is for loop nest optimization in program optimization. The polyhedral method treats each loop iteration within nested loops as lattice points inside mathematical objects called polyhedra, performs affine transformations or more general non-affine transformations such as tiling on the polytopes, and then converts the transformed polytopes into equivalent, but optimized (depending on targeted optimization goal), loop nests through polyhedra scanning.
The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of operations -- too large to be explicitly enumerated -- thereby requiring a compact representation. Nested loop programs are the typical, but not the only example, and the most common use of the model is for loop nest optimization in program optimization. The polyhedral method treats each loop iteration within nested loops as lattice points inside mathematical objects called polyhedra, performs affine transformations or more general non-affine transformations such as tiling on the polytopes, and then converts the transformed polytopes into equivalent, but optimized (depending on targeted optimization goal), loop nests through polyhedra scanning. define n 100 int i, j; int a[n][n] = ; for (i = 1; i The essential problem with this code is that each iteration of the inner loop on a[i][j] requires that the previous iteration's result, a[i][j - 1] , be available already. Therefore, this code cannot be parallelized or pipelined as it is currently written. An application of the polytope model, with the affine transformation (i',\, j') = (i+j,\, j) and the appropriate change in the boundaries, will transform the nested loops above into: a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1]; In this case, no iteration of the inner loop depends on the previous iteration's results; the entire inner loop can be executed in parallel. Indeed, given a(i, j) = a[i-j][j] then a(i, j) only depends on a(i - 1, x) , with x \in \{j - 1,\, j\} . (However, each iteration of the outer loop does depend on previous iterations.) Performing the affine transformation (p,\, t) = (i,\, 2j+i) on the original dependency diagram gives us a new diagram, which is shown in the next image. We can then rewrite the code to loop on p and t instead of i and j , obtaining the following "skewed" routine.
See also
Frameworks supporting the polyhedral model Loop nest optimization Loop optimization Loop unrolling Loop tiling
External links and references
"The basic polytope method", tutorial by Martin Griebl containing diagrams of the pseudocode example above "Code Generation in the Polytope Model" (1998). Martin Griebl, Christian Lengauer, and Sabine Wetzel "The CLooG Polyhedral Code Generator" "CodeGen+: Z-polyhedra scanning" PoCC: the Polyhedral Compiler Collection PLUTO - An automatic parallelizer and locality optimizer for affine loop nests polyhedral.info - A website that collect information about polyhedral compilation Polly - LLVM Framework for High-Level Loop and Data-Locality Optimizations The MIT Tiramisu Polyhedral Framework.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1360023420 under CC BY-SA 4.0; modifications have been made.