add simulation classes for online energy accounting inaccuracies

2 files changed, 253 insertions, 2 deletions

diff --git a/lib/codegen.py b/lib/codegen.py
index 30e79bb..1f4bd6f 100644
--- a/lib/codegen.py
+++ b/lib/codegen.py
@@ -1,6 +1,8 @@
 """Code generators for multipass dummy drivers for online model evaluation."""
 
-from automata import PTA
+from automata import PTA, Transition
+from modular_arithmetic import simulate_int_type
+import numpy as np
 
 header_template = """
 #ifndef DFATOOL_{name}_H
@@ -73,7 +75,131 @@ def get_accountingmethod(method):
         return StaticAccountingImmediateCalculation
     if method == 'static_statetransition':
         return StaticAccounting
-    raise ValueError('Unknown accounting method')
+    raise ValueError('Unknown accounting method: {}'.format(method))
+
+def get_simulated_accountingmethod(method):
+    """Return SimulatedAccountingMethod class for method."""
+    if method == 'static_state_immediate':
+        return SimulatedStaticStateOnlyAccountingImmediateCalculation
+    if method == 'static_statetransition_immediate':
+        return SimulatedStaticAccountingImmediateCalculation
+    if method == 'static_state':
+        return SimulatedStaticStateOnlyAccounting
+    if method == 'static_statetransition':
+        return SimulatedStaticAccounting
+    raise ValueError('Unknown accounting method: {}'.format(method))
+
+class SimulatedAccountingMethod:
+    """
+    Simulates overflows and timing inaccuracies in online energy accounting on embedded devices.
+
+    Inaccuracies are based on:
+    * timer resolution (e.g. a 10kHz timer cannot reliably measure sub-100us timings)
+    * timer counter size (e.g. a 16-bit timer at 1MHz will overflow after 65us)
+    * variable size for accounting of durations, power and energy values
+    """
+    def __init__(self, pta: PTA, timer_freq_hz, timer_type, ts_type, power_type, energy_type):
+        """
+        Simulate Online Accounting for a given PTA.
+        
+        :param pta: PTA object
+        :param timer_freq_hz: Frequency of timer used for state time measurement, in Hz
+        :param timer_type: Size of timer counter register, as C standard type (uint8_t / uint16_t / uint32_t / uint64_t)
+        :param ts_type: Size of timestamp variables, as C standard type
+        :param power_type: Size of power variables, as C standard type
+        :param energy_type: Size of energy variables, as C standard type
+        """
+        self.pta = pta
+        self.timer_freq_hz = timer_freq_hz
+        self.timer_class = simulate_int_type(timer_type)
+        self.ts_class = simulate_int_type(ts_type)
+        self.power_class = simulate_int_type(power_type)
+        self.energy_class = simulate_int_type(energy_type)
+        self.current_state = pta.state['UNINITIALIZED']
+
+        self.energy = self.energy_class(0)
+
+    def _sleep_duration(self, duration_us):
+        """
+        Return the sleep duration a timer with the classes timer frequency would measure.
+
+        I.e., for a 35us sleep with a 50kHz timer (-> one tick per 20us), the OS would likely measure one tick == 20us.
+        This is based on the assumption that the timer is reset at each transition.
+        """
+        us_per_tick = 1000000 / self.timer_freq_hz
+        ticks = self.timer_class(int(duration_us // us_per_tick))
+        return int(ticks.val * us_per_tick)
+
+    def sleep(self, duration_us):
+        pass
+
+    def pass_transition(self, transition: Transition):
+        self.current_state = transition.destination
+
+    def get_energy(self):
+        return self.energy.val
+
+class SimulatedStaticStateOnlyAccountingImmediateCalculation(SimulatedAccountingMethod):
+    def __init__(self, pta: PTA, timer_freq_hz, timer_type, ts_type, power_type, energy_type):
+        super().__init__(pta, timer_freq_hz, timer_type, ts_type, power_type, energy_type)
+
+    def sleep(self, duration_us):
+        self.energy += self.ts_class(self._sleep_duration(duration_us)) * self.power_class(int(self.current_state.power))
+
+class SimulatedStaticAccountingImmediateCalculation(SimulatedAccountingMethod):
+    def __init__(self, pta: PTA, timer_freq_hz, timer_type, ts_type, power_type, energy_type):
+        super().__init__(pta, timer_freq_hz, timer_type, ts_type, power_type, energy_type)
+
+    def sleep(self, duration_us):
+        self.energy += self.ts_class(self._sleep_duration(duration_us)) * self.power_class(int(self.current_state.power))
+
+    def pass_transition(self, transition: Transition):
+        self.energy += int(transition.energy)
+        super().pass_transition(transition)
+
+class SimulatedStaticAccounting(SimulatedAccountingMethod):
+    def __init__(self, pta: PTA, timer_freq_hz, timer_type, ts_type, power_type, energy_type):
+        super().__init__(pta, timer_freq_hz, timer_type, ts_type, power_type, energy_type)
+        self.time_in_state = dict()
+        for state_name in pta.state.keys():
+            self.time_in_state[state_name] = self.ts_class(0)
+        self.transition_count = list()
+        for transition in pta.transitions:
+            self.transition_count.append(simulate_int_type('uint16_t')(0))
+
+    def sleep(self, duration_us):
+        self.time_in_state[self.current_state.name] += self._sleep_duration(duration_us)
+
+    def pass_transition(self, transition: Transition):
+        self.transition_count[self.pta.transitions.index(transition)] += 1
+        super().pass_transition(transition)
+
+    def get_energy(self):
+        pta = self.pta
+        energy = self.energy_class(0)
+        for state in pta.state.values():
+            energy += self.time_in_state[state.name] * int(state.power)
+        for i, transition in enumerate(pta.transitions):
+            energy += self.transition_count[i] * int(transition.energy)
+        return energy.val
+
+
+class SimulatedStaticStateOnlyAccounting(SimulatedAccountingMethod):
+    def __init__(self, pta: PTA, timer_freq_hz, timer_type, ts_type, power_type, energy_type):
+        super().__init__(pta, timer_freq_hz, timer_type, ts_type, power_type, energy_type)
+        self.time_in_state = dict()
+        for state_name in pta.state.keys():
+            self.time_in_state[state_name] = self.ts_class(0)
+
+    def sleep(self, duration_us):
+        self.time_in_state[self.current_state.name] += self._sleep_duration(duration_us)
+
+    def get_energy(self):
+        pta = self.pta
+        energy = self.energy_class(0)
+        for state in pta.state.values():
+            energy += self.time_in_state[state.name] * int(state.power)
+        return energy.val
 
 class AccountingMethod:
     def __init__(self, class_name: str, pta: PTA):
diff --git a/lib/modular_arithmetic.py b/lib/modular_arithmetic.py
new file mode 100644
index 0000000..03cb7f8
--- /dev/null
+++ b/lib/modular_arithmetic.py
@@ -0,0 +1,125 @@
+# Based on https://rosettacode.org/wiki/Modular_arithmetic#Python
+# Licensed under GFDL 1.2 https://www.gnu.org/licenses/old-licenses/fdl-1.2.html
+import operator
+import functools
+ 
+@functools.total_ordering
+class Mod:
+    __slots__ = ['val','mod']
+ 
+    def __init__(self, val, mod):
+        if not isinstance(val, int):
+            raise ValueError('Value must be integer')
+        if not isinstance(mod, int) or mod<=0:
+            raise ValueError('Modulo must be positive integer')
+        self.val = val % mod
+        self.mod = mod
+ 
+    def __repr__(self):
+        return 'Mod({}, {})'.format(self.val, self.mod)
+ 
+    def __int__(self):
+        return self.val
+ 
+    def __eq__(self, other):
+        if isinstance(other, Mod):
+            self.val == other.val
+        elif isinstance(other, int):
+            return self.val == other
+        else:
+            return NotImplemented
+ 
+    def __lt__(self, other):
+        if isinstance(other, Mod):
+            return self.val < other.val
+        elif isinstance(other, int):
+            return self.val < other
+        else:
+            return NotImplemented
+ 
+    def _check_operand(self, other):
+        if not isinstance(other, (int, Mod)):
+            raise TypeError('Only integer and Mod operands are supported')
+ 
+    def __pow__(self, other):
+        self._check_operand(other)
+        # We use the built-in modular exponentiation function, this way we can avoid working with huge numbers.
+        return __class__(pow(self.val, int(other), self.mod), self.mod)
+ 
+    def __neg__(self):
+        return Mod(self.mod - self.val, self.mod)
+ 
+    def __pos__(self):
+        return self # The unary plus operator does nothing.
+ 
+    def __abs__(self):
+        return self # The value is always kept non-negative, so the abs function should do nothing.
+ 
+# Helper functions to build common operands based on a template.
+# They need to be implemented as functions for the closures to work properly.
+def _make_op(opname):
+    op_fun = getattr(operator, opname)  # Fetch the operator by name from the operator module
+    def op(self, other):
+        self._check_operand(other)
+        return Mod(op_fun(self.val, int(other)) % self.mod, self.mod)
+    return op
+ 
+def _make_reflected_op(opname):
+    op_fun = getattr(operator, opname)
+    def op(self, other):
+        self._check_operand(other)
+        return Mod(op_fun(int(other), self.val) % self.mod, self.mod)
+    return op
+ 
+# Build the actual operator overload methods based on the template.
+for opname, reflected_opname in [('__add__', '__radd__'), ('__sub__', '__rsub__'), ('__mul__', '__rmul__')]:
+    setattr(Mod, opname, _make_op(opname))
+    setattr(Mod, reflected_opname, _make_reflected_op(opname))
+
+class Uint8(Mod):
+    __slots__ = []
+
+    def __init__(self, val):
+        super().__init__(val, 256)
+
+    def __repr__(self):
+        return 'Uint8({})'.format(self.val)
+
+class Uint16(Mod):
+    __slots__ = []
+
+    def __init__(self, val):
+        super().__init__(val, 65536)
+
+    def __repr__(self):
+        return 'Uint16({})'.format(self.val)
+
+class Uint32(Mod):
+    __slots__ = []
+
+    def __init__(self, val):
+        super().__init__(val, 4294967296)
+
+    def __repr__(self):
+        return 'Uint32({})'.format(self.val)
+
+class Uint64(Mod):
+    __slots__ = []
+
+    def __init__(self, val):
+        super().__init__(val, 18446744073709551616)
+
+    def __repr__(self):
+        return 'Uint64({})'.format(self.val)
+
+
+def simulate_int_type(int_type: str):
+    if int_type == 'uint8_t':
+        return Uint8
+    if int_type == 'uint16_t':
+        return Uint16
+    if int_type == 'uint32_t':
+        return Uint32
+    if int_type == 'uint64_t':
+        return Uint64
+    raise ValueError('unsupported integer type: {}'.format(int_type))