Xref: utzoo comp.misc:2082 comp.arch:3889
Path: utzoo!mnetor!uunet!husc6!mit-eddie!ll-xn!ames!sgi!bron
From: bron@olympus.SGI.COM (Bron C. Nelson)
Newsgroups: comp.misc,comp.arch
Subject: Re: Instruction Scheduling
Message-ID: <12560@sgi.SGI.COM>
Date: 10 Mar 88 22:07:53 GMT
References: <12513@sgi.SGI.COM>
Sender: daemon@sgi.SGI.COM
Organization: Silicon Graphics Inc, Mountain View, CA
Lines: 88
Keywords: optimization   pipeline constraints  code re-organization
Summary: Bibliography

(Hummm... I see I somehow managed to stupidly post BOTH versions
of my introduction article.)


In an attempt to deflect the endless bickering over the RPM40
from comp.arch, I am taking a cue from Randell Jesup and am
trying to start a discussion of Instruction Scheduling.  Please
contribute your own experiences.

Let's start things off with the best of my scanty bibliography.
I strongly encourage people to suggest other relevant papers
(e-mail to me and I'll summarize, or post directly if you're so
inclined).



Thomas Gross
"Code Optimization of Pipeline Constraints"
Stanford University
Computer Systems Laboratory  Technical Report No. 83-255
December 1983

Based on the author's PhD dissertation.  Describes an instruction
scheduler that (I believe) formed the basis of the one that is
used by MIPS Co.  Scheduling is done after register selection
(post-pass scheduling).



Phillip Gibbons and Steven Muchnick
"Efficient Instruction Scheduling for a Pipelined Architecture"
Proceedings of the 1986 SIGPLAN Compiler Construction Conference
pp. 11 - 16

Instruction scheduler for the HP Precision Architecture.  Seems
to be strongly based on Gross's work.



Wei-Chung Hsu
"Register Allocation and Code Scheduling for Load/Store Architectures"
1987 Ph.D thesis
University of Wisconsin, Madison

Discusses pros and cons of scheduling before or after register
allocation (pre-pass vs post-pass methods).  Gives examples and
good algorithms for both.  Talks about the desirability of doing
integrated scheduling and register allocation and gives simple
methods of keeping the one in mind while doing the other to help
improve both.



John Ellis
"Bulldog: A Compiler for VLIW Architectures"
1985 Ph.D thesis
Yale University
Also published in the 
ACM Doctoral Dissertation Award Series by MIT press.

Trace scheduling explained.  A lot of reading, but well worth it.
The idea that makes VLIW machines work.



Rajiv Gupta and Mary Soffa
"Region Scheduling"
Proceedings of the 2nd International Conference on Supercomputing
International Supercomputing Institute, Inc. 1987
Vol III, pp 141 - 148

Describes work-in-progress without any hard numbers, but this looks
like a very clever idea.  The authors claim superiority over trace
scheduling on several grounds.  The ideas seem more solidly based
than trace scheduling (which always struck me as a good ad-hoc idea
carried to extremes) as well as easier to understand.  If this lives
up to its promises, I would rate it as something to follow closely.
BTW - anyone know where I can contact the authors/get more info?



Well, that's it!  (except for old and/or scummy papers that aren't
worth reading).  Surely some of you Out There can suggest more.



Bron Nelson  bron@sgi.com
Don't blame my employers for my opinions