Polytope model

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:
 const int n = 100;
 int i, j, a[n][n];
 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];
The essential problem with this code is that each iteration of the inner loop on codice_1 requires that the previous iteration's result, codice_2, 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 formula_1 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. (However, each iteration of the outer loop does depend on previous iterations.)
Detailed example.
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 codice_3 contains codice_4 rows of codice_5 pixels, each pixel having a grayscale value between 0 and 255 inclusive. After the routine has finished, the output array codice_6 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 codice_3 array. (Notice that codice_3 and codice_6 are both read and written during the computation; codice_3 is not read-only, and codice_6 is not write-only.)
Each iteration of the inner loop modifies the values in codice_12 based on the values of codice_13, codice_14, and codice_15. (The same dependencies apply to codice_16. For the purposes of loop skewing, we can think of codice_12 and codice_16 as the same element.) We can illustrate the dependencies of codice_12 graphically, as in the diagram on the right.
Performing the affine transformation formula_2 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 codice_20 and codice_21 instead of codice_22 and codice_23, obtaining the following "skewed" routine.