isl scheduler and spatial locality (Re: [PATCH][GRAPHITE] More TLC)

[Sven Verdoolaege]

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 <sebpop@gmail.com> wrote:
> >On Fri, Sep 29, 2017 at 2:37 PM, Sven Verdoolaege
> ><sven.verdoolaege@gmail.com> 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