# A statistical approach to the study of program behaviour via reference strings analysis

Anne Schroëder

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

## To cite this version:

Anne Schroëder. A statistical approach to the study of program behaviour via reference strings analysis. [Research Report] IRIA-RR-240, IRIA. 1977, pp.17. hal-04716459

HAL Id: hal-04716459

https://inria.hal.science/hal-04716459v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
Inv:03190 RR240

RIA
laboria

ARCHIVES

laboratoire de recherche
en informatique
et automatique

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

A STATISTICAL APPROACH
TO THE STUDY
OF PROGRAM BEHAVIOUR
VIA
REFERENCE STRINGS ANALYSIS

Anne SCHROEDER

Rapport de Recherche N° 240

Juin 1977

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20
A STATISTICAL APPROACH TO THE STUDY OF PROGRAM
BEHAVIOUR VIA REFERENCE STRINGS ANALYSIS

Anne Schroëder

IRIA/LABORIA

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

Résumé :

Les traces de références sont communément utilisées pour décrire le comportement dynamique
des programmes. Suivant le niveau de détail auquel on se place, il peut s'agir de suites d'adres-
es dans la mémoire virtuelle, de références aux pages, de traces symboliques, etc ...

Pour analyser de telles traces, nous proposons une approche basée sur les méthodes d'analyse
des données. Nous montrons comment des techniques multivariées telles que l'analyse des Cor-
respondances et la classification automatique peuvent être utilisées pour donner une définition
statistique de la notion de «localité». Cette définition est en accord avec les nombreuses carac-
térisations empiriques et intuitives qui en ont déjà été données.

L'approche présentée peut être utilisée pour l'analyse de traces de références à quelque niveau
de détail que ce soit. A titre d'exemple, nous présentons des expériences réalisées sur des traces
réelles de références aux pages.

Abstract :

Reference strings are widely used to describe the dynamic behaviour of programs. According to the level of detail of the description, these strings may be sequences of virtual memory addresses, of page references, of symbolic instructions, etc ...

We propose a statistical approach based on data analytic methods to analyse such strings. We show how multivariate statistical methods such as Correspondence Analysis and clustering techniques may be advantageously used for that purpose. A statistical notion of «locality» can then be derived, which is consistent with the various empirical definitions of locality given in the literature. This approach may be used for the description of reference strings at any level of details. As an example we present experiments on observed page reference strings.

* Ce papier a été accepté à l'International Symposium on Computer Performance, Modeling, Measurement and Evaluation organisé par le IFIP Working Group 7.3. à Yorktown Heights, N.Y. (U.S.A.) du 16 au 18 août 1977.
# 1. INTRODUCTION

The study of program behaviour is a capital step in the development of most research on operating systems. It is particularly essential when such techniques as analytical modelling and simulation are used for performance evaluation and prediction. The utilization of these tools requires that the system workloads are clearly characterized and quantified. This characterization may be done at various levels of detail : global statistics on the number and requirements of the users of a computer centre, classification of different kinds of jobs, or models for the sequence of addresses referenced by a job.

In this paper, we shall focus our attention on using this last type of information to find "localities" of references. The presence of localities is a most interesting feature in the behaviour of a program. It means that the execution time may be divided into distinct steps during which the program references mainly belong to some favoured set of addresses. The concept of locality of memory references is of great importance for the design of virtual memory systems, and it has been used explicitly in various memory management policies implemented in such systems. It has already been described by probabilistic models (hT 72, FrG 75]. A quantitative characterization of localities may be deduced from such models, like in [FrG 75].
Other characterizations which does not rely on a stochastic model have also been introduced : the notion of "working-set" [Den 68] and, more recently, the "activity sets" and "bounded locality intervals" (BLI) [MaB 76]. The working set model gives a simple and operational mean to exhibit local memory requirements of a program. The activity sets and BLI describe its behaviour at various levels of detail via hierarchies of nested localities ; though quite appealing this last approach seems too heavy for an on-line use.

Statistical analyses of reference strings have already been carried on but not directly in the purpose of locality detection. In [GaL 74, LeS 73] for instance, the aim was first to suggest a point process model for a process associated with the reference string (the sequence of page exceptions), and then to estimate and validate it. From an other point of view [Bry 75, BuL 76, Rod 73] give descriptive statistical results on the working-sets behaviour. In [Bry 75] the results are used to build a predictive model for the working-set sizes.

