When creating a Markov chain model of a system (or, to be more precise, implementing a model of a system as a Markov chain), we have to define an appropriate set of states. Whether we are using a discrete-time or continuous-time Markov chain, the states must satisfy two criteria:

A set of states that satisfies these two criteria is not necessarily unique. If we have a choice of states, we should try to choose a set that reduces the complexity of computing the steady state solution. One ad hoc strategy for doing this is the following:

An example of a system abstraction that illustrates this last point is the shared memory multiprocessor model. One definition of state that satisfies criteria 1 and 2 specifies, for each of the pp processors, the memory module that it attempts to access at the beginning of a memory cycle. For example, with two processors P1 and P2 and two memory modules M1 and M2, the possible states are

With mm modules, the number of states is mp m p . If p=8 p 8 and m=8 m 8 , this definition of state leads to 16,777,216 states, a fairly large number.

We can reduce the number of states required by noting that all processor behave similarly; keeping track of specific processors is unnecessary. Instead, define the state as an mm-tuple l 1 l 2 … l m T l 1 l 2 … l m where l i l i is the number of requests at memory module ii at the beginning of a memory cycle. For the two processor, two memory module example, the states are

With pp processors, the number of possible states is the number of ways of distributing pp like objects into mm distinct cells, with empty cells allowed. This reduces the number of states to C⁢m+p−1p C m p 1 p . For 8 processors and 8 memory modules, the number of states is 6,435, a significant improvement, although still somewhat problematic.

It is possible to do much better. Just as it is not necessary to keep track of the individual processors, we do not need to identify specific memory modules. All that is necessary is to know how many modules have 0 requests at the beginning of a memory cycle, how many have 1 request, and so forth. Returning to the example with two processors and two modules, the states are

Since the total number of requests outstanding at the beginning of a cycle is always pp, the number of states is simply the number of ways of distributing pp like objects into mm like cells, or 22 states for p=m=8 p m 8 .

Often, adopting an implementation that reduces the number of states is done at the cost of increasing the complexity of determining the state transition probabilities, since each transition may represent several or many transitions in a model with more states. This is certainly the case with the shared memory multiprocessor model (although if you want to verify this for yourself, you probably should not use 8 processors and 8 memory modules).

Content actions

Footer

This work is licensed by Bart Sinclair under a Creative Commons Attribution License (CC-BY 1.0), and is an Open Educational Resource.

Last edited by Elizabeth Gregory on Jun 9, 2005 10:21 am GMT-5.