On Thu, Feb 9, 2012 at 1:42 PM, Tobias Grosser <tob...@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.
