IN. 05448 RR335

115

IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B.P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

PERFORMANCE EVALUATION
OF A CACHE MEMORY
FOR A MINI-COMPUTER

Marc BADEL
Jacques LEROUDIER

Rapport de Recherche N° 335

Décembre 1978

29 p.
PERFORMANCE EVALUATION OF A CACHE MEMORY FOR
A MINI-COMPUTER*

Marc Badel, Jacques Leroudier

IRIA/LABORIA

Résumé :

Nous étudions, dans cet article, les performances d'une anté-mémoire pour un mini-ordinateur qui, dans notre cas, est un MITRA 125 de la SEMS (France). Les performances sont évaluées, en termes de taux de succès et d'accélérations de la machine visée, grâce à un simulateur alimenté par des traces d'adresses prélevées durant l'exécution de programmes réels. Comme de telles performances dépendent fortement du comportement des programmes analysés, ce comportement et son influence sur les performances sont soigneusement étudiés.

Abstract :

In this paper, we study the performance of a cache memory for a mini-computer, namely a MITRA 125 manufactured by SEMS, France. The performance is evaluated, in terms of hit ratios and speeding-ups of the target machine, via a simulator fed with address traces picked up during execution of real programs. Since such a performance strongly depends upon the behaviour of the programs analyzed, the impact of program behaviour on performance is carefully studied.

<footnote>*This work has been supported by SEMS (Société Européenne de Mini-Informatique et de Systèmes) under the contract IRIA/SEMS 02/78.</footnote>
PERFORMANCE EVALUATION OF A CACHE MEMORY

FOR A MINI-COMPUTER*

Marc BADEL, Jacques LEROUDIER
IRIA/LABORIA
BP 105
78150 LE CHESNAY
(FRANCE)

# 1 - INTRODUCTION

A cache memory [1, 2] is a buffer between the CPU of a computer and its main memory aiming at increasing the speed of the memory accesses. Usually in a computer, the CPU cycle is noticeably smaller than the read/write memory cycle, thus CPU is slowed down by memory. In this context, a cache represents a trade-off permitting to get better performance without using a fast but expensive technology for the entire memory of a computer [2, 3].

In our case, we study the gain, in terms of speeding-ups of the target machine, which can be expected by providing a mini-computer, namely a MITRA 125 [4], with a cache memory. Formerly BELL and CASENT [5] have evaluated the improvement brought to a PDP/8 by a cache the structure of which was very close to ours. But they mainly emphasized the implementation, ignoring the influence of programs' behaviour on performance. This paper thoroughly analyzes the performance obtained with a cache and attempts to relate it to the behaviour of the programs running on the machine.

In a first section, we describe the mechanism of the cache under study for our purposes and we also define the performance criteria to be considered. In the second section we describe the tool used to pick up measurements and we analyze the characteristics of the collected measurements, that is mainly the programs' behaviour. The third section is devoted to performance analysis via an address trace driven simulator. This performance is evaluated both in a steady and a non-steady state context.

# 2 - THE CACHE

## 2.1 - The mechanism

The structure of the cache we study is presented in Figure 1. This structure does

<footnote>* This work has been supported by SEMS (Société Européenne de Mini-Informatique et de Systèmes) under the contract IRIA/SEMS 02/78.</footnote>
not make any assumption on the addressing mechanism of the target machine. In particular, the use of base registers by the MITRA 125 [4] is completely transparent. The accesses to the cache are made through the absolute address of the information in main memory.

<figure><img src="image_2.png" /><figcaption>Figure 1 : Cache architecture</figcaption></figure>

The absolute address is a 19-bit number used to reference a 16-bit word in memory. This address is divided into two parts : the right-most part is composed of the k low order bits of the address and the left-most part of the (19-k) other bits (high order bits). For clarity, let us assume that the address to be interpreted has a right-most part which is the number *i* and a left-most part which is the number *j* (see figure 1).

The cache is divided into n segments (n being a power of 2) of $2^k$ entries each, if k is the number of bits of the address low-order part. Thus the total cache size, as far as the information part is concerned, is of $2^k \times n$ 16-bit words ($2^k \times n$ double words with a prefetching mechanism). The n segments are accessed in parallel through the k low-order bits of the address. More precisely, all the i-th entries of each segment are accessed in parallel (see figure 1). Each cache entry consists of three parts (see figure 1) :

1. a tag part of (19-k) bits which contains the high order bits of the address,
2 - a service part which contains validity and parity bits and also bits used by the replacement algorithm,

3 - an information part of 16 or 32 bits which contains the information itself (the content of the referenced word or double word according to the existence or not of prefetching).

The n i-th entries of each segment are scanned in order to find the tag equal to the number j (see figure 1). If such an entry exists, the referenced word is within the cache and the information part of the entry is transferred to CPU. If such an entry does not exist, the referenced word is not within the cache and it must be transferred to it from memory. If an i-th entry of a segment is still free, the referenced word is stored in it, otherwise the replacement algorithm has to free one of the n i-th entries.

It is noteworthy that the proposed architecture aims at exploiting a certain program "locality" [6] : the words having addresses the high-order parts of which are equal and the low-order parts successive (memory vicinity) will be loaded together into the cache.

## 2.2 - The performance criteria

To evaluate the improvement brought by the cache, we need to define some performance criterion. The level we consider is not detailed enough to take into account problems such as data or addresses interleaving, data path width, pipelining, and so on, all related to parallel accesses. We shall consider some "speeding-up" of the machine.

Let us consider the mean time for a word (or a double word) to be available for CPU. Let m and M be such mean times according to whether the word is within the cache or not. Let p be the probability of finding a referenced word within the cache (p is also called the hit ratio of the cache). Then the mean time for a word to be available is :

