# Quelques aspects de la modélisation par simulation à événements discrets

Jacques Leroudier, Michel Parent

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

To cite this version:

Jacques Leroudier, Michel Parent. Quelques aspects de la modélisation par simulation à événements discrets. [Rapport de recherche] IRIA-RR-098, IRIA. 1975, pp.30. hal-04716105

HAL Id: hal-04716105

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

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
IRIA
laboria

laboratoire de recherche
en informatique
et automatique

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

Quelques aspects
de la modélisation
par simulation
à évènements discrets

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

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n·98

Février 1975.
# *Quelques aspects de la modélisation des systèmes informatiques*
## *par simulation à événements discrets*

Jacques LEROUDIER, Michel PARENT

IRIA - LABORIA

## 1 - INTRODUCTION

La modélisation des systèmes informatiques s'est très rapidement développée au cours de ces dernières années. Ceci peut s'expliquer par le fait qu'une fois les problèmes de faisabilité résolus et la construction d'importants systèmes informatiques réalisée, on s'aperçut qu'il était difficile d'utiliser pleinement et efficacement toutes les possibilités de ces systèmes. Comme il devenait de plus en plus délicat de faire des expériences et des essais directement avec le système, vu sa complexité et son coût, la modélisation devint l'outil standard pour appréhender la réalité. Bien plus, cet outil est l'un des seuls (hormis l'intuition) que puisse utiliser un concepteur de système qui doit choisir entre plusieurs options toutes aussi inaccessibles à l'expérimentation du fait de contraintes de coût et de temps.

Parmi les modèles utilisés pour l'évaluation des performances des systèmes ou sous-systèmes informatiques, on distingue habituellement les modèles mathématiques et les modèles de simulation, essayons de déterminer leurs champs d'application respectifs. Dans la modélisation, des problèmes de complexité croissante se présentent. On trouve :

- les problèmes que l'on sait formaliser et résoudre analytiquement,

- les problèmes que l'on sait formaliser mais que l'on ne sait pas résoudre,

- et finalement les problèmes que l'on ne sait même pas formaliser, mais dont on est capable de décrire un mécanisme de fonctionnement.

Si la simulation permet d'appréhender ces trois domaines de problèmes, la modélisation mathématique limite sa portée aux deux premiers (dans le second cas nous trouverons essentiellement des méthodes numériques approchées). On perçoit donc les rôles respectifs des modélisation mathématique et par simulation. Dans le premier cas ces deux approches se valideront mutuellement, dans le second cas nous pourrons faire des calculs de précision d'une méthode par rapport à l'autre, le troisième cas demeurant l'apanage de la simulation.

<figure><img src="image_5.png" /></figure>
Les modélisations mathématique et par simulation ont été largement uti-
lisées pour étudier les différents aspects des systèmes informatiques : architec-
tures de machine, systèmes d'exploitation, réseaux d'ordinateurs, bases de don-
nées, etc ... Dans cet exposé, nous nous limiterons à l'étude de la modélisation
par simulation à événements discrets.

Cette dernière approche semble bien acceptée par les informaticiens,
peut-être parce qu'ils ne sont pas encore bien familiarisés avec les modèles ma-
thématiques, mais aussi grâce aux qualités propres aux modèles de simulation :

- analogie complète avec la réalité où l'espace d'état est aussi discret,

- possibilité de détail très fin,

- extension possible de modèles mathématiques en s'affranchissant d'hypo-
thèses telles que temps de service exponentiels, arrivées Poisson-
niennes, etc... (on parle alors de résolution du modèle par une méthode
de Monte-Carlo).

Après une brève présentation de la simulation par événements discrets,
nous nous intéresserons aux aspects suivants :

- langages de programmation,

- mesures et analyses statistiques,

et nous dirons quelques mots de l'étalonnage et de la validation d'un modèle,
deux sujets qui, malheureusement, sont trop souvent oubliés.
**Principe** : L'espace d'états du système considéré est fini ou dénombrable et chaque changement d'état, ou **événement**, se produit d'une manière discrète dans le temps aux instants $(t_i)_i \in \mathbb{N}$. Ces instants de changements d'état sont appelés **occurences d'événements**.

Cette discrétisation est liée à la nature du problème posé et non à sa technique de résolution : il n'éagit pas d'une approximation d'un phénomène continu, comme dans le cas de simulations continues, mais d'une représentation de la réalité qui est, par exemple, celle des systèmes informatiques.

**Mise en oeuvre** : Les événements arrivant d'une manière discrète, ils peuvent être ordonnancés dans le temps (ordre chronologique) et donc simulés sur une machine séquentielle l'un après l'autre. Le parallélisme, qui peut apparaître à l'utilisateur au niveau du fonctionnement logique du système, n'existe pas, en fait, au niveau des changements d'état. On parle de pseudo-parallélisme.

Nous supposerons que tous les changements d'état sont bien définis, même lorsqu'ils résultent d'événements composés qui se produisent au même instant. Ce problème se présente lorsque plusieurs processus peuvent modifier simultanément un même élément du système (sémaphore, emplacement de mémoire, bascule, etc...). On définit alors des priorités permettant un ordonnancement implicite ou explicite de chacun des événements (pour plus de détails voir [Par 74.a]).

En général, dans une simulation à événements discrets, l'état du système peut être représenté par des **entités** et les **activités** qui les concernent. Ces entités peuvent avoir un ou plusieurs **attributs** qui sont modifiés par les activités. Par exemple, dans un système à temps partagé, les **entités** peuvent être les utilisateurs (ou programmes), les **activités**, la réflexion devant un terminal, l'utilisation de l'unité centrale ou d'un périphérique, l'attente dans une file d'attente, etc..., et les **attributs**, le nombre de pages en mémoire, le temps d'unité centrale nécessaire, les caractéristiques des programmes, etc...

A partir de là, il existe deux manières de regarder une simulation : soit ne s'intéresser qu'aux entités et enregistrer chaque changement des **attributs** d'une entité lorsqu'elle passe d'une activité à une autre, on parle alors d'une **simulation par processus**, soit ne s'intéresser qu'aux **activités** et garder un his-
torique des traitements qu'elles effectuent sur les entités, dans ce dernier cas,
on parle d'une *simulation par événements* [Gor 69].

Deux méthodes sont utilisées pour faire progresser le temps dans une
simulation à événements discrets :

a - *Simulation dirigée par événements.*

Les seuls temps accessibles lors de la simulation sont des dates d'événements et l'incrémentation du temps se fait d'une date d'événement à l'autre.
Il y a plusieurs manières de réaliser cette méthode.

On peut avoir une liste d'événements où la tête de liste est l'événement courant (présent) et la fin de la liste l'événement le plus éloigné dans le futur.
Il faut remarquer, qu'à part l'événement courant, les autres événements sont purement *potentiels* car leurs apparitions peuvent être remises en cause lors du traitement des événements qui les précédent. Cette solution est celle adoptée par SIMULA 67 [Dah 68, Bir 69, voir aussi Vau 75].

Une autre mise en oeuvre consiste à chaîner les événements en anneau
et à avoir une horloge centrale. Une fois l'événement courant traité, on explore
l'anneau pour trouver l'événement suivant dans le temps. On fait alors progresser
l'horloge jusqu'à la date d'apparition de cet événement et on le traite. Cette
solution est celle de GPSS [IBM 67].

Ces deux solutions entretiennent un *échéancier*, dans un cas celui-ci
est ordonné, dans l'autre non.

Il faut noter que lorsque deux événements sont simultanés (événements
devant arriver au même instant), leur ordre d'apparition va dépendre de la manière
dont l'échéancier est mis à jour ou balayé. En fait dans la plupart des langages
de simulation, il existe des ordres spéciaux (tels que BEFORE, AFTER et PRIOR en
SIMULA 67) permettant de réaliser l'ordonnancement souhaité.