Our own approach is based on the idea that the phenomenon of locality is an objective property of each program which must be directly observed on its reference strings. We thus propose a characterization of localities which is deduced from descriptive analyses of reference strings. The statistical tools used are descriptive multivariate methods : Correspondence Analysis and a clustering algorithm.

In the next section of this paper, we shall present the reference strings, which we analyze and we shall illustrate experimentally the notion of locality. Then a formal definition of locality will be given in the 3rd section while the statistical tools we use to exhibit such localities will be presented in section 4. Finally, applications on real page references strings will be discussed in section 5.

## 2. MEASUREMENTS OF PROGRAMS BEHAVIOUR

### 2.1 - Reference strings

The dynamic behaviour of a program may be described by different strings :

- the string of addresses which is the sequence of all the virtual addresses referenced by the program during its execution. This string only depends on the program itself and its input data. It depends neither on the structure of the physical memory nor on the memory allocation strategy.

- the page string, easily deduced from the string of addresses as soon as the page size is given, is the sequence of page references.

- more generally, strings of blocks may be considered where "blocks" is used as a general name for any subset of addresses (modules, segments,...).

- the symbolic reference string describes the execution at the source language level [Bat 76].

In the following, we shall use the word "reference" in the most general meaning (address, page number, source language instruction, etc...).

### 2.2 - Notion of locality

Let $R$ be the space of references and $N$ its size. Then $R = \{r_1, r_2, ..., r_N\}$. The available observed information on $R$ is a reference string $S = \{s_1, ..., s_T, ..., s_T\}$ where $s_t$ is the $t$-th reference and $T$ is the number of observed references. In the following, the mean time between two successive references will be taken as the time unit. Hence, the indices $\{1, ..., T\}$ represent a time scale.
Figure 1 illustrates the page reference string of a LISP interpreter executing one program and Figure 2 that of a FORTRAN compiler compiling two different modules (for further details on the collection and representation of such strings, see BuL 76). On the horizontal axis is plotted the page set $R$, the vertical axis is a time axis in the following sense: Each line represents a working-set of window-size equal to 5000 references, by the mean of a "I" for pages in the working-set and a blank for the others. The time is running from top to bottom. The sampling of these workings-sets is detailed in §3.1.

These graphs obviously show phases in the execution of the programs, which are associated with different localities. Moreover a more careful observation reveals that there is not one definite locality structure. It would be better to talk of different levels of localities. For instance, in Figure 1, four main phases appear (the 2nd and the 4th one corresponding to the same locality), but, when going into further details several other subphases can be noticed.

These indications are the kind of observation we shall try to obtain automatically. For this purpose, we shall define on $R$ as well as on $\{1, 2, ..., T\}$ two structures describing those kinds of phases: determined subsets of references which the program addresses during determined time intervals.

### 3. A TIME x REFERENCE REPRESENTATION OF LOCALITIES

#### 3.1 - The data

The basic information we shall use from now on to describe localities will consists in occurrence tables between the set $R$ of references and the set of instants $[1, ..., T]$. Since the execution of any program may consist in several millions references, it is essential to sample them in order to extract a manageable information. A point sampling would not be appropriate since we are interested in analyzing a neighbourhood behaviour. We shall therefore have to

sample intervals. We chose here the simplest interval sampling procedure, though more sophisticated procedures could also be adapted. The observed periods are intervals of equal size $s$ (or "windows") sampled every $t_0$ units of time; they will be denoted by:

<figure><img src="image_5.png" /><figcaption>Figure 1</figcaption></figure>

$$I_1 = [t_0, t_0 + s], I_2 = [2t_0, 2t_0 + s], I_M = [Mt_0, Mt_0 + s]$$

where $M = \max\{m \in N | mt_0 + s \le T\}$.

It is easy to note that this sampling process consists in sampling working-sets of window size $s$ every $t_0$ references. This is important from a practical standpoint in order to get indications on the parameters $t_0$ and $s$ (see §5.1). Moreover, the practical use that has already been made of working-sets legitimates the sampling strategy.

Let $I$ be the set $\{I_1, I_2, ..., I_M\}$. In the sequel of the paper, the analysis will be conducted on the contingency table $C$ between $R$ and $I$. $C$ is defined by:
$$C(I_i, r_j) = a_{ij} = \begin{cases} 1 & \text{if } r_j \text{ has been referenced during } I_i \\ 0 & \text{otherwise} \end{cases}$$

So, the i-th row of C is nothing else than the characteristic function of the i-th "working-set" WS_i of window size s :

