Minimizing Variables' Lifetime in Loop-Intensive Applications

摘要

In this paper, we address a set of research problems regarding loop-intensive applications. The first problem consists of minimizing variables' lifetime under timing constraints. Any variable that is alive for more than one iteration must be saved by for instance storing it into a register. The second problem is derived from the first one, and consists of balancing variables' lifetime for a target total number of registers and under timing constraints. For the third problem, we focus on minimizing variables' lifetime in the context of software pipelining in the case of one loop as well as nested loops. We provide methods to solve these three problems, and show that a set of them have polynomial run-time. Once these methods are used, one may need to solve the problem of generating the transformed code and reducing its size. We provide algorithms to solve this fourth problem. Designers face these problems during hardware-software co-design, and in designing embedded systems as well as system-on-chip. Solving these problems is also useful in low power design. We exercise some of these methods on known benchmarks, and provide obtained numerical results that show their effectiveness. We solve these problems using techniques related to retiming, an algorithm originally developed for hardware optimization.