modulo scheduling for IA64

modulo scheduling for IA64

[Deepak B. Nayak]

hi
 one more question.....

 we have built data dependency graph for all the loops for modulo
scheduling..now for each edge we need to know the delay and distance..

nodes of our DDG are rtl insns

distance is no of iterations seperating the two operations involved...

how to calculate this...?

in dependence.c file there function have_dependence_p() which takes two
rtl insns and returns distance and direction vectors if there is
dependence....but these r vectors... we r not able to understand how we
get single value for distance....


regards

deepak

Re: modulo scheduling for IA64

[Jim Wilson]

Gcc does not currently have a modulo scheduler, and hence gcc doesn't have all
of the support routines you need.  There is no convenient function that will
give you the distance value you need.  You need to calculate it yourself.

The dependence.c file was an attempt to add dependence analysis to gcc.
However, there is currently no optimization pass that uses this info, so it
is somewhat more theoretical than practical.  Maybe it will be useful to you.
Maybe it won't.

There might be stuff in the RCSP code that you could use.  This stuff isn't
in the mainline sources, it is on a branch.

Jim

Re: modulo scheduling for IA64

[Deepak B. Nayak]

On 1 Oct 2002, Jim Wilson wrote:

> Gcc does not currently have a modulo scheduler, and hence gcc doesn't have all
> of the support routines you need.  There is no convenient function that will
> give you the distance value you need.  You need to calculate it yourself.
> 
> The dependence.c file was an attempt to add dependence analysis to gcc.
> However, there is currently no optimization pass that uses this info, so it
> is somewhat more theoretical than practical.  Maybe it will be useful to you.
> Maybe it won't.
> 
> There might be stuff in the RCSP code that you could use.  This stuff isn't
> in the mainline sources, it is on a branch.
> 
> Jim
> 

 okay
 then from where can we get RCSP code ...

 regards

deepak

Re: modulo scheduling for IA64

[Vladimir Makarov]

"Deepak B. Nayak" wrote:
> 
> On 1 Oct 2002, Jim Wilson wrote:
> 
> > Gcc does not currently have a modulo scheduler, and hence gcc doesn't have all
> > of the support routines you need.  There is no convenient function that will
> > give you the distance value you need.  You need to calculate it yourself.
> >
> > The dependence.c file was an attempt to add dependence analysis to gcc.
> > However, there is currently no optimization pass that uses this info, so it
> > is somewhat more theoretical than practical.  Maybe it will be useful to you.
> > Maybe it won't.
> >
> > There might be stuff in the RCSP code that you could use.  This stuff isn't
> > in the mainline sources, it is on a branch.
> >
> > Jim
> >
> 
>  okay
>  then from where can we get RCSP code ...

  I'll try to create a branch and place the code in a week or two.  But
I should say there is no calculation of the distances there.  The beauty
of RCSP is in that it does not require such information at all.  So you
need to write such code yourself.

Vlad

Re: modulo scheduling for IA64

[Jim Wilson]

>we need to do if-conversion....
>can we use in-conv pass already there in gcc...???

You can try to use it.  If it works, then the answer is yes.  If it doesn't
work, then the answer is no.

>also we want know if gcc does in-conv pass then does it do reverse-if conv
>for processors without predicated execution...

No.  The if-conversion pass only creates predicated insns for targets that
support predicated insns.

Jim

Re: modulo scheduling for IA64

[Robert Dewar]

<<  Yes, Jim is right.  Register rotation is an unexplored field of RCSP.
Although I don't see why register rotation can not be implemented in
RCSP.  RCSP is also can be forced to work as modulo pipelining.  But
implementation of register rotation in RCSP is more research work than
work for an industrial compiler.
>>

To implement software pipelining without taking advantage of
register renaming on the ia64 makes little sense to me. This
is far from a research topic, it is reaslly essentially to get
decent performance for numeric loops from the chip.

Re: modulo scheduling for IA64

[Vladimir Makarov]

Jim Wilson wrote:
> 
> >       The GCC DFA scheduler already has a software-pipelining feature
> >which has not been merged into the FSF sources, but which should provide
> >modulo scheduling.  Why not complete that work?
> 
> Actually it is RCSP, Resource Constrained Software Pipelining.  It is a good
> algorithm, but unfortunately not the right one for IA-64 as I understand it.
> This is because RCSP doesn't support register rotation, and modulo scheduling
> does.  You need to use register rotation on IA-64 if you want the best
> performance, and thus modulo scheduling is better for IA-64.  RCSP may be
> better for all other targets though, since IA-64 is the only target with
> register rotation.

  Yes, Jim is right.  Register rotation is an unexplored field of RCSP. 
