- Source: Simulation algorithms for coupled DEVS
Given a coupled DEVS model, simulation algorithms are methods to generate the model's legal behaviors, which are a set of trajectories not to reach illegal states. (see behavior of a Coupled DEVS model.) [Zeigler84] originally introduced the algorithms that handle time variables related to lifespan
t
s
∈
[
0
,
∞
]
{\displaystyle t_{s}\in [0,\infty ]}
and elapsed time
t
e
∈
[
0
,
∞
)
{\displaystyle t_{e}\in [0,\infty )}
by introducing two other time variables, last event time,
t
l
∈
[
0
,
∞
)
{\displaystyle t_{l}\in [0,\infty )}
, and next event time
t
n
∈
[
0
,
∞
]
{\displaystyle t_{n}\in [0,\infty ]}
with the following relations:
and
where
t
∈
[
0
,
∞
)
{\displaystyle t\in [0,\infty )}
denotes the current time. And the remaining time,
is equivalently computed as
apparently
t
r
∈
[
0
,
∞
]
{\displaystyle t_{r}\in [0,\infty ]}
.
Based on these relationships, the algorithms to simulate the behavior of a given Coupled DEVS are written as follows.
Algorithm
algorithm DEVS-coordinator
Variables:
parent // parent coordinator
t
l
{\displaystyle t_{l}}
: // time of last event
t
n
{\displaystyle t_{n}}
: // time of next event
N
=
(
X
,
Y
,
D
,
{
M
i
}
,
C
x
x
,
C
y
x
,
C
y
y
,
S
e
l
e
c
t
)
{\displaystyle N=(X,Y,D,\{M_{i}\},C_{xx},C_{yx},C_{yy},Select)}
// the associated Coupled DEVS model
when receive init-message(Time t)
for each
i
∈
D
{\displaystyle i\in D}
do
send init-message(t) to child
i
{\displaystyle i}
t
l
←
max
{
t
l
i
:
i
∈
D
}
{\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}
;
t
n
←
min
{
t
n
i
:
i
∈
D
}
{\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}
;
when receive star-message(Time t)
if
t
≠
t
n
{\displaystyle t\neq t_{n}}
then
error: bad synchronization;
i
∗
←
S
e
l
e
c
t
(
{
i
∈
D
:
t
n
i
=
t
n
}
)
;
{\displaystyle i^{*}\leftarrow Select(\{i\in D:t_{ni}=t_{n}\});}
send star-message(t)to
i
∗
{\displaystyle i^{*}}
t
l
←
max
{
t
l
i
:
i
∈
D
}
{\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}
;
t
n
←
min
{
t
n
i
:
i
∈
D
}
{\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}
;
when receive x-message(
x
∈
X
{\displaystyle x\in X}
, Time t)
if
(
t
l
≤
t
{\displaystyle (t_{l}\leq t}
and
t
≤
t
n
)
{\displaystyle t\leq t_{n})}
== false then
error: bad synchronization;
for each
(
x
,
x
i
)
∈
C
x
x
{\displaystyle (x,x_{i})\in C_{xx}}
do
send x-message(
x
i
{\displaystyle x_{i}}
,t) to child
i
{\displaystyle i}
t
l
←
max
{
t
l
i
:
i
∈
D
}
{\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}
;
t
n
←
min
{
t
n
i
:
i
∈
D
}
{\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}
;
when receive y-message(
y
i
∈
Y
i
{\displaystyle y_{i}\in Y_{i}}
, Time t)
for each
(
y
i
,
x
i
)
∈
C
y
x
{\displaystyle (y_{i},x_{i})\in C_{yx}}
do
send x-message(
x
i
{\displaystyle x_{i}}
,t) to child
i
{\displaystyle i}
if
C
y
y
(
y
i
)
≠
ϕ
{\displaystyle C_{yy}(y_{i})\neq \phi }
then
send y-message(
C
y
y
(
y
i
)
{\displaystyle C_{yy}(y_{i})}
, t) to parent;
t
l
←
max
{
t
l
i
:
i
∈
D
}
{\displaystyle t_{l}\leftarrow \max\{t_{li}:i\in D\}}
;
t
n
←
min
{
t
n
i
:
i
∈
D
}
{\displaystyle t_{n}\leftarrow \min\{t_{ni}:i\in D\}}
;
See also
Coupled DEVS
Behavior of Coupled DEVS
Simulation Algorithms for Atomic DEVS
References
[Zeigler84] Bernard Zeigler (1984). Multifacetted Modeling and Discrete Event Simulation. Academic Press, London; Orlando. ISBN 978-0-12-778450-2.
[ZKP00] Bernard Zeigler; Tag Gon Kim; Herbert Praehofer (2000). Theory of Modeling and Simulation (second ed.). Academic Press, New York. ISBN 978-0-12-778455-7.