Schedule depends on order of statement domains

[jakob...@gmail.com]

Hello,

I am observing a weird behavior in schedule generation, both by using the ISL library, as well as in the online Barvinok app.

It seems the generated schedule depends simply on the order of statement domain maps in the union map passed to the scheduling function.

This can be reproduced in the Barvinok online app (http://www2.cs.kuleuven.be/cgi-bin/dtai/barvinok.cgi), by comparing the output of the following two snippets which only differ in the order of statement domains:

Snippet 1:

D := {

 a[i0] : i0 >= 0;

 main1[i0] : i0 >= 1;

 main0[0];

 d[0];

};

R := { 

a[i0] -> main1[i0] : i0 >= 1;

 a[0] -> main0[0];

 d[0] -> a[o0] : o0 >= 0;

 main0[0] -> main1[1];

 main1[i0] -> main1[1 + i0] : i0 >= 1

};

S := schedule D respecting R minimizing R;

map S;

Result: { main0[i0] -> [1, 0, 2]; a[i0] -> [1, i0, 0]; main1[i0] -> [1, i0, 1]; d[i0] -> [0, 0, 0] }

Snippet 2:

D := {

 d[0];

 a[i0] : i0 >= 0;

 main1[i0] : i0 >= 1;

 main0[0];

};

R := { 

a[i0] -> main1[i0] : i0 >= 1;

 a[0] -> main0[0];

 d[0] -> a[o0] : o0 >= 0;

 main0[0] -> main1[1];

 main1[i0] -> main1[1 + i0] : i0 >= 1

};

S := schedule D respecting R minimizing R;

map S;

Result: { main1[i0] -> [3, i0]; d[i0] -> [0, 0]; main0[i0] -> [2, 0]; a[i0] -> [1, i0] }

These are two significantly different schedules.

Note that the domains are unbounded - perhaps this is a property unexpected by ISL?

Thank you for any insight,

Jakob

[Sven Verdoolaege]

On Fri, Dec 11, 2015 at 05:41:54PM -0800, jakob...@gmail.com wrote:
> D := {
> d[0];
> a[i0] : i0 >= 0;
> main1[i0] : i0 >= 1;
> main0[0];
> };
>
> R := {
> a[i0] -> main1[i0] : i0 >= 1;
> a[0] -> main0[0];
> d[0] -> a[o0] : o0 >= 0;
> main0[0] -> main1[1];
> main1[i0] -> main1[1 + i0] : i0 >= 1
> };
>
> S := schedule D respecting R minimizing R;
> map S;
>

> *Result:* { main1[i0] -> [3, i0]; d[i0] -> [0, 0]; main0[i0] -> [2, 0];

> a[i0] -> [1, i0] }
>
> These are two significantly different schedules.
>
> Note that the domains are unbounded - perhaps this is a property unexpected
> by ISL?

Sort of. First note that the scheduler typically has some freedom and
so the schedule that you get may indeed depend (in unpredictable ways)
on the internal representation of the input.
In your case, you're imposing an infinite number of proximity dependences
that cannot be optimized. In particular, you want "d[0]" to be close
to an infinite number of distinct instances of "a".
The proximity dependences are therefore ignored and you just get
a schedule that satisfies the validity dependences.
See the second paragraph of 1.5.3 Scheduling for details:

The default algorithm tries to ensure that the dependence distances over coinci-
dence constraints are zero and to minimize the dependence distances over proximity
dependences. Moreover, it tries to obtain sequences (bands) of schedule dimensions
for groups of domains where the dependence distances over validity dependences have
only non-negative values. Note that when minimizing the maximal dependence dis-
tance over proximity dependences, a single affine expression in the parameters is con-
structed that bounds all dependence distances. If no such expression exists, then the
algorithm will fail and resort to an alternative scheduling algorithm. In particular, this
means that adding proximity dependences may eliminate valid solutions. A typical ex-
ample where this phenomenon may occur is when some subset of the proximity depen-
dences has no restriction on some parameter, forcing the coefficient of that parameter
to be zero, while some other subset forces the dependence distance to depend on that
parameter, requiring the same coefficient to be non-zero. When using Feautrier's algo-
rithm, the coincidence and proximity constraints are only taken into account during the
extension to a full-dimensional schedule.

skimo

[Jakob Leben]

On Sat, Dec 12, 2015 at 3:58 AM, Sven Verdoolaege <skim...@kotnet.org> wrote:

Sort of.  First note that the scheduler typically has some freedom and
so the schedule that you get may indeed depend (in unpredictable ways)
on the internal representation of the input.

Even though there may be arbitrary choices that have to be taken by the scheduler (perhaps because they were not constrained by the input and options?), I would expect the algorithm to be deterministic, in the sense that differences that are not significant in the input (essentially, the input is exactly the same - by definition elements of a set are not ordered), do not produce such significant differences in the output.

 

In your case, you're imposing an infinite number of proximity dependences
that cannot be optimized.  In particular, you want "d[0]" to be close
to an infinite number of distinct instances of "a".
The proximity dependences are therefore ignored and you just get
a schedule that satisfies the validity dependences. 

See the second paragraph of 1.5.3 Scheduling for details: ...

Thank you for this explanation. I was wondering whether it would make sense to call it the responsibility of the scheduler to automatically omit the particular proximity constraints that are not satisfiable, instead of dropping all proximity constraints.

Jakob

[Sven Verdoolaege]

On Sat, Dec 12, 2015 at 12:16:46PM -0800, Jakob Leben wrote:
> Thank you for this explanation. I was wondering whether it would make sense
> to call it the responsibility of the scheduler to automatically omit the
> particular proximity constraints that are not satisfiable, instead of
> dropping all proximity constraints.

It may not necessarily be a single constraint, but rather
a combination of constraints, so it's not immediate obvious
how this could be done in general.
Still, I guess it could be useful to try again with fewer
proximity constraints. This is actually on my TODO list somewhere.

However, I do have some patches lying around that may help
you as well in this case. They don't affect the proximity
cosntraints, but they allow the schedule to be constructed
incrementally. In particular, they allow a, main0 and main1
to be merged, even if d cannot be merged with them.

I'm attaching a squashed version of the patches.

With these patches applied and with --isl-no-schedule-whole-component,
your two inputs produce

domain: "{ d[0]; a[i0] : i0 >= 0; main0[0]; main1[i0] : i0 >= 1 }"
child:
sequence:
- filter: "{ d[i0] }"
- filter: "{ a[i0]; main0[i0]; main1[i0] }"
child:
schedule: "[{ a[i0] -> [(i0)]; main0[i0] -> [(0)]; main1[i0] -> [(i0)] }]"
permutable: 1
coincident: [ 1 ]
child:
sequence:
- filter: "{ a[i0] }"
- filter: "{ main1[i0] }"
- filter: "{ main0[i0] }"

I'd be interested to know how this incremental method works
for you in genernal. I've actually been looking for people
interested in testing it for a while now.

skimo

[Jakob Leben]

On Mon, Dec 14, 2015 at 2:13 AM, Sven Verdoolaege <skim...@kotnet.org> wrote:

However, I do have some patches lying around that may help
you as well in this case.  They don't affect the proximity
cosntraints, but they allow the schedule to be constructed
incrementally.  In particular, they allow a, main0 and main1
to be merged, even if d cannot be merged with them.

I'm attaching a squashed version of the patches.

...

I'd be interested to know how this incremental method works
for you in genernal.  I've actually been looking for people
interested in testing it for a while now.

Thanks! I will try that.