$$ (1) \qquad T = pm + (1-p)M $$

Thus the CPU throughputs with and without cache, in terms of data words available to be processed by CPU, are respectively :

$$ (2) \qquad D_C = \frac{1}{pm + (1-p)M} $$

$$ (3) \qquad D_M = \frac{1}{M} $$

Therefore we can measure some increase of the speed of the machine by the ratio :

$$ (4) \qquad A = \frac{D_C}{D_M} = \frac{M}{pm + (1-p)M} = \frac{1}{1-p(1 - \frac{m}{M})} $$

It must be noticed that the improvement we measure is not the total resultant speeding-up of the machine since we do not consider parameters as possible parallel accesses, mean time per instruction processing and average number of accesses per instruction. It must be clear that the throughputs we consider are not instruction throughputs, but we think that equation (4) permits to roughly evaluate an order of magnitude of the speeding-up visible by a user.

It is evident from the equation (4) that in order to maximize A, we have to minimize the expression : $1-p(1 - \frac{m}{M})$, that is :

- p has to be as large as possible
- $\frac{m}{M}$ as small as possible.

The ratio $\frac{m}{M}$ is an architecture parameter which expresses the usefulness of the cache (m and M must be noticeably different). In our case, it is about $\frac{1}{4}$ ($\frac{m}{M} \approx \frac{1}{4}$) and we shall consider it as fixed. The hit ratio p depends on the cache structure and the programs' behaviour. From the equation (4) we give some "speeding-ups" we can expect for different values of p.

<table><tr><td>p</td><td>0.0</td><td>0.5</td><td>0.6</td><td>0.7</td><td>0.8</td><td>0.85</td><td>0.9</td><td>0.95</td><td>1.0</td></tr><tr><td>A</td><td>1.</td><td>1.60</td><td>1.82</td><td>2.10</td><td>2.50</td><td>2.76</td><td>3.08</td><td>3.48</td><td>4.0</td></tr></table>

Thus, roughly speaking, we can see that to double the speed of the machine we must assure a hit ratio of 0.7 and to triple the speed a hit ratio of 0.9.

Therefore we shall study, in this paper, a structure of cache aiming at maximizing the hit ratio p.

## 3 - THE COLLECTED MEASUREMENTS

### 3.1 - The measurement characteristics

The optimization of the hit ratio p cannot be undertaken independently of the programs' behaviour, which is, in our case, the way the programs address words in main memory.

For that purpose, hardware probes were plugged into a MITRA 125 CPU and connected to another SEMS mini-computer (a SOLAR*). Periodically the SOLAR copies on a magnetic tape the measurements it has picked up. Because of the way the measurements are collected, there exist "holes" on the tape which correspond to the measurements missed during copying (from 100 to 500 milliseconds). Thus measurements on the tape are gathered in blocks of 32K words of 32 bits separated from each other by "holes".

An elementary measurement (a referenced address) is coded on 32 bits and provides information on :

- the address referenced (19 bits)

- the nature of the access : data or instruction

- the base registers used

- the direction of the transfer between the CPU and the memory (write or read operation)

- the possible conflicts with i/o channels.

About thirty programs were run on the MITRA 125 and spied. We report, in this paper, the results concerning eight of them which are described in the following table :

<footnote>* all this part of work has been done by the SEMS Center at Echirolles (France)</footnote>
<table><thead><tr><td>Identification</td><td>Description</td></tr></thead><tbody><tr><td>Program A</td><td>Fortran Program</td></tr><tr><td>Program B</td><td>Test of the MMT2 Monitor</td></tr><tr><td>Program C</td><td>MAS2 Assembler</td></tr><tr><td>Program D</td><td>Benchmark (coded in FORTRAN)</td></tr><tr><td>Program E</td><td>MAS Assembler with standard environment</td></tr><tr><td>Program F</td><td>First phase of MAS Assembler</td></tr><tr><td>Program G</td><td>Sorting program</td></tr><tr><td>Program H</td><td>Grammar Generator</td></tr></tbody></table>

We studied the behaviour of these different programs according to:

- the uses of the different base registers,

- the respective access rates to instructions or data,

- the respective read or write access rates,

- the conflict rates with i/o transfers,

- the behaviour within memory, that is with respect to the referenced addresses,

Since the program behaviour within memory is much more complex than the behaviour related to other parameters such as base register uses or different access rates, we shall emphasize this point by devoting it a complete section in the sequel of the paper.

We give in figure 2 some characteristics of program behaviour. Some of them are rather stable and repeated through all the programs:

- the read access rates are high and stable (always between 83 % and 90 %). To explain this fact, notice that all the instruction accesses are read accesses.

- the instruction access rates are not very much stable, since they vary from 41 % to 68 % and the confidence interval widths can reach 4 %. But, however, they indicate a relative balance (around 50 %) between instructions and data.

- the conflicts with i/o transfers are either non-existent or very rare, except possibly for the programs E and F where they can reach 2 % and 3 % of all the references.

On the contrary, some other figures of merit heavily vary from one program to another:

- the base register G is relatively used, from a minimum of 13 % with program B (test of monitor) to a maximum around 70 % with programs F and H.
- the base register S (used by the only monitor) is very fluctuating. Its use is minimum for programs A (Fortran program) and D (Fortran benchmark), and maximum for programs C (assembler) and G (Sorting program). Notice that the use of base register S permits to roughly evaluate the overhead associated with each program.

- the base register Q (the base register of the shared sub-programs) is seldom used except by programs A, B and D. This base register seems to be associated with FORTRAN.

