{gSoc}application : Automatic parallelization in Graphite

{gSoc}application : Automatic parallelization in Graphite

[Li Feng]

Hi all,

Below is the proposal of this gSoc project.  I'd really like you review and
comment on this and then I can plan this project better.

Thanks,
Li Feng
----------------------------------------------------------------------------------------
#title Automatic parallelization in Graphite

* Synopsis

With the integration of Graphite to GCC4.4, a strong loop nest
analysis and transformation engine was introduced. But now it
does only non-parallel loop generation. My work is to detect
synchronization free parallel loops and generate parallel code
for them, which will mainly enables programs to run faster.

* The Project

In GCC there already exists an auto-parallelization pass, but it
can't works on some not-simple loops.
e.g. The following code can't be handled by autopar, which yields
a scev_not_known dependency.
<src lang="c">
int Z[100][100];

int main(void)
{
  int i,j;
  for (i = 0; i <= 10; i++)
    for (j = 0; j <=10; j++)
      Z[i][j] = Z[j+10][i+11];

  return 0;
}
</src>

I made some experimental work on "What kind of loops can
autopar handle and what it can't" ,you can find it here:
http://gcc.gnu.org/wiki/AutoparRelated.

Graphite can analyze every loop, condition that can be analyzed
by polyhedral analysis, and even complicated loop nests.
Under Graphite, we could detect synchronization free parallel
loops and generate parallel code for them. During Google Summer
of Code, I want to solve the two issues.

First of all, I will write test cases for different kind of loops
that can be parallelized under Graphite. This work will be done
by some discussions about data dependency analysis under polyhedral
model with Graphite developers.

The first issue will be parallel loop detection. This means that
Graphite will recognize simple parallel loops using SCoP detection
and data dependency analysis. SCoP detection is well supported
by Graphite and Konrad Trifunic is now working on data dependency
analysis based on polyhedral model, which will be done about 3-4
weeks.

The place for parallel loop detection will be after CLOOG generate
the new loops, either CLAST(cloog AST after call cloog on polyhedra)
or after clast_to_gimple. At this time as we have the polyhedral
information (poly_bb_p) still available during code generation, we
can try to update the dependency information using the restrictions
CLOOG added and the polyhedral dependency analysis to check if there
is any dependency in the generated loops.

So the basic step of parallel loop detection will be:
 1. Get the poly_bb_p after CLOOG
 2. Check that if there are dependencies.
 3. If dependency doesn't exist, mark the loop as parallel. We may
    add annotations of more detailed information here. e.g.
    shared/private objects.

The second issue will be parallel code generation. At this part,
I will try to integrate autopar's code generation to Graphite. This
work will be done precisely after cloog_to_gimple. I will make sure
that the loops Graphite creates can be handled by the autopar's
code generation. Currently the autopar pass in GCC lower the
OMP_FOR and OMP_PARALLEL to libgomp functions. Still, maybe we
could call autopar's reduction analysis, if the scalar analysis
determines that the loop is still parallelizable, then the code
generation will be called.


* Success Criteria

 1. Graphite can recognize and mark loops that can be parallelized
 2. Graphite will generate parallelized code for them
 3. Pass test cases for Graphite's auto-parallelization

* Road-map

 1. Since data dependency analysis is not available, I will firstly
    integrate autopar's code generation to Graphite. This work will
    be done step by step.(Mid June)
    - Introduce a flag -fgraphite-parallelize that forces auto-parallelization
      for all loops.
    - Make sure the loops Graphite creates can be handled by the autopar's
      code generation.
    - Call autopar for every loop.(The loops that can not be paralleled will
      just fail/crash.)
 2. Write test cases for the loops that can be parallelized. This will take a
    few discussions with Graphite developers to see which kind
    of loops we will should detect and can be auto-parallelized.(End June)
 3. Write code for parallel code detection. This part of job will based on
    SCoP detection and data dependency, and at this time, data dependency
    analysis should have been done. This part of work will take most of
    the time.(First week of August)
 4. Code cleaning and write documents.(Second week of August)

* Profit for GCC

 - When the auto-parallelization has been done in Graphite, developer
   can mostly take their effort to loop transformations. Graphite will
   in charge of optimizations(generate parallelism) and the autopar
   code in Graphite will just detect and generate code for them.

Re: {gSoc}application : Automatic parallelization in Graphite

[Tobias Grosser]

On Thu, 2009-03-26 at 10:36 +0800, Li Feng wrote:
> Hi all,
> 
> Below is the proposal of this gSoc project.  I'd really like you review and
> comment on this and then I can plan this project better.

Hi Li,

this looks nice. Thanks for your work on this.

Tobias

> 
> Thanks,
> Li Feng
> ----------------------------------------------------------------------------------------
> #title Automatic parallelization in Graphite
> 
> * Synopsis
> 
> With the integration of Graphite to GCC4.4, a strong loop nest
> analysis and transformation engine was introduced. But now it
> does only non-parallel loop generation. My work is to detect
> synchronization free parallel loops and generate parallel code
> for them, which will mainly enables programs to run faster.
> 
[..]

