Polytope model

From Wikipedia, the free encyclopedia

For physical models of polyhedra, see Polyhedron model.

The polytope model (also called the polyhedron method or loop skewing) is a mathematical framework for loop nest optimization in compiler theory. The polytope method models nested loop operations as mathematical objects called polytopes, performs affine transformations on the polytopes, and then converts the transformed polytopes into equivalent, but more efficient, loop nests.

Consider the following example in pseudocode:

for i := 0 to n do
    for j := 0 to i+2 do
        A(i, j) := A(i-1, j) + A(i, j-1)
    end
end

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 will transform the nested loops above into

for t := 0 to 2n+2 do
    for p := max(0, t-n) to min(t, floor(t/2)+1) do
        A(t-p, p) := A(t-p-1, p) + A(t-p, p-1)
    end
end

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, over t, does depend on previous iterations.)

[edit] Detailed example

The dependencies of src, before loop skewing. The red dot corresponds to src[1][0]; the purple dot corresponds to src[2][2].

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 src contains h rows of w pixels, each pixel having a grayscale value between 0 and 255 inclusive. After the routine has finished, the output array dst 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 src array. (Notice that src and dst are both read and written during the computation; src is not read-only, and dst is not write-only.)

Each iteration of the inner loop modifies the values in src[i][j] based on the values of src[i-1][j], src[i][j-1], and src[i+1][j-1]. (The same dependencies apply to dst[i][j]. For the purposes of loop skewing, we can think of src[i][j] and dst[i][j] as the same element.) We can illustrate the dependencies of src[i][j] graphically, as in the diagram on the right.

#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 (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;
        }
    }
}

The dependencies of src, after loop skewing. The array elements will be processed in the order gray, red, green, blue, yellow...

Performing the affine transformation 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.

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;
        }
    }
}

[edit] See also

• Loop nest optimization
• Loop unrolling
• Loop reversal
• Loop tiling

[edit] 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