Département d'informatique

Faculté des SciencesxactasyNaturelles

Université de Buenos Aires

INFORME TECHNIQUE

Introduction à la simulation de
Événements Discrets

Gabriel A. Wainer

96-005

Pavillon 1 - Rez-de-chaussée - Cité Universitaire

Buenos Aires
Argentine

[Link]
Title Introduction à la simulation des systèmes
événements discrets

AAuteurs : Gabriel A. Wentraîneur

E - mail gabrielw @[Link]

Rapportn.:96 - 00 5

Clé - Événements discrets Simulation et Modélisation, Parallèle

Simulation,Automates cellulaires.
A

Abstract: Dans ce travail, nous présentons une enquête sur différents mécanismes et
techniques de simulation d'événements discrets. Nous analysons plusieurs caractéristiques à propos de
modélisation et simulation, en prêtant une attention particulière à deux formalisms :
DEVS et Automates Cellulaires. Enfin, nous étudions des questions liées à l'augmentation
simulation de performance à travers des approches parallèles et distribuées.

Pour obtenir une copie de ce rapport, veuillez remplir votre nom et votre adresse et retourner cette page à :

Infothèque
Département d'Informatique - FCEN
Pavillon 1 - Rez-de-chaussée - Cité Universitaire
(1428) Buenos Aires - Argentine
TEL/FAX : (54)(1)783-0729
infoteca@[Link]

Vous pouvez également obtenir une copie par ftp anonyme à : [Link]/pub/tr

ou visiter notre site web :[Link]

Nom :..................................................................................................................................................

Adresse :................................................................................................................................................

............................................................................................................................................................
 Introduction à la simulation de systèmes d'événements discrets

Gabriel A. Wainer
Département d'informatique - FCEN
Université de Buenos Aires.
gabrielw@[Link]

Dans ce travail, nous présentons un rapport sur différents mécanismes et techniques de

simulation de systèmes d'événements discrets. On analyse des généralités concernant
modèles et simulation, et une attention particulière est accordée à deux formalisms : DEVS et
automates cellulaires. Enfin, des questions liées à la simulation sont analysées.
haut rendement en utilisant des solutions parallèles et distribuées.

Mots-clés : événements discrets, DEVS, simulation parallèle, automates cellulaires.

1. INTRODUCTION

En général, pour mettre en œuvre des systèmes automatisés flexibles, complexes et hautement précis,
nous devons construire des systèmes de test coûteux et complexes. Cette complexité rend la vérification difficile (ou
impossible), ainsi que la prévision de son comportement et de sa compréhension globale, indispensable pour
minimiser les risques dans le système développé. Pour atteindre ces objectifs avec une approche
Efficace en ce qui concerne les coûts, l'utilisation de méthodologies et d'outils de simulation est répandue.

Les avantages de la simulation sont multiples : le temps de développement du système peut être réduit,
les décisions peuvent être vérifiées artificiellement, un même modèle peut être utilisé plusieurs fois, etc. La
La simulation est un emploi plus simple que certaines techniques analytiques et nécessite moins de simplifications. Le
Le système à construire aura pour objectif d'aider les chercheurs à modéliser de tels phénomènes.
complexes.

L'objectif de ce travail est de servir d'introduction à certains concepts généraux sur

modélisation et simulation en utilisant certaines méthodologies. Nous présenterons un ensemble de techniques
importantes avec une utilité particulière dans la simulation de systèmes d'événements discrets. Le travail est basé
dans ceux mentionnés dans la bibliographie, et a pour intention de servir de matériel de base pour l'étude
en français. Il est destiné à diffuser les sujets dans ce domaine de la simulation, et il a été organisé en quatre
sections. Dans l'introduction, des concepts généraux de modèles, de systèmes et de simulation sont analysés. Dans le
Dans la deuxième section, on aborde les généralités du formalisme DEVS (un formalisme pour la simulation de
événements discrets). Une troisième section analyse un autre formalisme : les automates cellulaires. Dans la quatrième
section, les mécanismes de simulation parallèle et distribuée sont étudiés en détail, afin d'améliorer le
performance des simulations.

1.1. Systèmes, modèles et paradigmes

Pour commencer, nous donnerons quelques définitions. Tout d'abord, nous appellerons système une entity réelle ou
artificiel. En fait, il n'existe pas de définition de système qui ait une acceptation générale. On appelle système un
une partie d'une réalité, restreinte par un environnement. Elle est composée d'entités qui expérimentent
effets espace-temps et relations mutuelles. On dit aussi qu'un système est un ensemble ordonné de
 En ce qui nous concerne, nous distinguons deux interprétations du mot système :

un système réel est une combinaison d'éléments avec des relations structurelles qui s'influencent
mutuellement.
b) Un système dynamique est une construction formelle qui nous donne des concepts généraux de modélisation.
pour différentes classes de disciplines [Gia96].

Nous appellerons modèle une représentation intelligible (abstraite et cohérente) d'un système. Dans
Dans de nombreux cas, il n'est pas possible de résoudre un problème directement sur un système réel, c'est pourquoi nous raisonnons.
sur des modèles. Le processus de penser et de raisonner sur un système en mettant en lumière la réaction d'un modèle
modélisation des systèmes.

Exemple 1

Considérons la conception d'un circuit numérique. Si nous analysons la mesure des courants et des tensions
nous raisonnons sur un modèle électrique, en revanche si on fait une étude des fonctions booléennes
que réalise, on raisonne sur un modèle logique.

Pour étudier des systèmes complexes, l'idée est de commencer par faire un modèle du système que l'on souhaite
étudier, et on étudie des problèmes du système réel en étudiant le modèle.

Figure 1. Étapes dans l'étude d'un système par modélisation [Gia96]

Nous appellerons paradigme un ensemble de concepts, de lois et de moyens qui servent à définir un
ensemble de modèles. Les modèles sont construits sur un paradigme particulier.

Exemple 2

Considérons un langage de programmation algorithmique comme Pascal. Ici, nous utilisons le paradigme de
modélisation séquentielle/procédurale, afin de construire un modèle qui dans ce cas est un programme
modélisé par une activité séquentielle. De la même manière, le symbolisme des circuits logiques est un
paradigme dans lequel un schéma est le modèle d'un circuit numérique. Basé sur des portes logiques et un
ensemble de règles de connexion, nous permettons la construction d'un système de circuits logiques.
1.2. Modèles et simulation

Pourquoi fait-on des modèles des systèmes ? Pourquoi utilisons-nous la simulation ? La raison est que dans de nombreux ...
des cas ne peuvent pas être expérimentés directement sur le système à étudier, ou l'on souhaite éviter des coûts, des dangers,
etc. Actuellement, il existe une grande variété d'applications très complexes dans lesquelles des modèles sont utilisés
y/o simulation, qui vont de la fabrication à la conception de circuits pour ordinateurs, en passant par
applications militaires et étude d'expériences complexes. Les caractéristiques communes à ces systèmes
sa complexité et le manque d'outils d'évaluation de performance appropriés.

Nous distinguerons, alors, deux grands groupes de méthodes pour modéliser des systèmes complexes :

a) Analytique : les modèles sont basés sur le raisonnement. Ils sont généralement symboliques et permettent d'obtenir
solutions générales au problème. La solution est construite en utilisant les règles d'inférence reconnues
comme correctes dans le paradigme utilisé pour décrire le modèle, et elles sont obtenues sous une forme générale (dans
le sens qui est sous une forme symbolique). Les solutions particulières seront obtenues en remplaçant
les valeurs symboliques par leurs valeurs numériques. L'idée est qu'une fois la solution obtenue, elle est appliquée
une variable au modèle obtenu et de cette façon, on peut trouver des solutions particulières. Un
Un formalisme analytique très répandu est celui des équations différentielles.

Le problème est que si nous considérons des systèmes complexes, à quelques exceptions près, ils seront analytiquement
introuvables et numériquement prohibitifs à évaluer. Par conséquent, pour pouvoir utiliser ces méthodes pour les
les problèmes qui existent dans le monde réel doivent simplifier le modèle à un niveau tel que les solutions
obtenues peuvent s'éloigner de la réalité. Face à cette situation, la simulation offre une autre approche
de résolution de problèmes qui permet de traiter une certaine complexité.

B) Basés sur la simulation : il n'existe pas de solutions générales, mais ils cherchent des solutions
particuliers pour le problème. Si le problème est simple, l'utilisation de méthodes analytiques est préférable déjà
que nous permettent d'obtenir des solutions générales en toute sécurité. En revanche, si c'est complexe, en utilisant
la simulation permet d'essayer différentes conditions d'entrée qui ne seraient pas possibles à tester et à obtenir
résultats de sortie significatifs. Ainsi, on obtient des données qui peuvent être étudiées pour analyser quelque
comportement qui intéresse.

L'utilisation de la simulation permet une expérimentation contrôlée, une compression du temps (une simulation se
réalise en beaucoup moins de temps que le système réel qu'il modélise), et analyse de sensibilité. Une autre grande
l'avantage est que son utilisation n'affecte pas le système réel, qui peut continuer à être utilisé (ou ne pas exister). Enfin, la
La simulation est un outil efficace de formation. Certains problèmes existent dans l'utilisation de
simulation son le temps de développement, où les résultats peuvent diverger de la réalité
(validation précise), et pour reproduire le comportement du système simulé, il est nécessaire
collection extensive de données.

Définition :

La simulation est la reproduction du comportement dynamique d'un système réel sur la base d'un
système afin d'arriver à des conclusions applicables au monde réel [Gia96].

Par conséquent, la simulation est le processus de conception d'un modèle d'un système réel, et de conduite
experiments basés sur des ordinateurs pour décrire, expliquer et prédire le comportement du système
réel. En général, pour créer un simulateur, on suit les étapes suivantes :

a) Formulation du problème : à ce stade, un système réel est pris et il s'agit de le comprendre. Pour cela,
Tout d'abord, il s'agit d'identifier le problème à résoudre et de décrire son fonctionnement en termes d'objets et
activités dans un cadre physique. Ensuite, il s'agit d'identifier les variables d'entrée et de sortie de
système et sont catégorisées. Les variables d'entrée peuvent être des décisions (contrôlables) ou des paramètres
(non contrôlables). À cette étape, il s'agit également de définir des mesures de performance du système (comme
fonction de variables de sortie) et une fonction objectif (une combinaison de certaines des mesures).
 Ayant terminé cette spécification, il s'agit de construire une structure préliminaire du modèle.
interrelier les variables du système et les mesures de performance, en introduisant des présomptions et
simplifications appropriées. Enfin, une structure du modèle plus détaillée est construite,
identifiant tous les objectifs avec leurs attributs et interfaces.

b) Collecte et analyse des données d'entrée : à ce stade, le système réel est étudié pour obtenir
Données d'entrée par observation. Par conséquent, une observation directe et une collecte des attributs sont effectuées.
sélectionnés à l'étape précédente. En étudiant le flux des entités à travers le système, il s'agit de
les identifier avec des valeurs temporelles. Une autre question importante à ce stade est de choisir une taille de
échantillon statistiquement valide, et un format de données traitable par ordinateur. Enfin, il est décidé
quelles données seront considérées comme aléatoires et lesquelles seront considérées comme déterministes.

c) Modélisation : à ce stade, un modèle du système est construit avec les aspects que l'on souhaite
simuler. Pour cela, il y a deux phases.

Dans une première étape, il s'agit de comprendre le système, que ce soit en suivant une approche de flux
physique basé sur le flux d'entités à travers le système avec ses points de traitement et ses règles de
décision, ou une approximation d'événements (ou changement d'états), basé sur la définition de variables de
état interne suivi d'une description du fonctionnement du système lorsqu'un événement se produit. Dans un
la deuxième étape consiste à construire le modèle. Pour cela, on définit des objets, des attributs, des méthodes, dans le paradigme
choisi. Également à ce stade, un langage d'implémentation est choisi.

d) Mise en œuvre : à ce stade, une simulation du modèle est construite sur la base du langage choisi
qui peut être exécuté sur un ordinateur.

e) Vérification et validation du modèle : au cours des étapes précédentes, trois modèles ont été construits : le
conceptuel (spécification), logique (design) et informatique (code). La vérification est une affaire
de cohérence interne entre les trois modèles. La validation se concentre sur la correspondance entre le modèle et
la réalité. Sur la base des résultats obtenus lors de la validation et de la vérification, le modèle et son
l'implémentation doit être affinée.

f) Expérimentation de simulation et d'optimisation : à cette phase, une évaluation statistique des résultats est effectuée.
du simulateur pour déterminer un certain niveau de précision des mesures de performance. Si l'objet dans
l'intérêt passe par un comportement de période transitoire il faut faire attention à faire l'analyse sur
états stationnaires. Conception d'expériences de simulation basée sur la répétition de la
simulation avec les variables de décision à plusieurs niveaux.

g) Analyse des données de sortie : dans la dernière phase, les résultats de la simulation sont analysés pour
comprendre le comportement souhaité du système. Ces sorties sont utilisées pour obtenir une réponse à
comportement du système original.

Figure 2. Étapes dans l'étude des systèmes par simulation

 En fonction du niveau d'intervention de la personne qui décide sur le système réel, quatre sont définis.
niveaux d'utilisation des modèles pour la simulation :

. deexploration : une simulation est utilisée pour acquérir une meilleure compréhension des opérations du
système réel

la prédiction : un modèle est utilisé pour prédire le concept futur du système réel ;

. améliorations : utilisé pour optimiser la performance du système réel et étudier différentes alternatives
(par exemple, un système de production, de stocks, etc.);

. déconsidération : le système n'existe pas, et on utilise la simulation pour vérifier différentes solutions possibles
(par exemple, parce qu'un prototype ne peut pas être réalisé).

Dans tous les cas, nous sommes intéressés à avoir des modèles exécutables de systèmes, c'est-à-dire des descriptions
intelligibles sur lesquelles on peut exécuter des algorithmes en temps fini. Pour pouvoir construire un modèle
simulable, le système en considération doit obéir à deux principes fondamentaux :

Causalité : le futur ne peut pas influencer le passé. L'état du système à l'instant présent
tu es indépendant de tout ce qui peut être produit dans les heures futures à t.

Déterminisme : l'avenir du système peut être déterminé à partir de son état présent et son
passé. À chaque instant t, il existe une valeur positive telle que le comportement du système peut
se calculer jusqu'à t+e.

1.3. Catégories de paradigmes de modélisation

Pendant des siècles, le développement de systèmes dynamiques a été basé sur l'étude de modèles de
équations différentielles ordinaires et partielles. Celles-ci ont permis de modéliser avec succès les systèmes
dynamiques rencontrées dans la nature (en fait, les succès de la physique et cette ligne de recherche
étaient si grands qu'ils ont pénétré presque toute la pensée scientifique). Mais d'un autre côté, la technologie
moderna a permis à l'homme de créer des systèmes dynamiques qui ne peuvent pas être facilement décrits
par le biais d'équations différentielles ordinaires ou partielles. Comme exemples de tels systèmes nous pouvons
mentionner les lignes de production ou d'assemblage, les réseaux d'ordinateurs et de communications, les systèmes
de contrôle du trafic (dans les airs et sur terre), les systèmes de contrôle militaire, etc. Dans ces systèmes, l'évolution
dans le temps dépend des interactions complexes de plusieurs événements discrets et de leur temporalité, tels
comme l'arrivée ou le départ d'un travail, et le début ou la fin d'une tâche, etc. L' "état" de
de tels systèmes ne changent qu'à des instants discrets dans le temps au lieu de manière continue [Ho89].
La simulation apparaît comme une alternative pour étudier le comportement de ces systèmes complexes.

Une des premières applications de simulation avec des ordinateurs fut dans le projet Manhattan,
où l'on a étudié la diffusion aléatoire des neutrons pour le développement de la bombe atomique, en utilisant
méthodes de Monte-Carlo. L'impact de la technologie des ordinateurs a eu une grande influence sur le
développement de techniques de simulation, et actuellement il existe du matériel, des interfaces avec l'utilisateur et
outils de programmation qui ont influencé les méthodes théoriques existantes.

La grande variété de paradigmes de modélisation peut être classée selon différents critères :

En ce qui concerne la base de temps, il existe des paradigmes de temps continu, où il est supposé que le
le temps évolue de manière continue (c'est un nombre réel), et à temps discret, où le temps avance
par sauts d'une valeur entière à une autre (le temps est un entier).

En ce qui concerne les ensembles de valeurs des variables descriptives du modèle, il existe des paradigmes de
états ou événements discrets (les variables prennent leurs valeurs dans un ensemble discret), continus (les
les variables sont des nombres réels), et mixtes (les deux possibilités) [Gia96].
 Exemple 3

Équations différentielles : paradigme des variables continues à temps continu.

Équations aux différences : paradigme des variables continues à temps discret.
Machines à états finis : paradigme de variables discrètes à temps discret.
. DEVS et d'autres modèles d'événements discrets : paradigme des variables discrètes à temps continu. Un
un modèle d'événements discrets change d'états à cause d'un événement.

En ce qui concerne la caractérisation du problème à modéliser, les modèles peuvent être prescriptifs.
formulent et optimisent le problème (en général ce sont des méthodes analytiques) ou décrivent le
comportement des systèmes (ils sont généralement des méthodes numériques).

D'autre part, un modèle est dit déterministe si toutes les variables ont une certitude complète et
sont déterminées par leurs états initiaux et entrées. Le modèle est dit probabilistique dans le cas où
une réponse peut prendre une gamme de valeurs donnée l'état initial et ses entrées (si elle utilise des variables
aleatoires on dit que le modèle est stochastique). Dans un modèle probabiliste, les changements d'état de
les modèles se produisent par le biais de lois aléatoires : les entrées du modèle sont aléatoires (étant le modèle
déterministe), ou le temps d'arrivée des événements est aléatoire [Zei96b].

Selon l'environnement, les modèles sont autonomes (il n'y a pas d'entrées) ou non autonomes (il existe)
entrées). Les travailleurs indépendants évoluent en fonction du temps.

1.4. Simulation de DEDS

Les systèmes où les variables sont discrètes à temps continu sont appelés Systèmes
Systèmes Dynamiques d'Événements Discrets (DEDS - Systèmes Dynamiques d'Événements Discrets) en opposition aux Systèmes
Dynamiques des Variables Continues (CVDS - Systèmes Dynamiques à Variable Continue) qui se décrivent par
équations différentielles. Un paradigme de simulation pour DEDS suppose que le système simulé seulement
change d'états en points discrets dans le temps simulé, c'est-à-dire que le modèle change d'état en réponse à
occurrence d'un événement.

