Graphite news

[Tobias Grosser]

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.