A unified approach to instruction scheduling and register allocation on clustered VLIW processors

摘要

VLIW (Very Long Instruction Word) processors issue and execute multiple operations in parallel, on different functional units at each processor cycle. A major problem with VLIW processors is that a single register file hampers the scalability of the processor. Clustering is an efficient technique for improving the scalability and energy consumption of VLIW processors. In a clustered VLIW processor, each cluster has its own functional units and local register file with fewer registers and ports. Clusters are connected by an inter-cluster communication network. An optimising compiler plays a key role in improving the ILP (Instruction Level Parallelism) for clustered VLIW processors. Instruction scheduling and register allocation are two important parts in an optimising compiler for clustered VLIW processors. These two parts are closely related and have a significant impact on the ILP. This thesis studies instruction scheduling and register allocation on clustered VLIW processors, and presents a set of efficient techniques for these problems.Firstly, we study the problem of scheduling a set of operations of a basic block on a clustered VLIW processor where for any two functional units, the two subsets of operations executed on these two functional units are either the same or disjoint. The objective is to minimise the schedule length for all the operations in the basic block. We propose a novel priority-based, phase coupled heuristic. When computing the operation priorities, our heuristic considers not only the inter-operation latencies, but also the processor resource constraints. After computing the priorities, our heuristic schedules each operation on a functional unit of a cluster by considering different cases. Simulation results show that our heuristic significantly improves over two previous heuristics, UAS and Integrated, for the basic blocks taken from the MediaBench II benchmark suite based on six processors.Secondly, we study the problem of scheduling a set of operations of a basic block on a clustered VLIW processor where each functional unit can execute an arbitrary subset of operations. We extend the previous scheduling heuristic by using the maximum bipartite matching to find the latest start time and the earliest start time of an operation. Simulation results show that our extended heuristic significantly improves over UAS and Integrated for the basic blocks taken from the MediaBench II benchmark suite based on three processors.Thirdly, we study the problem of integrated instruction scheduling and register allocation. We propose a unified approach which integrates instruction scheduling, cluster assignment, and register allocation into a single phase. Our unified approach aims at minimising the overall schedule length of each basic block in a program, as well as balancing the register pressure on each cluster. It consists of an instruction scheduler and an incremental register allocator. The instruction scheduler schedules all the basic blocks of a program in reverse postorder, and all the operations of each basic block based on their priorities. The operation priorities are dynamically updated to reduce the register pressure during the instruction scheduling. When scheduling an operation, the instruction scheduler allocates physical registers to virtual registers of the operation by using the incremental register allocator. When performing cluster assignment for an operation,the instruction scheduler considers both the start time of the operation and the register pressure on each cluster, leading to a balanced usage of registers on all the clusters. Three different register allocation strategies and a register spill strategy have been developed. The simulation results show that our approach outperforms a previous approach, CARS, for three processors, in terms of the average schedule lengths of the basic blocks taken from the MediaBench II benchmark suite.Lastly, we extend our unified approach to instruction scheduling and register allocation by considering lifetime holes. A lifetime hole is an interval in which a variable does not contain a valid value. We propose efficient techniques for utilising lifetime holes on the-fly during register allocation and incorporate these techniques into our unified approach to instruction scheduling and register allocation. Furthermore, we present our simulation results showing that the unified approach considering lifetime holes performs better than the unified approach without considering lifetime holes.