This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Graphite news


On 06/22/2012 01:19 PM, Richard Guenther wrote:
On Fri, Jun 22, 2012 at 12:46 PM, Tobias Grosser<tobias@grosser.es> wrote:
On 06/22/2012 12:41 PM, Richard Guenther wrote:

On Thu, Mar 1, 2012 at 3:21 PM, Richard Guenther <richard.guenther@gmail.com> wrote:

On Thu, Feb 9, 2012 at 1:42 PM, Tobias Grosser<tobias@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.

I see - I am currently extracting patches from your git branch - is there any other repository of interest?

No. Not that I know of.


Btw, I'm going to push forward the move to cloog 0.17.0 and cherry pick one
or two fixes from you branch.

OK, great.


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

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


Tobi


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]