Item Details

Print View

Reduction Operations in Parallel Discrete Event Simulations

Pancerella, Carmen M
Format
Thesis/Dissertation; Online
Author
Pancerella, Carmen M
Advisor
Reynolds, Paul
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 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 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.
Published
University of Virginia, Department of Computer Science, PhD, 1994
Published Date
1994-05-31
Degree
PhD
Rights
All rights reserved (no additional license for public reuse)
Collection
Libra ETD Repository

Availability

Read Online