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

[Sebastian Pop <sebpop at gmail dot com>]

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.

Sebastian