$$V i \in \{1, 2, \dots, M\} \quad WS_i = \{r_j/1 \le j \le N \text{ and } a_{ij} = 1\}$$

Let us use the following notation :

$$V i \in \{1, 2, \dots, M\} \quad a_{i*} = \sum_{j=1, N} a_{ij}$$

$$V j \in \{1, 2, \dots, M\} \quad a_{j*} = \sum_{i=1, M} a_{ij}$$

and
$$a_{**} = \sum_{i=1, M} \sum_{j=1, N} a_{ij}$$

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

Thus $a_{i*}$ is the i-th working-set size, $a_{j*}$ the number of working-sets which contain $r_j$ and $a_{**} = M \cdot \overline{WS}$, where $\overline{WS}$ is the mean working-set size.

## 3.2 - The multidimensional approach

Once the data on the relationships between the set $R$ of references and the set $I$ have been collected, we propose to analyse them by using multidimensional statistical techniques. In these techniques the two sets $R$ and $I$ are considered as finite sets of vectors in spaces of respective dimensions $M$ and $N$. For instance, the page $r_j$ is identified with the vector $(a_{1j}, a_{2j}, \dots, a_{Mj})$ which is the j-th column of the table C and thus completely describes how $r_j$ is used throughout the sampled time intervals. Symmetrically, each sample window is represented by the corresponding line of C which is the characteristic function of its working-set. Multidimensional techniques attempt by different means to provide a clear description of such sets of objects placed in multidimensional spaces. In order to do that, these spaces are assigned a measure of distance and the problem of description can then be stated in geometrical teams.

For our purpose of locality detection, we shall use two of those techniques :
* Correspondence Analysis and a clustering procedure. They provide different forms of description of the data which prove to be complementary. They will be described more precisely in the following section 4. For both techniques, given distances $d_1$ and $d_2$ have to be taken for the two sets $I$ and $R$. Correspondence analysis also
requires weights to be assigned to the sets. We shall now see more precisely which are those distances and weights.

i) Weights and distance on the set $I$ :

Each sampled time interval or "window" $I_i$ is weighted by the number of distinct references that have been accessed during its duration, i.e. by its working-set size $a_{i*}$.

The distance between the $k^{th}$ and the $l^{th}$ windows is given by :

$$d_1^2(I_k, I_l) = M \overline{WS} \sum_{j=1, M} \frac{1}{a_{i*}^j} \left[ \frac{a_{kj}}{a_{k*}} - \frac{a_{lj}}{a_{l*}} \right]^2$$

Let us recall that :

$$\frac{a_{ij}}{a_{i*}} = \begin{cases} 1/a_{i*} & \text{if } r_j \text{ belongs to the } i^{\text{th}} \text{ working set} \\ 0 & \text{Otherwise} \end{cases}$$

It is easy to see that two time intervals are represented by a unique point in $I$ if and only if they have identical working sets :

$$d_1^2(I_k, I_l) = 0 \Leftrightarrow \{j/a_{kj} \neq 0\} = \{j/a_{lj} \neq 0\}$$

Moreover, when the working-sets are different, $I_k$ and $I_l$ are considered the closer their non common references are more frequently referenced. This is due to the terms $1/a_{i*}^j$ appearing in the sum defining this distance which is imposed by the use of Correspondence Analysis.

ii) Weights and distance on $R$ :

Each reference $r_j$ is weighted by the number $a_{i*}^j$ of sampled working-sets which contain it. The distance between two references $r_k$ and $r_l$ is given by :

$$d_2^2(r_k, r_l) = M \overline{WS} \sum_{i=1, N} \frac{1}{a_{i*}^j} \left[ \frac{a_{ik}}{a_{k*}} - \frac{a_{il}}{a_{l*}} \right]^2$$

As seen above in the case of the time intervals, we have :

$$V_i, \quad 1 \le i \le M \qquad \frac{a_{ij}}{a_{i*}} = \begin{cases} 1/a_{i*} & \text{if } r_j \text{ belongs to the } i^{\text{th}} \text{ working set} \\ 0 & \text{Otherwise} \end{cases}$$

$$V_j, \quad 1 \le j \le N$$

Two references are considered as identical when they occur in the same working-sets. They are closer or further away from each other according to whether the working-sets in which only one of them occurs are larger or smaller.

Finally, we see that the notions of "Importance" and of "Closeness" for references and for time intervals that will be introduced by the statistical techniques reflect well enough the empirical definition of "localities" of references.
# 4. THE STATISTICAL TOOLS

