Suppose we want to execute a program on a processor which can run in three different modes. Each mode can be describe by a pair $(E,\tau)$ where $E$ denotes the energy consumption per cycle (in nJ) and $\tau$ denotes the clock period (in ns). Given this notation, the three modes are:
- $A:=(40,20)$
- $B:=(25,32)$
- $C:=(10,40)$
Suppose our program has a deadline of $35$ms and needs $10^{-9}$ clock cycles to finish. Now, we want to minimize the power consumption and satisfy our deadline at the same time.
Using only one operation mode, $B$ would be the best choice (and our program would finish after $32$s). But if we could use two operation modes, there seems to be an even better solution.
So, the idea is as follows: We execute the program for $c_1$ cycles with a frequency of $f_1$ and $(1-c_1)$ cycles with a frequency of $f_2$. Since we want to satisfy our deadline, we can write down the following constraint $$35\text{s}=\frac{c_1}{f_1}+\frac{1-c_1}{f_2}$$ The objective function, we want to minimize, is $$c_1E_1+(1-c_1)E_2$$ where $E_1$ and $E_2$ is the energy (in nJ) per cycle which corresponds to the operation mode related to $f_1$ and $f_2$, respectively.
Seems to be quite easy, but I can't find the optimal solution. How would you do this?
Assuming cycle periods $\tau_2\gt\tau_1$, cycle numbers $C=C_1+C_2=10^9$ and energy consumptions per cycle $E_2\lt E_1$, we want to find the largest $C_2$ not violating the time constraint
$$\begin{align} C_1\tau_1 + C_2\tau_2 &\le T = 35s\\ (C - C_2)\tau_1 + C_2\tau_2 &\le T \\ C_2(\tau_2-\tau_1) + C\tau_1 &\le T \\ C_2 & \le \frac{T - C\tau_1}{\tau_2 - \tau_1} \end{align}$$
In your example:
$$\begin{align} C_2 &= \frac{35 s - 10^9 \times 32 \times 10^{-9}}{40 \times 10^{-9}s - 32 \times 10^{-9}s} \\ \\ &= \frac{35 - 32 }{8 \times 10^{-9} } \\ &=0.375 \times 10^9 \\ C_1 &= 0.625 \times 10^9 \\ T_1 &= C_1\tau_1 = 0.625 \times 10^9 \times 32 \times 10^{-9}s = 20s \\ T_2 &= C_2\tau_2 = 0.375 \times 10^9 \times 40 \times 10^{-9}s = 15s \\ E &= C_1 E_1 + C_2 E_2 = 0.625 \times 10^9 \times 25nJ + 0.375 \times 10^9 \times 10nJ \\ &= 19.375J \end{align}$$