# Etude de la gestion des evenements dans une simulation a evenements discrets

Jacques Leroudier, Denis Renault, Michel Renault

► To cite this version:

Jacques Leroudier, Denis Renault, Michel Renault. Etude de la gestion des evenements dans une simulation a evenements discrets. [Rapport de recherche] IRIA-RR-246, IRIA. 1977, pp.27. hal-04716441

HAL Id: hal-04716441

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

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

ARCHIVES

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

ÉTUDE DE LA GESTION
DES ÉVÈNEMENTS
DANS UNE SIMULATION
A ÉVÈNEMENTS DISCRETS

Jacques LEROUDIER

Denis RENAULT

Michel RENAULT

Rapport de Recherche N° 246

Août 1977

24p
# ÉTUDE DE LA GESTION DES ÉVÉNEMENTS DANS UNE SIMULATION A ÉVÉNEMENTS DISCRETS

Jacques Leroudier, Denis Renault, Michel Renault

## Résumé :

Dans toute simulation à événements discrets, et en particulier dans tout langage de simulation (SIMSCRIPT, SIMULA, GPSS, etc ...), il existe un mécanisme, appelé noyau de synchronisation, qui gère le temps simulé. Ce mécanisme étant un passage forcé pour toute activité de la simulation liée au temps, il doit être particulièrement efficace si l'on veut éviter une dégradation globale des performances. C'est ce problème d'efficacité que nous étudions.

## Abstract :

Every discrete event simulation, and therefore every simulation language (SIMSCRIPT, SIMULA, GPSS, etc ...), contains a mechanism, called time flow mechanism or simulation executive, which manages the simulated time. Because every time activity in the simulation has to use this mechanism, it must be very efficient if we want to avoid a global degradation of performance. It is this problem we study in this paper.
ETUDE DE LA GESTION DES EVENEMENTS
DANS UNE SIMULATION A EVENEMENTS DISCRETS

Jacques LEROUDIER(1), Denis RENAULT(2), Michel RENAULT(2)

PRESENTATION

Dans toute simulation à événements discrets, et en particulier
dans tout langage de simulation (SIMSCRIPT, SIMULA, GPSS, etc...), il existe
un mécanisme, appelé noyau de synchronisation, qui gère le temps simulé. Ce
mécanisme étant un passage forcé pour toute activité de la simulation liée au
temps, il doit être particulièrement efficace si l'on veut éviter une dégra-
dation globale des performances. C'est ce problème d'efficacité que nous
étudions ici.

# 1 - LES EVENEMENTS D'UNE SIMULATION A EVENEMENTS DISCRETS

Dans cet article nous ne nous intéressons qu'à la <u>simulation à</u>
<u>événements discrets</u> par opposition à la <u>simulation continue</u> [1].

Dans une <u>simulation à événements discrets</u> les variables que l'on
désire connaître A TOUT INSTANT sont DISCRETES et s'appellent les variables
d'état. L'ensemble des valeurs que ces variables peuvent prendre constitue
<u>l'espace d'état</u> du système (système étant pris ici au sens large). Il s'ensuit
que l'espace d'état sera <u>dénombrable</u> ou <u>fini</u> (ce qui est toujours le cas dans
les applications réelles). Du fait de la définition de l'espace d'état , on
voit donc que chaque <u>changement d'état</u> ou <u>événement</u> se produit d'une manière
discrète dans le temps à des instants (t<sub>i</sub>)<sub>i&isin;N</sub>. Ces instants de changements
d'état sont appelés <u>temps d'occurrence d'événements</u> ou <u>dates d'événements</u>.

<footnote>(1) IRIA-LABORIA - BP 105 - 78150 LE CHESNAY</footnote>

<footnote>(2) IRISA - BP 25A - 35031 RENNES CEDEX</footnote>
## REMARQUES

a - Le temps est une *variable continue* et *non pas discrète*. On dit que *l'espace des temps est continu* (ce qui n'empêche pas de se limiter au cas discret, si on le désire).

b - On peut considérer dans la simulation des variables continues, à condition qu'elles ne soient pas incluses dans les variables d'état. C'est-à-dire qu'on accepte de ne pas les connaître à tout instant, mais *seulement aux temps d'occurrence d'événements*. Ces variables sont dites des variables annexes ou *déduites*.

c - Pour que la simulation soit possible, il faut, de plus, être capable de décrire les changements d'état ou événements par des *algorithmes*. En général, lorsqu'on simule le fonctionnement d'un système informatique, cette contrainte n'en est pas vraiment une. En effet, de par la nature du problème, un événement pourra être décrit dans le pire des cas par l'algorithme du système lui-même.

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 *quasi-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.

