|
|
Overview
Reverse computation (executing code backward) is an efficient alternative to logging-based approaches. I am interested in various aspects of reverse computation: (a) exploring new practical applications and/or domains suited for reverse computation (b) realizing optimal reversible codes from traditional forward codes (c) automating reverse code generation from original forward codes.An excellent application for reverse computation is in rollback for Time Warp [TOMACS'99]. In my Ph.D. dissertation work, I have shown that reverse computation is an efficient alternative to traditional checkpointing-based rollback.
Much additional research remains, however. Recently, we have been able to extend this work even further, in plasma physics simulations [PADS'05].
Automation
Reverse code can be optimized quite a bit even though reversal of individual instructions can degenerate to log generation. For example, Fibonacci sequence generator code can be automatically reversed with no state saving, even though individual instructions are irreversible[GIT-TR-03].
To help in automating the reverse code generation, I developed a reverse C compiler. The picture below shows the architecture of the source-to-source compilation system [GIT-TR-99].
Performance
As a quick illustration, the graph below shows the performance improvement achieved by reverse computation on a benchmark application.
Related Publications
- Parallel Discrete Event Simulations of Physical Systems using Reverse
Computation
Yarong Tang, Kalyan Perumalla, Richard Fujimoto, Homa Karimabadi, Jonathan Driscoll and Yuri Omelchenko
to appear in ACM/IEEE/SCS Workshop on Parallel and Distributed Simulation (PADS), Monterey, CA, June 2005.
[Paper]
- Generating Perfect Reversals of Simple Linear Codes
Kalyan Perumalla
GIT-CERCS-TR-03-04
Center for Experimental Research in Computer Systems, Georgia Institute of Technology, May 2003.
[Paper]
- Efficient Optimistic Parallel Simulations using Reverse Computation
Christopher Carothers, Kalyan Perumalla and Richard Fujimoto
ACM Transactions on Modeling and Computer Simulation (TOMACS), Vol. 9, No. 3, July 1999.
[Paper]
- Using Reverse Circuit Execution for Efficient
Parallel Simulation of Logic Circuits
Kalyan Perumalla, and Richard Fujimoto
The International Society for Optical Engineering (SPIE) Annual Meeting, Seattle, WA, July 2002.
[Paper][Slides]
- Source Code Transformations for Efficient Reversibility
Kalyan Perumalla and Richard Fujimoto
GIT-CC-99-21
College of Computing, Georgia Institute of Technology, September 1999.
Compressed Postscript
- Techniques for Efficient Parallel Simulation and their
Application to Large-scale Telecommunication Network Models
Kalyan Perumalla
Ph.D. Thesis, College of Computing, Georgia Institute of Technology, December 1999
Compressed Postscript