Re: Graphite news

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

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.

Thanks,
Richard.

> https://github.com/tobig/gcc
>
> * The new scop detection
>
> This code is already committed into the graphite branch. Currently Vladimir
> is evaluating intensively the stability of his code.
>
> == Who will do all the work? ==
>
> After reading all the open projects you may wander who will do all the work?
> Unfortunately Sebastian switched jobs at the end of 2011, such that we lost
> one full time contributor. Furthermore, I am myself also not full time
> working on Graphite, but work on my PhD where I am founded to work on the
> LLVM Polly project. This means developer resources are currently rare.
>
> To solve this issue, I believe the best approach is to share as much
> infrastructure as possible between different projects. After the above
> patches have been integrated, graphite does not only have a very neat
> polyhedral infrastructure, but also can optimizations be applied at a nice,
> abstract level. This means for optimization we can (mostly) rely on high
> level polyhedral transformations. This is part of my PhD and I expect to
> contribute here significantly. Furthermore, I expect that we can directly
> take advantage of polyhedral optimizations developed outside of GCC e.g. in
> source to source tools. Overall, I am pretty confident in terms of developer
> resources on the polyhedral side.
>
> For the less polyhedral, more GCC internals related part of this work the
> situation is different. Here significantly more GCC knowledge is required
> and many high-level people will not be able to contribute. I will definitely
> be around and will review patches. However, to ensure fast resolution of bug
> reports we definitely need further help from within the GCC community.
> Additional support is highly welcome. In case someone is interested in a
> full time position working on GCC/Graphite, please get in touch with me. We
> have funding for a full-time developer position in Paris and we would love
> to use this money to support further Graphite/GCC development.
>
> That's all so far. I would be very glad to hear your opinion on this and am
> especially interested in people expressing their doubts and pointing out
> possible problems with these ideas.
>
> Thanks a lot
> Tobi
>
> [1] http://repo.or.cz/w/isl.git
> [2] http://pluto-compiler.sourceforge.net/
> [3] http://www.csa.iisc.ernet.in/~uday/publications/uday-cc08.pdf
> [4] http://www.csa.iisc.ernet.in/~uday/publications/uday-pldi08.pdf
> [5] http://pluto-compiler.sourceforge.net/intel.png
> [6] http://polly.grosser.es
>
>
> * Sven, the developer of isl, is affiliated with me. I have and am still
> working intensively with him. So this opinion is definitely biased. Please
> point me to any better alternatives, if you are aware of them.