Combining optimistic and pessimistic DVS scheduling: An adaptive scheme and analysis

Performance boosting of modern computing systems is constrained by the chip/circuit power dissipation. Dynamic voltage scaling (DVS) has been applied for reducing the energy consumption by dynamically changing the supply voltage. One can optimistically apply greedy online DVS scheduling algorithms by considering only the events that have arrived in the system. However, this might require a speed that is beyond a system´s capability. Alternatively, one can pessimistically use a conservative speed to ensure timing guarantees, which might consume an excessive amount of energy as events might be processed faster than necessary. This paper presents an adaptive scheme that combines these two strategies for the scheduling of arbitrary event streams. The proposed adaptive DVS scheduler chooses the execution speed dynamically as long as it is below a certain threshold. Once the speed exceeds this threshold, the proposed scheduler operates at a constant (pessimistic) speed for guaranteeing the feasibility. The computation of the threshold speed is, however, not straight-forward. For deriving it, we make use of a framework based on timed model checking because the scheduler is strongly state-dependent. The resulting analysis framework allows to obtain the threshold speed for the proposed adaptive DVS scheduling algorithm such that both timing and speed constraints are guaranteed to be met and at the same time an energy-efficient execution is ensured.