de_sim/examples/jupyter_examples/3. Ordering simultaneous events in DE-Sim.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<!-- :Author: Arthur Goldberg <Arthur.Goldberg@mssm.edu> -->\n",
"<!-- :Date: 2020-08-02 -->\n",
"<!-- :Copyright: 2020, Karr Lab -->\n",
"<!-- :License: MIT -->\n",
"# DE-Sim: Ordering simultaneous events\n",
"\n",
"DE-Sim makes it easy to build and simulate discrete-event models.\n",
"This notebook discusses DE-Sim's methods for controlling the execution order of simultaneous messages.\n",
"\n",
"## Installation\n",
"Use `pip` to install `de_sim`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Scheduling events with equal simulation times\n",
"\n",
"A discrete-event simulation may execute multiple events simultaneously, that is, at a particular simulation time.\n",
"To ensure that simulation runs are reproducible and deterministic, a simulator must provide mechanisms that deterministically control the execution order of simultaneous events.\n",
"\n",
"Two types of situations arise, *local* and *global*.\n",
"A local situation arises when a simulation object receives multiple event messages simultaneously, while a global situation arises when multiple simulation objects execute events simultaneously.\n",
"\n",
"Separate *local* and *global* mechanisms ensure that these situations are simulated deterministically.\n",
"The local mechanism ensures that simultaneous events are handled deterministically at a single simulation object, while the global mechanism ensures that simultaneous events are handled deterministically across all objects in a simulation.\n",
"\n",
"### Local mechanism: simultaneous event messages at a simulation object\n",
"The local mechanism, called *event superposition* after the [physics concept of superposition](https://en.wikipedia.org/wiki/Superposition_principle), involves two components:\n",
"\n",
"1. When a simulation object receives multiple event messages at the same time, the simulator passes all of the event messages to the object's event handler in a list.\n",
"(However, if simultaneous event messages have different handlers then the simulator raises a `SimulatorError` exception.)\n",
"2. The simulator sorts the events in the list so that any given list of events will always be arranged in the same order.\n",
"\n",
"Event messages are sorted by the pair (event message priority, event message content).\n",
"Sorting costs O(n log n), but since simultaneous events are usually rare, sorting event lists is unlikely to slow down simulations."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Simulation to 20 executed all messages in the order (Increment, Double).\n"
]
}
],
"source": [
"\"\"\" This example illustrates the local mechanism that handles simultaneous\n",
" event messages received by a simulation object\n",
"\"\"\"\n",
"import random\n",
"\n",
"import de_sim\n",
"from de_sim.event import Event\n",
"\n",
"class Double(de_sim.EventMessage):\n",
" 'Double value'\n",
"\n",
"class Increment(de_sim.EventMessage):\n",
" 'Increment value'\n",
"\n",
"class IncrementThenDoubleSimObject(de_sim.SimulationObject):\n",
" \"\"\" Execute Increment before Double, demonstrating superposition \"\"\"\n",
"\n",
" def __init__(self, name):\n",
" super().__init__(name)\n",
" self.value = 0\n",
"\n",
" def init_before_run(self):\n",
" self.send_events()\n",
"\n",
" def handle_superposed_events(self, event_list):\n",
" \"\"\" Process superposed events in an event list\n",
"\n",
" Each Increment message increments value, and each Double message doubles value.\n",
" Assumes that `event_list` contains an Increment event followed by a Double event.\n",
"\n",
" Args:\n",
" event_list (:obj:`event_list` of :obj:`de_sim.Event`): list of events\n",
" \"\"\"\n",
" for event in event_list:\n",
" if isinstance(event.message, Increment):\n",
" self.value += 1\n",
" elif isinstance(event.message, Double):\n",
" self.value *= 2\n",
" self.send_events()\n",
"\n",
" # The order of the message types in event_handlers, (Increment, Double), determines\n",
" # the sort order of messages in `event_list` received by `handle_superposed_events`\n",
" event_handlers = [(Increment, 'handle_superposed_events'),\n",
" (Double, 'handle_superposed_events')]\n",
"\n",
" def send_events(self):\n",
" # To show that the simulator delivers event messages to `handle_superposed_events`\n",
" # sorted into the order (Increment, Double), send them in a random order.\n",
" if random.randrange(2):\n",
" self.send_event(1, self, Double())\n",
" self.send_event(1, self, Increment())\n",
" else:\n",
" self.send_event(1, self, Increment())\n",
" self.send_event(1, self, Double())\n",
"\n",
" # Register the message types sent\n",
" messages_sent = (Increment, Double)\n",
"\n",
"\n",
"class TestSuperposition(object):\n",
"\n",
" def increment_then_double_from_0(self, iterations):\n",
" v = 0\n",
" for _ in range(iterations):\n",
" v += 1\n",
" v *= 2\n",
" return v\n",
"\n",
" def test_superposition(self, max_time):\n",
" simulator = de_sim.Simulator()\n",
" simulator.add_object(IncrementThenDoubleSimObject('name'))\n",
" simulator.initialize()\n",
" simulator.simulate(max_time)\n",
" for sim_obj in simulator.get_objects():\n",
" assert sim_obj.value, self.increment_then_double_from_0(max_time)\n",
" print(f'Simulation to {max_time} executed all messages in the order (Increment, Double).')\n",
"\n",
"TestSuperposition().test_superposition(20)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This example shows how event superposition handles simultaneous events.\n",
"An `IncrementThenDoubleSimObject` simulation object stores an integer value.\n",
"It receives two events every time unit, one carrying an `Increment` message and another containing a `Double` message.\n",
"Executing an `Increment` event increments the value, while executing a `Double` message event doubles the value.\n",
"The design for `IncrementThenDoubleSimObject` requires that it increments before doubling.\n",
"\n",
"Several features of DE-Sim and `IncrementThenDoubleSimObject` ensure this behavior:\n",
"\n",
"1. The mapping between event message types and event handlers, stored in the list `event_handlers`, contains `Increment` before `Double`. This gives events containing an `Increment` message a higher priority than events containing `Double`.\n",
"2. Under the covers, when DE-Sim passes superposed events to a subclass of [`SimulationObject`](https://docs.karrlab.org/de_sim/master/source/de_sim.html#de_sim.simulation_object.SimulationObject), it sorts the messages by their (event message priority, event message content), which sorts events with higher priority message types earlier.\n",
"3. The message handler `handle_superposed_events` receives a list of events and executes them in order.\n",
"\n",
"To challenge and test this superposition mechanism, the `send_events()` method in `IncrementThenDoubleSimObject` randomizes the order in which it sends `Increment` and `Double` events.\n",
"Finally, `TestSuperposition().test_superposition()` runs a simulation of `IncrementThenDoubleSimObject` and asserts that the value it computes equals the correct value for a sequence of increment and double operations."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Global mechanism: simultaneous event messages at multiple simulation objects\n",
"A *global* mechanism is needed to ensure that simultaneous events which occur at distinct objects in a simulation are executed in a deterministic order.\n",
"Otherwise, the discrete-event simulator might execute simultaneous events at distinct simulation objects in a different order in different simulation runs that use the same input.\n",
"When using a simulator that allows 0-delay event messages or global state shared between simulation objects -- both of which DE-Sim supports -- this can alter the simulation's predictions and thereby imperil debugging efforts, statistical analyses of predictions and other essential uses of simulation results.\n",
"\n",
"The global mechanism employed by DE-Sim conceives of the simulation time as a pair -- the event time, and a *sub-time* which breaks event time ties.\n",
"Sub-time values within a particular simulation time must be distinct.\n",
"Given that constraint, many approaches for selecting the sub-time would achieve the objective.\n",
"DE-Sim creates a distinct sub-time from the state of the simulation object receiving an event.\n",
"\n",
"The sub-time is a pair composed of a priority assigned to the simulation class and a unique identifier for each class instance.\n",
"Each simulation class defines a `class_priority` attribute that determines the relative execution order of simultaneous events by different simulation classes.\n",
"Among multiple instances of a simulation class, the attribute `event_time_tiebreaker`, which defaults to a simulation instance's unique name, breaks ties.\n",
"All classes have the same default priority of `LOW`. If class priorities are not set and `event_time_tiebreaker`s are not set for individual simulation objects, then an object's global priority is given by its name."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.0: MediumPrioritySimObj B running\n",
"0.0: LowPrioritySimObj A running\n",
"1.0: MediumPrioritySimObj B running\n",
"1.0: LowPrioritySimObj A running\n",
"2.0: MediumPrioritySimObj B running\n",
"2.0: LowPrioritySimObj A running\n",
"6 events executed\n"
]
}
],
"source": [
"from de_sim.simulation_object import SimObjClassPriority\n",
"\n",
"\n",
"class ExampleMsg(de_sim.EventMessage):\n",
" 'Example message'\n",
"\n",
"\n",
"class NoPrioritySimObj(de_sim.SimulationObject):\n",
"\n",
" def init_before_run(self):\n",
" self.send_event(0., self, ExampleMsg())\n",
"\n",
" # register the message types sent\n",
" messages_sent = (ExampleMsg, )\n",
"\n",
"\n",
"class LowPrioritySimObj(NoPrioritySimObj):\n",
"\n",
" def handler(self, event):\n",
" print(f\"{self.time}: LowPrioritySimObj {self.name} running\")\n",
" self.send_event(1., self, ExampleMsg())\n",
"\n",
" event_handlers = [(ExampleMsg, 'handler')]\n",
"\n",
" # have `LowPrioritySimObj`s execute at low priority\n",
" class_priority = SimObjClassPriority.LOW\n",
"\n",
"\n",
"class MediumPrioritySimObj(NoPrioritySimObj):\n",
"\n",
" def handler(self, event):\n",
" print(f\"{self.time}: MediumPrioritySimObj {self.name} running\")\n",
" self.send_event(1., self, ExampleMsg())\n",
"\n",
" event_handlers = [(ExampleMsg, 'handler')]\n",
"\n",
" # have `MediumPrioritySimObj`s execute at medium priority\n",
" class_priority = SimObjClassPriority.MEDIUM\n",
"\n",
"simulator = de_sim.Simulator()\n",
"simulator.add_object(LowPrioritySimObj('A'))\n",
"simulator.add_object(MediumPrioritySimObj('B'))\n",
"simulator.initialize()\n",
"print(simulator.simulate(2).num_events, 'events executed')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This example illustrates the scheduling of simultaneous event messages.\n",
"`SimObjClassPriority` is an `IntEnum` that provides simulation object class priorities, including `LOW`, `MEDIUM`, and `HIGH`.\n",
"We create two classes, `LowPrioritySimObj` and `MediumPrioritySimObj`, with `LOW` and `MEDIUM` priorities, respectively, and execute them simultaneously at simulation times 0, 1, 2, ...\n",
"At each time, the `MediumPrioritySimObj` object runs before the `LowPrioritySimObj` one.\n",
"\n",
"#### Execution order of objects without an assigned `class_priority`\n",
"The next example shows the ordering of simultaneous events executed by objects that don't have assigned priorities."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"9 priority: LOW\n",
"6 priority: LOW\n",
"2 priority: LOW\n",
"0.0: DefaultPrioritySimObj 2 running\n",
"0.0: DefaultPrioritySimObj 6 running\n",
"0.0: DefaultPrioritySimObj 9 running\n",
"1.0: DefaultPrioritySimObj 2 running\n",
"1.0: DefaultPrioritySimObj 6 running\n",
"1.0: DefaultPrioritySimObj 9 running\n",
"2.0: DefaultPrioritySimObj 2 running\n",
"2.0: DefaultPrioritySimObj 6 running\n",
"2.0: DefaultPrioritySimObj 9 running\n",
"9 events executed\n"
]
}
],
"source": [
"class DefaultPrioritySimObj(NoPrioritySimObj):\n",
"\n",
" def handler(self, event):\n",
" print(f\"{self.time}: DefaultPrioritySimObj {self.name} running\")\n",
" self.send_event(1., self, ExampleMsg())\n",
"\n",
" event_handlers = [(ExampleMsg, 'handler')]\n",
"\n",
"\n",
"simulator = de_sim.Simulator()\n",
"for name in random.sample(range(10), k=3):\n",
" sim_obj = DefaultPrioritySimObj(str(name))\n",
" print(f\"{sim_obj.name} priority: {sim_obj.class_event_priority.name}\")\n",
" simulator.add_object(sim_obj)\n",
"simulator.initialize()\n",
"print(simulator.simulate(2).num_events, 'events executed')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this example, the [`SimulationObject`s](https://docs.karrlab.org/de_sim/master/source/de_sim.html#de_sim.simulation_object.SimulationObject) have no priorities assigned, so their default priorities are `LOW`. (The `class_event_priority` attribute of a simulation object is a `SimObjClassPriority`)\n",
"\n",
"Three objects with names randomly selected from '0', '1', ..., '9', are created.\n",
"When they execute simultaneously, events are ordered by the sort order of the objects' names.\n",
"\n",
"#### Execution order of instances of simulation object classes with relative priorities\n",
"Often, a modeler wants to control the *relative* simultaneous priorities of simulation objects, but does not care about their absolute priorities.\n",
"The next example shows how to specify relative priorities."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"SecondNoPrioritySimObj: A; priority: SECOND\n",
"FirstNoPrioritySimObj: B; priority: HIGH\n",
"0.0: FirstNoPrioritySimObj B running\n",
"0.0: SecondNoPrioritySimObj A running\n",
"1.0: FirstNoPrioritySimObj B running\n",
"1.0: SecondNoPrioritySimObj A running\n",
"2.0: FirstNoPrioritySimObj B running\n",
"2.0: SecondNoPrioritySimObj A running\n",
"6 events executed\n"
]
}
],
"source": [
"class FirstNoPrioritySimObj(NoPrioritySimObj):\n",
"\n",
" def handler(self, event):\n",
" print(f\"{self.time}: FirstNoPrioritySimObj {self.name} running\")\n",
" self.send_event(1., self, ExampleMsg())\n",
"\n",
" event_handlers = [(ExampleMsg, 'handler')]\n",
"\n",
"\n",
"class SecondNoPrioritySimObj(NoPrioritySimObj):\n",
"\n",
" def handler(self, event):\n",
" print(f\"{self.time}: SecondNoPrioritySimObj {self.name} running\")\n",
" self.send_event(1., self, ExampleMsg())\n",
"\n",
" event_handlers = [(ExampleMsg, 'handler')]\n",
"\n",
"\n",
"# Assign decreasing priorities to classes in [FirstNoPrioritySimObj, SecondNoPrioritySimObj]\n",
"SimObjClassPriority.assign_decreasing_priority([FirstNoPrioritySimObj,\n",
" SecondNoPrioritySimObj])\n",
"\n",
"simulator = de_sim.Simulator()\n",
"simulator.add_object(SecondNoPrioritySimObj('A'))\n",
"simulator.add_object(FirstNoPrioritySimObj('B'))\n",
"for sim_obj in simulator.simulation_objects.values():\n",
" print(f\"{type(sim_obj).__name__}: {sim_obj.name}; \"\n",
" f\"priority: {sim_obj.class_event_priority.name}\")\n",
"simulator.initialize()\n",
"print(simulator.simulate(2).num_events, 'events executed')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `assign_decreasing_priority` method of `SimObjClassPriority` takes an iterator over `SimulationObject` subclasses, and assigns them decreasing simultaneous event priorities.\n",
"The `FirstNoPrioritySimObj` instance therefore executes before the `SecondNoPrioritySimObj` instance at each discrete simulation time."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.6"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": false,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": false
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 4
}