b - *Simulation dirigée par une horloge.*

On définit une unité de temps appropriée au problème et on dispose
d'une horloge centrale qui progresse par pas d'une unité de temps. A chaque incré-
mentation de l'horloge, on explore la liste des événements pour voir si l'un d'eux
apparaît à cette date [Pee 74].

Cette incrémentation régulière du temps est à rapprocher de celle pra-
tiquée dans les simulations continues [FOR 68, PUG 73].
## 3.1. Les langages universels.

Nous avons vu qu'une simulation à événements discrets était en fait un processus séquentiel, donc représentable sur une machine séquentielle. A partir de là, on conçoit qu'une telle simulation puisse être décrite par un quelconque langage universel de programmation.

Au niveau le plus proche de la machine, le modèle de simulation peut être décrit en langage d'assemblage. Cette approche, bien que très coûteuse du point de vue de la programmation et de la mise au point, est encore employée dans de grandes applications telles que le simulateur de systèmes CSS [Sea 69] ou le simulateur de réseaux de l'université de Waterloo [Pee 74], où les considérations d'efficacité et de taille mémoire nécessaire sont impératives.

Parmi les langages de programmation de plus haut niveau, FORTRAN semble très apprécié, aussi bien pour de grandes applications telles que OSSL [Dew 72], un outil de description de simulations, que de petites [Reh 68, Noe 72]. Citons aussi PL/1 qui a été utilisé chez IBM pour simuler d'une manière très détaillée OS sous LASP [Wal 72] et MAD qui a servi pour des études d'algorithmes d'ordonnancement dans CTSS [Sch 65].

En général, l'emploi de tels langages demande un effort de conception et de programmation propre à la simulation (entretien d'une horloge, pseudo-parallélisme, génération de nombres aléatoires, manipulation de listes). Un tel effort ne peut s'expliquer que dans le cadre de projets importants où les performances et la portabilité peuvent être primordiales.

## 3.2. Les langages généraux de simulation.

Assez tôt des langages généraux de simulation furent créés [McD 70] pour fournir aux utilisateurs les outils qui leur étaient nécessaires. Ces langages de simulation apparurent comme des extensions de langages généraux déjà existants ou même comme des langages entièrement nouveaux. S'ils peuvent être utilisés plus ou moins efficacement pour simuler des systèmes informatiques, [Tei 66, Kiv 67, McD 70], il n'en demeure pas moins que certains sont plus appropriés pour résoudre certains types de problèmes.
Nous ne citerons ici que quelques-uns de ces langages avec leurs principales caractéristiques :

* **SIMSCRIPT** [Dim 64, Mar 64, Mar 66] est une extension de FORTRAN (SIMSCRIPT est un pré-processeur pour un compilateur FORTRAN) basée sur la notion d'événement. Les entités et leurs attributs sont explicitement définis, mais une distinction est faite entre entités temporaires et permanentes. Les entités peuvent être groupées en ensembles au moyen d'outils fournis par le langage. Les activités sont des sous-programmes liés à des événements et qui sont appellés lorsqu'un événement se produit.

* **GPSS** [Her 65, IBM 67] est un langage basé sur la notion de diagramme de blocs. La description du modèle de simulation se fait sous forme de blocs qui sont assemblés en un diagramme. Les entités appellées transactions sont générées par des blocs spéciaux (GENERATE) et circulent à travers le diagramme suivant les conditions et les délais spécifiés par les blocs. GPSS est sans doute moins souple qu'une extension d'un langage de haut niveau, mais il est relativement simple à utiliser, surtout pour des gens ayant peu de connaissances en programmation. C'est un langage qui est très utilisé, peut-être parce que distribué par IBM.

* **SIMULA 67**. [Dah 68, Dah 68, Bir 69] est une véritable extension d'ALGOL 60 (c'est un sur-ensemble d'ALGOL 60). C'est un langage très puissant qui possède une structure de données dynamique et complexe réalisée par l'intermédiaire de blocs (au sens ALGOL 60) et de classes (objet purement SIMULA). Le langage définit le concept de processus. Ceux-ci peuvent être exécutés en parallèle et représenter soit des activités, soit des entités. Les processus peuvent être programmés indépendamment bien qu'ils puissent partager des données entre eux, être activés ou suspendus par eux-mêmes ou par d'autres processus.

* **Autres langages de simulation** : Bien d'autres langages généraux de simulation ont été développés, chacun d'eux essayant de fournir de nouvelles possibilités. Cet éventail varié ne doit pas faire illusion, le plus souvent un utilisateur ne choisira pas un langage pour ses caractéristiques et ses possibilités, mais pour sa disponibilité sur le site d'exploitation, sa documentation, la connaissance qu'il en a ou l'effort de programmation qu'il demande. Quoi qu'il en soit nous donnons
le nom de quelques autres langages qu'il est possible de rencontrer :

- **ASPOL** [McD 73] bien que conçu pour la simulation de systèmes informatiques, est en fait un langage général. Il est très proche de SIMULA 67 et en a la notion de "processus", mais les synchronisations s'opèrent par des "événements" qui sont des sémaphores.

- **CSL** [IBM 66] fut le premier pré-processeur FORTRAN de simulation (comme SIMSCRIPT). C'est maintenant un compilateur disponible sur plusieurs machines.

- **DESPL/1** [Red 73] et **SIMPL/1** [Ret 74] sont des pré-processeurs PL/1 utilisables à partir d'un compilateur PL/1 (ils sont écrits en PL/1).

- **GASP** [Kiv 64, Pri 69] est une extension de FORTRAN réalisée sous la forme d'un ensemble de sous-programmes FORTRAN, ce qui rend GASP facilement disponible sur la plupart des machines.

- **SOL** [Knu 64] est un langage de type ALGOL qui possède beaucoup d'idées reprises plus tard par SIMULA.

### 3.3. Les langages spécialisés pour la simulation de systèmes informatiques.

Bien que la simulation de systèmes informatiques ait été rendue plus facile par l'emploi de langages de simulation, la similitude des concepts entre les divers modèles simulés rendait souhaitable la création de modèles très paramétrés et très souples, voire même de langages spéciaux permettant une description aisée de ces modèles. Deux approches sont alors possibles :

- étendre un langage existant en lui rajoutant des fonctions permettant de représenter certaines parties des systèmes informatiques,

- définir un nouveau langage dont les concepts de base sont liés aux composants d'un système informatique.

Nous donnons quelques exemples de ces deux approches :

* **CSS** (Computer System Simulator) [Sea 69, IBM 70] a été développé par IBM et utilise de nombreux concepts de GPSS. Toute la structure du langage est orientée vers la simulation du matériel et du logiciel des séries 360/370 d'IBM [Ber 74], ce qui rend le langage peu apte à décrire une autre structure de système. Pour finir, disons que CSS est un programme qui est la propriété d'IBM.

* **ECSS** (Extendable Computer System Simulator) [Nie 70] est une extension de SIMSCRIPT II qui a été écrite par la RAND Corporation. ECSS a
toute la souplesse d'un langage général de simulation, mais il dispose
en plus de fonctions permettant de décrire la configuration d'un système
et sa charge.

* **OSSL** (Operating System Simulation Language) [Dew 71, Dew 72, Wya 72]
  a été développé dans les universités pour l'enseignement et la recherche
  sur les systèmes informatiques. Le langage emploie la même terminologie
  que les concepteurs de système et fournit des outils permettant de dé-
 crire les caractéristiques du matériel, le système d'exploitation et
  l'environnement. Signalons qu'il semble difficile de simuler des archi-
  tectures non conventionnelles avec OSSL.

