Models of Computation for Dymodetron Simulations

What are “models of computation”?

When you build a model, you use a certain set of underlying concepts to express the model. These underlying concepts are your model of computation. In other words, what are the kinds of things that will be computed, what are the kinds of relationships that they have with one another? What elemental concepts make up the set of widgets you can use to build your model?

For example, you might build a model that consists of a set of coupled first order ordinary differential equations (ODEs). The underlying widgets in the toolbox for constructing that model are:

  1. A continuous notion of time.

  2. A set of quantities that you’ll use to quantify different aspects of the system. Sometimes these quantities are called states.

  3. Equations to express the rate of change of each state quantity as a function of the other quantities in the system, and time.

  4. Usually, a number of parameters are present within the equations.

  5. You’ll have a value or range of values for each parameter.

  6. For each quantity in the system, you’ll have an initial value or range of values for the state quantity and its initial rate of change.

Those concepts together make up a model of computation for ODE systems. Depending on the system you are modeling and the questions that you want to ask your model, this underlying model of computation may be perfectly appropriate, or it may be completely useless.

Another example of a model of computation is the one that Dymodetron supports, state machines, described below.

State Machines

Dymodetron supports a single model of computation: state machines. This section briefly summarizes this model of computation. More details about each piece of the puzzle are available in the section on modeling constructs.

Note

The word ‘state’ in ‘state machine’ does not mean exactly the same thing it means in the ODE example we discussed earlier. But, it is similar in the sense that states are a way of describing/quantifying a simulated entity. In Dymodetron state machines, we describe/quantify simulated entities using two distinct concepts: states, and entity attributes. Both are discussed in this section.

Dymodetron state machines are an interpretation of the concept of Harel statecharts, which is a formalism for describing complex systems. They are also similar to UML state machines, which themselves were built on Harel’s statechart ideas. Dymodetron supports hierarchical state machines but does not support Harel’s “orthogonal regions”, nor does it support “history” states (although with some work it could).

There’s a description of an example Dymodetron state machine in the overview. We repeat the illustration of the example diagram below.

%%{init: { 'theme': 'base' } }%% stateDiagram-v2 awake sleeping [*] --> sleeping : initial_event sleeping --> awake : not_tired_event awake --> sleeping : tired_event state awake { drinking eating staring_out_window [*] --> staring_out_window : initial_event staring_out_window --> eating : hungry_event eating --> staring_out_window : not_hungry_event staring_out_window --> drinking : thirsty_event drinking --> staring_out_window : not_thirsty_event }

Entities

Entities are the individual nouns in your model, which will be described as having attributes and states. Your model may have any number of entities, within computing resource constraints.

For example, your entities might be cats.

Entity Attributes

Entity attributes are the quantifiable, measurable characteristics of your entities. Each individual entity has its own value for each entity attribute.

For example, you might measure the weight and height of your cats.

States

States are the atomic unit of the description of the behaviors of your entities. An individual entity is described as being in a discrete set of states at any given time. An individual state is a binary proposition: an entity is either in that state, or it’s not. The model might have any number of states that an entity can be in. As time goes on, the set of states that an entity is in will change. This happens via state transitions triggered by events. Events can be generated by state entry and exit actions. When entities transition between states, the entry and exit of states can trigger follow-on transitions; this ongoing process propagates the behavior of the model.

States are organized into state machines. There can be multiple state machines, each describing different aspects of the behavior of the entities. The multiple state machines execute concurrently.

For example, you might have a state machine to describe the conscious behavior of the cat performing its daily routine of sleeping, eating, and drinking. Separately, you might have a state machine describing the evolution of the cat’s inner dialog, which goes on irrespective of the conscious daily cat routine, and which may be alternating back and forth between instinctive ancestral memories of ancient egypt and ruminations on better places to hide a lizard in the house where you’ll be most surprised and disgusted when you find it.

In the example state machine diagram above, the states a cat can be in are: ‘sleeping’, ‘awake’, ‘staring_out_window’, ‘eating’, and ‘drinking’. Due to the hierarchical nature of this particular state machine, if a cat is in state ‘staring_out_window’, ‘eating’, or ‘drinking’, it is also simultaneously in state ‘awake’.

Sub-state-machines

A state can have a state machine within it. When the state is entered, the initial transition of the sub-state-machine fires, and the enclosed state machine can begin responding to events by transitioning between states in the sub-state-machine. This is a key feature for managing the complexity of the model while still enabling interesting, useful models.

In the example state machine above, we model a cat as either “asleep’ or “awake”. While it’s awake, it has additional states that it can transition in and out of as events happen.

Events

Events cause transitions to trigger, causing entities to transition between states. Events are generated by action statements within state entry and exit actions. Events are targeted at a subset of entities in the system (one, many, or all).

In the example state machine above, the events are: ‘initial_event’, ‘tired_event’, ‘not_tired_event’, ‘hungry_event’, ‘not_hungry_event’, ‘thirsty_event’, and ‘not_thirsty_event’. Note that ‘initial_event’ is a special event that is present in every state machine, that takes the state machine from the initial state (black dot) to a modeler-defined state.

Transitions

Transitions are how entities can leave one state and enter another state. Transitions are triggered by a particular event, and define the source and target states.

When a particular event “arrives” at an entity, at a given time, the entity may or may not have any valid transitions to be triggered at that time. In this case, the event is ignored.

In the example state machine above, if the cat is in state ‘sleeping’, then when ‘not_tired_event’ arrives at a given cat entity instance, that cat will transition to state ‘awake’. If the same event arrives at a cat while it is in state ‘awake’, no transitions will occur, and the event is ignored.

Action statements

Action statements are sequences of logic and calculations that run within state entry and exit actions. Action statements can implement numerical calculations to update the entity attributes. They can also be used to generate events on subsets (1, many, or all) of the entities in the system.

State Entry and Exit Actions

A state can be defined to have action statements executed when the state is entered, or when it is exited, or both. Those actions can result in updates to entity attribute values, and/or the generation of additional events.

Time

State machines have a discrete time model. Events are scheduled to happen at a certain time. Once all the events at that time have occurred, the simulation time progresses to the time of the next event. So time skips along from one event time to the next, until some simulation termination condition is met.

Time is measured in “ticks”. “Ticks” are whatever you want them to be: years, days, hours, minutes, seconds, nanoseconds, etc. Just make sure to be consistent!

Heterogeneous models of computation

Dymodetron doesn’t support this yet, but has aspirations to support heterogeneous models of computation. This would enable the construction of models that use a heterogeneous mix of models of computation, integrated together. This is useful in that it would allow user models to express different kind of system behavior in the manner that is most useful and efficient for the question/topic at hand.

Mixing models of computation together requires addressing two key integration problems:

  1. How to integrate the different notions of time present in the different models of computation?

  2. How to integrate behaviors together between the two models of computation, so that models can be built of elements that use these different widgets but are still able to interact with each other?

    • For example, if integrating an ODE model of compute with a state machine model of compute, how can state machine events be used to change ODE model parameters? Similarly, how can ODE state (or rate) thresholds be used to trigger events in a state machine?

This idea of models relying on a heterogeneous mix of models of computation isn’t new, and it has been explored. For example, here’s a book on the topic. And here’s a widely used commercial tool that implements the idea.