Home Research & Teaching Links

Methods and algorithms for the performance evaluation of systems with a large state space.

Benoit, Anne

18 June 2003

Thesis prepared at the ID-IMAG laboratory, Grenoble
advisor's name : Plateau, Brigitte

in computer science, systems and communications
170 pages - Document language : French

Full-text - Version française

Abstract : Markov Chains facilitate the performance analysis of dynamic systems in many areas of application. This thesis presents the formalism of stochastic automata networks (SANs) to represent Markov systems. The main goal of this work consists in improving existing methods for the performance evaluation of systems with a large state space. For this, we introduce the concept of SANs with replicas, and techniques to reduce the state space of such models. To obtain performance indices, we propose an improvement of the basic operations by taking into account the fact that inside the product state space, the actual reachable state space can be much smaller. The new methods and algorithms have been implemented into the PEPS 2003 software. Numerical examples are provided to illustrate the contributions of this thesis.

Keywords : Performance evaluation ; Large state space ; Stochastic Automata Networks ; Tensor algebra ; Continuous and Discrete time ; Automata replication ; Exact aggregation ; Vector-descriptor product ; Shuffle algorithm

ACM Classification : I.6 ; C.4 ; G.1

MSC Classification : 68M20 ; 65F10

IMAG electronic publications home page

  E-Mail Last modified: Wed Jan 12 16:36:27 GMT 2005