# Minimizing Energy and Computation in Long-Running Software
## 2 A Single Loop Program with Checkpoints
### Fixed Checkpoint Intervals  
Earlier work has shown that \"age dependent\" checkpoints [51] can reduce the overall cost of checkpointing and failure recovery, when (for instance) the failure rate of a system increases with time. However, most practical checkpointing schemes use a simpler approach where checkpoints are carried out periodically each time the program has executed successfully a predetermined fixed number of instructions \(y_{n}=y\). Thus, in the sequel we will make this assumption so that checkpoints are placed after \(Y_{1}=y,\ Y_{2}=2y,\..\ Y_{n}=ny\), etc. instructions have been successfully executed, and we will proceed to compute the optimum value of \(y\), assuming that \(n\) is fixed in advance.  
When the program ends after \(Y=Ny\) instructions are executed, a further \((N+1)\)-th checkpoint is not needed, while the first checkpoint is obviously installed before the first instruction is executed.  
We can then formulate our problem as that of a program that executes a total fixed number of instructions \(Y\), where we want to choose the constant value \(y\) of the number of instructions between checkpoints, or equivalently we can choose \(N\), the number of checkpoints so that \(Y=Ny\) so that the total overhead in additional work and energy consumption due to failures and due to checkpoints is minimized.  
For a given \(y\), let us compute \(K^{c}(y)\), which is the corresponding total expected execution time including all restarts due to failures, starting from the most recent checkpoint. When the average execution time per instruction is \(c\), and the failure probability per instruction is \((1-a)\), the total average time elapsed time for the execution of \(y\) instructions is:  
\[K^{c}(y) = cya^{y}+(b_{0}+K^{c}(y))(1-a^{y}), \tag{2}\] \[+(K^{c}+b^{c}_{1})\sum_{x=1}^{y}xa^{x-1}(1-a),\]because with probability \(a^{y}\) a failure does not occur during the \(y\) instructions, leading to an execution time of \(K^{c}y\) time units, while with probability \((1-a)^{y}\) at least one failure does occur among the \(y\) instructions, and the first of those requires a program re-start time of \(b_{0}^{c}\), to which we should add \(K^{c}(y)\) representing the effect of all future failures after the program has been re-initialised from the checkpoint.  
Also, we have to include the execution time plus the amount of additional work needed per executed instruction, until the failure occurs--hence the term \((K^{c}+b_{1}^{c})-\) multiplied by \(x\) and the probability that the failure occurs at instruction \(x\) which is \(a^{x-1}a\), summed over \(x\) running from \(1\) to \(y\). Since  
\[\sum_{x=0}^{y}a^{x} = \frac{1-a^{y+1}}{1-a},\] \[\text{and}\ \frac{d}{da}\frac{1-a^{y+1}}{1-a} = \frac{1-ya^{y}(1-a)-a^{y}}{(1-a)^{2}},\]  
we obtain:  
\[K^{c}(y)=b_{0}^{c}[a^{-y}-1]+\frac{K^{c}+b_{1}^{c}}{1-a}[a^{-y}-1]-b_{1}^{c}y. \tag{3}\]  
the total expected energy consumption \(K^{c}(y)\) for a number of instructions \(y\) after the most recent checkpoint, we similarly obtain the quantity:  
\[K^{c}(y)=b_{0}^{c}[a^{-y}-1]+\frac{K^{c}+b_{1}^{c}}{1-a}[a^{-y}-1]-b_{1}^{c}y, \tag{4}\]  
where \(K^{c}\) denotes the average energy consumption per instruction, so that  
\[C(y) = \alpha K^{c}(y)+\beta K^{c}(y), \tag{5}\] \[= b_{0}[a^{-y}-1]+\frac{c+b_{1}}{1-a}[a^{-y}-1]-b_{1}y.\]  
Interestingly enough, we can show using I'Hopital's Rule, for all \(y\geq 1\), that:  
\[\lim_{a\to 1}\ C(y)\ =\ c^{y}, \tag{6}\]  
as would be expected.  
Treating \(y\) as if it were a real number, we can compute the derivative of \(C(y)\). We first note that for a differentiable function \(f(y)\) of the real variable \(y\), we can write:  
\[\frac{df}{dy}=f.\frac{d\ln f}{dy},\ hence\ \ \frac{d}{dy}a^{-y}=-a^{-y}.\ln a, \tag{7}\]  
and therefore  
\[\frac{dC(y)}{dy}=-\ln a.[\frac{b_{0}}{a^{y}}+\frac{c+b_{1}}{a^{y}(1-a)}]-b_{1}. \tag{8}\]  
Because \(a\leq 1\), the quantity \(-\ln a\geq 0\), and since \(y\) is large, \(\frac{1}{a^{y}}\) is very large and \(\frac{dC(y)}{dy}>0\).