Exemple 4

Un cas typique d'un DEDS est un réseau d'ordinateurs. Des variables d'état peuvent être incluses pour
indiquer la longueur des files de messages, l'état des liaisons de communication (occupé ou libre),
etc. Les événements typiques peuvent inclure la réception d'un message sur un nœud du réseau, la transmission de
un message à un autre nœud, pannes de composants, etc.

Pour mettre en œuvre une simulation d'événements discrets, on utilise généralement :

a) Un ensemble de variables d'état discrètes.

b) Un planificateur qui contient une liste chronologique d'événements (ou de messages) à traiter. Un événement est un
changement d'état qui doit être effectué à une heure ti (le temps est continu).
c) Une horloge globale qui indique l'instant actuel de simulation ; c'est l'heure de survenance de l'événement qui
il est actuellement en cours de traitement.

Comparé aux systèmes à variables continues, fondamentaux en physique, la modélisation des DEDS est
un phénomène relativement récent. Bien qu'il appartienne au domaine de la Recherche Opérationnelle
(du point de vue où l'IO peut être considérée comme la technique des opérations et des événements des systèmes)
faits par l'homme), le développement des DEDS a également reçu un grand élan de la théorie du contrôle et
systèmes. En particulier, les concepts de dynamique (constantes de temps, temps de réponse, fréquence,
La contrôlabilité) est importante dans le développement de modèles et d'outils de DEDS [Ho89].
 Il est utile de distinguer entre deux types de DEDS : ceux à topologie fixe et dynamique. L'interaction entre
Les composants de topologie fixe peuvent être décrits par un graphe dans lequel les nœuds représentent des composants.
tes et les arcs représentent les chemins possibles d'interaction. De tels systèmes sont généralement représentés comme
réseaux de collage dans lesquels il y a un ensemble fixe de stations et des clients qui se déplacent d'une station à l'autre
station. Les itinéraires possibles des clients sont fixes (par exemple, systèmes de fabrication et réseaux de
communication). Dans les systèmes de topologie dynamique, les interactions sont arbitraires et dynamiques (Ex.:
scénarios de champs de bataille et systèmes de radio mobile). Les composants de ces systèmes peuvent
se déplacer dans toutes les directions et interagir avec les autres composants. Les systèmes de topologie
la dynamique ne sont généralement pas strictement DEDS car les composants peuvent se déplacer continuellement, sans
embargo, pour le but de la simulation, le modèle de mouvement physique dans le système est discrétisé en
le temps.

1.5. Paradigmes de spécification de modèles DEDS

Il existe une variété de paradigmes qui peuvent être utilisés pour spécifier formellement des systèmes dynamiques.
et ont une existence conceptuelle indépendante des langages de simulation qui peuvent être utilisés pour
implémenter les simulations. On ne peut pas dire qu'aucun des formalisme existants soit meilleur que
un autre pour représenter la variété de comportement des systèmes réels, car cela dépend de
divers facteurs, certains sont plus naturels et produisent des simulations plus efficaces. Il existe même
paradigmes génériques, mais il n'y a pas de consensus pour décider quel modèle a le plus grand potentiel. Parmi les
formalismes développés jusqu'à présent, nous mentionnons les suivants :

. Chaînes de Markov/modèles d'automates (dans ce groupe, nous incluons également les Réseaux de Petri et
machines à état étendues)
Modèles d'ondes
Modèles algébriques min-max.
. Modèles basés sur des ordinateurs (ex. : CSP)
. Modèles de processus semi-markoviens généralisés (GSMP - dans cette catégorie, nous incluons
tous les efforts liés aux langages de simulation d'événements discrets).

Avec le temps Sans temps

Logique Logique temporelle Machines à états finis
Réseaux de Petri
Algébrique Algèbre min-max Processus finiment récursifs
CSP
Performance Cadenas de Markov
Modèles de files d'attente

GSMP
Simulation
Stochastique <- Déterministe

Figure 3. Classification des outils de modélisation DEDS [Ho89]

Il existe une variété de raisons pour l'existence de formalismes de modélisation pour les DEDS :

i) La nature discrète des événements. Il est parfois possible d'analyser DEDS en utilisant
approximations continues (via modèles de diffusion ou en gérant exclusivement les taux au lieu des
parties constitutives), mais comme les états réels d'un DEDS sont intrinsèquement discrets, il est difficile
éviter la nature discrète du problème.

ii) La nature continue de la plupart des mesures de performance : les mesures de

le rendement des DEDS est souvent formulé en termes de variables continues, telles que
moyenne
 iii) L'importance de la formulation probabilistique : dans les systèmes DEDS, des perturbations surviennent
planifiés et/ou chutes. Cela n'implique pas qu'une approche totalement déterministe (par exemple, les
Les réseaux de Petri ou l'algèbre min-max) n'ont pas d'utilité, mais des extensions stochastiques doivent être faites.

iv) La nécessité d'une analyse hiérarchique : les opérations réalisées par l'homme opèrent à des niveaux
hiérarchiques. (Exemples : une usine a des plans annuels, trimestriels, mensuels, hebdomadaires et quotidiens ; les
les commandements militaires se divisent en niveaux de théâtre/flotte/bataillon/section). Ensuite, les détails
nécessaires pour modéliser et contrôler doivent être différents pour chaque niveau

v) La présence de dynamique : les modèles doivent capturer le comportement dynamique et transitoire de

les DEDS.

vi) Limite computationnel : dans les machines à états finis ou chaînes de Markov sans structure additionnelle
le nombre d'états physiques discrets du DEDS modélisé explose de manière combinatoire, ce qui
conduit à des exigences de calcul non réalisables. Par conséquent, le paradigme doit être orienté vers
performance, en distinguant entre modèles conceptuels et computationnels. L'exigence de calcul
de un modèle ne doit pas non plus croître de manière exponentielle avec sa taille [Ho79].

1.6. Modèles simulables

Pour résoudre un problème, il faut passer de la spécification dynamique à une spécification.

simulable, puis interpréter les résultats de la simulation dans le système dynamique (faire le passage
inverso). Le passage du système dynamique aux spécifications simulables imposera certaines restrictions
sur les ensembles de systèmes dynamiques.

Figure 4 - Relations de modélisation et de simulation [Zei90]

Comme nous le voyons, nous devons prendre en compte trois objets de base qui entrent en jeu :

a. Le système réel en existence, qui est vu comme une source de données. Le système réel est la partie du
monde réel dans lequel on s'intéresse et génère des données de comportement. Le système a certaines
variables observables et d'autres non. Lors de la création du modèle, des relations d'entrée/sortie doivent être établies.
de manière à ce qu'en effectuant une variation d'entrée, on puisse observer une variation de sortie semblable à celle qui
cela se produit dans le système réel. Si les éléments d'entrée sont discrets/continus, le modèle doit également
serlo.
 Figure 5 - Variables dans un système réel

L'objectif de la construction d'un modèle est le développement d'une représentation simplifiée et

observable du comportement et/ou de la structure du système réel. Un modèle est simplificateur, un filtre de la
réalité : elle ne la représente ni de manière exacte ni de manière complète. La définition du modèle doit inclure
de plus, les conditions de fonctionnement du système réel et les domaines d'application (il faut définir
ses conditions réelles d'utilisation).

b. Le modèle est un ensemble d'instructions pour générer des données comparables aux observables dans le
système réel. La structure du modèle est son ensemble d'instructions. Le comportement du modèle est
l'ensemble de toutes les données possibles qui peuvent être générées en exécutant les instructions du modèle.
Permet de générer ces données de comportement.

Le modèle de base spécifie le comportement de toutes les relations d'entrée/sortie qui se

construisent, et le modèle simplifié est une simplification (sur le nombre de composants ou le niveau
du paradigme) pour observer le comportement.

c. Le simulateur, qui exécute les instructions du modèle pour générer son comportement.

Ces objets de base sont liés par deux relations :

La relation de modélisation, qui relie le système réel et le modèle, et définit comment le modèle
représente le système ou l'entité modélisée. En termes généraux, un modèle peut être considéré comme valide
si les données générées correspondent à celles produites par le système réel dans un cadre expérimental de
intérêt (validité du modèle conceptuel).

La relation de simulation relie le modèle et le simulateur, et représente à quel point le simulateur est fidèle.
dor peut exécuter les instructions du modèle. Cela concerne l'exactitude avec laquelle l'ordinateur
traite les instructions du modèle. Cette exactitude est appelée la précision du programme ou du modèle
simulable [Zei90].

En réalisant un modèle d'un système réel, nous devons également prendre en considération d'autres éléments :

a) Cadre expérimental : c'est un ensemble restreint des circonstances sur lesquelles on observe le
système (le modèle est restreint à ce cadre). Le cadre doit être déterminé par le modélisateur, et définit
les conditions d'utilisation du modèle. Réflecte les objectifs du modélisateur qui ont un impact sur la
construction, expérimentation et validation du modèle.

b) Ordinateur : en mettant en œuvre le modèle sur l'ordinateur, il y a une réduction supplémentaire de la

capacité. C'est une simplification supplémentaire du modèle. Le modèle conceptuel est converti en un modèle informatique,
ce qui implique un nouveau filtre en raison de la limitation des langages de description et de l'efficacité du
processus d'exécution (durée, mémoire). Dans ce passage, des informations sont également perdues.
1.7. Comportement et structure

La théorie mathématique des systèmes fournit un cadre pour représenter et étudier les systèmes dynamiques,
distinguer entre la structure (constitution interne) d'un système et son comportement (son
manifestation extérieure).

Si le modèle ne permet que l'observation du comportement, on l'appelle modèle comportemental.

boîte noire. Dans ce cas, seules les entrées/sorties du modèle sont prises en compte. Lorsque
considérons le comportement d'un système, nous pouvons utiliser des représentations causales et empiriques. Les
empiriques sont des enregistrements réels de données (histoire dans le temps des variables) pris du système réel.
En revanche, les relations causales s'intègrent dans des unités qui peuvent générer des données empiriques.

Si le modèle représente la structure du système modélisé, on l'appelle modèle structurel ou boîte.

blanca. Dans ce cas, les composants du système réel sont précisés (qui peuvent être des modèles
comportementales simples). Ici entrent en jeu des concepts de décomposition (comme diviser un système
en composants) et couplage (comment combiner les composants pour le reconstituer). Un troisième
la relation fondamentale est la taxonomie qui concerne les variantes admissibles d'un composant et ses
spécialisations.

Exemple 5

Considérons la représentation d'un modèle de circuit. Nous pouvons spécifier deux classes de
modèles. Dans ce cas, le premier est comportemental, et le second est structurel. En général, pour
la simulation utilise ceux-ci, car ils permettent de construire un modèle complexe à partir de modèles simples.
En définissant les composants et les unions, on peut construire un modèle complexe basé sur des composants.
simples.

Figure 6. Modèles comportementaux et structurels.

Comme déjà expliqué, dans la grande majorité des cas, les modèles et leur mise en œuvre souffrent
simplifications due to the complexity of the system to be modeled. This complexity can be of two types:
. Qualitative : dépend de la sémantique du paradigme. Prend en compte la nature variable des
constituants du système.
. Quantitative : dépend du nombre de constituants du modèle. Est lié au système modélisé et
non au paradigme utilisé.

Si l'on souhaite réduire la complexité, il faut réduire l'une ou l'autre, que ce soit celle du paradigme, ou celle de
quantité de constituants dans la formulation du modèle.
 Exemple 6

