1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Could you please provide some background for the question? You can check the FAQ for some tips about writing a good question. $\endgroup$ – Kaveh Jan 31 '12 at 19:24
  • 1
    $\begingroup$ Don't you want 0≤i≤n, i≤j≤n, and i≤k≤n, like it says right there in the code? $\endgroup$ – Jeffε Feb 1 '12 at 9:01
3
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.