We investigated the benefit of exploiting the symmetries of graphs for partitioning. We represent the model to be simulated by a weighted graph. Graph symmetries are studied in the theory of permutation groups and can...
详细信息
ISBN:
(纸本)0769521118
We investigated the benefit of exploiting the symmetries of graphs for partitioning. We represent the model to be simulated by a weighted graph. Graph symmetries are studied in the theory of permutation groups and can be calculated in polynomial time with the nauty algorithm [15]. We designed an algorithm to extract useful symmetries from the automorphism group, which can be used to create partitions derived from the graph's structure. Our approach is focused on composite graphs, for which identical subgraphs reoccur in the graph. If these identical subgraphs can be mapped onto each other by symmetries, the subgraphs are replaced by equivalent multivertices, resulting in a 'natural' aggregation of vertices. This approach is applied to parallelsimulation of a detailed IP-switch with a conservative synchronous algorithm. The experimental results show that even for good partitions, global and temporal load imbalances are inevitable.
In distributed wargame simulations, the states of simulation entities need to be updated and sent to other simulation nodes in a timely manner, which may incur high overhead on the network. Thus, how to efficiently us...
详细信息
ISBN:
(纸本)0769521118
In distributed wargame simulations, the states of simulation entities need to be updated and sent to other simulation nodes in a timely manner, which may incur high overhead on the network. Thus, how to efficiently use the limited bandwidth of the network is very important to the performance of distributed wargame simulations. In this paper, a utility model is proposed to evaluate the relative importance of a simulation entity. In our proposed utility model, the utility of an entity is determined by the number of entities on which this entity may have influence and the distances between this entity and the entities within its area of influence. Based on the utility model, we may devise some flexible updating mechanisms which can utilize the band-width more efficiently. For example, the state updates of an important entity which may have great influence on the simulation could be sent to other nodes with a high frequency;on the other hand, the state updates of an entity with little importance may be sent to other simulation nodes with a low frequency. In this paper, we will focus on the utility computation of a simulation entity rather than the flexible state updating mechanisms for the simulation entities. Our proposed utility computation mechanism is general and can be easily implemented using the HLA services. Experimental results show that the utility computation mechanism incurs little overhead.
In this work we focus on a new technique for making cloning of parallelsimulations more efficient. Cloning provides a means for running multiple similar simulations in parallel where many computations are shared rath...
详细信息
ISBN:
(纸本)0769521118
In this work we focus on a new technique for making cloning of parallelsimulations more efficient. Cloning provides a means for running multiple similar simulations in parallel where many computations are shared rather than repeated [12]. A simulation is cloned on an event for a particular set of logical processes, creating new LP clones. The clones diverge as messages from the new LPs arrive at uncloned LPs. Until replication, all the computations for a particular LP are shared between the clones. simulation kernels using cloning achieve efficiency by incrementally replicating logical processes as necessary. This enables regions of the simulation that have not been affected to use the same computations for both the new and old clone. Clearly, the longer replication can be delayed, the more efficient the simulation. We hypothesize that in many cases replication takes place before it is strictly necessary. We propose just-in-time cloning that addresses this issue by relaxing the constraints of simulation cloning to further benefit from shared computations.
We study the adaptation of an optimistic Time Warp kernel to cross-cluster computing on the Grid. Wide area communication, the primary source of overhead, is off-loaded onto dedicated routing processes. This allows th...
详细信息
ISBN:
(纸本)0769521118
We study the adaptation of an optimistic Time Warp kernel to cross-cluster computing on the Grid. Wide area communication, the primary source of overhead, is off-loaded onto dedicated routing processes. This allows the simulation processes to run at full speed and it thus significantly decreases the performance gap caused by the wide area distribution. Further improvements are obtained by employing message aggregation on the wide area links. We achieve many of our objectives for lazy cancellation and moderate communication, but high communication rates with aggressive cancellation remains a challenge.
Conservative parallel discrete event simulation takes a connection-oriented approach to inter-process communication. Conservative processes modeling physical entities are connected via channels that represent physical...
详细信息
ISBN:
(纸本)0769521118
Conservative parallel discrete event simulation takes a connection-oriented approach to inter-process communication. Conservative processes modeling physical entities are connected via channels that represent physical links in the target system. By contrast, optimistic strategy and its implementation in Time Warp machine, take a connectionless approach where a process can communicate freely with any other process without prior connection. This paper presents the case for a connection-oriented optimistic approach and provides a data structure for the event set of Time Warp processes that significantly reduces the cost of event scheduling and cancellation under connection-oriented operation. Detailed description of the proposed implementation is given and performance of the structure in forward event scheduling and backward event cancellation is tested and the results are discussed.
An important question for network simulation is what level of detail is required to obtain a desired level of accuracy. While in some networks, the level of detail is an open research issue (for example, radio propaga...
详细信息
ISBN:
(纸本)0769521118
An important question for network simulation is what level of detail is required to obtain a desired level of accuracy. While in some networks, the level of detail is an open research issue (for example, radio propagation models in wireless networks), it has long been assumed that wired networks could be accurately modeled by fairly simple queues with a bandwidth limit and propagation delay. To our knowledge this assumption has not been widely tested In this paper we evaluate different levels of detail for an Ethernet simulation. We consider two models for Ethernet simulation;a detailed, CSMA/CD protocol based model and a more abstract model using a DropTail, shared queue. Using web traffic with two different TCP simulation models, we evaluated the accuracy of these Ethernet models as compared to testbed measurements. We observed the DropTail Ethernet model requires significantly less execution time and can accurately model performance using a bandwidth normalization factor.
In mobile ad hoc network (MANET) studies, it is imperative to use highly detailed device models as they provide high layer protocols with good prediction of underlying wireless communication performance. However, such...
详细信息
ISBN:
(纸本)0769521118
In mobile ad hoc network (MANET) studies, it is imperative to use highly detailed device models as they provide high layer protocols with good prediction of underlying wireless communication performance. However, such studies often utilize abstract models for execution speed and simplicity. This paper first shows that physical layer variables including path loss, shadowing, multipath, Doppler have significant effects on the predicted overall networking performance. It then proposes an approach to simulate details of wireless propagation and radio characteristics in networking studies while still maintaining a reasonable simulation execution time. Through our runtime performance studies with detailed OFDM Simulink / MATLAB models and QualNet network simulator, it is shown that the proposed approach can improve the simulation runtime performance by three to four orders of magnitudes without compromising the fidelity of simulation results.
With the wide use of Commercial Off-The-Shelf (COTS) simulation packages and the advent of the High Level Architecture (HLA) standard which supports interoperability and reusability, it is desirable to build distribut...
详细信息
ISBN:
(纸本)0769521118
With the wide use of Commercial Off-The-Shelf (COTS) simulation packages and the advent of the High Level Architecture (HLA) standard which supports interoperability and reusability, it is desirable to build distributedsimulations by linking various types of simulation models developed using best-fit COTS packages. While almost all current work on integrating COTS packages and the HLA is based on conservative synchronization, it is worthwhile to investigate the optimistic synchronization approach. The optimistic approach can exploit parallelism and achieve promising performance in situations where causality errors may occur but in fact seldom occur. In our paper, we introduce a rollback controller using a middleware approach to handle the complex rollback procedure on behalf of the simulation model. To fully utilize the benefits of optimistic synchronization, we also introduce a novel time advance algorithm using the services provided by the HLA. A comparison of performance between the conservative and optimistic synchronization approaches based on a typical reference model is also provided.
We discuss an approach for creating a federated network simulation that eases the burdens on the simulator user that typically arise from more traditional methods for defining space-parallelsimulations. Previous appr...
详细信息
ISBN:
(纸本)0769521118
We discuss an approach for creating a federated network simulation that eases the burdens on the simulator user that typically arise from more traditional methods for defining space-parallelsimulations. Previous approaches have difficulties that arise from the need for global topology knowledge when forwarding simulated packets between the federates. In all but the simplest cases, proper packet forwarding decisions between federates requires routing tables of size 0(mn) (m is the number of nodes modeled in a particular simulator instance, and n is the total number of network nodes in the entire topology) in order to determine how packets should be routed between federates. Further, the benefits of the well-known NIx-Vector routing approach cannot be fully achieved without global knowledge of the overall topology. We seek to overcome these difficulties by utilizing a topology partitioning methodology that uses Ghost Nodes. A ghost node is a simulator object in a federate that represents a simulated network node that is spatially assigned to some other federate, and thus that other federate is responsible for maintaining all state associated with the node. However, ghost nodes do retain topology connectivity information with other nodes, allowing all federate in a space-parallelsimulation to obtain a global picture of the network topology. We show with experimental results that the memory overhead associated wit the ghosts is minimal relative to the overall memory footprint of the simulation.
Real-time simulation is a familiar technique for testing hardware and software in the loop and for operator training. An important parameter of these simulations is the frame-time necessary to capture the dynamics of ...
详细信息
ISBN:
(纸本)0769521118
Real-time simulation is a familiar technique for testing hardware and software in the loop and for operator training. An important parameter of these simulations is the frame-time necessary to capture the dynamics of the system being simulated. Modern power electronic systems, using higher frequency pulse-width modulation (PWM) converter control demand frame times that are significantly shorter than those found in most real-time simulators. The paper describes an approach to real-time simulation that is capable of achieving the frame times of 10muS and less required for this application. It is a scalable technique that uses arrays of digital signal processors on commercially available boards plugged into a conventional desktop computer. Analog and digital interfaces provide for the connection of real hardware to the simulation. Although the technique has so far been applied only to power electronic systems, it is capable of being used in a wide range of applications in which frame times of less than 10muS are required.
暂无评论