Efficient Optimistic Parallel Simulations Using Reverse Computation

In optimistic parallel simulations, state-saving techniques have been traditionally 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 transparently reap the performance benets of reverse computation. For certain fine-grain models, such as queuing network models, we show that reverse computation can yield signifiant improvement in execution speed coupled with signifiant redu\ud tion in memory utilization, as \ud ompared to tradi-tional state-saving. On sample models using reverse \ud omputation, we observe as much as six-fold improvement in execution speed over traditional state-saving