Retournons au cas d'un modèle de circuits logiques. La complexité qualitative est faible, car il existe
un nombre petit et simple de composants : {0,1}, {ET, OU, NON}. Pendant ce temps, la complexité
quantitative dépend du circuit à modéliser (il pourrait y avoir des milliers de circuits pour un système donné).
Supposons maintenant que j'ai un circuit de N portes logiques. Si le paradigme change
modélisation, et au lieu de variables booléennes, on utilise "transformation d'enregistrements", je réduis la
complexité quantitative. Dans ce cas, des entiers, des opérations +, -, *, etc. sont manipulés. Cela augmente également
la complexité qualitative (dans le cas d'un enregistrement, des centaines de portes sont modélisées avec un seul opérateur
par le biais d'un paradigme plus complexe). Une autre façon de réduire la complexité quantitative serait par
moyen de description hiérarchique, utilisant des éléments de base, qui s'unissent pour former des modèles de plus haut niveau
niveau.

D'autre part, si nous considérons à nouveau le modèle d'un programme séquentiel, sa programmation en
l'assembleur a une complexité qualitative très basse (puisque l'ensemble des instructions est limité à quelques
combien d'opérations simples), mais quantitativement complexe. L'opposé se produit dans un langage de haut
niveau, qui est qualitativement complexe, et quantitativement simple.

2. FORMALISME DEVS

De nombreuses approches existantes pour modéliser des systèmes d'événements discrets cherchent à
décrire le phénomène en combinant diverses techniques, rendant le développement des très difficile.
simulations. Pour éviter ces problèmes, Zeigler [Zei76] a proposé un mécanisme de simulation
hiérarchique, connu sous le nom de DEVS (Discrete EVents dynamic Systems). Cette approche propose une
théorie de la modélisation des systèmes à temps continu utilisant la modélisation d'événements discrets. Permet
descriptionmodulaire des phénomènes à modéliser (approche modulaire) et attaque la complexité en utilisant
une approche hiérarchique.

L'approche fournit une manière de spécifier un objet mathématique appelé système. Cela se
décrire comme un ensemble cohérent d'une base de temps, d'entrées, de sorties et de fonctions pour calculer
les états et sorties suivants. Cette approche a ensuite été intégrée avec des notions de pro-
programmation orientée objet [Zei84, Zei90, Zei95]. Elle prend en charge la construction de modèles de manière hiérarchique
quica et modulaire. En plus d'un moyen pour construire des modèles simulables, il fournit une représentation
formel pour manipuler mathématiquement des systèmes d'événements discrets.

DEVS est un formalisme universel pour modéliser et simuler DEDS. On peut le voir comme une façon de...
Spécifier des systèmes dont les entrées, états et sorties sont constants par morceaux, et dont les transitions se
ils sont identifiés comme des événements discrets. Le formalisme définit comment générer de nouvelles valeurs pour les variables
et les moments où ces valeurs doivent changer. Les intervalles de temps entre les occurrences sont
des variables, ce qui apporte certains avantages : dans les formalismes avec une seule granularité, il est difficile de décrire
les modèles où de nombreux processus opèrent à différentes échelles de temps, et la simulation n'est pas
efficace car les états doivent se mettre à jour au moment où l'augmentation de temps est la plus faible, ce qui
il gaspille du temps lorsqu'il s'applique aux processus les plus lents.

Un modèle DEVS se construit sur la base d'un ensemble de modèles fondamentaux (atomiques), qui sont combinés.
pour former des modèles couplés. Les modèles atomiques sont des objets modulaires indépendants, avec
variables d'état et paramètres, fonctions de transition internes, externes, de sortie et d'avancement du temps.
Il existe deux variables d'état standard : phase et . S'il n'y a pas d'événements externes, le modèle reste dans le
phase pendant . c'est le temps restant jusqu'à la prochaine transition interne. S'il y a des événements externes, la
la transition externe fait que le modèle change de phase et , le préparant pour la prochaine transition
internes. L'état dans lequel on entre après un événement externe dépend de l'entrée, de l'état actuel, et
le temps écoulé dans cet état, permettant de représenter le comportement des systèmes temporels
je continue avec des événements discrets. Un modèle couplé spécifie comment les entrées et les sorties sont connectées.
les composants. Les nouveaux modèles sont également des modèles modulaires, et peuvent être utilisés pour assembler
modèles de plus haut niveau.

Le principe de la simulation dirigée par événements consiste à générer un planificateur. Celui-ci contient
à chaque instant, la liste chronologique ordonnée des événements à traiter dans le futur. Contient les événements po-
tencielles et représente un avenir possible du modèle. Dans ce cas, des modèles de base sont spécifiés à partir de
desquels on construit d'autres plus complexes, et comment accoupler ces modèles de manière hiérarchique. Le
la liste des événements n'est pas unique, mais est restreinte à chaque sous-modèle. La modélisation hiérarchique permet
la création d'une base de données de modèles, permettant la réutilisation des modèles créés et
vérifiés. De cette manière, la sécurité de la simulation est améliorée, réduisant le temps de vérification des
nouvelles simulations, et améliorant la productivité.

2.1. Modèles atomiques

Un modèle atomique est une spécification d'un modèle comportemental. Formellement, cette
la spécification peut être définie comme

M = <X, S, Y, int ext,

X : ensemble d'événements externes d'entrée ;

S : ensemble d'états séquentiels ;
Y : ensemble d'événements externes générés pour la sortie;
int : S -> S, fonction de transition interne, qui définit les changements d'état en raison d'événements
internes;
ext : QxX->S, fonction de transition externe, qui définit les changements d'état en raison d'événements
externes, Q est l'ensemble des états totaux du système spécifié par l'ensemble Q = { (s,e) / s
S, e [0,ta(s)] }, où e représente le temps écoulé depuis la dernière transition d'état avec
état s. Par conséquent, la fonction de transition externe dépend de l'état actuel et du temps
écoulé
S-> Y, fonction de sortie;
ta : S->R,+ fonction de durée d'un état ;
ta(s) : c'est le temps que le modèle reste dans l'état s s'il n'y a pas d'événement externe.

Un modèle atomique DEVS transite entre les états (S) via ses fonctions de transition. Quand non
il y a des événements externes, l'heure d'une fonction de transition interne est déterminée par la fonction de
passage de temps (ta) appliqué à l'état actuel. Le nouvel état du modèle est déterminé en appliquant la
fonction de transition interne ( int) à l'état ancien. Avant chaque transition interne, le modèle peut
générer un événement de sortie qui dépend de l'état précédent à la transition. Il peut également y avoir une
transition d'état lorsqu'il y a un événement d'entrée externe. La fonction de transition externe détermine
le nouvel état basé sur l'état actuel, le temps écoulé dans cet état, et l'entrée.
 Exemple 7

Dans la figure 7, nous voyons la séquence d'événements dans un système modélisé avec DEVS : s2= int(s1);
s3 int(s2), etc. Ce sont les transitions internes, qui se produisent lorsqu'il n'y a pas d'événements externes. Par
exemple, ta(s2) détermine l'heure de la prochaine transition interne en fonction de l'état s2. Cette heure du
le prochain événement est calculé sur la base de l'événement actuel. Ici y1= (s1), ..., sont les événements de sortie
générés. Ceux-ci s'exécutent avant les transitions internes. Lorsqu'un événement d'entrée est reçu
externa x1, la transition externe résultante dépend de l'état actuel, s4, du temps écoulé, e4, et le
événement d'entrée, x1, pour déterminer un nouvel état, s5 = ext(s4, e4, x1).

Figure 7 - Trajectoires dans un modèle atomique DEVS [Cho95]

Pour spécifier des modèles DEVS, il est commode de voir le modèle comme avec des ports d'entrée/sortie qui
interagissent avec l'environnement. Lorsque les événements externes sont reçus dans les ports d'entrée, la description
le modèle doit déterminer comment répondre. Par conséquent, un modèle atomique possède des ports d'entrée et de sortie
par lesquels toute interaction avec son environnement circule, ce qui facilite l'encapsulation. Ce concept
L'interface avec l'environnement permettra une construction modulaire de modèles plus complexes, facilitera la
validation sous-ensemble par sous-ensemble et la réutilisation des descriptions déjà effectuées
(encapsulation). Then, the simulatable description of an atomic model can be stored in a
bibliothèque pour faire un couplage avec d'autres modèles plus complexes.

Par conséquent, un modèle atomique doit contenir les informations suivantes :

L'ensemble des ports d'entrée par lesquels des événements externes sont reçus
L'ensemble des ports de sortie par lesquels des événements externes sont envoyés
L'ensemble des variables d'état et des paramètres : comme nous l'avons dit, deux variables sont généralement présentes.
phase (temps jusqu'à la prochaine transition interne).
La fonction d'avance de temps qui contrôle le timing des transitions internes (cette fonction
simplement la valeur de ).
La fonction de transition interne qui spécifie à quel état le système passera après le temps donné
par la fonction de la progression du temps.
La fonction de transition externe qui spécifie comment l'état du système change lorsqu'il reçoit
une entrée. L'effet est de mettre le système dans une nouvelle phase et , en le planifiant pour le prochain
transition interne ; le prochain état est calculé en fonction de l'état actuel et de la valeur de l'événement externe (qui
vient par un port d'entrée), et le temps écoulé dans l'état actuel.
La fonction de sortie qui génère une sortie externe avant une transition interne.

Chaque port d'entrée nécessite une spécification d'une transition externe, sous la forme de "quand
recevez x dans le port d'entrée p...". La fonction de transition interne peut être spécifiée dans un
description procédurale avec phases et leurs transitions. La fonction de sortie utilise des phrases de la forme "envoyer et
au port de sortie p

Exemple 8

Considérons un modèle de mise en mémoire tampon simple (fig. 8). Il y a trois ports d'entrée : entrée, pour recevoir
données d'entrée, prêt, à recevoir la reconnaissance du niveau inférieur, et arrêter pour le contrôle de flux de
processus de niveau supérieur. Le portsortie envoie des éléments vers le bas. Les variables e (temps
écoulé dans la phase actuelle), et (temps restant dans la phase actuelle), essentiels pour atteindre la modularité
en modèles d'événements discrets (on suppose que ces variables sont gérées par le simulateur abstrait).

_______________________________________________
Transition externe

Quand je reçois x à l'entrée du port

insérer(x, file)
sihay_uno(cola) /* Doit être transmis immédiatement */
temps_de_préparation /*Délai de préparation*/
Figure 8 - Un modèle de maintenir ENVOYER pendant e /* Changement de phase */
tamponnement simple sino
continuer

Quand je reçois prêt dans le port prêt

oui! vide (queue) /* Prendre l'élément suivant */
temps_de_préparation
maintenir ENVOYER pendant e
sinon
continuer /* Mettre à jour sigma */

Lorsque je reçois x dans le portpararcon, le temps écoulé e

ENVOYANT
temps_restant
pasivar

PASIVAyx
e = temps_restant
maintenir ENVOYANT par e
sino
continuer
_____________________________________________
Transition interne

ENVOIE /* Enlève le premier de la file puis

del tpo. de préparation */
resto(Cola)
passif
______________________________________________
Sortie

ENVOYER
envoyer d'abord (Queue) à la sortie du port
garde sur id_trab et il est simulé que le processeur travaille (maintenir occupé tpo_procesamiento, qui met
phase en occupé, et sigma en tpo_traitement). S'il arrive un autre travail, il l'ignore (continuer, qui met à jour
sigma pour refléter le passage du temps). Lorsque le processeur a terminé de traiter, il met l'identité du
Je travaille à la sortie, et je reviens à la phase passive. La première chose qui s'exécute est la fonction de sortie.
Après la fonction de sortie, la fonction de passage d'état est appelée, qui contient la phrase "pasivar".
que met le modèle en libre (phase=passive, sigma=inf). P a deux variables d'état : id_trab et
tpo_procesamiento. Tpo_procesamiento est fixe : c'est un paramètre du modèle. Ce processeur peut être
combiner avec d'autres composants pour créer des modèles d'architectures afin d'analyser leur performance. Le
Le modèle de base peut être affiné pour représenter des aspects plus complexes de l'opération.

Il est important de noter qu'il n'y a pas moyen de générer une sortie directement à partir d'un événement d'entrée
externe. Une sortie ne peut se produire qu'avant une transition interne. Pour qu'un événement externe
provoque une sortie sans délai, il faut "planifier" un état interne d'une durée zéro. Sigma garde
le temps restant jusqu'au prochain événement interne (la valeur de progression du temps à être produite par la
fonction de progression du temps.

Figure 10. Exécution du modèle de l'exemple 9

2.2. Modèles accouplés

Les modèles de base peuvent être couplés dans le formalisme DEVS pour former un modèle
multicomposants ou couplés, défini par la structure :

DN = <X soi-même
, Y , D, {Mi},
soi-même{Ii}, {Zij}, sélectionner>

D : ensemble de composants ; pour chaque i dans D U {self},

Mi est un modèle de composant de base ;
Ii est l'ensemble des influencés de i ; et pour chaque j dans Ii,
Zij est la fonction de traduction de la sortie i à j.
Select est une fonction, le sélecteur de tie-breaking (fonction de séquentialisation ou de priorité).

Cette structure est soumise aux restrictions selon lesquelles pour chaque i D

Mi = <Xi, Si, Yi, je, moi, tai>

c'est un modèle atomique ;
Ii D U {self}; i Ii;
Zmoi, X j -> Xj, Z moi-même
Y soi ;
Elle : Yi -> Xj.
sélectionner D->D / E { }, sélectionner(E) E.
 Pour tout j dans Ii, Zij est une fonction, traduction de sortie de i à j, Zij : Xi -> Xj. La connexion de i à j
est spécifiée en désignant j comme influencé par i fournissant une fonction de traduction Zij depuis le
état de i jusqu'au ensemble des entrées de j. Lorsqu'un événement interne se produit dans i, il envoie un signal au
composant j au même instant.

Un modèle couplé indique comment coupler (connecter) plusieurs modèles composants pour en former un nouveau
modèle. Ce modèle peut être utilisé comme composant, permettant une construction hiérarchique. Un
le modèle couplé contient les informations suivantes :

Ensemble de composants
Pour chaque composant, ses influences
L'ensemble des ports d'entrée par lesquels des événements externes sont reçus
L'ensemble des ports de sortie par lesquels des événements externes sont envoyés
. La spécification de couplage, consistant en
- Le couplage d'entrée externe qui connecte les ports d'entrée du modèle couplé à un ou ...
plus des ports des composants (dirige les entrées reçues par le modèle couplé aux modèles
composants désignés);
Le couplage de sortie externe qui connecte les ports de sortie des composants aux ports de sortie
du modèle couplé (quand une sortie est générée par un composant, elle peut être envoyée à un port de
sortie désignée du modèle couplé, et se transmettre à l'extérieur);
acouplement interne, qui connecte les ports de sortie des composants aux ports d'entrée d'autres
composants (lorsqu'une entrée est générée par un composant, elle peut être envoyée aux ports d'entrée
des composants désignés, en plus d'être envoyés à un port de sortie du modèle couplé).
La fonction de sélection, qui comprend les règles utilisées pour choisir lequel des composants
inminentes (ceux qui ont le moins de temps avant le prochain événement) exécutera son prochain événement.

Exemple 10

Figure 11 - Un modèle couplé

Faisons une description hiérarchique d'un modèle A5 (figure 11). Ici le modèle A1-A2 est dans une
forme modulaire, et peut être placé dans la bibliothèque pour être utilisé dans des descriptions plus complexes; le modèle
se transforme en un modèle de base. Pour construire ce modèle, nous suivons ces étapes : d'abord, on fait
une description comportementale des modèles atomiques A1, A3, A4, et ils sont stockés dans une bibliothèque. A
la suite consiste en une description structurelle du modèle couplé A2, stockage en bibliothèque, A2
se transforme en un modèle de base, et enfin la description structurelle du modèle couplé A5.
Tous les modèles créés sont stockés dans la bibliothèque.

Un modèle multicomposant DN peut être exprimé comme un modèle équivalent de base dans le
formalisme DEVS. Ce modèle de base peut être utilisé dans un modèle multi-composants plus important. Le
le formalisme est fermé sous couplage, comme requis pour la construction de modèles hiérarchiques. Le
exprimer un modèle multicomposant DN comme un modèle de base équivalent capture les supports par les
quels sont les composants qui interagissent pour atteindre le comportement général. Un modèle couplé regroupe
plusieurs modèles DEVS dans un composé qui peut être vu comme un autre modèle DEVS, en raison de la propriété
de clôture. De cette manière, un modèle peut être construit hiérarchiquement à partir de sous-modèles DEVS.
Un modèle DEVS qui n'est pas construit en utilisant un modèle couplé est un modèle atomique. Un modèle de
la base est un modèle atomique (description hiérarchique à deux niveaux) ou un modèle couplé (description
jerarchique à n niveaux). Un modèle couplé stocké dans une bibliothèque se transforme en un modèle de
base.

Exemple 11

Soit un modèle couplé qui consiste en un générateur, GENR, et un transducteur TRANSDR. Le

générateur génère une séquence d'identifiants de travaux espacés dans le temps. ("maintenir actif
tpo_entre_llegadas), qui ramène le modèle à la phase ACTIVE après chaque transition interne et la
planifie de commencer une nouvelle transition au moment donné par tpo_entre_llegadas (qui dans ce
le cas est constant, mais pourrait varier). Avant que la transition interne n'ait lieu, il y a une sortie de
un symbole id_trab. Comme GENR est un modèle DEVS, il peut être testé séparément. En principe, le
le générateur est un modèle autonome, par conséquent il n'a pas besoin d'une fonction de transition externe. Cependant,
on ajoute un port d'entrée, qui, lorsqu'il est stimulé, interrompt les sorties du générateur.

Le transducteur mesure deux indices : le débit et le temps moyen de réponse. Pour calculer
mesures de performance, le transducteur localise les id_trabs qui arrivent dans son port d'entrée arrivée dans son
liste_des_arrivées ainsi que leurs temps d'arrivée. Lorsque l'id_trab apparaît dans le port d'entrée
résolu, TRANSD le place dans la liste_des_résolus et calcule également le temps de traitement. TRANSD maintient
votre propre horloge locale pour mesurer les temps d'arrivée et de retour. Le formalisme DEVS ne permet pas que
l'horloge de la simulation est disponible pour les composants, donc les modèles doivent maintenir leurs
montres accumulant des informations sur le temps écoulé, en sigma et e.

MODÈLE ATOMIQUE : GENR MODÈLE ATOMIQUE : TRANSD

variables d'état : sigma = inf ; variables d'état : sigma = intervalle d'observation.
active actif
lista_llegada = lista_resueltos = ();
tpo_entre_llegadas = 10 horloge
_____________________________ ___________________________________
Transition externe Transition externe
avancer l'horloge locale h/pour qu'elle coïncide avec la globale
casier d'entrée caseport
passif ajouter le travail à liste_l'arrivée
sino : erreur stockage heure_d'arrivée
_____________________________ résolu : chercher le temps d'arrivée du travail
Transition interne heure totale - temps d'arrivée
ajouter le travail à liste_résolus
cas de phase continuer
activa : maintenir active pendant ___________________________________
temps_entre_arrivées Transition interne
pasive: /* cela n'arrive jamais */ casefase
_____________________________ activa : pasiva /* fin du intervalle d'observ. */
Sortie ___________________________________
Sortie
cas de phase casestade
activa: envoyer nom_au_hasard au rotation_moyenne = total_ta / trab_res
portsalida débit = trab_res / horloge
pasive: /* never happens */ autre : il n'y a pas de sortie

La spécification de l'interconnexion des composants pour construire un nouveau modèle a trois

parties
Ports d'entrée, qui spécifient comment les ports d'entrée du modèle couplé sont identifiés
formant ses composants;
. Ports de sortie : spécifiez comment les ports de sortie du modèle couplé sont identifiés en informant
à ses composants;
 . connexions internes : spécifie comment les ports de sortie des composants internes sont liés
dos avec les ports d'entrée des autres.

MODELE RACCORDÉ : EF

ARBRE DE COMPOSITION
GENR, TRANSD.

ACCOUPLEMENT D'ENTRÉE
EXTERNE
[Link]

ACOPLAMIENTO DE SORTIE
EXTERNE:
[Link]
[Link]

ACOPLAMIENTO INTERNE
Figure 12 - Modèle couplé EF
TRANSD.légado
[Link]

Pour expérimenter avec le modèle de processeur unique P, nous l'avons couplé directement avec le composant
EF pour former le digraphe EF-P. Noter qu'accoler un cadre expérimental et un modèle forme un système.
fermé, libre d'entrées. Ensuite, il n'y a pas de couplage d'entrée externe dans EF-P. Le couplage de
la sortie externe fait en sorte que la sortie du transducteur soit dans le Résultat d'EF-P. Le couplage interne est très
simple : les ports 'sortie de chaque composant s'acquièrent aux ports 'entrée des autres. Le cadre
l'EF expérimental peut s'acclimater à n'importe quel autre modèle de cette façon. Bien sûr, pour que cela ait
sens, le modèle doit utiliser son port d'entrée pour recevoir des identifiants de travail et produire
identifiants de travail dans votre port de sortie. Cela sera vrai pour une sélection de modèles de
architecture que nous discuterons. Utilisés de cette manière, le cadre expérimental générera des travaux pour le
architecture et mesurera son débit et son temps de réponse.

MODELE ACCOUPLÉ : EF-P

ARBRE DE COMPOSITION
EF, P.

ACOPLAGE DE SORTIE
EXTERNE :
[Link]
Figure 13 - Modèle couplé EF-P.
ACOPLAMIENTO INTERNO:
[Link]
[Link] -> [Link]

(P EF)

La fonction select contient des règles pour rompre les liens avec la planification. Ex. : dans EF-P, si le générateur
et le processeur ont des temps d'arrivée et de traitement égaux (ou harmoniques), ils auront la même
temps du prochain événement lorsque les deux seront prêts à envoyer un travail simultanément. Dans
particulier, si le générateur de tpo_entre_llegadas et le temps de traitement sont identiques, tous les se-
Certains travaux se perdent si le générateur exécute son prochain événement en premier : la sortie du générateur
trouve un processeur occupé, et on l'ignore. Pour éviter cela, la fonction select peut être définie de telle manière
que le processeur soit choisi comme composant imminent lorsqu'il existe la boucle.
2.3. Simulateur abstrait

La principale caractéristique de la modularité des modèles DEVS est garantie par le fait que la
La simulation est réalisée par un simulateur abstrait, qui est générique. Dans le concept de simulateur.
Abstrait, la simulation des modèles atomiques et couplés est réalisée par différents processeurs.
appelés simulateurs et coordinateurs. Fondamentalement, la simulation est déclenchée par la réception de
messages de simulation qui invoquent séquentiellement les sorties, transitions externes et transitions
internes planifiées par les fonctions de temps. En essence, un simulateur abstrait est une description
algorithme sur comment exécuter les instructions implicites dans les modèles DEVS pour générer leur
comportement.
La simulation d'un modèle structurel hiérarchique se fait avec trois classes de processeurs;

. Simulateur : traite des modèles atomiques. Un simulateur est associé à chaque modèle atomique avec le rôle de
mander l'exécution de différentes fonctions du modèle.
Coordonnateur : traite les modèles couplés. À chaque modèle couplé est associé un coordonnateur avec le
rôle de commander les contrôleurs des modèles qui constituent l'accouplement.
. Coordinateur principal : génère la simulation liée aux coordinateurs de plus haut niveau.

Chaque simulateur ne communique qu'avec le contrôleur de niveau supérieur (parent). Au sommet de la

À la hiérarchie se trouve le coordinateur racine qui distribue les messages à ses enfants. Un coordinateur racine
gère toute la simulation et est enchaîné avec le coordinateur du modèle couplé extérieur. La
La simulation se déroule par le biais de messages échangés entre les processeurs qui peuvent entraîner
informations concernant les événements internes et externes, ainsi que les besoins et la synchronisation. Les
les messages ont des champs pour la source d'origine, l'heure (contenant des horodatages locaux ou globaux,
selon l'utilisation), et un contenu cohérent de port/valeur, tous deux déterminés par des fonctions de
sortie du modèle atomique. Il y a 4 types de messages : *, X, Y, prêt.

La simulation s'effectue par passage de messages entre les différents processeurs. Un message a les
source
associé, pour les modèles atomiques).

Un message représente l'arrivée d'un événement externe. Inclut l'heure globale et vient du parent.
deux actions possibles face à un messageX:
Un coordinateur le transmet au simulateur via une méthode de traduction.
- Un simulateur appelle la fonction de transition externe du composant considéré, et répond avec
un message liste qui indique que la transition d'état est terminée et l'heure prévue du prochain
événement interne.

Le message * parvient à un processeur indiquant que le prochain événement interne à traiter le concerne.
- S'il s'agit d'un coordinateur, il transmet le même message à son fils avec le moins de temps possible.
événement, appelé enfant imminent. Cela signifie que le prochain événement interne sera réalisé dans son
environnement.
Le simulateur exécute ce message provoquant le changement d'état donné par la fonction de transition.
internes du modèle atomique, qui répondra avec un message et un message prêt (indique que la
la transition a été effectuée; elle entraîne l'heure du prochain événement).

Un message Yacarrea valeurs de la fonction de transition externe. Lorsque un coordinateur reçoit un

mensajeYde son fils imminent, consultez le schéma de couplage de sortie externe pour voir s'il doit
être transmis à son père, et son schéma de couplage interne pour obtenir l'enfant et ses respectifs
ports d'entrée auxquels il faut envoyer le message.

Un message indique au père que son fils a terminé ses devoirs. Lorsqu'un coordinateur a reçu
les messageslistede toutes les influences (dans le cas d'un message Y ascendant) ou les récepteurs (dans le
caso de mensaje X descendant), calcule le minimum de ses enfants (liste des temps des prochains événements) et
détermine son nouveau fils imminent pour quand le prochain message * sera reçu. Envoie aussi celui-ci.
nouveau minimum comme l'heure de son prochain événement interne dans un message prêt à son père.
 Figure 14 - Processeurs, variables utilisées et leurs messages.

Un modèle atomique est géré par un simulateur qui peut recevoir deux types de messages : * (indique
que le prochain événement interne est celui de son modèle); et X (arrivée d'un événement externe). Un simulateur
maintient plusieurs variables : l'heure actuelle, t ; l'état du modèle, s ; l'heure du dernier événement tl ; l'heure
du prochain événement interne, tn=tl+ta(s); le temps écoulé depuis le dernier événement, e=t-tl; et le temps
restante jusqu'au prochain événement interne, = tn- t = ta(s) - e.

Si un message * arrive, on vérifie si son heure correspond à tn (cela doit être le cas car un * n'arrive que au
simulateur si son modèle est imminent), et applique la fonction de sortie. Le contenu est mis dans un message
Y, et il l'envoie au niveau supérieur. La fonction de transition interne s'applique pour mettre à jour l'état s, et
les heures des événements sont mises à jour : tn=tl+ta(s) ; tl = tn. Enfin, un message prêt est créé, qui indique
que la transition d'état a été effectuée et que le nouveau tn reporte au niveau supérieur.

Un messageXprovoque qu'on vérifie si l'heure du message est correcteX [t1, tn] (cela devrait être ainsi
parce qu'un message doit seulement arriver après le dernier événement et avant le prochain interne). Il est mis à jour
le temps écoulé : e = t-tl. La fonction de transition externe est appliquée avec des valeurs mises à jour de e et
X;s = ext(s,e,x), y se actualise les heures des événements : tn=tl+ta(s) ; tl = tn. Enfin, un message est créé.
prêt, ce qui indique que la transition d'état a été effectuée et qui rapporte le nouveau tn au niveau supe-
rior.

La simulation commence par l'initialisation des états des modèles atomiques, en déterminant leurs tn. Ces
les temps se propagent vers le haut par des messages prêts, et établissent un chemin de sous-composants
inminentes depuis le modèle couplé supérieur jusqu'à un modèle atomique. Lorsque le coordinateur racine
reçoit un message de votre fils (le coordinateur du modèle couplé supérieur), il vous renvoie un *
marquant votre tn. Cela commence la simulation, car le * sera transmis vers le bas au simulateur
imminent. Cela entraînera une vague de messagesY vers le haut, une vague de messagesX vers le bas, et
une vague de messages prêts à remonter, le dernier étant transmis au coordonnateur racine lance la
prochaine ronde de simulation (traitement de l'événement interne suivant).

Le prochain événement dans le système se produira au plus tôt à l'un des temps planifiés, le moment
t+ ( c'est le minimum des temps restants, tai(si)-ei, entre les composants i de DN) en en choisissant un
en utilisant la fonction select. Soit i* ce composant choisi (imminent). Au moment t+ , juste avant que
j* change d'état, calculez sa sortie et *= i*(si*). Cette sortie est envoyée à chacune des influences de
i* en forme d'une entrée traduite : pour l'influencé j, l'entrée xi*j est Zi*j(y*). Le temps
écoulé dans n'importe quel composant i au temps t+ es e'i=ei+ . Un influencé j répond au
événement externe généré par i* appliquant sa fonction de transition externe, pour obtenir le suivant
état s'j = dext(sj, e'j, xi*j) et met son temps écoulé à 0. D'autres composants qui ne sont pas dans le
L'ensemble d'influence n'est pas affecté par l'activation de i* sauf que son horloge de temps écoulé
s'incrémente de . Enfin, le composant i* effectue sa transition interne en passant à l'état
si*'=dint(si*), et en mettant son temps écoulé à 0.

Exemple 12

Voyons l'association du simulateur abstrait avec le modèle EF-P, qui est montré dans la figure 15. Ici les
Les cercles représentent les processeurs et les rectangles les modèles associés.

Figure 15 - Simulateur abstrait pour le modèle EF-P.

Le cycle de simulation commence par un message * envoyé par le coordinateur racine au coordinateur de
modèle extérieur. Ici, C:EF-P reçoit le message * et le transmet à son fils imminent. Pour C:EF-P, le fils
inminent peut être EF (quand il est temps de générer un nouveau travail), ou P (quand un travail a été
procesado). Pour C:EF, GENR est l'imminent jusqu'à ce que TRANSD devienne imminent pour arrêter le
simulation. Lorsque S:GENR reçoit un message * envoie un message à son père C:EF (appliquant son
fonction de sortie pour produire un contenu avec portsaliday et une valeur id_trab). S:GENR aussi
provoque l'exécution de la fonction de transition interne GENR, et envoie un message avec le tn de
GENR. Pour C:EF, lorsque GENR est imminent, le messageY qui est mis dans le portsalidase se traduit en
un messageDans le portail et il est envoyé à votre influencé, TRANSD.
Pour C:EF, lorsque GENR est imminent, le message et ce qui apparaît dans le portsortie est un
messageDans le portail votre père EF. Comme EF est le fils imminent d'EF-P, le messageOui
envoyé à C:EF-P, où il sera envoyé comme un message X au simulateur de P, l'influencé de EF. Dans
dans ce cas, si P est libre, il devient occupé. Lorsque le temps de traitement est terminé, S:P
génère un message et (un id_trab dans le portsortie) qui va à son père C:EF-P et ensuite comme un messageX
un C:EF, l'influencé de P.

Pour C:EF, le seul récepteur d'un message Xen dans le port d'entrée est TRANSD, et traduit le port.
entradaaresuelto. Ensuite, le message qu'il envoie à S:TRANSD est le même que celui qu'il reçoit, sauf que le
le port est changé en résolu. Après avoir retransmis le message à tous les récepteurs, il les met sur sa liste
de attente.
 Voyons ce qui se passe avec un message prêt. Par exemple, si les fils de C:EF sont {(GENR 10),(TRANSD
1000)}, GENR est imminent, et le tn de C:EF est 10. Ensuite, C:EF envoie un messagelistocon temps 10 à
son père, C:EF-P. Celui-ci, ayant reçu tout sonlisto, envoie unlisto au coordinateur racine. En supposant
que leurs enfants sont {(EF 10)(P 15)}, la liste de C:EF-P contient tn 10. La liste se mande à la racine et revient
apparaissant comme un * à C:EF-P à 10 heures. Cela lance un nouveau cycle de simulation, dans ce cas avec
GENR générant un second travail.

Le simulateur abstrait est générique, c'est-à-dire qu'il fonctionne avec n'importe quel modèle de la classe ou de ses sous-classes.
L'interface entre le modèle et son simulateur est définie par des méthodes représentant des requêtes et des opérations.
que le simulateur fait au modèle. Les détails de la structure interne du modèle sont cachés dans cette
interface. Tout modèle peut être simulé par un simulateur s'il a les méthodes de l'interface. Le
suppression de toutes les informations liées à la simulation de la spécification du modèle, nous
permet de traiter les modèles comme des connaissances, c'est-à-dire de travailler avec une Base de Modèles.

3. MODÈLES CELLULAIRES

Les automates cellulaires sont un formalisme pour le modélisation de systèmes dynamiques complexes, de
variables et temps discrets (le temps, l'espace et les états du système sont discrets), créés
originellement par von Neumann et S. Ulam. Un automate cellulaire est un ensemble infini n-dimensionnel
des cellules situées géométriquement. Chaque point de la grille spatiale infinie (appelée une cellule) peut
avoir un parmi un ensemble de valeurs finies d'états, c'est-à-dire que chaque cellule a un état choisi de
un alphabet fini. Chacune contient le même appareil de calcul que les autres et se connectent entre elles de
forme uniforme. L'état des cellules est mis à jour simultanément et de manière indépendante des
d'autre part en étapes de temps discret. Pour cela, on définit le voisinage d'une cellule, qui est un ensemble de
cellules voisines. Ce voisinage est homogène pour toutes les cellules

Les états des cellules dans la grille se mettent à jour selon une règle locale. C'est-à-dire, l'état de
une cellule à un moment donné dépend uniquement de son propre état au moment précédent, et les
états de ses voisins à ce même moment. Toutes les cellules de la grille se mettent à jour de manière synchrone.
Puis, l'état de toute la cellule avance par étapes de temps discret. Les cellules mettent à jour leurs valeurs.
en utilisant une fonction de transition, qui prend comme entrée l'état actuel de la cellule, et un ensemble
finito de cellules voisines, qui sont à une distance limitée (le voisinage). L'uniformité dans l'espace
cela signifie que le système possède une invariance spatiale et temporelle.

Ils peuvent être utilisés pour modéliser une variété de systèmes discrets naturels, mais ils servent aussi à
comprendre de nombreux formalisme communs qui peuvent être vus comme des extensions de concepts de base. Se
ils sont souvent utilisés, tout comme les équations différentielles pour la modélisation de systèmes physiques. Il existe
automates pour modéliser la dynamique des fluides et des gaz, des colonies d'animaux, des modèles écologiques, entre autres
autres. Ils ont également une application en cryptographie. Ils permettent de spécifier des modèles de systèmes complexes avec
niveaux de description différents, ce qui permet de s'attaquer à une plus grande complexité que les équations
différentiels, permettant le modélisation et l'étude de systèmes très complexes.

Figure 16 - Un fragment d'automate cellulaire bidimensionnel.

 Ensuite, un automate cellulaire se caractérise en spécifiant trois paramètres : un ensemble d'états S,
un voisinage N, et une fonction de transition T. Les voisins d'une cellule sont déterminés à l'aide de
voisinage N (c'est une paire ordonnée finie d'entiers, qui s'ajoutent à la paire (i,j) pour obtenir les voisins). Un
état global à un instant t (une affectation à chaque cellule de l'ensemble S), change d'état dans l'ins-
tante t+1. Simultanément, pour chaque cellule, la fonction de transition T est appliquée aux états. Les
Les voisins d'une cellule sont ceux qui influencent son prochain état (ses influenceurs). Un automate
le cellulaire est un système discret autonome (sans entrées), bien qu'il existe des extensions qui permettent
entrées. D'autres extensions permettent que chaque cellule puisse avoir différentes règles, et dans ces cas-là
un automate cellulaire est inhomogène. Le modèle permet différentes règles et connexions (avec des applications à la
biologie théorique).

Formellement, un automate cellulaire est défini comme un ensemble CA=<S,N,T>. Soit a i,j
(t) la valeur de la
cellule i,j au temps t (automate cellulaire bidimensionnel). Ensuite, l'automate évolue selon
la fonction :

aij (t+1) = T[a

i-r,j-r (t),..., uni,j(t),..., un i+r, j+r (t)]

où T désigne la règle de transformation de l'automate, et chaque site est spécifié par un entier
aij(t) dans la plage [0,k-1] au moment t. Le paramètre de plage r spécifie la région affectée par un site
dé

L'automate spécifié par CA, Mca, se définit :

Mca=<Q, d>, où Q={q / q:IxI ->S} et d:Q->Q. d(q) (i,j)=T(q/N+(i,j)) pour chaque q Q e (i,j) IxI.

Noter que l'ensemble des états de Mca est l'ensemble des états globaux du système. Un état
global q est une affectation à chacune des cellules d'un élément de S, qui s'appelle un état local. La
la fonction d de Mca s'appelle la fonction de transition globale (et la T, la locale).

Les automates cellulaires sont discrets, réguliers et synchrones. Beaucoup des caractéristiques uniques de
la dynamique des automates cellulaires peut être liée à la mise à jour synchrone des états de
les cellules. Le comportement collectif semble être stable à toutes sortes de perturbations du modèle sauf
en abandonnant les mises à jour synchrones. L'organisation des sous-unités dans un modèle doit
approcher l'organisation des sous-unités dans le système à modéliser, et la dynamique du modèle doit être
une bonne approximation de la dynamique dans le monde réel.

Pour comprendre le système modélisé par l'automate cellulaire, un état initial est choisi et on observe
la séquence résultante des états. Dans de nombreux cas, le système atteint l'équilibre, indépendamment
des caractéristiques des valeurs initiales. En général, des changements dans les conditions initiales peuvent
provoquer des changements dans les résultats.

Bien qu'ils soient un outil puissant, les automates cellulaires ont certaines restrictions
importantes. D'une part, on suppose que dans l'espace des cellules, les cellules sont actives simultanément
(c'est un système parallèle), mais il y a une contrainte importante sur l'activité simultanée : toutes changent
de l'état simultanément. Un autre problème est que l'espace des cellules est infini. Pour qu'il puisse être
simulé, le modèle doit être limité à un nombre fini de cellules à chaque étape. La façon la plus simple de
le faire en limitant le modèle à une zone finie, ce qui fait perdre l'homogénéité : que fait-on avec
les bords ? Pour cela, on utilise généralement deux approches : soit l'état des bords est spécifié depuis
dehors, ou les extrémités sont connectées entre elles.

D'autre part, le grand nombre de cellules fait qu'en général, des calculs inutiles sont effectués.
Pour l'éviter, on utilise une approche qui détecte si une cellule ne peut pas changer d'état. C'est-à-dire
simple à réaliser, car une cellule ne peut pas changer d'état dans sa transition si aucun de ses voisins
Ils l'ont fait. Appelons un événement dans une cellule un changement d'état dans une cellule. Nous pouvons dire que dans
un automate cellulaire, les événements peuvent se produire dans un petit nombre d'entre eux (bien qu'il soit possible que
se produit simultanément dans toutes), et nous détectons si un événement se produira dans une cellule en regardant s'il y a eu
événements chez ses voisins.
 Il est possible de maintenir une liste des derniers événements, qui contient les cellules dont les événements se sont produits à t.
Sur cette base, nous pouvons déterminer dans quelles cellules des événements se produiront à t+1. Ensuite, nous simulons.
À chaque transition, nous vérifions s'il y a eu un changement d'état ; si c'est le cas, nous mettons la
cellule dans la liste des derniers événements pour t+1.

Pour commencer la procédure, il faut avoir un état initial. Si le modèle est fini avec un nombre
fin de cellules, nous pouvons mettre toutes les cellules dans la liste des prochains événements. Une meilleure
L'approche consiste à détecter des états spéciaux, appelés états latents, où si un élément s... S / si
une cellule et ses voisines sont dans l'état s à l'instant t, la cellule restera dans le même état à t+1 (ou
mer, la fonction T(s,...,s)=s). Alors il est simple de commencer la simulation, car seules les cellules qui ne sont pas
Dans un état latent, ils doivent être ajoutés à la liste des prochains événements.

De plus, s'il n'y a qu'un seul ensemble de cellules en état non latent, il est possible de simuler un modèle avec un
nombre infini de cellules.
Dans certains cas, pour les modèles finis, le traitement supplémentaire de la liste peut ne pas en valoir la peine. Pour
un modèle dans lequel toutes les cellules effectuent des actions tout le temps, il n'est pas bon de l'utiliser
cette stratégie. Pour voir la relation coût/benefice, il faut examiner le niveau d'activité du modèle (relation
entre cellules qui effectuent une activité sur le total des cellules). Ce niveau d'activité est une mesure
du parallélisme du modèle.

Bien que les automates cellulaires représentent un modèle de résolution élégant pour un grand nombre de
problèmes complexes, la recherche quantitative des propriétés fondamentales de l'évolution du temps et
L'état des automates cellulaires commence. Cependant, certains résultats ont été obtenus.
importantes. Par exemple, dans [Wol84] il a été montré que la plupart des automates cellulaires peuvent
se classer en quatre classes :

I - L'évolution de tous les états initiaux conduit, après un temps fini, à un état
homogène, où tous les endroits ont la même valeur.

II - L'évolution conduit à un ensemble de structures séparées stables ou périodiques.

III - L'évolution conduit à un modèle chaotique (exemple : systèmes physiques).

IV - L'évolution conduit à des structures complexes localisées, généralement métastables (exemple :

un modèle pour le Jeu de la Vie).

3.1. Modèles d'automates cellulaires asynchrones

Comme nous l'avons dit, un problème des automates cellulaires est qu'ils sont des modèles à temps discret, ce qui dans
Dans de nombreux cas, cela réduit l'efficacité des simulations et le degré de parallélisme du modèle. L'idée est de
avoir un modèle d'automates cellulaires avec des horloges asynchrones, et faire en sorte que le modèle soit géré par
événements. Les transitions d'état de chaque cellule sont indépendantes des autres de l'automate, et le
l'automate peut se comporter de manière très hétérogène. Si nous utilisons des horloges indépendantes, le temps de
L'itération pour chaque cellule peut être différente. Nous définirons un automate cellulaire asynchrone comme :

<Id, N, V, v0, f, F, T>

Ides le ensemble d'entiers de d-tuples, appelé un tableau de l'espace cellulaire. Un élément de Id

représente les coordonnées d'une cellule ou une cellule à cette coordonnée. L'entier positif s'appelle le
dimension de l'espace cellulaire. Nes un n-tuple d'éléments distincts d'Id, appelé l'indice de
voisinage. Avec N=(n1,..., nn) et étant donnée une cellule a, un élément de l'ensemble {(a+n1),..., (a+nn)} est appelé
une cellule de voisinage de a, et a est la cellule centrale de ce voisinage. L'ensemble consistant de
Les éléments de N s'appellent le voisinage. L'espace cellulaire est homogène, donc, pour toutes les cellules, Ves
un ensemble fini non vide, appelé un ensemble d'états. L'ensemble V a un élément, v0, dans le
quelle cellule est au repos, appelée un état latent. La fonction locale est un mappage de Vn à V et
satisfaire la propriété que f(v0,..., v0) = v0. L'état suivant de a est donné par st(a) = F(a, N, f, t),
où f est instantané appliqué au voisinage N de a au temps t. Le temps d'évaluation du changement
le prochain état de a est décrit par t'=T(a, N,t), où t'> t.
Un automate cellulaire asynchrone non déterministe peut être obtenu en introduisant une expérience
aléatoire et définissant une variable aléatoire dans l'espace d'échantillonnage de l'expérience.

La fonction locale non déterministe f est augmentée avec S, qui est une implémentation de la variable
aléatoire. La fonction locale s'écrit comme fS, où l'on peut penser à fS comme une fonction tabulée
selon S, ou si la variable aléatoire est discrète, S peut être considéré comme un argument à la
fonction. De la même manière, la fonction d'incrément de temps peut être écrite comme TS, qui peut être
une fonction tabulée dépendante de S, o, pour des variables continues ou discrètes aléatoires, S peut
se considérer comme un argument de la fonction TS. L'utilisation de S pour les variables aléatoires continues est valide déjà
que le temps est continu dans les automates cellulaires asynchrones.

3.2. Modèles NEVS

Zeigler [Zei90] a également défini une extension à son formalisme DEVS, qui permet de formuler des modèles
DEVS cellulaires. Un espace de cellules d'événement prochain (NEVS) est spécifié par un 4-upla,
<S,N,T,SELECT>. À nouveau, nous considérons une grille infinie de cellules. L'état de chaque cellule est un
par (s, ), avec un s en S, en R.+Une cellule en (s, ) reste dans cet état pendant un certain temps avant de
faire une transition induite par elle-même. Cependant, au milieu, un message peut arriver que
modifiez cet état, comme résultat de l'action d'une autre cellule. Ensuite, s et se appellent l'état séquentiel et
le temps restant de l'état. Une cellule c dans cet état au moment t est dite pouvoir être exprimée
comme elle est dans l'état séquentiel s et a été planifiée pour une transition au moment (o
t+ ).

Nouveau les voisins se calculent en ajoutant leurs coordonnées au voisinage prototype N (autre
ensemble de paires finies). Lorsqu'une transition d'événements se produit dans une cellule, elle et ses voisines font
un changement d'état comme le dicte la fonction de transition T. Ensuite, en contraste avec l'automate, T
prends une liste de paires (s, ) - tous les états de la cellule et de ses voisins avant l'événement - et produit une
liste de ces paires, donnant les états totaux de ces cellules juste après la transition.

En contraste avec l'automate cellulaire, la mise à jour d'un modèle NEVS a lieu à des instants de
calculo espacés irrégulièrement. Soit ti tel instant, et son successeur ti+1 calculé ainsi :

Imaginer l'état global en toi comme une liste de paires (s, ) avec les états totaux de toutes les cellules
en ce moment. Soit * le minimum de tous les dans la liste. Ensuite, ti+1=ti+ *. L'état global en ti+1
se calcule ainsi : appelez les cellules dont est égal à * dans l'instant toi. Ces cellules sont
planifiées pour un événement à t+1. S'il y en a plus d'une, appliquer SELECT et en choisir une, que nous appelons c*.
Cette cellule remplit la fonction de transition comme indiqué auparavant, aboutissant à un nouvel état glo-
bal. Les états totaux des voisins de c* sont calculés en utilisant T; l'état total des autres est converti
de (s, ) a (s, - *).

Exemple 13

Considérons le mouvement d'un seul corps dans un plan. Il existe un corps dans un plan, qui
avance, toujours vers la droite. Chaque cellule de l'automate a donc deux états possibles
(présence ou absence). S={0,1}. Une cellule passive ne deviendra jamais active d'elle-même; elle est représentée
par (0,inf). Il se déplace vers la droite, puis N = {(0,0), (1,0)}, qui ajoutés à (i,j) donnent les deux
coordonnées de la cellule (i,j) et de son voisin de droite.

La fonction de transition est très simple (pseudo-code)

. Mettre l'état séquentiel à 0. Passiver.
Prendre l'état du voisin (1) et planifier une transition en TEMPS_DE_DÉPLACEMENT.

Dans ce cas, il n'y a pas de conflits entre les sous-modèles, donc il n'est pas nécessaire d'inclure la fonction Sélection.
 La spécification des automates cellulaires ne place aucune restriction sur leur état global initial. Sans
embargo, il faut le faire pour que cela puisse être simulé sur un ordinateur. Une façon de le faire est de demander
un état local latent, dans lequel certaines cellules ne sont pas présentes (nombre fini). L'idée est que la majorité de
l'espace restera latent et restera ainsi, et il n'y aura qu'un nombre fini de cellules capables de quitter cela.
état à la fois.

Exemple 14

Considérons maintenant une extension du modèle précédent pour étudier la congestion du trafic. Le modèle
Le précédent ne précise pas ce qui se passe en cas de collisions. Supposons qu'au lieu d'un individu dans un
plan, nous avons des voitures dans une direction, et quand l'une bloque le chemin, celui qui veut avancer
changement de voie (de préférence vers la gauche). L'ensemble des états S={0,1} représente
absence/présence d'une automobile. Nous mettons N dans toutes les cellules au-dessus et en dessous du centre, pour que le
la voiture se déplace dans ces directions. Si N est ordonné dans l'ordre légal de passer :

Figure 17 - Voisinage de l'exemple

Un pseudocode de la fonction de transition interne est le suivant :

. Trouver la première cellule non occupée
Prendre cette cellule et planifier un événement en TEMPS_DE_MOUVEMENT.
. Mettre l'état propre à 0, désactiver, laisser les autres cellules non affectées (laisser leur état inchangé,
y leur soustraire leur temps_restant( *) pour mettre à jour les valeurs de temps).
Si aucun voisin n'est présent, replanifiez après TEMPS_DE_RECONNEXION. Laissez les autres cellules.
égal.

Ici, la fonction select détermine lequel de deux voitures se déplaçant vers le même carré en même temps le
logrera. Ensuite, l'ordre dans lequel les cellules sont choisies fait une différence. Un état initial dans ce
le modèle place un ensemble fini de cellules dans l'état 1, avec un temps time_left entre 0 et
TEMPS_DE_MOUVEMENT
les voitures effectuant des manœuvres pour bloquer les obstructions. Remarquer que pour rendre la simulation plus réaliste,
TIEMPS_DE_MOUVEMENT et TIEMPS_DE_REESSAI peuvent devenir des variables aléatoires, de
de manière à ce que les voitures se déplacent au hasard plutôt qu'à une vitesse constante.

Un état local s est un état latent lorsque les voisins d'une cellule sont en s au moment t,
ensuite la cellule sera en s à t+1. C'est-à-dire, s est latent si s=T(s,...,s). Tout état local du modèle de
la diffusion satisfait ce critère, car la moyenne d'une constante est la constante. Si au départ toutes
les cellules sont dans le même état latent, le système persistera dans le temps (état d'équilibre).
Les états globaux les plus intéressants sont ceux dans lesquels il existe des ensembles finis de cellules non latentes. En raison de
À la finitude du voisinage, ces états évoluent vers des états globaux avec la même propriété. Plus
Cependant, même si l'état latent est connu, la plupart des cellules qui sont dans cet état à tout moment
elles n'ont pas besoin d'être examinées par un simulateur. Cela rend la simulation calculable.
 Ensuite, une cellule peut changer d'état du moment t à t+1 seulement s'il y a une cellule dans son voisinage
ce qui a changé de t-1 à t. Le simulateur doit savoir à chaque étape quelles cellules ont changé pour
déterminer les cellules qui peuvent changer d'état au prochain pas dans ces circonstances. La
voisinage inversé, -N, est l'ensemble des images miroir des éléments de N (par exemple, (i,j) dans -N si et seulement si
(-i, -j) en N).

Lemme : une cellule (i,j) est dans le voisinage d'une cellule (k,l) si et seulement si (k,l) est dans le voisinage
inverso de (i,j). Une cellule peut changer d'état de t à t+1 si et seulement si elle est dans le voisinage inverse de
une cellule qui a changé d'état de t-1 à t. Ensuite, l'ensemble des cellules qui peuvent changer d'état
entre t et t+1 est l'union des voisins inverses de l'ensemble qui ont changé de t-1 à t.

Comme dans le cas des automates cellulaires, les états initiaux globaux doivent être restreints pour
calculabilité. Ici, le rôle de l'état latent est joué par l'état passif. Une cellule est passive si son
le temps restant est égal à inf. Un état global initial peut consister au maximum en un ensemble fini de
celles non passives.

4. SIMULATION PARALLÈLE

Jusqu'à présent, nous avons étudié différents formalismes pour les systèmes d'événements discrets, avec utilité
pour faire des simulations. Dans de nombreux cas, l'exécution de ces simulations est peu efficace. Le
Le principal problème de vitesse a des causes statistiques, en plus de la complexité des modèles à
spécifier. Pour qu'une simulation soit statistiquement significative, elle doit générer un nombre
suffisamment d'évolutions typiques du système. Pour éviter ces problèmes, on peut essayer d'utiliser
simulations qui ne nécessitent pas la génération d'un grand nombre de cycles de simulation. Certains
Des méthodes appelées de réduction de variance visent à réduire le nombre de répétitions nécessaires des cycles.
est proportionnel à la variance de l'estimation aléatoire mesurée dans un cycle donné. Ces méthodes sont
difficiles à préparer et que la réduction de variance qu'elles fournissent n'est pas très grande (une re-
duction d'un facteur de 2 à 5).

Un moyen évident d'obtenir une simulation plus rapide est de consacrer plus de ressources. En particulier,
nous pouvons accélérer une simulation en utilisant un système multiprocesseur au lieu d'un seul processeur. Comme
la plupart des simulations concernent des systèmes qui ont de nombreux composants fonctionnant en parallèle,
il semble raisonnable de supposer que la simulation exploite également le parallélisme inhérent du système. Le
La simulation parallèle d'événements discrets (PDES), souvent appelée simulation distribuée, se réfère
à l'exécution d'un programme de simulation d'événements discrets sur un ordinateur parallèle. L'utilisation de
des processeurs multiples semble être une approche prometteuse pour améliorer la vitesse, car la
la majorité des systèmes simulés qui se composent de nombreux composants opérant en parallèle, et ainsi se
exploite le parallélisme inhérent au système.

La définissation d'accélération est le temps qu'il faut à un seul processeur pour effectuer une simulation divisé.
temps que prend le système multiprocesseur pour faire la même simulation. L'accélération peut être envisagée
comme le nombre effectif de processeurs utilisés (l'accélération idéale avec N processeurs est N). Le
Le problème avec cette définition est de spécifier ce que signifie qu'un seul processeur fasse la simulation.
Prémissiblement, nous voulons un processeur ayant les mêmes capacités que ceux du système multiprocessus.
dor, mais ceux-ci peuvent ne pas avoir suffisamment de mémoire propre pour gérer toute la simulation. Ensuite, le
le monoprocesseur doit avoir la même capacité que les processeurs dans le système multiprocesseur mais
avec suffisamment de mémoire pour exécuter toute la simulation.

Pour obtenir une mesure précise de l'accélération réelle, le monoprocesseur devrait exécuter de la manière suivante
le plus efficacement possible. Cependant, en pratique, cela peut être difficile à déterminer. Une alternative
la pratique consiste à mesurer combien de temps il faut à un seul processeur pour exécuter la simulation distribuée, en mesurant le temps
total occupé de tous les processeurs pendant la simulation distribuée. La mesure résultante de
l'accélération devrait être supérieure à l'accélération réelle obtenue en distribuant la simulation. Aussi
nous pouvons être intéressés par l'efficacité de la simulation, c'est-à-dire, l'accélération divisée par le nombre de
processeurs utilisés (mesure l'utilisation effective des processeurs).
4.1. Formes de décomposition parallèle

Il existe diverses manières de décomposer une simulation pour qu'elle soit traitée sur plusieurs processeurs, dont
les mérites et les inconvénients seront discutés dans cette section.

a) Une approche évidente est de faire des répliques indépendantes d'une simulation existante dans
processeurs séparés, puis collecter les résultats pour une analyse statistique. Cette approche est
très efficace car aucune coordination entre les processeurs n'est nécessaire. Ensuite, avec N processeurs, le
l'accélération est virtuellement N. En général, distribuer les expériences sera plus efficace si le système
arrive rapidement à un état stable et les temps de simulation sont longs. Ils pourraient également être faits.
des courses indépendantes simultanément avec différents paramètres. La distribution des expériences
il se peut que ce ne soit pas possible en raison de contraintes de mémoire, car cela nécessite que tous les processeurs aient
mémoire suffisante pour contenir toute la simulation. De plus, cette approche ne permet pas
décomposition de problèmes complexes, ce qui dans le cas de simulations multiprocesseur permet si-
modélisations plus complexes et réalistes.

b) Une autre façon est d'appliquer un compilateur parallélisant à un programme séquentiel. Ceux-ci essaient de
trouver des séquences de code qui peuvent être exécutées en parallèle et les planifier sur différents processeurs.
C'est bon parce que c'est transparent pour l'utilisateur et peut s'appliquer à tout le logiciel de simulation séquentielle
existant, mais ignore la structure du problème et exploite une petite partie du parallélisme existant.

c) Une autre approche est les définitions distribuées, qui attribue des tâches de support aux processeurs.
individuels (par exemple, génération de variables aléatoires, collecte statistique, entrée/sortie,
manipulation de fichiers, génération de graphiques, supervision, etc.). Cette approche n'a pas de prise en charge.
mortel et est transparent pour l'utilisateur, mais n'exploite pas le parallélisme, offrant une quantité limitée de
accélération.

d) Rappelons que dans un modèle discret, on ne change d'état qu'à des moments discrets dans le temps.
simulé (un événement). On utilise généralement une liste d'événements avec tous les événements prévus en attente, et
une variable globale horloge pour connaître le progrès de la simulation. En utilisant des événements distribués
il maintient une liste globale d'événements, et lorsqu'un processeur est disponible, le prochain est traité
événement en temps simulé. Des protocoles sont nécessaires pour préserver la cohérence, car le suivant
L'événement dans la liste peut être affecté par les événements traités actuellement. Cette approche est
particulièrement adaptée aux systèmes de mémoire partagée, car la liste des événements peut être ac-
cédée par tous les processeurs. L'approche des événements distribués peut être raisonnable lorsque
il y a un petit nombre de processus et quand il y a un grand nombre d'informations globales utilisées par
composants du système.

e) La dernière approche est de décomposer le modèle en composants faiblement couplés.

Tant que le système simulé ne nécessite pas beaucoup d'informations et de contrôle global, cette approche
Il semble prometteur, car il a la capacité de tirer parti du parallélisme inhérent au modèle.
Cependant, cela nécessite une attention particulière lors de la synchronisation. Les processus communiquent par le passage de messages.
(bien que pas nécessairement dans une machine de passage de messages), qui incluent des horodatages qui
représentent le temps simulé d'un événement. Le système est généralement modélisé comme un graphe dirigé dans le
que les nœuds représentent des processus, et les liens représentent les interactions possibles ou les chemins des
messages.
 Figure 18 - Mécanismes de décomposition. (a) Réplication indépendante ; (b) Compilateur
paralélisante; (c) fonctions distribuées; (d) événements distribués; (e) décomposition du modèle.

4.2. Synchronisation dans les modèles distribués

En distribuant les composants du modèle, nous devons fournir des schémas de synchronisation. Les façons
Pour aborder ces questions, cela dépend de si la simulation est dirigée par le temps ou par les événements, et si la
la simulation est synchronisée (il y a une horloge globale et tous les processus doivent avoir le même temps)
simulé) ou asynchrone (chaque processus a sa propre horloge locale et le temps simulé pour différents
les processus peuvent être différents). À son tour, la simulation peut être gérée par le temps, dans laquelle l'horloge
avance d'un tick et tous les événements planifiés sont simulés, ou par événements, où l'horloge avance à
l'heure de la transmission du message simulé.

a) Simulación dirigée par le temps

Dans la simulation dirigée par le temps, le temps simulé avance par des incréments fixes (cliquez), et chaque
Le processus simule son composant à chaque tick. Les ticks doivent être courts pour garantir la précision, ce qui
que implique une plus grande durée de la simulation. La simulation peut être synchrone ou asynchrone. Si c'est
synchrone, tous les processus doivent terminer de simuler un tick avant que quiconque puisse commencer à
simuler le tick suivant. Par conséquent, après la simulation, il y a une phase de mise à jour de l'état et
communication. Lorsque la simulation est asynchrone, un processus peut commencer à simuler le prochain tick
dès que ses prédécesseurs ont terminé le dernier tick, et se synchronisent en envoyant des messages à
ses successeurs. Pour mettre en œuvre une horloge globale, on peut utiliser une approche centralisée (un processus
dédié à agir en tant que synchroniseur) ou de manière distribuée (avec un algorithme de diffusion
adapté).

La simulation asynchrone permet une plus grande concurrence, mais à un coût de communication plus élevé.
(comme un processeur ne peut pas simuler le tick suivant tant qu'il ne sait pas ce que ses prédécesseurs
ils ont terminé de simuler le dernier tick, vous devez recevoir un message de chacun de vos prédécesseurs pour chaque
tic). D'autre part, si la simulation est synchrone, une fois que l'horloge globale est synchronisée, il n'y a que
il est nécessaire de transmettre les messages en indiquant les interactions ou les mises à jour des états. Ensuite, si les états
changent moins fréquemment qu'à chaque tic, une horloge globale peut être plus efficace.

La simulation dirigée par le temps semble être moins efficace que celle gérée par événements car
il peut y avoir des ticks pendant lesquels il n'y a pas d'événements à simuler. Cependant, la
la simulation gérée par le temps évite la surcharge supplémentaire de synchronisation nécessaire. Ensuite, cela peut être
adaptée aux systèmes avec une topologie dynamique, et pour les systèmes dans lesquels beaucoup de choses se passent au
même temps.

b) Simulation dirigée par événements

Rappelons que dans les simulations dirigées par événements, le temps s'augmente d'un événement à l'autre.
suivant (l'événement représente un changement d'état), il peut alors avoir une plus grande accélération potentielle.
Cela peut aussi être :

1) Synchrone : l'horloge mondiale est réglée sur le temps minimum du prochain événement pour tous les processus.
Il peut y avoir un unique processus dédié à la synchronisation, ou être distribué. Il existe différentes méthodes pour
maintenir l'horloge mondiale :

