Reduction Operations in Parallel Discrete Event Simulation (PhD Dissertation)

Report
Author:Pancerella, Carmen, Department of Computer ScienceUniversity of Virginia
Abstract:

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 well-known PDES synchronization protocols, such as conservative techniques and Time Warp. We enhance the hardware portion of Reynolds's 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 information in PDES's. A target-specific reduction is one where each logical process receives synchronization information (reduced values) only from those logical processes on which it is logically dependent. We demonstrate that the computation of target-specific values can have a sub-quadratic sequential time complexity. Supporting empirical results clearly demonstrate that target-specific reductions will provide significant time and space savings in PDES's.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Pancerella, Carmen. "Reduction Operations in Parallel Discrete Event Simulation (PhD Dissertation)." University of Virginia Dept. of Computer Science Tech Report (1994).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1994