## 4.1 - Correspondence Analysis

Due to J.P. Benzecri [Ben 69, Ben 73], this multivariate statistical method is derived from Fisher's Canonical Analysis of contingency tables and is closely related to other multivariate statistical techniques, such as Principal Components and Canonical Analysis [And 58, Hil 74, Sch 76].

As seen in the previous paragraph the two sets *I* and *R* to analyse may be considered as sets of vectors in a N-dimension and in a M-dimension spaces. The aim of Correspondence Analysis is to give the best possible representation of such a multidimensional set in a space of low dimension (in a plane, for instance, in order to get the structure of the set directly legible). The problem of finding that subspace on which the data set can be projected with a minimal loss of information is solved by using mechanical arguments : it is the principal inertia subspace of the data set. The quality of the representation obtained is measured by the ratio :

dispersion of the projected set
total dispersion of the data set

This ratio indicates the part of information which is preserved after the projection. The dispersions involved in the ratio are dispersions in the sense of the distance chosen for the analysed set (here $d_1$ for *I* and $d_2$ for *R*).

Thus, Correspondence Analysis provides a low-dimension representation for the two sets *I* and *R* and a measure of the quality of these representations. Moreover, the theoretical properties of the method ensure that the two representations of *I* and *R* can be interpreted simultaneously with the help of each other. The use and the interpretation of the graphical representations provided by such an analysis will appear more clearly in section 5 in which applications are presented.

Let us note that the choice of the particular distances $d_1$ and $d_2$ is characteristic of Correspondence Analysis and that it is this choice which allows the simultaneous interpretation of the two representations. With any other distances, good representations of each set could be obtained by a Principal Components Analysis, but there would not be any results allowing to compare the two representations. These distances also have a property, called by J.P. Benzecri, "distributional equivalence" which will be illustrated in §5.1.

## 4.2 - A clustering procedure

Given a finite set of vectors on which a distance measure is chosen, clustering techniques find out a partition of this set which is optimum for some quality criterion. Those techniques differ from one to another by their criterion and the algorithm they use to get an optimum (or, most generally, a local optimum) of the criterion.

The method we use here is due to G. Govaert [Gov 76]. It is a particular case of the large family of clustering techniques known as Dynamic Clusters type methods [DiS 74]. It requires that the number *k* of classes required in the partition is given and considers the weights and distances introduced in 3.2. The two sets *I* and *R* are analysed separately by this method. Since they play symmetrical parts, we shall only detail the analysis of *I*. The analysis of *I* provides a partition ($I_1, I_2, ..., I_k$) of *I*.
Notation :

$$
\left.
\begin{array}{l}
\forall \ell = 1, k \\[1em]
\forall j = 1, N
\end{array}
\right\}
\quad
b_{\ell j} = \sum_{\{i/I_i \in I_{\ell}\}} a_{i j}
$$

and

$$
b_{\ell*} = \sum_{\{i/I_i \in I_{\ell}\}} a_{i*}
$$

So $C' = [b_{\ell j}]_{\ell=1, \dots, k}^{j=1, \dots, N}$ is the contingency table deduced from $C$ by partitioning $I$
into $(I_1, \dots, I_k)$ and $b_{\ell*}$ is the total weight of the class $I_\ell$.

The partition obtained maximizes the following criterion :

$$
K^2 = \sum_{\ell=1,k} b_{\ell*} \sum_{j=1,N} \frac{1}{a_{*j}} \left[ \frac{b_{\ell j}}{b_{\ell*}} - a_{*j} \right]^2
$$

This criterion expresses the strength of the correlation between the set *I* divided
into the *k* classes (*I*₁, ..., *I*ₖ) and the set *R*. (Under classical hypotheses, this
quantity is proved to be distributed as a χ² variable and is commonly used as a
test of homogeneity in contingency tables).

5. APPLICATIONS

The statistical methods have been applied to various examples.

The data were collected at the University of Rennes (France) by interpreting the
execution of programs running on a CII 10070 Computer. The traces obtained are the
address strings of the observed programs, i.e. the sequence of all addresses refe-
renced during the execution. These references may be identified as instruction or
data references. Further detail on these reference strings may be found in [Bul 76].

5.1 - Analysis of the FORTRAN compiler

