Efficient optimistic parallel simulations using reverse computation
- 1 July 1999
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 9 (3), 224-253
- https://doi.org/10.1145/347823.347828
Abstract
In optimistic parallel simulations, state-saving techniques have traditionally been used to realize rollback. In this article, we propose reverse computation as an alternative approach, and compare its execution performance against that of state-saving. Using compiler techniques, we describe an approach to automatically generate reversible computations, and to optimize them to reap the performance benefits of reverse computation transparently. For certain fine-grain models, such as queuing network models, we show that reverse computation can yield significant improvement in execution speed coupled with significant reduction in memory utilization, as compared to traditional state-saving. On sample models using reverse computation, we observe as much as a six-fold improvement in execution speed over traditional state-saving.Keywords
This publication has 15 references indexed in Scilit:
- Reverse execution of programsACM SIGPLAN Notices, 1999
- Formal verification and empirical analysis of rollback relaxationJournal of Systems Architecture, 1998
- Mersenne twisterACM Transactions on Modeling and Computer Simulation, 1998
- Algorithm 755: ADOL-CACM Transactions on Mathematical Software, 1996
- A case study in simulating PCS networks using Time WarpACM SIGSIM Simulation Digest, 1995
- History cacheACM SIGARCH Computer Architecture News, 1994
- Program inversion: More than fun!Science of Computer Programming, 1990
- Communications of the ACM, 1990
- A formal approach to undo operations in programming languagesACM Transactions on Programming Languages and Systems, 1986
- The thermodynamics of computation—a reviewInternational Journal of Theoretical Physics, 1982