2) Asynchrone : l'horloge locale de chaque processus est réglée sur le temps minimal d'événement pour ce processus.
Il a un potentiel de haute performance, car les processus passent moins de temps à attendre d'autres, et les événements
indépendants peuvent être simulés simultanément, bien qu'ils se produisent à des moments simulés différents.
Cette approche a été très diffusée parce qu'elle semble être celle à partir de laquelle on peut obtenir
plus grands degrés d'accélération. Dans les sections suivantes, nous étudierons en détail les algorithmes pour
synchronisation dans ce type de simulation.

Exemple 15

Supposons le cas de simuler des événements dans un réseau comme celui qui apparaît dans la figure 19. Dans le cas (a),
initialement, nous partons d'une horloge mondiale synchronisée (5) et tous les processus avancent simultanément
au tick suivant de l'horloge (6). Le degré de parallélisme s'améliore dans le cas (b), où la simulation est
asincrone. Ici, chaque processus peut avancer d'un tick s'il reçoit des signaux des processus prédécesseurs,
favorisant l'accélération dans la simulation. La situation s'améliore encore davantage dans le cas d'une simulation
dirigée par événement, car l'horloge mondiale (GVT) avance dirigée par événements et non par horloge, pouvant
accélérer encore plus le traitement des événements. Dans le cas où la simulation est synchrone, les processus
ils doivent se synchroniser entre eux jusqu'à ce que tous aient le même temps de simulation. Le plus haut degré de
L'accélération est réalisée dans le cas (d), où la simulation est dirigée par des événements et asynchrone, puis les
les seules dépendances sont données par les données de la simulation elle-même.

