.. Generated from papers/intro/paper.rst -- do not edit here. Overview of a Unified DES Simulation Framework ============================================== Model, Computations and Paradigms --------------------------------- Let a **model** (:math:`M`) be defined as a finite set of state-changing event computations, :math:`e`. .. math:: 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 :math:`e`. 2. **Pardigm Exclusivity:** A given :math:`e_i` is scheduled following exactly one paradigm; and this paradigm is established when :math:`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 :math:`e_i \in M` is consequently assigned to exactly one of these three paradigms. Let :math:`P`, :math:`E`, and :math:`A` denote the subsets of :math:`M` whose computations are assigned to the periodic, event-based, and agent-based paradigms, respectively. Their membership is therefore defined as .. math:: \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} .. raw:: latex \Needspace{9\baselineskip} By paradigm exclusivity, these sets are pairwise disjoint, and together they contain every state-changing computation in the model: .. math:: M = P \mathbin{\dot\cup} E \mathbin{\dot\cup} A where :math:`\dot\cup` denotes a disjoint union. Transformations and Event Segments ---------------------------------- Let an **event segment model** (:math:`M'`) be defined as a finite set of event segments, :math:`e'`. .. math:: M' = \{e'_1, e'_2, \ldots e'_m\} And a gate transformation: .. math:: G : e^{+} \rightarrow e'^{+} :math:`G` transforms one or more :math:`e` into one or more :math:`e'`. The purpose of a **gate transformation** is to transform the state-changing event computations into **event segments** :math:`e'` which are state-changing computations that are self-scheduling for execution by our proposed unified DES kernel. More specifically, the resulting :math:`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 :math:`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: .. math:: \begin{aligned} G_P &: P \rightarrow P', \\ G_E &: E \rightarrow E', \\ G_A &: A \rightarrow A'. \end{aligned} For a paradigm set :math:`X \in \{P, E, A\}`, partition :math:`X` into disjoint nonempty groups :math:`X = \bigcup_k X_k` (the units on which the paradigm's transform acts — e.g. the :math:`\mathrm{Pi}_{p,\delta}` classes for :math:`P`, singletons for :math:`E` and :math:`A`), and define :math:`G_X` as the setwise extension of :math:`G` across these groups: .. math:: 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: .. math:: M' = P' \mathbin{\dot\cup} E' \mathbin{\dot\cup} A' where :math:`M'` is an event-segment representation of :math:`M`. The transformation does not change the modeled behavior. Thus, :math:`M` and :math:`M'` are **semantically equivalent**: .. math:: M \equiv M' where :math:`\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: .. math:: \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} Here, :math:`\tau_P`, :math:`\tau_E`, and :math:`\tau_A` perform the paradigm-specific transformations. The universal transformation :math:`\tau_0` propagates resource changes to event segments waiting on those resources, causing affected segments to become schedulable. :math:`\tau_0` : Universal Transform .................................... The **universal transformation** is: .. math:: \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} } where :math:`\Vert` denotes concatenation. * :math:`\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 :math:`\tau_0` conservatively. Appending ``scan`` where it is not required is a no-op. .. raw:: latex \Needspace{20\baselineskip} :math:`\tau_P` : Periodic Paradigm Transform ............................................ For each period :math:`p` and offset :math:`\delta`, define the set .. math:: \mathrm{Pi}_{p,\delta} = \{\,e \in P \mid \operatorname{period}(e)=p \land \operatorname{offset}(e)=\delta\,\} For each nonempty :math:`\mathrm{Pi}_{p,\delta}`, let .. math:: e^+ = \mathrm{Pi}_{p,\delta} where :math:`e^+` denotes one or more periodic event computations that share the same period and offset. Let :math:`e'` denote the compiled event segment representing the group :math:`e^{+}`. The **periodic paradigm transformation** is then .. math:: \boxed{ \begin{gathered} \tau_P : e^{+} \rightarrow e', \\[8pt] \tau_P(e^{+}) = e' \Vert \texttt{sched}(p,e') \end{gathered} } The appended ``sched`` operation causes :math:`e'` to reschedule itself with period :math:`p` upon each execution. Note that the first occurrence of each :math:`e'` is scheduled at offset :math:`\delta`. :math:`\tau_E` : Event-Based Paradigm Transform ............................................... The **event-based paradigm transformation** is: .. math:: \boxed{ \begin{gathered} \tau_E : e \rightarrow e' \\[8pt] \tau_E(e) = e' \end{gathered} } * :math:`\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 :math:`e'`. .. raw:: latex \Needspace{40\baselineskip} :math:`\tau_A` : Agent-Based Paradigm Transform ............................................... The **agent-based paradigm transformation** is: .. math:: \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} } The indices :math:`1,\ldots,n` above are with respect to a single agent computation in the abstract; once instantiated for a particular agent instance with context :math:`c`, each segment carries that context as an additional subscript, written :math:`e'_{c,1},\ldots,e'_{c,n}`, as used in :math:`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, :math:`c`. * For a particular agent instance identified by context :math:`c`, the resulting transformed agent graph: .. math:: 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 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 :math:`R_c`. The initial event segment is scheduled when the agent is launched. A segment with no successor terminates the agent. .. raw:: latex \Needspace{25\baselineskip} Kernel ------ The simulation kernel required to run :math:`M'` is extremely simple, having no paradigm-specific aspect and just these components: * event list * :math:`t`, the current time * MAX_TIME, the defined end of simulation time .. code-block:: // 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 .. raw:: latex \Needspace{10\baselineskip} 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.