Radu Calinescu
Abstract
The optimistic approach to parallel discrete event simulation (PDES) has led to a number of algorithms capable of fully exploiting the inherent parallelism of discrete event systems. On the other hand, these parallel algorithms, as well as most implementations of the Time Warp mechanism were designed to suit a specific parallel architecture, therefore suffering from lack of portability. This paper proposes the bulk synchronous parallel (BSP) model as a target platform for the design of portable parallel algorithms for optimistic simulation. After an overview of the main directions in PDES, the paper describes the Time Warp mechanism, presenting the most important issues related to optimistic simulation. A class of BSP algorithms for GVT computation is introduced and analysed in terms of the the BSP cost model. Then, two BSP algorithms for optimistic PDES are discussed; the first algorithm aims at avoiding recursive rollbacks in aggressive-cancellation Time Warp implementations, while the second one is a BSP variant of filtered rollback.