Figure 19 - Simulation parallèle dirigée par temps : (a) Synchronique ; (b) Asynchrone, et dirigée par
eventos: (a) Sincrónica; (b) Asincrónica
4.3. Processus physiques et logiques

Réanalysons le fonctionnement d'un simulateur d'événements discrets : chaque événement a un

L'émulateur retire l'événement ayant le plus petit timestamp de la liste et le traite, planifiant
de plus de nouveaux événements dans le futur simulé. Avec ce paradigme d'exécution, il est crucial que l'on soit toujours
sélectionnez l'événement avec le timestamp le plus bas. Si quelqu'un choisissait un événement avec un timestamp plus élevé, il pourrait modifier
variables d'état utilisées par la suite par l'événement de timestamp le plus bas, provoquant des erreurs de
causalité. En d'autres termes, certaines restrictions de séquence doivent être satisfaites pour que les calculs
soyez corrects.

La plupart des stratégies PDES existantes évitent de telles séquences en utilisant une méthodologie
orientée vers les processus qui interdisent strictement l'accès direct des processus aux variables de
état partagé en utilisant une approche asynchrone par événements. Le système modélisé, connu
système physique, il semble qu'il soit composé d'un ensemble de processus physiques qui
interagissent à différents points dans le temps simulé. Le simulateur est construit comme un ensemble de
processus logiques P0, P1,..., un par processus physique. Toutes les interactions entre processus physiques se
modélisent avec des messages envoyés entre les processus logiques correspondants.

