Optimal Memory Management for Time Warp Parallel Simulation | Data Structures and Algorithms with Object-Oriented Design Patterns in Java (Worldwide Series in Computer Science)

Website of Bruno R. Preiss

Next : Simulating Continuous Systems with Up: Journal Articles Previous: Effects of the Checkpoint

Yi-Bing Lin and Bruno Richard Preiss. ACM Trans. on Modeling and Computer Simulation , 1(4):283-307, October 1991. (Accepted May 1992. Published September 1992.)[14].

Recently there has been a great deal of interest in performance evaluation for parallel simulation. Most work is devoted to the time complexity and assumes that the amount of memory available for parallel simulation is unlimited. This paper studies the space complexity of parallel simulation. Our goal is to design an efficient memory management protocol which guarantees that the memory consumption of parallel simulation is of the same order as sequential simulation. (Such an algorithm is referred to as optimal .) We first derive the relationships among the space complexities of sequential simulation, Chandy-Misra simulation, and Time Warp simulation. We show that Chandy-Misra may consume more storage than sequential simulation, or vice versa. Then we show that Time Warp always consumes more memory than sequential simulation. Then we describe cancelback , an optimal Time Warp memory management protocol proposed by Jefferson. Although cancelback is considered as a complete solution for the storage management problem in Time Warp, some efficiency issues in implementing this algorithm must be considered . In this paper, we propose an optimal algorithm called artificial rollback . We show that this algorithm is easy to implement and analyze. An implementation of artificial rollback is given, which is integrated with processor scheduling to avoid inefficiency that may occur in cancelback.

external Full text. $external$ BibTeX entry.