On Thu, Mar 1, 2012 at 3:21 PM, Richard Guenther <richard.guent...@gmail.com> wrote: > 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.
I'm picking this up now, trying to massage it to a mergeable state (thus, ripping out all remaining PPL dependencies). Richard.
