llvm dev - May 2012 - [LLVMdev] SIV tests in LoopDependence Analysis, Sanjoy's patch

On Mon, 14 May 2012 11:46:02 -0700
Preston Briggs <preston.briggs at gmail.com> wrote:
> On Sat, Apr 21, 2012 at 6:08 AM, Sanjoy Das
> <sanjoy at playingwithpointers.com> wrote:
> >
> > Sorry for having been quiet for so long, I have my university exams
> > going on, and will be able to contribute only after the coming
> > Friday.
> 
> Gents,
> 
> While you've been fooling around with exams, I have been focused with
> laser-like intensity, or something...
> Here are new versions of 4 SIV tests:
> 
>    - the Strong SIV test:
>    https://sites.google.com/site/parallelizationforllvm/strong-siv-test
>    - the Weak-Zero SIV test:
>    https://sites.google.com/site/parallelizationforllvm/weak-zero-siv-test
>    - the Weak-Crossing SIV test:
>   
https://sites.google.com/site/parallelizationforllvm/weak-crossing-siv-test
>    - the Exact SIV test:
>    https://sites.google.com/site/parallelizationforllvm/weak-siv-test
> 
> and our first MIV test:
> 
>    - the RDIV test:
>    https://sites.google.com/site/parallelizationforllvm/rdiv-test
Can you explain this comment:
> With minor algebra, this test can also be used for things like [c1 +
> a1*i + a2*j][c2].
> 
> If you have any thoughts about this code, I'd be very interested in
> hearing them.
I this look good, but, as you say below, we also need to work on the
top-level infrastructure. It will be hard to validate and evaluate
this code without a framework in which to use it.

One thing that I would like to mention is that 'use' here should also
include user feedback. This means being able to pass information back
to the frontends about which loops are being effectively analyzed, and
for loops that are not, why not.

 -Hal
> 
> I'm going to take a break from working on these low-level tests and
> spend some time working top-down on the high-level structure of the
> Delta Test (finding coupled subscripts, etc).
> 
> Preston


-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

On Mon, May 14, 2012 at 1:30 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> Can you explain this comment:
> > With minor algebra, this test can also be used for things like [c1 +
> > a1*i + a2*j][c2].
It's really too simple to deserve mention...
Given a subscript pair, [c1 + a1*i + a2*j] and [c2], we can test for
dependence using the RDIV test by rewriting as [c1 + a1*i] and [c2 -
a2*j].
> I this look good, but, as you say below, we also need to work on the
> top-level infrastructure. It will be hard to validate and evaluate
> this code without a framework in which to use it.
Yep. I've written a simple framework to do tests on my own, but it
needs to be extended to be more generally useful.
> One thing that I would like to mention is that 'use' here should
also
> include user feedback. This means being able to pass information back
> to the frontends about which loops are being effectively analyzed, and
> for loops that are not, why not.
Absolutely. I've been thinking in terms of passing info back to the
programmer (see
https://sites.google.com/site/parallelizationforllvm/feedback). It's a
very interesting problem and one where I think there are real research
possibilities.

Preston

On Mon, 14 May 2012 13:54:19 -0700
Preston Briggs <preston.briggs at gmail.com> wrote:
> On Mon, May 14, 2012 at 1:30 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
> 
> > Can you explain this comment:
> > > With minor algebra, this test can also be used for things like
> > > [c1 + a1*i + a2*j][c2].
> 
> It's really too simple to deserve mention...
> Given a subscript pair, [c1 + a1*i + a2*j] and [c2], we can test for
> dependence using the RDIV test by rewriting as [c1 + a1*i] and [c2 -
> a2*j].
> 
> > I this look good, but, as you say below, we also need to work on the
> > top-level infrastructure. It will be hard to validate and evaluate
> > this code without a framework in which to use it.
> 
> Yep. I've written a simple framework to do tests on my own, but it
> needs to be extended to be more generally useful.
> 
> > One thing that I would like to mention is that 'use' here
should
> > also include user feedback. This means being able to pass
> > information back to the frontends about which loops are being
> > effectively analyzed, and for loops that are not, why not.
> 
> Absolutely. I've been thinking in terms of passing info back to the
> programmer (see
> https://sites.google.com/site/parallelizationforllvm/feedback). It's a
> very interesting problem and one where I think there are real research
> possibilities.
Do you think that we should do this by adding metadata, or should we
establish some kind of separate feedback channel? Metadata would make
it more useful for writing regression tests (perhaps), but a separate
feedback channel might be more useful for the front ends. Maybe we
should have a separate feedback channel that, lacking any other
consumer, writes out metadata?

 -Hal
> 
> Preston


-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory