# Minimizing Energy and Computation in Long-Running Software
## 2 A Single Loop Program with Checkpoints  
Consider a program P that executes \(y_{n}\) instructions between its \((n-1)\)-th and \(n\)-th checkpoint, without counting all possible failures and failure recoveries. Now consider the instant \(t_{n}>0\) when the program creates its \(n\)-th checkpoint, and let \(Y_{n}\) denote the total number of instructions that the program has executed by time \(t_{n}\) since it started, where \(Y_{n}\) does not include all the repeated instructions that were executed due to checkpoints and failure recovery, and obviously: \(Y_{n}=\sum_{i=1}^{n}\ y_{i}\).  
Let \(B^{c}(Y_{n})\) be the computation time needed to create the \(n\)-th checkpoint. This quantity will generally depend on the total memory space occupied by the program, but in certain cases it may depend on \(Y_{n}\), since the program may generate new data as it is executing. Hence we will write \(B^{c}(Y_{n})=B^{c}_{0}+B^{c}_{1}Y_{n}\) where \(B^{c}_{0}>0\) and \(B^{c}_{1}\geq 0\) are constants for the given program.  
On the other hand, suppose a failure occurs after the program has successfully executed \(y\) instructions after the \(n\)-th checkpoint, i.e., after the program has executed \(Y_{n}+y\) instructions. If \(b^{c}(Y_{n},y)\) is the computation time needed to restart the program from the most recent checkpoint, when the program has successfully executed \(y\leq Y_{n+1}-Y_{n}\) instructions after the most recent checkpoint but before the \((n+1)\) checkpoint, then we will have:  
\[b^{c}(Y_{n},y)\ =\ b^{c}_{0}\ +\ b^{c}_{1}y,\ \ \text{where}\ \ b^{c}_{0}>0,\ \ \text{and}\ \ b_{1}\geq 0\ \ \text{are constants}. \tag{1}\]Therefore the time duration \(b^{c}(Y_{n},y)\) depends on the number \(y\) of instructions that have been executed by the program since the last checkpoint was established. In summary, we are assuming that:  
* The time \(B^{c}(Y_{n})\) needed to establish the \(n\)-th checkpoint depends on the \"age of the program\" or the total number of instructions \(Y_{n}\) it has executed since the beginning, i.e., \(B^{c}(Y_{n})=B^{c}_{0}+B^{c}_{1}(Y_{n})\),
* The time \(b^{c}(Y_{n},y)\) needed to recover from a failure after the \(n\)-th checkpoint, including the time related to re-loading system state after the failure, only depends on \(y\leq Y_{n+1}-Y_{n}\), the \"computation time undertaken by the program since the last checkpoint\", i.e., \(b^{c}(Y_{n},y)\equiv b^{c}(y)=b^{c}_{0}+b^{c}_{1}y\).  
Similarly, we denote the energy consumption for creating the \(n\)-th checkpoint to be \(B^{c}(Y_{n})\), and \(b^{c}(y)\) is the energy used to recover from a failure after a failure that occurs when the total number of instructions executed is \(Y_{n}+y\leq Y_{n+1}\). Also, we will have \(B^{c}(Y_{n})=B^{c}_{0}+B^{c}_{1}Y_{n}\), and \(b^{c}(y)=b^{c}_{0}+b^{c}_{1}y\) with \(B^{c}_{0}>0,\ B^{c}_{1}\geq 0\) and \(b^{c}_{0}>0,\ b^{c}_{1}\geq 0\).  
Let \(\alpha,\beta>0\) be positive constants that represent the relative costs of computation time and energy consumption. We can then define the parameters:  
\[B_{0} = \alpha B^{c}_{0}+\beta B^{c}_{0},\] \[B_{1}(Y_{n}) = \alpha B^{c}_{1}(Y_{n})+\beta B^{c}_{1}(Y_{n}),\] \[b_{0} = \alpha b^{c}_{0}+\beta b^{c}_{0},\] \[b_{1} = \alpha b^{c}_{1}+\beta b^{c}_{1},\]  
and the total cost of an instruction can be viewed as the weighted sum of its executon time and of its energy consumption \(c=\alpha K^{c}+\beta K^{c}\).