Checkpointing in a time warp synchronized parallel simulator is a necessary and potentially expensive operation. In the simple case, a time warp simulator checkpoints every χ events, for some fixed value χ. For larg...
详细信息
ISBN:
(纸本)9780818671203
Checkpointing in a time warp synchronized parallel simulator is a necessary and potentially expensive operation. In the simple case, a time warp simulator checkpoints every χ events, for some fixed value χ. For larger values of χ, the simulator requires less overhead for saving the state, but incurs an increased latency during rollback. Thus, the problem is to balance the time to save states against the time to coast forward upon rollback. Unfortunately, a static determination of a optimal value for χ is very difficult and can vary widely, even between closely related instances of a time warp simulator. Furthermore, the optimal checkpoint interval may actually vary over the lifetime of the *** address these problems, several investigators have proposed dynamically adjusting the checkpoint interval χ as the simulation progresses. This paper analyzes three previous techniques for dynamically sizing checkpoint intervals and presents a new, heuristic algorithm for this purpose. All four techniques are implemented in a common application domain (digital system simulation from VHDL descriptions) and a direct comparison between the algorithms is performed. The results show a significant difference in the performance of the implemented algorithms. However, in virtually all cases, the dynamic algorithms performed near or better than the best static value. Furthermore, the best algorithms performed as much as 12% better than the best static value.
We present, in this paper, a hybrid algorithm which makes use of Time Warp between clusters of LPs and a sequential algorithm within the cluster. Time Warp is, of course, traditionally implemented between individual L...
详细信息
ISBN:
(纸本)9780818671203
We present, in this paper, a hybrid algorithm which makes use of Time Warp between clusters of LPs and a sequential algorithm within the cluster. Time Warp is, of course, traditionally implemented between individual LPs. The algorithm was implemented in a digital logic simulator, and its performance compared to that of Time *** upon this platform we develop a family of three checkpointing algorithms, each of which occupies a different point in the spectrum of possible trade-offs between memory usage and execution time. The algorithms were implemented on several digital logic circuits and their speed, number of states saved and maximal memory consumption were compared to those of Time Warp. One of the algorithms saved between 35 and 50% of the maximal memory consumed by Time Warp (depending upon the number of processors used), while the other two decreased the maximal usage up to 30%. The latter two algorithms exhibited a speed comparable to Time Warp, while the first algorithm was 30-60% *** algorithms are also simpler to implement than optimal checkpointing algorithms.
The proceedings contain 25 papers. The topics discussed include: paralilel proximity detection and the distribution list algorithm;a unified framework for conservative and optimistic distributedsimulation;investigati...
ISBN:
(纸本)1565550277
The proceedings contain 25 papers. The topics discussed include: paralilel proximity detection and the distribution list algorithm;a unified framework for conservative and optimistic distributedsimulation;investigations in adaptive distributedsimulation;ports: a parallel, optimistic, real-time simulator;a distributed memory lapse: parallelsimulation of message-passing programs;discrete-event simulation and the event horizon;a generalized carrier-null method for conservative parallelsimulation;cooperative acceleration: robust conservative distributed discrete event simulation;and stability of event synchronization in distributed discrete event simulation.
This paper studies the space complexity of an optimistic parallelsimulation protocol called Time Warp. We evaluate four Time Warp memory management algorithms: fossil collection, message sendback. cancelback, and art...
This paper studies the space complexity of an optimistic parallelsimulation protocol called Time Warp. We evaluate four Time Warp memory management algorithms: fossil collection, message sendback. cancelback, and artificial rollback. We identify two criteria in designing Time Warp memory management algorithms. Criterion 1 tests if a memory management algorithm ensures that Time Warp simulation always stops (either completes or terminates when memory is exhausted). If an algorithm does not satisfy this criterion, then the simulation may be trapped in an infinite loop. Criterion 2 tests if a memory management algorithm is independent of processor parameters (e.g., number of processors available for the parallelsimulation, processor speed, and interprocessor communication costs). We show that if an algorithm satisfies this second criterion, then the amount of memory consumed by Time Warp simulation is bounded by the amount consumed by sequential simulation. For algorithms that do not have full control of uncommitted objects (e.g., fossil collection and message sendback), Criterion 2 is not satisfied in general. For algorithms that have full control of uncommitted objects (e.g., cancelback and artificial rollback), special treatments are necessary to satisfy Criterion 1 (i.e., to ensure that the algorithms do not cancel future objects such that global virtual time never advances).
parallel independent replicated simulation (PIRS) is an effective approach to speed up the simulation processes. In a PIRS, a single simulation run is executed by multiple computers in parallel. The statistical proper...
详细信息
ISBN:
(纸本)1565550277
parallel independent replicated simulation (PIRS) is an effective approach to speed up the simulation processes. In a PIRS, a single simulation run is executed by multiple computers in parallel. The statistical properties for a PIRS may be affected by the scheduling policies. For an unbiased PIRS scheduling policy, a reliable distributed computing environment is required. We consider an unbiased PIRS scheduling policy on a distributed platform such as a network of workstations. We observe that including more computing resources may degrade the performance of PIRS. Simple rules are proposed to select processors for PIRS.
Maya is a simulation platform for evaluating the performance of parallel programs on parallel architectures. It allows the rapid prototyping of memory protocols with varying degrees of coherence and facilitates the st...
详细信息
ISBN:
(纸本)1565550277
Maya is a simulation platform for evaluating the performance of parallel programs on parallel architectures. It allows the rapid prototyping of memory protocols with varying degrees of coherence and facilitates the study of the impact of these protocols on application programs. The design of Maya and its simulation mechanism are discussed. Performance results on architectural simulation with different memory coherence protocols are presented. parallel discrete event simulation techniques are adopted for the executiondriven simulation of parallel architectures.
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.
parallel discrete event simulation (PDES) research has led to the development of distributed order preserving protocols. Generalization of these protocols offers the prospect of parallel and yet deterministic executio...
详细信息
The carrier-null message approach to conservative distributed discrete-event simulation can significantly reduce the number of synchronization messages required to avoid deadlock. In thts paper we show that the origin...
详细信息
ISBN:
(纸本)1565550277
The carrier-null message approach to conservative distributed discrete-event simulation can significantly reduce the number of synchronization messages required to avoid deadlock. In thts paper we show that the original approach does not apply to simulations with arbitrary communication graphs and we propose a modified carrier-null approach whtch does. We present and discuss some preliminary results obtained using our approach to simulate digital logic circuits.
暂无评论