Experimental Study of Register Saturation in Basic Blocks and Super-Blocks: Optimality and heuristics - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

Experimental Study of Register Saturation in Basic Blocks and Super-Blocks: Optimality and heuristics

Résumé

Register saturation (RS) is the exact maximal register need of all valid schedules of a data dependence graph \cite{Touati:RSILP05}. Its optimal computation is NP-complete. This report proposes two variants of heuristics for computing the acyclic RS of directed acyclic graphs (DAG). The first one improves the previous greedy-k heuristic \cite{Touati:RSILP05} in terms of approximating the RS with equivalent computation times. The second heuristic is faster, has better RS approximation than greedy-k, but scarifies the computation of saturating values. In order to evaluate the efficiency of these two heuristics, we designed an optimal combinatorial algorithm computing the optimal RS for tractable cases, which turns out to be satisfactory in practice. Extensive experiments have been conducted on thousands of data dependence graphs extracted from FFMPEG, MEDIABENCH, SPEC2000 and SPEC2006 benchmarks. Numerical results are presented to demonstrate the efficiency of the two proposed heuristics, so hence they can replace the greedy-k heuristic presented in \cite{Touati:RSILP05}. Our RS computation methods are distributed as a C independent library (\texttt{RSlib}) under LGPL licence.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
main_RS_report.pdf (403.31 Ko) Télécharger le fichier
RSlib-1.1.tar.bz2 (96.16 Ko) Télécharger le fichier
public_data.tar.bz2 (360.91 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Autre
Format : Autre
Loading...

Dates et versions

inria-00431103 , version 1 (27-11-2009)

Identifiants

  • HAL Id : inria-00431103 , version 1

Citer

Sébastien Briais, Sid Touati. Experimental Study of Register Saturation in Basic Blocks and Super-Blocks: Optimality and heuristics. [Research Report] 2009, pp.33. ⟨inria-00431103⟩

Collections

CNRS UVSQ LARA
156 Consultations
182 Téléchargements

Partager

Gmail Facebook X LinkedIn More