Abstract
The Time-Warp machine, has emerged as the most effective parallel execution environment for discrete event simulation applications where parallelism or sequentiality of programmed interactions cannot be determined at program design stage. In this paper a new and more efficient implementation of the machine, the Tentative Time Warp algorithm, is introduced. In this implementation the number of cancellation messages are reduced; the need for searching the event list prior to propagation of rollbacks is eliminated (in primary rollbacks) or minimised(in secondary rollbacks); a more balanced and effi cient event ordering structure, with O(1) event cancellation characteristic, is introduced and tentative cancellation, as opposed to eager or lazy cancellation, is supported. Detailed design of the data structures and empirical measurement of event ordering and cancellation costs, compared to the classic Time-Warp implementation, are presented
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Berry, O. Performance evaluation of the Time Warp distributed simulation mechanism Ph.D. thesis, University of Southern California, May 1986.
Chandy, K. M. and Misra, J. Asynchronous distributed simulation via a sequence of parallel computations. Commun. ACM 24, 11 (November 1981) 198–205
Fujimoto, R. M. Performance measurement of distributed simulation strategies. Transactions of Society for Computer Simulation. 6, 2 (April 1989), 89–132.
Fujimoto, R.M. Performance of Time Warp under synthetic workloads. In Proceedings of the SCS Multiconference on Distributed Simulation 22, 1 (January 1990), pp. 23–28.
Gafni, A. Rollback mechanisms for optimistic distributed simulation systems. In Proceedings as of the SCS Multiconference on Distributed Simulation 19, 3 (July 1988), pp. 61–67.
INMOS Ltd. The T9000 TranSputer. INMOS databook series, Bristol, 1991, pp 35–43.
Jefferson, D. Virtual time. ACM Trans. Prog. Lang. and Syst. 7, 3 (July 1985), 404–425.
Jones, D. W. An empirical comparison of priority queue and event-set implementations. Commun. ACM 29, 4 (April 1986), 300–311.
Ming X-Q. Parallel discrete event simulation: its protocol development and application, PhD. thesis, University of Exeter, UK, April 1991.
Ronngren, R Ayani, R Fujimoto, R M and Das, S. R Efficient implementation of event sets in Time Warp. In Proceedings of 7th Workshop on Parallel and distributed simulation PADS93, (May 1993).
West, D. Optimising Time Warp: lazy rollback and lazy re-evaluation, MS. thesis, University of Calgary, January 1988. *** DIRECT SUPPORT *** A0008C42 00016
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Katantery, N. (1997). Tentative time warp. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002770
Download citation
DOI: https://doi.org/10.1007/BFb0002770
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive