Many systems rely on the ability to rollback (or restore) parts of the system state to undo or recover from undesired or erroneous computations. Examples of such systems include fault tolerant systems with checkpointi...
详细信息
Many systems rely on the ability to rollback (or restore) parts of the system state to undo or recover from undesired or erroneous computations. Examples of such systems include fault tolerant systems with checkpointing, editors with undo capabilities, transaction and data base systems and optimistically synchronized parallel and distributedsimulations. An essential part of such systems is the state saving mechanism. It should not only allow efficient state saving, but also support efficient state restoration in case of roll back. Furthermore, it is often a requirement that this mechanism is transparent to the user. In this paper we present a method to implement a transparent incremental state saving mechanism in an optimistically synchronized parallel discrete event simulation system based on the Time Warp mechanism. The usefulness of this approach is demonstrated by simulations of large, detailed, realistic FCA and a DCA-like cellular phone systems.
Lookback is defined as the ability of a logical process to change its past locally (without involving other logical processes). Logical processes with lookback are able to process out-of-timestamp order events, enabli...
ISBN:
(纸本)0769516084
Lookback is defined as the ability of a logical process to change its past locally (without involving other logical processes). Logical processes with lookback are able to process out-of-timestamp order events, enabling new synchronization protocols for the parallel discrete event simulation. Two of such protocols, LB-GVT (LookBack-Global Virtual Time) and LB-EIT (LookBack-Earliest Input Time), are presented and their performance on the Closed Queuing Network (CQN) simulation is discussed. We also discuss in detail the relation between lookahead and lookback. Finally, we demonstrate that lookback allows conservative simulations to circumvent the speedup limit imposed by the critical path.
This paper reports on the performance of four parallel algorithms for simulating an associative cache operating under the LRU (Least-Recently-Used) replacement policy. Three of the algorithms are implemented on the Ma...
详细信息
This paper reports on the performance of four parallel algorithms for simulating an associative cache operating under the LRU (Least-Recently-Used) replacement policy. Three of the algorithms are implemented on the MasPar MP-2. Another algorithm is a parallelization of an efficient serial algorithm on the Intel Paragon. We assess the strengths and weaknesses of these algorithms as a function of problem size and characteristics, and compare their performance on traces derived from execution of three SPEC92 benchmark programs.
The Generic Runtime Infrastructure for distributedsimulation (GRIDS) has been developed to investigate modularity issues in distributedsimulation. It could be argued that although the HLA RTI is a widespread solutio...
详细信息
ISBN:
(纸本)0769518532
The Generic Runtime Infrastructure for distributedsimulation (GRIDS) has been developed to investigate modularity issues in distributedsimulation. It could be argued that although the HLA RTI is a widespread solution to distributedsimulation, it cannot include all possible services. This paper investigates an approach to extending the distributedsimulation services available in the HLA RTI. One example of this is bridging support for HLA/DIS legacy integration. This paper therefore presents GRIDS, how GRIDS can be used to provide modular service support for the HLA RTI, and a case study on legacy integration to demonstrate our approach.
Circuit simulation is a critical bottleneck in VLSI design. This paper describes the implementation of an existing parallel switch-level simulator called MIR-SIM on a shared-memory multiprocessor architecture. The sim...
详细信息
Circuit simulation is a critical bottleneck in VLSI design. This paper describes the implementation of an existing parallel switch-level simulator called MIR-SIM on a shared-memory multiprocessor architecture. The simulator uses a set of three different conservative protocols: the null message protocol, the conditional eyelet protocol and the accelerated null message protocol, a combinations of the preceding two algorithms. The paper describes the implementation of these protocols to exploit shared-memory features, measures their relative performance for a set of six benchmark circuits ranging in size from 3000 to almost 70,000 transistors, and compares the speedup obtained by each of the three protocols.
A distributed algorithm is introduced for the analysis of large continuous time Markov chains (CTMCs) by combining in some sense numerical solution techniques and simulation. CTMCs are described as a set of processes ...
详细信息
A distributed algorithm is introduced for the analysis of large continuous time Markov chains (CTMCs) by combining in some sense numerical solution techniques and simulation. CTMCs are described as a set of processes communicating via message passing. The state of a process is described by a probability distribution over a set of reachable states rather than by a single state. simulation is used to determine event times and messages types to be exchanged, whereas transitions are realized by vector matrix products as in iterative numerical analysis techniques. In this way, the state space explosion of numerical analysis is avoided, but it is still possible to determine more detailed results than with simulation. parallelization of the algorithm is realized applying a conservative synchronization scheme, which exploits the possibility of precomputing event times as already proposed for parallelsimulation of CTMCs. In contrast to a pure simulation approach, the amount of computation is increased, whereas the amount of communication keeps constant. Hence it is possible to achieve even on a workstation cluster a significant speedup.
The efficiency of parallel Discrete Event simulations that use the optimistic protocol is strongly dependent on the overhead incurred by rollbacks. This paper introduces a novel approach to rollback processing which l...
详细信息
The efficiency of parallel Discrete Event simulations that use the optimistic protocol is strongly dependent on the overhead incurred by rollbacks. This paper introduces a novel approach to rollback processing which limits the number of events rolled back as a result of a straggler or antimessage. The method, called Breadth-First Rollback (BFR), is suitable for spatially explicit problems where the space is discretized and distributed among processes and simulation objects move freely in the space. BFR uses incremental state saving, allowing the recovery of causal relationships between events during rollback. These relationships are then used to determine which events need to be rolled back. Our results demonstrate an almost linear speedup - a dramatic improvement over the traditional approach to rollback processing.
A simulation-oriented language can significantly enhance the usability of parallel Discrete Event simulation (PDES) by hiding the complexities of the synchronization protocol used to ensure that events are processed i...
详细信息
A simulation-oriented language can significantly enhance the usability of parallel Discrete Event simulation (PDES) by hiding the complexities of the synchronization protocol used to ensure that events are processed in the correct order. The higher-level interface presented to the user by such a language also allows optimizations to be performed that are difficult and cumbersome with current parallel simulators, such as granularity control. APOSTLE is a new high-level simulation-oriented language for PDES, and in this paper we report that the APOSTLE granularity control mechanism reduced simulation run-times by as much as 80%. We also report that APOSTLE achieved a parallel speed-up of around 9 on 16 processors relative to its optimized sequential implementation and a parallel speed-up of around 6 on 16 processors relative to MODSIM II. Overall, we believe that the widespread success of PDES can only be achieved using a simulation-oriented language, and that APOSTLE has made a significant contribution towards this goal.
A new adaptive protocol for distributed discrete event simulation is proposed. This protocol spans the continuum of protocols from conservative to optimistic allowing each process in a distributedsimulation to adapt ...
详细信息
ISBN:
(纸本)1565550277
A new adaptive protocol for distributed discrete event simulation is proposed. This protocol spans the continuum of protocols from conservative to optimistic allowing each process in a distributedsimulation to adapt to the specific simulation problem at runtime. An actual implementation of the protocol has been tested on a network of workstations for a closed queueing system. The results are very favorable and the algorithm has outperformed a conservative and an optimistic protocol in some cases.
暂无评论