The first string we have chosen to analyse because of its typical local behaviour,
is that of a FORTRAN compiler of 30K words compiling two different modules and
containing 3 207 168 references (≈ 3 seconds). It has first been converted in two
page reference strings assuming respectively the page size to be 512 or 256 words.
Thus, in the sequel, the set R of references will be either R₁ (page size =
512 words) or R₂ (page size = 256 words). The corresponding traces are presented
in Figures 2 and 3.
<figure><img src="image_7.png" /><figcaption>Figure 2</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 3</figcaption></figure>

From $R_1$ we have also deduced two other page reference strings : $R_{1i}$ and $R_{1d}$ by
making a distinction between instruction references ($R_{1i}$) and data references
($R_{1d}$). This will permit to compare the specific behaviour of data and instructions
references with the global one.

The next step is to sample time intervals. This sampling, as seen in 3.1 depends
on two parameters : the size s of the intervals (window size) and the sampling
period $t_0$. Guided by the experience of authors who have analysed working-set pro-
perties [BuL 76] or implemented working-set memory management [Rod 73], we made
experiments with the following values for those parameters.

$s = 2\,000, 5\,000$ or $10\,000$ references
$t_0 = 10\,000$ or $50\,000$ references.

The value $s = 5\,000$ and $t_0 = 50\,000$ have been finally kept since they give the best
results with the fewest number of references to deal with. However, it should be
noted that the choice of these values may depend on the program to analyse and a
first investigation of the data must be made to get an idea of the "size" of possi-
ble localities.

i) Correspondence Analysis

Four analyses have been performed : analyses of the Table C between *I* and the sets
$R_1, R_2, R_{1i}$ and $R_{1d}$.

We shall first present the detailed results of the analysis of C between *I* and $R_1$
which appeared to be the most informative of the four performed analyses. Then,
the other ones will be more briefly described and compared to this one and to one
another.

- Analysis of $I \times R_1$ :

This analysis provides plane representations for *I* and $R_1$ which bring 36 % of the
global information contained in the Table C. The representation of *I* is shown in
Figure 4.
<figure><img src="image_9.png" /><figcaption>Figure 4</figcaption></figure>

Four clusters appear, indicated by numbers 1, 2, 3 and 4 in Figure. Group 1 contains two phases in the execution of the program (from the 1st to the 18th sampled windows and from the 31st to the 49th). In the same way, the three other obvious phases of the execution seen in Figure 2 are represented here in the groups 2, 3 and 4.

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

Simultaneously, we can see on the representation of $R_1$ (Figure 5) which pages characterize those phases. Around the centre of gravity are clustered the most frequently referenced pages : they are accessed during all the execution and cannot characterize a particular phase. The others are clustered according to a pattern similar to the one displayed in that of the time interval of Figure 4 (groups A, B, C and D on Figure 5).
The 1st and 5th phases in the execution time are both characterized by references to the pages represented in Group A on Figure 5, and so on for the other groups. Several isolated points represent pages which are shared by different phases.

By taking one more dimension into account, we can add 10 % of information. This gain is not important compared with the 36 % of information brought by the two first dimensions. We shall however examine it to see whether it contains relevant information or not. The plane representation of *I* on the 1st and 3rd axes is shown on Figure 6. One can note that if the groups 2, 3 and 4 of Figure 4 are still the same, the group 1 is split into subgroups. One of the two subgroups is very close to group 4. By observing the representation of *R*₁ on these same axes (not reproduced here), we can see that the two subgroups of group 1 are characterized by the use they make of pages 18, 19, 21, 22, 64, 65, 67, 69 on one hand and of pages 8, 15, 27, 28, 71 on the other.

<figure><img src="image_11.png" /><figcaption>Figure 6</figcaption></figure>

- Analyses of $I \times R_{1i}$ and $I \times R_{1d}$:

There are 54 pages containing data references and only 14 containing instructions references. Both representations of *I* and $R_{1d}$ are very close to the representations issued from $I \times R_1$. This is certainly due to the fact that pages references are most often data references as noted just above. The interesting point is that the similarity is still true in the results of $I \times R_{1i}$. This observation may indicate that the detected phases are phases in the instructions sequence of the program which, of course, imply phases in the data references.

- Analyses of $I \times R_2$:

The sampling process is still the same as above, but the page size is 256 words i.e. half of that for $R_1$. The representation of *I* is almost the same as in the analysis of $I \times R_1$. This means that the phases are the same when observing the behaviour of the program at these two different levels of detail. This conclusion is confirmed by observing the traces in Figures 2 and 3. This illustrates the stability of the results of the analyses when aggregating (or disaggregating) classes
of elements that are close to one another. It is due to the property of "distribu-
tional equivalence" that we have mentioned in §4.1. (This property is the
following : if two elements in one of the two sets we analyse, let us say $r_1$ and
$r_2$ in $R$, are at a null distance from each other, they can be replaced by a unique
point, weighted by the sum of their weights : $a_{*j_1} + a_{*j_2}$, without changing any-
thing to the distances $d_1$ between the elements of $I$).