Par la manière de gérer le temps dans une simulation à événements discrets, on distingue les simulations *dirigées par une horloge* et les simulations *dirigées par événements*.
## 1.1 - *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. Le temps de la simulation est alors géré à partir d'un *échéancier* qu'on peut se représenter conceptuellement comme une liste linéaire d'événements. La tête de la 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.

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é.

## 1.2 - *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 deux apparaît à cette date [2]. On remarque que cette exploration pouvant s'avérer négative, il convient donc d'être particulièrement prudent dans le choix de l'unité de temps afin de minimiser le taux d'échec des recherches d'événements [3].

## 2 - *STRUCTURE D'UN NOYAU DE SYNCHRONISATION*

Dans cet article nous ne nous intéresserons qu'aux simulations dirigées par événements. Pour pouvoir réaliser une simulation, en plus de l'échéancier, il faut des procédures qui permettent de l'entretenir et de le
manipuler. L'ensemble de ces programmes et de ces structures de données s'appelle un **noyau de synchronisation**. Un tel noyau de synchronisation existe sous une forme ou sous une autre dans toute simulation à événements discrets et en particulier dans tout langage de simulation (SIMULA 67, SIMSCRIPT, GPSS, etc...).

## 2.1 - Représentation des événements et des activités

Ainsi que nous l'avons décrit au §1, un **événement** est un changement de l'état du système considéré. Lors d'une simulation l'occurrence d'un événement va donc provoquer l'exécution d'un programme qui réalise ce changement d'état (mouvements de files d'attente, bascullement de booléens, etc...). Chaque exécution de tels programmes représente une **activité** de la simulation. Il existe deux approches pour réaliser ce mécanisme.

a - Le noyau de synchronisation fournit des fonctions élémentaires permettant d'ordonnancer les événements dans le temps, par exemple par des ordres du type "EVENEMENT X A heure absolue". Lorsque l'événement considéré arrivera en tête de l'échéancier, on exécutera alors le **sous-programme** associé à l'événement qui décrit le changement d'état considéré dans le système (une **activité**). Bien entendu, ce sous-programme peut ordonnancer l'événement qui a provoqué son appel ou d'autres événements. On dit que le noyau de synchronisation (ou la simulation) est basé sur la notion d'événement (c'est le cas de SIMSCRIPT).

b - Chaque **activité** de la simulation, qui demeure toujours la description d'un changement d'état, donc d'un événement, est vue à un niveau logique comme "l'activité" d'un processus. Le modèle simulé est alors décrit comme un ensemble de processus progressant parallèlement dans le temps. Chaque processus représente une entité qui peut évoluer dans le temps au contraire des autres entités de la simulation qui demeurent passives. Du fait du parallélisme des différentes activités entre elles, elles ne peuvent plus être décrites par des sous-programmes (elles seraient
alors purement séquentielles), mais elles le sont par des co-routines [4] qui leur assurent une exécution en quasi-parallélisme. Le noyau de synchronisation fournit alors des ordres du type "ACTIVER PROCESSUS X A heure absolue". Dans une telle mise en oeuvre, on dit que le noyau de synchronisation est basé sur la notion de processus (c'est le cas de SIMULA).

Du point de vue du résultat, les deux approches sont bien évidemment équivalentes, mais elles diffèrent par leur facilité à décrire un problème donné. La première est bien adaptée à un problème posé en terme d'événements (par exemple dans un système informatique, la gestion des interruptions) ; la seconde est mieux adaptée à un problème posé en terme d'activités se déroulant en parallèle et elle permet généralement de rester à un niveau logique de description du système simulé. Par ailleurs, l'approche basée sur la notion de processus permet une dualité dans la description du système à simuler en permettant un échange entre entités passives et entités actives (processus). Par exemple, dans le cas d'un système informatique, on peut penser que les programmes sont des entités passives qui reçoivent des services des entités actives que sont les différentes unités du système (U.C., canaux, etc...). Mais l'on peut aussi envisager la situation duale : les unités recevant des services de chaque programme. Cette possibilité de dualité est très importante et permet de faire un choix sur le coût et les performances de la simulation projetée. Ce qui coûte cher dans une telle simulation, ce sont, bien entendu, les entités actives (processus) représentées par des co-routines, on visera donc à faire un choix qui en minimise le nombre. Ainsi si l'on veut étudier ce qui se passe sur une chaîne de montage pour une voiture défilant devant 50 postes, il sera plus efficace de considérer la voiture comme l'entité active qui sert 50 entités passives, plutôt que la situation duale.

Il est clair que l'efficacité d'un noyau de synchronisation dépend beaucoup de la structure et de la gestion de l'échéancier utilisé. A priori, cette efficacité va dépendre :
- de la structure de l'échéancier,

- des algorithmes d'entretien de l'échéancier,

- du nombre d'événements dans l'échéancier,

- de la distribution du temps entre événements dans l'échéancier.

Parmi ces paramètres, les deux derniers représentent l'environnement du noyau de synchronisation. C'est donc par rapport à eux qu'on doit étudier plus particulièrement l'efficacité du noyau, soit pour rechercher un optimum robuste (indépendant de l'environnement), soit pour mettre en oeuvre un mécanisme qui adapte le noyau de synchronisation à l'environnement.

Plusieurs structures de données peuvent être envisagées pour l'échéancier : liste linéaire, liste linéaire indexée, arbre binaire, arbre binaire équilibré.

Avec une liste linéaire, le temps de recherche dans la liste est proportionnel au nombre N d'événements dans la liste, tandis qu'avec un arbre binaire ce même temps est proportionnel à Log₂N. En effet, dans un arbre binaire on élimine à chaque test toute une partie des possibilités restantes (la moitié, si l'arbre est équilibré), alors que dans une liste on élimine seulement une possibilité. Aussi lorsque N devient grand, une structure en arbre peut devenir nettement plus efficace qu'une liste linéaire. Par ailleurs, des résultats obtenus par MYHRHAUG [5] indiquent qu'il ne convient d'équilibrer un arbre qu'au-delà de 400 événements dans l'échéancier, sinon le gain d'efficacité est négligeable comparé au temps supplémentaire de gestion introduit.

Lorsqu'on utilise une liste linéaire, on peut l'indexer pour éviter de balayer trop d'éléments. C'est-à-dire, qu'en se servant d'une table d'index, on peut entrer directement en des points au milieu de la liste, ce qui évite
le balayage des éléments du début de la liste. Une autre manière de voir cette structure de données est de considérer qu'on a autant de listes linéaires que d'index, ces sous-listes étant directement accessibles.

Nous supposons le lecteur familier avec ces différentes structures de données. Néanmoins devant l'importance qu'a dans cet article la liste linéaire indexée nous décrivons brièvement son fonctionnement dans le paragraphe qui suit.

## 2.2 - *Echéancier géré suivant une liste linéaire indexée*

Une liste indexée est une liste linéaire dans laquelle on a inséré des éléments fictifs (ici des événements fictifs) qui permettent, en se servant d'une table de pointeurs, d'entrer directement à l'intérieur de la liste. Ces pseudo événements, appelés *index*, sont séparés les uns des autres par un intervalle de temps constant appelé *pas d'indexation*. Pour qu'une telle structure soit efficace, elle doit être constituée de sous-listes dont les probabilités d'accès pondérées par leurs longueurs doivent être sensiblement égales. C'est-à-dire qu'une sous-liste souvent accédée doit contenir moins d'éléments (exploration plus efficace) qu'une sous-liste assez peu accédée. Le pas d'indexation, qui est un intervalle de temps, va donc dépendre non seulement de nombre d'événements dans la liste indexée, mais aussi de la distribution du temps entre événements. Nous reviendrons au paragraphe suivant sur ce problème d'efficacité.

Bien sûr, les *index*, et donc la table de pointeurs qui permet de les accéder directement, doivent être *gérés* de manière à suivre la progression du temps simulé. Lorsqu'un *index* (pseudo-*événement*) se trouve avoir une date d'occurrence inférieure au temps présent de la simulation, il doit être *chainé* dans la liste à une nouvelle date égale à :
$$ (1) \quad \text{ancienne date} + \text{NBI} \times \text{PAS} $$

où NBI est le nombre d'index et PAS, le pas d'indexation.

tandis que la table des pointeurs est mise à jour d'une manière circulaire.

Afin de clarifier les idées nous donnons sur la figure 1 un exemple de liste indexée où le nombre d'index est de 5 et le pas d'indexation de 10. Remarquons que pour gérer la liste dans le temps, il est nécessaire d'entretenir deux variables ICOURANT et ANTECEDENT, qui contiennent respectivement le numéro du pointeur pointant le premier index et la date du dernier pseudo-événement (index) dépassé par l'écroulement du temps. Pour des raisons d'efficacité, il est aussi bon d'entretenir un pointeur COURANT pointant sur l'événement en cours de traitement (définissant donc le temps présent de la simulation).

<figure><img src="image_3.png" /><figcaption>**Figure 1** : Liste linéaire indexée à 5 index et ayant un pas d'indexation de 10 unités de temps simulé.</figcaption></figure>
Notons par ailleurs que le dernier index est toujours un index de débordement.

Sur la figure 1, les liens non orientés représentent des doubles chainages (avant et arrière) : les événements sont doublement chainés en anneau (structure nécessaire lors d'une réorganisation due à un changement de pas d'indexation cf. §4.2). Les pseudo-événements sont marqués d'une croix et, d'une manière générale, les événements sont représentés par leur date d'occurrence. En fait, lors d'une mise en oeuvre réelle, un événement dans l'échéancier pourra être représenté par une structure de données analogue à celle décrite par la figure 2.

<table><caption>Figure 2 : Représentation d'un événement</caption><tr><td>Jeu de pointeurs dépendant de la structure de l'échéancier</td></tr><tr><td>nom (n°) de l'événement</td></tr><tr><td>date d'occurrence</td></tr><tr><td>pointeur vers le sous-programme ou la co-routine</td></tr></table>

## 3 - EFFICACITE D'UN NOYAU DE SYNCHRONISATION

Dans un premier temps, nous avons été guidés par les conclusions de VAUCHER et de DUVAL [5] sur le sujet. Comme ces deux auteurs nous jugerons de l'efficacité du noyau de synchronisation par rapport au temps d'exécution de la fonction qui permet d'ordonnancer dans le futur l'événement courant (représentant le temps présent de la simulation). Cette fonction (fonction HOLD SIMULA) est en effet représentative à la fois par son emploi, qui est très courant en simulation, et par son fonctionnement, qui résume bien ce
que l'on peut faire sur un échéancier. Elle prend l'événement en tête de l'échéancier et balaye l'échéancier pour trouver, selon la nouvelle date d'apparition de l'événement, sa place d'insertion.

Il est clair qu'une telle étude ne permet de juger de l'efficacité d'un noyau de synchronisation qu'en ce qui concerne les manipulations de l'échéancier par rapport au temps. C'est le cas le plus fréquent qui nous intéresse seul ici. Lorsque l'ordonnancement des événements se fait par rapport aux événements eux-même : "ORDONNANCER X AVANT (ou APRES) Y", un mécanisme distinct est alors mis en oeuvre pour accéder les événements dans l'échéancier. En général, ce mécanisme ne pose pas de problème et il peut être très efficace : on peut par exemple songer à une table de pointeurs (pointant les différents événements de l'échéancier) indicée par un numéro d'événement.

Les expériences que nous avons entreprises ont été réalisées sur un ordinateur CII 10070. Afin d'obtenir les meilleures performances possibles, les échéanciers et leurs fonctions d'accès ont été écrits en LP-70, sorte de langage d'assemblage algolisé (semblable à PL 360 pour les familiers du matériel IBM), tandis que les programmes décrivant l'environnement du noyau de synchronisation, et en particulier les programmes de tests, ont été écrits en FORTRAN.

Toutes les expériences ont été menées à N, le nombre d'événements (ou de processus) dans l'échéancier, constant et nous avons fait varier N d'une expérience à l'autre pour obtenir les courbes présentées dans cet article.

Toutes les mesures de temps ont été effectuées grâce à une horloge du CII 10070 battant au $\frac{1}{512}$ ème de seconde. La résolution de cette horloge étant de l'ordre de 2 millisecondes, elle est insuffisante pour mesurer un HOLD. Aussi pour avoir une précision satisfaisante (de l'ordre de la micro-seconde), la mesure porte-t-elle sur une boucle de 1000 HOLD. Le temps moyen d'un HOLD est alors obtenu en retranchant du temps mesuré par l'horloge le temps nécessaire pour effectuer la boucle (temps mesuré une fois pour toute) et en divisant par 1000 le résultat.
Chaque expérience consiste ainsi en une initialisation de l'échéancier à N événements fixés avec un temps inter-événement approprié, puis en une boucle de 1000 HOLD.

### 3.1 - *Influence de la structure de l'échéancier*

D'après [5] la meilleure structure pour un noyau de synchronisation semble être une liste linéaire indexée. Nos propres résultats, que nous présentons sur les figures 3, 4 et 5, semblent indiquer qu'il faille être plus prudent dans les conclusions.

Pour déterminer l'influence de la distribution du temps entre événements, nous avons considéré, dans nos expériences, les distributions suivantes dont les numéros d'ordre sont reportés sur les figures que nous donnons :

#### *Caractéristiques des distributions utilisées*

* 1 - exponentielle négative de moyenne 1

* 2 - exponentielle négative de moyenne 10

* 3 - uniforme entre 0 et 2

* 4 - uniforme entre 0 et 20

* 5 - constante égale à 1

* 6 - constante égale à 10

* 7 - discrète prenant d'une manière équiprobable les valeurs 0, 1 ou 2

* 8 - discrète prenant d'une manière équiprobable les valeurs 0, 1, 2, ..., 19 ou 20

* 9 - bimodale formée pour 90 % d'une gaussienne $\mu = 0.5, \sigma = 0.5$ et 10 % d'une gaussienne $\mu = 6.5, \sigma = 1$

.10 - bimodale formée pour 90 % d'une gaussienne $= 0.75, \sigma = 0.5$ et 10 % d'une gaussienne $= 3.25, \sigma = 1$
.11 - bimodale formée pour 60 % d'une gaussienne µ = 0.5, σ = 0.5
et 40 % d'une gaussienne µ = 1.75, σ = 1

.12 - bimodale formée pour 60 % d'une gaussienne µ = 0.25, σ = 0.5
et 40 % d'une gaussienne µ = 2.125, σ = 1

.13 - bimodale formée pour 90 % d'une gaussienne µ = 5, σ = 1
et 10 % d'une gaussienne µ = 65, σ = 2

.14 - bimodale formée pour 90 % d'une gaussienne µ = 7.5, σ = 1
et 10 % d'une gaussienne µ = 32.5, σ = 2

.15 - bimodale formée pour 60 % d'une gaussienne µ = 5, σ = 1
et 40 % d'une gaussienne µ = 17.5, σ = 2

.16 - bimodale formée pour 60 % d'une gaussienne µ = 2.5, σ = 1
et 40 % d'une gaussienne µ = 21.25, σ = 2

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

<figure><img src="image_5.png" /><figcaption>Figure 4</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 5</figcaption></figure>

Pour discerner plus particulièrement l'influence de la moyenne, nous avons considéré les mêmes distributions ayant tantôt une moyenne de 1 (distributions : 1, 3, 5, 7, 9, 10, 11, 12) tantôt une moyenne de 10 (distributions : 2, 4, 6, 8, 13, 14, 15, 16).

On constate sur les figures 3 et 4 que, si N est le nombre d'événements dans l'échéancier (les mots événements et processus seront employés indifféremment), on a bien un temps d'exécution de la fonction HOLD qui est proportionnel à N, dans un cas, et à Log₂N dans l'autre. On remarque que l'amélioration apportée par une structure arborescente est notable dès 50 événements dans l'échéancier.

En ce qui concerne la liste linéaire indexée (figure 5), les résultats sont assez différents. Les performances du noyau de synchronisation semblent dépendre uniquement de la moyenne des distributions et non pas des distributions
toutes entières. C'est pour cette raison que nous n'avons donné que 2 courbes correspondant aux moyennes de 1 et 10, les autres courbes étant très proches, pratiquement confondues. Pour expliquer la différence qui existe entre ces deux courbes, il faut comparer la moyenne du temps entre événements avec la valeur du pas d'indexation (intervalle de temps entre deux sous-listes).

Lorsque la moyenne est égale à 1 (dans ce cas la moyenne est égale au pas), les événements se trouvent en début de liste et sont donc mal répartis dans les sous-listes. On constate donc un comportement assez proche d'une liste linéaire simple. Lorsque la moyenne est de 10 (dans ce cas la moyenne est dix fois plus grande que le pas d'indexation) les performances sont bonnes lorsque le nombre d'événements est suffisant. On voit que si N est petit, la liste linéaire indexée est très mauvaise, car les pseudo événements, plus nombreux que les événements eux-mêmes, en pénalisent fortement la gestion.
Cependant, il semble qu'elle puisse devenir très bonne si l'on adapte la valeur du pas au temps moyen entre événements. Pour ce faire, nous avons étudié l'influence du rapport :

Pas d'indexation
temps moyen entre événements

pour pouvoir déterminer quelle était la valeur à donner au pas. Nous présentons
figures 6 et 7 les résultats obtenus.

3.2 - Influences de N et T̅
<figure><img src="image_7.png" /><figcaption>Figure 6</figcaption></figure>

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

La figure 7 est un grossissement de la figure 6 pour permettre de déterminer avec plus de précision la relation qui doit lier le pas d'indexation (PAS) et le temps moyen entre événements ($\bar{T}$) afin de se situer toujours sur l'enveloppe basse des courbes qui représente l'optimum à atteindre. Cette relation est :

$$ (2) \qquad \text{PAS} = \begin{cases} 100 \times \bar{T} & \text{si } N \le 8 \\ 20 \times \bar{T} & \text{si } 8 < N \le 12 \\ \bar{T} & \text{si } 12 < N \le 18 \\ 0,5 \times \bar{T} & \text{si } 18 < N \le 48 \\ 0,2 \times \bar{T} & \text{si } N > 48 \end{cases} $$

Il est possible d'implanter une telle fonction dans le noyau de synchronisation. Sa mise en oeuvre nécessite un compteur du nombre d'événements dans l'échéancier (N) et un estimateur de $\bar{T}$. Mais avant d'aller plus loin, il
nous faut contrôler que l'amélioration apportée par la relation (2) se conserve quelles que soient les distributions considérées. Dans ce but, nous avons répété nos premières expériences avec les 16 distributions que nous avions considérées précédemment. A chaque expérience la liste linéaire indexée avait les caractéristiques optimales déterminées par (2). Les résultats obtenus sont présentés sur la figure 8.

Si nous comparons ces résultats avec ceux des figures 3 et 4, nous voyons que nous pouvons en général obtenir de meilleures performances dès 50 événements dans l'échéancier.

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

Il ne faut pas oublier que l'optimisation qui vient d'être faite (le pas d'indexation en fonction de N et $\bar{T}$), l'a été d'une manière statique et à l'extérieur du noyau de synchronisation. Lorsque cette optimisation se
fera dynamiquement, il faut prévoir que ces performances seront sans doute dégradées par le mécanisme d'adaptation. C'est ce que nous étudions au paragraphe 4.

### 3.3 - Influence du nombre d'index

Dans toutes les expériences que nous avons présentées jusqu'ici, le nombre d'index de la liste linéaire indexée était fixé à 10, c'est-à-dire que la liste était constituée de 10 sous-listes. Il nous faut maintenant étudier l'influence de ce paramètre.

Le pas d'indexation étant optimisé, nous avons fait varier le nombre d'index de la liste de 2 à 100 (2, 5, 10, 15, 40, 70, 100). Les résultats obtenus sont présentés sur la figure 9. On remarque que le nombre optimal d'index se situe autour de 70. Il est bien évident qu'une telle liste indexée est très coûteuse, car elle nécessite l'entretien de 70 sous-listes. Les performances obtenues pour 15 index n'étant pas trop dégradées (figure 9), cette valeur constitue notre meilleur choix.

<figure><img src="image_10.png" /><figcaption>Figure 9</figcaption></figure>
Signalons, pour compléter cette étude, que nous avons considéré une liste comprenant 70 index et que nous avons fait varier la moyenne et la variance du temps entre événements. Nous avons alors constaté que l'optimum obtenu pour 70 index était peu sensible à ces variations de paramètres.

Les résultats présentés sur la figure 9 correspondent à une distribution entre événements exponentielle et de moyenne égale à 1. Pour une distribution gaussienne de moyenne 100 et d'écarts type variant de 1 à 10, la différence maximum constatée pour 200 événements est de 20 µs, c'est-à-dire négligeable.

Dans le reste de notre étude NBI sera donc fixé à 15 et nous ne nous en soucierons plus.

## 4 - ADAPTATION DU NOYAU DE SYNCHRONISATION A SON ENVIRONNEMENT

Le problème que nous avons maintenant à résoudre est celui de l'adaptation de la liste linéaire indexée à son environnement. Il faut en effet prévoir que le nombre d'événements et la distribution du temps entre événements peuvent varier au cours d'une simulation. On ne peut donc pas effectuer une optimisation statique.

Cette adaptation nécessite la présence de 4 outils dans le noyau de synchronisation :

- un compteur d'événements où est entretenu le nombre d'événements N présents dans l'échéancier. Ce compteur ne pose pas de problème.

- un estimateur de la moyenne $\bar{T}$. Nous verrons qu'il n'est pas possible d'utiliser un estimateur classique de moyenne.

- un mécanisme prenant la décision de changer le pas d'indexation (PAS).

- un mécanisme de réorganisation des index, lorsque le pas d'indexation a changé.
## 4.1 - L'estimation de $\bar{T}$

La moyenne $\bar{T}$ est évaluée grâce à un estimateur lissé exponentiellement, car nous désirons réagir rapidement à tout changement de moyenne. Une telle contrainte nécessite en effet l'emploi d'un estimateur qui "oublie" le passé, c'est-à-dire qui accorde plus de poids au présent et au passé proche qu'au passé lointain. Ce n'est bien évidemment pas le cas de l'estimateur classique :

$$ \bar{T} = \hat{E}(T) = \frac{1}{n} \sum_{i=1}^{n} T_{i} $$

où toutes les mesures $T_i$ ont exactement le même poids. L'estimateur que nous avons utilisé est défini par la formule de réccurrence :

$$ (3) \quad \begin{array}{l} Y_i = \alpha T_i + (1-\alpha) Y_{i-1} \quad \text{avec } 0 < \alpha \le 1 \\ \text{et } Y_0 = 0 \end{array} $$

et une formule de débiaisage de l'estimation :

$$ (4) \quad \bar{T}_i = \hat{E}(T) = \lambda_i Y_i \quad \text{où } \lambda_i = \frac{1}{1 - (1-\alpha)^i} $$

Notons que si la réccurrence est initialisée différemment ($Y_0 = X_0$) l'estimateur est alors sans biais.

Dans cette réccurrence, on voit que $\alpha$ est le poids accordé à la nouvelle mesure $T_i$ par rapport aux poids $\alpha(1-\alpha), \alpha(1-\alpha)^2, ..., \alpha(1-\alpha)^k...$ accordés aux mesures précédentes $T_{i-1}, T_{i-2}, ..., T_{i-k},...$. Tous les problèmes concernant cet estimateur et son adaptativité sont soigneusement étudiés dans [6], nous y renvoyons donc le lecteur.

## 4.2 - Mécanismes de décision et de réorganisation

La décision de changer le pas d'indexation doit se juger d'un double point de vue à la fois statistique et économique.
Statistiquement la moyenne estimée doit avoir significativement changé pour décider d'ajuster le pas d'indexation en se servant de (2). La solution rigoureuse de ce problème passe pas la construction d'un intervalle de confiance $[\bar{T} - \delta, \bar{T} + \delta]$ autour de $\bar{T}$ (donné par (4)) avec un niveau de confiance donné. Pour ce faire, il faut estimer la variance de l'estimateur de $\bar{T}$ utilisé. Comme cette variance peut elle-même varier dans le temps, il faut à nouveau employer, pour la variance, des estimateurs non classiques qui ont de "l'oubli". On montre dans [6] qu'on peut obtenir une estimation ayant ces propriétés grâce à :

$$ (5) \qquad \hat{V}(\bar{T}_i) = \frac{\lambda_i^2}{1 - \alpha^2 \lambda_i^2} \left\{ \alpha^2 [W_i - \lambda_i^2 (Y_i)^2] + (1-\alpha)^2 V(\bar{T}_i) \right\} $$

où $\bar{T}_i$ est la ième estimation de $\bar{T}$ obtenue à partir de (4), $Y_i$ est fourni par (3) et $W_i$ est une estimation "avec oubli" de $E(T_i^2)$.

Si $\bar{T}$ suit une loi de Gauss (voir [6]), on peut alors placer cette quantité dans l'intervalle $[\bar{T}_i - \epsilon\hat{V}(\bar{T}_i), \bar{T}_i + \epsilon\hat{V}(\bar{T}_i)]$ avec une confiance p donnée (pour $p = 84 \%$, $\epsilon = 1$).

Malheureusement la décision à prendre doit aussi être jugée d'un point de vue économique, en particulier du temps de calcul nécessaire. Après avoir implanté dans le noyau de synchronisation le mécanisme que nous venons de décrire, il est apparu que cette solution n'était pas viable (hormis l'utilisation d'outils matériels spéciaux). Nous proposons donc, pour prendre une décision, une méthode moins rigoureuse, mais aussi moins complexe. Elle consiste à considérer l'intervalle $[\bar{T} - c\bar{T}, \bar{T} + c\bar{T}]$ (ce qui évite d'estimer une variance) où $c$ est un pourcentage. Une telle approche peut sembler arbitraire (et elle est), elle se fonde néanmoins sur la constation que le pas d'indexation optimal est proportionnel à $\bar{T}$ (cf. relation (2) et figure 7). Il convient donc de juger les fluctuations de $\bar{T}$ proportionnellement à $\bar{T}$. C'est ce que nous avons fait.
Par ailleurs, il ne faut pas réorganiser la liste linéaire indexée trop souvent (le changement du pas d'indexation entraîne un réarrangement des index) pour ne pas perdre le bénéfice de l'optimisation entreprise [7]. Nous donnons sur la figure 10 le coût d'une réorganisation de l'échéancier pour une liste indexée composée de 15 sous-listes (l'optimum que nous avons choisi) et suivant deux méthodes : dans un cas on se sert des index eux-mêmes pour réorganiser la liste (coûteux s'il y a moins de 37 événements dans l'échéancier), dans l'autre non. La conclusion de cette expérience est qu'une réorganisation décidée après la détection d'une variation de la moyenne du temps entre événements coûte environ 2,5 millisecondes.

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

Etant donné ce coût et la valeur de α, le paramètre d'oubli du lissage (voir paragraphe suivant), nous avons décidé de ne pas réorganiser la liste avant d'avoir effectué au moins 20 mesures (20 appels de la fonction HOLD).
### 4.3 - Les expériences d'adaptation

Nous montrons sur la figure 11 que nous sommes effectivement capables de réagir à un changement de la moyenne du temps entre événements et que la rapidité d'adaptation est satisfaisante pour $\alpha = 0,20$.

<figure><img src="image_12.png" /><figcaption>Figure 11</figcaption></figure>

Les conditions de l'expérience étaient les suivantes. Nous avons fait varier le temps moyen entre événements et nous avons compté le nombre de mesures qu'il nous fallait prélever (nombre d'appels à la fonction HOLD) pour nous ajuster sur la nouvelle moyenne.

Notre noyau de synchronisation adaptatif étant réalisé, il nous faut maintenant montrer qu'il est plus efficace qu'aucun autre. Si l'on compare les figures 3, 4 et 8 le seul autre candidat sérieux à la première place est un noyau de synchronisation muni d'un échéancier arborescent. Pour comparer ces deux noyaux nous avons effectué l'expérience suivante. Nous avons considéré 6 distributions différentes du temps entre événements.
1 - exponentielle négative

2 - uniforme

3 - constante

4 - discrète

5 - première bimodale

6 - deuxième bimodale

A chaque test, pour chacun de deux noyaux de synchronisation considérés, nous avons effectué 30 changements de distributions en tirant au hasard à chaque fois la moyenne. Ces 30 changements ont été constitués sous forme de 5 cycles comprenant les 6 distributions envisagées.

Trois tests ont été effectués sur chacun des noyaux :

1 - cycle des distributions : 1, 2, 3, 4, 5, 6.

2 - même cycle mais avec des variations de moyennes différentes.

3 - cycle des distributions : 3, 2, 4, 1, 5, 6.

Pour pouvoir comparer les résultats, les changements de distributions et de moyennes ont été pris identiques lors des expériences sur chacun des noyaux.

Les résultats de la figure 12 montrent que le temps d'exécution d'une fonction HOLD sur un échéancier en arbre dépend des cycles des distributions et des moyennes employées, alors que pour notre noyau, un tel temps est pratiquement constant. Par ailleurs, nous constatons que notre noyau s'adapte effectivement et qu'il est plus efficace dès que le nombre d'événements dans l'échéancier est supérieur à 15.

Après ces expériences, il semble acquis que notre noyau de synchronisation adaptatif est plus efficace qu'un autre noyau statique, surtout pour les simulations où les événements dans l'échéancier sont assez nombreux. Il faut noter que dès 50 événements le gain de temps peut être de 25 % (cf. Figure 12).
<figure><img src="image_13.png" /><figcaption>Figure 12</figcaption></figure>

## 5 - CONCLUSION

Nous avons recherché une structure optimale de noyau de synchronisation. Les meilleurs résultats ont été obtenus pour les structures d'arbre binaire et de liste indexée. Cependant une étude plus détaillée de la liste indexée a montré que pour qu'elle soit vraiment efficace elle devrait s'adapter à son environnement, et plus particulièrement au nombre d'événements dans l'échéancier et au temps moyen entre événements. Le paramètre de la liste qui d'adapte à ces variables est le pas d'indexation, l'adaptation s'effectuant au moyen d'un compteur d'événement, d'un estimateur du temps moyen entre événement, d'un mécanisme de décision et d'un mécanisme de réorganisation, nécessaire lors d'un changement de pas.

Les conclusions que nous donnons ont été validées pour de larges plages de variation des paramètres. Nous pensons pourtant qu'il faudrait compléter cette étude si l'on désire faire des simulations comportant un nombre d'événements supérieur à 1000.
REFERENCES

[1] FORRESTER J.W. - "Industrials dynamics" - M.I.T. Press - Students's Edition - 1968.

[2] 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 - Mars 1974.

[3] BABICH A.F., GRASON J., PARNAS D.L. - "Significant event simulation" - Communications of ACM - Vol. 18 - n° 6 - Juin 1975.

[4] KNUTH D.E. - "The art of computer programming - Fundamental algorithms - Information structures" - Vol. 1 - Chapitre 2 - Adison Wesley Publishing Company - 1968.

[5] VAUCHER J.G., DUVAL P. - "A comparison of simulation event list algorithms" - Communications of ACM - Vol. 18 - n° 4 - Avril 1975.

[6] LEROUDIER J. - "Systèmes adaptatifs à mémoire virtuelle" - Thèse d'Etat - Université de Grenoble - Mai 1977.

[7] RENAULT D., RENAULT M. - "Etude d'un noyau de synchronisation pour une simulation à événements discrets" - Rapport de fin d'études - INSA de Rennes - Juin 1976.