Christopher D. Carothers
Kalyan S. Perumalla
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.
- BAKER, H. G. 1992. NReversal of fortune--The thermodynamics of garbage collection. In Proceedings of the International Workshop on Memory Management (St. Malo, France, Sept. 1992), Lecture Notes in Computer Science, vol. 637. Springer-Verlag, New York, 507-524. Google Scholar
- 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.Google Scholar
- BENNETT, C. 1982. Thermodynamics of computation. Int. J. Phys. 21,905-940.Google Scholar
- BISHOP, P. 1997. Using reversible computing to achieve fail-safety. In Proceedings of the 8th International Symposium on Software Reliability Engineering (ISSRE 97), 182-191. Google Scholar
- BISWAS, B. AND MALL, R. 1999. Reverse execution of programs. SIGPLAN Not. 34, 4 (Apr.), 61-69. Google Scholar
- CAROTHERS, C. D., FUJIMOTO, R. M., AND LIN, Y.-B. 1995. A case study in simulating PCS networks using Time Warp. SIGSIM Simul. Dig. 25, 1 (July 1995), 87-94. Google Scholar
- CAROTHERS, C. D., PERUMALLA, K. S., AND FUJIMOTO, R. M. 1999. The effect of state-saving in optimistic simulation on a cache-coherent non-uniform memory access architecture. In Proceedings of the 1999 Winter Conference on Simulation (WSC '99), ACM Press, New York, NY. Google Scholar
- CHEN, W. AND UDDING, J. T. 1990. Program inversion: More than fun!. Sci. Comput. Program. 15, 1 (Nov. 1990), 1-13. Google Scholar
- DAS, S., FUJIMOTO, R., PANESAR, K., ALLISON, D., AND HYBINETTE, M. 1994. GTW: A time warp system for shared memory multiprocessors. In Proceedings of the 1994 Winter Conference on Simulation (WSC'94, Lake Buena Vista, FL, Dec. 11-14, 1994), D. A. Sadowski, A. F. Seila, M. S. Manivannan, and J. D. Tew, Eds. Society for Computer Simulation, San Diego, CA, 1332-1339. Google Scholar
- 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.Google Scholar
- FRANK, M. 1999. The R programming language and compiler, http://www.ai.mit.eduFmpf/ rc/home.htmlGoogle Scholar
- 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.Google Scholar
- FUJIMOTO, R. M. 1990. Parallel discrete event simulation. Commun. ACM 33, 10 (Oct. 1990), 30 -53. Google Scholar
- GOMES, F 1996. Optimizing incremental state-saving and restoration. Ph.D. Dissertation. University of Calgary, Calgary, Canada. Google Scholar
- GRIEWANT, A., JUEDOS, D., MITEV, H., UTKE, J., VOGEL, O., AND WALTHER, A. 1996. ADOL-C: A package for the automatic differentiation of algorithms written in C/ C + +. ACM Trans. Math. Softw. 22, 2 (Feb.), 131-167. Google Scholar
- 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.Google Scholar
- LEEMAN, G. B. 1986. A formal approach to undo operations in programming languages. ACM Trans. Program. Lang. Syst. 8, 1 (Jan.), 50-87. Google Scholar
- L'ECUYER, P. AND ANDRES, T. H. 1997. A random number generator based on the combination of four LCGs. Math. Comput. Simul. 44, 1, 99-107. Google Scholar
- MATSUMOTO, M. AND NISHIMURA, T. 1998. Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8, 1, 3-30. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- POPLAWSKI, A. AND NICOL, D. M. 1998. Nops: A conservative parallel simulation engine for TeD. In Proceedings of the 12th Workshop on Parallel and Distributed Simulation (PADS '98, Banff, Alta., Canada, May 26-29, 1998), B. Unger and A. Ferscha, Eds. IEEE Computer Society Press, Los Alamitos, CA, 180-187. Google Scholar
- MIT. 1999. The reversible computing home page at MIT. Massachusetts Institute of Technology, Cambridge, MA. http://www.ai.mit.eduFcvieri/reversible.htmlGoogle Scholar
- SosIc, R. 1994. History cache: Hardware support for reverse execution. SIGARCH Comput. Arch. News 22, 5 (Dec. 1994), 11-18. Google Scholar
- STEINMAN, J. S. 1993. Incremental state saving in SPEEDES using C+ +. In Proceedings of the Winter Conference on Simulation (WSC '93, Los Angeles, CA, Dec. 12-15, 1993), G. W. Evans, M. Mollaghasemi, E. C. Russell, and W. E. Biles, Eds. ACM Press, New York, NY, 687-696. Google Scholar
- UMAMAGESWARAN, K., SUBRAMANI, K., WILSEY, P. A., AND ALEXANDER, P. 1998. Formal verification and empirical analysis of rollback relaxation. J. Syst. Archit. 44, 6&7, 473-495. Google Scholar
- VANDEN EYNDEN, C. 1987. Elementary Number Theory. Random House Inc., New York, NY.Google Scholar
- XIAO, Z., UNGER, B., SIMMONDS, R., AND CLEARY, J. 1999. Scheduling critical channels in conservative parallel discrete event simulation. In Proceedings of the 13th Workshop on Parallel and Distributed Simulation (PADS '99), IEEE Computer Society Press, Los Alamitos, CA, 20-28. Google Scholar
Index Terms
- Efficient optimistic parallel simulations using reverse computation
Recommendations
Optimistic Simulations of Physical Systems Using Reverse Computation
Efficient computer simulation of complex physical phenomena has long been challenging due to their multiphysics and multiscale nature. In contrast to traditional time-stepped execution methods, the authors describe an approach using optimistic parallel ...
Parallel Vehicular Traffic Simulation using Reverse Computation-based Optimistic Execution
PADS '08: Proceedings of the 22nd Workshop on Principles of Advanced and Distributed SimulationVehicular traffic simulations are useful in applications such as emergency management and homeland security planning tools. High speed of traffic simulations translates directly to speed of response and level of resilience in those applications. Here, a ...
Optimistic Parallel Discrete Event Simulations of Physical Systems Using Reverse Computation
PADS '05: Proceedings of the 19th Workshop on Principles of Advanced and Distributed SimulationEfficient computer simulation of complex physical phenomena has long been challenging due to their multi-physics and multi-scale nature. In contrast to traditional time-stepped execution methods, we describe an approach using optimistic parallel ...
Reviews
Osman Balci
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 unacceptable state. The rollback is commonly achieved by using a technique called state saving. The authors propose reverse computation, which performs the inverses of the individual operations that led to the unacceptable state, as a new rollback technique. Using two examples, ATM Multiplexor Cascade and PCS Network, the authors demonstrate that their new approach has insignificant forward computation overhead and low state memory requirements in fine-grain simulations; achieves better caching, resulting in two- to three-fold speedup when compared to copy state-saving, periodic state-saving, and incremental state-saving; and can be automated using compiler-based techniques. The paper is well written and self-contained. Every researcher or practitioner working on parallel simulation should read it.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments