Re: Graphite news

[Richard Guenther <richard dot guenther at gmail dot com>]

On Fri, Jun 22, 2012 at 12:46 PM, Tobias Grosser <tobias@grosser.es> wrote:
> On 06/22/2012 12:41 PM, Richard Guenther wrote:
>>
>> On Thu, Mar 1, 2012 at 3:21 PM, Richard Guenther
>> <richard.guenther@gmail.com> ?wrote:
>>>
>>> On Thu, Feb 9, 2012 at 1:42 PM, Tobias Grosser<tobias@grosser.es> ?wrote:
>>>>
>>>> Hi,
>>>>
>>>> it has been quiet around Graphite for a while and I think it is more
>>>> than
>>>> time to give an update on Graphite.
>>>>
>>>> == The Status of Graphite ==
>>>>
>>>> Graphite has been around for a while in GCC. During this time a lot of
>>>> people tested Graphite and Sebastian fixed many bugs. As of today the
>>>> Graphite infrastructure is pretty stable and hosts already specific
>>>> optimizations such as loop-interchange, blocking and loop-flattening.
>>>>
>>>> However, during the development of Graphite we also found areas where
>>>> we are still way behind our possibilities.
>>>> First of all we realized that the use of a rational polyhedral library,
>>>> even
>>>> though it provides some functionality for integer polyhedra, is blocking
>>>> us.
>>>> Rational rational polyhedra worked OK for some time, but we have now
>>>> come to
>>>> a point where the absence of real integer polyhedra is causing problems.
>>>> We
>>>> have bugs that cannot be solved, just because rational polyhedra do not
>>>> represent correctly the set of integer points in the loop iterations.
>>>> Another deficit in Graphite is the absence of a generic optimizer. Even
>>>> though classical loop transformations work well for certain problems,
>>>> one of
>>>> the major selling points of polyhedral techniques is the possibility to
>>>> go
>>>> beyond classical loop transformations and to forget about the
>>>> corresponding
>>>> pass ordering issues. Instead it is possible to define a generic cost
>>>> function for which to optimize. We currently do not take advantage of
>>>> this
>>>> possibility and therefore miss possible performance gains.
>>>> And as a last point, Graphite still does not apply to as much code as it
>>>> could. We cannot transform a lot of code, not only because of the
>>>> missing
>>>> support for casts (for which we need integer polyhedra), but also
>>>> because of
>>>> an ad hoc SCoP detection and because some passes in the
>>>> GCC pass order complicate Graphite's job. Moving these road blocks out
>>>> of
>>>> the way should increase the amount of code we can optimize
>>>> significantly.
>>>>
>>>> == The pipeline of upcoming graphite changes ==
>>>>
>>>> As just pointed out there is still a lot of work to be done. We have
>>>> been
>>>> aware of this and we actually have several ongoing projects to get this
>>>> work
>>>> done.
>>>>
>>>> 0. Moving to recent version of CLooG.
>>>>
>>>> Graphite was relying for a long time on CLooG-PPL, a CLooG version
>>>> Sebastian
>>>> forked and ported to PPL, because of copyright issues at that time. The
>>>> fork
>>>> was never officially maintained by cloog.org, but always by Sebastian
>>>> himself. This was a significant maintenance burden and meant that we
>>>> where
>>>> cut of from improvements in the official CLooG library. With Andreas
>>>> Simbuerger we had 2011 a summer of code student, that added support to
>>>> use
>>>> the official cloog.org. The cloog.org version
>>>> proved to be very stable, but we could not yet switch entirely over,
>>>> as this version uses isl as polyhedral library, which would introduce
>>>> another library dependence to GCC (ppl, CLooG and now isl). One solution
>>>> to
>>>> get this patch in and to not increase the number of library dependences
>>>> is
>>>> to follow CLooG and to replace PPL with isl. As this was
>>>> desirable for several other reasons Sebastian went ahead:
>>>>
>>>> 1. The integer set library
>>>>
>>>> Back in September Sebastian started the work to move Graphite to an
>>>> actual
>>>> integer set library. We have chosen isl [1], which is nowadays probably
>>>> the
>>>> most advanced open source integer set library*. The patch set as posted
>>>> in
>>>> September was incomplete and in parts incorrect. I finished the patch
>>>> set.
>>>> With the new patch set the core graphite transformations work entirely
>>>> with
>>>> isl. The only exceptions are the interchange cost function, the openscop
>>>> export/import and the loop-flattening pass. Due to the native support
>>>> for
>>>> integer maps and especially due to how we can combine sets and maps with
>>>> isl, the isl
>>>> implementation of graphite functions is often a lot simpler and easier
>>>> to
>>>> understand. But, more importantly, it finally allows us to gather modulo
>>>> wrapping and undefined overflow characteristics and solves several other
>>>> issues we had due to the use of rational polyhedra.
>>>>
>>>> 2. A real polyhedral optimizer
>>>>
>>>> To get a real, generic polyhedral optimizer for Graphite we have chosen
>>>> the
>>>> Pluto algorithm. The original implementation of Pluto is available here
>>>> [2],
>>>> the relevant publications are [3] and [4]. Pluto is an polyhedral
>>>> optimizer
>>>> that uses a single cost function to optimize simultaneously for data
>>>> locality, parallelism and tileability. It has shown good results on
>>>> various
>>>> kernels [5] (or see the papers) and Uday, the original author was
>>>> employed
>>>> to reimplement it in IBM XL. We added an implementation of this
>>>> algorithm to
>>>> isl. My recent patch set enables Graphite to use this new optimizer.
>>>> Even
>>>> though the patch is an early draft and definitely needs tuning to match
>>>> the
>>>> results of the original implementation, it is a great starting point for
>>>> a
>>>> real polyhedral optimizer in Graphite.
>>>>
>>>> 3. A new SCoP detection
>>>>
>>>> Valdimir Kargov has implemented a new, structured SCoP detection within
>>>> his
>>>> 2010 Google Summer of Code project. The structured SCoP detection allows
>>>> us
>>>> to remove several limitations on the kind of SCoPs we can detect. The
>>>> work
>>>> was done during his summer of code project and his patches are already
>>>> part
>>>> of the Graphite branch and pass all the internal tests. For the moment
>>>> we
>>>> did not commit them to mainline, as we did not want to risk new bugs
>>>> before
>>>> the next gcc release. We plan to commit these patches as soon as stage
>>>> one
>>>> is open again.
>>>>
>>>> The existing patches are:
>>>>
>>>> * Patches for point 0/1/2
>>>>
>>>> There is a git repository that branches from trunk and has patches for
>>>> the points 0, 1 and 2.
>>>
>>>
>>> As stage1 of GCC 4.8 is very close and your overall plan sounds excellent
>>> it's a good time to move re-base the patches for 0/1/2 and push them out
>>> for review again.
>>
>>
>> I'm picking this up now, trying to massage it to a mergeable state
>> (thus, ripping
>> out all remaining PPL dependencies).
>
>
> Hey Richi,
>
> that is great news. I hesitated to move this forward, as I have currently
> not the bandwidth to respond timely on bugreports and consequently don't
> want to introduce a lot of new code.
>
> Also, as far as I know Umesh (CCed) worked recently on those patches.

I see - I am currently extracting patches from your git branch - is there any
other repository of interest?

Btw, I'm going to push forward the move to cloog 0.17.0 and cherry pick one
or two fixes from you branch.  Then try to get to 1) and drop the parallel
maintaining of PPL data structures.  Any help in that is appreciated (though
I consider "crippling" functionality in the areas that do not have an ISL
equivalent at this point).

Thanks,
Richard.

> Cheers
> Tobi
>