Possible to specify dependency between two iteration points

[thisi...@gmail.com]

I'm evaluating CLooG as a possible codegen backend for my project right now, and am just wondering the possibility to specify a scattering function/dependency relation between two iteration point. Two use cases are the following:

for(i = 0; i < N; i++) {

   A[i] = i;                 // s1

   B[i] = A[i] * 2;       // s2

}

Clearly s2 depends on s1. From the documentation, it seems like if I specify the scattering function phi(s1) < phi(s2). CLooG will generate two separate loops instead of one:

for(i = 0; i < N; i++) {

   A[i] = i;                 // s1

}

for(i = 0; i < N; i++) {

   B[i] = A[i] * 2;       // s2

}

Is there a way to eliminate this control overhead?

-------

Further more, often times my computation can involve reductions:

for(i = N - 2 ; i >= 0; i--) {

   A[i] = min(A[i + 1], B[i]); // s2

}

I know that an alternative way to specify the above is the following:

for(i = 0 ; i <= N - 1; i++) {

   A[N - i - 1] = min(A[N - i], B[N - i - 1]); // s2

}

But it would be much more convenient if I can specify the dependency between A[i] <- A[i+1] instead and let CLooG do the inference. 

--------

Is the above possible? 

[Sven Verdoolaege]

This is from a while ago, but it seems nobody has responded.

On Fri, Feb 02, 2018 at 11:29:17AM -0800, thisi...@gmail.com wrote:
> I'm evaluating CLooG as a possible codegen backend for my project right
> now, and am just wondering the possibility to specify a scattering
> function/dependency relation between two iteration point. Two use cases are
> the following:
>
> for(i = 0; i < N; i++) {
> A[i] = i; // s1
> B[i] = A[i] * 2; // s2
> }
>
> Clearly s2 depends on s1. From the documentation, it seems like if I
> specify the scattering function phi(s1) < phi(s2). CLooG will generate two
> separate loops instead of one:
>
> for(i = 0; i < N; i++) {
> A[i] = i; // s1
> }
> for(i = 0; i < N; i++) {
> B[i] = A[i] * 2; // s2
> }
>
> Is there a way to eliminate this control overhead?

You just need to specify a different schedule (scattering function).
Here's an illustration using iscc (the CLooG syntax is similar,
but more verbose):

codegen [N] -> { s1[i] -> [0,i] : 0 <= i < N; s2[i] -> [1,i] : 0 <= i < N };
{
for (int c1 = 0; c1 < N; c1 += 1)
s1(c1);
for (int c1 = 0; c1 < N; c1 += 1)
s2(c1);
}
codegen [N] -> { s1[i] -> [i,0] : 0 <= i < N; s2[i] -> [i,1] : 0 <= i < N };
for (int c0 = 0; c0 < N; c0 += 1) {
s1(c0);
s2(c0);

}

> Further more, often times my computation can involve reductions:
>
> for(i = N - 2 ; i >= 0; i--) {
> A[i] = min(A[i + 1], B[i]); // s2
> }
>
> I know that an alternative way to specify the above is the following:
>
> for(i = 0 ; i <= N - 1; i++) {
> A[N - i - 1] = min(A[N - i], B[N - i - 1]); // s2
> }

This has an extra iteration, so it's probably not equivalent.

> But it would be much more convenient if I can specify the dependency
> between A[i] <- A[i+1] instead and let CLooG do the inference.

CLooG take a schedule as input, so you first need to construct
a schedule that respects the dependencies.
There are various ways of constructing such a schedule,
including Farkas based approaches (available in, e.g., Pluto and isl)
and transitive closure based approaches (e.g., TRACO).

skimo