Overview of a Unified DES Simulation Framework

Overview of a Unified DES Simulation Framework#

Model, Computations and Paradigms#

Let a model (\(M\)) be defined as a finite set of state-changing event computations, \(e\).

\[M = \{e_1, e_2, \ldots e_n\}\]

We adopt these axioms:

  1. State Mutation: The model state is changed only via the execution of \(e\).

  2. Pardigm Exclusivity: A given \(e_i\) is scheduled following exactly one paradigm; and this paradigm is established when \(e_i\) is defined.

There are many paradigms for scheduling state-changing event computations in a DES simulation. This framework considers four: periodic, iterative, event-based, and agent-based. The iterative paradigm is a special case of the periodic paradigm and is therefore not treated separately hereafter.

Each \(e_i \in M\) is consequently assigned to exactly one of these three paradigms. Let \(P\), \(E\), and \(A\) denote the subsets of \(M\) whose computations are assigned to the periodic, event-based, and agent-based paradigms, respectively.

Their membership is therefore defined as

\[\begin{split}\begin{aligned} P &= \{\,e \in M \mid e\text{ is periodic}\,\}, \\ E &= \{\,e \in M \mid e\text{ is event-based}\,\}, \\ A &= \{\,e \in M \mid e\text{ is agent-based}\,\}. \end{aligned}\end{split}\]

By paradigm exclusivity, these sets are pairwise disjoint, and together they contain every state-changing computation in the model:

\[M = P \mathbin{\dot\cup} E \mathbin{\dot\cup} A\]

where \(\dot\cup\) denotes a disjoint union.

Transformations and Event Segments#

Let an event segment model (\(M'\)) be defined as a finite set of event segments, \(e'\).

\[M' = \{e'_1, e'_2, \ldots e'_m\}\]

And a gate transformation:

