Graphite news

[Tobias Grosser]

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.

Cheers
Tobi