Update: Items 1. to 3. are done for GCC 4.8

This page is the copy of an email sent on 9. February 2012 to the gcc mailing lists. It gives an update on the current status of Graphite and future plans.


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.

1. 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:

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

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

4. 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 1/2/3

There is a git repository that branches from trunk and has patches for the points 1, 2 and 3.


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

None: Graphite-4.8 (last edited 2013-08-23 15:10:53 by JonathanWakely)