Spatial Complexity of Reversibly Computable DAG - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Spatial Complexity of Reversibly Computable DAG

Résumé

In this paper we address the issue of making a program reversible in terms of spatial complexity. Spatial complexity is the amount of memory/register locations required for performing the computation in both forward and backward directions. Spatial complexity has important relationship with the intrinsics power consumption required at run time; this was our primary motivation. But it has also important relationship with the trade off between storing or recomputing reused intermediate values, also known as the rematerialization problem in the context of compiler register allocation, or the checkpointing issue in the general case. We present a lower bound of the spatial complexity of a DAG (directed acyclic graph) with reversible operations, as well as a heuristic aimed at finding the minimum number of registers required for a forward and backward execution of a DAG . We define energetic garbage as the additional number of registers needed for the reversible computation with respect to the original computation. We have run experiments that suggest that the garbage size is never more than 50% of the DAG size for DAGs with unary/binary operations.
Fichier principal
Vignette du fichier
p47-bahi.pdf (1.28 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00554738 , version 1 (11-01-2011)

Identifiants

  • HAL Id : inria-00554738 , version 1

Citer

Mouad Bahi, Christine Eisenbeis. Spatial Complexity of Reversibly Computable DAG. international conference on Compilers, architecture, and synthesis for embedded systems, Oct 2009, Grenoble, France. ⟨inria-00554738⟩
281 Consultations
194 Téléchargements

Partager

Gmail Facebook X LinkedIn More