Re: Graphite news

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

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).

Richard.