Title: Avoiding redundancies in the Proxel method

Authors: Robert Buchholz; Claudia Krull; Graham Horton

Addresses: Department of Computer Science, Otto-von-Guericke University, P.O. Box 4120, 39016 Magdeburg, Germany ' Department of Computer Science, Otto-von-Guericke University, P.O. Box 4120, 39016 Magdeburg, Germany ' Department of Computer Science, Otto-von-Guericke University, P.O. Box 4120, 39016 Magdeburg, Germany

Abstract: The simulation of discrete stochastic systems is used to make predictions on system behaviour. Its most widely used technique, discrete event simulation, computes possible simulation results by using random numbers. Consequently, these results are also only random numbers. Alternative state space-based simulation techniques can directly compute the actual system behaviour, but are computationally infeasible for bigger models. In this work, we improve the state space-based Proxel simulation method by avoiding some of its redundancies through clustering of discrete states. Our experiments demonstrate a speedup by a factor of two to five for realistic models, without any loss in accuracy. If no redundancies in the model can be exploited, the method only incurs a small computational overhead. Our approach thus has the potential of making deterministic state space-based analysis of existing models more efficient, and of enabling the analysis of bigger models that more accurately reflect real systems.

Keywords: model analysis; model evaluation; approximation techniques; Markov chain; discrete stochastic modelling; state space-based simulation; Proxel method; redundancies; system behaviour; discrete state clustering.

DOI: 10.1504/IJCAET.2015.068330

International Journal of Computer Aided Engineering and Technology, 2015 Vol.7 No.2, pp.176 - 191

Published online: 31 Mar 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article