* **QAL** (Queueing Analysis Language) [Fos 74] est un langage de très haut niveau permettant de décrire un réseau de files d'attente et de le simuler. La modélisation d'un système informatique par un réseau de files d'attente est très riche lorsqu'on s'intéresse au parallélisme de fonctionnement entre les divers composants du système et aux engorgements qui peuvent survenir. On voit donc l'intérêt d'un langage comme QAL.

* Pour finir, citons encore SCERT [SCE 67] ou S3 [S3 67] qui permettent de simuler des systèmes informatiques dont la structure est bien précise et rigide.

### 3.4. Les descriptions graphiques.

Dès le début, il a semblé naturel de représenter un système informatique
par un graphe et il existait plusieurs formalismes permettant d'appréhender le
problème : graphes de Petri [Pet 62], schémas de programmes parallèles [Kar 69], etc..
Après avoir réalisé des systèmes d'interaction graphique permettant de manipuler
ces graphes (projet LOGOS [Ros 72]), il a été montré que ces modèles pouvaient
servir à évaluer la cohérence et les performances de l'ensemble d'un système
informatique [Par 74], même au moment de la conception [Bae 73]. En particulier,
les graphes de Petri furent étendus [Noe 73] pour permettre une meilleure repré-
sentation de la réalité et une meilleure évaluation des performances [Nut 72, Nut 73].
Puis ils furent utilisés comme une description graphique de modèles de simu-
lation [Nut 74]. Une telle approche peut être comparée à une représentation graphi-
que liée à GPSS ou à QAL; par l'emploi de consoles de visualisation pour construire
le graphe, on gagne en souplesse et on s'affranchit du fardeau de la programmation.
### 3.5. Conclusion.

Le reproche habituellement fait aux langages généraux et spécialisés de simulation est le grand temps d'exécution nécessaire. En fait ce reproche semble peu fondé si un effort est fait sur les performances du produit et si on considère les temps de développement et de mise au point nécessaires lorsqu'un langage conventionnel est utilisé [Kos 73]. Dans tous les langages, le temps d'exécution ne dépend pas tant de la complexité du modèle que du nombre d'événements pris en compte. Pour fixer les idées, on peut rappeler le tableau cité par TEOREY [Teo 73] :

<table><thead><tr><td>Niveau</td><td>Occurence d'événements</td><td>Temps d'exécution</td></tr></thead><tbody><tr><td>description fonctionnelle grossière</td><td>50 à 500 millisecondes</td><td>10 à 50 fois plus rapide que le temps réel</td></tr><tr><td>description fonctionnelle détaillée</td><td>1 à 10 millisecondes</td><td>20 fois plus lent à 10 fois plus rapide que le temps réel</td></tr><tr><td>instruction machine</td><td>1 à 10 microsecondes</td><td>plus de 20 fois plus lent que le temps réel</td></tr></tbody></table>

Ceci montre clairement qu'il est inconcevable, du fait de temps d'exécution prohibitifs, de simuler avec le même modèle des événements se déroulant au niveau de la micro-seconde et des événements qui arrivent toutes les secondes ou toutes les minutes. Par exemple, il n'est pas pensable de réaliser un modèle de simulation d'une hiérarchie de mémoire qui parte du niveau du cache, dont l'unité de temps est la nano-seconde, pour aller jusqu'au niveau d'une librairie sur bandes magnétiques, dont l'unité de temps est $10^9$ ou $10^{10}$ fois supérieure.
Une simulation permet de générer une suite temporelle d'événements qui soit conforme au fonctionnement – plus ou moins idéalisé – d'un système réel. Parfois l'intérêt de la simulation réside dans la seule production de cette suite et aucun traitement quantitatif n'est nécessaire : c'est le cas lorsqu'on veut tester la possibilité d'un événement particulier (interblocage, non récupération d'une erreur de transmission, ...) ou que l'on veut s'assurer de la correction fonctionnelle d'un mécanisme [Mer 73, Hay 69]. Toutefois la suite d'événements produite par la simulation est généralement utilisée pour évaluer les performances (quantitatives) du système étudié.

Deux types de problèmes se posent alors [Bor 71, Hol 71, Ler 73] :

- prélever des mesures : les grandeurs à mesurer sont considérées comme des réalisations de processus stochastiques qu'il s'agit d'échantillonner [Boi 73, Knu 73, Ler 73],

- évaluer des statistiques définies sur cet échantillon [Bar 71, Rod 72].

Nous retrouvons là les mêmes difficultés que pour l'analyse des systèmes réels, même si la méthode ou la technologie employées pour l'obtention des échantillons sont différentes.

Dans les simulations, comme dans l'observation des systèmes réels, le prélèvement des mesures est déclenché par un événement tel que :

- changement d'état du système étudié,

- intervention humaine,

- signal d'horloge.

Ce prélèvement pose à la fois des problèmes techniques :

- la variable à échantillonner n'est pas accessible à tout instant ou n'est pas mise à jour [Boi 73],

- le dispositif de prise de mesure perturbe la variable à mesurer [Hol 71],

- la résolution de l'échelle des temps manque de finesse [Gau 73] (des variations rapides de la grandeur à mesurer passent inaperçues), et des problèmes statistiques (au moins quand la quantité mesurée est considérée comme la réalisation d'une variable aléatoire) :
- choix d'un événement pouvant apporter des simplifications au traitement statistique de l'échantillon. La connaissance de points de régénération, (*) en particulier, est très utile.

- compensation de l'auto-corrélation [Cra 74, Fis 65, Fis 67],

- vérification de la stationnarité des processus étudiés [Cox 68, Cox 72].

<footnote>(*) Rappelons que l'instant $t_o$ est un point de régénération du processus stationnaire $\{X(t)\}$, si la connaissance de $X(t)$ à tout instant $t < t_o$ ne fournit pas plus d'information sur l'évolution du processus après $t$ que la connaissance de $X(t_o)$. (par exemple pour l'étude de la longueur d'une file d'attente à arrivées indépendantes, les instants de fin de service sont des points de régénérations) [Cra 74].</footnote>
5.1. Estimation d'un processus stochastique.

Les mesures tirées de modèles de simulation n'ont de sens que si l'on dispose d'une évaluation de la confiance qu'on peut leur accorder. L'évolution dans le temps de la grandeur observée est représentée mathématiquement par un processus stochastique [Cox 72] :

$$
\mathcal{X} = \{ X(t) \}_{t \in T}, \text{ l'ensemble T étant un intervalle de l'axe des temps.}
$$

Supposons que n mesures Xᵢ (i = 1,2,..., n) soient prélevées à des instants tᵢ (tᵢ > tᵢ-₁). Dans ce formalisme, le nombre Xᵢ est une réalisation de la variable aléatoire X(tᵢ). C'est à partir de telles familles de réalisations que l'on doit tirer une information significative sur X.

Le processus stochastique X serait parfaitement défini si, pour toute
famille t₁, t₂, ..., tₘ d'instants, on connaissait la fonction de répartition con-
jointe :

$$
F(t_1, t_2, \dots, t_m ; u_1, u_2, \dots, u_m) = \Pr[X(t_1) < u_1 ; X(t_2) < u_2 ; \dots ; X(t_m) < u_m]
$$

Dans la pratique, il est souvent très difficile d'estimer cette fonction.
On se contente généralement de la fonction de répartition absolue :

$$
F(t;u) = \Pr[X(t) < u]
$$

voire de sa moyenne $\mathbb{E}[X(t)] = \mu(t)$ et de sa variance $V[X(t)] = \sigma^2(t)$.