- the base register Z (the base register of the shared data) is not very used. This should change in the future, in the case of interactive systems (conversational systems, data bases, and so on).

- the base register H permits to evaluate the frequency of instructions moving bytes strings in memory.

<table><thead><tr><th>Programs</th><th>Read Access Rates in %</th><th>Conflict Rates with I/O transfers in %</th><th>Instruction Access Rates in %</th><th>Access Rates using base C in %</th><th>Access Rates using base Z in %</th><th>Access Rates using base Q in %</th><th>Access Rates using base S in %</th><th>Access Rates using base H in %</th></tr></thead><tbody><tr><td>A</td><td>83.00 ± 0.08</td><td>no conflict</td><td>42.6 ± 0.2</td><td>45.5 ± 0.4</td><td>0.05 ± 0.05</td><td>29.6 ± 0.7</td><td>0.3 ± 0.2</td><td>24.5 ± 0.5</td></tr><tr><td>B</td><td>89.6 ± 0.7</td><td>1.6 ± 0.5</td><td>68. ± 2.</td><td>13. ± 1.</td><td>4.3 ± 0.3</td><td>45. ± 3.</td><td>26. ± 2.</td><td>8.6 ± 0.5</td></tr><tr><td>C</td><td>88.0 ± 0.2</td><td>0.8 ± 0.2</td><td>55.1 ± 0.2</td><td>44. ± 1.</td><td>3.7 ± 0.1</td><td>0.33 ± 0.09</td><td>48.4 ± 0.9</td><td>3.1 ± 0.3</td></tr><tr><td>D</td><td>87.8 ± 0.2</td><td>0.3 ± 0.2</td><td>58.1 ± 0.3</td><td>30.3 ± 0.2</td><td>0.5 ± 0.1</td><td>62. ± 1.</td><td>4. ± 1.</td><td>2.9 ± 0.2</td></tr><tr><td>E</td><td>85.2 ± 0.5</td><td>2. ± 0.5</td><td>53.3 ± 0.5</td><td>57. ± 3.</td><td>2.7 ± 0.2</td><td>1.1 ± 0.3</td><td>29. ± 2.</td><td>8.3 ± 0.5</td></tr><tr><td>F</td><td>85.3 ± 0.6</td><td>1.1 ± 0.6</td><td>51.0 ± 0.5</td><td>73. ± 2.</td><td>1.8 ± 0.2</td><td>2.2 ± 0.9</td><td>14. ± 2.</td><td>7.3 ± 0.6</td></tr><tr><td>G</td><td>77.6 ± 0.8</td><td>2.9 ± 0.9</td><td>41.8 ± 0.8</td><td>20.4 ± 0.9</td><td>4.7 ± 0.3</td><td>0.8 ± 0.3</td><td>47. ± 1.</td><td>24. ± 1.</td></tr><tr><td>H</td><td>86.9 ± 0.8</td><td>0.8 ± 0.8</td><td>46.2 ± 0.5</td><td>71. ± 4.</td><td>1.6 ± 0.6</td><td>1.1 ± 0.6</td><td>19. ± 3.</td><td>6. ± 1.</td></tr></tbody></table>

Figure 2

It must be noticed that the program G significantly differs from the other ones, mainly because of numerous references issued by the i/o channels. In particular, this phenomenon affects the read access and instruction access rates.

We may wonder about the validity of our results, for the number of references analyzed varies from 325,445 to 1,295,419, which represents the execution of 100,000 to 600,000 instructions. This number can seem very low, but one should remember the technique which was used to collect the measurements. The referenced addresses were sampled per blocks of 32,768 consecutive addresses, each block being separated from the next one by a "hole" in time of about 100 to 500 milliseconds. Therefore the analysis we performed concerns relatively long program executions (about 10 minutes) and we can guess its validity.

These results lead to some first conclusions :

- the structure of the cache must not depend on the uses of the different base registers, for these uses vary too much from one program to another and, possibly, in the future.
- on the contrary, the structure of the cache may perhaps depend on the distribution between instructions and data by dividing the cache into two parts according to the measured distribution (roughly 50% for each part).

## 3.2 - Program behaviour with respect to memory

In a first step, we visualized the behaviour of the different programs in memory. The figures in Annexe I display raw information that we dispose on each program.

The X-axes represent the execution time given in numbers of references and the numbers of the references pages (blocks of consecutive words in memory) are plotted on the Y-axes. A dash on the graph indicates the pages referenced by the program at a given instant of time.

Notice that, due to the scales used to plot the figures, several addresses seem to be referenced simultaneously. This is only an artefact. The scales which have been used are as follows :

- X-axes : the time unit is of 1024 references

- Y-axes : the memory address unit is of 1000 words.

Because of the technique used to collect measurements, magnetic tapes contain blocks of 32K consecutive references. We have visualized this fact in Annexe I by drawing on each figure vertical lines to separate the different blocks. It is noteworthy that, on each tape (thus for each program), blocks look very similar. This fact confirms that the data can be considered as relatively representative.

From these results we can deduce that :

- program A is "quiet" and stationary, except possibly on the block 16 where we notice the influence of printer i/o operations.

- program B is more "excited", perhaps representative of a heavy and varied workload. This program will be preferably considered to evaluate the cache performance in order to avoid performance overestimation.

- "stripes" of continuously referenced addresses can be noticed in the different programs.

- program H shows the influence of

- addresses referenced by i/o transfers (block 17)

- wait loops when the machine is idle (blocks 18, 19, 20, 21, 22).

In order to quantify this memory behaviour we studied some measure of program "locality" [6].

### 3.2.1 - LRU Stacks [7]

