On the Periodic Register Need in Software Pipelining - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue IEEE Transactions on Computers Année : 2007

On the Periodic Register Need in Software Pipelining

Résumé

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.
Fichier principal
Vignette du fichier
On_the_Periodic_Register.pdf (246.45 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00636095 , version 1 (26-10-2011)

Identifiants

Citer

Sid Touati. On the Periodic Register Need in Software Pipelining. IEEE Transactions on Computers, 2007, 56 (11), pp.1493-1504. ⟨10.1109/TC.2007.70752⟩. ⟨inria-00636095⟩

Collections

CNRS UVSQ
55 Consultations
170 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More