Minimisation du facteur de déroulage de boucle dans une allocation périodique de registres
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
This thesis addresses 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 hardware; (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 are sufficient for periodic register allocation ; yet the only heuristic to control the amount of post-pass loop unrolling does not achieve this bound or leads to undesired register spills. This thesis gathers our extensive research results on the open problem of minimal loop unrolling allowing a software-only code generation that does not trade the optimality of the initiation interval (II) for the compactness of the generated code. At the first part of this thesis, we propose to use the remaining free registers after periodic register allocation to relax the constraints on register reuse. We show that the problem of minimal loop unrolling arises either before or after software pipelining, either with a single or with multiple register types. We provide a formal problem definition for each situation, and we propose and study a dedicated algorithm for each problem. These solutions are implemented within an industrial-strength compiler for a VLIW embedded processor from STMicroelectronics (ST2xx processor family). Our large-scale experiments on multiple benchmarks family (LAO, FFMPEG, MEDIABENCH, SPEC2000, SPEC2006) demonstrate the effectiveness of the proposed unroll degree minimisation, both in terms of code size and in terms of initiation intervals, along with satisfactory compilation times. Nevertheless, some loops still require high unrolling degrees even after our minimisation. At the second part of this thesis, we study, for these occasional high unrolling degrees, the potential for live range splitting to reduce kernel loop unrolling with details of how to introduce new move instructions without inscreasing II. In fact, extra move instructions can be added where the software pipelining schedule leaves some free units to carry the information between the splitted variables. Concerning the experimental evaluation, we carefully studied the efficiency of this method in standalone context. The different experiments show that the exhaustive solution for splitting variables produce dramatic positive results.
Abstract FR:
La génération de code est un des problèmes majeurs dans les compilateurs modernes en raison de l'évolution rapide des processeurs et de l'introduction de parallélisme interne entre instructions appelé parallélisme à grain fin. Nous nous sommes intéressés a la partie la plus sensible des programmes à savoir les boucles. De nos jours, une phase d'ordonnancement des instructions appelé pipeline logiciel est devenue indispensable pour optimiser le code des boucles. Cette technique apporte des contraintes supplémentaires car des instructions de plusieurs itérations peuvent s'entremêler. Au sein de cette thèse, nous nous focalisons sur un objectif clair : comment générer un code compact pour une boucle ordonnancée avec la technique du pipeline logicielle? Le pipeline logiciel permet de générer des boucles hautement optimisées pour la vitesse d'exécution, mais au prix d'une forte expansion de code généré par le déroulage de la boucle engendré par la phase d'allocation périodique des registres. Minimiser ce degré de déroulage constitue notre objectif de recherche dans le volet de la minimisation de la taille de code sans perte de performance. Le déroulage de boucles doit être appliqué lorsque les variables de la boucle pipelinée logiciellement, sont en vie pendant plus d'une itération, ce qui accroît la taille du code. Le déroulage influence aussi les besoins en registres. Les outils SIRA et le Meeting Graph, développés dans cette optique, sont des environnements destinée à l'allocation périodique des registres. SIRA réalise l'allocation périodique des registres pour les boucles avant la phase du pipeline logiciel par contre le Meeting Graph réalise l'allocation périodique des registres pour les boucles après la phase du pipeline logiciel. Cependant, le degré de déroulage proposé, par ces deux méthodes, peut être très grand: Dans un premier volet, cette thèse propose de le minimiser après avoir formulé le problème. Notre solution mathématique montre comment calculer le degré de déroulage minimal en utilisant les registres restants après la phase d'allocation périodique des registres. Nous avons implémenté cette solution dans SIRA et le Meeting Graph qui proposent dorénavant une allocation périodique de registres avec un degré de déroulage minimal. Les statistiques sur les résultats de nos expériences montrent qu'en pratique le degré de déroulage minimal trouvé par notre solution est acceptable. Comme ces résultats ne prennent en compte qu'un seul type de registre, nous avons aussi généralisé cette solution pour des processeurs qui ont plusieurs types de registres. Nous avons appliqué la solution sur les codes de ST-Microelectronics, après avoir intégré la nouvelle version de SIRA dans le LAO (compilateur de ST-Microelectronics). Cependant, quelques degrés de déroulage restent grands. Pour pallier ce problème, la deuxième partie de cette thèse étudie la minimisation du degré de déroulage par le rajout de move operations sans compromettre le parallélisme entre instructions. Une étude expérimentale sur plusieurs boucles, montre que la technique de renommage de registres sans altérer les performances, minimise le degré de déroulage des boucles.