Discrete Event System Specification

DEVS (de l'anglais Discrete Event System Specification) est un formalisme modulaire et hiérarchique pour la modélisation, la simulation et l'analyse de systèmes complexes qui peuvent être des systèmes à événements discrets décrits par des fonctions de transitions d'états et des systèmes continus décrits par des équations différentielles, par exemple et des systèmes hybrides (continus et discrets).

DEVS (pour Discrete Event System Specification) est un formalisme de spécification des systèmes à événements discrets. Il a été proposé par Bernard P. Zeigler (en) en 1976 dans la première version de son ouvrage "Theory of modelling and simulation"^{[réf. non conforme]}.

Cette extension, développée par Zeigler et Alex C. H. Chow^[1] a pour rôle de fournir une technique simple de parallélisation des calculs. Les extensions traditionnelles utilisent des techniques où des branches de la hiérarchie de modèles sont répartis sur des calculateurs. Un point de synchronisation est alors nécessaire pour effectuer un test sur la causalité des événements. Les techniques de synchronisation sont décrites dans [zeigler00]^{[réf. à confirmer]} avec des techniques optimistes, de type Time Warp, et pessimistes.

La méthode DEVS parallèle utilise une méthode simple de parallélisation des calculs en utilisant une parallélisation des modèles lorsqu'au dépilement d'une date dans l'échéancier, toutes les fonctions de transition internes ou externes des modèles sont effectuées en parallèle.

B. P. Zeigler définit DEVS parallèle à partir de DEVS classique. Nous utilisons DEVS classique avec ports. Le modèle atomique utilisant DEVS parallèle avec ports se définit comme suit :

D E V S = ⟨ X , Y , S , δ e x t , δ i n t , δ c o n , λ , t a ⟩ {\displaystyle DEVS=\langle X,Y,S,\delta _{ext},\delta _{int},\delta _{con},\lambda ,ta\rangle }

Où :

• X = { ( p , v ) | p ∈ I P o r t s , v ∈ V X {\displaystyle X=\{(p,v)|p\in IPorts,v\in V_{X}} est l'ensemble des valeurs d'entrée avec :
  • I P o r t s {\displaystyle IPorts} l'ensemble des ports d'entrée,
  • V X {\displaystyle V_{X}} l'ensemble des valeurs possibles sur les ports d'entrée,
• Y = { ( p , v ) | p ∈ O P o r t s , v ∈ V Y {\displaystyle Y=\{(p,v)|p\in OPorts,v\in V_{Y}} est l'ensemble des valeurs de sortie avec :
  • O P o r t s {\displaystyle OPorts} l'ensemble des ports de sortie,
  • V Y {\displaystyle V_{Y}} l'ensemble des valeurs possibles sur les ports de sortie,
• S {\displaystyle S} est l'ensemble des états,
• δ i n t : S → S {\displaystyle \delta _{int}:S\rightarrow S} la fonction de transition interne,
• δ e x t : Q × X b → {\displaystyle \delta _{ext}:Q\times X^{b}\rightarrow } la fonction de transition externe où :
  • X b {\displaystyle X^{b}} est un ensemble du sac d'éléments finis de X {\displaystyle X}
• δ c o n : S × X b → {\displaystyle \delta _{con}:S\times X^{b}\rightarrow } la fonction de conflit où :
  • δ c o n ( s , ∅ ) = δ i n t ( s ) {\displaystyle \delta _{con}(s,\emptyset )=\delta _{int}(s)}
• λ : S → Y b {\displaystyle \lambda :S\rightarrow Y^{b}} la fonction de sortie
• t a : S → R 0 + ∪ ∞ {\displaystyle ta:S\rightarrow \mathbb {R} _{0}^{+}\cup \infty } la fonction d'avancée du temps où :
  • Q = ( s , e ) | s ∈ S , 0 < e < t a ( s ) {\displaystyle Q={(s,e)|s\in S,0<e<ta(s)}}
  • e {\displaystyle e} est le temps écoulé depuis le dernier changement d'état.

La différence entre DEVS parallèle et le DEVS classique est l'utilisation de sac d'événements en entrée sur la fonction de transition externe. Un sac, ou bag dans la terminologie de B. P. Zeigler, est un ensemble d'événements non trié provenant d'une ou plusieurs sources différentes.

La fonction de conflit (B. P. Zeigler, dans [zeigler00]^{[réf. à confirmer]}, utilise le terme confluent transition function que nous traduisons ici par fonction de conflit), δ c o n {\displaystyle \delta _{con}} , introduite par DEVS parallèle, donne la possibilité au modélisateur de choisir, pour un modèle, entre ses événements externes et interne s'ils ont lieu à la même date. Cette fonction remplace la fonction de sélection de DEVS classique.

La structure d'un modèle couplé dans DEVS parallèle est identique à celle définie précédemment. Les ensembles E I C {\displaystyle EIC} et E O C {\displaystyle EOC} , respectivement les ensembles de connexions entre le modèle couplé et les sous-modèles, et les sous-modèles vers le modèle couplé, n'existent plus en raison de la mise à plat de la hiérarchie de modèle DEVS. De la même manière, la fonction de sortie, λ {\displaystyle \lambda } , du modèle couplé n'a plus lieu d'exister. La définition du modèle couplé est la suivante :

N = ⟨ D , { M d } , I C ⟩ {\displaystyle N=\langle D,\{M_{d}\},IC\rangle }

Où pour chaque d ∈ D {\displaystyle d\in D}  :

• M d {\displaystyle M_{d}} est un modèle atomique DEVS parallèle

La différence entre DEVS parallèle et DEVS classique intervient surtout dans la définition des fonctions de transitions. Pour simplifier la définition de ces fonctions, nous définissons les ensembles suivants :

• Les modèles imminents, I M M ( s ) {\displaystyle IMM(s)} dont des sorties vont être générées juste avant la prochaine transition :

I M M ( s ) = { d | σ d = t a ( s ) } {\displaystyle IMM(s)=\{d|\sigma _{d}=ta(s)\}}

• Ensemble des modèles recevant au moins un message en entrée :

I N F ( s ) = { d | i ∈ I C i , d , i ∈ I M M ( s ) ∧ x d b ∉ ∅ } {\displaystyle INF(s)=\{d|i\in IC_{i,d},i\in IMM(s)\wedge x_{d}^{b}\notin \emptyset \}} avec x b {\displaystyle x^{b}} un sac d'événement en entrée : x d b = { I C i , d ( λ i ( s i ) ) | i ∈ I M M ( s ) ∩ I C i , d } {\displaystyle x_{d}^{b}=\{IC_{i,d}(\lambda _{i}(s_{i}))|i\in IMM(s)\cap IC_{i,d}\}}

• Un sous-ensemble des modèles de I M M ( s ) {\displaystyle IMM(s)} recevant au moins une entrée et effectuant une transition interne :

C O N F ( s ) = I M M ( s ) ∩ I N F ( s ) {\displaystyle CONF(s)=IMM(s)\cap INF(s)}

• Un sous-ensemble des modèles de I M M ( s ) {\displaystyle IMM(s)} qui n'ont pas de messages d'entrée :

I N T ( s ) = I M M ( s ) − I N F ( s ) {\displaystyle INT(s)=IMM(s)-INF(s)}

• Un sous-ensemble des modèles de I M M ( s ) {\displaystyle IMM(s)} recevant un événement en entrée mais n'effectuant de transition interne :

E X T ( s ) = I N F ( s ) − I M M ( s ) {\displaystyle EXT(s)=INF(s)-IMM(s)}

La fonction d'avancée du temps se traduit alors : t a ( s ) = m i n i m u m { σ d | d ∈ D } {\displaystyle ta(s)=minimum\{\sigma _{d}|d\in D\}} Où :

• s ∈ S {\displaystyle s\in S}
• σ d = t a ( s d ) − e d {\displaystyle \sigma _{d}=ta(s_{d})-e_{d}}

La fonction de transition interne résultante est le compromis des quatre types de transition, transition internes I N T ( s ) {\displaystyle INT(s)} , externes E X T ( s ) {\displaystyle EXT(s)} et en conflit C O N F ( s ) {\displaystyle CONF(s)} . Nous définissons : δ i n t ( s ) = ( … , ( s d ′ , e d ′ ) , … ) {\displaystyle \delta _{int}(s)=(\ldots ,(s'_{d},e'_{d}),\ldots )} , où :

• ( s d ′ , e d ′ ) = ( δ i n t , d ( s d ) , 0 ) p o u r d ∈ I N T ( s ) {\displaystyle (s'_{d},e'_{d})=(\delta _{int,d}(s_{d}),0)pourd\in INT(s)}
• ( s d ′ , e d ′ ) = ( δ e x t , d ( s d , e d + t a ( s ) , x d b ) , 0 ) {\displaystyle (s'_{d},e'_{d})=(\delta _{ext,d}(s_{d},e_{d}+ta(s),x_{d}^{b}),0)} pour d ∈ E X T ( s ) {\displaystyle d\in EXT(s)}
• ( s d ′ , e d ′ ) = ( δ c o n , d ( s d , x d b ) , 0 ) {\displaystyle (s'_{d},e'_{d})=(\delta _{con,d}(s_{d},x_{d}^{b}),0)} pour d ∈ C O N F ( s ) {\displaystyle d\in CONF(s)}
• ( s d ′ , e d ′ ) = ( s d , e d + t a ( s ) ) {\displaystyle (s'_{d},e'_{d})=(s_{d},e_{d}+ta(s))} dans les autres cas

La fonction de transition externe découpe le sac d'événements x b {\displaystyle x^{b}} vers les modèles influencés par l'événement x d b {\displaystyle x_{d}^{b}} . Elle est définie comme :

δ e x t ( s , e , x b ) = ( … , ( s d ′ , e d ′ ) , … ) {\displaystyle \delta _{ext}(s,e,x^{b})=(\ldots ,(s'_{d},e'_{d}),\ldots )} Où :

• 0 < e < t a ( s ) {\displaystyle 0<e<ta(s)}
• ( s d ′ , e d ′ ) = ( δ e x t , d ( s d , e d + e , x d b ) , 0 ) {\displaystyle (s'_{d},e'_{d})=(\delta _{ext,d}(s_{d},e_{d}+e,x_{d}^{b}),0)} pour d ∈ E I C {\displaystyle d\in EIC}
• ( s d ′ , e d ′ ) = ( s d , e d + e ) ( s ) ) {\displaystyle (s'_{d},e'_{d})=(s_{d},e_{d}+e)(s))} dans les autres cas

Enfin, la fonction de conflit est appelée quand un modèle possède un événement interne et au moins un événement externe à la même date. À la différence de DEVS classique qui doit prendre en compte les événements des connexions de l'ensemble E I C {\displaystyle EIC} , la fonction de conflit, dans un environnement à plat de la hiérarchie, se traduit de la même manière que la fonction de transition interne : δ i n f ( s , x b ) = ( … , ( s d ′ , e d ′ ) , … ) {\displaystyle \delta _{inf}(s,x^{b})=(\ldots ,(s'_{d},e'_{d}),\ldots )} Où :

• ( s d ′ , e d ′ ) = ( δ i n t , d ( s d ) , 0 ) {\displaystyle (s'_{d},e'_{d})=(\delta _{int,d}(s_{d}),0)} pour d ∈ I N T ( s ) {\displaystyle d\in INT(s)}
• ( s d ′ , e d ′ ) = ( δ e x t , d ( s d , e d + t a ( s ) , x d b ) , 0 ) {\displaystyle (s'_{d},e'_{d})=(\delta _{ext,d}(s_{d},e_{d}+ta(s),x_{d}^{b}),0)} pour d ∈ E X T ( s ) {\displaystyle d\in EXT(s)}
• ( s d ′ , e d ′ ) = ( δ c o n , d s d , x d b ) , 0 ) {\displaystyle (s'_{d},e'_{d})=(\delta _{con,d}s_{d},x_{d}^{b}),0)} pour d ∈ C O N F ( s ) {\displaystyle d\in CONF(s)}
• ( s d ′ , e d ′ ) = ( s d , e d + t a ( s ) ) {\displaystyle (s'_{d},e'_{d})=(s_{d},e_{d}+ta(s))} dans les autres cas

• « adevs »^{(Archive.org • Wikiwix • Google • Que faire ?)} (consulté le 7 avril 2013)
• CD++
• DEVS/C++
• DEVS/HLA
• DEVSJAVA
• « DEVSSim++ »^{(Archive.org • Wikiwix • Google • Que faire ?)} (consulté le 7 avril 2013)
• GALATEA
• GK-DEVS
• DEVS++
• DEVS#
• fwkDEVS
• JDEVS
• PF3S
• Python DEVS
• SimBeans
• SmallDEVS
• VLE
• DEVSimPy
• ProjectDEVS

• [Cellier91] (en) François E. Cellier, Continuous System Modeling, Springer, 1991, 1^re éd., 755 p. (ISBN 978-0-387-97502-3, LCCN 90025286, lire en ligne)
• [CK06] (en) François E. Cellier and Ernesto Kofman, Continuous System Simulation, New York, Springer, 2006, 1^re éd., 643 p. (ISBN 978-0-387-26102-7, LCCN 2005936516, lire en ligne)
• [Zeigler68] (en) Bernard Zeigler, On the Feedback Complexity of Automata : Thèse de doctorat, University of Michigan, 1968
• [Zeigler76] (en) Bernard Zeigler, Theory of Modeling and Simulation, Wiley Interscience, New York, 1976, 1^re éd.
• [Zeigler84] (en) Bernard Zeigler, Multifacetted Modeling and Discrete Event Simulation, Academic Press, London; Orlando, 1984, 372 p. (ISBN 978-0-12-778450-2, LCCN 83072316)
• [Zeigler87] (en) Bernard Zeigler, « Hierarchical, modular discrete-event modelling in an object-oriented environment », SIMULATION, vol. 49,‎ 1987, p. 219–230
• [ZKP00] (en) Bernard Zeigler, Tag Gon Kim, Herbert Praehofer, Http : //acims.eas.asu.edu/PUBLICATIONS/HTML/tms2e.html Theory of Modeling and Simulation, Academic Press, New York, 2000, 2^e éd., 510 p. (ISBN 978-0-12-778455-7, LCCN 99064635, lire en ligne)

• QSS, méthode d'intégration à événements discrets

• Portail des mathématiques
• Portail de l'informatique théorique