Check access overlapping when the access is in linearized indices.

[Paul Vario]

Given the two perfect loopnests accessing the same array A (the 1st loopnest is a writer, the other is a reader), both accesses are via a linearized index (an affine function of loop index variables; s0, s1, t0, t1 represent strides)

for (int i = 0; i < n0; i++)

    for (int j = 0; j < n1; j++) {

         int linearized_index = offsetS + i * s0 + j * s1

         def A[linearized_index]

     }

for (int i = 0; i < m0; i++)

    for (int j = 0; j < m1; j++) {

         int linearized_index = offsetT + i * t0 + j * t1

         use A[linearized_index]

     }

What's the best way to reason about whether these two loopnests access the same element in the array A or not using ISL?

My current thinking is to represent the loopnests as two isl_basic_set of three dimensions (i.e., two nested loop indices, plus the linearized index as the last dim). And then check if the intersect of the two basic sets is empty or not. Not sure if this is the canonical way of using ISL. Could you please advise me on what's the best approach in ISL for solving these types of problems. Thanks a bunch!

Best Regards,

Paul

[Sven Verdoolaege]

On Wed, Apr 19, 2023 at 10:55:19AM -0700, Paul Vario wrote:
> Given the two perfect loopnests accessing the same array A (the 1st
> loopnest is a writer, the other is a reader), both accesses are via a
> linearized index (an affine function of loop index variables; s0, s1, t0,
> t1 represent strides)
>
> for (int i = 0; i < n0; i++)
> for (int j = 0; j < n1; j++) {
> int linearized_index = offsetS + i * s0 + j * s1

Are s0 and s1 variables or numerical constants?
In the first case, you cannot directly represent the linearized access in isl
and you'd have to delinearize it first.
See, e.g., https://dl.acm.org/doi/10.1145/2751205.2751248

> What's the best way to reason about whether these two loopnests access the
> same element in the array A or not using ISL?

This is not very precise. Do you want to know if the access *any* element
inf common?
If so and If it's possible to represent the accesses,
then I guess you'd check if the ranges of the access relations intersect.

> My current thinking is to represent the loopnests as two isl_basic_set of
> three dimensions (i.e., two nested loop indices, plus the linearized index
> as the last dim). And then check if the intersect of the two basic sets is
> empty or not.

This would only give you common accessed elements that happen
to be accessed by loop iterators with the same values
in both loop nests.

skimo

[Paul Vario]

Thanks very much for the detailed response!

On Wednesday, April 19, 2023 at 5:22:13 PM UTC-4 Sven Verdoolaege wrote:

On Wed, Apr 19, 2023 at 10:55:19AM -0700, Paul Vario wrote:
> Given the two perfect loopnests accessing the same array A (the 1st
> loopnest is a writer, the other is a reader), both accesses are via a
> linearized index (an affine function of loop index variables; s0, s1, t0,
> t1 represent strides)
>
> for (int i = 0; i < n0; i++)
> for (int j = 0; j < n1; j++) {
> int linearized_index = offsetS + i * s0 + j * s1

Are s0 and s1 variables or numerical constants?
In the first case, you cannot directly represent the linearized access in isl
and you'd have to delinearize it first.
See, e.g., https://dl.acm.org/doi/10.1145/2751205.2751248

Thanks a lot for the paper. s0, s1 and offsetS are numerical constants (at the isl set construction time in the code). We have the plan to later extend this access overlap check to the situation where s0, s1 and offsetS are variables (this probably requires us to represent them as parameters at the isl set construction time).

 

> What's the best way to reason about whether these two loopnests access the
> same element in the array A or not using ISL?

This is not very precise. Do you want to know if the access *any* element
inf common?
If so and If it's possible to represent the accesses,
then I guess you'd check if the ranges of the access relations intersect.

Yes, exactly. The ask is to check whether they access *any* element in common (e.g., if there is, then a dependence edge needs to be drawn between them on the DDG).

Representing them as accesses sounds exactly I should be doing :-). IIUC, per your recommendation, the two accesses should first be translated to isl_map (since they belongs to different space), then call upon isl map utility functions to check if there's any common element access between the two maps? if my understanding is on track, which isl map utility functions are better fits for the check (do they optimize to check the ranges of the access relations as opposed to checking each individual pairs of accesses one by one)?

btw, is there any example in the isl unit tests that does the same:  "check if the ranges of the access relations intersect."?

 

> My current thinking is to represent the loopnests as two isl_basic_set of
> three dimensions (i.e., two nested loop indices, plus the linearized index
> as the last dim). And then check if the intersect of the two basic sets is
> empty or not.

This would only give you common accessed elements that happen
to be accessed by loop iterators with the same values
in both loop nests.

oic, that makes sense. But given that I define the basic set with the linearized index as an extra dimension, is there a way for ISL to just check if there exists an integer value that is common along that *linearized* dimension?

 

skimo

Thanks again skimo!

Paul 

[Sven Verdoolaege]

On Thu, Apr 20, 2023 at 09:46:53AM -0700, Jiading Gai wrote:
> > What's the best way to reason about whether these two loopnests access
> the
> > same element in the array A or not using ISL?
>
> This is not very precise. Do you want to know if the access *any* element
> inf common?
> If so and If it's possible to represent the accesses,
> then I guess you'd check if the ranges of the access relations intersect.
>
>

> Yes, exactly. The ask is to check whether they access *any* element in
> common (e.g., if there is, then a dependence edge needs to be drawn between
> them on the DDG).
> Representing them as accesses sounds exactly I should be doing :-). IIUC,
> per your recommendation, the two accesses should first be translated to
> isl_map (since they belongs to different space), then call upon isl map
> utility functions to check if there's any common element access between the
> two maps? if my understanding is on track, which isl map utility functions
> are better fits for the check (do they optimize to check the ranges of the
> access relations as opposed to checking each individual pairs of accesses
> one by one)?
>

> btw, is there any example in the isl unit tests that does the same: "check
> if the ranges of the access relations intersect."?

The document "Presburger formulas and polyhedral compilation" describes
most supported operations in detail.

I guess you want to do something like the following (in iscc syntax):

A1 := [n0,n1] -> { S1[i=0:n0-1,j=0:n1-1] -> A[5 + 10 i + 20 j] };
A2 := [m0,m1] -> { S2[i=0:m0-1,j=0:m1-1] -> A[1 + 2 i + 16 j] };
(ran A1) * (ran A2);
$0 := [m0, m1, n0, n1] -> { A[i0] : exists (e0, e1: (5 + i0) mod 10 = 0 and 0 <= e0 < n1 and 5 - 10n0 + i0 <= 20e0 <= -5 + i0 and 0 <= e1 < m1 and -2m0 + i0 < 16e1 < i0) }

> > My current thinking is to represent the loopnests as two isl_basic_set of
> > three dimensions (i.e., two nested loop indices, plus the linearized
> index
> > as the last dim). And then check if the intersect of the two basic sets
> is
> > empty or not.
>
> This would only give you common accessed elements that happen
> to be accessed by loop iterators with the same values
> in both loop nests.
>

> oic, that makes sense. But given that I define the basic set with the
> linearized index as an extra dimension, is there a way for ISL to just
> check if there exists an integer value that is common along that
> *linearized* dimension?

You shouldn't put variables with completely different meanings
in the same tuple. That's both difficult to reason about and
difficult to express in isl.

skimo