Polyhedral Compilation (opens in new tab)

Oh, cool. This came up in a conversation a work somewhat recently, which is where I first heard the term. The basic idea is slick but straightforward:

Say you have a multidimensional array, A[i][j] for concreteness. A loop over the array will typically look like nested loops, e.g. assuming we start with a properly initialized array, something like

    for(i=0; i<I; i++) {
        for(j=i; j<2*i; j++) {
            A[i+1][j+2]+=A[i][j];
        }
    }

Since A[i+1][j+1] has a data dependency on both i and j indicies, the loop has to be executed sequentially over both i and j. However, drawing out the data flow shows how a change of perspective can make the inner loop completely vectorizable. First, let's draw the traversed indices on a grid like

    . . . . . o o o o o
    . . . . o o o o o .
    . . . . o o o o . .
    . . . o o o o . . .
    . . . o o o . . . .
    . . o o o . . . . .
    . . o o . . . . . .
    . o o . . . . . . .
    . o . . . . . . . .
    o . . . . . . . . .

Notice that we get a polygon in this 2D case. Drawing with more indices and a higher-dimensional pen will give you polyhedron, whence the name! Now connect marked indices that have a data dependency; zooming into the bottom-left corner, it looks something like the below in our example:

    .   . / o / o
         / / /
    .   o / o   .
       / /
    . / o   .   .
     /
    o   .   .   .

The key insight here is that we have a bunch of parallel lines, meaning we should be able to start our calculation at all the bottom left points and flow up-and-right (at slope 2!) along each line in parallel. Doing this in code means we want all those lines to be parallel with grid lines as much as possible, reducing the problem to a simple linear transformation of the polygon!

In particular, the indices correspond to the grid points and the polygon our data. We want data to be flowing perpendicular to an index in order to parallelize said axis, so crunching out the details of a solution for our example gives

    for(i=0; i<I; i++) {
        for(j=i; j<2*(i-I); i++, j+=2) {
            A[i+1][j]+=A[i][j];
        }
    }

Notice that array in the inner loop no longer data between j indices any more! That lets us run the entire thing in parallel.

That's the basic idea anyway.

Small related a thread a few months ago https://news.ycombinator.com/item?id=40848340

As someone that frequently searches for code and algorithms related to actual polyhedra, I find this choice of terminology rather irritating.

Most likely this API is used then https://libisl.sourceforge.io/user.html#Polyhedral-Compilati...

I have no idea what this is, and I still have no idea after reading the website.

It reads like one of those fake AI written papers about nonsense that seem kinda real at first glance.