Skip to Main content Skip to Navigation
Reports

Optimal Register Saturation in Acyclic Superscalar and VLIW Codes

Sid Touati 1
1 A3 - Advanced analysis to code optimization
UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : In a previous work [TT00], we theoretically studied the register saturation notion in the acyclic data dependence graphs (DDG). It consists in computing the exact maximal number of the registers needed to achieve the computation of the DDGs independently from the schedules. We proved that this problem is NP-complete and we proposed a greedy heuristic to solve it. In this work, we study how to compute the optimal solution using the integer linear programming. Also, new theorems are given to formally prove some of our assertions written in the previous report. We prove also that the problem of reducing the register saturation by introducing new arcs is an NP-hard problem, and we give a method to compute the optimal solution using the integer linear programming.
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072324
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 8:24:21 PM
Last modification on : Wednesday, September 16, 2020 - 4:57:21 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:03:52 PM

Identifiers

  • HAL Id : inria-00072324, version 1

Collections

Citation

Sid Touati. Optimal Register Saturation in Acyclic Superscalar and VLIW Codes. RR-4263, INRIA. 2001. ⟨inria-00072324⟩

Share

Metrics

Record views

249

Files downloads

168