Distributed Discrete-Event Simulation Using Variants of the Chandy-Misra Algorithm on the Intel Hypercube
Abstract
The goal of distributed simulation is to speed up simulation by distributing a simulation model's execution over multiple processors. This thesis reviews existing methods for distributed simulation, the distributed event list algorithm, based on the Chandy-Misra algorithm, with an event list, similar to that used in sequential simulation, at each logical process. Null messages are used for deadlock avoidance. The algorithm is described, and is shown to require a bounded amount of memory at each logical process. A performance analysis of the distributed event list algorithm is performed. In the analytical portion, a linear event list implementation is shown to be of super-linear time complexity in relation to events simulated. This time complexity implies theoretical speed-up of greater than N for a simulation distributed over N processors. This result contradicts a commonly-held view of the existence of a bound of N on attainable speed-up. Alternate strategies for sending the Null messages used for deadlock avoidance are compared. Results show that for tandem and feed-forward topologies, a certain level of Null messages are beneficial to speed-up. The problem of assigning a given simulation model to a set of logical processes is addressed. It is seen that topology of the logical system plays a critical role in the effectiveness of assignment strategy.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1988
- Accession Number
- ADA202849
Entities
People
- David L. Mannix
Organizations
- Air Force Institute of Technology