add simulation classes for online energy accounting inaccuracies

4 files changed, 418 insertions, 23 deletions

diff --git a/bin/generate-dfa-benchmark.py b/bin/generate-dfa-benchmark.py
index 8489d40..e869a9d 100755
--- a/bin/generate-dfa-benchmark.py
+++ b/bin/generate-dfa-benchmark.py
@@ -30,6 +30,12 @@ Options:
 
 --sleep=<ms> (default: 0)
     How long to sleep between function calls.
+
+--trace-filter=<transition,transition,transition,...>[ <transition,transition,transition,...> ...]
+    Only consider traces whose beginning matches one of the provided transition sequences.
+    E.g. --trace-filter='init,foo init,bar' will only consider traces with init as first and foo or bar as second transition,
+    and --trace-filter='init,foo,$ init,bar,$' will only consider the traces init -> foo and init -> bar.
+        
 """
 
 import getopt
@@ -255,11 +261,6 @@ if __name__ == '__main__':
             accounting_object = get_accountingmethod(opt['accounting'])(opt['dummy'], pta)
         else:
             accounting_object = None
-        drv = MultipassDriver(opt['dummy'], pta, repo.class_by_name[opt['dummy']], enum=enum, accounting=accounting_object)
-        with open('/home/derf/var/projects/multipass/src/driver/dummy.cc', 'w') as f:
-            f.write(drv.impl)
-        with open('/home/derf/var/projects/multipass/include/driver/dummy.h', 'w') as f:
-            f.write(drv.header)
 
     runs = list(pta.dfs(opt['depth'], with_arguments = True, with_parameters = True, trace_filter = opt['trace-filter']))
 
@@ -273,20 +274,4 @@ if __name__ == '__main__':
     if next(filter(lambda x: len(x.return_value_handlers), pta.transitions), None):
         need_return_values = True
 
-    harness = OnboardTimerHarness(gpio_pin = timer_pin, pta = pta, counter_limits = runner.get_counter_limits_us(opt['arch']), log_return_values = need_return_values)
-
-    if len(args) > 1:
-        results = run_benchmark(args[1], pta, runs, opt['arch'], opt['app'], opt['run'].split(), harness, opt['sleep'], opt['repeat'], runs_total = len(runs), dummy = 'dummy' in opt)
-        json_out = {
-            'opt' : opt,
-            'pta' : pta.to_json(),
-            'traces' : list(map(lambda x: x[1].traces, results)),
-            'raw_output' : list(map(lambda x: x[2], results)),
-        }
-        with open(time.strftime('ptalog-%Y%m%d-%H%M%S.json'), 'w') as f:
-            json.dump(json_out, f)
-    else:
-        outbuf = benchmark_from_runs(pta, runs, harness)
-        print(outbuf.getvalue())
-
     sys.exit(0)
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))
diff --git a/test/test_codegen.py b/test/test_codegen.py
new file mode 100755
index 0000000..2d54158
--- /dev/null
+++ b/test/test_codegen.py
@@ -0,0 +1,159 @@
+#!/usr/bin/env python3
+
+from automata import PTA
+from codegen import get_simulated_accountingmethod
+import unittest
+
+example_json_1 = {
+    'parameters' : ['datarate', 'txbytes', 'txpower'],
+    'initial_param_values' : [None, None, None],
+    'state' : {
+        'IDLE' : {
+            'power' : {
+                'static' : 5,
+            }
+        },
+        'TX' : {
+            'power' : {
+                'static' : 100,
+                'function' : {
+                    'raw' : 'regression_arg(0) + regression_arg(1)'
+                        ' * parameter(txpower)',
+                    'regression_args' : [ 100, 2 ]
+                },
+            }
+        },
+    },
+    'transitions' : [
+        {
+            'name' : 'init',
+            'origin' : ['UNINITIALIZED', 'IDLE'],
+            'destination' : 'IDLE',
+            'duration' : {
+                'static' : 50000,
+            },
+            'set_param' : {
+                'txpower' : 10
+            },
+        },
+        {
+            'name' : 'setTxPower',
+            'origin' : 'IDLE',
+            'destination' : 'IDLE',
+            'duration' : { 'static' : 120 },
+            'energy ' : { 'static' : 10000 },
+            'arg_to_param_map' : { 'txpower' : 0 },
+            'argument_values' : [ [10, 20, 30] ],
+        },
+        {
+            'name' : 'send',
+            'origin' : 'IDLE',
+            'destination' : 'TX',
+            'duration' : {
+                'static' : 10,
+                'function' : {
+                    'raw' : 'regression_arg(0) + regression_arg(1)'
+                        ' * function_arg(1)',
+                    'regression_args' : [48, 8],
+                },
+            },
+            'energy' : {
+                'static' : 3,
+                'function' : {
+                    'raw' : 'regression_arg(0) + regression_arg(1)'
+                        ' * function_arg(1)',
+                    'regression_args' : [3, 5],
+                },
+            },
+            'arg_to_param_map' : { 'txbytes' : 1 },
+            'argument_values' : [ ['"foo"', '"hodor"'], [3, 5] ],
+            'argument_combination' : 'zip',
+        },
+        {
+            'name' : 'txComplete',
+            'origin' : 'TX',
+            'destination' : 'IDLE',
+            'is_interrupt' : 1,
+            'timeout' : {
+                'static' : 2000,
+                'function' : {
+                    'raw' : 'regression_arg(0) + regression_arg(1)'
+                        ' * parameter(txbytes)',
+                    'regression_args' : [ 500, 16 ],
+                },
+            },
+        }
+    ],
+}
+
+class TestCG(unittest.TestCase):
+    def test_statetransition_immediate(self):
+        pta = PTA.from_json(example_json_1)
+        pta.set_random_energy_model()
+        pta.state['IDLE'].power = 9
+        cg = get_simulated_accountingmethod('static_statetransition_immediate')(pta, 1000000, 'uint8_t', 'uint8_t', 'uint8_t', 'uint8_t')
+        cg.current_state = pta.state['IDLE']
+        cg.sleep(7)
+        self.assertEqual(cg.get_energy(), 9 * 7)
+        pta.transitions[1].energy = 123
+        cg.pass_transition(pta.transitions[1])
+        self.assertEqual(cg.get_energy(), 9 * 7 + 123)
+        cg.pass_transition(pta.transitions[1])
+        self.assertEqual(cg.get_energy(), (9 * 7 + 123 + 123) % 256)
+
+        cg = get_simulated_accountingmethod('static_statetransition_immediate')(pta, 100000, 'uint8_t', 'uint8_t', 'uint8_t', 'uint8_t')
+        cg.current_state = pta.state['IDLE']
+        cg.sleep(7)
+        self.assertEqual(cg.get_energy(), 0)
+        cg.sleep(15)
+        self.assertEqual(cg.get_energy(), 90)
+        cg.sleep(90)
+        self.assertEqual(cg.get_energy(), 900 % 256)
+
+    def test_statetransition(self):
+        pta = PTA.from_json(example_json_1)
+        pta.set_random_energy_model()
+        pta.state['IDLE'].power = 9
+        cg = get_simulated_accountingmethod('static_statetransition')(pta, 1000000, 'uint8_t', 'uint8_t', 'uint8_t', 'uint8_t')
+        cg.current_state = pta.state['IDLE']
+        cg.sleep(7)
+        self.assertEqual(cg.get_energy(), 9 * 7)
+        pta.transitions[1].energy = 123
+        cg.pass_transition(pta.transitions[1])
+        self.assertEqual(cg.get_energy(), 9 * 7 + 123)
+        cg.pass_transition(pta.transitions[1])
+        self.assertEqual(cg.get_energy(), (9 * 7 + 123 + 123) % 256)
+
+    def test_state_immediate(self):
+        pta = PTA.from_json(example_json_1)
+        pta.set_random_energy_model()
+        pta.state['IDLE'].power = 9
+        cg = get_simulated_accountingmethod('static_state_immediate')(pta, 1000000, 'uint8_t', 'uint8_t', 'uint8_t', 'uint8_t')
+        cg.current_state = pta.state['IDLE']
+        cg.sleep(7)
+        self.assertEqual(cg.get_energy(), 9 * 7)
+        pta.transitions[1].energy = 123
+        cg.pass_transition(pta.transitions[1])
+        self.assertEqual(cg.get_energy(), 9 * 7)
+        cg.pass_transition(pta.transitions[1])
+        self.assertEqual(cg.get_energy(), 9 * 7)
+
+    def test_state(self):
+        pta = PTA.from_json(example_json_1)
+        pta.set_random_energy_model()
+        pta.state['IDLE'].power = 9
+        cg = get_simulated_accountingmethod('static_state')(pta, 1000000, 'uint8_t', 'uint8_t', 'uint8_t', 'uint8_t')
+        cg.current_state = pta.state['IDLE']
+        cg.sleep(7)
+        self.assertEqual(cg.get_energy(), 9 * 7)
+        pta.transitions[1].energy = 123
+        cg.pass_transition(pta.transitions[1])
+        self.assertEqual(cg.get_energy(), 9 * 7)
+        cg.pass_transition(pta.transitions[1])
+        self.assertEqual(cg.get_energy(), 9 * 7)
+
+        cg = get_simulated_accountingmethod('static_state')(pta, 1000000, 'uint8_t', 'uint16_t', 'uint16_t', 'uint16_t')
+
+
+if __name__ == '__main__':
+    unittest.main()