Register allocation for optimal loop scheduling
Ning, Qi · 1993
One of the major challenges in designing optimizing compilers, especially for scientific computation, is to take advantage of the parallelism in loops in order to obtain maximum speedup on parallel computer architectures. Optimal loop scheduling is therefore one of the most important topics studied by many computer scientists. However how to allocate minimum number of registers to support optimal loop scheduling for parallel architectures is less understood. In this thesis, we propose a simultaneous scheduling and register allocation approach for a parallelizing compiler, which will find one among all the time-optimal periodic schedules that uses minimum amount of registers. We prove that the general problem of finding such an optimal scheduling together with register allocation is NP-complete. Then we propose a practical approach to divide the register allocation problem into two steps. The first step solves a minimum buffer allocation problem, which will find a time-optimal periodic schedule using minimum number of buffers. We give a polynomial time algorithm to solve this problem. The second step analyzes the live ranges of the variables and uses coloring algorithms to reduce the register requirements by sharing. The algorithm has been implemented and used to test selected loops on benchmark programs. Testing results are reported in this thesis. In order to allocate enough memory spaces to support optimal dynamic schedules, we propose a cycle balancing scheme that allocates buffers to the arcs of the dataflow graph representing a loop, so that it can allow a loop being scheduled dynamically to achieve maximum speedup. We show how to formulate the problem into an integer programming problem. Practical polynomial time solution algorithms are given.