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 > > > >
