Optimal Memory Management for Time Warp Parallel Simulation

Yi-Bing Lin, Bruno R. Preiss

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

Recently there has been a great deal of interest in performance evalution of 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. 1991 First, we derive the relationships among the space complexities of sequential simulation, Chandy-Misra simulation [2], and Time Warp simulation [7]. We show that Chandy-Misra may consume more storage than sequential simulation, or vice versa. Then we show that Time Warp never consumes less memory than sequential simulation. Then we describe cancelback, an optimal Time Warp memory management protocol proposed by Jefferson. Although cancelback is considered to be complete solution for the storage management problem in Time Warp, some efficiency issues in implementing this algorithm must be considered. We propose an optimal algorithm called artifical 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 adjust the memory consumption rate based on the amount of free storage available in the system.

Original languageEnglish
Pages (from-to)283-307
Number of pages25
JournalACM Transactions on Modeling and Computer Simulation (TOMACS)
Volume1
Issue number4
DOIs
StatePublished - 10 Jan 1991

Keywords

  • Time Warp
  • artificial rollback
  • discrete event simulation
  • parallel simulation

Fingerprint

Dive into the research topics of 'Optimal Memory Management for Time Warp Parallel Simulation'. Together they form a unique fingerprint.

Cite this