Nous supposons que la simulation se compose de N processus logiques P0, ..., PN-1. Clocki fait référence au temps
simulé jusqu'à quel point Pi a avancé. Lorsqu'un événement est traité, l'horloge du processus avance
jusqu'à l'horodatage de cet événement. Si Pi peut envoyer un message à Pj pendant la simulation, nous dirons
qu'il y a un lien entre Pi et Pj.

Comme chaque processus logique contient une portion de l'état correspondant au processus physique que
Modèle, les variables d'état sont divisées en un ensemble disjoint, il faut veiller à ce qu'aucun processus
logique d'accéder directement à plus d'un état, ce qui est plus ou moins complexe selon l'application
cación. Par exemple, il n'est généralement pas difficile pour une simulation d'un réseau avec des files d'attente (un processus logique pour
chaque serveur). En revanche, dans les automates cellulaires, l'information doit être partagée entre les cellules voisines.
En l'absence de variables d'état partagées, l'approche la plus naturelle pour programmer cela
La simulation est 'émuler' la mémoire partagée en construisant un processus logique pour chaque secteur de la
grilla, et en envoyant des messages de "lecture et écriture" d'événements pour accéder à l'information partagée.
Cependant, la performance est faible car le surcoût du passage des messages est substantiel, et les
les processus de la grille peuvent se transformer en goulets d'étranglement. Une approche plus efficace est
dupliquer les informations partagées dans les processus logiques (cellules) qui en ont besoin. Comme l'état
partagé peut être modifié, un protocole est nécessaire pour assurer la cohérence entre les diverses
copies de l'état partagé. Cette approche peut être efficace pour atteindre de bonnes performances ; sans
l'embargo complique significativement le codage de l'application, rendant difficile sa compréhension et
maintenance.

Pour garantir qu'il n'y a pas d'erreurs de causalité, la contrainte de causalité locale doit être respectée :
Une simulation d'événements discrets consistant en des processus logiques obéit à la contrainte de causalité.
local si et seulement si chaque processus logique traite les événements dans un ordre non décroissant de timestamps. Le respect de
Cette restriction est suffisante bien qu'elle ne soit pas nécessaire pour garantir qu'il n'y a pas d'erreurs de causalité. Peut
il n'est pas nécessaire, car deux événements au sein d'un même processus logique peuvent être indépendants, dans
dont le traitement hors séquence ne provoque pas d'erreurs de causalité.

Figure 20 - Erreur de causalité par synchronisation entre processus logiques.

L'exclusion d'états partagés peut provoquer des erreurs de causalité. Considérons deux événements,
E1 dans le processus logique LP1 avec un horodatage de 10, et E2 dans LP2 avec un horodatage de 20. Si E1 planifie un nouveau
événement E3 pour LP2 qui contient un timestamp inférieur à 20, E3 pourrait affecter E2, par conséquent se
nécessite une exécution séquentielle des trois événements. Si l'un d'eux n'a pas d'informations sur les événements
pourraient être planifiés par d'autres événements, on serait contraint de conclure que le seul événement sûr pour
Le processus ayant le plus ancien timestamp provoque une exécution séquentielle.

Du point de vue du système physique, la cause doit toujours précéder l'effet. Ces relations
la cause-effet du système physique se transforme en contraintes de séquence dans le simulateur (et le
le simulateur peut avoir plus de restrictions qui découlent de la manière dont il a été programmé). La
la responsabilité du mécanisme de simulation est de s'assurer que ces restrictions ne soient pas violées au
exécuter en parallèle. Nous pouvons décider si E1 peut s'exécuter simultanément avec E2, mais comment
savons-nous si E1 affecte E2 sans avoir exécuté la simulation d'E1 ? C'est le dilemme fondamental dans les
stratégies de PDES. La séquence dans laquelle E1 affecte E2 peut être une séquence complexe d'événements,
et dépend des timestamps des événements.

Les mécanismes PDES tentent de fournir des solutions à ce type de problème. En général, deux sont utilisés.
approximations : conservatrices et optimistes. Les conservatrices évitent la possibilité d'erreurs de
causalité, basé sur une stratégie pour déterminer quand il est sûr de traiter un événement. Par un autre
d'autre part, les approches optimistes utilisent une solution de détection et de récupération : les erreurs se
ils détectent et invoquent un mécanisme de rollback pour se récupérer.

4.4. Mécanismes conservateurs

Les premiers mécanismes de simulation distribuée étaient conservateurs. Le problème de base de

Ces mécanismes servent à déterminer quand il est sûr de traiter un événement. Plus précisément, si un processus
il a un événement non traité avec un horodatage (et aucun autre avec un horodatage inférieur), et il peut
déterminer qu'il est impossible de recevoir un autre événement avec un timestamp inférieur, l'événement peut être traité de
de manière sûre, car il n'y aura pas de violation de la restriction de causalité.

