<p>This isn't really my area, but I think you want to Google for "the polytope model" or "the polyhedral model", and specifically for "affine-by-statement scheduling". The basic idea is that iterations in a loop nested $d$ deep are turned into a $d$-dimensional polytope, and that each iteration is a point within the polytope. You can then look at data dependencies between the iterations to figure out how to parallelize code (which turn out to correspond to affine transformations of the polytope). </p>

CC BY-SA 3.0
2012-01-31T15:09:29.630Z
2012-01-31T15:09:29.630Z
Neel Krishnaswami
<p>In a general for loop of the form:</p>

<pre><code>for (i = 0, i &lt;= n, i++) {
    for (j = i, j &lt;= n, j++)
        ...
    for (k = i, k &lt;= n, k++)
        ...
}
</code></pre>

<p>What form do the inequalities representing the iteration space take? Or what convex polyhedron represents this?</p>

<p><strong>Background</strong>
I am looking at the <em>Dragon Book</em>'s chapter on parallelisation. This talks in detail of nested loops of the form:</p>

<pre><code>for (i = 0, i &lt;= n, i++) {
    for (j = i, j &lt;= n, j++)
       ...
}
</code></pre>

<p>but not of the form described at the top.</p>

<p>The iteration space of d-deep nested loops can be represented as:
$$
\{ i \in \mathbb{Z}^d \mid Bi + b \geq 0 \}
$$</p>

<p>where B is a $d \times d $ integer matrix and b is a vector of length $d$</p>

<p>My question is basically do I have to do anything different when a loop contains multiple inner loops not nested within each other?</p>

CC BY-SA 3.0
2012-01-31T19:24:41.693Z
Could you please provide some background for the question? You can check the [FAQ] for some tips about writing a good question.
Kaveh
CC BY-SA 3.0
2012-02-01T09:01:37.253Z
Don't you want 0≤i≤n, i≤j≤n, and i≤k≤n, like it says right there in the code?
Jeffε
<dc.parallel-comp><compilers>
How is the iteration space of a nested for-loop containing two sequential nested loops represented?
Magnus
# How is the iteration space of a nested for-loop containing two sequential nested loops represented?

(Asked by: username_0 on 2012-01-31)

In a general for loop of the form:
for (i = 0, i <= n, i++) {
    for (j = i, j <= n, j++)
        ...
    for (k = i, k <= n, k++)
        ...
}

What form do the inequalities representing the iteration space take? Or what convex polyhedron represents this?
Background
I am looking at the Dragon Book's chapter on parallelisation. This talks in detail of nested loops of the form:
for (i = 0, i <= n, i++) {
    for (j = i, j <= n, j++)
       ...
}

but not of the form described at the top.
The iteration space of d-deep nested loops can be represented as:
$$
\{ i \in \mathbb{Z}^d \mid Bi + b \geq 0 \}
$$
where B is a $d \times d $ integer matrix and b is a vector of length $d$
My question is basically do I have to do anything different when a loop contains multiple inner loops not nested within each other?

**Tags:** dc.parallel-comp, compilers

> **Comments:**
> **username_1**: Could you please provide some background for the question? You can check the [FAQ] for some tips about writing a good question.  
> **username_2**: Don't you want 0≤i≤n, i≤j≤n, and i≤k≤n, like it says right there in the code?  

---

## 1 answers

### Answer by username_3 on 2012-01-31. Score: 3

This isn't really my area, but I think you want to Google for "the polytope model" or "the polyhedral model", and specifically for "affine-by-statement scheduling". The basic idea is that iterations in a loop nested $d$ deep are turned into a $d$-dimensional polytope, and that each iteration is a point within the polytope. You can then look at data dependencies between the iterations to figure out how to parallelize code (which turn out to correspond to affine transformations of the polytope).


---

