CIRCUIT RETIMING APPLIED TO DECOMPOSED SOFTWARE PIPELINING

This paper elaborates on a new view on software pipelining, called dec omposed software pipelining, and introduced by Gasperoni and Schwiegel shohn, and by Wang, Eisenbeis, Jourdan, and Su. The approach is to dec ouple the problem into resource constraints and dependence constraints . Resource constraints management amounts to scheduling an acyclic gra ph subject to resource constraints for which an efficiency bound is kn own, resulting in a bound for loop scheduling. The acyclic graph is ob tained by cutting some particular edges of the (cyclic) dependence gra ph. In this paper, we cut edges in a different way, using circuit reti ming algorithms, so as to minimize both the longest dependence path in the acyclic graph, and the number of edges in the acyclic graph. With this technique, we improve the efficiency bound given for Gasperoni a nd Schwiegelshohn algorithm, and we reduce the constraints that remain for the acyclic problem. We believe this framework to be of interest because it brings a new insight into the software problem by establish ing its deep link with the circuit retiming problem.