llvm dev - Jun 2016 - [GSoC 2016] Implementation of the packing transformation

2016-06-27 15:52 GMT+05:00 4lbert C0hen <4lbert.h.c0hen at
gmail.com>:
> Dear Roman and all,
>
> Such features would be extremely useful to implement array expansion
(scalar
> and array renaming, privatization with new subscript expressions of higher
> dimension) and storage mapping optimization (generalizing array
> contraction). It would be interesting to have these future applications in
> mind when working on the packing transformation.
Thank you for the comment! Could you please advise me where I can find
definitions of array expansion and storage mapping optimization?

I've found the following papers that are probably related to this: [1]
and [2]. However, maybe I missed something.

Refs.:

[1] -
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.5704&rep=rep1&type=pdf
[2] - https://hal.archives-ouvertes.fr/hal-01257316/document

-- 
                                    Cheers, Roman Gareev.

On 06/28/2016 10:53 AM, Roman Gareev wrote:
> 2016-06-27 15:52 GMT+05:00 4lbert C0hen <4lbert.h.c0hen at
gmail.com>:
>> Dear Roman and all,
>>
>> Such features would be extremely useful to implement array expansion
(scalar
>> and array renaming, privatization with new subscript expressions of
higher
>> dimension) and storage mapping optimization (generalizing array
>> contraction). It would be interesting to have these future applications
in
>> mind when working on the packing transformation.
>
> Thank you for the comment! Could you please advise me where I can find
> definitions of array expansion and storage mapping optimization?
>
> I've found the following papers that are probably related to this: [1]
> and [2]. However, maybe I missed something.
>
> Refs.:
> [1] -
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.5704&rep=rep1&type=pdf
Yes, this is one of the must-read papers for any polyhedral compilation 
work!

The following is a generalization to approximate array dataflow (journal 
extension of a POPL 1998 paper)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.26.6376&rep=rep1&type=pdf
Rather theoretical, and can be simplified to not make explicit usage of 
transitive closure computations. There is much research to be done in 
the area, with short term applications and implementation in production. 
E.g., on-demand expansion on top of the Live Range Reordering technique 
implemented in isl and PPCG (papers and slides below):
http://impact.gforge.inria.fr/impact2016
> [2] - https://hal.archives-ouvertes.fr/hal-01257316/document
That one is rather specific to parallel programs and also theoretical.

State of the art:

- POPL 2016
http://conf.researchr.org/event/POPL-2016/popl-2016-papers-smo-an-integrated-approach-to-intra-array-and-inter-array-storage-optimization
http://dl.acm.org/citation.cfm?id=2837636

There is a tool available but it has received little publicity yet:
https://github.com/bondhugula/smo
Yet the input is in for of polyhedral sets/maps, not code.

- CC 2016, Darte, Isoard, Yuki
https://www.conference-publishing.com/list.php?Event=CC16
Better heuristic. Currently limited to single-array SMO.

Again, much potential for research and implementation.

I'll be glad to discuss transfer of these results to Polly, as well as 
Alexandre, Uday and others on this list.

Albert

2016-06-29 13:02 GMT+05:00 4lbert C0hen <4lbert.h.c0hen at
gmail.com>:
> On 06/28/2016 10:53 AM, Roman Gareev wrote:
>>
>> 2016-06-27 15:52 GMT+05:00 4lbert C0hen <4lbert.h.c0hen at
gmail.com>:
>>>
>>> Dear Roman and all,
>>>
>>> Such features would be extremely useful to implement array
expansion
>>> (scalar
>>> and array renaming, privatization with new subscript expressions of
>>> higher
>>> dimension) and storage mapping optimization (generalizing array
>>> contraction). It would be interesting to have these future
applications
>>> in
>>> mind when working on the packing transformation.
>>
>>
>> Thank you for the comment! Could you please advise me where I can find
>> definitions of array expansion and storage mapping optimization?
>>
>> I've found the following papers that are probably related to this:
[1]
>> and [2]. However, maybe I missed something.
>>
>> Refs.:
>
>
>> [1] -
>>
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.5704&rep=rep1&type=pdf
>
> Yes, this is one of the must-read papers for any polyhedral compilation
> work!
>
> The following is a generalization to approximate array dataflow (journal
> extension of a POPL 1998 paper)
>
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.26.6376&rep=rep1&type=pdf
> Rather theoretical, and can be simplified to not make explicit usage of
> transitive closure computations. There is much research to be done in the
> area, with short term applications and implementation in production. E.g.,
> on-demand expansion on top of the Live Range Reordering technique
> implemented in isl and PPCG (papers and slides below):
> http://impact.gforge.inria.fr/impact2016
>
>> [2] - https://hal.archives-ouvertes.fr/hal-01257316/document
>
> That one is rather specific to parallel programs and also theoretical.
>
> State of the art:
>
> - POPL 2016
>
http://conf.researchr.org/event/POPL-2016/popl-2016-papers-smo-an-integrated-approach-to-intra-array-and-inter-array-storage-optimization
> http://dl.acm.org/citation.cfm?id=2837636
>
> There is a tool available but it has received little publicity yet:
> https://github.com/bondhugula/smo
> Yet the input is in for of polyhedral sets/maps, not code.
>
> - CC 2016, Darte, Isoard, Yuki
> https://www.conference-publishing.com/list.php?Event=CC16
> Better heuristic. Currently limited to single-array SMO.
>
> Again, much potential for research and implementation.
>
> I'll be glad to discuss transfer of these results to Polly, as well as
> Alexandre, Uday and others on this list.
>
Thank you for the information! I'll try to take these applications into
account.

-- 
                                    Cheers, Roman Gareev.