Checking schedule legality

[Emil Vatai]

Dear Sven,

Assume there is a (1) `pet_scop` which I got from a C file using `pet_scop_extract_from_C_source` (or a similar method), and (2) an `isl_schedule` obtained `isl_schedule_read_from_file` (or `isl_schedule_read_from_str`).

Can I check in ISL (and if I can how) whether the schedule is a legal schedule considering the dependencies of the scop?

Best,

Emil

[Sven Verdoolaege]

You should be able to check the validity using isl.
Can the schedule involve extension nodes?
How about expansion nodes?

How are the dependencies represented?

If you only have validity dependences and the schedule does not contain
any extension or expansion node, then the easiest (but not neceessarily
most efficient) way is probably to call isl_schedule_get_map
on the schedule, apply that to both sides of the validity dependences,
take the differences and check that they are all lexicographically positive.

skimo

[Emil Vatai]

Dear Sven,

Thanks for the quick response!

You should be able to check the validity using isl.

Exactly what I'm looking for, hence my question :)

 

Can the schedule involve extension nodes?
How about expansion nodes?

Ultimately, (I think) I'm looking for the most general case possible, but as a first step I'll be very happy with the simplest case possible (so I guess no extension/expansion nodes for now). Also I'll need to read up on extension/expansion nodes (to understand how they make life easier/harder and might come back with more questions -- but that's a problem for later)

 

How are the dependencies represented?