Dans l'algorithme présenté par [Cha79], un processus avec un message non traité dans tous ses liens
En entrant, il met son horloge locale à la valeur minimale de tous les timestamps et traite tous les messages avec celle-ci.
horodatage. Tous les messages futurs auront des horodatages ultérieurs à l'heure locale car ils arrivent en
ordre chronologique à chaque lien. La procédure se répète tant qu'il y a des messages non traités dans
les liens entrants. Si un lien avec le plus bas timestamp n'a pas de messages, alors il est bloqué
(parce qu'il peut recevoir un message avec un horodatage inférieur à tous les autres).

Cette approche peut provoquer un étranglement mortel s'il existe un cycle de processus bloqués. En général,
s'il y a relativement peu de messages d'événements non traités par rapport au nombre de liens dans le
rouge, ou si les événements non traités sont regroupés dans une portion du réseau, l'étreinte mortelle peut se produire
très fréquemment [Cha81].

Exemple 16

Supposons une simulation avec quatre processus logiques comme dans la figure 21. Supposons que P1
envoyer le message (3, m1) à P2, P3 envoie le message (2,m2) à P2, et P3 n'a pas de messages non traités
comme on le voit dans la fig. 21a. P2 traite le message (2,m2) et produit (5, m3) qui est envoyé à P4, comme on le voit
dans la fig. 21b. À ce stade, P2 ne peut pas traiter le message (3,m1) car P2 est bloqué par P3.
P3 est également bloqué par P2 : par conséquent, il y a une étreinte mortelle.

(a) (b)

Figure 21. Deadlock dans les approches conservatrices

4.4.1. Éviter l'étreinte mortelle

Une façon de résoudre le problème de l'existence d'une étreinte mortelle consiste à les éviter en spécifiant
estatiquement des liens qui indiquent quels processus peuvent communiquer avec d'autres [Cha79]. Nous savons que
pour déterminer quand il est sûr de traiter un message, la séquence de timestamps dans un lien doit être
croissant. Par conséquent, la date et l'heure du dernier message dans un lien entrant est une limite inférieure dans le
timestamp de tout message suivant. L'idée est d'exploiter cette information et d'utiliser des messages nuls,
qui ne correspondent à aucune activité dans le système physique.

Un message nul de PA à PB est une promesse qu'aucun message avec un horodatage inférieur ne sera envoyé.
que le message nul. Comment sont déterminés les timestamps des messages nuls qui sont envoyés ? L'horloge
De chaque lien d'entrée fournit une limite inférieure sur le timestamp de l'événement suivant non traité. Ce
La limite d'entrée peut être utilisée pour déterminer une limite inférieure sur le timestamp du message suivant
de sortie. Chaque fois qu'un processus termine de traiter un événement, il envoie un message nul à chacun de
ses ports de sortie indiquant la limite. De cette façon, le récepteur du message nul peut calculer de nouveaux
limites dans ses liens sortants, envoyer cette information à ses voisins, etc. De cette façon, cela brise le
cycle de processus bloqués et évite l'étreinte mortelle.

Exemple 17

Supposons que nous étudions les trois processus logiques de la figure 22a. Dans ce cas, l'algorithme
Le conservateur entre dans un blocage. Supposons maintenant que chaque processus logique progresse par étapes de 9.
unités de temps. Dans la figure 22b, nous voyons l'émission des messages nuls pour ce cas. Ensuite, le
Le processus P2 a deux liens d'entrée avec un temps local de 21, il traite donc le premier message du
lien choisi et disparaît l'étreinte mortelle qui existait auparavant.

Figure 22 - Éviter le Deadlock avec des messages nuls

.

Ce mécanisme évite l'étreinte mortelle tant qu'il n'y a pas de cycles dans lesquels l'augmentation
de l'horodatage collectif d'un message qui traverse le cycle peut être zéro. Une condition nécessaire et
suffisant pour un câlin mortel en utilisant ce schéma est qu'il existe un cycle de liens avec le même temps
de lien (par exemple, dans la figure 22 si l'avancement est zéro, il y a étreinte mortelle).

Voyons un argument intuitif sur le pourquoi il n'y a pas d'étreinte mortelle. Pour qu'elle existe, il doit y avoir un cycle.
de processus bloqués, par exemple, P1 bloque P2, P2 bloque P3, etc. jusqu'à Pn, et Pn bloque P1.
Soit ti le temps local de l'horloge de Pi. Ensuite, si Pi bloque Pj, Pj doit attendre un
le message de Pi et son heure locale, tj doit être égale à l'heure du lien de Pi à Pj. Mais si Pi aussi
est bloqueé, vous devez avoir mis à jour les horloges de vos liens de sortie pour qu'elles soient supérieures ou
égaux à l'heure locale de Pi, ti. Ensuite, si tj>=ti, t1 >= t1. Par la présomption de prévisibilité, au moins
un processus dans le cycle, disons Pi, avec des horloges de la liaison de sortie strictement supérieures à son horloge
local, par exemple, ti>ti+1. Ensuite, nous avons t1>t1, une contradiction.
 Exemple 18

Voyons comment les algorithmes de messages nuls évitent l'étreinte mortelle pour l'exemple de la figure 23.
Le pré-calcul pour les processeurs P2 et P3 est supposé être de 2. Les chiffres au-dessus des processeurs dans
La figure montre vos horloges locales avant que les messages ne soient envoyés. P2 envoie le message nul (4, null)
un P3. Ensuite, P3 met à jour son horloge locale à 4 et envoie le message (6, null) à P2. P2 peut traiter le message
(3, m1) et mettre à jour son horloge à 3, produisant le message (8, m4), qui est envoyé à P3.

Figure 23 - Utilisation de messages nuls pour la figure 21

Une variation dans l'approche du message nul consiste à envoyer des messages nuls dans une base de demande.
au lieu de après chaque événement, comme le fait le protocole SRADS [Rey82]. Ici, chaque fois qu'un
le processus est sur le point de se bloquer, il demande le message suivant (nul ou autre) au processus émetteur connecté au lien
de l'entrée. Cette approche aide à réduire la quantité de trafic de messages nuls, bien qu'elle puisse être
nécessaire un délai plus long pour recevoir des messages nuls car deux messages sont nécessaires. SRADS
travaille bien avec des systèmes synchrones ayant des interactions peu fréquentes, car à mesure que l'interaction
augmente, la surcharge dégrade la performance.

Une amélioration du schéma des messages nuls utilise un délai d'attente pour la transmission. Si la transmission d'un
Un message nul prend du temps, il pourrait ne pas avoir besoin d'être transmis car un message sera généré.
avec un timestamp plus élevé. Cela réduira le nombre total de messages nuls nécessaires, bien que certains processus
ils peuvent être retardés en attendant des informations sur le timing. Les messages nuls ultérieurs sur un lien
pourraient supprimer des messages nuls non traités précédemment dans le lien, car ils sont obsolètes. Autre
une amélioration possible de l'algorithme est qu'un processus envoie des messages nuls uniquement sur ses liens de sortie
quand il se bloque.

4.4.2. Détection et récupération de l'étreinte mortelle

Une approche alternative utilise un mécanisme pour détecter quand la simulation est entrée en étreinte.
mortal, et un autre pour le rompre. L'étreinte mortelle peut être rompue car les messages avec le temps le plus court-
tamp toujours sont sûrs de traiter. Quand un processus se bloque, il envoie un message (appelé
"sonde") avec un horodatage avec son horloge locale à l'un de ses prédécesseurs pour obtenir des informations sur ses
montres. Le processus récepteur enverra sa valeur de l'horloge locale au processus qui le demande si celle-ci est postérieure au
horloge locale du processus qui le demande. Sinon, envoie des sondes à ses prédécesseurs. La plupart des solutions
précisent que le message contienne le chemin qui a été traversé et possiblement les horloges locales des
processus en cours pour détecter et corriger une étreinte mortelle. Ensuite, les messages s'allongent.
tandis qu'ils passent.
 Cette approche peut être modifiée pour détecter et récupérer des câlins mortels locaux (par exemple,
situations où seule une portion du réseau est dans une étreinte mortelle). Un prétraitement peut être effectué pour
identifier tous les sous-réseaux qui pourraient avoir un câlin mortel, et appliquer ces techniques dans les sous-réseaux
individuelles (le surcoût peut être important si la topologie du réseau contient de nombreux cycles).

4.4.3. Précalcul des temps de service

Nous appelons précalcule (lookahead) la capacité de prédire ce qui va se passer (ou, plus important, ce qui NE va PAS)
se produira) dans le futur simulé. Si un processus dans le temps simulé Clock peut prédire tous les événements
qui générera jusqu'au temps Clock+L, on dit que le processus a un pré-calcul L. Le pré-calcul améliore la
capacité à prédire des événements futurs, qui peuvent être utilisés pour déterminer quels autres événements sont sûrs
de traiter. Il est utilisé dans l'approche visant à éviter l'étreinte mortelle pour déterminer les horodatages qui se
asignent à des messages nuls. Il est également utilisé pour la détection et la récupération de l'étreinte mortelle parce que toujours
qu'un processus envoie un message avec un horodatage incrémenté de T à un autre processus, cela garantit
que aucun autre message ne suivra dans le lien contenant un horodatage inférieur à Horloge + T.

On dit qu'il y a de la "prédictibilité" lorsqu'il existe une limite inférieure de pré-calcul pour chaque cycle.
Intuitivement, les processus maintiennent les horloges de leurs liens sortants en avance sur leurs horloges locales.
envoyant des messages nuls. Au moment de l'initialisation, toutes les horloges sont remises à zéro. L'horloge
le local du processus est mis au minimum de toutes les horloges de ses liens d'entrée, et les mises à jour sont effectuées
relojes des liens de sortie inférieurs à l'horloge locale (que ce soit en envoyant des messages réels ou nuls). Quand
un processus met à jour les horloges des liaisons de sortie, les déplace aussi loin que possible, mais ne
met à jour les horloges de départ qui sont déjà en avance sur votre montre locale. Ensuite, traitez tout message de
entrée avec un horodatage égal à son heure locale.

On peut améliorer la compétence de pré-calcul des processus en le faisant par portions de calcul.
événements futurs. Par exemple, en simulant un réseau de files d'attente FIFO sans suppression, il est possible de pré-calculer le
temps de service des travaux qui n'ont pas encore été reçus. Si le serveur est libre et que son horloge a
un valeur de 100, et le temps de service du prochain travail a été pré-calculé à 50, la limite
inférieur en le timestamp du prochain message qu'il enverra est 150 au lieu de 100. Le précalcul est
possible s'il est possible de prévoir des aspects des événements futurs sans connaître les messages qui provoquent des calculs.
Dans notre exemple, si le temps de service dépend d'un paramètre dans le message, le précalcule ne sera pas
si simple.

Exemple 19

Considérons la simulation d'un réseau de mise en file d'attente constitué de deux stations connectées en série.
Chaque station dispose d'un serveur et d'une file d'attente avec des tâches (clients) attendant de recevoir un service (les tâches
se traitent dans l'ordre FIFO). En général, on utilise deux types d'événements : (1) un d'arrivée d'un travail à
une station ; (2) une de sortie de travail terminé. Un travail J qui arrive à la première station dans le
Le moment T passera, en général Q >= 0 unités de temps dans la file d'attente, attendant d'être servi et une can...
papa S de temps étant pris en charge. Ce simulateur a de mauvaises propriétés de pré-calcul. P1 doit avancer
son temps simulé à T+Q+S avant de générer un nouvel événement d'arrivée avec un horodatage T+Q+S pour
P2. Il a un pré-calcul zéro en ce qui concerne la génération de nouveaux événements d'arrivée (Fig. 24).

Une approche alternative élimine l'événement de sortie. Ici, traiter un événement d'arrivée dans P1
provoque la planification d'un nouvel événement d'arrivée dans P2 (car des files d'attente FIFO sans suppression sont utilisées). L'événement
au moment T, vous pouvez prédire l'événement d'arrivée à T+Q+S car S et Q peuvent être calculés en
temps simulé T. En particulier, Q est le temps de service restant pour le travail pris en charge dans le mo-
mento T, mais les temps de service de tous les travaux qui le précèdent. De manière similaire, cela peut
calculer S à T car cela ne dépend pas de l'état du processus à un instant ultérieur à T. Le précalcul
en utilisant cette approche alternative, c'est Q + S [Fuj90].
 Figure 24 - Précalcul des temps de service

On ne peut pas toujours avoir un bon précalcul. Par exemple, si la distribution du temps de service a
un minimum de zéro et il y a un retrait, un travail de haute priorité simulé jusqu'au temps T pourrait affecter
(bien que très rarement) à toute la station dans le réseau au moment T, de sorte qu'aucune station
je pourrais faire du pré-calcul au-delà de T.

4.4.4. Fenêtres temporelles conservatrices

Lubachevsky [Lub89] utilise un mécanisme avec des messages nuls et un précalcul, mais une fenêtre mobile de
temps simulé. Il s'agit de réduire le surcoût existant pour déterminer quand il est sûr de traiter
un événement. La limite inférieure de la fenêtre est définie comme le timestamp minimum de tout événement sans
traiter, et seuls les événements non traités dont l'horodatage se trouve dans la fenêtre peuvent être traités.

Le but de la fenêtre est de réduire l'"espace de recherche" qu'il faut parcourir pour déterminer si
un événement est sûr. Par exemple, si la fenêtre s'étend du temps simulé 10 au temps simulé
20, et l'application est telle que chaque événement traité génère un nouveau avec un horodatage incrémenté
minimum de 8 unités, chaque processus logique n'a besoin d'examiner que les événements non traités dans les processus
logiques voisines pour déterminer quels événements sont sûrs : il n'y a pas d'événements non traités à deux ou plusieurs sauts
qui pourraient affecter quelqu'un dans la fenêtre de 10 à 20 parce qu'un tel événement devrait avoir un timestamp
antérieur au début de la fenêtre.

Une question importante est la méthode utilisée pour déterminer la taille de la fenêtre temporelle. Si
la fenêtre est très petite, il y aura très peu d'événements disponibles pour une exécution concurrente. Par contre
Côté, si la fenêtre est très grande, le mécanisme de simulation se comporte de la même manière que l'a-
ria si aucune fenêtre de temps n'était utilisée, ce qui ne justifie pas le surcoût du mécanisme de la fenêtre.
Un tamaño adéquat de fenêtre nécessite des informations spécifiques à l'application (qui doivent être obtenues de
programmeur, du compilateur ou à l'exécution).

4.4.5. Performance des mécanismes de conservation

Il existe diverses études empiriques et analytiques pour déterminer la performance des divers
schémas conservateurs. On a étudié les schémas pour éviter, détecter et récupérer l'étreinte mortelle avec
résultat différent. Le degré de pré-calcul joue un rôle critique dans la performance, car un processus avec
Le pré-calcul L peut permettre à d'autres processus de traiter en toute sécurité des messages d'événements.
dents.

La programmation de la simulation en exploitant le précalcul peut améliorer de manière spectaculaire les performances. En
la figure 25 montre les mesures de performance lors de la simulation d'un réseau de mise en file d'attente avec un serveur central
en utilisant l'algorithme de détection et de récupération de l'étreinte mortelle dans un Butterfly BBN (chaque processus
logique exécutant sur un processeur séparé). Il y a un nombre fixe de tâches (la population de messages).
On montre le nombre moyen de messages traités entre les câlins mortels, et l'accélération relative
une liste d'événements séquentiels. Il semble que l'utilisation de pré-calcul soit supérieure à ne pas le faire. Les courbes de
L'accélération pour l'approche d'évitement de l'étreinte mortelle en utilisant des messages nuls était similaire. On a vu
que l'approche de détecter et de récupérer l'étreinte mortelle est généralement supérieure, particulièrement
lorsqu'il y a un petit nombre de processus dans le système.

Figure 25 - Performance of conservative algorithms (a) Efficiency; (b) Acceleration [Fuj90]

D'autre part, les mesures extensives des algorithmes pour éviter, détecter et récupérer des câlins.
des mortels s'exécutant sur un multiprocesseur ont obtenu des performances plutôt mauvaises sauf dans quelques cas
spécialisés. S'il y a des cycles, il n'y a guère d'accélération. Le retard semble affecter la performance du
schéma de messages nuls, mais pas dans le schéma de détection et de récupération. La conclusion générale est
que les techniques de Chandy-Misra ne sont pas viables.

Dans un autre travail, Fujimoto utilise des charges synthétiques pour caractériser quantitativement le précalcul.
Bonjour, utilise un paramètre appelé relation de pré-calcul et présente des données empiriques pour démontrer la
importance d'exploiter le pré-calcul pour obtenir de bonnes performances. Selon le pré-calcul, il se
Ils classifient les accélérations pour ces charges synthétiques depuis les plus lentes que l'exécution séquentielle
jusqu'aux presque idéaux. On a pu voir que le schéma détection/récupération et de messages nuls peut avoir
des efficacités aussi élevées que 75 % avec le schéma de messages nuls (accélération relative à un
monoprocesseur). Le précalcul et la population des messages ont une influence (il y a une plus grande accélération.
plus grand pré-calcul et population de messages). Pour le schéma de détection/récupération d'étreinte
mortal il y a un niveau de population critique : des populations inférieures produisent des performances médiocres et constantes. À
À mesure que la population augmente au-delà de ce niveau, les performances s'améliorent de manière spectaculaire.
La population nécessaire pour obtenir une bonne performance dépend du précalcul (un plus grand précalcul réduit la
population nécessaire) [Fuj89].

Peut-être que l'inconvénient le plus évident des approches conservatrices est qu'elles ne peuvent pas exploiter par
je complète le parallélisme disponible dans l'application de simulation. Si un événement peut affecter un autre,
doivent être exécutées séquentiellement. En général, l'exécution séquentielle est forcée sans qu'elle soit nécessaire. Par
fin, les algorithmes dépendent du pré-calcul. Un autre problème est lié à la robustesse : les changements
les mineurs dans l'application peuvent avoir un effet catastrophique sur la performance. Cela pose problème
parce que les chercheurs n'ont généralement pas de connaissances avancées sur toute la gamme d'expériences. Autre
le problème est que les configurations sont statiques : il n'est pas possible de créer dynamiquement de nouveaux processus, et
sa interconnexion doit également être définie de manière statique.

La plupart des schémas conservateurs exigent que le programmeur fournisse des connaissances avec
concernant le comportement du processus logique. Une estimation très conservatrice peut aboutir à
un très mauvais rendement, et un très optimiste peuvent provoquer des violations des restrictions de causalité.
Peut-être le plus sérieux inconvénient des protocoles conservateurs existants est que le programmeur doit
prendre soin des détails du mécanisme de synchronisation pour obtenir de bonnes performances. Ceux qui proposent
des approches optimistes disent que l'utilisateur ne doit pas se soucier d'une telle complexité.

4.5. Mécanismes optimistes

Les méthodes optimistes ne préviennent pas les erreurs de causalité mais les détectent et s'en remettent. En revanche
avec les mécanismes conservateurs, ils ne précisent pas quand il est sûr de procéder ; mais ils détectent
une erreur se produit et un processus de récupération est invoqué, exploitant le parallélisme là où cela peut se produire
erreurs de causalité mais en fait elles ne se produisent pas.

Le mécanisme Time Warp est le protocole optimiste le plus connu [Jef85]. Quand le message d'un
l'événement reçu dans un processus logique a un horodatage inférieur à celui de l'horloge du processus, il y a une erreur de
causalité. L'événement qui provoque le rollback s'appelle disperseur. La récupération se fait en annulant
les effets de tous les événements qui ont été traités prématurément par les processus qui reçoivent le
dispersor (c'est-à-dire, les événements traités avec un timestamp supérieur à celui du dispersor).

Les messages ont deux horodatages : l'heure d'émission et l'heure de réception. L'horloge locale (LVT - Heure Locale)
Le Temps Virtuel d'un processus est mis au minimum du temps de réception de tous les messages non
traités. Les processus peuvent exécuter des événements tant qu'ils ont une entrée, donc le LVT d'un
Le processus peut devancer ceux de ses prédécesseurs et peut recevoir un message d'un événement du passé.
Dans ce cas, le processus effectue un rollback, et la simulation est refaite en tenant compte du nouvel événement.

Un rollback, en plus de modifier l'état, peut envoyer des messages à d'autres processus. Pour la première chose
Il faut stocker l'état du processus (lors du rollback, un vecteur d'état ancien est restauré). Pour annuler
un message transmis envoie un message négatif ou un antimessage qui élimine l'original à son arrivée
à sa destination. Les messages d'événements s'appellent des messages positifs. S'il reçoit un antimessage d'un
message positif traité, le processus doit être annulé, et le message positif doit être supprimé. Répétant cela
Le processus peut annuler tous les calculs erronés de manière récursive.
Pour annuler les effets des messages erronés, il est nécessaire de stocker les états de chaque processus.
depuis le dernier temps « correct » (appelé GVT - Temps Virtuel Global). C'est le minimum des LVTs
de tous les processus et les temps d'émission de tous les messages envoyés mais non traités.

Pour implémenter Time Warp, chaque processus doit maintenir son LVT, son état actuel, une file d'attente de
états avec des copies de leurs états précédents (avec au moins un état précédent au GVT) ; une file d'attente de
entrée avec tous les messages reçus avec des temps d'émission supérieurs ou égaux au GVT (dans l'ordre de
réception); et une file de sortie avec une copie des messages envoyés avec des temps d'émission supérieurs ou
égaux au GVT (dans l'ordre d'émission). Les messages d'entrée ont un signe positif ; les copies dans la
la queue de sortie est des antimensajes et ont un signe négatif. Si un message et son antimensaje sont dans le
même queue, ils se détruisent.

En recevant un disperseur (temps de réception inférieur au LVT), le processus effectue un rollback et le traite.
Le processus remet l'état actuel dans le dernier état enregistré avant le temps de réception du disperseur.
et met son LVT à l'heure de cet état. Il élimine tous les états suivants de sa file d'attente d'états,
envoyer tous les anti-messages de sa file de sortie avec un temps d'émission supérieur à son LVT. Traitez le
disperseur et traite les messages dans sa file d'attente d'entrée avec des temps de réception supérieurs ou égaux à
LVT, il avance dans le temps de simulation.
 Exemple 20

Regardons le cas de la figure 26a. Ici, le LVT est au temps simulé 29, et un disperseur arrive avec
temps 22. Alors, il est inséré dans la file d'attente, le LVT devient 22, et sont envoyés, comme antimisages, les
messages de la file d'attente de sortie 25 et 33, dispersant l'événement d'arrivée.

Figure 26 - Arrivée d'un antimessage dans Time Warp.

En supposant une mémoire infinie, l'algorithme Time Warp n'entrera pas en étreinte mortelle, car les
des processus individuels n'entrent pas dans une étreinte mortelle tant qu'ils ont des entrées, et le GVT ne cesse de croître.
De plus, il a un potentiel d'accélération plus important que les approximations conservatrices, mais au prix d'un coût plus élevé.
exigence de mémoire. Un avantage est qu'il n'est pas nécessaire de connaître la topologie des possibles
interactions entre processus. Comme aucun événement avec un horodatage inférieur au GVT ne peut être annulé, le
Le stockage utilisé par de tels événements peut être utilisé. Les opérations irrévocables (comme celles de
L'entrée/sortie ne peut pas se faire tant que le GVT n'a pas effacé le temps simulé au cours duquel cela s'est produit.
opération. Ce processus s'appelle la collecte de fossiles.

En résumé, l'algorithme suit ces étapes :

. Si un antimensaje arrive avant le message correspondant, il est stocké dans la file d'attente d'entrée (sans
importer si votre temps est avant ou après le LVT). Quand le message positif arrive, les deux se
détruisent.

Si un message positif arrive avant son antimessage, et à l'arrivée de l'antimessage, le LVT est inférieur à
le temps de réception (les messages sont en futur simulé), les deux se détruisent.

Si un message arrive avant son antimessage et quand l'antimessage arrive, le LVT est supérieur à son
temps de réception, le processus effectue un rollback. Le message actuel est remis à l'état enregistré le plus récent avec
le temps simulé avant le temps de réception du message, le message et l'anti-message sont détruits, et le
le processus avance.

Un inconvénient de Time Warp est qu'il nécessite beaucoup de mémoire. Si le GVT est calculé consécutivement, il
vous pouvez extraire des messages d'entrée et de sortie. Le GVT peut être estimé avec un algorithme distribué linéaire.
au moment de diffuser à tous les processeurs du système. Si le GVT est estimé
Fréquemment, moins de mémoire est nécessaire mais il y aura un plus grand overhead en temps. Une autre façon de
économiser de la mémoire consiste à éliminer les états avec des timestamps supérieurs au LVT qui apparaissent à partir de
retours en arrière.

4.5.1. Annulation Paresseuse

L'annulation paresseuse [Gaf88] est une optimisation pour réparer les dommages causés par les calculs
incorrects au lieu de les répéter complètement. Le mécanisme de Time Warp décrit utilise l'annulation.
agressive : si l'on fait un rollback à un temps T, les antimessages sont immédiatement envoyés
correspondants. Mais un dispersoir peut ne pas modifier le calcul des événements dont il fait marche arrière, et
les messages (positifs) générés par ces événements peuvent être les mêmes. Avec l'annulation paresseuse,
les processus n'envoient pas immédiatement les antimessages pour tout rollback, mais ils vérifient si la
La réexécution du calcul régénère les mêmes messages. Dans ce cas, il n'est pas nécessaire d'annuler le
message. Un anti-message n'est envoyé que lorsque le LVT passe son temps sans le régénérer.

En fonction de l'application, l'annulation paresseuse peut améliorer ou dégrader les performances, car
nécessite un overhead supplémentaire pour déterminer si un antMessage existe déjà. Permet également que les
des calculs erronés se dispersent plus qu'avec une annulation agressive, par conséquent la performance peut
se dégrade si le simulateur force l'exécution de calculs incorrects. D'autre part, si les messages ne se
les rollbacks dans les processus suivants seront nécessaires sous les deux mécanismes et se produiront
avant avec une annulation agressive.

Dans la plupart des cas, l'annulation paresseuse est plus rapide (il existe des preuves empiriques) mais
elle nécessite plus de mémoire que l'agressive. L'annulation paresseuse permet également que les calculs se
s'exécute en moins de temps que le cas du chemin critique, car les calculs avec une entrée incorrecte (ou
partiellement correcte) peuvent générer des résultats corrects. Supposons qu'un processus calcule le
mínimum de A et B, et exécute prématurément en utilisant une valeur incorrecte de A. Si les deux valeurs (correctes
e incorrecto) de A sont plus grands que B, l'exécution incorrecte produit le même résultat que la
correcta). Cela n'est pas possible en utilisant une annulation agressive, car la réalisation d'un rollback des calculs s
rejetez immédiatement.

Ces facteurs sont liés à la propriété de pré-calcul. Rappelons-nous que dans l'exemple 19
que l'événement d'arrivée en T+Q+S était invariant par rapport à d'autres événements dans [T, T+Q+S]. Ensuite, P1 fait
précalculez et planifiez l'événement d'arrivée T+Q+S bien que votre horloge locale n'avance que jusqu'à T. Maintenant
considérons une simulation Time Warp utilisant une annulation paresseuse qui utilise les événements d'arrivée et
départ. Supposons que P1 ait avancé au-delà de T+Q+S, et ait traité l'événement de départ dans
T+Q+S, et l'événement de l'arrivée suivante est planifié. Supposons qu'un événement dispersif arrive avec
estampille Tx tel que T < Tx < T+Q+S. Si P1 fait un rollback, traite le disperseur, et réexécute l'événement de
partie en T+Q+S. Cependant, comme l'événement d'arrivée en T+Q+S n'est pas affecté par l'événement
dispersor (en raison de l'utilisation de files d'attente FIFO), le même événement d'arrivée qui a été généré sera recréé
dans l'exécution originale. Étant donné que l'annulation paresseuse est utilisée, l'exécutif Time Warp n'annule pas le
temps d'arrivée original dans le temps T+Q+S. La propriété d'invariance sur laquelle se base le
Le précalcul est la même propriété qui permet à l'annulation paresseuse de réussir.

L'annulation paresseuse tire parti du pré-calcul même si l'application n'a pas été programmée
explicitement pour l'exploiter, contrairement aux approches conservatrices qui exigent que l'on
spécifiez explicitement. L'inconvénient est que son overhead est plus élevé, car le calcul invariant doit
réexécuter, et des comparaisons de messages sont nécessaires pour déterminer quand elle est applicable
optimisation.

4.5.2. Fenêtres de temps optimistes

Des fenêtres de temps ont également été proposées pour des protocoles optimistes. Ici, elles sont utilisées pour prévenir
que les calculs incorrects se propagent dans le futur simulé. L'approche de la fenêtre temporelle
en mouvement, une fenêtre de temps fixe de taille W est utilisée. Ici, seuls ceux-ci sont sélectionnés pour être traités.
événements avec des timestamps en [T, T+W], où T est l'événement avec le timestamp le plus bas [Sok88].
 Les critiques de la méthode disent qu'elle ne peut pas distinguer les bons calculs des mauvais, donc ils peuvent
empêcher le progrès de calculs corrects. De plus, les calculs incorrects qui sont en avance sur le
Le futur simulé est déjà discriminé par le mécanisme de planification de Time Warp, qui donne
priorité aux activités avec des timestamps petits. Enfin, il n'est pas clair comment cela doit être déterminé
la taille de la fenêtre. Les données empiriques suggèrent que les fenêtres de temps offrent peu d'avantage dans
certains cas, et améliorations dans d'autres.

4.5.3. Appels de Wolf

