On the Periodic Register Need in Software Pipelining

Abstract : This article presents several theoretical and fundamental results on register need in periodic schedules, also known as MAXLIVE. Our first contribution is a novel formula for computing the exact number of registers needed by a scheduled loop. This formula has two advantages: its computation can be done using a polynomial algorithm with O(n lg n) complexity (n is the number of instructions in the loop), and it allows the generalization of a previous result [13]. Second, during software pipelining, we show that the minimal number of registers needed may increase when incrementing the initiation interval (II), contrary to intuition. For the case of zero architectural delays in accessing registers, we provide a sufficient condition for keeping the minimal number of registers from increasing when incrementing the II. Third, we prove an interesting property that enables to optimally compute the minimal periodic register sufficiency of a loop for all its valid periodic schedules, irrespective of II. Fourth and last, we prove that the problem of optimal stage scheduling under register constraints is polynomially solvable for a subclass of data dependence graphs, while this problem is known to be NP-complete for arbitrary dependence graphs [7]. Our latter result generalizes a previous achievement [13] which addressed data dependence trees and forest of trees. In this study we consider cyclic data dependence graphs without taking into account any resource constraints. The aim of our theoretical results on periodic register need is to help current and future software pipeliners achieve significant performance improvements by making better (if not best) use of the available resources.
Type de document :
Article dans une revue
IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2007, 56 (11), pp.1493-1504. 〈http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4336298&tag=1〉. 〈10.1109/TC.2007.70752〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00636095
Contributeur : Sid Touati <>
Soumis le : mercredi 26 octobre 2011 - 16:47:50
Dernière modification le : jeudi 11 janvier 2018 - 06:21:30
Document(s) archivé(s) le : vendredi 27 janvier 2012 - 02:35:04

Fichier

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

Identifiants

Collections

Citation

Sid Touati. On the Periodic Register Need in Software Pipelining. IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2007, 56 (11), pp.1493-1504. 〈http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4336298&tag=1〉. 〈10.1109/TC.2007.70752〉. 〈inria-00636095〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

78