If some "locality" phenomenon exists the probability for an address to be referenced roughly decreases as its rank in the LRU stack increases. Therefore we simulated the LRU (Least Recently Used) algorithm [7] with the address references recorded on the magnetic tapes previously described. We have considered two kinds of stacks :

- in the first one, the information to be addressed consists of 128 words blocks (pages of 128 words). The block size has been chosen because of the MITRA 125 addressing mechanism with which only
128 words can be directly addressed (otherwise a base register has to be modified).

- in the second one, the information to be addressed consists of double word blocks (pages of 2 words). In this case, our purpose is to find out some "intimate" locality.

<figure><img src="image_3.png" /><figcaption>(3.1)</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(3.2)</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(3.3)</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(3.4)</figcaption></figure>

Figures 3 : LRU Stacks
We give in figures 3 some typical results we obtained. We have plotted the proba-
bility for a rank of the LRU stack to be referenced as a function of the rank.

As far as the 128 words stacks are concerned, we observe a global decrease (see figure 3.1) which can be locally contradicted on a few ranks (see figure 3.2). This fact comes from sudden cyclic locality changes. Despite that point, we may conclude there exists some locality phenomenon.

We may notice that such a behaviour is very close to the ones met on large compu-
ters which use other addressing mechanisms and more sophisticated instructions.

As for the double word stacks, the decrease is not so obvious because of the in-
fluence of program loops (see figures 3.3 and 3.4). This influence is particularly
noticeable for programs A and C (we give in figure 3.4 the results for program C)
where some ranks the order of which is greater than 10 or 40 have almost the same
probability as the first rank to be referenced. It is noteworthy that some of these
peaks can be interpreted to give an order of magnitude of program loop sizes. Note
also that the high probability for the first rank to be referenced indicates that
the prefecting mechanism described in section 2.1 will increase the hit ratio of
the cache, since after having referenced a double word, there is a high probabili-
ty for referencing it again.

### 3.2.2 - Working Sets [8]

The results we have just presented do not allow to size up the cache and do not give a detailed behaviour of programs with respect of memory. Therefore we have studied the working-sets [8] of the different programs. In fact, instead of the working-set itself, we have studied its size. Because of the MITRA 125 addressing mechanism (see § 3.2.1) we considered again 128 words pages.

We give in figures 4 two kinds of results. Both are related to program locality, but the second one can be used to roughly estimate the global size of the cache.

#### a - program locality

We have plotted the mean size of the working-sets as a function of their window $T(\bar{W}(T))$. The slower the increases of these curves, the more "local" the programs. Let us notice that these curves are unit slope straight lines for a program not "local" at all which accesses a new page at each reference. From figure 4.1, we can conclude that the notion of locality exists (on the figure, since the scales are quite different, a unit slope straight line is very "close" to vertical).

#### b - global size of the cache

The cache will be all the more efficient as its size will be large enough to load working-sets of programs. We give in figure 4.2 the working-set according to the time for a relatively "excited" program (program B). The working-sets under study have a window of 2048 references. Their sizes are counted in number of 128 words pages and the time is counted in steps of 512 references.

From this kind of figures of merit, we may deduce that

- a waiting loop has a working-set of roughly 5 pages,

- the "quiet" programs have working-sets of 20 to 30 pages and "excited" ones of 40 to 50 pages,

- no program has a working-set which contains more than 80 pages.

We can conclude that the order of magnitude of the cache size is possibly about 10K words. This will be corroborated by the results presented in section 4.
<figure><img src="image_7.png" /></figure>

(4.1)

<figure><img src="image_8.png" /></figure>

(4.2)

<caption>Figures 4 : Working Sets</caption>

3.3 - Program behaviour with respect to the low order bits of the referenced addresses

Because of the cache structure (see § 2.1, figure 1), the low order bits of a referenced address take a prominent part in the cache performance, from the standpoints of both hit ratio and segment space utilization. In particular, a good segment space utilization needs a uniform probability distribution of the low order part of the referenced addresses, since, in this case, all the segment entries have the same probability to be accessed. (Notice the conflict with the "locality" assumption).
<table><tr><td>0.0545</td><td>0.0546</td><td>0.0940</td><td>0.0646</td><td>0.0800</td><td>0.0556</td><td>0.0622</td><td>0.0807</td><td>0.0690</td><td>0.0502</td><td>0.0454</td><td>0.0791</td><td>0.0553</td><td>0.0479</td><td>0.0441</td><td>0.0628</td></tr><tr><td>0.1090</td><td>0.1586</td><td>0.1356</td><td>0.1429</td><td>0.1192</td><td>0.1246</td><td>0.1031</td><td>0.1069</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.2676</td><td></td><td>0.2786</td><td></td><td>0.2438</td><td></td><td>0.2101</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.5462</td><td></td><td></td><td></td><td>0.4538</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></table>

Odd

even

odd

Program A

<table><tr><td>0.0533</td><td>0.0457</td><td>0.2133</td><td>0.0386</td><td>0.0419</td><td>0.0443</td><td>0.0449</td><td>0.0383</td><td>0.0418</td><td>0.0411</td><td>0.0381</td><td>0.0427</td><td>0.2097</td><td>0.0324</td><td>0.0419</td><td>0.0319</td></tr><tr><td>0.0990</td><td>0.2520</td><td>0.0862</td><td>0.0832</td><td>0.0829</td><td>0.0808</td><td>0.2422</td><td>0.0737</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.3510</td><td></td><td>0.1695</td><td></td><td>0.1637</td><td></td><td>0.3159</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.5204</td><td></td><td></td><td></td><td>0.4796</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></table>

Odd

even

odd

Program B