Although I don't see why register rotation can not be implemented in
RCSP.  RCSP is also can be forced to work as modulo pipelining.  But
implementation of register rotation in RCSP is more research work than
work for an industrial compiler.

  As for RCSP, I believe that it has the biggest potential.  My
experience shows me that although modulo scheduling is conceptually
simple, the rest of problems which should be resolved (dealing with ifs,
decreasing register pressure) complicates it too much and the result
algorithm is more complicated than perfect pipelining class algorithms
(as RCSP).  There is a big field in researches of RCSP and adapting
modern architectures to it (with register rotation).  It is much more
interesting than modulo scheduling whose research potential was
exhausted long ago.

  Also I look more widely at insns scheduling.  Software pipelining is
important for some scientific class algorithms, global insn
scheduling is more important.  With this point of view usage of RCSP is
more preferable because its algorithm core could be used for good global
(interblock) insns scheduling.  Its core is analogous to percolation
scheduling or Intel's wavefront scheduling.  So I'd think about software
pipelining as part of global scheduling e.g. as in selective scheduling
and pipelining in more recent version of haifa scheduler. 

  In any case, It is good to have more implementations of pipeling to
choose a better one. 

  Only one additional thought.  If modulo scheduling for ia64 is
implemented as machine dependent part (as I understood from the original
email), it will be wrong way.

  Machine independent implementation of modulo scheduling requires to
use the old or DFA pipeline description.  Unfortunately, the DFA
pipeline hazard recognizer is not good enough to support modulo
scheduling (it needs more interface functions).  But the support could
be provided.

Vlad

Re: modulo scheduling for IA64

[Jim Wilson]

>	The GCC DFA scheduler already has a software-pipelining feature
>which has not been merged into the FSF sources, but which should provide
>modulo scheduling.  Why not complete that work?

Actually it is RCSP, Resource Constrained Software Pipelining.  It is a good
algorithm, but unfortunately not the right one for IA-64 as I understand it.
This is because RCSP doesn't support register rotation, and modulo scheduling
does.  You need to use register rotation on IA-64 if you want the best
performance, and thus modulo scheduling is better for IA-64.  RCSP may be
better for all other targets though, since IA-64 is the only target with
register rotation.

Jim

Re: modulo scheduling for IA64

[Daniel Berlin]

On Monday, September 30, 2002, at 01:48  PM, David Edelsohn wrote:

>>>>>> Deepak B Nayak writes:
>
> Deepak> we r implementing modulo scheduling for IA64...
> Deepak> still we r at the beginning stage....
> Deepak> we r in process of calculating initiation interval...
> Deepak> we need to do if-conversion....
> Deepak> can we use in-conv pass already there in gcc...???
> Deepak> also we want know if gcc does in-conv pass then does it do
> Deepak> reverse-if conv for processors without predicated execution...
>
> 	The GCC DFA scheduler already has a software-pipelining feature
> which has not been merged into the FSF sources, but which should 
> provide
> modulo scheduling.
It doesn't.
It provides Resource Constrained Software Pipelining, which is 
something different.
:)
--Dan

Re: modulo scheduling for IA64

[David Edelsohn]

>>>>> Deepak B Nayak writes:

Deepak> we r implementing modulo scheduling for IA64...
Deepak> still we r at the beginning stage....
Deepak> we r in process of calculating initiation interval...
Deepak> we need to do if-conversion....
Deepak> can we use in-conv pass already there in gcc...???
Deepak> also we want know if gcc does in-conv pass then does it do
Deepak> reverse-if conv for processors without predicated execution...

	The GCC DFA scheduler already has a software-pipelining feature
which has not been merged into the FSF sources, but which should provide
modulo scheduling.  Why not complete that work?

David

modulo scheduling for IA64

[Deepak B. Nayak]

hi
 we r implementing modulo scheduling for IA64...
 still we r at the beginning stage....
we r in process of calculating initiation interval...
we need to do if-conversion....
can we use in-conv pass already there in gcc...???
also we want know if gcc does in-conv pass then does it do reverse-if conv
for processors without predicated execution...

regards

deepak


*********************************************************************************
                        Whatever you are, be a good one.
           						 -- Abraham Lincoln 
				HAVE A NICE DAY

DEEPAK.B.NAYAK
ME-CSE , 604101201
B-3 ,IISc Hostels
IISc
BANGALORE-12

Hostel Phone  - (080)3092431
Computing Lab1- (080)3092368-extn-115
Computing Lab2- (080)3092368-extn-102
Intel Lab     - (080)3092368-extn-227

*********************************************************************************