Name
Title | ||
|---|---|---|
Analytical Performance Modeling for Null Message-Based Parallel Discrete Event Simulation |
Abstract | ||
|---|---|---|
This paper presents a new analytical performance analysis for null message-based parallel discrete event simulation(PDES). Our analysis builds upon the key operation of selecting simulation events for processing in the null message algorithms. The results not only explain the well-known facts of how the look ahead capability of individual simulation processes (called logical processes, or LPs) affect the simulation performance, but also reveals quantitatively how the look ahead, the communication topology, the computation and communication delays, and the flow control mechanism affect the simulation performance. We first show that all of the LPsin a strongly connected component in the communication topology asymptotically progress at the same speed, regardless of their individual characteristics and their share of computation resource. Second, we derive an analytical upper bound on the simulation performance. The derivation shows that the ratio between the sum of the look ahead and the sum of the event processing and communication delays of LPs in a cycle bounds the simulation speed from the above, and the cycle of LPs imposes the tightest upper bound becomes the bottleneck of the simulation. We conduct a series of simulation experiments to empirically validate our findings. Moreover, we show that by using the derived upper bound as an optimization guidance, we improve the partitioning of a simple parallel simulation example and achieve a four times speedup against the same simulation based on a classic min-cut partitioning strategy. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/MASCOTS.2011.60 | MASCOTS |
Keywords | Field | DocType |
communication topology asymptotically progress,communication topology,simulation event,new analytical performance analysis,simulation experiment,simple parallel simulation example,individual simulation process,communication delay,parallel discrete event simulation,simulation speed,simulation performance,analytical performance modeling,parallel processing,synchronization,algorithm design,algorithm design and analysis,message passing,upper bound,computational modeling,strongly connected component,computer model,discrete event simulation,flow control | Upper and lower bounds,Computer science,Complex event processing,Look-ahead,Real-time computing,Simulation language,Strongly connected component,Message passing,Discrete event simulation,Speedup,Distributed computing | Conference |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cheng-Hong Li | 1 | 79 | 5.98 |
| Alfred J. Park | 2 | 35 | 4.53 |
| Eugen Schenfeld | 3 | 296 | 38.01 |