Graphite news
Tobias Grosser
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.
* 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.
Vladimir Makarov
>
> == 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.
I just thought about licensing. If you are going to share the code
between GCC and LLVM, who will be the owner (FSF or UIUC). But may be I
understood you incorrectly and you meant only libraries (isl etc).
Tobias Grosser
> On 02/09/2012 07:42 AM, Tobias Grosser wrote:
>>
>> == 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.
>
> I just thought about licensing. If you are going to share the code
> between GCC and LLVM, who will be the owner (FSF or UIUC). But may be I
> understood you incorrectly and you meant only libraries (isl etc).
Both. Libraries are simple, as they are just used. For code I can only
share code that I have written. That means, if I have written code I can
add it at both places. If people start to contribute, moving code
becomes more difficult. However, I assume that most of the stuff that
can be shared will actually be part of isl, and only compiler specific
stuff goes into GCC and LLVM. So I do not expect that a lot of code
needs to be moved later on.
Tobi
Tobias Grosser
Or maybe I should be more specific.
I think the stuff that can actually be shared are polyhedral concepts
and algorithms. Those are mathematical algorithms which are so high
level that they are compiler independent. For Graphite and Polly itself
I do not see too much code reuse. Obviously they will share some
techniques and ideas, but the actual implementation will strongly depend
on the compiler it is built for. Here we have not only different coding
styles and conventions, but also different needs how we interact with
the rest of the compilers, which heuristics we choose and how in general
we use the polyhedral techniques. I have earlier implemented some
algorithms for both compiler, but as soon as they are pushed upstream
they slowly start to diverge and to adapt to what is best for each
compiler. From that on I believe the sharing will most probably happen
by sharing experience and ideas, not actual code. Not having the same
code base will also allow both projects to explore new directions
individually, which may result in useful ideas for both.
Cheers
Tobi
Vladimir Makarov
not depend only from you. I think the final results for LLVM will look
better than for GCC because LLVM generated code not so optimized as GCC one.
Thanks for the clarification, Tobias. In general, it looks ok for me
although there are always some advantages and disadvantages of such
approach: better resource usage but less competition as the approach to
loop optimizations in the both compilers will be basically the same.
Tobias Grosser
Hey Vladimir,
thanks for your feedback!
> Personally, I'd prefer that you focus more on GCC but it probably does
> not depend only from you. I think the final results for LLVM will look
> better than for GCC because LLVM generated code not so optimized as GCC
> one.
No, not entirely. There have been various reasons to start with
Polly/LLVM, one the need for GPU code generation. Even though I now need
to split my development time, I am still very interested in continuing
the development of Graphite.
> Thanks for the clarification, Tobias. In general, it looks ok for me
> although there are always some advantages and disadvantages of such
> approach: better resource usage but less competition as the approach to
> loop optimizations in the both compilers will be basically the same.
It really depends who steps in to do the work. I will for myself
obviously not take two entirely different approaches for GCC and LLVM,
but I welcome everybody to join the loop optimization affords. If people
want to take different ways I am the last person to block anybody.
Please complain loudly, if any of the directions I propose for Graphite
does not sound right to you. You are invited to either convince me to
change directions or to experiment with a different approach. I am eager
to learn where I fail badly or where I could do better.
In terms of competition I agree and I also see both positive and
negative points. One good point I see is that with the joint polyhedral
base library the competition now moves to the kind of high level
optimizations implemented, instead of competing over the quality of the
low level infrastructure.
Cheers
Tobi
Richard Guenther
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.
Alain Lichnewsky
I am wondering whether there is a summary of Graphite functionality as available in GCC 4.7.0, as well as
some summary documentation on flags and options to be used in conjunction with Graphite in GCC 4.7.0.
My specific areas of interest at this time:
- using Graphite to obtain vector code for Intel AVX
- generating openMP
Are there Howtos and/or tests for these functionalities?
Thanks a lot
Alain
Richard Guenther
(thus, ripping
out all remaining PPL dependencies).
Richard.
Tobias Grosser
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
Richard Guenther
other repository of interest?
Btw, I'm going to push forward the move to cloog 0.17.0 and cherry pick one
or two fixes from you branch. Then try to get to 1) and drop the parallel
maintaining of PPL data structures. Any help in that is appreciated (though
I consider "crippling" functionality in the areas that do not have an ISL
equivalent at this point).
Thanks,
Richard.
> Cheers
> Tobi
>
Tobias Grosser
> Btw, I'm going to push forward the move to cloog 0.17.0 and cherry pick one
> or two fixes from you branch.
> Then try to get to 1) and drop the parallel
> maintaining of PPL data structures.
> Any help in that is appreciated (though
> I consider "crippling" functionality in the areas that do not have an ISL
> equivalent at this point).
openscop import/export and the loop interchange heuristic. I think you
can safely crop the openscop import/export, as it is currently unused
and can later be added back if needed. In respect of the loop
interchange. I am personally not interested in a dedicated loop
interchange pass, but the isl scheduling optimizer does not yet provide
a valuable alternative. This is one of the other reasons I did not push
the patches through, as I was afraid of the discuss that the loop
interchange removal may cause (and I was too lazy to rewrite and fix the
buggy loop interchange heuristic).
Tobi
Michael Matz
On Fri, 22 Jun 2012, Tobias Grosser wrote:
> There are two areas that do not yet have an isl counterpart. The
> openscop import/export and the loop interchange heuristic. I think you
> can safely crop the openscop import/export, as it is currently unused
> and can later be added back if needed. In respect of the loop
> interchange. I am personally not interested in a dedicated loop
> interchange pass, but the isl scheduling optimizer does not yet provide
> a valuable alternative. This is one of the other reasons I did not push
> the patches through, as I was afraid of the discuss that the loop
> interchange removal may cause (and I was too lazy to rewrite and fix the
> buggy loop interchange heuristic).
isl/ppl-illiterate tries to fiddle with that, though?
Ciao,
Michael.
Tobias Grosser
happily answer questions to the best of my knowledge (I did not write
the loop interchange heuristic (Sebastian did it)).
I personally hope we can remove the specific transformations (like
interchange, blocking, ...) and move to a more uniform optimizer.
However, this is touching the area of research and it may be valuable to
have the existing stuff around to compare.
One reason, I would prefer to remove them is that they enforce the
maintenance of the loop statement tree (an imperative data structure)
next to the abstract model we have. Being able to work just within our
abstract model seems a lot nicer both conceptually, but also in terms of
maintenance work needed.
Cheers
Tobi