<table><tr><td>0.1248</td><td>0.0483</td><td>0.0217</td><td>0.0645</td><td>0.0922</td><td>0.0671</td><td>0.0728</td><td>0.0668</td><td>0.0927</td><td>0.0421</td><td>0.0222</td><td>0.0656</td><td>0.0451</td><td>0.0657</td><td>0.0662</td><td>0.0422</td></tr><tr><td>0.1732</td><td>0.0862</td><td>0.1593</td><td>0.1396</td><td>0.1347</td><td>0.0878</td><td>0.1108</td><td>0.1084</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.2594</td><td></td><td>0.2988</td><td></td><td>0.2225</td><td></td><td>0.2193</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.5582</td><td></td><td></td><td></td><td>0.4418</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></table>

Odd

even

odd

Program C

<table><tr><td>0.0656</td><td>0.0446</td><td>0.0623</td><td>0.0647</td><td>0.0620</td><td>0.0751</td><td>0.0776</td><td>0.0748</td><td>0.0570</td><td>0.0469</td><td>0.0566</td><td>0.0610</td><td>0.0710</td><td>0.0614</td><td>0.0574</td><td>0.0621</td></tr><tr><td>0.1102</td><td>0.1270</td><td>0.1371</td><td>0.1524</td><td>0.1039</td><td>0.1176</td><td>0.1323</td><td>0.1195</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.2372</td><td></td><td>0.2895</td><td></td><td>0.2215</td><td></td><td>0.2518</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>0.5266</td><td></td><td></td><td></td><td>0.4734</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></table>

Odd

even

odd

Program D

<caption>Figure 5</caption>
In this context, we have estimated histograms of the low order part addresses generated by programs. We have considered low order parts coded on 1, 2, ..., 10 bits. That is we have estimated the entry access probabilities of segments of $2, 2^2, ..., 2^{10}$ words.

The results we obtained (see figure 5) shows that these probabilities are not equal (non uniform distribution) for large segments (many entries). If the segments are small, the accesses are more balanced, but they can fluctuate according to the programs (see programs B and C). Therefore if the segments are too large, bad segment space utilizations have to be expected. This is corroborated by the results presented in section 4.

We give in figure 5 some results we obtained for segments of 2, 4, 8 and 16 entries. Notice that the probabilities to access odd or even addresses are relatively equal but the ones for the even addresses are always slightly greater.

## 3.4 - Conclusion

Up to now the results we have presented deal with the only program behaviour, but they permit to have some strong conclusions on the cache architecture :

- the idea of a cache memory is quite justified since the concept of "locality" exists both at a fine level (the 16 bits words) and at a more global one (the 128 words page).

- the cache will be large enough, about 10K words (the maximum working-set size).

- the segments will not be too large so that they are filled enough, but not too small in order to allow the loading of a "locality".

- a prefetching mechanism will increase the hit ratio of the cache (see § 3.2.1).

# 4 - THE PERFORMANCE EVALUATION

## 4.1 - The simulator

Precise cache performance has been evaluated by simulation. A simulator of the cache structure as described in section 2.1 was built in such a way that it permits to study the impact of :

- the cache size,

- the number of segments,

- the replacement algorithm (three algorithms were considered : FIFO, LRU and RANDOM),

- the policies concerning write accesses originated either from CPU or from i/o channels.

The inputs of the simulator consists of addresses' traces and the outputs provide information on hit ratios, space utilizations (global and for each segment), stationary or non-stationary behaviour of the cache (in case of stationarity, coincidence intervals are built on the different figures of merit).

The results we seek for are of three kinds :

- to evaluate the minimum performance to be expected for the cache (which can be reached in the worst case).
- to study transient behaviour of the cache in order to find out reasonable performance (which can be expected, in average, on a long run).

- to evaluate the influence of the write accesses (generated from either CPU or i/o channels) on performance.

## 4.2 - The minimum performance

We have considered the worst operation conditions, that is :

- the cache is started empty. Our purpose is to take into account a sudden context change large enough so that information contained in the cache is no longer relevant.

- the length of the addresses' trace feeding a simulation run is limited to one block of 32K consecutive referenced addresses (see § 3.1).

- the blocks selected for the simulation runs are particularly "excited" in order to get pessimistic performance.

The approach we present aims at determining performance reachable at any time. In other respects, building confidence intervals in such conditions has the following meaning : all the conditions during the experiments are stationary. That is, intuitively speaking, the references are always rather not "local" and "complete" cache "renewals" regular and relatively frequent (in the average, every 32K references).

We give in figure 6 the characteristics of the "excited" blocks selected according to the program behaviour studies we have presented in section 3.

<table><caption>Figure 6</caption><thead><tr><th>Programs</th><th>Selected block numbers (see Annex I)</th><th>Numbers of references different within the block</th><th>Min. Numbers of references different for the whole program</th><th>Max. Numbers of references different for the whole program</th></tr></thead><tbody><tr><td>A</td><td>16</td><td>3335</td><td>495</td><td>3335</td></tr><tr><td>B</td><td>21</td><td>5687</td><td>1848</td><td>7762</td></tr><tr><td>C</td><td>3</td><td>2544</td><td>74</td><td>4718</td></tr><tr><td>D</td><td>18</td><td>3550</td><td>1668</td><td>3639</td></tr><tr><td>E</td><td>17</td><td>4632</td><td>3176</td><td>8141</td></tr><tr><td>F</td><td>19</td><td>5874</td><td>3012</td><td>8134</td></tr><tr><td>G</td><td>17</td><td>9278</td><td>57</td><td>11019</td></tr><tr><td>H</td><td>8</td><td>3077</td><td>1350</td><td>8125</td></tr></tbody></table>

