Optimal instruction scheduling and register allocation for multiple-issue processors.

Abstract

As processors make use of wider instruction issue and deeper pipelines, the number of instructions in flight and consequently the number of simultaneously live values per cycle increases. Fine grain scheduling and register allocation algorithms need to be closely coupled to make the best use of the available parallelism. In my research, I have developed a group of optimal scheduling and register allocation algorithms for statically scheduled processors that can issue more than one operation per cycle. This class of processors includes vector supercomputers and VLIW computers such as the Cydra-5 and Multiflow Trace VLIW computers and the Kendall Square Research (KSR) machine. My contributions include: An integer linear programming formulation that computes the shortest schedule for a general multiple-issue processor. This formulation inserts spills where needed, puts no restrictions on the program dependence graph, and admits a wide range of processors with specifiable issue widths, instruction latencies, and register set size. A quadratic time algorithm that optimally schedules a binary dependence tree on a dual-issue processor under the classical restriction that the operations all have unit latency. By showing that at least one optimal solution is in contiguous form and that all k-spill contiguous form schedules have the same cost, I am able to eliminate all but one k-spill candidate schedule from consideration. A dynamic programming algorithm to find an optimal register allocation that minimizes spill cost for a given, dual-issue, instruction schedule. Value exclusions and implicit and explicit pruning rules are used to substantially reduce the size of the search space.