Skip to content Skip to navigation Skip to collection information
(What does "Endorsed by" mean?)
Inside Collection (Book): 2008-'09 Open Education Cup: High Performance Computing
Summary: (Blank Abstract)
A shared-memory multiprocessor consists of a number of processors accessing one or more shared memory modules. The processors can be physically connected to the memory modules in a variety of ways, but logically every processor is connected to every module.
We can use any of several metrics to evaluate the performance of a multiprocessor system. In order to keep the model and its implementation manageable, we will focus on the degree of parallelism among the memory modules; that is, we are interested in determining the average number of memory modules that are being accessed simultaneously. The model is as follows:
We know that the Markov chain has a steady state solution (is ergodic) since the chain will be finite and at least one state will have a self-loop. The chain is finite because the number of ways that processors' access requests can be distributed among the modules is finite. Any state that represents at least one request at each memory module will have a self-loop, since any processor that has its request satisfied during a cycle beginning in that state has a non-zero probability of sending its next access request to the same module.
As usual, we proceed in three steps. We first determine, for a
given
It is not possible in general to implement the model using states that only tells us how many modules are going to be busy during the next cycle. Consider, for example, a model for a system with 4 processors and 2 memory modules. A state that only tells us that two modules will be busy during the next cycle does not include enough information to tell us the probabilities of being in the various states at the beginning of the next cycle. This is because two modules will be busy during a cycle that starts with requests distributed among the modules in either of two ways:
If we start a cycle with the four requests distributed as in (1), at the end of the cycle we have two requests left at one module, no requests at the other module, and two processors ready to make new requests. The next cycle may start with the four requests distributed as in (1) or (2), or with four requests at a single module. If we start a cycle as in (2), both modules have a request waiting at the end of the cycle. The next cycle cannot begin with all four requests at a single module.
We must use a definition of state that allows us to determine how the access requests that must wait during a cycle are distributed among the modules at the end of the cycle, in addition to telling us how many modules will be busy during the cycle. (1) and (2) above illustrate exactly how this is done. Each state specifies how the p requests are distributed among the modules, without regard to which module is which. It is unimportant in (1) to know which module has three requests and which has two, since the modules and processors are identical.
With this general definition of state, computing the state
transition probabilities can be divided into two parts. The
first is simple: if
The second part of computing state transition probabilities is to count the number of ways in which processors may choose to make new requests that will result in the same distribution of requests at the beginning of the next cycle (the same next state). Consider the following example with 4 processors and 2 memory modules, as above. Suppose the model begins one cycle with two requests at each module. At the end of the cycle, each module has one request remaining. Two processors will make new requests before the start of the next cycle. If they select the same module, the next state has three requests at one module and one request at the other. There are two ways that this can happen, since there are two modules that they can select and each of these modules has one request remaining from the previous cycle.
To put the two parts together, we compute the single step state
transition probability for the transition from state A to state
B by multiplying the probability of choosing any set of modules
following the cycle beginning in state A by the number of ways
we can choose a set of modules that takes us to state B. For
the example, the probability of making the transition from the
state with two requests at each module to the state with three
requests at one module and one at the other is
Generally, the process of computing state transition probabilities is more difficult that this example would indicate, even though the process just described always works. The difficulty will always come in the second part - counting the number of ways of choosing where new requests go that take the model to the same next state. For this reason, we recommend that you follow the above procedure to compute all single step transition probabilities for each state. Because the single step transition probabilities for a given state (including a transition back to the same state) must sum to 1, this will provide a useful check on whether or not you counted all the possibilities.
We illustrate the complete procedure with several examples. Let
| State | |
|---|---|
| 1 | 2 requests at the same module |
| 2 | 1 request at each of two modules |
First, find the single step transition probabilities. At the
risk of overkill for this particularly simple case, we
explicitly write each probability as the product of the
probability that the new requests go to a particular set of
modules (
Continuing with the example, choose the first
Chapman-Kolmogorov equation. Then
| State | |
|---|---|
| 1 | 3 requests at one module |
| 2 | 2 requests at one module, 1 request at another module |
| 3 | 1 request at each of three modules |
We will make use of the Chapman-Kolmogorov equations for
| State | |
|---|---|
| 1 | all four requests are at one module |
| 2a | three requests are at one module and one request is at another module |
| 2b | two requests are at one module and two requests are at another module |
| 3 | two requests are at one module and one request is at each of two other modules |
| 4 | one request is at each of four modules |
We've chosen the state names to make explicit the number of
memory modules busy in each state. The state transition
probabilities are
The solution is
The three examples allow us to compare the average memory module concurrency with four modules for two, three, and four processors:
| p |
|
|---|---|
| 2 | 1.750 |
| 3 | 2.269 |
| 4 | 2.261 |
In going from 2 to 3 processors, we see about a 30% increase in memory module concurrency. When we go from 3 processors to 4, the performance improves only about 15.5%.
More about this module: Metadata | Downloads | Version History
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:10 am -0500.
