Re: isl scheduler and spatial locality (Re: [PATCH][GRAPHITE] More TLC)
On Sun, Oct 01, 2017 at 11:58:30AM +0200, Sven Verdoolaege wrote: > For the approach pluto is taking, you'll have to look at the source > code, see pluto_intra_tile_optimize_band. > For the other two approaches I mentioned above, reports will > be made available within the next couple of weeks. https://hal.inria.fr/hal-01628798 http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW709.abs.html skimo
Re: isl scheduler and spatial locality (Re: [PATCH][GRAPHITE] More TLC)
On Sat, Sep 30, 2017 at 07:47:43PM +0200, Richard Biener wrote:
> On September 29, 2017 9:58:41 PM GMT+02:00, Sebastian Pop
> wrote:
> >On Fri, Sep 29, 2017 at 2:37 PM, Sven Verdoolaege
> > wrote:
> >> [Sorry for the resend; I used the wrong email address to CC Alex]
> >>
> >> On Wed, Sep 27, 2017 at 02:18:51PM +0200, Richard Biener wrote:
> >>> Ah, so I now see why we do not perform interchange on trivial cases
> >like
> >>>
> >>> double A[1024][1024], B[1024][1024];
> >>>
> >>> void foo(void)
> >>> {
> >>> for (int i = 0; i < 1024; ++i)
> >>> for (int j = 0; j < 1024; ++j)
> >>> A[j][i] = B[j][i];
> >>> }
> >>
> >> I didn't see you mentioning _why_ you expect an interchange here.
> >> Are you prehaps interested in spatial locality?
> >> If so, then there are several approaches for taking
> >> that into account.
> >> - pluto performs an intra-tile loop interchange to
> >> improve temporal and/or spatial locality. It shouldn't
> >> be too hard to do something similar on an isl generated
> >> schedule
> >> - Alex (Oleksandr) has been working on an extension of
> >> the isl scheduler that takes into account spatial locality.
> >> I'm not sure if it's publicly available.
> >> - I've been working on a special case of spatial locality
> >> (consecutivity). The current version is available in
> >> the consecutivity branch. Note that it may get rebased and
> >> it may not necessarily get merged into master.
> >>
> >> There are also other approaches, but they may not be that
> >> easy to combine with the isl scheduler.
> >
> >Would the following work?
> >Add to the proximity relation the array accesses from two
> >successive iterations of the innermost loop:
> >A[j][i] -> A[j][i+1] and B[j][i] -> B[j][i+1]
> >With these two extra relations in the proximity map,
> >isl should be able to interchange the above loop.
>
> Can anyone give a hint on how to do that in ISL terms?
For the approach pluto is taking, you'll have to look at the source
code, see pluto_intra_tile_optimize_band.
For the other two approaches I mentioned above, reports will
be made available within the next couple of weeks.
For the last one, there is a sample implementation in the
consecutivity branch of PPCG.
skimo
Re: isl scheduler and spatial locality (Re: [PATCH][GRAPHITE] More TLC)
On September 29, 2017 9:58:41 PM GMT+02:00, Sebastian Pop
wrote:
>On Fri, Sep 29, 2017 at 2:37 PM, Sven Verdoolaege
> wrote:
>> [Sorry for the resend; I used the wrong email address to CC Alex]
>>
>> On Wed, Sep 27, 2017 at 02:18:51PM +0200, Richard Biener wrote:
>>> Ah, so I now see why we do not perform interchange on trivial cases
>like
>>>
>>> double A[1024][1024], B[1024][1024];
>>>
>>> void foo(void)
>>> {
>>> for (int i = 0; i < 1024; ++i)
>>> for (int j = 0; j < 1024; ++j)
>>> A[j][i] = B[j][i];
>>> }
>>
>> I didn't see you mentioning _why_ you expect an interchange here.
>> Are you prehaps interested in spatial locality?
>> If so, then there are several approaches for taking
>> that into account.
>> - pluto performs an intra-tile loop interchange to
>> improve temporal and/or spatial locality. It shouldn't
>> be too hard to do something similar on an isl generated
>> schedule
>> - Alex (Oleksandr) has been working on an extension of
>> the isl scheduler that takes into account spatial locality.
>> I'm not sure if it's publicly available.
>> - I've been working on a special case of spatial locality
>> (consecutivity). The current version is available in
>> the consecutivity branch. Note that it may get rebased and
>> it may not necessarily get merged into master.
>>
>> There are also other approaches, but they may not be that
>> easy to combine with the isl scheduler.
>
>Would the following work?
>Add to the proximity relation the array accesses from two
>successive iterations of the innermost loop:
>A[j][i] -> A[j][i+1] and B[j][i] -> B[j][i+1]
>With these two extra relations in the proximity map,
>isl should be able to interchange the above loop.
Can anyone give a hint on how to do that in ISL terms?
Richard.
>Sebastian
Re: isl scheduler and spatial locality (Re: [PATCH][GRAPHITE] More TLC)
On 29/09/17 21:58, Sebastian Pop wrote:
On Fri, Sep 29, 2017 at 2:37 PM, Sven Verdoolaege
wrote:
[Sorry for the resend; I used the wrong email address to CC Alex]
On Wed, Sep 27, 2017 at 02:18:51PM +0200, Richard Biener wrote:
Ah, so I now see why we do not perform interchange on trivial cases like
double A[1024][1024], B[1024][1024];
void foo(void)
{
for (int i = 0; i < 1024; ++i)
for (int j = 0; j < 1024; ++j)
A[j][i] = B[j][i];
}
I didn't see you mentioning _why_ you expect an interchange here.
Are you prehaps interested in spatial locality?
If so, then there are several approaches for taking
that into account.
- pluto performs an intra-tile loop interchange to
improve temporal and/or spatial locality. It shouldn't
be too hard to do something similar on an isl generated
schedule
- Alex (Oleksandr) has been working on an extension of
the isl scheduler that takes into account spatial locality.
I'm not sure if it's publicly available.
- I've been working on a special case of spatial locality
(consecutivity). The current version is available in
the consecutivity branch. Note that it may get rebased and
it may not necessarily get merged into master.
There are also other approaches, but they may not be that
easy to combine with the isl scheduler.
Would the following work?
Add to the proximity relation the array accesses from two
successive iterations of the innermost loop:
A[j][i] -> A[j][i+1] and B[j][i] -> B[j][i+1]
With these two extra relations in the proximity map,
isl should be able to interchange the above loop.
Sebastian
Hi,
this looks very close to what we do for spatial locality in the
scheduler, except that we separate proximity and "spatial proximity"
maps. There is a couple of caveats in just plugging those into
proximity, in particular resolving conflicts between spatial and
temporal locality and unnecessary skewing.
Cheers,
Alex
--
Oleksandr Zinenko,
Inria / École Normale Supérieure,
cont...@ozinenko.com, oleksandr.zine...@inria.fr
https://www.ozinenko.com
Re: isl scheduler and spatial locality (Re: [PATCH][GRAPHITE] More TLC)
On Fri, Sep 29, 2017 at 2:37 PM, Sven Verdoolaege
wrote:
> [Sorry for the resend; I used the wrong email address to CC Alex]
>
> On Wed, Sep 27, 2017 at 02:18:51PM +0200, Richard Biener wrote:
>> Ah, so I now see why we do not perform interchange on trivial cases like
>>
>> double A[1024][1024], B[1024][1024];
>>
>> void foo(void)
>> {
>> for (int i = 0; i < 1024; ++i)
>> for (int j = 0; j < 1024; ++j)
>> A[j][i] = B[j][i];
>> }
>
> I didn't see you mentioning _why_ you expect an interchange here.
> Are you prehaps interested in spatial locality?
> If so, then there are several approaches for taking
> that into account.
> - pluto performs an intra-tile loop interchange to
> improve temporal and/or spatial locality. It shouldn't
> be too hard to do something similar on an isl generated
> schedule
> - Alex (Oleksandr) has been working on an extension of
> the isl scheduler that takes into account spatial locality.
> I'm not sure if it's publicly available.
> - I've been working on a special case of spatial locality
> (consecutivity). The current version is available in
> the consecutivity branch. Note that it may get rebased and
> it may not necessarily get merged into master.
>
> There are also other approaches, but they may not be that
> easy to combine with the isl scheduler.
Would the following work?
Add to the proximity relation the array accesses from two
successive iterations of the innermost loop:
A[j][i] -> A[j][i+1] and B[j][i] -> B[j][i+1]
With these two extra relations in the proximity map,
isl should be able to interchange the above loop.
Sebastian