Si l'on désire plus d'informations sur le comportement du processus sto-
chastique, on en estime parfois la fonction d'auto-corrélation :

$$
\rho(\tau) = \frac{\mathbb{E}[(X(t) - \mu)(X(t+\tau) - \mu)]}{\sigma^2}
$$

Cette estimation n'est possible que sous certaines hypothèses de sta-
tionnarité sur le processus X, en particulier, on doit avoir :

$$
\mu(t) = \mu = c^{\text{ste}}
$$

$$
V[X(t)] = \sigma^2(t) = \sigma^2 = c^{\text{ste}}
$$

Plusieurs niveaux de difficultés se rencontrent dans l'étude de $\mathcal{X}$ suivant
les propriétés qu'il possède.
a - $\chi$ est un processus strictement stationnaire.

Cela signifie que, pour tous $t_1, t_2, ..., t_m, h$, la distribution conjointe des variables aléatoires

$$X(t_1), X(t_2), ..., X(t_m)$$

est identique à la distribution conjointe de

$$X(t_1+h), X(t_2+h), ..., X(t_m+h)$$

soit :

$$F_X(t_1),..., X(t_m) = F_X(t_1+h),..., X(t_m+h) \quad \forall h, t_1, ..., t_m, \forall m \in \mathbb{N}^+$$

Ceci implique, en particulier, que la distribution de $X(t)$ ($F(t;u)$) ne dépend pas de $t$. Cette propriété permet d'estimer la fonction de répartition absolue $F(.;.)$ à l'aide d'une seule simulation. Par ailleurs, d'après le théorème de Doobs-Birkhov [LeG 68], l'espérance mathématique du processus $E(X(t))$ peut être estimée par la moyenne temporelle (processus ergodique en moyenne) :

$$E(X(t)) = \lim_{T \to \infty} \frac{1}{T} \int_{0}^{T} X(t) dt.$$

ce qui permet d'utiliser l'estimateur suivant pour la moyenne :

$$\bar{X} = \frac{1}{n} \sum_{j=1}^{n} X_j (t_i - t_{i-1}) \quad (1)$$

où les $t_i$ sont les instants de changement de valeur de $X(t)$. Cet estimateur est meilleur que la moyenne arithmétique des valeurs $X_j$ :

$$\bar{X} = \frac{1}{n} \sum_{j=1}^{n} X_j \quad (2)$$

en effet, l'estimateur (1) tient compte des poids relatifs dans le temps de chaque valeur $X_i$. Pour pouvoir utiliser l'estimateur (2), il faut échantillonner régulièrement dans le temps, tous les $\Delta t$ et l'intervalle $\Delta t$ doit être petit par rapport aux $t_i - t_{i-1}$, intervalles de temps séparant les changements de valeur de $X(t)$.

Le cas le plus favorable est celui où il existe une fonction $G(.)$ telle que pour toute famille d'instants $t_1, t_2, ..., t_m$ et toute famille de réels $u_1, u_2, ..., u_m$, on puisse écrire :

$$F(t_1, t_2, ..., t_m; u_1, u_2, ..., u_m) = G(u_1) G(u_2) ... G(u_m)$$

ce qui signifie que les mesures prélevées sont indépendantes. On n'a pas à s'affranchir des problèmes d'auto-corrélation. Les méthodes classiques d'analyse de
variance permettent de déterminer des intervalles de confiance [Fou 67] pour les résultats trouvés (cf. 5.2.).

b - $\bar{X}$ est un processus faiblement stationnaire.

A moins d'hypothèses théoriques, il n'est pas possible de montrer qu'un processus est strictement stationnaire. En revanche, on peut tester les deux hypothèses suivantes [Leh 59] :

- l'espérance de $X(t)$ est constante : $E(X(t)) = \mu$

- l'auto-covariance sur $X(t)$ ne dépend que de l'intervalle de temps considéré :

$$ \text{Cov}(X(t+h), X(t)) = \gamma(h) $$

Un processus satisfaisant à ces deux hypothèses est dit faiblement stationnaire. Remarquons que la variance de $X(t)$ est constante :

$$ V(X(t)) = \gamma(0) $$

et que l'auto-corrélation s'exprime par :

$$ \rho(h) = \frac{\gamma(h)}{\gamma(0)} $$

On montre qu'un processus gaussien est strictement stationnaire si et seulement s'il est faiblement stationnaire [Cox 72]. La propriété de faible stationnarité permet d'estimer en une seule simulation les deux premiers moments de la variable aléatoire $X(t)$ et donc de déterminer des intervalles de confiance sur ces moments (cf. 5.2.)

c - $\bar{X}$ n'est pas un processus stationnaire.

Tous les moments de $X(t)$ dépendent, a priori, du temps. Ils doivent être estimés point par point dans le temps ce qui rend nécessaire le déroulement de plusieurs simulations dont l'indépendance est assurée par des initialisations différentes des générateurs de nombres aléatoires.

Par exemple, si nous disposons, par n simulations, d'un échantillon de taille n de $X(t)$ à l'instant $t = X_1(t), X_2(t),..., X_n(t)$ nous aurons :

$$ \overline{X(t)} = \frac{1}{n} \sum_{i=1}^{n} X_i(t) $$