We present some results we obtained in figures 7. The figure of merit we consider is the hit ratio.
<figure><img src="image_9.png" /><figcaption>Figure 7.1</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 7.2</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 7.3</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>Figure 7.4</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 7.5</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 7.6</figcaption></figure>
We can summarize these results as follows :

1 - Replacement algorithm

• the replacement algorithm has a slight influence on hit ratios.
In general, the confidence intervals obtained are overlapped.

• the LRU algorithm is often the best and FIFO is very close to LRU. RANDOM is the worst.

• the influence of the replacement algorithm becomes noticeable when the cache is small and has many segments. That is normal.

2 - Number of segments

• the hit ratios increase with the number of segments.

• this parameter has a strong influence, if the cache is small.

3 - Global size of the cache

• the hit ratios increase with the cache size.

• this increase depends on the programs.

• beyond 8K or 10K, this parameter has a small influence on performance.

4 - Prefetching

• this parameter has a strong influence on performance.

• prefetching seems to be essential in order to get satisfactory performance.

All the results we present have confidence intervals the widths of which vary from
‡ 0.05 for the small caches (512 words) to ‡ 0.03 for the large ones (8K words).

4.3 - Transient behaviour of the cache

4.3.1 - Stationarity of time intervals between cache faults

The hit ratio we are interested in derives from time intervals between cache faults counted in numbers of references. Therefore we will consider these time intervals in order to get some results on the cache stationarity. Let T be the period during which we observed the cache and t₁, t₂, ..., tₙ ≤ T ≤ tₙ₊₁ the n instants at which n cache faults occurred. If we assume stationarity, we get (see [9]) :

$$
(5) \quad \lim_{n \to \infty} U_n = \lim_{n \to \infty} \frac{\frac{\sum_{i=1}^{n} t_i}{n} - \frac{1}{2} T}{T \sqrt{\frac{1}{12n}}} = N(0,1)
$$

That is $U_n$ converges towards a Gaussian distribution. Notice that the test we con-
sider is optimal [9], if the stochastic process is Poisson with an arrival rate
given by :
$$ (6) \qquad \lambda(t) = e^{\alpha+\beta t} $$

In that case, we get :

$$ \beta = 0 \quad \langle=> \quad \text{stationarity} $$

$$ \beta \neq 0 \quad \langle=> \quad \text{non-stationarity} $$

We computed the $U_n$'s for the programs A, B, and C for large n's by considering the whole traces without taking into-account the "holes" (see section 3.1). This approach seems reasonable if we consider the figures given in Annexe I where the "holes" do not disturb the sampling. The results we got shows that the $U_n$'s absolutely values are very much greater than 1.96, that is (see a table of Gaussian distribution) the stationarity is rejected with a 95 % confidence. Therefore stationarity does not exist for programs A, B and C as far as we consider them globally.

We repeated computations of $U_n$'s for different n's (hence for different periods T) in order to find out some piecewise stationarity. This assumption has been rejected for the programs B and C where the stationary regions were very "small". On the contrary, for program A we found out "large" stationary regions (from 10,000 to 100,000 references) interrupted by "small" non stationary ones (from 1,000 to 5,000 references). Thus, strictly speaking, there does not exist a stationary state performance. Therefore we undertook a more precise study in order to formalize this notion.

For that purpose, we defined a new measure intermediate between traces given in Annexe I and working-sets, more appropriate to take into account working-set variations. The main memory is divided into 128 words pages and its "occupancy" is represented by a boolean vector where 0's or 1's indicate whether the corresponding pages were referenced or not during the considered time window. The measure we consider is the *distance* between two such consecutive memory "occupancies". That is :

$$ (7) \qquad d(\bar{x}, \bar{y}) = \sum_{i=1}^{n} x_i \oplus y_i \quad \text{where } \bar{x} \text{ and } \bar{y} \text{ are two memory "occupancies" and } x_i, y_i \text{, their respective components.} $$

It is obvious that the distance we just defined is the number of the components of vectors $\bar{x}$ and $\bar{y}$ which differ. So the larger the distances, the more "excited" the programs.

We give in figures 8 the results we obtained for programs A', B' and C' which are very similar to programs A, B and C reported through this paper. The time windows we considered are of 1024 references. The Y-axes represent both the distances (between two consecutive memory "occupancies") and the numbers of cache faults (on a time window), whereas the X-axes represent the time counted in windows of 1024 references. The dotted lines are distances and the continuous lines are numbers of cache faults for caches of :

1 - 2 segments of 4K with prefetching

2 - 1 segment of 8K without prefetching

3 - 2 segments of 4K with prefetching

4 - 1 segment of 8K without prefetching.
nb faults × 10⁻¹
distance

<figure><img src="image_15.png" /><figcaption>PROGRAM B'</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>PROGRAM C'</figcaption></figure>

<figure><img src="image_17.png" /></figure>

Figures 8
When the curves are separated from each other, they always are in the order indicated above (1, 2, 3, 4). From figures ⁸, we can notice that the cache (in fact, its performance) immediately reacts to program behaviour : a mediocre performance corresponds to an "excited" behaviour (concordance of peaks) and a good one to a "quiet" behaviour (concordance of troughs). From this strong evidence, we tried to model the cache by a simple transfer function between distances representing program behaviour and cache fault rates representing the figures of merit under consideration. Unfortunately we were unable to find out such a function.

### 4.3.2 - The hit ratio as a function of time

From the previous results we have presented, we cannot consider a limiting quantity such as :

$$ (8) \qquad \hat{p} = \lim_{t \to \infty} \hat{p}(t) \qquad \text{where } \hat{p}(t) \text{ is an estimation of the hit ratio computed between the instants 0 and t.} $$

