On Periodic Register Need in Software Pipelining

This paper presents several theoretical and fundamental results on the register need in periodic schedules, also known as MAXLIVE. Our first contribution is a novel formula for computing the exact number of registers needed by a scheduled loop. This formula has two advantages: Its computation can be done by using a polynomial algorithm with O(n lg n) complexity (n is the number of instructions in the loop) and it allows the generalization of a previous result [13]. Second, during software pipelining, we show that the minimal number of registers needed may increase when incrementing the initiation interval (II), which is contrary to intuition. For the case of zero architectural delays in accessing registers, we provide a sufficient condition for keeping the minimal number of registers from increasing when incrementing the II. Third, we prove an interesting property that enables us to optimally compute the minimal periodic register sufficiency of a loop for all its valid periodic schedules, irrespective of II. Fourth and last, we prove that the problem of optimal stage scheduling under register constraints is polynomially solvable for a subclass of data dependence graphs, whereas this problem is known to be NP-complete for arbitrary dependence graphs [7]. Our latter result generalizes a previous achievement [13] which addressed data dependence trees and forest of trees. In this study, we consider cyclic data dependence graphs without taking into account any resource constraints. The aim of our theoretical results on the periodic register need is to help current and future software pipeliners achieve significant performance improvements by making better (if not the best) use of the available resources.