With parallel and Discrete Event simulation (PDES) techniques, the runtime performance of detailed wireless network simulation can be improved significantly without compromising fidelity of the simulation results. How...
详细信息
ISBN:
(纸本)0769521118
With parallel and Discrete Event simulation (PDES) techniques, the runtime performance of detailed wireless network simulation can be improved significantly without compromising fidelity of the simulation results. However modelling characteristics of wireless communications such as signal propagation and interference may severely hinder the potential speedup yielded by PDES. This paper proposes various optimization techniques to address three major concerns in achieving efficient parallel execution of wireless network simulation: i.e., (1) reducing communication and computation overhead of simulating signal propagation across multiple logical processes;(2) reducing synchronization overhead among logical processes;(3) minimizing event scheduling overhead within individual logical processes. These techniques have been implemented in a parallel version of GloMoSim and QualNet. The experimental results with mobile ad hoc networking scenarios demonstrate that the proposed optimization techniques can improve the performance of parallel wireless network simulation by up to an order of magnitude.
The parallel (and distributed) Discrete Event simulation (PADS) community - over it's more than 20 years of existence has achieved remarkable results in getting the execution of simulations of discrete event syste...
详细信息
ISBN:
(纸本)0769521118
The parallel (and distributed) Discrete Event simulation (PADS) community - over it's more than 20 years of existence has achieved remarkable results in getting the execution of simulations of discrete event systems faster, involving multiple, logically and/or physically dispersed, communicating computational resources. A solid, mature and empirically approved body of foundational concepts, models, systems, methods and algorithms are at hand and well documented in more than 50.000 pages of research papers. PADS simulation engines, model and software libraries, and operating systems have proven feasibility and applicability of these results in solving real world problems. Despite the (healthy) self-criticism of it's proponents ("Will the field survive?"), PADS was - and is - a success! With this talk we aim at a prospect for the challenges posed by the emerging new models of computational and communication, the evolving new paradigms of interaction and coordination, the new styles of system design, and even the availability of new technologies, for which - in my opinion - no other community qualifies better than the PADS community.
The notion of temporal uncertainty, expressed as the possibility for an event to occur in an interval of simulation time, rather than at a specific instant, has been recently proposed and exploited in order to enhance...
详细信息
ISBN:
(纸本)0769521118
The notion of temporal uncertainty, expressed as the possibility for an event to occur in an interval of simulation time, rather than at a specific instant, has been recently proposed and exploited in order to enhance the performance of parallel/distributedsimulation systems. In this paper we propose the concept of "spatial uncertainty" expressed as the possibility for a simulation event to occur in one of a set of points within the simulated system space. How to handle/exploit space uncertain events in an optimistic simulation system is discussed. Also, experimental results for optimistic simulations of a Personal Communication System (PCS) modeled with space uncertain events are reported These results show the ability of spatial uncertainty to increase the performance of the parallelsimulation system by providing a more flexible approach to synchronization.
In optimistic simulations, checkpointing techniques are often used to reduce the overhead caused by state saving. In this paper, we propose event reconstruction as a technique with which to reduce the overhead caused ...
详细信息
ISBN:
(纸本)0769521118
In optimistic simulations, checkpointing techniques are often used to reduce the overhead caused by state saving. In this paper, we propose event reconstruction as a technique with which to reduce the overhead caused by event saving, and compare its memory consumption and execution time to the results obtained by dynamic checkpointing. As the name implies, event reconstruction reconstructs input events and anti-events from the differences between adjacent states, and does not save input events in the event queue. For simulations with fine event granularity and small state size, such as the logic simulation of VLSI circuitry, event reconstruction can yield an improvement in execution time as well as a significant reduction in memory utilization when compared to dynamic checkpointing. Moreover, this technique facilitates load migration because only the state queue needs to be moved from one processor to another.
This paper advocates the use of a formal framework for analyzing simulation performance. simulation performance is characterized based on the three simulation development process boundaries: physical system, simulatio...
详细信息
ISBN:
(纸本)0769521118
This paper advocates the use of a formal framework for analyzing simulation performance. simulation performance is characterized based on the three simulation development process boundaries: physical system, simulation model, and simulator implementation. Firstly, we formalize simulation event ordering using partially ordered set theory. A simulator implements a simulation event ordering, and incurs implementation overheads when enforcing event ordering at runtime. Secondly, we apply our formalism to extract and formalize the simulation event orderings of both sequential and parallelsimulations. Thirdly, we propose the relation stricter and a measure called strictness for comparing and quantifying the degree of event dependency of simulation event orderings respectively.
Designing fast parallel discrete event simulation systems for shared-memory parallel computers is simplified by the efficient communication operations enabled by the common memory space. The difficulties involved in d...
详细信息
ISBN:
(纸本)0769521118
Designing fast parallel discrete event simulation systems for shared-memory parallel computers is simplified by the efficient communication operations enabled by the common memory space. The difficulties involved in designing large shared-memory computers and the resulting high cost of even modest size systems has led to the proliferation of computer systems consisting of small shared-memory computers connected via low-latency message-passing interconnection networks. This paper describes how a network simulation system using a simulation kernel optimized for high performance operation on shared-memory parallel computers has been extended to operate on computers that mix shared-memory and message-passing paradigms. Results are presented showing that the system can achieve over 60 million simulated packet transmissions per second on 32 4-processor nodes. The results demonstrate the advantage of using a mixture of shared-memory and message-passing over using only message-passing in many cases.
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.
暂无评论