On minimizing register usage of linearly scheduled algorithms with uniform dependencies

摘要

Efficient register usage is crucial to avoid the bottlenecks associated with accessing memory. This problem becomes magnified in loop nests since the number of variable accesses accumulated increases in each iteration. Although cache memory helps alleviate the speed penalties associated with memory access, having a register file with sufficient capacity to avoid spilling registers is needed to extract the maximum performance of a system.rnIn this paper, we discuss an approach to minimize register pressure of loop nests with regular dependencies through the use of linear schedules in conjunction with loop unrolling. Linear scheduling is a method of partitioning the indexes of loop nests into a series of hyperplanes defined by a vector parameter ∏. Once a suitable linear schedule has been discovered, the loop nest will be unrolled in a way that satisfies ∏. For each linear schedule, we determine the minimum number of registers needed by the loop nest to avoid spilling (i.e. each variable is loaded into a register exactly once during a loop nest). In the case where the loop nests contains variables with at most one dependence we present a method to estimate the number of registers used. Otherwise we employ a more general method to determine the exact register requirements. Our experimental results indicate that an optimal linear schedule uses 36% fewer register than a schedule that uses the most registers on average.