Re: SMS scheduling

[Mostafa Hagog <MUSTAFA at il dot ibm dot com>]

canqun@nudt.edu.cn wrote on 02/10/2004 11:41:05:

> Mostafa Hagog <MUSTAFA@il.ibm.com>:
>
> >
> > Canqun Yang <canqun@nudt.edu.cn> wrote on 28/09/2004
> 11:06:29:
> >
> > > Hi, all
> > >
> > > I tested the Swing Modulo Scheduling of GCC. For
> > > simple program, the numerical caculation of PI, it
> > > achieves significant speedup on IA64. But, for
> little
> > > bit complex programs, the SMS can hardly work out a
> > > successful schedule.
> > >
> > > The algorithms implemented by Ayal and Mostafa are
> > > correct. It seems that the SMS itself is wrong. The
> > > schedule priority order calculated by SMS is much
> > > different from normal MinDist algorithm.
> >
> > SMS prioritizes the nodes using critical patch based
> > heuristic - the main idea is that instructions that
> are
> > on the critical path are less flexible in means of
> > scheduling.
> > Why do you think that the priority order should be
> > according to MinDist algorithm (what is the minimum
> > distance in this case)? Can you provide an example
> > that supports this?
> >
>
> Yes, I'll give an example after my holiday.
>
> > > Besides this,
> > > SMS is not sensitive to II. Is SMS really wrong?
> >
> > The node ordering step in SMS is not sensitive to II
> > (as mentioned before it is based on critical path
> > heuristic).  However, the scheduling step is sensitive
> > to II - failing to schedule the nodes of a loop within
> > II cycles will lead to try scheduling the nodes again
> > within II + 1 cycles.
> >
> The node order calculated by SMS is not suitable.

Not suitable for what? For your example?

> Although, the scheduling step does increase the II
> value to try a successful schedule, it is useless. In
> fact, the scheduler almost always fail at the same insn
> while the II is increasing.

This shouldn't be the case in general (maybe this is in
your specific example). In general, when we increase the
II we increase the "mobility" of instructions (i.e the
cycles that we can schedule an instruction in).  Thus if
an instructions couldn't be scheduled within II cycles it
has better chance to be scheduled within II + 1 cycles.
So there maybe a specific problem of your example and/or
ia64 scheduling.

Mostafa.