NPSI Adaptive Synchronization Algorithms for Parallel Discrete Event Simulation

Synchronization of parallel discrete-event simulations (PDES) is a difficult problem. Despite a decade and a half of research with several successes, a synchronization algorithm that consistently performs well over a wide range of applications eludes the community. This is due primarily to the fact that the synchronization requirements of simulations are generally irregular, dynamic and unpredictable. The thesis developed here is that an adaptive approach based on the use of near-perfect state information (NPSI) offers significant potential to be consistently efficient.
We present two contributions of our investigations into optimality of adaptive protocols: a correct sufficient condition for a protocol to be super-critical, and proof that independence among events is not necessary for super-critical speed, an observation that has significance in lower bound theory of PDES.
We establish the foundation for a new class of synchronization algorithms called NPSI adaptive synchronization algorithms (protocols). These are characterized by the use of near-perfect state information to adaptively control the optimism of processes in a PDES. We propose a design framework for NPSI protocols and describe the Elastic Time Algorithm (ETA) based on this framework. An extensive performance study shows that ETA consistently outperforms Time Warp — the protocol favored by many researchers — over a wide range of workloads. The success of ETA substantiates our thesis and is a significant contribution of our work to PDES research.
In the first analytical result concerning adaptive protocols, we identify a general class of adaptive protocols (the AAWP’s) and show that Time Warp and AAWP’s can arbitrarily outperform each other. This result is significant as it demonstrates a theoretical limitation of AAWP’s and suggests that adaptive protocols must be designed with care.