Using The Meeting Graph Framework to Minimise Kernel Loop Unrolling for Scheduled Loops

Mounira Bachir 1 David Gregg 2 Sid Touati 3
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
Abstract : This paper improves our previous research effort [1] by providing an efficient method for kernel loop unrolling minimisation in the case of already scheduled loops, where circular lifetime intervals are known. When loops are software pipelined, the number of values simultaneously alive becomes exactly known giving better opportunities for kernel loop unrolling. Furthermore, fixing circular lifetime intervals allows us to reduce the algorithmic complexity of our method compared to [1] by computing a new research space for minimal kernel loop unrolling. The meeting graph (MG) [3] is one of the frameworks proposed in the literature which models loop unrolling and register allocation together in a common formal framework for software pipelined loops. Although MG significantly improves loop register allocation, the computed loop unrolling may lead to unpractical code growth. This work proposes to minimise the loop unrolling degree in the meeting graph by making an adaptation of the approach described in [1]. We explain how to reduce the research space for minimal kernel loop unrolling in the context of MG, yielding to a reduced algorithmic complexity. Furthermore, our experiments on SPEC2000, SPEC2006, MEDIABENCH and FFMPEG show that in concrete cases the loop unrolling minimisation is very fast and the minimal loop unrolling degree for 75% of the optimised loops is equal to 1 (i.e. no unroll), while it is equal to 7 when the software pipelining (SWP) schedule is not fixed.
Type de document :
Communication dans un congrès
22nd International Workshop on Languages and Compilers for Parallel Computing (LCPC 2009), Oct 2009, Newark, United States. Springer, 5898, pp.278-292, 2009, LNCS. 〈10.1007/978-3-642-13374-9_19〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00643759
Contributeur : Sid Touati <>
Soumis le : mardi 22 novembre 2011 - 17:00:42
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : jeudi 23 février 2012 - 02:30:49

Fichier

Using_The_Meeting_Graph.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Mounira Bachir, David Gregg, Sid Touati. Using The Meeting Graph Framework to Minimise Kernel Loop Unrolling for Scheduled Loops. 22nd International Workshop on Languages and Compilers for Parallel Computing (LCPC 2009), Oct 2009, Newark, United States. Springer, 5898, pp.278-292, 2009, LNCS. 〈10.1007/978-3-642-13374-9_19〉. 〈hal-00643759〉

Partager

Métriques

Consultations de la notice

488

Téléchargements de fichiers

102