|
 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.
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
|
|
| |
2
|
BELLENOT, S. 1992. State skipping performance with the time warp operating system. In Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS '92), 53-64.
|
| |
3
|
BENNETT, C. 1982. Thermodynamics of computation. Int. J. Phys. 21,905-940.
|
| |
4
|
|
 |
5
|
|
| |
6
|
|
| |
7
|
Christopher D. Carothers , Kalyan S. Perumalla , Richard M. Fujimoto, The effect of state-saving in optimistic simulation on a cache-coherent non-uniform memory access architecture, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.1624-1633, December 05-08, 1999, Phoenix, Arizona, United States
[doi> 10.1145/324898.325340]
|
| |
8
|
|
| |
9
|
Samir Das , Richard Fujimoto , Kiran Panesar , Don Allison , Maria Hybinette, GTW: a time warp system for shared memory multiprocessors, Proceedings of the 26th conference on Winter simulation, p.1332-1339, December 11-14, 1994, Orlando, Florida, United States
|
| |
10
|
EPPSTEIN, D. 1985. A heuristic approach to program inversion. In Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI '85), Morgan Kaufmann, San Mateo, CA, 219-221.
|
| |
11
|
FRANK, M. 1999. The R programming language and compiler, http://www.ai.mit.eduFmpf/ rc/home.html
|
| |
12
|
FUJIMOTO, R. M. 1989. Time warp on a shared memory multiprocessor. In Proceedings of the International Conference on Parallel Processing (ICPP '89, Aug.), Pennsylvania State University, University Park, PA, 242-249.
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
GRIMM, J., POTTIER, L., AND ROSTIANG-SCHMIDT, N. 1996. Optimal time and minimum space-time product for reversing a certain class of programs. Res. Rep.. INRIA, Rennes, France.
|
| |
17
|
|
| |
18
|
|
| |
19
|
|
| |
20
|
PERUMALLA, K. S., COOPER, C. A., AND FUJIMOTO, R. M. 1996. An efficiency prediction method for ATM multiplexers. In Proceedings of the International IFIP-IEEE Conference on Broadband Communications, IEEE Press, Piscataway, NJ, 477-488.
|
| |
21
|
PERUMALLA, K. S. AND FUJIMOTO, R. M. 1999. Source code transformations for efficient reversibility. Tech. Rep. GIT-CC-99-21. College of Computing, Georgia Institute of Technology, Atlanta, GA.
|
| |
22
|
PRESS, B. AND MACINTYRE, I. 1992. On the trade-off between time and space in optimistic parallel discrete event simulation. In Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS '92), 33-42.
|
| |
23
|
|
| |
24
|
MIT. 1999. The reversible computing home page at MIT. Massachusetts Institute of Technology, Cambridge, MA. http://www.ai.mit.eduFcvieri/reversible.html
|
| |
25
|
|
| |
26
|
|
| |
27
|
|
| |
28
|
VANDEN EYNDEN, C. 1987. Elementary Number Theory. Random House Inc., New York, NY.
|
| |
29
|
Z. Xiao , B. Unger , R. Simmonds , J. Cleary, Scheduling critical channels in conservative parallel discrete event simulation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.20-28, May 01-04, 1999, Atlanta, Georgia, United States
|
CITED BY 27
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
David Bauer , Garrett Yaun , Christopher D. Carothers , Murat Yuksel , Shivkumar Kalyanaraman, Simulation of large scale networks III: ROSS.Net: optimistic parallel simulation framework for large-scale internet models, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
|
|
|
Yarong Tang , Kalyan S. Perumalla , Richard M. Fujimoto , Homa Karimabadi , Jonathan Driscoll , Yuri Omelchenko, Optimistic Simulations of Physical Systems Using Reverse Computation, Simulation, v.82 n.1, p.61-73, January 2006
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yarong Tang , Kalyan S. Perumalla , Richard M. Fujimoto , Homa Karimabadi , Jonathan Driscoll , Yuri Omelchenko, Optimistic Parallel Discrete Event Simulations of Physical Systems Using Reverse Computation, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.26-35, June 01-03, 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
REVIEW
"Osman Balci : Reviewer"
Parallel simulation models generally take one of two approaches:
optimistic or conservative. The optimistic approach allows the model to
reach an unacceptable state, then rolls back to an acceptable state
after realizing that it has reached an
more...
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
I.6