since there does not exist a steady state. Therefore we studied hit ratios as functions of time. We give in figure 9 some results we obtained. In order to get reasonable sizes for the different figures we used a logarithmic scale for the X-axes where the time is counted in references. For all the experiments, all the 32K references blocks of a program trace (see section 3.1) were considered as consecutive and devoid of "holes" (see also 4.3.1).

<figure><img src="image_18.png" /><figcaption>Figure 9 : Hit ratios as functions of time</figcaption></figure>

From all the results we got, it seems there exists, except perhaps for programs B and G, an asymptote (a limiting hit ratio) located a bit beyond 0.9. This would lead to conclude that the limiting quantity in (8) exists. In fact we have to be careful because $\hat{p}(t)$ is an cumulative quantity and therefore not much sensitive to fluctuations. However that may be we give these limiting quantities for some caches in figures 10. To understand the behaviour of the cache as the time is running we give in figures 11 the space utilization of the cache as a function of time. Except for program B, which is very scattered in memory (see Annexe I), we notice that the space utilizations are very low. We must not deduce from this that the cache is badly used : it is the price we have to pay in order to get satisfactory performance.
<table><caption>Figure 10.1</caption><thead><tr><th>Programs</th><th>LRU<br>without<br>prefetching</th><th>LRU<br>with<br>prefetching</th></tr></thead><tbody><tr><td>A</td><td>0.977</td><td>0.979</td></tr><tr><td>B</td><td>0.910</td><td>0.954</td></tr><tr><td>C</td><td>0.972</td><td>0.984</td></tr><tr><td>D</td><td>0.984</td><td>0.991</td></tr><tr><td>E</td><td>0.900</td><td>0.949</td></tr><tr><td>F</td><td>0.903</td><td>0.946</td></tr><tr><td>G</td><td>0.877</td><td>0.922</td></tr><tr><td>H</td><td>0.936</td><td>0.960</td></tr></tbody></table>

Hit ratios of caches of two segments of 4K (confidence intervals less than 0.01)

<table><caption>Figure 10.2</caption><thead><tr><th>Cache</th><th>LRU<br>without<br>prefetching</th><th>LRU<br>with<br>prefetching</th></tr></thead><tbody><tr><td>1 × 8K</td><td>0.889</td><td>0.942</td></tr><tr><td>2 × 4K</td><td>0.910</td><td>0.954</td></tr><tr><td>4 × 2K</td><td>0.926</td><td>0.959</td></tr><tr><td>8 × 1K</td><td>0.934</td><td>0.961</td></tr><tr><td>1 × 4K</td><td>0.835</td><td>0.920</td></tr><tr><td>2 × 2K</td><td>0.858</td><td>0.934</td></tr><tr><td>2 × 1K</td><td>0.797</td><td>0.900</td></tr><tr><td>2 × 512</td><td>0.738</td><td>0.862</td></tr></tbody></table>

Hit ratios of different caches for program B (confidence intervals less than 0.01)
PROGRAM A

<figure><img src="image_19.png" /><figcaption>Figure 11.1</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Figure 11.2</figcaption></figure>

PROGRAM C

<figure><img src="image_21.png" /><figcaption>Figure 11.3</figcaption></figure>
### 4.3.3 - The influence of the initial state

The results given in section 4.2 are surely pessimistic but the ones given just above are perhaps optimistic. Therefore we studied the influence of the initial state of the cache on the performance. In this view we give in figures 12 some results we obtained. We have drawn hit ratios as functions of time, on the one hand the simulation experiments were started with the cache empty of information and on the other hand the cache was initialized with the 32K references blocks preceding the selected one (see section 4.2).

From these experiments we may conclude that the average cache performance on a long run will be probably a lot better than the results reported in figures 7 and perhaps not so far from the ones given in figures 10.

<figure><img src="image_22.png" /><figcaption>Figure 12.1</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Figure 12.2</figcaption></figure>

### 4.4 - The influence of the write accesses

A word in the cache can be read or written either by the CPU or by the i/o channels. Several policies can be implemented as far as the write accesses (modification of information) are concerned. Until now, the policy we have followed in all the experiments consists in:

1. invalidating the data within the cache which are modified by i/o channels,

