Tools for understanding why Scheduling fails

[Pedro Silvestre]

Hi all, Sven,

I'm using islpy to schedule computations (though I'm open to answers that only apply to isl's C interface).

When scheduling fails, a terse error message ("islpy._isl.Error: call to isl_schedule_constraints_compute_schedule failed: unable to carry dependences in /project/isl/isl_scheduler.c:5199") is displayed. This is a problem I am facing quite frequently.

What tools are there for understanding why scheduling a certain computation is impossible?  For example, is there a way to isolate a specific cycle of dependencies that is causing the issue? Or is there a way to enable more verbose error messages?

Right now, I am attempting to schedule (a much more complex form of) the following computation:

```

dom_str = """
    [D0, D1, D2] -> {
        A[i0] : 0 <= i0 <= 4;
        B[i0, i1] : 0 <= i0 <= 4 and 0 <= i1 <= 8;
        C[i0, i1] : 0 <= i0 <= 4 and 0 <= i1 <= 9;
        D[i0, i1 = 0, i2] : 0 <= i0 <= 4 and 0 <= i2 <= 9;
        E[i0] : 0 <= i0 <= 2;
        F[i0, i1, i2] : 0 <= i0 <= 4 and 0 <= i1 <= 1 and 0 <= i2 <= 9;
        G[i0] : 0 <= i0 <= 1;
        H[i0, i1] : 0 <= i0 <= 4 and 0 <= i1 <= 9;
        I[i0, i1, i2] : 0 <= i0 <= 4 and 0 <= i1 <= 1 and 0 <= i2 <= 9;
    }
    """
    val_str = """
    [D0, D1, D2] -> {
        I[i0, i1 = 0, i2] -> D[d0 = i0, d1, d2 = i2];
        C[i0, i1] -> I[d0 = i0, d1, d2 = i1];
        H[i0, i1] -> I[d0 = i0, d1, d2 = i1];
        F[i0, i1, i2] -> G[d1 = i1];
        G[i0] -> E[d1 = 1 + i0];
        I[i0, i1, i2] -> F[d0 = i0, d1 = i1, d2 = i2];
        D[i0, i1, i2] -> H[d0 = i0, d2 = i2];
        E[i0] -> I[d0, d1 = i0, d2];
        C[i0, i1] -> F[d0 = i0, d1, d2 = i1];
        A[i0] -> C[d0 = i0, d2 = 0];
        D[i0, i1, i2] -> B[d0 = i0, d2 = i2];
        B[i0, i1] -> C[d0 = i0, d2 = 1 + i1];
    }
    """

    dom = isl.UnionSet(dom_str)
    val = isl.UnionMap(val_str)

    sc = isl.ScheduleConstraints.on_domain(dom)
    sc = sc.set_validity(val)
    print(sc.compute_schedule())

```

And cannot wrap my head around why it is impossible. I would appreciate help that relates directly to understanding this as well.

Thanks in advance for any help in this.

[Sven Verdoolaege]

On Sun, Mar 17, 2024 at 11:57:13AM -0700, Pedro Silvestre wrote:
> Hi all, Sven,
>
> I'm using islpy to schedule computations (though I'm open to answers that
> only apply to isl's C interface).
>
> When scheduling fails, a terse error message ("islpy._isl.Error: call to
> isl_schedule_constraints_compute_schedule failed: unable to carry
> dependences in /project/isl/isl_scheduler.c:5199") is displayed. This is a
> problem I am facing quite frequently.

I agree that this is suboptimal. The interface assumes that a solution
can be found, while that may not necessarily be the case.

> What tools are there for understanding why scheduling a certain computation
> is impossible? For example, is there a way to isolate a specific cycle of
> dependencies that is causing the issue? Or is there a way to enable more
> verbose error messages?

You could simply consider successive powers of the validity constraints
until you hit a cycle.

You have mutually dependent instances, so there is no way to schedule
them apart.

Here are all triples of instances that form a cycle:

[D0, D1, D2] -> { D[i0 = 0:4, i1 = 0, i2 = 0:9] -> [H[d0 = i0, d2 = i2] -> I[i0' = i0, i1' = 0, i2' = i2]]; I[i0 = 0:4, i1 = 0, i2 = 0:9] -> [D[d0 = i0, d1 = 0, d2 = i2] -> H[i0' = i0, i1' = i2]]; H[i0 = 0:4, i1 = 0:9] -> [I[d0 = i0, d1 = 0, d2 = i1] -> D[i0' = i0, i1' = 0, i2 = i1]] }

Here's one of them:

[D0 = 0, D1 = 0, D2 = 0] -> { D[i0 = 4, i1 = 0, i2 = 0] -> [H[d0 = 4, d2 = 0] -> I[i0' = 4, i1' = 0, i2' = 0]] }

skimo