Re: Questing on finding II in SMS

[Ayal Zaks <ZAKS at il dot ibm dot com>]

Geert Bosch <bosch@adacore.com> wrote on 20/11/2006 22:24:51:

>  From http://gcc.gnu.org/wiki/SwingModuloScheduling:
> > SMS trying too many II (Vladimir Yanovsky, Ayal Zaks): SMS tries to
> > schedule the kernel in II cycles, starting from some MinII lower
> > bound, incrementing by 1 if unsuccessful, until reaching some MaxII
> > upper bound (where it gives up). The current upper bound was simply
> > a sum of the latencies for all instructions in the loop, which
> > should be achievable by the regular scheduler. In some cases, there
> > is an inherent problem preventing the loop from being SMS'ed
> > successfully, and increasing the II will not help (it only consumes
> > compile time). Due to the inaccuracy of the current MaxII bound,
> > and in order to limit compile-time consumption, we'd like to reduce
> > MaxII.
>
> Just curious: why would we essentially do a linear search for the II,
> instead of a binary one? If II would typically be very close to MinII
> and much
> farther from MaxII, the search might just be weighted differently to be
> efficient in the common case, but still OK in the worst case.
> For example, trying MinII, MinII + 1, MinII + 2, MinII + 4, etc.

Well, success is not guaranteed to be monotonous, as we're applying
scheduling heuristics (and without backtracking). So MinII + 4 may fail
where MinII + 3 succeeds, at-least theoretically. If it does behave
monotonously in practice, then I agree with you that MinII, MinII + 1,
MinII + 2, MinII + 4 is better.

Ayal.