Graphite news

[Tobias Grosser]

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