ii) Clustering

The clustering procedure has been applied to the set *I* of the working-sets corres-
ponding to *R*₁. Since the results obtained coincide exactly with those of Corres-
pondence Analysis it has not been necessary to cluster the set of references : the
characteristic references of the observed phases have already been obtained.

Three experiments have been made asking respectively for three, four or five
classes in the partition.

Partition obtained with three classes :

$I_1 = \{I_1 \text{ to } I_{18} \text{ and } I_{29} \text{ to } I_{65}\} : \text{groups 1 and 4 of Figure 4}$

$I_2 = \{I_{19} \text{ to } I_{24} \text{ and } I_{50} \text{ to } I_{58}\} : \text{group 2 of Figure 4}$

$I_3 = \{I_{25} \text{ to } I_{28} \text{ and } I_{59} \text{ to } I_{62}\} : \text{group 3 of Figure 3}$

In the partition obtained with four classes, *I*₂ and *I*₃ remain the same and *I*₁ is
split into the two subclasses which have been found in the 2nd plane given by
Correspondence Analysis (Figure 6). When asking for five classes, it is the small
group 4 of Correspondence Analysis which is separated from the subclass of group 1
to which it was so close.

NB : The quality criterion of the partitions obtained is of course increasing with the number of classes required : it has to be maximum when there are as many classes as elements in the set. When making several experiments with different number of classes, it is important to examine whether asking for one more class significantly improves the criterion or not. If it does not it means that the lowest number of classes is a "good" one, in the sense that clustering cannot be improved by adding a new class.

In this particular application, the criterion increases noticeably and regularly
when passing from three classes to four, and from four to five. So, all successive
partitions bring worthwhile information.

The clustering method and the Correspondence Analysis exhibit the same locality
structure for the FORTRAN compiler under study. Since the structure was a very
pronounced feature, it could have been unambiguously deduced from Correspondence
Analysis graphs. However, these graphs are not always so easy to interpret because
of poor representation in a low dimension space or of overlapping classes. In these
cases, clustering is the method which is able to display relevant classes. Moreover,
results provided by Correspondence Analysis have a more attractive form than those
of any clustering algorithms, but from a computational standpoint a Correspondence
Analysis is more expensive than the clustering method used here.

5.2 - Analysis of the LISP interpreter

The LISP interpreter requires 14K words of core and interprets a whole user LISP
program. Its reference string contains 3 663 872 references (≈ 3.7 seconds). We
analysed its page reference string (Figure 1) with a page size of 512 words. Let $R$ be the set of these pages. The values of the sampling parameters (see 3.1) are : $s = 5 000$ and $t_0 = 20 000$. They have been selected after some experiments as in 5.1.

### i) Correspondence Analysis

A first analysis has been performed on $I \times R$. It has not been of great interest since the only feature it could point out is the fact that the two first sampled working-sets are completely apart from all the others : on the representations, all the other working-sets are gathered on a single point. When looking at the trace (Figure 1), it appears that these two working-sets $I_1$ and $I_2$ belong to an initialization phase in which the program will never return.

We then analysed $(I - \{I_1, I_2\})$. The parts of information brought by the successive dimensions are :

<table><tr><td>1st dimension</td><td>: 33 %</td></tr><tr><td>2nd "</td><td>: 17 %</td></tr><tr><td>3rd "</td><td>: 10 %</td></tr><tr><td>4th "</td><td>: 7 %, etc...</td></tr></table>

On the plane of the two first dimension (global information : 50 %) the working-sets are represented on Figure 7 and the pages on Figure 8. The 1st dimension (horizontal axis) separates the working-sets $I_{67}$ to $I_{126}$ and $I_{146}$ to $I_{180}$ (except $I_{86}$, $I_{97}$, $I_{115}$, $I_{177}$) from all the others. We can see on Figure 1 that those working-sets obviously constitute one locality which is held during two long phases (the 4 exceptions appear like outliers). The 2nd dimension (vertical axis) puts apart the phase containing $I_{127}$ to $I_{144}$ though a subphase $I_{138}$ to $I_{144}$ can be distinguished. These phase and subphase are also noticeable on Figure 1. Eventually, on this first plane, remains the first phase of the execution ($I_3$ to $I_{65}$ with some exceptions).

