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.
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.
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.
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 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.
simulation has always been a valuable tool for experimentation and validation of models, architectures and mechanisms in the, field of networking. In the case of the DiffServ framework, simulation is even more valuabl...
详细信息
ISBN:
(纸本)0769518532
simulation has always been a valuable tool for experimentation and validation of models, architectures and mechanisms in the, field of networking. In the case of the DiffServ framework, simulation is even more valuable, due to the fact that an analytical approach of mechanisms and services is infeasible because of the aggregation and multiplexing of flows. In this work, we have extended the functionality of a widely used simulation environment towards the direction of realistic traffic generation and a series of mechanisms defined by the DiffServ architecture. The modules created are being presented and a case study of a simulation scenario that exploits the functionality provided by them is described.
We present a novel approach to parallel discrete event simulation based on the Cilk model of multithreaded computation. Cilk's runtime system not only manages the low-level aspects of program execution, but also p...
详细信息
We present a novel approach to parallel discrete event simulation based on the Cilk model of multithreaded computation. Cilk's runtime system not only manages the low-level aspects of program execution, but also provides the user with an algorithmic model of performance which can be used to predict the execution time of a parallelsimulation. Moreover, a Cilk application can `scale down' to run on a single processor with nearly the same performance as that of serial code. A conservative parallel discrete event simulation algorithm has been developed in which communication between logical processes is achieved using Cilk's virtual memory model, dag consistent shared memory. The simulation executes in cycles, where each cycle involves a divide and conquer computation. Although local lookahead information can be exploited, the algorithm is robust in that it also calculates a global simulation time for each cycle. It can therefore be used for applications where zero lookahead may occur.
We present a case study in which we apply parallelsimulation methods and interoperability techniques to network simulations for simulation-based on-line control of military communication networks. The on-line simulat...
ISBN:
(纸本)0769516084
We present a case study in which we apply parallelsimulation methods and interoperability techniques to network simulations for simulation-based on-line control of military communication networks. The on-line simulations model actual military networks, including wired shipboard sub-networks connected via satellite links, and wireless mobile devices. The modeled scenario depicts the communication requirements of an amphibious landing where a complex network connects troops ashore and naval vessels. The simulations use a heterogeneous set of tools, including ns2 models for shipboard wired networks, and GloMoSim models for the wireless devices. In this paper, we document the challenges we encountered in applying parallel and interoperable simulation methods, and describe our solutions. We describe our experiences in addressing the interoperability problems that naturally arose due to the heterogeneity of scenario models. We also present a preliminary study on the scalability of real-time performance of parallel network simulations, which is crucial for on-line simulations. Salient system characteristics of the subject military network scenarios are described for the benefit of exposure to the modeling and simulation research community. Our exercise not only highlights the relevance of parallel and distributedsimulation techniques to an important real-life problem, but also demonstrates the feasibility of applying those techniques in a practical setting.
The partitioning of complex processor models on the gate and register-transfer level for parallel functional simulation based on the clock-cycle algorithm is considered. We introduce a hierarchical partitioning scheme...
详细信息
The partitioning of complex processor models on the gate and register-transfer level for parallel functional simulation based on the clock-cycle algorithm is considered. We introduce a hierarchical partitioning scheme combining various partitioning algorithms in the frame of a competing strategy. Melting together different partitioning results within one level using superpositions we crossover to a mixture of experts one. This approach is improved applying genetic algorithms. In addition we present two new partitioning algorithms both of them taking cones as fundamental units for building partitions.
ECATNets (Extended Concurrent Algebraic Term Nets) are a kind of high-level algebraic net used for specifying various aspects of distributed and parallel systems. We address the problem of developing parallel simulati...
详细信息
暂无评论