The master/worker (MW) paradigm can be used as an approach to parallel discrete event simulation (PDES) on metacomputing systems. MW PDES applications incur overheads not found in conventional PDES executions executing on tightly coupled machines. We introduce four optimization techniques in MW PDES systems on public resource and desktop grid infrastructures. Work unit caching, pipelined state updates, expedited message delivery, and adaptive work unit scheduling mechanisms in the context of MW PDES are described. These optimizations provide significant performance benefits when used in tandem. We present results showing that an optimized MW PDES system using these techniques can exhibit performance comparable to a traditional PDES system for queueing network and particle physics simulation applications while providing execution capability across metacomputing systems.

Parallel discrete event simulation (PDES) represents a class of codes that are challenging to scale to large number of processors due to tight global timestamp-ordering and fine-grained event execution. One of the critical factors in scaling PDES is the efficiency of the underlying global virtual time (GVT) algorithm needed for correctness of parallel execution and speed of progress. Although many GVT algorithms have been proposed previously, few have been proposed for scalable asynchronous execution and none customized to exploit one-sided communication. Moreover, the detailed performance effects of actual GVT algorithm implementations on large platforms are unknown. Here, three major GVT algorithms intended for scalable execution on high-performance systems are studied: (1) a synchronous GVT algorithm that affords ease of implementation, (2) an asynchronous GVT algorithm that is more complex to implement but can relieve blocking latencies, and (3) a variant of the asynchronous GVT algorithm, proposed and studied for the first time here, to exploit one-sided communication in extant supercomputing platforms. Performance results are presented of implementations of these algorithms on up to 129,024 cores of a Cray XT5 system, exercised on a range of parameters: optimistic and conservative synchronization, fine-to medium-grained event computation, synthetic and non-synthetic applications, and different lookahead values. Performance to the tune of tens of billions of events executed per second are registered, exceeding the speeds of any known PDES engine, and showing asynchronous GVT algorithms to outperform state-of-the-art synchronous GVT algorithms. Detailed PDES-specific runtime metrics are presented to further the understanding of tightly-coupled discrete event dynamics on massively parallel platforms.

Stream computing is an emerging computational model for performing complex operations on and across multi-source, high volume data flows. Given that the deployment of the model has only started, the pool of mature applications employing this model is fairly small, and therefore the availability of workloads for various types of applications is scarce. Thus, there is a need for synthetic generation of large-scale workloads for evaluation of stream computing applications at scale. This paper presents a framework for producing synthetic workloads for stream computing systems. Our framework extends known random graph generation concepts with stream computing specific features, providing researchers with realistic input stream graphs and allowing them to focus on system development, optimization and analysis. Serving the goal of covering a disparity of potential applications, the presented framework exhibits high user-controlled configurability. The produced workloads could be used to drive simulations for performance evaluation and for proof-of-concept prototyping of processing, networking and operating system hardware and software.

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 LPs in 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.

μπ (MUPI) is a parallel discrete event simulator designed for enabling software-based experimentation via simulated execution across a range of synthetic to unmodified parallel programs using the Message Passing Interface (MPI) with millions of tasks. Here, we report work in progress in improving the efficiency of μπ. Among the issues uncovered are the scaling problems with implementing barriers and intertask message ordering. Preliminary performance shows the possibility of supporting hundreds of virtual MPI ranks per real processor core. Performance improvements of at least 2x are observed, and enable execution of benchmark MPI runs with over 16 million virtual ranks synchronized in a discrete event fashion on as few as 16,128 real cores of a Cray XT5.

Cloud computing offers the potential to make parallel discrete event simulation capabilities more widely accessible to users who are not experts in this technology and do not have ready access to high performance computing equipment. Services hosted within the ldquocloudrdquo can potentially incur processing delays due to load sharing among other active services, and can cause optimistic simulation protocols to perform poorly. This paper proposes a mechanism termed the Time Warp Straggler Message Identification Protocol (TW-SMIP) to address optimistic synchronization and performance issues associated with executing parallel discrete event simulation in cloud computing environments.

Issues concerning optimistic time management on public-resource computing infrastructures and desktop grids are explored. The master/worker (MW) approach used for these platforms calls for a rethinking of optimistic synchronization and the development of new mechanisms and protocols specific to this paradigm. Approaches to rollback, message cancellation, state management and state saving are described. Challenges specific to adapting optimism to this computing paradigm are discussed as well as optimizations and overhead reduction techniques. The impact of various key parallel discrete event simulation (PDES) application properties on performance of an optimistic MW implementation is evaluated using Aurora, a framework supporting PDES over desktop grids.