<figure><img src="image_12.png" /><figcaption>Figure 7</figcaption></figure>
The characteristic references of these classes of working-sets are easy to read on Figure 8.

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

When observing the third dimension (not represented here) the only new feature is a partition of the 1st phase into two classes : $I_{25}$ to $I_{29}$ and $I_{52}$ to $I_{60}$ on one hand, the rest on the other. Once more these subphase may be seen on Figure 1.

Using three dimensions, which represent 60 % of the information, it has been possible to detect the major phases in the execution of the program, while all the certain points on the resulting graphs are the small localities which are seen as isolated working-sets on Figure 1. ($I_{10}$, $I_{15}$, $I_{30}$, etc...).

## ii) Clustering

Five experiments have been made asking respectively for three, four, five, six and seven classes. The criteria obtained at the four last experiments were almost equal to the value obtained with three classes. This means (see §5.1.ii)) that there is a robust structure of three classes in the set $I - \{I_1, I_2\}$ to analyse and that the gain obtained by partitioning it into more classes is negligible.

We found two different partitions into three classes which have equal quality criteria. Both of them exhibit the three main phases : $I_3$ to $I_{65}$, $I_{127}$ to $I_{137}$ and ($I_{66}$ to $I_{126}$ + $I_{145}$ to $I_{182}$), with the same outliers as those noticed in Correspondence Analysis. The only difference is in the assignment of the subphase $I_{138}$ to $I_{144}$ which is classified either with $I_3 - I_{65}$ or with $I_{127} - I_{137}$. This intermediate position was already noticed on Figure 7.

# 6. CONCLUDING REMARKS

We have presented in this paper an attempt to characterize localities by a descriptive analysis of the reference string of a program. The major benefit of this approach is its objectivity, since no underlying model for the locality structure has to be assumed. It must also be noticed that the description obtained is a
detailed one. It is able to display different levels of nested localities, and this
description is derived by only observing a limited subset of the string (from 10
to 20 percent of the total number of references).

A first application of our approach is to provide convenient tools for on-line de-
tection of localities. We have seen how sampled working-sets of a program may be
considered as N-vectors, how they can be compared to one another by using the
distance defined in §3.2, and how a locality may be defined as a cluster of those
vectors. Thus, a new sampled working-set may be identified as belonging to one of
the detected localities by measuring its distance to the different clusters repre-
senting those localities and being assigned to the locality the closest to which it
is. The only hypotheses needed to make such a prediction valid is that the phases
of a program are the same from one execution to another ; no assumption has to be
made concerning the lengths and orders of the phases. Such on-line methods which
identify in which locality a program is running may be used to design adaptive
memory management policies using predictive loading techniques such as those
presented in [BaS 76].

The description of localities of references we have presented can also be applied
to program restructuring : the known restructuring techniques [Fer 75, MaS 74,
AcB 76] are clustering methods applied to connection tables between logical blocks
of the program. Our method could either improve those blocks definition or suggest
restructuring procedures directly built on our obtained pages clusters.

It should also be noted that the approach we have presented here can be extended
to the characterization of localities at other levels of the program behaviour,
such as file access sequences or transaction initiations in a data base system.
From a technical point of view, sampling and analysis tools have still to be
studied and refined.

## ACKNOWLEDGEMENTS

Special thanks are due to Dominique POTIER, Domenico FERRARI and one of the
referees for their helpful criticisms and comments.
detailed one. It is able to display different levels of nested localities, and this description is derived by only observing a limited subset of the string (from 10 to 20 percent of the total number of references).

A first application of our approach is to provide convenient tools for on-line detection of localities. We have seen how sampled working-sets of a program may be considered as N-vectors, how they can be compared to one another by using the distance defined in §3.2, and how a locality may be defined as a cluster of those vectors. Thus, a new sampled working-set may be identified as belonging to one of the detected localities by measuring its distance to the different clusters representing those localities and being assigned to the locality the closest to which it is. The only hypotheses needed to make such a prediction valid is that the phases of a program are the same from one execution to another ; no assumption has to be made concerning the lengths and orders of the phases. Such on-line methods which identify in which locality a program is running may be used to design adaptive memory management policies using predictive loading techniques such as those presented in [BaS 76].

The description of localities of references we have presented can also be applied to program restructuring : the known restructuring techniques [Fer 75, MaS 74, AcB 76] are clustering methods applied to connection tables between logical blocks of the program. Our method could either improve those blocks definition or suggest restructuring procedures directly built on our obtained pages clusters.

