A use of matrix with GVT computation in optimistic time warp algorithm for parallel simulation

Shalini Potham, Syed S. Rizvi, Khaled M. Elleithy, Aasia Riasat

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

One of the most common optimistic synchronization protocols for parallel simulation is the Time Warp algorithm proposed by Jefferson [12]. Time Warp algorithm is based on the virtual time paradigm that has the potential for greater exploitation of parallelism and, perhaps more importantly, greater transparency of the synchronization mechanism to the simulation programmer. It is widely believe that the optimistic Time Warp algorithm suffers from large memory consumption due to frequent rollbacks. In order to achieve optimal memory management, Time Warp algorithm needs to periodically reclaim the memory. In order to determine which event-messages have been committed and which portion of memory can be reclaimed, the computation of global virtual time (GVT) is essential. Mattern [2] uses a distributed snapshot algorithm to approximate GVT which does not rely on first in first out (FIFO) channels. Specifically, it uses ring structure to establish cuts C1 and C2 to calculate the GVT for distinguishing between the safe and unsafe event-messages. Although, distributed snapshot algorithm provides a straightforward way for computing GVT, more efficient solutions for message acknowledging and delaying of sending event messages while awaiting control messages are desired. This paper studies the memory requirement and time complexity of GVT computation. The main objective of this paper is to implement the concept of matrix with the original Mattern's GVT algorithm to speedups the process of GVT computation while at the same time reduce the memory requirement. Our analysis shows that the use of matrix in GVT computation improves the overall performance in terms of memory saving and latency.

Original languageEnglish (US)
Title of host publicationProceedings of the 2012 Spring Simulation Multiconference, SpringSim 2012 - 15th Communications and Networking Symposium 2012, CNS 2012
Pages25-30
Number of pages6
Edition3 BOOK
StatePublished - 2012
Event15th Communications and Networking Symposium 2012, CNS 2012, Part of the 2012 Spring Simulation Multiconference, SpringSim 2012 - Orlando, FL, United States
Duration: Mar 26 2012Mar 30 2012

Publication series

NameSimulation Series
Number3 BOOK
Volume44
ISSN (Print)0735-9276

Other

Other15th Communications and Networking Symposium 2012, CNS 2012, Part of the 2012 Spring Simulation Multiconference, SpringSim 2012
Country/TerritoryUnited States
CityOrlando, FL
Period3/26/123/30/12

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'A use of matrix with GVT computation in optimistic time warp algorithm for parallel simulation'. Together they form a unique fingerprint.

Cite this