2. not loading the data outside the cache which are modified either by the CPU or by the i/o channels (write accesses).
<table><caption>Figure 13</caption><thead><tr><th>Programs</th><th>Cache</th><th>LRU without prefetching</th><th>LRU with prefetching</th><th>Total Number of analyzed references</th><th>Total Number of i/o accesses</th><th>Number of write i/o accesses</th></tr></thead><tbody><tr><td rowspan="3">A</td><td>1 × 4K</td><td>0.978</td><td>0.991</td><td rowspan="3">1,245,184</td><td rowspan="3"></td><td rowspan="3"></td></tr><tr><td>2 × 4K</td><td>0.996</td><td>0.998</td></tr><tr><td>1 × 8K</td><td>0.978</td><td>0.995</td></tr><tr><td rowspan="3">B</td><td>1 × 4K</td><td>0.868</td><td>0.953</td><td rowspan="3">1,295,419</td><td rowspan="3"></td><td rowspan="3"></td></tr><tr><td>2 × 4K</td><td>0.947</td><td>0.988</td></tr><tr><td>1 × 8K</td><td>0.925</td><td>0.977</td></tr><tr><td rowspan="3">C</td><td>1 × 4K</td><td>0.944</td><td>0.984</td><td rowspan="3">1,306,624</td><td rowspan="3"></td><td rowspan="3"></td></tr><tr><td>2 × 4K</td><td>0.982</td><td>0.993</td></tr><tr><td>1 × 8K</td><td>0.977</td><td>0.988</td></tr><tr><td rowspan="3">D</td><td>1 × 4K</td><td>0.967</td><td>0.988</td><td rowspan="3">980,507</td><td rowspan="3"></td><td rowspan="3"></td></tr><tr><td>2 × 4K</td><td>0.993</td><td>0.998</td></tr><tr><td>1 × 8K</td><td>0.984</td><td>0.995</td></tr><tr><td rowspan="3">E</td><td>1 × 4K</td><td>0.817</td><td>0.913</td><td rowspan="3">1,132,956</td><td rowspan="3">25,033</td><td rowspan="3">13,924</td></tr><tr><td>2 × 4K</td><td>0.944</td><td>0.978</td></tr><tr><td>1 × 8K</td><td>0.865</td><td>0.949</td></tr><tr><td rowspan="3">F</td><td>1 × 4K</td><td>0.852</td><td>0.941</td><td rowspan="3">682,308</td><td rowspan="3">7,637</td><td rowspan="3">5,820</td></tr><tr><td>2 × 4K</td><td>0.937</td><td>0.977</td></tr><tr><td>1 × 8K</td><td>0.904</td><td>0.966</td></tr><tr><td rowspan="3">G</td><td>1 × 4K</td><td>0.815</td><td>0.935</td><td rowspan="3">672,005</td><td rowspan="3">19,780</td><td rowspan="3">16,123</td></tr><tr><td>2 × 4K</td><td>0.925</td><td>0.976</td></tr><tr><td>1 × 8K</td><td>0.892</td><td>0.958</td></tr><tr><td rowspan="3">H</td><td>1 × 4K</td><td>0.899</td><td>0.954</td><td rowspan="3">325,445</td><td rowspan="3">2,720</td><td rowspan="3">2,235</td></tr><tr><td>2 × 4K</td><td>0.953</td><td>0.976</td></tr><tr><td>1 × 8K</td><td>0.923</td><td>0.966</td></tr></tbody></table>

(Confidence intervals less than 0.01)
We will compare this policy with the new one that we consider now :

1 - the data within the cache which are modified by i/o channels are updated,

2 - the data outside the cache which are modified by the CPU (and not by the i/o channels (write accesses)) are loaded into the cache.

We give some interesting results we obtained in such conditions in figure 13. More details are presented concerning the i/o transfers of the programs E, F, G and H, since their percentages are higher than the others (see figures 2, section 3.1).

By comparing these results with the ones given in figures 10, we notice an increase of the hit ratios not negligible if we consider the speeding up of the target machine (see equation (4) and table in section 2.2).

## 5 - CONCLUSION

We have presented in this paper the performance improvement which can be expected by providing a mini-computer with a cache memory. The major criterion we have considered is the hit ratio from which we deduce a speeding up of the target machine. Our results show that in order to get satisfactory and stable performance a relatively large cache is needed, the size of which is of the order of 10K words. These results also show that when high performance is achieved, the improvements brought by implementing a prefetching mechanism or by increasing the number of segments are of the same order, but that in bad operating conditions a prefetching solution is always better. Therefore we may conclude that, in our case, we can easily triple the speed of the target machine with a reasonable trade-off.

In other respects, we carefully studied the behaviour of the program run on the machine and we showed the strong influence of the locality phenomenon on the performance.

## ACKNOWLEDGEMENTS

We would like to thank Ph. LEBLANC and M. LEGOUX who participated in this work. In other respects we are indebted to SEMS for having entrusted us with this study and made it possible by supporting it and by providing us with basic data. In this regard, we would like to thank MM. MICHEL, BASTIE, DE LAMOTTE, GAULENE, GAUDEY, from SEMS.

## REFERENCES

[1] LIPTAY J.S. - "Structural Aspects of the system/360 Model 85, II the Cache" - IBM Systems Journal, Vol. 7, n° 1, 1968.

[2] MEADE R.M. - "Design Approaches for Cache Memory Control" - Computer Design, Vol. 10, January 1971.

[3] KAPLAN K.R., WINDER R.O. - "Cache-based Computer Systems" - Computer, March 1973.

[4] SEMS - "MITRA 125 - Manuel de référence" - Brochures n° 4648 U1 FR and n° 4649 U1 FR edited by SEMS (Société Européenne de Mini-Informatique et de Systèmes), 1978.

[5] BELL C.G., CASASENT D. - "Implementation of a Buffer Memory in Mini-Computers" - Computer Design, Vol. 10, November 1971.

[6] BURGEVIN P., LEROUDIER J. - "Characteristics and Models of Program Behaviour" - National Conference ACM 76 - Houston (Texas) - October 1976.
[7] MATTSON R.L., GECSEI J., SLUTZ D.R., TRAIGER I.L. - "Evaluation techniques for storage hierarchies" - IBM System Journal n° 2, 1968.

[8] DENNING P.J. - "The Working Set Model for Program Behavior" - Communication of the ACM, Vol. 11, n° 5, May 1968.

[9] COX D.R., LEWIS P.A.W. - "The Statistical Analysis of Series of Events" - Methuen - 1966.

ANNEXE I

<figure><img src="image_24.png" /><figcaption>Program A</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>Program B</figcaption></figure>
<figure><img src="image_26.png" /></figure>

Program C

<figure><img src="image_27.png" /></figure>

Program D

<figure><img src="image_28.png" /></figure>

Program E
<figure><img src="image_29.png" /></figure>

Program F

<figure><img src="image_30.png" /></figure>

Program G
<figure><img src="image_31.png" /><figcaption>Program H</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>Program I</figcaption></figure>