Reduction Operations in Parallel Discrete Event Simulations

Building on Reynolds's hardware/software framework for parallel discrete event simulation (PDES), we establish a number of novel and best known results based on the use of reduction-based computing to support PDES. We demonstrate the utility of reduction-based computing to a spectrum of wellknown PDES synchronization protocols, such as conservative techniques and Time Warp. We enhance the hardware portion of this framework at three levels: 1) we define a virtual computation model, 2) we develop a functional design, and 3) we present a detailed implementation of this design. Each of the preceding steps is based on correctness criteria we establish here. We develop novel algorithms for performing reduction-based message acknowledgments. We prove the correctness of one of them, a single phase acknowledgment algorithm that takes advantage of the existence of global virtual time. Finally, we introduce target-specific reductions, a very promising strategy for disseminating near-perfect state..