Exactly! This is the narrowed down version of my question: if I have a pet_scop, how can I read/get/compute the dependencies from a pet_scop using ISL? The rest, I should be OK with, i.e. theta is legal if for all (s, t) edges of the dependency graph, satisfy theta(t) - theta(s) > 0, right? (I don't know how to get the dependency graph using ISL).

If you only have validity dependences and the schedule does not contain
any extension or expansion node, then the easiest (but not neceessarily
most efficient) way is probably to call isl_schedule_get_map
on the schedule, apply that to both sides of the validity dependences,
take the differences and check that they are all lexicographically positive.

I was looking at PPCG (and Pluto) to find the pieces of code where the dependency graph is computed, but now I'm not even sure they create the dependency graph explicitly. If you can point me to the right place in the PPCG repo (assuming there is code there which is relevant for my question) that would also be of great help.

Or should I be just reading the last chapter of "Presburger Formulas and Polyhedral Compilation" a bit more instead of spamming the mailing list? <thinking emoji>

Best,

Emil

[Sven Verdoolaege]

On Wed, May 24, 2023 at 11:01:31AM +0200, Emil Vatai wrote:
> > If you only have validity dependences and the schedule does not contain
> > any extension or expansion node, then the easiest (but not neceessarily
> > most efficient) way is probably to call isl_schedule_get_map
> > on the schedule, apply that to both sides of the validity dependences,
> > take the differences and check that they are all lexicographically
> > positive.
> >
>
> I was looking at PPCG (and Pluto) to find the pieces of code where the
> dependency graph is computed, but now I'm not even sure they create the
> dependency graph explicitly. If you can point me to the right place in the
> PPCG repo (assuming there is code there which is relevant for my question)
> that would also be of great help.

In PPCG, the dependences are computed in a function
called "compute_dependences".

> Or should I be just reading the last chapter of "Presburger Formulas and
> Polyhedral Compilation" a bit more instead of spamming the mailing list?

This is probably the best place to start, yes.
You first need to decide what kind of dependences you want to compute.
What PPCG implements is just one possible option (well, actually, it's three).

skimo

[Emil Vatai]

Dear Sven,

After looking at `compute_dependencies` in the PPCG source code, and reading the very nice "Presburger Formulas and Polyhedral Compilation" I think I have a minimal working example of getting data dependencies. But now I'm stuck with the

> If you only have validity dependences and the schedule does not contain
> any extension or expansion node, then the easiest (but not neceessarily
> most efficient) way is probably to call isl_schedule_get_map
> on the schedule, apply that to both sides of the validity dependences,
> take the differences and check that they are all lexicographically positive.

part.

I have the dependency as an `isl_union_map` and so is the schedule (after `isl_schedule_get_map`), and now how do I "apply that to both sides"? I tried getting the domain/range, but that just returned different sets. I'm now trying to convert them into `isl_union_pw_multi_aff` and/or `isl_multi_union_pw_aff` but without much success... Or to be more precise, the conversion works (I would say it is easy), but the part when I have to get two objects, and then apply the schedule to them and take the difference is where I'm failing. ISL is quite intuitive, when I know what I'm doing, but currently that is not the case. So my question is, how do I get both sides? What type should a "side" be? (from there I hope I'll be able to figure out how to apply the schedule (map), take the difference and check lexicographical positivity).

Assume a very simple case, e.g.:

     dependency: [N] -> { S_0[i, j] -> S_0[i' = 1 + i, j' = j] : 0 < i <= -2 + N and 0 <= j < N }

     schedule: [N] -> { S_0[i, j] -> [i, j] }

(although I'm a bit confused why I got i' = 1 + i and not i' = i - 1, but maybe I'm mixing up the role of i and i', the code is this:

  for (size_t i = 1; i < N; i++) {
    for (size_t j = 0; j < N; j++) {
      A[i][j] = A[i][j] + A[i - 1][j];
    }
  }

)

Best,

Emil

--

Emil Vatai

[Sven Verdoolaege]

On Tue, Jun 06, 2023 at 09:58:08PM +0900, Emil Vatai wrote:
> I have the dependency as an `isl_union_map` and so is the schedule (after
> `isl_schedule_get_map`), and now how do I "apply that to both sides"? I
> tried getting the domain/range, but that just returned different sets. I'm
> now trying to convert them into `isl_union_pw_multi_aff` and/or
> `isl_multi_union_pw_aff` but without much success... Or to be more precise,
> the conversion works (I would say it is easy), but the part when I have to
> get two objects, and then apply the schedule to them and take the
> difference is where I'm failing. ISL is quite intuitive, when I know what
> I'm doing, but currently that is not the case. So my question is, how do I
> get both sides? What type should a "side" be? (from there I hope I'll be
> able to figure out how to apply the schedule (map), take the difference and
> check lexicographical positivity).
>
> Assume a very simple case, e.g.:
> dependency: [N] -> { S_0[i, j] -> S_0[i' = 1 + i, j' = j] : 0 < i <=
> -2 + N and 0 <= j < N }
> schedule: [N] -> { S_0[i, j] -> [i, j] }
>
> (although I'm a bit confused why I got i' = 1 + i and not i' = i - 1, but
> maybe I'm mixing up the role of i and i', the code is this:

These dependences map dependees to dependers, perhaps you're expecting
them to go the other way.

>>> import isl
>>> s = isl.union_map("[N] -> { S_0[i, j] -> [i, j] }")
>>> d = isl.union_map("[N] -> { S_0[i, j] -> S_0[i' = 1 + i, j' = j] : 0 < i <= -2 + N and 0 <= j < N }")
>>> d.apply_domain(s).apply_range(s)
isl.union_map("[N] -> { [i0, i1] -> [1 + i0, i1] : 0 < i0 <= -2 + N and 0 <= i1 < N }")
>>> d.apply_domain(s).apply_range(s).deltas()
isl.union_set("[N] -> { [1, 0] : N >= 3 }")

skimo

[Emil Vatai]

Dear Skimo,

Huge thanks! All worked like a charm! Now back to your first reply:

--

> If you only have validity dependences and

Would it be an acceptable thing to do, to feed the may_reads, may_writes, must_writes (which I get from pet_scop_get_* functions) to isl_union_access_info_compute_flow as described in [1] and use the isl_union_flow_get_may_dependence as the validity dependence?

--

> the schedule does not contain any extension or expansion node, 

Can PET read schedules with extension or expansion nodes from C source (e.g. using pet_scop_extract_from_C_source), or are they nodes which you'd generate when performing a more complex code transformation?

--

> then the easiest (but not neceessarily most efficient) way is probably to call isl_schedule_get_map on the schedule, apply that to both sides of the validity dependences, take the differences and check that they are all lexicographically positive.

Any pointers on how to do it in a more efficient way? My idea was maybe taking the dependency relation apart (the union_map into maps) and somehow process the maps in tandem with the schedule (without converting it into a schedule_map). How far am I with this idea?

--

[1] Presburger Formulas and Polyhedral Compilation

--

Again, thanks for all the help!

Best,

Emil

--

Emil Vatai

[Sven Verdoolaege]

On Thu, Jun 15, 2023 at 09:32:37PM +0900, Emil Vatai wrote:
> > If you only have validity dependences and
>
> Would it be an acceptable thing to do, to feed the may_reads, may_writes,
> must_writes (which I get from pet_scop_get_* functions) to
> isl_union_access_info_compute_flow as described in [1] and use the
> isl_union_flow_get_may_dependence as the validity dependence?

Sounds reasonable.

> > the schedule does not contain any extension or expansion node,
>
> Can PET read schedules with extension or expansion nodes from C source
> (e.g. using pet_scop_extract_from_C_source), or are they nodes which you'd
> generate when performing a more complex code transformation?

The schedules extracted by pet shouldn't include such nodes.

> > then the easiest (but not neceessarily most efficient) way is probably to call
> isl_schedule_get_map on the schedule, apply that to both sides of the
> validity dependences, take the differences and check that they are all
> lexicographically positive.
>
> Any pointers on how to do it in a more efficient way? My idea was maybe
> taking the dependency relation apart (the union_map into maps) and somehow

Why would you do that?

> process the maps in tandem with the schedule (without converting it into a
> schedule_map). How far am I with this idea?

Traversing the nodes of the schedule is probably more effecient, yes.
If you don't have extension or expansion nodes, you can probably
just traverse it top-down. If you do have such nodes, it gets
a bit more complicated.

skimo