An efficient resource-constrained global scheduling technique for superscalar and VLIW processors
Authors:
Open Access
- 10 December 1992
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMICRO Newsletter
- Vol. 23 (1-2) , 55-71
Abstract
We describe a new algorithm for parallelization of sequential code that eliminates anti and output dependence8 by renaming registers on an as-needed basis during scheduling. A dataflow attribute at the beginning of each basic block indicates what operations are available for moving up through this basic block. Scheduling consists of choosing the best operation from the set of operations that can move to a point, moving the instances of the operation to the point, making bookkeeping copies for edges that join the moving path but are not on it, and updating the dataflow attributes of basic blocks only on the paths that were traversed by the instances of the moved operations. The code motions are done globally without going through atomic transformations of percolation scheduling, for better eficiency. For performing the code motions, we use an intermediate representation that is directly executable as sequential RISC code, rather than VLIW code. As a result, the new algorithm can be used to generate parallelized code for multiple ALU superscalar processors as well. The enhanced pipeline scheduling algorithm for software pipelining of arbitrary code is reformulated within the framework of the new sequential RISC representation. The new algorithm has been implemented, and preliminary results on AIX utilities indicate that it requires significantly less compilation time than the percolation scheduling approach.Keywords
This publication has 9 references indexed in Scilit:
- Global instruction scheduling for superscalar machines1991
- Efficient and exact data dependence analysis1991
- Exploiting fine-grained parallelism through a combination of hardware and software techniques1991
- Practical dependence testing1991
- Boosting beyond static scheduling in a superscalar processor1990
- An efficient method of computing static single assignment form1989
- A global resource-constrained parallelization technique1989
- A development environment for horizontal microcodeIEEE Transactions on Software Engineering, 1988
- The program dependence graph and its use in optimizationACM Transactions on Programming Languages and Systems, 1987