Spatial complexity of reversibly computable DAG

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Spatial complexity of reversibly computable DAG

Full text

Pdf (1.34 MB)

Source

International Conference on Compilers, Architecture and Synthesis for Embedded Systems archive
Proceedings of the 2009 international conference on Compilers, architecture, and synthesis for embedded systems table of contents

Grenoble, France

SESSION: Compiler techniques for performance table of contents

Pages 47-56

Year of Publication: 2009

ISBN:978-1-60558-626-7

Authors

Mouad Bahi	Inria and LRI, Université Paris-Sud 11, Orsay, France
Christine Eisenbeis	Inria and LRI, Université Paris-Sud 11, Orsay, France

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 16, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1629395.1629404 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	H. G. Baker. NRVERSAL of fortune -- the thermodynamics of garbage collection. Int'l Workshop on Memory Mgmt, 1992.
	2	C. H. Bennett. Logical reversibility of a computation. IBM Journal of Research and Development, 1973.
	3	C. H. Bennett. Time-space tradeo's for reversible computation. SIAM J. Comput, 1989.
	4	D. Berson, R. Gupta, and M. L. Soffa. Ursa: A unified resource allocator for registers and functional units in vliw architectures. In In Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, 1992.
	5	D. A. Berson, R. Gupta, and M. L. Soffa. Integrated instruction scheduling and register allocation techniques. In Proc. of the Eleventh International Workshop on Languages and Compilers for Parallel Computing, LNCS, 1998.
	6	P. G. Bishop. Using Reversible Computing to Achieve Fail-safety. IEEE Computer Society, 1997.
	7	S. Burckel and E. Gioan. In situ design of register operations. In ISVLSI '08: IEEE Computer Society Annual Symposium on Very-Large-Scale Integration, 2008.
	8	S.-K. Chen, W. K. Fuchs, and J.-Y. Chung. Reversible debugging using program instrumentation. IEEE Trans. Softw. Eng., 2001.
	9	R. P. Dilworth. A decomposition theorem for partially ordered sets. Ann. of Math., 1950.
	10	M. P. Frank. The R programming language and compiler. MIT RC Pro j. Memo #M8, 1997.
	11	M. P. Frank. The physical limits of computing. Computing in Science and Engg., 2002.
	12	M. Iri, K. Tanabe, K. Academic, and A. Griewank. On automatic differentiation. In in Mathematical Programming: Recent Developments and Applications,
	13	k. Perumalla and R. Fujimoto. Source-code transformations for efficient reversibility. Technical Report GIT-CC-99-21, College of Computing, Georgia Tech., 1999.
	14	T. F. Knight, F. R. Morgenthaler, C. J. Vieri, and C. J. Vieri. Pendulum: A reversible computer architecture. Master's thesis, MIT Artificial Intelligence Laboratory, 1995.
	15	T. Koju, S. Takada, and N. Doi. An efficient and generic reversible debugger using the virtual machine based approach. In VEE '05: Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments. ACM, 2005.
	16	R. Kralovic. Time and space complexity of réversible pebbling. In SOFSEM '01: Proceedings of the 28th Conference on Current Trends in Theory and Practice of Informatics Piestany, 2001.
	17	R. Landauer. Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 1961.
	18	C. Lutz and H. Derby. Janus: a time-reversible language. Caltech class pro ject, 1982.
	19	D. Maslov and G. W. Dueck. Reversible cascades with minimal garbage. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004.
	20	P. Matherat and M. T. Jaekel. Logical Dissipation of Automata Implements -- Dissipation of Computation. Technique et Science Informatiques, 1996.
	21	U. Naumann. On optimal DAG reversal. Technical Report AIB-2007-05, 2007.
	22	P. Vitanyi. Time, space, and energy in réversible computing. In CF '05: Proceedings of the 2nd conference on Computing frontiers. ACM, 2005.
	23	H. Yang, G. R. Gao, and C. Leung. On achieving balanced power consumption in software pipelined loops. In CASES '02: Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, 2002.