Superblock Scheduling Alg in GCC

[Ghassan Shobaki]

I had sent this message on Thursday attaching the paper to it, but it 
bounced due to the size limit enforced by the gcc email server. Here is 
the paper citation:

A. Eichenberger and W. Meleis, Balance Scheduling: Weighing Branch 
Tradeoffs in Superblocks, 32nd Annual Intl. Conf. on Microarchitecture 
(IEEE/ACM), 1999, pp. 272. 
 
A soft copy can be found at:

http://www.ece.neu.edu/faculty/meleis.html

Regards

-Ghassan


On Thu, 15 Apr 2004, Ghassan Shobaki wrote:

> 
> The attached paper by Eichenberger and Meleis includes a 
> sufficiently clear description of the Dependence Height and Speculative 
> Yield DHASY Heuristic (the one that I prefer to call weighted 
> critical path WCP for simplicity). The objective of the paper is 
> presenting a complex heuristic, called Balance Scheduling, which 
> seems to be too slow for practical use, but in the Background section 
> they describe DHASY among other simpler heuristics. DHASY appears in the 
> second paragraph of page 274.
> 
> In my experiments I have used a modified version of it that seems to work 
> a bit better in practice. I don't yet have a good explanation why my 
> modified version works better, but I can provide you with some information 
> about it if you want. 
> 
> -Ghassan
>  
> 
> On Wed, 14 Apr 2004, Vladimir Makarov wrote:
> 
> > Ghassan Shobaki wrote:
> > 
> > >Guys,
> > >
> > >I have done some experiments on two different heuristics for superblock 
> > >scheduling by comparing them with optimal scheduling. The two heuristics 
> > >are simple critical path CP (priority is the CP from the last branch only) 
> > >and weighted critical path WCP (priority is a weighted sum of critical pahts 
> > >from all branches below an instruction, with the branch weight being the 
> > >probability of exiting the superblock at that branch). On the simple 
> > >machine model that I am using, I got the following results: 
> > >
> > >fp2000 benchmark: CP is optimal on 72% of the superblocks and WCP is 
> > >optimal on 84% of the superblocks
> > >
> > >int2000 benchmark: CP is optimal on 83% of the superblocks and WCP is 
> > >optimal on 94% of the superblocks
> > >
> > >These numbers do not necessarily reflect actual run-time performance 
> > >improvements, since they were collected in a standalone setup were 
> > >superblock data dependence graphs were extracted from gcc and scheduled
> > >separately for a simple machine model (dual issue in which one int and one 
> > >fp instruction can issue in each cycle). However, these results 
> > >do suggest that the WCP heuristic is significantly better than the simple CP.
> > >
> > >The reference for the WCP heuristic is:
> > >R. Bringmann, Compiler-Controlled Speculation, PHD thesis, Dept. of CS, 
> > >UIUC, IL 1995. (where the technique is called Dependence Height and 
> > >Speculative Yield DHASY).
> > >
> > >However, you don't really need to go there since the heuristic itself is 
> > >so simple and intuitive that my description above is almost sufficient. 
> > >Let me know if you are interested and I'll give you the details and 
> > >explain one particular subtility about it.
> > >
> > >  
> > >
> > Yes, I am interesting in this.  Could you give me the reference to WCP 
> > details (I can not find the document on the Internet).   I could give it 
> > a try.  May be this approach will work.
> > 
> > Vlad
> > 
> >