top/green.tex

   1 \documentclass[../thesis.tex]{subfiles}
   2
   3 \input{subfilepreamble}
   4
   5 \begin{document}
   6 \input{subfileprefix}
   7
   8 \chapter{Green computing with \texorpdfstring{\gls{MTASK}}{mTask}}%
   9 \label{chp:green_computing_mtask}
  10 \begin{chapterabstract}
  11         This chapter demonstrate the energy saving features of \gls{MTASK}.
  12         First it gives an overview of general green computing measures for edge devices.
  13         Then \gls{MTASK}'s task scheduling is explained and it is shown how to customise it so suit the applications and energy needs.
  14         Finally it shows how to use interrupts in \gls{MTASK} to reduce the need for polling.
  15 \end{chapterabstract}
  16
  17 The edge layer of the \gls{IOT} contains small devices that sense and interact with the world and it is crucial to lower their energy consumption.
  18 While individual devices consume little energy, the sheer number of devices in total amounts to a lot.
  19 Furthermore, many \gls{IOT} devices operate on batteries and higher energy consumption increases the amount of e-waste as \gls{IOT} edge devices are often hard to reach and consequently hard to replace \citep{NIZETIC2020122877}.
  20
  21 To reduce the power consumption of an \gls{IOT} device, the specialized low-power sleep modes of the microprocessors can be leveraged.
  22 Different sleep modes achieve different power reductions because of their different run time characteristics.
  23 These specifics range from disabling or suspending WiFi; stopping powering (parts) of the \gls{RAM}; disabling peripherals; or even turning off the processor completely, requiring an external signal to wake up again.
  24 Determining when exactly and for how long it is possible to sleep is expensive in the general case and often requires annotations in the source code, a real-time operating system or a handcrafted scheduler.
  25
  26 \begin{table}
  27         \centering
  28         \small
  29         \begin{tabular}{ccccccccc}
  30                 \toprule
  31                 & \multicolumn{4}{c}{Wemos D1 mini} & \multicolumn{4}{c}{Adafruit Feather M0 Wifi} \\
  32                 \midrule
  33                                 & active & modem & light & deep & active & modem & light & deep \\
  34                                 & & sleep & sleep & sleep & & sleep & sleep & sleep \\
  35                 \midrule
  36                 WiFi      & on & off & off & off  & on & off & off & off \\
  37                 CPU       & on & on & pending & off & on & on & idle & idle \\
  38                 \gls{RAM} & on & on & on & off & on & on & on & on\\%low power \\
  39                 \midrule
  40                 current   & 100--240 & 15 & 0.5 & 0.002 & 90--300 & 5 & 2 &  0.005\\
  41                 \bottomrule
  42         \end{tabular}
  43         \caption{Current use in \unit{\milli\ampere} of two microprocessor boards in various sleep modes.}%
  44         \label{tbl:top_sleep}
  45 \end{table}
  46
  47 \Cref{tbl:top_sleep} shows the properties and current consumption of two commonly used microcontrollers.
  48 It shows that switching the WiFi radio off yields the biggest energy savings.
  49 In most \gls{IOT} applications, we need WiFi for communications.
  50 It is fine to switch it off, but after switching it on, the WiFi protocol needs to transmit a number of messages to re-establish the connection.
  51 This implies that it is only worthwhile to switch the radio off when this can be done for some time.
  52 The details vary per system and situation.
  53 As a rule of thumb, it is only worthwhile to switch the WiFi off when it is not needed for at least some tens of seconds.
  54
  55 \section{Green \texorpdfstring{\glsxtrshort{IOT}}{IoT} computing}
  56 The data in \cref{tbl:top_sleep} shows that it is worthwhile to put the system in some sleep mode when there is temporarily no work to be done.
  57 A deeper sleep mode saves more energy, but also requires more work to restore the software to its working state.
  58 A processor like the ESP8266 driving the Wemos D1 mini loses the content of its \gls{RAM} in deep sleep mode.
  59 As a result, after waking up, the program itself is preserved, since it is stored in flash memory, but the program state is lost.
  60 When there is a program state to be preserved, we must either store it elsewhere, limit us to light sleep, or use a microcontroller that keeps the \gls{RAM} intact during deep sleep.
  61
  62 For \gls{IOT} nodes executing a single task, explicit sleeping to save energy can be achieved without too much hassle.
  63 This becomes much more challenging as soon as multiple independent tasks run on the same node.
  64 Sleeping of the entire node induced by one task prevents progress of all tasks.
  65 This is especially annoying when the other tasks are executing time critical parts, like communication protocols.
  66 Such protocols control the communication with sensors and actuators.
  67 Without the help of an \gls{OS}, the programmer is forced to combine all subtasks into one big system that decides if it is safe to sleep for all subtasks.
  68
  69 \Gls{MTASK} offers abstractions for edge layer-specific details such as the heterogeneity of architectures, platforms and frameworks; peripheral access; and multitasking but also for energy consumption and scheduling.
  70 In \gls{MTASK}, tasks are implemented as a rewrite system, where the work is automatically segmented in small atomic bits and stored as a task tree.
  71 Each cycle, a single rewrite step is performed on all task trees, during rewriting, tasks do a bit of their work and progress steadily, allowing interleaved and seemingly parallel operation.
  72 After a loop, the \gls{RTS} knows which task is waiting on which triggers and is thus able to determine the next execution time for each task automatically.
  73 Utilising this information, the \gls{RTS} can determine when it is possible and safe to sleep and choose the optimal sleep mode according to the sleeping time.
  74 For example, the \gls{RTS} never attempts to sleep during an \gls{I2C} communication because \gls{IO} is always contained \emph{within} a rewrite step.
  75
  76 An \gls{MTASK} program is dynamically transformed to byte code.
  77 This byte code and the initial \gls{MTASK} expression are shipped to \gls{MTASK} \gls{IOT} node.
  78 For the example in \cref{lst:blink} there is byte code representing the \cleaninline{blink} function and \cleaninline{main} determines the initial expression.
  79
  80 The \gls{MTASK} rewrite engine rewrites the current expression just a single rewrite step at a time.
  81 When subtasks are composed in parallel, all subtasks are rewritten unless the result of the first rewrite step makes the result of the other tasks superfluous.
  82 The task design ensures such that all time critical communication with peripherals is within a single rewrite step.
  83 This is very convenient, since the system can inspect the current state of all \gls{MTASK} expressions after a rewrite and decide if sleeping and how long is possible.
  84 %As a consequence, we cannot have fair multitasking.
  85 %When a single rewrite step would take forever due to an infinite sequence of function calls, this would block the entire IoT node.
  86 Even infinite sequences rewrite steps, as in the \cleaninline{blink} example, are perfectly fine.
  87 The \gls{MTASK} system does proper tail-call optimizations to facilitate this.
  88
  89 \section{Task scheduling}
  90 Some \gls{MTASK} examples contain one or more explicit \cleaninline{delay} primitives, offering a natural place for the node executing it to pause.
  91 However, there are many \gls{MTASK} programs that just specify a repeated set of primitives.
  92 A typical example is the program that reads the temperature for a sensor and sets the system \gls{LED} if the reading is below some given \cleaninline{goal}.
  93
  94 \begin{lstClean}[caption={A basic thermostat task.},label={lst:thermostat}]
  95 thermostat :: Main (MTask v Bool) | mtask v
  96 thermostat = DHT I2Caddr \dht->
  97              {main = rpeat (
  98                  temperature dht >>~. \temp.
  99                  writeD builtInLED (goal <. temp)
 100              )}
 101 \end{lstClean}
 102
 103 This program repeatedly reads the \gls{DHT} sensor and sets the on-board \gls{LED} based on the comparison with the \cleaninline{goal} as fast as possible on the \gls{MTASK} node.
 104 This is a perfect solution as long as we ignore the power consumption.
 105 The \gls{MTASK} machinery ensures that if there are other tasks running on the node, they will make progress.
 106 However, this solution is far from perfect when we take power consumption into account.
 107 In most applications, it is very unlikely that the temperature will change significantly within one minute, let alone within some milliseconds.
 108 Hence, it is sufficient to repeat the measurement with an appropriate interval.
 109
 110 There are various ways to improve this program.
 111 The simplest solution is to add an explicit delay to the body of the repeat loop.
 112 A slightly more sophisticated option is to add a repetition period to the \cleaninline{rpeat} combinator.
 113 The combinator implementing this is called \cleaninline{rpeatEvery}.
 114 Both solutions rely on an explicit action of the programmer.
 115
 116 Fortunately, \gls{MTASK} also contains machinery to do this automatically.
 117 The key of this solution is to associate dynamically an evaluation interval with each task.
 118 The interval $\left\langle low, high \right\rangle$ indicates that the evaluation can be safely delayed by any number of milliseconds in that range.
 119 Such an interval is just a hint for the \gls{RTS}.
 120 It is not a guarantee that the evaluation takes place in the given interval.
 121 Other parts of the task expression can force an earlier evaluation of this part of the task.
 122 When the system is very busy with other work, the task might even be executed after the upper bound of the interval.
 123 The system calculates the refresh rates from the current task expression.
 124 This has the advantage that the programmer does not have to deal with them and that they are available in each and every \gls{MTASK} program.
 125
 126 \subsection{Basic Refresh Rates}
 127
 128 We start by assigning default refresh rates to basic tasks.
 129 These refresh rates reflect the expected change rates of sensors and other inputs.
 130 Writing to basic \gls{GPIO} pins and actuators has refresh rate $\langle 0, 0 \rangle$, this is never delayed.
 131
 132 \begin{table}
 133         \centering
 134         \begin{tabular}{ll}
 135                 \toprule
 136                 task & default interval \\
 137                 \midrule
 138                 reading \pgls{SDS} & $\langle 0, 2000 \rangle$ \\
 139                 slow sensor, like temperature & $\langle 0, 2000 \rangle$ \\
 140                 gesture sensor & $\langle 0, 1000 \rangle$ \\
 141                 fast sensor, like sound or light & $\langle 0, 100 \rangle$ \\
 142                 reading GPIO pins & $\langle 0, 100 \rangle$ \\
 143                 \bottomrule
 144         \end{tabular}
 145         \caption{Default refresh rates of basic tasks.}%
 146         \label{tbl:refresh}
 147 \end{table}
 148
 149 \subsection{Deriving Refresh Rates}
 150 Based on these refresh rates, the system can automatically derive refresh rates for composed \gls{MTASK} expressions using $\mathcal{R}$.
 151 We use the operator $\cap_{\textit{safe}}$ to compose refresh ranges.
 152 When the ranges overlap the result is the overlapping range.
 153 Otherwise, the result is the range with the lowest numbers.
 154 The rationale is that subtasks should not be delayed longer than their refresh range.
 155 Evaluating a task earlier should not change its result but can consume more energy.
 156
 157 \begin{align}
 158         \cap_{\textit{safe}} :: \langle \mathit{Int}, \mathit{Int} \rangle \; \langle \mathit{Int}, \mathit{Int} \rangle & \shortrightarrow \langle \mathit{Int}, \mathit{Int} \rangle & \notag \\
 159         R_1 \cap_{\textit{safe}} R_2 & = R_1 \cap R_2 & \text{if } R_1 \cap R_2 \neq \emptyset \\
 160         \langle l_1, h_1 \rangle \cap_{\textit{safe}} \langle l_2, h_2 \rangle & = \langle l_2, h_2 \rangle & \text{if } h_2 < l_1 \\
 161         R_1 \cap_{\textit{safe}} R_2 & = R_1  & \text{otherwise}
 162 \end{align}
 163
 164 \begin{align}
 165         \mathcal{R} :: (\mathit{MTask}~v~a)    & \shortrightarrow \langle \mathit{Int}, \mathit{Int} \rangle \notag \\
 166         \mathcal{R} (t_1~{.||.}~t_2)  & = \mathcal{R}(t_1) \cap_{\textit{safe}} \mathcal{R}(t_2) \label{R:or} \\
 167         \mathcal{R}(t_1~{.\&\&.}~t_2) & = \mathcal{R}(t_1) \cap_{\textit{safe}} \mathcal{R}(t_2) \label{R:and}\\
 168         \mathcal{R}(t_1~{>\!\!>\!|.}~t_2)   & = \mathcal{R}(t_1) \label{R:seq} \\
 169         \mathcal{R}(t~{>\!\!>\!=.}~f)       & = \mathcal{R}(t) \label{R:bind} \\
 170         \mathcal{R}(t~{>\!\!>\!\!*.}~[a_1 \ldots a_n]) & = \mathcal{R}(t) \label{R:step} \\
 171         \mathcal{R}(\mathit{rpeat}~t)             & = \langle 0, 0 \rangle \label{R:rpeat} \\
 172         \mathcal{R}(\mathit{rpeatEvery}~d~t)   & = \langle 0, 0 \rangle \label{R:rpeatevery} \\
 173         \mathcal{R}(delay~d) & = \langle d, d \rangle \label{R:delay} \\
 174         \mathcal{R}(t) & =
 175                 \left\{%
 176                         \begin{array}{ll}
 177                                 \langle \infty, \infty \rangle~& \text{if}~t~\text{is Stable} \\
 178                                 \langle r_l, r_u \rangle & \text{otherwise}
 179                         \end{array}
 180                 \right.\label{R:other}
 181 \end{align}
 182
 183 We will briefly discuss the various cases of deriving refresh rates together with the task semantics of the different combinators
 184
 185 \subsubsection{Parallel Combinators} For the parallel composition of tasks we compute the intersection of the refresh intervals of the components as outlined in the definition of $\cap_{\textit{safe}}$.
 186 The operator \cleaninline{.\|\|.} in \cref{R:or} is the \emph{or}-combinator; the first subtask that produces a stable value determines the result of the composition.
 187 The operator \cleaninline{.&&.} in \cref{R:and} is the \emph{and}-operator. The result is the tuple containing both results when both subtasks have a stable value.
 188 The refresh rates of the parallel combinators have no direct relation with their task result.
 189
 190 \subsubsection{Sequential Combinators}
 191 For the sequential composition of tasks we only have to look at the refresh rate of the current task on the left.
 192 The sequential composition operator \cleaninline{>>\|.} in \cref{R:seq} is similar to the monadic sequence operator \cleaninline{>>\|}.
 193 The operator \cleaninline{>>=.} in \cref{R:bind} provides the stable task result to the function on the right-hand side, similar to the monadic bind.
 194 The operator \cleaninline{>>~.} steps on an unstable value and is otherwise equal to \cleaninline{>>=.}.
 195 The step combinator \cleaninline{>>*.} in \cref{R:step} has a list of conditional actions that specify a new task.
 196
 197 \subsubsection{Repeat Combinators}
 198 The repeat combinators repeats their argument indefinitely.
 199 The combinator \cleaninline{rpeatEvery} guarantees the given delay between repetitions.
 200 The refresh rate is equal to the refresh rate of the current argument task.
 201 Only when \cleaninline{rpeatEvery} waits between the iterations of the argument the refresh interval is equal to the remaining delay time.
 202
 203 \subsubsection{Other Combinators}
 204 The refresh rate of the \cleaninline{delay} in \cref{R:delay} is equal to the remaining delay.
 205 Refreshing stable tasks can be delayed indefinitely, their value never changes.
 206 For other basic tasks, the values from \cref{tbl:refresh} apply.
 207 The values $r_l$ and $r_u$ in \cref{R:other} are the lower and upper bound of the rate.
 208
 209 The refresh intervals associated with various steps of the thermostat program from \cref{lst:thermostat} are given in \cref{tbl:intervals}.
 210 Those rewrite steps and intervals are circular, after step 2 we continue with step 0 again.
 211 Only the actual reading of the sensor with \cleaninline{temperature dht} offers the possibility for a non-zero delay.
 212
 213 %%\begin{table}[tb]
 214 \begin{table}
 215         \centering
 216         \begin{tabular}{cp{20em}c}
 217                 \toprule
 218                 Step & Expression & Interval \\
 219                 \midrule
 220                 0  &
 221                 \begin{lstClean}[aboveskip=-2ex,belowskip=-2ex,frame=]
 222 rpeat ( temperature dht >>~. \temp.
 223         writeD builtInLED (goal <. temp)
 224 )\end{lstClean}
 225                    &
 226                    $\langle 0, 0 \rangle$ \\
 227                    %\hline
 228                 1  &
 229                 \begin{lstClean}[aboveskip=-2ex,belowskip=-2ex,frame=]
 230 temperature dht >>~. \temp.
 231 writeD builtInLED (goal <. temp) >>|.
 232 rpeat ( temperature dht >>~. \temp.
 233         writeD builtInLED (goal <. temp)
 234 )\end{lstClean}
 235                    & $\langle 0, 2000 \rangle$ \\
 236                    %\hline
 237                 2  &
 238                 \begin{lstClean}[aboveskip=-2ex,belowskip=-2ex,frame=]
 239 writeD builtInLED false >>|.
 240 rpeat ( temperature dht >>~. \temp.
 241         writeD builtInLED (goal <. temp)
 242 )\end{lstClean}
 243                 & $\langle 0, 0 \rangle$ \\
 244                 \bottomrule
 245         \end{tabular}
 246         \caption{Rewrite steps of the thermostat from \cref{lst:thermostat} and associated intervals.}%
 247         \label{tbl:intervals}
 248 \end{table}
 249
 250 \subsection{User Defined Refresh Rates}
 251 In some applications, it is necessary to read sensors at a different rate than the default rate given in \cref{tbl:refresh}, i.e.\ to customise the refresh rate.
 252 This is achieved by calling the access functions with a custom refresh rate as an additional argument (suffixed with the backtick (\cleaninline{`}))
 253
 254 \begin{lstClean}[caption={Auxiliary definitions to \cref{lst:gpio} for \gls{DHT} sensors and digital \gls{GPIO} with custom timing intervals.},label={lst:dht}]
 255 class dht v where
 256         ...
 257         temperature` :: (TimingInterval v) (v DHT) -> MTask v Real
 258         temperature  ::                    (v DHT) -> MTask v Real
 259         humidity`    :: (TimingInterval v) (v DHT) -> MTask v Real
 260         humidity     ::                    (v DHT) -> MTask v Real
 261
 262 class dio p v | pin p where
 263         ...
 264         readD` :: (TimingInterval v) (v p) -> MTask v Bool | pin p
 265         readD  ::                    (v p) -> MTask v Bool | pin p
 266 \end{lstClean}
 267
 268 A tailor-made \gls{ADT} determines the timing intervals.
 269
 270 % doordat texcl aanstaat in listings zijn comments automatisch al in LaTeX
 271 \begin{lstlisting}[language=Clean,caption={The \gls{ADT} for timing intervals in \gls{MTASK}.},label={lst:interval}]
 272 :: TimingInterval v = Default
 273                     | BeforeMs (v Int)            // yields $\langle 0, x \rangle $
 274                     | BeforeS  (v Int)            // yields $\langle 0, x \times 1000 \rangle $
 275                     | ExactMs  (v Int)            // yields $\langle x, x \rangle $
 276                     | ExactS   (v Int)            // yields $\langle 0, x \times 1000 \rangle $
 277                     | RangeMs  (v Int) (v Int)    // yields $\langle x, y \rangle $
 278                     | RangeS   (v Int) (v Int)    // yields $\langle x \times 1000, y \times 1000 \rangle $
 279 \end{lstlisting}
 280
 281 As example, we define an \gls{MTASK} that updates the \gls{SDS} \cleaninline{tempSds} in \gls{ITASK} in a tight loop.
 282 The \cleaninline{temperature`} reading requires that this happens at least once per minute.
 283 Without other tasks on the \gls{IOT} node, the temperature \gls{SDS} is updated once per minute.
 284 Other tasks can cause a slightly more frequent update.
 285
 286 \begin{lstClean}[caption={Updating \pgls{SDS} in \gls{ITASK} at most once per minute.},label={lst:updatesds2}]
 287 delayTime = BeforeS (lit 60) // 1 minute in seconds
 288
 289 devTask :: Main (MTask v Real) | mtask, dht, liftsds v
 290 devTask = DHT (DHT_DHT pin DHT11) \dht =
 291           liftsds \localSds = tempSds
 292           In {main = rpeat (temperature` delayTime dht >>~. setSds localSds)}
 293 \end{lstClean}
 294
 295 \subsection{Language}
 296 \subsection{Device}
 297
 298 \section{Interrupts}
 299
 300 \input{subfilepostamble}
 301 \end{document}