Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!uxc!uxc.cso.uiuc.edu!uicsgva.csg.uiuc.edu!pohua
From: pohua@uicsgva.csg.uiuc.edu
Newsgroups: comp.arch
Subject: Re: Fujitsu SPARC Interlocks
Message-ID: <1600003@uicsgva.csg.uiuc.edu>
Date: 9 Feb 89 20:31:00 GMT
References: <28200269@mcdurb>
Lines: 24
Nf-ID: #R:mcdurb:28200269:uicsgva.csg.uiuc.edu:1600003:000:978
Nf-From: uicsgva.csg.uiuc.edu!pohua    Feb  9 14:31:00 1989


Is there a good algorithm for scheduling 'negative' dependencies
without backtracking, when delayed branch is used?

For example,
	A : 	r3 = r4 + r5
	B :	br (r1>9)

The operation A can be moved into operation B's delay slot space.
Thus, the dependence graph constructed from the above code will
indicate a 'negative' control-dependence distance from A to B.

Many interesting deterministic scheduling schemes which I have read
about model a program by its dependence graph. Then the interlocking
problem is transformed into one which finds correct initiation times
for all the operations. Because all types of dependencies (data/control/...)
can be expressed as some inequality equations, I don't think any
one of these dependencies is more difficult than others to be handled.

Of course, the scheduling problem is made more difficult by
adding resource constraints and increasing pipeline length.
But I still believe that software interlocking is a feasible approach.

pohua