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.
In this paper we consider the distributedsimulation of queueing networks of FCFS servers with infinite buffers, and irreducible Markovian routing. We first show that for either the conservative or optimistic synchron...
详细信息
In this paper we consider the distributedsimulation of queueing networks of FCFS servers with infinite buffers, and irreducible Markovian routing. We first show that for either the conservative or optimistic synchronization protocols the simulation of such networks can prematurely block owing to event buffer exhaustion. Buffer exhaustion can occur in the simulator whether or not the simulator is stable, and, unlike simulators of feedforward networks, cannot be prevented by interprocessor flow control alone. We propose a simple technique (which we call compactfication), which, when used in conjunction with interprocessor flow control, prevents buffer exhaustion. This leads to a general algorithm, for both conservative and optimistic synchronization, that allows one to simulate the queueing network within the finite amount of memory available at each processor. For each algorithm presented we also provide the proof that it cannot get deadlocked owing to buffer exhaustion.
The proceedings contain 24 papers. The topics discussed include: realising parallel and distributedsimulation in industry: a roadmap;distribution of random streams in stochastic models in the age of multi-core and ma...
ISBN:
(纸本)9781457713668
The proceedings contain 24 papers. The topics discussed include: realising parallel and distributedsimulation in industry: a roadmap;distribution of random streams in stochastic models in the age of multi-core and manycore processors;parallel discrete event N-body dynamics;modeling billion-node torus networks using massively parallel discrete-event simulation;empirical study on entity interaction graph of large-scale parallelsimulations;collaborative interest management for peer-to-peer networked virtual environment;dead reckoning-based update scheduling against message loss for improving consistency in DVEs;trading computation time for synchronization time in spatial distributedsimulation;framework for simulation of hybrid systems: interoperation of discrete event and continuous simulators using HLA/RTI;an analysis of the cost of validating semantic composability;and fairness verification of BOM-based composed models using petri nets.
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...
详细信息
This paper introduces a Coloured Petri Nets formalism -TCPN- which is suitable for modelling and simulation of complex systems. Novel in TCPN is (i) a timing model which accommodates both unordered and ordered (queue)...
详细信息
ISBN:
(纸本)0769518532
This paper introduces a Coloured Petri Nets formalism -TCPN- which is suitable for modelling and simulation of complex systems. Novel in TCPN is (i) a timing model which accommodates both unordered and ordered (queue) places;(ii) the adoption of Java as the net inscription language. TCPN is supported by a graphical tool RAINBOW - which allows model design, testing and simulation. A large TCPN model can be split into regions (subnets) whose execution is assigned to different LP/processors of a networked simulator. distributedsimulation relies on TUTW an agent-based Time Warp algorithm capable of exploiting temporal uncertainty for improving simulation performance. The paper describes TCPN and its distributed execution kernel. The practical use of TCPN is demonstrated through an example and some experimental results.
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...
详细信息
A real-time fault-tolerant multicast protocol is necessary for obtaining high performance in operating distributed real-time computing systems. The purpose of this paper is to show the efficiency of RFRM (Release-time...
详细信息
ISBN:
(纸本)0769515762
A real-time fault-tolerant multicast protocol is necessary for obtaining high performance in operating distributed real-time computing systems. The purpose of this paper is to show the efficiency of RFRM (Release-time based Fault-tolerant Real-time Multicast) protocol which is based on the idea of attaching the official release time to each multicast message. As a part of this, a real-time simulation based on the TMO structuring scheme is conducted to evaluate the proposed approach. We experiment a real-time multicast model which does not receive ack-messages toward reducing the message traffic on the network by employing fault detection mechanism. simulation results promised the efficiency of the proposed real-time multicast protocol.
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.
Presented is a dynamic load balancing algorithm developed for Clustered Time Warp, a hybrid approach which makes use of Time Warp between clusters of LPs and a sequential mechanism within the clusters. The load balanc...
详细信息
Presented is a dynamic load balancing algorithm developed for Clustered Time Warp, a hybrid approach which makes use of Time Warp between clusters of LPs and a sequential mechanism within the clusters. The load balancing algorithm focuses on distributing the load of the simulation evenly among the processors and then tries to reduce interprocessor communications. A triggering technique is used that is based on the throughput of the simulation system. The algorithm was implemented and its performance was measured using two of the largest benchmark digital circuits of the ISCAS '89 series. Results show that by dynamically balancing the load, the throughput was improved by 40-100% when compared to Time Warp.
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 an...
详细信息
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 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 that the best static value. Moreover, the best algorithms performed as much as 12% better the best static value.
暂无评论