Reverse computation is a software application of the concept of reversible computing. Because it offers a possible solution to the heat problem faced by chip manufacturers, reversible computing has been extensively studied in the area of computer architecture. The promise of reversible computing is that the amount of heat loss for reversible architectures would be minimal for significantly large numbers of transistors. Rather than creating entropy (and thus heat) through destructive operations, a reversible architecture conserves the energy by performing other operations that preserve the system state. The concept of reverse computation is somewhat simpler than reversible computing in that reverse computation is only required to restore the equivalent state of a software application, rather than support the reversibility of the set of all possible instructions. Reversible computing concepts have been successfully applied as reverse computation in software application areas such as database design, checkpointing and debugging, and code differentiation.
Reverse Computation for Parallel Discrete Event Simulation
Based on the successful application of Reverse Computation concepts in other software domains, Chris Carothers, Kalyan Perumalla and Richard Fujimoto suggest the application of reverse computation to reduce state saving overheads in parallel discrete event simulation (PDES). They define an approach based on reverse event codes (which can be automatically generated), and demonstrate performance advantages of this approach over traditional state saving for fine-grained applications (those with a small amount of computation per event). The key property that reverse computation exploits is that a majority of the operations that modify the state variables are “constructive” in nature. That is, the undo operation for such operations requires no history. Only the most current values of the variables are required to undo the operation. For example, operators such as ++, ––, +=, -=, *= and /= belong to this category. Note, that the *= and /= operators require special treatment in the case of multiply or divide by zero, and overflow / underflow conditions. More complex operations such as circular shift (swap being a special case), and certain classes of random number generation also belong here. Operations of the form a = b, modulo and bitwise computations that result in the loss of data, are termed to be destructive. Typically these operations can only be restored using conventional state-saving techniques. However, we observe that many of these destructive operations are a consequence of the arrival of data contained within the event being processed. For example, in the work of Yaun, Carothers, et al., with large-scale TCP simulation, the last-sent time records the time stamp of the last packet forwarded on a router logical process. The swap operation makes this operation reversible.
History of Reverse Computation as applied to Parallel Discrete Event Simulation
In 1985 Jefferson introduced the optimistic synchronization protocol, which was utilized in parallel discrete event simulations, known as Time Warp. To date, the technique known as Reverse Computation has only been applied in software for optimistically synchronized, parallel discrete event simulation. In December 1999, Michael Frank graduated from the University of Florida. His doctoral thesis focused on reverse computation at the hardware level, but included descriptions of both an instruction set architecture and a high level programming language (R) for a processor based on reverse computation.
… excerpt ends here. Continue reading the full article.
