THE MAGAZINE FOR COMPUTER APPLICATIONS
Circuit Cellar Online offers articles illustrating creative solutions
and unique applications through complete projects, practical
tutorials, and useful design techniques.

MONITORING YOUR MICRO

by Daniel Mann & Jim Magro

Start ý Data Gathering ý DRAM Memory Interface Buffer ý Write Buffer "Hit" Monitoring ý Sources and PDF

DATA GATHERING

The type of performance data that is being measured is random in nature, such as the cache hit rate or the number of cycles to read memory. These parameters vary during program execution. Measuring random data enables a precise value to be generated. These precise values take the form of averages, such as the average cache hit rate.

Measured performance parameters are a good estimate of future performance. Actual performance at any instant may vary widely from the measured estimate. The typical use of two large counters does not make any attempt to measure this deviation.

Consider, for example, that an on-chip cache may successfully provide the required data at each memory access. The sequence of hit-and-miss data can be represented by a simple one or zero bitstream. The probability of a one is the same as the probability of a hit occurrence. A stochastic Addie can be used to integrate the probability stream and determine the relevant probability.

Figure 1 shows a possible Addie configuration. A counter is compared with a random number. If the counter is greater than the random number, a one is generated. Large counter values are more likely to produce an output of one from the comparator than smaller counter values.

Figure 1ýHere you can see a possible Addie configuration where a counter is compared with a random number.

The counter output is compared with the 1/0 datastream of interestýthe cache hit information. These two stochastic datastreams are compared to see which one has the highest probability of being one. This sounds more difficult than it is, only an XOR gate is required. When the datastreams differ, there is a difference in probability. This information is fed back to increase or decrease the counter value. Consequently, with each new comparison, the counter is adjusted to produce a probability stream (from the comparator), which matches the input datastream.

The Addie device effectively integrates the probability stream. Hence, converting the probability stream into a digital value (held in the counter) represents the probability of the parameter being measured.

This method of measuring probability is different from the dual counter method. There is no potential overflow. There is no need for an overflow interrupt handler. And, the counter can be read at any time to give a measure of the current probability.

AN 8-BIT ADDIE

As the number of bits used by the counter and random number generator increase, the probability resolution improvs. For example, an 8-bit counter provides a probability resolution of 0.39% (1/255). However, increasing the resolution slows down the integration process. This results in a greater number of samples required before a good estimate of probability can be obtained. Figure 2 shows an 8-bit Addie used to measure a synthetic data stream with a 25% probability.

Figure 2ýAn 8-bit Addie is used to measure a synthetic datastream with a 25% (64/255) probability.

As you can see, the Addie starts with an initial value of 50%. As the input data is sampled, the Addieýs counter value heads towards the expected value. After about 500 samples, the Addie closely tracks the input datastream. This indicates that, after as little as 500 samples, the counter could be read to produce an estimate of the performance parameter being measured.

During the generation of the presented data, both the input and Addie datastreams are averaged over 250 samples. Keeping this window small helps to detect temporary fluctuations in both the generated test data and Addie response.

Figure 3 shows the 8-bit Addie used to measure a 78% probability. The 8-bit counter was initially at a value of 128, which represents a probability of 50%. Once again, after about 500 samples the measuring instrument converges on the desired value.

Figure 3ýHere the 8-bit Addie is used to measure a 78% (200/255) probability.

RANDOM NUMBER GENERATION

The Addie operation requires a random number generator (see Figure 4). A pseudo-random number generator is ideal for this task. A maximum length (m-sequence) can be produced by feeding back selected stages of an n-stage shift register. The required stages are modulo-2 combined and used to produce the input signal for the first stage.

Figure 4ýA random number generator is required for the Addie operation.

The Addie can be encouraged to converge on the required value by using random numbers that correlate. This can be achieved by selecting consecutive stages of the shift register and inverting the most-significant bit (MSB). Hence, the MSB of the current random number will be inverted, becoming the next-to MSB of the next random number to follow.

The test data shown used a 31-bit shift register with feedback taken from stages 3 and 31. The top 8 or 12 bits were used to form the required random number. A smaller (less than 31 bits) shift register can also be used.

PREVIOUS • NEXT