On 06/22/2012 12:41 PM, Richard Guenther wrote:
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).
Hey Richi,
that is great news. I hesitated to move this forward, as I have
currently not the bandwidth to respond timely on bugreports and
consequently don't want to introduce a lot of new code.
Also, as far as I know Umesh (CCed) worked recently on those patches.
Cheers
Tobi
