Parallel Simulation of Queueing Petri Nets

Abstract

Queueing Petri Nets (QPNs) are a powerful formalism to model the performance of software systems. Such modelscan be solved using analytical or simulation techniques.Analytical techniques suffer from scalability issues, whereassimulation techniques often require very long simulation runs.Existing simulation techniques for QPNs are strictly sequentialand cannot exploit the parallelism provided by modernmulti-core processors. In this paper, we present an approachto parallel discrete-event simulation of QPNs using a conservativesynchronization algorithm. We consider the spatialdecomposition of QPNs as well as the lookahead calculationfor different scheduling strategies. Additionally,we propose techniques to reduce the synchronization overheadwhen simulating performance models describing systemswith open workloads. The approach is evaluated inthree case studies using performance models of real-worldsoftware systems. We observe speedups between 1.9 and2.5 for these case studies. We also assessed the maximumspeedup that can be achieved with our approach using syntheticmodels.

Keywords

• parallel discrete event simulation
• performance prediction
• stochastic performance modeling
• queueing petri nets