Reducing Markov Chains for Performance Evaluation
A major problem in performance evaluation
of real-life industrial systems is the enormous number of
states generated by the system's model during the simulation process. An example is in a Parallel Object-Oriented
Specification Language (POOSL) model, which can be interpreted as a discrete-time Markov chain enabling the evaluation of long-run average performance metrics. In general
this Markov chains is huge, making performance simulation expensive since all performance estimations must be updated in each state.
In this paper, we introduce a method for performance
evaluation based on Markov chain theory, which aims at the
reduction of the original Markov chain into a smaller chain.
We prove that the reduction yields another Markov chain
and it preserves several important properties. We further
give a method to effectively construct the reduced chain. The
reduction method yields an efficient way to estimate performance metrics during model simulation, since in general it
requires estimations to be updated only in a relatively small
part of the state space.
|
