Spatial Complexity of Reversibly Computable DAG

Mouad Bahi 1 Christine Eisenbeis 1
1 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France
Abstract : 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.
Type de document :
Communication dans un congrès
international conference on Compilers, architecture, and synthesis for embedded systems, Oct 2009, Grenoble, France. 2009
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00554738
Contributeur : Mouad Bahi <>
Soumis le : mardi 11 janvier 2011 - 11:28:08
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 12 avril 2011 - 02:44:38

Fichier

p47-bahi.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00554738, version 1

Collections

Citation

Mouad Bahi, Christine Eisenbeis. Spatial Complexity of Reversibly Computable DAG. international conference on Compilers, architecture, and synthesis for embedded systems, Oct 2009, Grenoble, France. 2009. 〈inria-00554738〉

Partager

Métriques

Consultations de la notice

409

Téléchargements de fichiers

112