> * Road-map
> 
>  1. Since data dependency analysis is not available, I will firstly
>     integrate autopar's code generation to Graphite. This work will
>     be done step by step.(Mid June)
>     - Introduce a flag -fgraphite-parallelize that forces auto-parallelization
>       for all loops.
>     - Make sure the loops Graphite creates can be handled by the autopar's
>       code generation.
>     - Call autopar for every loop.(The loops that can not be paralleled will
>       just fail/crash.)

I think on this point we should discuss with Razya and the others where
your work ends.  Just adapting autopar to handle all graphite loops is a
project on its own. So I do not think it can be done by you in two
weeks.

>  2. Write test cases for the loops that can be parallelized. This will take a
>     few discussions with Graphite developers to see which kind
>     of loops we will should detect and can be auto-parallelized.(End June)
>  3. Write code for parallel code detection. This part of job will based on
>     SCoP detection and data dependency, and at this time, data dependency
>     analysis should have been done. This part of work will take most of
>     the time.(First week of August)

How much time this point takes depends how exact you want to solve it. I
think a correct but conservative implementation might be written in a
week. If you want to detect all loops it will take you more time.

>  4. Code cleaning and write documents.(Second week of August)

I think it is useful to define the limits of your work a little bit
stricter. For me there are two options:

1. You stay more on the autopar/gimple side (Step 1) and adapt autopar
for graphite. This is very necessary for graphite, but it might need
some time to get up to speed in autopar.

2. You stay more on the graphite/polyhedral side. You work on all these
steps, but we limit step 1 to the graphite internal parts. This means
you connect autopar to graphite and try to generate parallel loop nests.
If autopar can not handle a loop nest you analyse it and write a bug
report. Someone else will extend autopar.

As Razya already has some knowlege about autopar and she is also
interested in working on parallelization maybe she is able to support
you with the autopar stuff? So you might be able to actually focus more
on the polyhedral part.

> * Profit for GCC
> 
>  - When the auto-parallelization has been done in Graphite, developer
>    can mostly take their effort to loop transformations. Graphite will

be

>    in charge of optimizations(generate parallelism) and the autopar
>    code in Graphite will just detect and generate code for them.



Tobias

Re: {gSoc}application : Automatic parallelization in Graphite

[Li Feng]

Hi Tobi,

On Thu, Mar 26, 2009 at 3:17 PM, Tobias Grosser
<grosser@fim.uni-passau.de> wrote:
> On Thu, 2009-03-26 at 10:36 +0800, Li Feng wrote:
>> Hi all,
>>
>> Below is the proposal of this gSoc project.  I'd really like you review and
>> comment on this and then I can plan this project better.
>
> Hi Li,
>
> this looks nice. Thanks for your work on this.
>
> Tobias
>
>>
>> Thanks,
>> Li Feng
>> ----------------------------------------------------------------------------------------
>> #title Automatic parallelization in Graphite
>>
>> * Synopsis
>>
>> With the integration of Graphite to GCC4.4, a strong loop nest
>> analysis and transformation engine was introduced. But now it
>> does only non-parallel loop generation. My work is to detect
>> synchronization free parallel loops and generate parallel code
>> for them, which will mainly enables programs to run faster.
>>
> [..]
>
>> * Road-map
>>
>>  1. Since data dependency analysis is not available, I will firstly
>>     integrate autopar's code generation to Graphite. This work will
>>     be done step by step.(Mid June)
>>     - Introduce a flag -fgraphite-parallelize that forces auto-parallelization
>>       for all loops.
>>     - Make sure the loops Graphite creates can be handled by the autopar's
>>       code generation.
>>     - Call autopar for every loop.(The loops that can not be paralleled will
>>       just fail/crash.)
>
> I think on this point we should discuss with Razya and the others where
> your work ends.  Just adapting autopar to handle all graphite loops is a
> project on its own. So I do not think it can be done by you in two
> weeks.
>
>>  2. Write test cases for the loops that can be parallelized. This will take a
>>     few discussions with Graphite developers to see which kind
>>     of loops we will should detect and can be auto-parallelized.(End June)
>>  3. Write code for parallel code detection. This part of job will based on
>>     SCoP detection and data dependency, and at this time, data dependency
>>     analysis should have been done. This part of work will take most of
>>     the time.(First week of August)
>
> How much time this point takes depends how exact you want to solve it. I
> think a correct but conservative implementation might be written in a
> week. If you want to detect all loops it will take you more time.
>
>>  4. Code cleaning and write documents.(Second week of August)
>
> I think it is useful to define the limits of your work a little bit
> stricter. For me there are two options:
>
> 1. You stay more on the autopar/gimple side (Step 1) and adapt autopar
> for graphite. This is very necessary for graphite, but it might need
> some time to get up to speed in autopar.
>
> 2. You stay more on the graphite/polyhedral side. You work on all these
> steps, but we limit step 1 to the graphite internal parts. This means
> you connect autopar to graphite and try to generate parallel loop nests.
> If autopar can not handle a loop nest you analyse it and write a bug
> report. Someone else will extend autopar.
>
> As Razya already has some knowlege about autopar and she is also
> interested in working on parallelization maybe she is able to support
> you with the autopar stuff? So you might be able to actually focus more
> on the polyhedral part.

