Discrete Event System Specification

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

Sommaire

Histoire

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 1976 dans la première version de son ouvrage "Theory of modelling and simulation".

Formalisme

Extensions de DEVS

Parallel-DEVS

Cette extension, développée par B.P. Zeigler 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] avec des techniques optimistes, de type Time Warp, et pessimistes. Ces techniques, bien que très bien décrites, n'ont pas été mise en place pour des raisons d'utilités dans les modèles que nous utilisons.

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 :

DEVS = \langle X, Y, S, \delta_{ext}, \delta_{int}, \delta_{con}, \lambda,ta \rangle

Où :

  • X = \{(p,v)|p \in IPorts, v \in V_X est l'ensemble des valeurs d'entrée avec :
    • IPorts l'ensemble des ports d'entrée,
    • VX l'ensemble des valeurs possibles sur les ports d'entrée,
  • Y = \{(p,v)|p \in OPorts, v \in V_Y est l'ensemble des valeurs de sortie avec :
    • OPorts l'ensemble des ports de sortie,
    • VY l'ensemble des valeurs possibles sur les ports de sortie,
  • S est l'ensemble des états,
  • \delta_{int} : S \rightarrow S la fonction de transition interne,
  • \delta_{ext} : Q \times X^b \rightarrow la fonction de transition externe où :
    • Xb est un ensemble du sac d'éléments finis de X
  • \delta_{con} : S \times X^b \rightarrow la fonction de conflit où :
    • \delta_{con}(s, \emptyset) = \delta_{int}(s)
  • \lambda : S \rightarrow Y^b la fonction de sortie
  • ta : S \rightarrow \mathbb{R}_0^+ \cup \infty la fonction d'avancée du temps où :
    • Q = {(s,e)|s \in S,0 < e < ta(s)}
    • 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], utilise le terme confluent transition function que nous traduisons ici par fonction de conflit), δ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 EIC et 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, λ, du modèle couplé n'a plus lieu d'exister. La définition du modèle couplé est la suivante :

N = \langle D, \{M_d\}, IC \rangle

Où pour chaque d \in D :

  • Md 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, IMM(s) dont des sorties vont être générées juste avant la prochaine transition :

IMM(s) = {d | σd = ta(s)}

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

INF(s) = \{d|i \in IC_{i,d}, i \in IMM(s) \wedge x^b_d \notin \emptyset \} avec xb un sac d'événement en entrée : x^b_d = \{IC_{i,d}(\lambda_i(s_i))|i \in IMM(s) \cap IC_{i,d}\}

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

CONF(s) = IMM(s) \cap INF(s)

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

INT(s) = IMM(s) − INF(s)

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

EXT(s) = INF(s) − IMM(s)

La fonction d'avancée du temps se traduit alors : ta(s) = minimum\{\sigma_d|d \in D\} Où :

  • s \in S
  • σd = ta(sd) − ed

La fonction de transition interne résultante est le compromis des quatre types de transition, transition internes INT(s), externes EXT(s) et en conflit CONF(s). Nous définissons : \delta_{int}(s) = (\ldots,(s'_d,e'_d), \ldots) , où :

  • (s'_d,e'_d) = (\delta_{int,d}(s_d),0) pour d \in INT(s)
  • (s'_d,e'_d) = (\delta_{ext,d}(s_d,e_d + ta(s),x^b_d),0) pour d \in EXT(s)
  • (s'_d,e'_d) = (\delta_{con,d}(s_d,x^b_d),0) pour d \in CONF(s)
  • (s'd,e'd) = (sd,ed + ta(s)) dans les autres cas

La fonction de transition externe découpe le sac d'événement xb vers les modèles influencés par l'événement x^b_d. Elle est défini comme :

\delta_{ext}(s,e,x^b) = (\ldots,(s'_d,e'_d), \ldots) Où :

  • 0 < e < ta(s)
  • (s'_d,e'_d) = (\delta_{ext,d}(s_d,e_d + e, x^b_d),0) pour d \in EIC
  • (s'd,e'd) = (sd,ed + 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 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 : \delta_{inf}(s,x^b) = (\ldots, (s'_d,e'_d),\ldots) Où :

  • (s'd,e'd) = (δint,d(sd),0) pour d \in INT(s)
  • (s'_d,e'_d) = (\delta_{ext,d}(s_d,e_d + ta(s),x^b_d),0) pour d \in EXT(s)
  • (s'_d,e'_d) = (\delta_{con,d}s_d,x^b_d),0) pour d \in CONF(s)
  • (s'd,e'd) = (sd,ed + ta(s)) dans les autres cas

Plate-formes

Références

  • [Cellier91] (en) Francois E. Cellier, Continuous System Modeling, Springer, 1991, firste éd. (ISBN 978-0-387-97502-3) (LCCN 90025286) 
  • [CK06] (en) Francois E. Cellier and Ernesto Kofman, Continuous System Simulation, Springer, 2006, firste éd. (ISBN 978-0-387-26102-7) (LCCN 2005936516) 
  • [Zeigler68] (en) Bernard Zeigler, On the Feedback Complexity of Automata, University of Michigan, 1968, Ph.D. Thesise éd. 
  • [Zeigler76] (en) Bernard Zeigler, Theory of Modeling and Simulation, Wiley Interscience, New York, 1976, firste éd. 
  • [Zeigler84] (en) Bernard Zeigler, Multifacetted Modeling and Discrete Event Simulation, Academic Press, London; Orlando, 1984 (ISBN 978-0-12-778450-2) (LCCN 83072316) 
  • [Zeigler87] Bernard Zeigler, « Hierarchical, modular discrete-event modelling in an object-oriented environment », dans 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, seconde éd. (ISBN 978-0-12-778455-7) (LCCN 99064635) 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Discrete Event System Specification de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Finite & Deterministic Discrete Event System Specification — FD DEVS (Finite Deterministic Discrete Event System Specification) is a formalism for modeling and analyzing discrete event dynamic systems in both simulation and verification ways. FD DEVS also provides modular and hierarchical modeling features …   Wikipedia

  • Discrete event simulation — In discrete event simulation, the operation of a system is represented as a chronological sequence of events. Each event occurs at an instant in time and marks a change of state in the system [1]. For example, if an elevator is simulated, an… …   Wikipedia

  • Discrete event dynamic system — In control engineering, a discrete event dynamic system (DEDS) is a discrete state, event driven system of which the state evolution depends entirely on the occurrence of asynchronous discrete events over time. Although similar to continuous… …   Wikipedia

  • System time — Unix date command In computer science and computer programming, system time represents a computer system s notion of the passing of time. In this sense, time also includes the passing of days on the calendar. System time is measured by a system… …   Wikipedia

  • DEVS — 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 à… …   Wikipédia en Français

  • DEVS — abbreviating Discrete Event System Specification is a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event systems which might be described by state transition tables, and continuous state… …   Wikipedia

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • Distributed operating system — A distributed operating system is the logical aggregation of operating system software over a collection of independent, networked, communicating, and spatially disseminated computational nodes.[1] Individual system nodes each hold a discrete… …   Wikipedia

  • SP-DEVS — abbreviating Schedule Preserving Discrete Event System Specification is a formalism for modeling and analyzing discrete event systems in both simulation and verification ways. SP DEVS also provides modular and hierarchical modeling features which …   Wikipedia

  • P system — For the computer p System, see UCSD p System. A P system is a computational model in the field of computer science that performs calculations using a biologically inspired process. They are based upon the structure of biological cells,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”