Browsing by Author "Sanjeevan, Vasant"

Now showing 1 - 3 of 3
  • Thumbnail Image
    The Cost of Terminating Optimistic Parallel Discrete-Event Simulations
    Sanjeevan, Vasant; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
    In a previous paper, we proposed seven algorithms for mechanically adding an arbitrary termination condition to a conservative-synchronous, non-terminating parallel simulation. Informal arguments about the performance of each algorithm were made, and the arguments were confirmed through measurement for four of these algorithms. The benchmark used was the simulation of a Torus network using the Bounded Lag protocol on a shared memory multiprocessor. In this paper, we report on the performance of the simulation of the same Torus network benchmark with the same four termination conditions using an optimistic protocol on a message-passing multiprocessor. We also report on the performance of a colliding pucks simulation with three additional termination conditions.
  • Thumbnail Image
    The cost of terminating parallel discrete-event simulations
    Sanjeevan, Vasant (Virginia Tech, 1992)
    Simulation models use many different rules to decide when to terminate. Parallel simulations generally use a single, simple rule: each process comprising the simulation terminates after a predefined period of time. A number of parallel simulation protocols have been proposed that enforce constraints on the order in which processes are scheduled in parallel so that the result of a parallel simulation is the same as that of the corresponding sequential simulation. Parallel simulations protocols can be broadly classified into two categories: conservative and optimistic. Conservative protocols can be subclassified into synchronous and asynchronous protocols. In this thesis, our objective is to compare the predicted and measured wall clock running times of parallel simulations for conservative-synchronous and optimistic protocols with and without termination conditions. We propose eight algorithms for mechanically adding an arbitrary termination condition to a conservative-synchronous non-terminating parallel simulation. Informal arguments about the expected performance of each algorithm are made, and the arguments are confirmed through measurement of the simulation of a torus network with three termination conditions using the conservative-synchronous Bounded Lag protocol on a shared memory multiprocessor. We also propose four algorithms for mechanically adding a termination condition to an optimistic non-terminating parallel simulation. We make informal arguments about the expected performance of these algorithms and report on the actual performance of the simulation of the torus network benchmark with two of these algorithms and the same three termination conditions using the optimistic Time Warp protocol on a message-passing multiprocessor. In addition to the torus network benchmark for the optimistic protocol, we also report on the performance of a colliding pucks simulation with these two algorithms and three additional termination conditions. Our study indicates that termination conditions which require exhaustive evaluation introduce substantial running time overhead. We propose and evaluate a scheme to reduce this overhead.
  • Thumbnail Image
    Termination and Output Measure Generation in Optimistic and Conservative-Synchronous Parallel Simulations
    Abrams, Marc; Sanjeevan, Vasant; Richardson, Debra S. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
    This paper proposes algorithms to stop parallel discrete event simulations using arbitrary termination conditions and to collect output measures. We show that the time complexity of termination can be higher than that of the underlying simulation; therefore termination can reduce or even preclude speed-up. We propose simulation protocol independent algorithms solving the termination and generation problems. Implementations of the algorithms for conservative-synchronous and optimistic protocols are presented. The predicted and measured increase in real time required to execute a time warp and a bounded lag simulation equipped with our termination algorithms is presented. The chief conclusion is that when the time required for each evaluation of the termination condition exceeds the mean time to execute an event, termination can dominate the simulation running time.