It's good that Razya do the autopar related job, then I can focus mostly on the
polyhedral part. So I think my work will be:

1.  detect loops that can be parallel(based on SCoP detection and data
dependency test).
2.  connect Graphite with autopar part(by Razya)

And thanks for your comment :)

>> * Profit for GCC
>>
>>  - When the auto-parallelization has been done in Graphite, developer
>>    can mostly take their effort to loop transformations. Graphite will
>
> be
>
>>    in charge of optimizations(generate parallelism) and the autopar
>>    code in Graphite will just detect and generate code for them.
>
>
>
> Tobias
>
>

Li Feng

Re: {gSoc}application : Automatic parallelization in Graphite

[andrew babanin]

Hi.

 I wrote to gcc mail list some time ago about my work on new RPC system.
 So it has auto-parallelization for functions and uses GCC wrapper
compiler to do this job.

May be you will find it interesting in repect with your job.
Project site is - crpc.sf.net

Andrey.

Re: {gSoc}application : Automatic parallelization in Graphite

[Razya Ladelsky]

Tobias Grosser <grosser@fim.uni-passau.de> wrote on 26/03/2009 09:17:26:

> On Thu, 2009-03-26 at 10:36 +0800, Li Feng wrote:
> > Hi all,
> > 
> > Below is the proposal of this gSoc project.  I'd really like you 
review and
> > comment on this and then I can plan this project better.
> 
> Hi Li,
> 
> this looks nice. Thanks for your work on this.
> 
> Tobias
> 
> > 
> > Thanks,
> > Li Feng
> > 
> 
----------------------------------------------------------------------------------------
> > #title Automatic parallelization in Graphite
> > 
> > * Synopsis
> > 
> > With the integration of Graphite to GCC4.4, a strong loop nest
> > analysis and transformation engine was introduced. But now it
> > does only non-parallel loop generation. My work is to detect
> > synchronization free parallel loops and generate parallel code
> > for them, which will mainly enables programs to run faster.
> > 
> [..]
> 
> > * Road-map
> > 
> >  1. Since data dependency analysis is not available, I will firstly
> >     integrate autopar's code generation to Graphite. This work will
> >     be done step by step.(Mid June)
> >     - Introduce a flag -fgraphite-parallelize that forces auto-
> parallelization
> >       for all loops.
> >     - Make sure the loops Graphite creates can be handled by the 
autopar's
> >       code generation.
> >     - Call autopar for every loop.(The loops that can not be 
paralleled will
> >       just fail/crash.)
> 
> I think on this point we should discuss with Razya and the others where
> your work ends.  Just adapting autopar to handle all graphite loops is a
> project on its own. So I do not think it can be done by you in two
> weeks.
> 
> >  2. Write test cases for the loops that can be parallelized. This 
> will take a
> >     few discussions with Graphite developers to see which kind
> >     of loops we will should detect and can be auto-parallelized.(End 
June)
> >  3. Write code for parallel code detection. This part of job will 
based on
> >     SCoP detection and data dependency, and at this time, data 
dependency
> >     analysis should have been done. This part of work will take most 
of
> >     the time.(First week of August)
> 
> How much time this point takes depends how exact you want to solve it. I
> think a correct but conservative implementation might be written in a
> week. If you want to detect all loops it will take you more time.
> 
> >  4. Code cleaning and write documents.(Second week of August)
> 
> I think it is useful to define the limits of your work a little bit
> stricter. For me there are two options:
> 
> 1. You stay more on the autopar/gimple side (Step 1) and adapt autopar
> for graphite. This is very necessary for graphite, but it might need
> some time to get up to speed in autopar.
> 
> 2. You stay more on the graphite/polyhedral side. You work on all these
> steps, but we limit step 1 to the graphite internal parts. This means
> you connect autopar to graphite and try to generate parallel loop nests.
> If autopar can not handle a loop nest you analyse it and write a bug
> report. Someone else will extend autopar.
> 
> As Razya already has some knowlege about autopar and she is also
> interested in working on parallelization maybe she is able to support
> you with the autopar stuff? So you might be able to actually focus more
> on the polyhedral part.

I think this sounds like a good plan for the parallel code generation part 
(phase 1)
Li will focus more on the Graphite side  and I will contribute on the 
gimple side.

Razya

> 
> > * Profit for GCC
> > 
> >  - When the auto-parallelization has been done in Graphite, developer
> >    can mostly take their effort to loop transformations. Graphite will
> 
> be
> 
> >    in charge of optimizations(generate parallelism) and the autopar
> >    code in Graphite will just detect and generate code for them.
> 
> 
> 
> Tobias
>