Re: Solve transitive closure issue in modulo scheduling

[Daniel Berlin <dberlin at dberlin dot org>]

On Fri, Jan 30, 2009 at 7:44 AM, Bingfeng Mei <bmei@broadcom.com> wrote:
> Hello,
> I try to make modulo scheduling work more efficiently for our VLIW target. I found one serious issue that prevents current SMS algorithm from achieving high IPC is so-called "transitive closure" problem, where scheduling window is only calculated using direct predecessors and successors. Because SMS is not an iterative algorithm, this may cause failures in finding a valid schedule. Without splitting rows, some simple loops just cannot be scheduled not matter how big the II is. With splitting rows, schedule can be found, but only at bigger II. GCC wiki (http://gcc.gnu.org/wiki/SwingModuloScheduling) lists this as a TODO. Is there any work going on about this issue (the last wiki update was one year ago)? If no one is working on it, I plan to do it. My idea is to use the MinDist algorithm described in B. Rau's classic paper "iterative modulo scheduling" (http://www.hpl.hp.com/techreports/94/HPL-94-115.html). The same algorithm can also be used to compute better RecMII. The biggest concern is complexity of computing MinDist matrix, which is O(N^3). N is number of nodes in the loop. I remember somewhere GCC coding guide says "never write quadratic algorithm" :-) Is this an absolute requirement?

It's not an absolute requirement, just a general guideline.

We have plenty of quadratic and worse algorithms, and we'd rather see
less of them :)
Obviously, when it comes to things requiring transitive closure, you
can't really do better.