Skip to Main content Skip to Navigation
Journal articles

Minimal Unroll Factor for Code Generation of Software Pipelining

Mounira Bachir 1 Sid Touati 2, 1 Brault Frédéric 1 David Gregg 3 Albert Cohen 1, 4
1 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France
2 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : We address the problem of generating compact code from software pipelined loops. Although software pipelining is a powerful technique to extract fine- grain parallelism, it generates lifetime intervals spanning multiple loop iterations. These intervals require periodic register allocation (also called variable expansion), which in turn yields a code generation challenge. We are looking for the minimal unrolling factor enabling the periodic register allocation of software pipelined kernels. This challenge is generally addressed through one of: (1) hardware support in the form of rotating register files, which solve the unrolling problem but are expensive in hard- ware; (2) register renaming by inserting register moves, which increase the number of operations in the loop, and may damage the schedule of the software pipeline and reduce throughput; (3) post-pass loop unrolling that does not compromise throughput but often leads to impractical code growth. The latter approach relies on the proof that MAXLIVE registers (maximal number of values simultaneously alive) are sufficient for periodic register allocation (Eisenbeis et al. in PACT '95: Proceedings of the IFIP WG10.3 working conference on Parallel Architectures and Compilation Techniques, pages 264-267, Manchester, UK, 1995; Hendren et al. in CC '92: Proceedings of the 4th International Conference on Compiler Construction, pages 176-191, London, UK, 1992). However, the best existing heuristic for controlling this code growth--modulo variable expansion (Lam in SIGPLAN Not 23(7):318-328, 1988)--may not apply the correct amount of loop unrolling to guarantee that MAXLIVE registers are enough, which may result in register spills Eisenbeis et al. in PACT '95: Proceedings of the IFIP WG10.3 working conference on Parallel Architectures and Compilation Techniques, pages 264-267, Manchester, UK, 1995. This paper presents our research results on the open problem of minimal loop unrolling, allowing a software-only code generation M. Bachir * S.-A.-A. Touati (B) * F. Brault * D. Gregg * A. Cohen University of Nice Sophia-Antipolis, Nice, France e-mail: 123  that does not trade the optimality of the initiation interval ( I I ) for the compactness of the generated code. Our novel idea is to use the remaining free registers after periodic register allocation to relax the constraints on register reuse. The problem of minimal loop unrolling arises either before or after software pipelining, either with a single or with multiple register types (classes). We provide a formal problem definition for each scenario, and we propose and study a dedicated algorithm for each problem. Our solu- tions are implemented within an industrial-strength compiler for a VLIW embedded processor from STMicroelectronics, and validated on multiple benchmarks suites.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download
Contributor : Sid Touati <>
Submitted on : Friday, December 14, 2012 - 4:37:10 PM
Last modification on : Wednesday, November 4, 2020 - 3:34:44 AM
Long-term archiving on: : Friday, March 15, 2013 - 3:44:52 AM


Files produced by the author(s)




Mounira Bachir, Sid Touati, Brault Frédéric, David Gregg, Albert Cohen. Minimal Unroll Factor for Code Generation of Software Pipelining. International Journal of Parallel Programming, Springer Verlag, 2012, ⟨10.1007/s10766-012-0203-z⟩. ⟨hal-00764521⟩



Record views


Files downloads