{{Short description|Framework for computer program optimization}} {{for|physical models of polyhedra|Polyhedron model}} {{More footnotes needed|date=February 2026}} 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.
== Simple example ==
Consider the following example written in C:
<syntaxhighlight lang="c"> const int n = 100; int i, j; int a[n][n] = {{0,1}};
for (i = 1; i < n; i++) { for (j = 1; j < (i + 2) && j < n; j++) { a[i][j] = a[i - 1][j] + a[i][j - 1]; } }
for (i = 0; i < n; i++) { for (j = 0; j < n; ++j) { printf("%4d ", a[i][j]); } puts(""); } </syntaxhighlight>
The essential problem with this code is that each iteration of the inner loop on <code>a[i][j]</code> requires that the previous iteration's result, <code>a[i][j - 1]</code>, 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 <math>(i',\, j') = (i+j,\, j)</math> and the appropriate change in the boundaries, will transform the nested loops above into:
<syntaxhighlight lang="c"> a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1]; </syntaxhighlight>
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 <code>a(i, j) = a[i-j][j]</code> then <code>a(i, j)</code> only depends on <code>a(i - 1, x)</code>, with <math>x \in \{j - 1,\, j\}</math>. (However, each iteration of the outer loop does depend on previous iterations.)
== Detailed example ==
[[File:Polytope model unskewed.svg|thumb|right|The dependencies of <code>src</code>, before loop skewing. The red dot corresponds to <code>src[1][0]</code>; the pink dot corresponds to <code>src[2][2]</code>.]] The following C code implements a form of error-distribution dithering similar to Floyd–Steinberg dithering, but modified for pedagogical reasons. The two-dimensional array <code>src</code> contains <code>h</code> rows of <code>w</code> pixels, each pixel having a grayscale value between 0 and 255 inclusive. After the routine has finished, the output array <code>dst</code> will contain only pixels with value 0 or value 255. During the computation, each pixel's dithering error is collected by adding it back into the <code>src</code> array. (Notice that <code>src</code> and <code>dst</code> are both read and written during the computation; <code>src</code> is not read-only, and <code>dst</code> is not write-only.)
Each iteration of the inner loop modifies the values in <code>src[i][j]</code> based on the values of <code>src[i-1][j]</code>, <code>src[i][j-1]</code>, and <code>src[i+1][j-1]</code>. (The same dependencies apply to <code>dst[i][j]</code>. For the purposes of loop skewing, we can think of <code>src[i][j]</code> and <code>dst[i][j]</code> as the same element.) We can illustrate the dependencies of <code>src[i][j]</code> graphically, as in the diagram on the right.
<!-- This table nonsense makes the page look slightly better in Firefox on Windows XP. Is there a more portable and self-explanatory way to get the code and images not to overlap with each other? --~~~~ --> {| |- | <syntaxhighlight lang="c"> #define ERR(x, y) (dst[x][y] - src[x][y])
void dither(unsigned char** src, unsigned char** dst, int w, int h) { int i, j; for (j = 0; j < h; ++j) { for (i = 0; i < w; ++i) { int v = src[i][j]; if (i > 0) v -= ERR(i - 1, j) / 2; if (j > 0) { v -= ERR(i, j - 1) / 4; if (i < w - 1) v -= ERR(i + 1, j - 1) / 4; } dst[i][j] = (v < 128) ? 0 : 255; src[i][j] = (v < 0) ? 0 : (v < 255) ? v : 255; } } } </syntaxhighlight> |}
thumb|right|The dependencies of <code>src</code>, after loop skewing. The array elements will be processed in the order ''gray, red, green, blue, yellow...''
Performing the affine transformation <math>(p,\, t) = (i,\, 2j+i)</math> 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 <code>p</code> and <code>t</code> instead of <code>i</code> and <code>j</code>, obtaining the following "skewed" routine.
<!-- Please don't break this code. Test before committing! --> {| |- | <syntaxhighlight lang=C> void dither_skewed(unsigned char **src, unsigned char **dst, int w, int h) { int t, p; for (t = 0; t < (w + (2 * h)); ++t) { int pmin = max(t % 2, t - (2 * h) + 2); int pmax = min(t, w - 1); for (p = pmin; p <= pmax; p += 2) { int i = p; int j = (t - p) / 2; int v = src[i][j]; if (i > 0) v -= ERR(i - 1, j) / 2; if (j > 0) v -= ERR(i, j - 1) / 4; if (j > 0 && i < w - 1) v -= ERR(i + 1, j - 1) / 4; dst[i][j] = (v < 128) ? 0 : 255; src[i][j] = (v < 0) ? 0 : (v < 255) ? v : 255; } } } </syntaxhighlight> |}
==See also== *Frameworks supporting the polyhedral model *Loop nest optimization *Loop optimization *Loop unrolling *Loop tiling
==External links and references== *[https://www.infosun.fim.uni-passau.de/cl/loopo/doc/loopo_doc/node3.html "The basic polytope method"], tutorial by Martin Griebl containing diagrams of the pseudocode example above *[http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.5675 "Code Generation in the Polytope Model"] (1998). Martin Griebl, Christian Lengauer, and Sabine Wetzel *[http://www.cloog.org/ "The CLooG Polyhedral Code Generator"] *[http://www.chunchen.info/omega "CodeGen+: Z-polyhedra scanning"]{{dead link|date=March 2018 |bot=InternetArchiveBot |fix-attempted=yes }} *[http://web.cs.ucla.edu/~pouchet/software/pocc/ PoCC: the Polyhedral Compiler Collection] *[https://pluto-compiler.sourceforge.net/ PLUTO - An automatic parallelizer and locality optimizer for affine loop nests] **{{Cite book|last1=Bondhugula|first1=Uday|last2=Hartono|first2=Albert|last3=Ramanujam|first3=J.|last4=Sadayappan|first4=P.|title=Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation |chapter=A practical automatic polyhedral parallelizer and locality optimizer |date=2008-01-01|series=PLDI '08|location=New York, NY, USA|publisher=ACM|pages=101–113|doi=10.1145/1375581.1375595|isbn=9781595938602|s2cid=7086982}} *[http://polyhedral.info/ polyhedral.info] - A website that collect information about polyhedral compilation *[http://polly.llvm.org/ Polly - LLVM Framework for High-Level Loop and Data-Locality Optimizations] *The MIT [http://tiramisu-compiler.org/ Tiramisu Polyhedral] Framework.
Category:Compiler optimizations Category:Articles with example pseudocode Category:Articles with example C code