State Saving and Rollback Costs for an Aggressive Global Windowing

Abstract

Windowing algorithms represent an important class of synchronization protocols for parallel discrete event simulation. In these algorithms, a simulation window is chosen such that all events within the window can be executed concurrently without the possibility of a causality error. Using the terminology of Chandy and Sherman (1989), these are unconditional events. Windowing algorithms, as all nonaggressive algorithms, have been criticized for not allowing a computation to proceed because there exists the possibility of a causality error. In Dickens, Reynolds and Duva (1992) we investigated the impact of extending the simulation window in order to allow the computation of conditional events, that is, those events that may cause an error. We demonstrated analytically and empirically that significant performance gains are made possible as a result of this aggressive processing. In this paper we propose a simple state saving and rollback protocol to correct errors that occur as a result of aggressive processing. We extend our analytic model to include the costs associated with aggressive processing. As we discuss, the two primary costs of aggressive processing are saving state and the possibility of cascading rollbacks. We demonstrate analytically that the probability of cascading rollbacks developing is negligible. Also we show that excellent performance gains are made possible by aggressive processing even when the costs of saving state are included in the model. Note: Abstract extracted from PDF file via OCR