Dans [Mad88], un message dispersif provoque qu'un processus envoie des messages de contrôle spéciaux pour
arrêter la dispersion des calculs erronés. Les processus qui peuvent être 'infectés' par des calculs erronés
Ils sont notifiés lorsqu'une erreur est détectée (c'est-à-dire un message de dispersion).

Comme dans le schéma de fenêtre de temps, l'inconvénient est que certains calculs corrects peuvent
geler inutilement. De plus, l'ensemble des processeurs affectés par des calculs erronés pourrait
être significativement plus grand que l'ensemble réel ; par conséquent, certains messages peuvent être envoyés.
contrôles inutiles. Enfin, il faut connaître la vitesse à laquelle le calcul peut se disperser
erroné et le temps nécessaire pour transmettre les messages de contrôle. Déterminer des limites dans ces
Les quantités peuvent être difficiles.

4.5.4. Annulation directe

Dans Time Warp, il est important que l'on puisse annuler un calcul incorrect avant qu'il ne puisse
se disperser dans le système. Autrement, il peut arriver que les erreurs de calcul se dispersent rapidement
à travers le système, tandis qu'il y a des anti-messages essayant frénétiquement de les trouver. Tel
le comportement peut être évité ; une manière de le prévenir est de donner aux anti-messages une plus grande priorité que
les messages positifs.

Un mécanisme, appelé de cancellation directe [Fuj89b] (pour mémoire partagée) fait que toujours
que un événement E1 planifie un autre E2, et laisse un pointeur de E1 à E2. Ce pointeur est utilisé si ensuite on décide
que E2 devrait être annulé (en utilisant l'annulation paresseuse ou agressive). Par contraste, les systèmes de Time
Les warp conventionnels doivent chercher pour trouver des messages annulés. Les avantages de ce mécanisme.
son doubles : réduit la surcharge associée à l'annulation des messages, et trouve rapidement
calculs erronés pour minimiser les dommages.

4.5.5. Performance des mécanismes optimistes

Les mécanismes optimistes ont permis d'accélérer substantiellement les simulations de champs de
bataille, réseaux de communications, systèmes biologiques, simulation producteur/consommateur, de matériel
numérique et d'autres phénomènes physiques. L'accélération typique dans un hypercube a une plage de 10 à 20
en utilisant 32 processeurs. En utilisant 100 processeurs d'une Butterfly BBN, des accélérations ont été obtenues de
37, et de 57 sur une Butterfly BBN de 64 processeurs. Une amélioration significative a pu être obtenue dans le
performance en utilisant des connaissances spécifiques de l'application pour optimiser l'exécution. Autres
les expériences ont obtenu des accélérations supérieures à 10 en utilisant 16 processeurs, et des efficacités aussi élevées que
90%. Le nombre de processus par processeur et l'équilibre de la charge ont des impacts significatifs sur
la performance. Avec 8 processus dans chacun des 127 processeurs et 9 processus dans un processeur
de plus, l'efficacité est de 72 % contre une efficacité de 91 % lorsqu'il y a 8 processus par processeur pour
128 processeurs.

Les preuves indiquent que tandis que le pré-calcul améliore la performance des algorithmes optimistes,
ce n'est pas un prérequis pour Time Warp. Dans la figure 27, Time Warp est comparé aux algorithmes de
éviter, détecter et récupérer l'étreinte mortelle. Une fraction des travaux dans le simulateur est désignée.
(ici un 1 %) comme haute priorité, tandis que le reste est de basse priorité. Les travaux de haute
priorité enlève le service de ceux de basse priorité. Comme mentionné précédemment, cette simulation contient
caractéristiques de précalcul très pauvres, et ne peut pas être optimisé en utilisant des files d'attente FIFO comme cela a été fait auparavant
pour le simulateur. Comme on peut le voir, Time Warp peut obtenir une accélération significative pour cela.
problème, tandis que les algorithmes conservateurs ont certaines difficultés.

Figure 27 - Accélération de la simulation Time Warp (256 processus logiques) [Fuj90]

Les mesures ont utilisé 256 processus logiques. La performance est montrée en utilisant des files d'attente FIFO et des files d'attente avec

removal. Using synthetic loads, the effect of precalculation, the distribution of increments was measured.
horodatage (localité temporelle), topologie (spécifiquement localité spatiale), et granularité des
calculs sur la performance. Il a été trouvé que Time Warp peut réaliser une accélération en proportion de la
quantité de parallélisme disponible dans la charge sous des conditions de test saturées (plus de parallélisme que
processeurs) et non saturés (moins de parallélisme que les processeurs). Bien que les résultats soient
Encourageants, nous devons dire que les frais généraux de sauvegarde d'état peuvent dégrader considérablement la performance.
peño (baisse lorsque la taille de l'état augmente).

Si l'on considère le cas où le rollback nécessite zéro temps, si les calculs incorrects ne font jamais
rollback des corrects. Time Warp utilisant l'annulation agressive produit une performance optimale (temps de
exécution égale au chemin critique du plus bas montant). En supposant un coût fixe pour le rollback, il a été démontré
que Time Warp peut améliorer les algorithmes de Chandy-Misra de manière arbitraire (p. ex. en
proportion au nombre de processeurs disponibles). Intuitivement, cela se produit parce que le parallélisme que
se perd en s'exécutant de manière conservatrice peut être arbitrairement grande, et l'exécution optimiste
peut exploser ce parallélisme [Lip90].

Les modèles analytiques existants ont produit des performances allant de très bonnes à très
pauvre, en fonction du coût du rollback (tous les calculs non présents lors des calculs normaux). Le
le rollback produit trois overheads : restaurer les files d'attente d'entrée, d'état et de sortie. Restaurer les files d'attente
L'entrée et l'état ont un coût négligeable car seules quelques instructions machines sont nécessaires.
pour placer le pointeur sur le prochain événement à traiter (autres coûts tels que l'insertion du disperseur
dans la file d'attente d'entrée, les coûts de rollback ne sont pas pris en compte car ils peuvent avoir lieu pendant le progrès
normal). Le principal overhead lors d'un rollback réside dans la restauration de la file de sortie, ce qui implique d'envoyer
antimensages.

Le coût du rollback n'est pas proportionnel à sa longueur. D'une part, l'envoi d'antimessages prend moins
temps d'envoyer des messages positifs : seuls des messages préexistants sont envoyés tandis que l'envoi d'un
un message positif nécessite d'assigner un tampon et de le remplir avec des données, en plus d'autres coûts (frais généraux de
planification, traitement des messages entrants, sauvegarde de l'état, et bien sûr, et calcul de la
simulation).

Exemple 21

Supposons que faire un rollback d'un calcul T unités de temps simulé prenne le double que le
progrès vers l'avant. Considérons le cas de deux processeurs, P1 et P2 : supposons que P2 est à 10
unités en avant de P1 lorsque P1 envoie un message à P2, provoquant le rollback de P2.
Supposons que la transmission du message prenne un temps nul. Pendant ce temps, P2 effectue un rollback de 10
unités de temps, selon notre présomption que faire un rollback est plus lent que le progrès.
Les deux processeurs avancent de quelques unités de temps simulé, et P2 envoie un message qui fait
rollback de P1. Pendant que P1 fait un rollback de 20 unités, P2 avance de 40 unités. Il est clair que si
ces processeurs continuent à faire un rollback de l'autre, la distance de rollback et le temps de le faire
augmente exponentiellement avec la simulation. Ensuite, le taux de progression des processeurs.

Figure 28 - Comportement des processus avec Time Warp

Une question critique à laquelle sont confrontés les systèmes optimistes tels que Time Warp est de savoir si le système
exhibera un comportement de thrashing où la majorité de son temps est consacrée à exécuter des calculs
incorrects et en cours de rollback. Les calculs incorrects seront exécutés au détriment des corrects ; mais
Cependant, si l'application ne contient qu'un parallélisme limité par rapport au nombre de processeurs disponibles, c'est
inévitable un degré significatif de retour en arrière.

Les algorithmes optimistes ont tendance à utiliser beaucoup plus de mémoire que leurs homologues.
conservatrices. L'utilisation d'une politique de planification de processus inadéquate lors de sa mise en œuvre peut être
catastrophique. De plus, le débogage des implémentations de Time Warp prend du temps parce que
peut nécessiter une analyse détaillée des scénarios de rollback complexes. D'autre part, ce coût de
le développement ne doit être payé qu'une seule fois lors du développement du noyau de Time Warp.

5. Conclusions

Dans ce travail, nous avons présenté divers mécanismes utilisés actuellement pour permettre
simulation efficace de systèmes d'événements discrets. Cette activité nécessite des formalismes spéciaux
qui permettent sa construction de manière efficace, sûre et à faible coût.

Le formalisme DEVS est l'un de ces formalismes, qui est de plus en plus diffusé dans les activités de
simulation d'événements discrets. Sa base formelle permet de l'utiliser comme outil mathématique,
permettant d'étudier en détail le comportement des systèmes développés. D'autre part, son
La structure hiérarchique et modulaire facilite le développement et la maintenance des applications.

Les automates cellulaires, en revanche, permettent de simuler certaines classes de systèmes complexes (depuis
flux de trafic vers des systèmes écologiques complexes) par le biais d'un mécanisme simple.
Dans tous les cas, il est nécessaire de fournir des méthodes efficaces pour l'exécution des simulations. Pour cela
nous avons analysé divers mécanismes existants à l'heure actuelle, essentiellement ceux qui sont
asinchrones et permettent la division de la simulation à réaliser (et sa liste d'événements), car ce sont eux qui
semblent offrir un plus grand degré d'accélération sur les simulations séquentielles. Une attention particulière a été accordée
en différentes méthodes, classées en optimistes et pessimistes. Les mécanismes pessimistes étaient une
première forme d'attaquer ces problèmes, bien que de nos jours les approches optimistes semblent
être les plus appropriées pour résoudre la plupart des problèmes.

6. Referencias

[Aya92] AYANI, R.; RAJAEI, H. "Simulation parallèle utilisant des fenêtres temporelles conservatrices", Proc. de la
Conférence de simulation d'hiver. Déc. 1992. pp. 709-717.

[Cha79] CHANDY, K; MISRA, J. « Simulation distribuée : une étude de cas dans la conception et la vérification de
programmes distribués", IEEE TOSE, septembre 1979.

[Cha81] CHANDY, K; MISRA, J. "Simulation distribuée asynchrone via une séquence de

calculs". CACM, (24):4, avril 1981. pp 198-206.

[Cho94] CHOW, A.; ZEIGLER, B. "DEVS révisé : un modèle de simulation parallèle, hiérarchique et modulaire"
"formalisme". Proc. Conférence de Simulation d'Hiver, 1994.

[Cho94b] CHOW, A.; ZEIGLER, B. "Simulateur abstrait pour le formalisme DEVS parallèle".

[Cho95] CHO, Y. "Mise en œuvre parallèle de conteneurs utilisant une machine virtuelle parallèle". Mémoire de maîtrise.
Département de génie électrique et informatique. Université de l'Arizona. 1995.

[Cho95b] CHOW, A. "Un lien C++ du formalisme DEVS parallèle". Actes de la SCS'95. pp. 38.
1995.

[Con88] CONCEPTION, A.; ZEIGLER, B. "Formalisme DEVS : un cadre pour le modèle hiérarchique
développement", Transactions IEEE sur l'ingénierie logicielle. Vol 14, No. 2. Février 1988. Pp. 228-241.

[Con89] CONCEPCION, A. "Une architecture informatique hiérarchique pour la simulation distribuée", IEEE
Transactions avec des ordinateurs, Fév. 1989.

[Eck95] ECKART, J.D. "Un système de simulation d'automates cellulaires". Rapport technique de l'Université de Radford.
1995.

[Esc95] ESCUDE, B. "Conception et réalisation d'un simulateur hiérarchisé, modulaire et à événements "
discrets". Mémoire du D.E.A d'Informatique et d'automatique. Université de Droit, d'Économie et des
Sciences d'Aix-Marseille III. Institut Universitaire des sciences pour l'Ingénieur de Marseille. 1995.

[Fuj89] FUJIMOTO, R. "Mesures de performance des stratégies de simulation distribuée". Transactions

du SCS, 6, 2 (Mars 1989). pp. 21-26.

[Fuj89b] FUIMOTO, R. "Distorsion temporelle sur un multiprocesseur à mémoire partagée". Transactions de la SCS. 6, 3
(Juillet 1989). pp. 211-239.

[Fuj90] FUJIMOTO, R. "Simulation parallèle d'événements discrets". Communications de l'ACM Vol. 33.
No. 10. pp. 30-53. 1990.

[Gaf88] GAFNI, A. "Mécanismes de retour en arrière pour les systèmes de simulation distribuée optimistes". Proc. de la
SCS M. sur DS. 19(3) :61-67, juillet 1988.

Les combinaisons fantastiques du nouveau jeu de solitaire 'La vie' de John Conway.
Scientific American, 23 (4), 1970, pp. 120-123.
[Gar86] GARZIA, R.F.; GARZIA, M.R.; ZEIGLER, B.P. "Simulation d'événements discrets", IEEE Spectrum
Décembre 1986. pp. 32-36.

[Gia95] GIAMBIASI, N. "Introduction à la modélisation et à la simulation". Matériaux du cours de

D.E.A.; Université d'Aix-Marseille III. 1996.

[Gra80] GRAYBEAL, W.; POOCH, U. "Simulation : Principes et méthodes". Cambridge, MA, 1980.

[Gut95] GUTOWITZ, H. "Automates cellulaires et les sciences de la complexité. Partie I-II". À paraître dans le
journal Complexité. Novembre 1995.

[Ho89] HO, Y. "Numéro spécial sur les systèmes dynamiques à événements discrets", Actes de l'IEEE, 77 (1), 1989.

[Hoo89] HOOVER, S.; PERRY, R. "Simulation : Une Approche de Résolution de Problèmes", Addison Wesley,
Reading, MA, 1989.

[Jef85] JEFFERSON, D. "Temps Virtuel". ACM TOPLS, 7(3) : 404-425. Juillet 1985.

[Jef87] JEFFERSON, D. "Simulation distribuée et le système d'exploitation Time Warp". Dans le 11ème.
Symposium sur les principes des systèmes d'exploitation. pp 77-93. Novembre 1987.

[Kim95] KIM, K. et al. "Simulation optimiste distribuée de modèles DEVS hiérarchiques". Actes de
les SCS'95. pp. 32. 1995.

[Lin95] LIN, Y.; FISHWICK, P. "Simulation d'événements discrets parallèles asynchrones", Transactions IEEE
sur les Systèmes, l'Homme et la Cybernétique. 1995.

[Lip90] LIPTON, R.; MIZELL, D. "Time-Warp contre Chandy-Misra : une comparaison dans le pire des cas".
Actes de la multiconférence SCS sur la simulation distribuée. 22, 1 (Janvier 1990). pp. 137-143.

[Lub89] LUBACHEVSKY, B. "Simulations distribuées efficaces basées sur des événements de réseaux à boucles multiples".
Communications de l'ACM 32. Janvier 1989. pp. 111-123.

[Mad88] MADISETTI, V.; WALRAND, J; MASSERSCHMIT, D. "Wolf : un algorithme de retour en arrière pour
"systèmes de simulation distribués optimistes", dans les actes de la Conférence de Simulation d'Hiver, 296-305. 1988.

[Mis86] MISRA, J. "Simulations distribuées à événements discrets". ACM Computing surveys. Vol. 18, No. 1,
39-65. 1986.

[Nic94] NICOL, D.; FUJIMOTO, R. "Simulation parallèle aujourd'hui". Annales de la recherche opérationnelle, vol.
53, 249-285. Nov 1994.

[Ove92] OVEREINDER, B.; SLOOT, P. "Application du Time-Warp aux simulations parallèles avec
automates cellulaires asynchrones. 1992.

[Ove93] OVEREINDER, B.; SLOOT, P.; HERZBERGER, L. "Time-Warp sur une plateforme transputer : pilote
étude avec des automates cellulaires asynchrones." 1993.

[Pra95] PRAEHOFER, H.; REISINGER, G. "Réalisation orientée objet d'un événement discret parallèle
"Simulateur". Rapport technique Université Johannes Kepler, Département de théorie des systèmes et d'information
Ingénierie. 1995.

[Rey82] REYNOLDS, P. Jr. "Un algorithme de ressource partagée pour la simulation distribuée". Actes de la
9ème Symposium Annuel sur l'Architecture Informatique pp. 259-266. 1982.

[Rig89] RIGHTER, R.; WALRAND, J. "Simulation distribuée de systèmes à événements discrets". Actes de
l'IEEE. p. 99. Janvier 1989.
[Sok88] SOKOL, L; BRISCOE, D; WIELAND, A. "MTW : une stratégie pour la planification de simulation discrète
événements pour l'exécution concurrente", Proc. de la conférence SCS sur la simulation distribuée, 34-42. 1988.

TOFFOLI, T. "Occam, Turing, von Neumann, Jaynes : Combien pouvez-vous obtenir pour si peu ? (Un)
introduction conceptuelle aux automates cellulaires)". Actes de ACRI'94. (1994).

[Wol84] WOLFRAM, S. "Universalité et complexité dans les automates cellulaires", Physica, 10D, 1-35 (1984).

[Zei76] ZEIGLER, B. "Théorie de la modélisation et de la simulation". Wiley, 1976.

ZEIGLER, B. "Modélisation multifacette et simulation d'événements discrets". Presses Académiques, 1984.

[Zei89] ZEIGLER, B. "Représentation DEVS des systèmes dynamiques : contrôle intelligent basé sur les événements."
Actes de l'IEEE, Vol. 77 No. 1, pp. 27-80. 1989.

[Zei90] ZEIGLER, B. "Simulation orientée objet avec des modèles modulaires hiérarchiques". Academic Press,
1990.

[Zei95a] ZEIGLER, B.; KIM, D. "Conception de modélisation de haut niveau / simulation à haut rendement
environnements". Rapport technique, Département de génie électrique et informatique, Université
Arizona. 1995.

[Zei95b] ZEIGLER, B.; KIM, D. "Étendre la simulation basée sur la connaissance DEVS-Scheme"
environnement pour le contrôle en temps réel basé sur les événements". Rapport technique, Département d'électricité et
Ingénierie informatique, Université de l'Arizona. 1995.

[Zei96] ZEIGLER, B.; MOON, Y.; KIM, D.; KIM, D. "DEVS-C++ : Une modélisation à haute performance et
environnement de simulation". Rapport technique, Département de génie électrique et informatique,
Université de l'Arizona. Dans les Actes de la 29ème Conférence internationale d'Hawaï sur les sciences des systèmes, janvier.
1996.