It should also be noted that the approach we have presented here can be extended to the characterization of localities at other levels of the program behaviour, such as file access sequences or transaction initiations in a data base system. From a technical point of view, sampling and analysis tools have still to be studied and refined.

## ACKNOWLEDGEMENTS

Special thanks are due to Dominique POTIER, Domenico FERRARI and one of the referees for their helpful criticisms and comments.
REFERENCES

[AcB 76] M.S. Achard, J.Y. Babonneau, G. Morisset - "Adaptation automatique des programmes au milieu paginé" - Research Report n° 196, IRIA-LABORIA - Octobre 1976 - (an English version of this paper will be presented at the 6th ACM Symposium on Operating Systems principles to be held at Purdue University - November 1977 - with the following title : "Automatic and general solution to the adaptation in the paging environment").

[And 58] T.W. Anderson - "Introduction to multivariate statistical analysis" - John Wiley - 1958.

[BaS 76] J.L. Baer, G.R. Sager - "Dynamic improvement of locality in virtual memory systems" - IEEE Trans. on Software Engineering - Vol. SE-2 - n° 1 - pp. 54-62 - March 1976.

[Bat 76] A. Batson - "Program behavior at the symbolic level" - Computer - Vol. 9 - n° 11 - pp. 21-28 - November 1976.

[Ben 69] J.P. Benzecri - "Statistical analysis as a tool to make patterns emerge from data" - in Methodologies of Pattern Recognition (S. Watanabe, ed.) - pp. 35-60 - Academie Press N.Y. - 1969.

[Ben 73] J.P. Benzecri et Coll. - "L'analyse des données T.1 : La taxinomie, T.2 : L'analyse des Correspondances" - Dunod - Paris - 1973.

[BuL 76] P. Burgevin, J. Leroudier - "Characteristics and models of program behavior" - National Conference ACM 76 - Houston - Texas - October 1976.

[Den 68] P. Denning - "The working-set model for program behavior" - Communications of the ACM - Vol. 11 - pp. 323-333 - May 1968.

[DiS 74] E. Diday, A. Schroeder, Y. Ok - "The dynamic clusters method in pattern recognition" - Information Processing 74 - IFIP - Stockholm - North-Holland Publishing C. - pp. 691-697 - 1974.

[Fer 75] D. Ferrari - "Tailoring programs to models of program behavior" - IBM J. Res. Develop. - pp. 244-251 - May 1975.

[FrG 75] W.F. Freiberger, U. Grenander, P.D. Sampson - "Pattern in program references" - IBM J. Res. Develop. - pp. 230-243 - May 1975.

[GaL 74] D.P. Gaver, P.A.W. Lewis, G.S. Shedler - "Analysis of exception data in a staging hierarchies" - IBM J. Res. Develop. - Vol. 18, n° 5 - pp. 423-434 - September 1974.

[Gov 77] G. Govaert - "Algorithme de classification d'un tableau de contingence" - Journées Analyse des Données et Informatique - IRIA - Rocquencourt - France - Septembre 1977.

[Hil 74] M.O. Hill - "Correspondence analysis : a neglected multivariate method" - Appl. Statist. - 23 - n° 3 - pp. 340-354 - 1974.

[LeS 73] P.A.W. Lewis, G.S. Shedler - "Empirically derived micro models for sequences of page exceptions" - IBM J. Res. Develop. - pp. 86-100 - March 1973.

[MaB 76] A.W. Madison, A.P. Batson - "Characteristics of program localities" - Communications of the ACM - Vol. 19 - n° 5 - pp. 285-294 - May 1974.
[MaS 74] T. Masuda, J. Shiota, K. Noguhi, T. Ohki - "Optimization of program organization by cluster analysis" - IFIP 1974 - Stockholm - North-Holland Publishing C. - 1974.

[Rod 73] J. Rodriguez-Rosell - "Empirical working-set behavior" - Communications of the ACM - Vol. 16 - n° 9 - pp. 556-560 - September 1973.

[Sch 76] A. Schroeder - "Descriptive methods in multidimensional data analysis" - IFIP Workshop on Decision Making and Medical Care (Dombal and Grémy, eds) - North-Holland Publishing C. - 1976.

[ShT 72] G.S. Shedler, C. Tung - "Locality in page reference strings" - SIAM J. Comp. - Vol. 1 - n° 3 - pp. 218-241 - September 1972.