Decomposing Meeting Graph Circuits to Minimise Kernel Loop Unrolling

Mounira Bachir 1 Sid Touati 2 Albert Cohen 1
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, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : This article studies an important open problem in backend compilation regarding loop unrolling after periodic register allocation. Although software pipelining is a powerful technique to extract fine-grain parallelism, variables can stay alive across more than one kernel iteration, which is challenging for code generation. The classical software solution that does not alter the computation throughput consists in unrolling the loop a posteriori (13; 12). However, the resulting unrolling degree is often unacceptable and may reach absurd levels. Alternatively, loop unrolling can be avoided thanks to software register renaming. This is achieved through the insertion of move operations. However, inserting those operations may increase the initiation interval (II) and nullifies the benefits of software pipelining itself. We propose in this article a new technique to minimise the loop unrolling degree generated after periodic register allocation. In fact, this technique consists on decomposing the generated meeting graph circuits by inserting move instructions without compromising the throughput benefits of software pipelining. The different experiments showed that the execution time is acceptable and good results can be produced when we have many functional units which can execute move operations.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00637938
Contributor : Sid Touati <>
Submitted on : Thursday, November 3, 2011 - 12:14:23 PM
Last modification on : Thursday, April 5, 2018 - 12:30:12 PM
Document(s) archivé(s) le : Saturday, February 4, 2012 - 2:25:17 AM

File

Decomposing_Meeting.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00637938, version 1

Collections

Citation

Mounira Bachir, Sid Touati, Albert Cohen. Decomposing Meeting Graph Circuits to Minimise Kernel Loop Unrolling. 9th Workshop on Optimizations for DSP and Embedded Systems (ODES-9), In conjunction with: International Symposium on Code Generation and Optimization (CGO), Apr 2011, Chamonix, France. pp.8. ⟨inria-00637938⟩

Share

Metrics

Record views

429

Files downloads

109