si nous disposons aussi d'un échantillon de taille n de $X(t)$ à l'instant $t'$ :
$X_1(t'), X_2(t'),...,X_n(t')$, nous pourrons estimer l'auto-covariance de $\bar{X}$ entre les instants $t$ et $t'$ à partir de la formule :
$$ \text{Cov}(X(t), X(t')) = E(X(t) X(t')) - E(X(t)) E(X(t')) $$

dont un estimateur est :

$$ \hat{\text{Cov}}(X(t), X(t')) = \frac{1}{n} \left[ \sum_{i=1}^{n} X_i(t) X_i(t') - \frac{1}{n} \sum_{i=1}^{n} X_i(t) \sum_{i=1}^{n} X_i(t') \right] $$

On voit donc qu'il est difficile et coûteux d'estimer les caractéristiques d'un processus non stationnaire. Il existe essentiellement deux approches pour se ramener à un cas stationnaire. Dans un cas, on considère que le processus non stationnaire est la somme d'une tendance déterministe et d'un processus stationnaire [Cox 66], dans l'autre on essaie de découper la durée d'observation du processus en intervalles durant lesquels une hypothèse de stationnarité est justifiée. Cette dernière approche semble particulièrement fructueuse et elle signifie que l'on cherche à distinguer deux échelles de temps. Dans un modèle de simulation, on pourra avoir :

- une échelle microscopique au niveau des événements (services à l'unité centrale entre défauts de page et E/S)

- une échelle macroscopique au niveau des variations dans le temps des fonctions de distribution (changements dans le comportement des utilisateurs ou des programmes).

Sans autres hypothèses, il est très difficile de trouver le découpage approprié. Un moyen peut être de se donner un découpage arbitraire et de procéder à des tests de stationnarité faible sur les intervalles obtenus pour valider ce découpage. Des hypothèses théoriques peuvent permettre de s'affranchir de ces tests. Ce peut être le cas d'un processus stochastique intervenant dans un système où il est possible de préciser les instants de variations des paramètres du processus et où ces instants sont suffisamment distants pour permettre d'obtenir un échantillon significatif. Un système qui possède une telle propriété est dit *quasi-décomposable*. Cette propriété a été étudiée en détail dans le cadre des chaines de Markov (où elle fonde la méthode d'aggrégation des variables). Cette méthode a d'abord été utilisée dans les modèles économiques [Sim 61, And 63] avant d'être introduite dans les modèles de systèmes informatiques [Cou 71, Avi 73].

Suivant les caractéristiques du processus $\lambda$, voyons maintenant quelle confiance nous pourrons accorder à des grandeurs évaluées à partir d'une réalisation de $\lambda$.
## 5.2. Constructions d'intervalle de confiance.

En général dans les modèles aussi bien mathématique que de simulation, on s'intéresse aux valeurs moyennes des différentes variables intervenant dans le modèle.

Nous rechercherons donc une estimation de l'espérance mathématique (moyenne) du processus $X(t)$ considéré. Si $X(t)$ est faiblement stationnaire et $t_1, t_2, \dots, t_n$ n instants où l'on mesure la grandeur considérée, la statistique :

$$ \bar{X} = \frac{1}{n} \sum_{i=1}^{n} X_{i} \quad \text{où} \quad X_{i} = X(t_{i}) $$

est une estimateur non biaisé (et de variance minimale) de

$$ \mu = E(X(t)). $$

Nous voulons connaître la confiance que nous pouvons avoir dans $\bar{X}$. L'inégalité de Bienaymé-Tchebycheff nous permet de construire un premier intervalle sur $\bar{X}$. En effet :

$$ \text{Pr} \left[ |X - \mu| < \delta \sigma_{\bar{X}} \right] > 1 - \frac{1}{\delta^2} \quad \text{Vd} \delta > 0 \\ \text{où } \sigma_{\bar{X}} = \sqrt{V(\bar{X})} $$

ainsi $\mu$ se trouve encadrée avec une probabilité d'au moins $1 - \frac{1}{\delta^2}$ par :
$$ \bar{X} - \delta \sigma_{\bar{X}} < \mu < \bar{X} + \delta \sigma_{\bar{X}} $$

Pour une confiance habituelle de 95%, nous aurons $1 - \frac{1}{\delta^2} = 0,95$, d'où
$$ \delta = \sqrt{20} \approx 4,5. $$

Donc avec une probabilité supérieure à 0,95, on a :

$$ \bar{X} - 4,5 \sigma_{\bar{X}} < \mu < \bar{X} + 4,5 \sigma_{\bar{X}} $$

L'inégalité de Bienaymé-Tchebycheff ne fait aucune hypothèse sur la loi suivie par $\bar{X}$, si on suppose que $\bar{X}$ suit une loi gaussienne (c'est le cas, si les réalisations $X_i$ sont indépendantes d'après le théorème Central Limite), on peut obtenir un intervalle plus serré. Pour une confiance de 95%, les tables de la loi de Gauss donnent :

$$ \bar{X} - 1,96 \sigma_{\bar{X}} < \mu < \bar{X} + 1,96 \sigma_{\bar{X}} $$

Pour achever la construction de l'intervalle de confiance sur $\bar{X}$, il faut estimer $V(\bar{X})$ pour avoir $\sigma_{\bar{X}} = \sqrt{V(\bar{X})}$. Un cas particulièrement intéressant est d'avoir un estimateur convergent de $V(\bar{X})$ [Fou 67]. Nous pourrons alors rendre arbi- triement petite l'amplitude de l'intervalle déterminé en augmentant la taille de
l'échantillon (par exemple en prolongeant une simulation) ; c'est-à-dire atteindre
une précision fixée à l'avance. L'estimation de $V(\bar{X})$ est délicate car elle est
sensible à l'auto-corrélation éventuelle de l'échantillon dont on dispose. Trois
méthodes sont couramment utilisées :

a - On peut estimer $V(\bar{X})$ en utilisant la fonction d'auto-corrélation $\gamma(h)$.

$$
\begin{align*}
V(\bar{X}) &= V\left(\frac{1}{n}\sum_{i=1}^{n} X_i\right) = \frac{1}{n^2} \left[ \sum_{i=1}^{n} V(X_i) + \sum_{\substack{i,j=1 \\ i \neq j}}^{n} \text{Cov}(X_i, X_j) \right] \\
&= \frac{V(X)}{n} + \frac{1}{n^2} \sum_{\substack{i,j=1 \\ i \neq j}}^{n} \text{Cov}(X_i, X_j)
\end{align*}
$$

Si les mesures X₁, X₂, ..., Xₙ sont deux à deux indépendantes, on peut alors écrire Vᵢ,j et i≠j Cov (Xᵢ, Xⱼ) = 0. D'où V(∑X) / n et en appliquant le théorème Central-Limite, on obtient l'intervalle de confiance :

$$
\bar{X} - 1,96 \sqrt{\frac{V(X)}{n}} < \mu < \bar{X} + 1,96 \sqrt{\frac{V(X)}{n}}
$$

où $V(X)$ est estimée sans biais par la statistique :

$$
\hat{V}(X) = \frac{1}{n-1} \left[ \sum_{i=1}^{n} x_i^2 - \frac{1}{n} \left( \sum_{i=1}^{n} x_i \right)^2 \right]
$$

Remarquons que l'estimateur de $V(\bar{X})$ est convergent :

$$
\lim_{n \to \infty} V(\bar{X}) = \lim_{n \to \infty} \frac{V(X)}{n} = 0
$$

l'intervalle de confiance construit peut donc être rendu aussi petit que l'on veut.

Si au contraire les variables aléatoires X₁, X₂, ..., Xₙ ne sont pas stochas-
tiquement indépendantes, d'après l'hypothèse de stationnarité faible, on a :

$$
\mathrm{Cov}(X_i, X_j) = \gamma (|t_i - t_j|)
$$

La fonction $\gamma$ peut être estimée grâce à l'échantillon, mais la précision décroît lorsque l'argument de cette fonction augmente puisqu'on dispose de moins en moins de points pour cette estimation. Souvent on admet qu'il existe un seuil s'au-delà duquel la fonction $\gamma$ est nulle :

$$
h \ge s \Rightarrow \gamma(h) = 0
$$
Une autre manière de procéder est de se donner, à priori, une forme pour la fonction $\gamma$ et d'en ajuster les paramètres sur l'échantillon [Cox 68, Bro 59]. On parle alors, suivant le cas, d'oubli linéaire, exponentiel... Il faut remarquer que cette **méthode n'est pas séquentielle**, elle exige de disposer de **tout l'échantillon** pour le traiter. On ne peut donc pas, par cette méthode, arrêter une simulation sur une précision fixée à l'avance.

b - On peut également fractionner l'échantillon $X_1, X_2, ..., X_n$ en k blocs de mesures consécutives [Con 63] :

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

Sur le bloc $j$, on calcule la moyenne :

$$ \bar{X}^{(j)} = \frac{1}{l_j} \sum_{i=1}^{l_j} X_{d+i} \quad \text{où } d = l_1 + l_2 + \dots + l_{j-1} $$

L'idée est de former une partition en blocs telle que $(\bar{X}^{(1)}, \bar{X}^{(2)}, ..., \bar{X}^{(k)})$ constitue un échantillon non auto-corrélé de la variable aléatoire $\bar{X}$. Cet objectif peut être atteint de deux manières :

- On peut faire en sorte que les blocs soient séparés par des points de régénération [Cra 74].

- ou que la taille des blocs soit suffisamment grande pour que les variables $\bar{X}^{(i)}$ et $\bar{X}^{(j)}$ apparaissent comme indépendantes pour tous i et j distincts (auto-corrélation nulle d'un bloc à l'autre).

On obtient alors un estimateur de $V(\bar{X})$ par :

$$ \hat{V}(\bar{X}) = \frac{1}{k \cdot l_j} \left[ \sum_{i=1}^{k} (\bar{X}^{(i)})^2 - \frac{1}{k} \left( \sum_{i=1}^{k} \bar{X}^{(i)} \right)^2 \right] $$

Nous remarquons qu'après la détermination d'une taille de bloc minimale $l_0$, cette méthode peut être **séquentielle**.

Dans le cas d'une simulation, on procèdera donc ainsi :

- détermination d'une taille de bloc $l_0$ à partir d'une première réalisation de $X(t)$ (une simulation).

- nouvelles simulations où la taille de bloc $l_0 \gg l$ (la même pour tous les blocs) est donnée en paramètre.
La taille de bloc lo doit être choisie pour être valable d'une simulation
à l'autre et elle sera déterminée à partir de la fonction d'auto-corrélation de
telle manière que :

$$
|\rho(10)| = \left| \frac{\gamma(10)}{\gamma(0)} \right| \ll 1
$$

$$
\text{avec } \hat{\gamma}(h) = \frac{1}{n-h} \sum_{i=1}^{n-h} X_{i} X_{i+h} - \frac{1}{(n-h)^2} \left( \sum_{i=1}^{n-h} X_{i} \sum_{i=1}^{n-h} X_{i+h} \right)
$$

où h << n

c - Une autre méthode consiste à faire une analyse spectrale de l'échantillon
des (Xᵢ) [Par 61, Jen 61]. On considère la partie réelle de la transformée
i=1,...,n
inverse de Fourier de l'auto-covariance :

$$
f(\lambda) = \frac{2}{\pi\gamma(0)} \int_{0}^{\infty} \gamma(\tau) \cos \gamma\tau \, d\tau
$$

ou si on considère le processus X(t) aux instants t=0, ±1, ±2, ..., ±∞ :

$$
f(\lambda) = \frac{1}{\pi} \left[ 1 + 2 \sum_{\tau=1}^{\infty} \left( R_{\tau} / R_{0} \right) \cos \lambda\tau \right] \quad 0 \le \lambda \le \pi
$$

$$
\text{où :} \quad R_{\tau} = E\left[(X_{t-\mu} - \mu)(X_{t-\tau} - \tau)\right] \quad \tau = 0, 1, 2, \dots, \infty
$$

$$
\text{avec :} \quad \mu = E(X_t)
$$

Cette fonction f(λ) est appelée fonction de densité spectrale et peut servir à
caractériser le processus X(t), en particulier si on désire étudier les déviations
de X(t) par rapport à sa moyenne [Fis 65, Fis 67].

La notion de densité spectrale conduit à la définition du temps de corré-
lation [Fis 67] :

$$
\tau^* = \frac{\pi}{2} f(0)
$$

qui correspond au cas idéalisé d'un processus entièrement corrélé sur une durée de
τ* et non corrélé au-delà.
Ce temps de corrélation qui peut-être estimé directement à partir des estimations :

$$ \hat{R}_{\tau} = \frac{1}{T-\tau} \sum_{t=1}^{T-\tau} (X_t - \bar{X}) (X_{t+\tau} - \bar{X}) $$

peut servir à définir un nombre équivalent d'observations indépendantes :

$$ N = T/(2\tau^*) $$

où T est le nombre d'observations réels. Ceci revient à dire qu'on peut considérer des observations distantes de $2\tau^*$ comme indépendantes.

Signalons toutefois que cette méthode présente certaines difficultés pratiques [Fis. 67] et qu'elle n'est pas à l'abri de critiques théoriques [Leg 68].

d - Nous pouvons aussi citer une méthode qui vise à réduire la variance l'estimateur $V(\bar{X})$ en rendant négatif le terme $Cov(X_i, X_j)$ qui intervient dans l'expression de $V(\bar{X})$. Pour ce faire on réalise deux échantillons à partir de génération de variables aléatoires antithétiques [Pag 63] et on considère ensuite l'échantillon fait de l'union des deux échantillons initiaux. Cette méthode est relativement lourde, car elle exige plusieurs simulations, et elle a souvent des résultats peu convainquants [Fer 75] si la grandeur mesurée n'est pas directement liée à la génération des variables aléatoires antithétiques.
Si soigneusement qu'il soit construit, un modèle ne sera acceptable que s'il reflète, au moins en partie, une réalité connue. Il faut tout d'abord l'étalonner, c'est-à-dire s'assurer sur quelques points que les résultats obtenus par simulation concordent avec ceux que l'on a pu tirer de mesures sur le système réel. Une fois cette opération terminée, on n'est sûr de la qualité du modèle que sur ces quelques points. Il s'agit d'élargir le domaine où l'on peut faire confiance au modèle, faute de quoi celui-ci ne serait guère utile : cette seconde phase est celle de la validtion.

Etalonnage et validation sont souvent confondus, bien qu'ils soient différents [Bei 73, Ern 71]. En fait, seul l'étalonnage a fait récemment l'objet de recherche [Bei 72]. La validation n'a pas été abordée sérieusement et sa formalisation, qui reste à faire, semble très délicate.

En général les étalonnages réalisés sont relativement grossiers [Ric 73, Noe 72]. Ils consistent, le plus souvent, à comparer visuellement des tableaux de nombres ou des courbes produits à partir du modèle testé et d'un système de référence. Ce système de référence peut être le système réel ou un modèle précédemment étalonné et validé (étalonnage et validation par "bootstraping" de modèles [Bei 73]).

Néanmoins un effort de formalisation et de méthodologie a été accompli pour l'étalonnage des modèles de simulation alimentés par une trace [Bei 72]. La méthode proposée consiste à comparer des mesures réelles associées à la trace avec des mesures tirées du simulateur : les différences constatées sont exprimées sous forme de régressions multilinéaires afin d'ajuster les paramètres adéquats dans le simulateur. En prolongement de l'étalonnage une tentative a été faite pour valider la simulation : une partie de la trace est utilisée pour l'étalonnage proprement dit et l'autre pour vérifier que le modèle étalonné se comporte convenablement sur un ensemble de points différents. Toutefois cette méthode ne peut pas être considérée comme une validation indiscutable. En particulier, les deux traces utilisées, bien que différentes au niveau microscopique, peuvent avoir des caractéristiques identiques au niveau macroscopique.

La validation reste un acte de foi.
## 7 - CONCLUSION

Les modèles de simulation sont souvent préférés aux modèles mathématiques pour leur caractère plus réaliste et leur formalisation moins rebutante. En fait, il s'agit là d'une fausse sécurité et d'une fausse facilité.

Fausse sécurité, car le critère de réalité n'affecte en rien la valeur des résultats : de nombreux modèles mathématiques sont peu réalistes dans leurs hypothèses, mais donnent d'excellents résultats. Plus qu'un modèle réaliste, on doit chercher à avoir un modèle robuste (on dit qu'un modèle est robuste, si les hypothèses ont peu d'influence sur les prédictions de performances obtenues). [Buz 74, Cha 74], étalonné et validé.

Fausse facilité, car de nombreux problèmes, dont certains sont très ardus, restent posés :

- problèmes de simulateurs décrits par un graphe [Noe 73, Nut 73, Nut 74, Par 74], où les objets du graphe permettent des contrôles de validité [Wat 70] et des pri- ses automatiques de mesures,

- problèmes de précision des résultats, liés non seulement à la convergence de la simulation, mais où la qualité des entrées du simulateur (validation d'une trace) et au niveau de simulation choisi [Teo 73],

- problèmes d'étalonnage et de validation d'un modèle.

Cette exigence de rigueur ne relève pourtant pas d'un perfectionnisme purement académique. Le manque d'homogéneité que l'on coscrate trop souvent entre échantillons différents a pour conséquence qu'en l'abscence de précautions, on est très vite amené à des conclusions erronées. Les collectes de données effectuées dans des conditions peu satisfaisantes ou mal connues proviennent du manque de collaboration entre :

- les spécialistes en systèmes d'exploitation qui fournissent les outils de prélèvement et les mesures,

- les mathématiciens et les statisticiens qui développent des métho- des d'analyse de données,

- et les spécialistes de simulation qui, accaparés par les problèmes de modélisation et de langage, ont tendance à ne pas s'inquiéter de la validité des résultats fournis.
Il semble souhaitable d'aborder ces problèmes d'une manière globale.

Il est, en particulier, nécessaire d'intégrer dans les systèmes réels et dans
les modèles de simulation des outils évolués pour collecter les mesures et en
assurer le dépouillement. Ces outils sont indispensables dans les systèmes
auto-régulés où il est nécessaire de détecter le plus rapidement possible une modi-
fication significative des conditions de fonctionnement [Bad 74], ce qui suppose
la mise en oeuvre de méthodes statistiques efficaces.
[And. 63] ANDO A., FISHER F.M. - "Near decomposability, partition and aggregation, and the relevance of stability discussions" - International economic review - Vol. 4, n° 1, January 1963.

[Avi. 73] AVI-ITZHAK B., HEYMAN D.P. - "Approximate queueing models for multiprogramming computer systems" - Operations Research - Vol. 21, n° 6, Nov.-December 1973.

[Bad. 74] BADEL M., GELENBE E., LEROUDIER J., POTIER D. - "Adaptive optimization of a virtual memory computer" - SIGMETRICS 74 - Symposium on Measurements and Evaluation Performance - Montreal - October 1974.

[Bae. 73] BAER J.L. - "Models for the Design, Simulation, and Performance of Distributed Function Architecture" - Computer - March 1974.

[Bar. 71] BARD Y. - "CP-67 Measurement and Analysis - Overhead and Throughput" - ACM-SIGOPS - Workshop on System Performance Evaluation - April 1971 - Harvard University.

[Bei. 73] BEILNER H. - "Problems in calibrating and validating simulation models" - 2nd Seminar on Experimental simulation and solving of Probability problems - Liblice (CSSR) - June 1973.

[Bei. 72] BEILNER H., WALDBAUM G. - "Statistical methodology for calibrating a trace driven simulator of a batch computer system" - IBM Research - RC 3855 - May 1972.

[Ber. 74] BERETEVAS T. - "A simulation model representing the OS/VS2 release 2 control program" - Colloque IRIA - Avril 1974.

[Bir. 69] BIRTWISTLE G. - "Notes on the SIMULA language" - Publication n° S.8 - Norwegian Computing Center - OSLO 3 NORWAY - April 1969.

[Boi. 73] BOI L., DRUCBERT J.P. - "OSSYOSCOPE : System on auxiliary processors for measuring operating systems" - International computing symposium 1973 - Davos - Switzerland - September 1973 -

[Bor. 71] BORDSEN D.T. - "Univac 1108 instrumentation system" - SIGOPS-ACM - Workshop on system performance evaluation - April 1971 - Harvard University.

[Box. 70] BOX G.E., JENKINS G.M. - "Time Series Analysis Forecasting and Control" - Holden-Day - 1970.
[Bro. 63] BROWN R.G. - "Smoothing, forecasting and prediction of discrete time series" - Prentice-Hall Inc. - Englewood Cliffs - N.J. 1963.

[Buz. 74] BUZEN J.P., GOLBERG P.S. - "Guidelines for the use of infinite source queueing models in the analysis of computer system performance" - National Conference 1974.

[Cha. 74] CHANDY K.M., HOWARD J., KELLER T.W., TOWSLEY D.J. - "Local balance, Robustness, Poisson departure and the product form in queueing networks" - Internal Report of the University of Texas at Austin - 1974.

[Con. 63] CONWAY R.W. - "Some tactical problems in digital simulation" - Management Sciences - Vol 10, n° 1 - October 1963.

[Cou. 71] COURTOIS P. - "On the near-complete decomposability of networks of queues and of stochastic models of multiprogramming computing systems" - MBLE Report - Belgium - November 1971.

[Cox. 68] COX D.R., LEWIS P.A. - "The Statistical Analysis of Series of Events" - M.S. Bartlett's. - Methuen monographs - London 1968.

[Cox. 72] COX D.R., MILLER H.D. - "The theory of stochastic processes" - Chapman and Hall - London 1972.

[Cra. 74] CRANE M.A., IGLEHART D.L. - "Simulating stable stochastic systems I : General multiserver queues - II : Markov chains" - JACM - Vol. 21, n° 1 - January 1974.

[Dah. 66] DAHL O.J., NYGAARD K. - "Simula - an Algol based simulation language" - CACM - Vol. 9, n° 9 - September 1966.

[Dah. 68] DAHL O.J., MYHRHAUG B., NYGAARD K. - "SIMULA 67 Common Base Language" - Publication n° S-2 - Norwegian Computing Center - OSLO 3 - NORWAY - May 1968.

[Dew. 71] DEWAN P.B., WYATT J.B. - "OSSL : Operating System Simulation Language, a user's guide" - Report RS I-71 - November 1971 - University of Houston (Texas).

[Dew. 72] DEWAN P.B., DONAGHEY C.E., WYATT J.B. - "OSSL - A specialized language for simulating computer systems" - Spring Joint Computer Conference 1972.

[Dim. 64] DIMSDALE B., MARKOWITZ H.M. - "A description of the SIMSCRIPT language" - IBM Syst. Journal 3, 1 - 1964.

[Ern. 71] ERNST H.A. - "Problems in computing systems performance modelling : characterization, calibration and validation" - IBM Research - RC 3319 - April 1971.
[Fer. 75] FERRARI D., LINDSAY D.S., PEAK P.M - "Variance Reduction Techniques in Computer System Performance Measurements" - International Computing Symposium 1975 - Antibes - France - June 1975.

[Fis. 65] FISHMAN G.S., KIVIAT P.J. - "Spectral analysis of time series generated by simulation models" - Rand Corporation - Memorandum - RM - 4393 - PR - February 1965.

[Fis. 67] FISHMAN G.S. - "Problems in the statistical analysis of simulation experiments : the comparison of means and the length of sample records" - CACM - Vol. 10, n° 2 - February 1967.

[Fos. 74] FOSTER D.U., Mac GEHEARTY, SAUER C.H., WAGGONER C.N. - "A language for analysis of queueing models" - Report TR33 - University of Texas at Austin - April 1974.

[Fou. 67] FOURGEAUD D.C., FUCHS A. - "Statistique" - Dunod 1967.

[Gau. 73] GAUDEUL B. - "Evaluation des performances des systèmes par méthode Hardware" - Compte rendu des Journées d'Etudes sur les recherches en mesure, simulation, modélisation des systèmes informatiques - Toulouse - Juin 1973.

[Gor. 69] GORDON G. - "System Simulation" - Prentice Hall, Inc. - Englewood Cliffs - New Jersey - 1969.

[Hay. 69] HAYS G.G. - "Computer Aided Design : Simulation of Digital Design Logic" - IEEE Transactions on Computers - Vol. C-18 - n° 1 - January 1969.

[Her. 65] HERSCOVITCH H., SCHNEIDER T.H. - "GPSS III : An Expanded General Purpose Simulator" - IBM System Journal - Vol. 4, n° 3 - 1965.

[Hol. 71] HOLTWICK G.M. - "Designing a commercial performance measurement system" - SIGOPS-ACM - Workshop on performance evaluation - April 1971 - Harvard University.

[IBM. 66] IBM - "Control and simulation language users manual" - IBM United Kingdom - Limited Data Center - 1966.

[IBM. 67] IBM - "General Purpose Simulation System/360 Users Manual" - IBM Corporation, H20-0326-0 - 1967.

[IBM. 70] IBM - "Computer System Simulator (CSS II) General Information" - IBM Corporation, GH20-0874-0 - October 1970.

[Jen. 61] JENKINS G.M. - "General considerations in the analysis of Spectra" - Technometrics - Vol. 3, n° 2 - May 1961.

[Kar. 69] KARP R.M., MILLER R.E. - "Parallel Program Schemata" - Journal of Comp. and System Sc. - n° 3 - 1969.
[Kiv. 64] KIVIAT P.J. - "GASP : A General Activity Simulation Program" - P 2864 - The RAND Corporation - 1964.

[Kiv. 67] KIVIAT P.J. - "Computer simulation programming languages : perspectives and prognosis" - Rand Corporation (collection) - Report P 3599 - September 1967.

[Kle. 73] KLEIJNEN J.P.C. - "Statistical Techniques in Simulation" - Marcel Dekker - New York - 1973.

[Knu. 64] KNUTH D.E., Mac NELEY J.L - "SOL : A symbolic Language for General Purpose System Simulation" - IEEE Trans. on Computers - August 1964.

[Knu. 73] KNUTH D.E., STEVENSON F.R. - "Optimal measurements points for program frequency counts" - BIT 13 (1973)

[Kos. 73] KOSY D.W. - "An Interim Empirical Evaluation of ECSS for Computer System Simulation Development" - Symp. on the Simulation of Comp. System - 1973.

[LeG. 68] LE GALL P. - "Convergence des simulations et application aux réseaux téléphoniques" - AFIRO monographies de recherche opérationnelle - n° 7 - 1968.

[Leh. 59] LEHMANN E.L. - "Testing statistical hypotheses" - John Wiley and Sons, Inc. - New York - 1959.

[Ler. 73] LEROUDIER J. - "Analyse d'un système à partage de ressources" - RAIRO - October 1973.

[Mar. 64] MARKOWITZ H.M., HANSNER B., KARR H. - "Simscript" - Prentice-Hall - Englewood Cliffs - N.J. 1964.

[Mar. 66] MARKOWITZ H.M. - "Simulating with SIMSCRIPT" - Management Science - Vol. 12, n° 10 - June 1966.

[McD. 73] Mac DOUGALL M.H., Mac ALPINE J.S. - "Computer System Simulation with ASPOL" - Symposium on the Simulation of Computer System - June 1973.

[McD. 70] Mac DOUGALL M.H. - "Computer System Simulation : an Introduction" - Comp. Surveys - Vol. 2, n° 3 - September 1970.

[Mer. 73] MERMET J. - "Etude méthodologique de la conception assistée par ordinateur des systèmes logiques" - Thèse d'état - Grenoble - Avril 1973.

[Nie. 70] NIELSEN N.R. - "ECSS : An extendable computer system simulator" - Rand Corporation - Memorandum - RM-6132-NASA - February 1970.
[Noe. 72] NOE J.D., NUTT G.J. - "Validation of a trace driven CDC 6400 simulation" - SJCC 72.

[Noe. 73] NOE J.D., NUTT G.J. - "Macro E-Nets for Representation of Parallel Systems" - IEE transactions on computer 73 - Vol. C-22, n° 8 - August 1973.

[Nut. 72] NUTT G.J. - "Evaluation nets for computer system performance analysis" - Fall Joint Computer Conference - 1972.

[Nut. 73] NUTT G.J. - "The computer System Representation Problem" - Symp. on the Simulation of Comp. System - June 1973.

[Nut. 74] NUTT G.J. - "Evaluation net simulation system reference manual" - University of Colorado - Dept. of Comp. Sc. - Tech. Report n° CU-CS-042-74 - April 1974.

[Pag. 64] PAGE E.S. - "On Monte-Carlo methods in congestion problems : II - Simulation of queueing systems" - Operation Research 13 - n° 2 - Avril 1964.

[Par. 74] PARENT M.R. - "The control graph models : a unified approach to performance evaluation" - Ph.D. Thesis - Case Western Reserve - University - Cleveland - Ohio - June 1974.

[Par. 61] PARZEN E. - "Mathematical considerations in the estimation of spectra" - Technometrics - Vol. 3, n° 2 - May 1961.

[Pee. 74] PEEBLES R.W., BUCK D.L., MANNING E. - "Simulation studies of a homogeneous computer network for data sharing" - CCNG Report E-19 - University of Waterloo - Ontario - Canada - March 1974.

[Pet. 62] PETRI C.A. - "Kommunikation mit automaten" - Thèse de doctorat - Université de Bonn - 1962.

[Pri. 69] PRITSKER A.A., KIVIAT P.J. - "Simulation with GASP II" - Prentice Hall - Englewood Cliffs - N.J. - 1969.

[Red. 73] REDDY Y.V., BRYAN R.H. - "DESPL/1 : A discrete simulation language based on PL/1" - SCSC - Summer Computer Simulation Conference - Montréal - Canada - July 1973.

[Reh. 68] REHMANN S.L., GANGWERE S.G. - "A simulation study of resource management in a time-sharing system" - FJCC 68.
[Ret. 74] RETTENMAYER J.W. - "SIMPL/1 : a simulation programming language" -
Winter Simulation Conference - Washington D.C. - January 1974.

[Ric. 73] RICHARDS F.M., WEATHERBEE J.E., WILLIAMS T. - "A validation
procedure for discrete digital simulation models" - 1973 SCSC -
Summer Computer Simulation Conference - Montréal - Canada -
July 1973.

[Rod. 72] RODRIGUEZ-ROSELL J., DUPUY J.P. - "The evaluation of a time sharing
page demand system" - Spring Joint Computer conference - 1972.

[Ros. 72] ROSE C.W. - "LOGOS and the software engineer" - Proceedings of
the FJCC - Vol. 41 - 1972.

[Sce. 67] "SCERT - System and Computers Evaluation Review and Technique" -
Comress Inc. - Washington DC - 1967.

[Sch. 65] SCHERR A.L. - "An analysis of time-share computer system" - Thesis
Project MAC - M.I.T (1965).

[Sea. 69] SEAMAN P.H., SOUCY R.C. - "Simulating operating systems" - IBM
System Journal - n° 4 - 1969.

[Sim. 61] SIMON H., ANDO A. - "Aggregation of variables in dynamic systems" -
Econometrica - Vol 20, n° 2 - April 1961.

[Slu. 68] SLUTZ D.R. - "The flow graph schemata model of parallel computation" -
Ph. D. Thesis - Massachusetts Institute of Technology - Sept. 1968.

[S3. 67] S3 : System and software simulator - Defense Document Clearinghouse -
AD 679269 - Sept. 1967.

[Tei. 66] TEICHROEN D., LUBIN J.F. - "Computer Simulation - Discussion of the
Technique and Comparison of Languages" - Communications of ACM -
Vol. 9, n° 10 - October 1966.

[Teo. 73] TEOREY T.J., MERTEN A.G. - "Considerations on the Level of Detail
in Simulation" - Symp. on the Simulation of Comp. System 1973.

[Van. 71] VAN HORN R.L. - "Validation of simulation results" - Management
Science - Vol 17, n° 5 - January 71.

[Vau. 75] VAUCHER J.G., DUVAL P. - "A comparison of simulation event list
algorithms" - CACM - Vol. 18, n° 4 - April 1975.

[Wal. 72] WALBAUM G., BEILNER H. - "SOUL : a simulation of OS under LASP" -
IBM Research RC 3810 - March 30 - 1972.
[Wat. 70] WATTERS L.J., VASILIK M.V. - "A Stochastic Network Approach to Test and Chackout" - Fourth Conference on Applications of Simulation - New York - Dec. 1970.

[Wya. 72] WYATT J.B., DEWAN P.B. - "A teaching Tool for Interactive Computer System Design" - ONLINE 72 - Conference Proceedings.