\[G : e^{+} \rightarrow e'^{+}\]

\(G\) transforms one or more \(e\) into one or more \(e'\).

The purpose of a gate transformation is to transform the state-changing event computations into event segments \(e'\) which are state-changing computations that are self-scheduling for execution by our proposed unified DES kernel.

More specifically, the resulting \(e'_i\) is the compiled (executable) version of some original state-changing computation, along with the possible addition of scheduling code. It is notable that each \(e'_i\) is an executable block, and that the unified kernel executes such a block when it’s popped from the event list.

For each paradigm, a gate transformation is defined that maps the corresponding set of model computations into a set of event segments:

\[\begin{split}\begin{aligned} G_P &: P \rightarrow P', \\ G_E &: E \rightarrow E', \\ G_A &: A \rightarrow A'. \end{aligned}\end{split}\]

For a paradigm set \(X \in \{P, E, A\}\), partition \(X\) into disjoint nonempty groups \(X = \bigcup_k X_k\) (the units on which the paradigm’s transform acts — e.g. the \(\mathrm{Pi}_{p,\delta}\) classes for \(P\), singletons for \(E\) and \(A\)), and define \(G_X\) as the setwise extension of \(G\) across these groups:

\[G_X(X) = \bigcup_k G(X_k), \qquad X' = G_X(X)\]

The transformed model is the union of these three sets of event segments:

\[M' = P' \mathbin{\dot\cup} E' \mathbin{\dot\cup} A'\]

where \(M'\) is an event-segment representation of \(M\). The transformation does not change the modeled behavior. Thus, \(M\) and \(M'\) are semantically equivalent:

\[M \equiv M'\]

where \(\equiv\) denotes equivalence of model behavior.

Gate Composition#

Each gate transformation is composed of two transformations. The first is the paradigm transformation, which converts a paradigm-specific computation into an event-segment representation. The second is a universal transformation, applied to the resulting event segments regardless of paradigm.

For the three paradigms:

\[\begin{split}\begin{aligned} G_P &= \tau_0 \circ \tau_P, \\ G_E &= \tau_0 \circ \tau_E, \\ G_A &= \tau_0 \circ \tau_A. \end{aligned}\end{split}\]

Here, \(\tau_P\), \(\tau_E\), and \(\tau_A\) perform the paradigm-specific transformations. The universal transformation \(\tau_0\) propagates resource changes to event segments waiting on those resources, causing affected segments to become schedulable.

\(\tau_0\) : Universal Transform#

The universal transformation is:

\[\begin{split}\boxed{ \begin{gathered} \tau_0 : e' \rightarrow e' \\[8pt] \tau_0(e') = \begin{cases} e' \Vert \texttt{scan} & \text{if } e' \text{ can increase availability} \\[4pt] e' & \text{otherwise} \end{cases} \end{gathered} }\end{split}\]

where \(\Vert\) denotes concatenation.

  • \(\tau_0\) is defined over all event segments; it appends scan to those segments that can increase availability of a resource.

  • Availability increases in exactly two ways: a held unit is released, or a capacity is raised. A capacity reduction never increases availability, and therefore never requires a scan.

  • Only a suspendable computation can block on claim, hence only a suspendable computation can hold a unit, hence only a suspendable computation can release one. A segment of a non-suspendable paradigm therefore requires scan only if it raises a capacity.

  • Where appended, scan is the final operation of the segment, running after the segment’s own scheduling operation. It iterates the resources, granting each free unit to the longest-waiting segment blocked on it, and repeats until a full pass grants nothing.

  • An implementation may apply \(\tau_0\) conservatively. Appending scan where it is not required is a no-op.

\(\tau_P\) : Periodic Paradigm Transform#

For each period \(p\) and offset \(\delta\), define the set

\[\mathrm{Pi}_{p,\delta} = \{\,e \in P \mid \operatorname{period}(e)=p \land \operatorname{offset}(e)=\delta\,\}\]

For each nonempty \(\mathrm{Pi}_{p,\delta}\), let

\[e^+ = \mathrm{Pi}_{p,\delta}\]

where \(e^+\) denotes one or more periodic event computations that share the same period and offset.

Let \(e'\) denote the compiled event segment representing the group \(e^{+}\). The periodic paradigm transformation is then

\[\begin{split}\boxed{ \begin{gathered} \tau_P : e^{+} \rightarrow e', \\[8pt] \tau_P(e^{+}) = e' \Vert \texttt{sched}(p,e') \end{gathered} }\end{split}\]

The appended sched operation causes \(e'\) to reschedule itself with period \(p\) upon each execution. Note that the first occurrence of each \(e'\) is scheduled at offset \(\delta\).

\(\tau_E\) : Event-Based Paradigm Transform#

The event-based paradigm transformation is:

\[\begin{split}\boxed{ \begin{gathered} \tau_E : e \rightarrow e' \\[8pt] \tau_E(e) = e' \end{gathered} }\end{split}\]

  • \(\tau_E\) is the identity transform:

  • Of the events in the event paradigm, only those scheduled during model initialization are scheduled initially; the rest are scheduled only when scheduled by another \(e'\).

\(\tau_A\) : Agent-Based Paradigm Transform#

The agent-based paradigm transformation is:

\[\begin{split}\boxed{ \begin{gathered} \tau_A : e \rightarrow e'^{+} \\[8pt] \tau_A(e) = \{e'_1, e'_2, \cdots e'_n\}, \qquad n \geq 1 \end{gathered} }\end{split}\]

The indices \(1,\ldots,n\) above are with respect to a single agent computation in the abstract; once instantiated for a particular agent instance with context \(c\), each segment carries that context as an additional subscript, written \(e'_{c,1},\ldots,e'_{c,n}\), as used in \(A_c\) below.

  • An agent computation is divided into event segments at each point where the agent performs a timeout(), claim(), or release() operation. Each resulting segment retains access to the locals defined by the agent through a context, \(c\).

  • For a particular agent instance identified by context \(c\), the resulting transformed agent graph:

    \[ \begin{align}\begin{aligned}A_c = (V_c, R_c)\\V_c = \{e'_{c,1}, e'_{c,2}, \ldots, e'_{c,n}\}\\R_c \subseteq V_c \times V_c\end{aligned}\end{align} \]

    where each vertex is an event segment and each directed edge identifies a successor segment to be scheduled.

  • The transformation modifies each segment according to the operation at which the segment terminates:

    • A segment ending in timeout() is transformed to schedule its successor segment after the specified delay.

    • A segment ending in claim() is transformed to claim the specified resource and, when the claim succeeds, schedule its successor segment.

    • A segment ending in release() is transformed to release the specified resource and schedule its successor segment.

  • The transformed agent consists of self-scheduling segments whose scheduling operations identify successor segments through \(R_c\). The initial event segment is scheduled when the agent is launched. A segment with no successor terminates the agent.

Kernel#

The simulation kernel required to run \(M'\) is extremely simple, having no paradigm-specific aspect and just these components:

  • event list

  • \(t\), the current time

  • MAX_TIME, the defined end of simulation time

// kernel loop

done = false
ok = true
while (ok and not done) do
   t, e' = pop(eventlist)      // current time, new e' to execute

   if t > MAX_TIME             // stop before execution?
       done = true
   else
       ok = exec(e')           // stop after execution?
end

Result#

By applying the transformations to the model computations we have event segments that schedule themselves to run on a kernel that does not distinguish the various paradigms.