kinch@chan.csd.uwo.ca (Dave Kinchlea) (01/08/91)
The subject pretty well says it all, I need to write an instruction scheduler and would like to get an idea of existing algorithms. Thanx in advance cheers kinch
preston@ariel.rice.edu (Preston Briggs) (01/09/91)
For scheduling within basic blocks Efficient Instruction Scheduling for a Pipelined Architecture Gibbons and Muchnick Sigplan 86 Symposium on Compiler Construction (in Sigplan Notices, Volume 21, Number 7) more recently, there a paper by Warren in the January 1990 issue of IBM Journal of R & D that pretty much subsumes Gibbons and Muchnick. There are several papers by Gross and Hennessy. Unfortunately, there scheme is more expensive than those above. Further, they advocate scheduling after register allocation -- a fundamental mistake (IMHO). The basic block methods can be extended to trees of blocks (extended basic blocks) with some effort. A further paper in the January 90 IBM Journal of R&D (by Golumbic and someone) discusses other scheduling ideas across basic blocks. Scheduling loops is much more of a research topic. Important papers by Lam and by Aiken and Nicolau appear in the Sigplan 88 proceedings. There's also the trace scheduling work. A good resource is Bulldog: A Compiler for VLIW Architectures Ellis (PhD Thesis from Yale, about 84. Published in the MIT Distinguished Dissertation series) Preston Briggs
mark@hubcap.clemson.edu (Mark Smotherman) (01/09/91)
See the work of my former M.S. student: Sanjay Krishnamurthy, "A Brief Survey of Papers on Scheduling for Pipelined Processors," SIGPLAN Notices, vol. 25, no. 7, July 1990, pp. 97-106. He references 29 papers. Sanjay is now at Rice University working on a Ph.D. (best wishes, Sanjay!) -- Mark Smotherman, Comp. Sci. Dept., Clemson University, Clemson, SC 29634 INTERNET: mark@hubcap.clemson.edu UUCP: gatech!hubcap!mark