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