Dynamic Voltage Scaling for Low-Power Hard Real-Time Systems:Off-Line Decisions for Run-Time Scheduling
Off-Line Decisions for Run-Time Scheduling
Static scheduling is not flexible enough to accommodate or take advantage of run-time variations appearing from instance to instance. Run-Time speed management is necessary in this case. Nevertheless, all run-time techniques do employ some sort of off-line phase in order to benefit from the a priori knowledge of certain task parameters. Such off-line decisions include besides classic real-time scheduling choices (i.e. fixing task priorities), determining upper bounds on processor speeds for each task (maxi- mum required speeds, MRS) or even forcing preemption points and altering task priorities, all in order to make the run-time speed management more efficient.
However, it is common that typical static approaches are used in an off-line phase even for run-time strategies, making the distinction between static scheduling and the off-line phase of run-time approaches less clear. In general, static DVS approaches tend to provide a complete solution to the scheduling problem, while off-line decisions are intended to complement and help run-time DVS scheduling, without loading the system with possibly unnecessary data. The large amount of data regarding job speeds and start times that most static DVS techniques provide is becoming obsolete, as run-time speed management takes over.
Maximum Required Speeds for RM Scheduling
The maximum required speed (MRS) method presented in this section is an example of using static task data to improve the run-time schedule via off-line decisions. The main idea of this approach rests on reaching a close to 100% processor utilization by identifying tasks that can run slower. More precisely, MRS is not a scheduling algorithm in itself, but a procedure to compute the smallest possible processing speeds for which a task set is still schedulable with a specific on-line algorithm. At run time, the task set is still scheduled according to the on-line algorithm, but the processor speeds are set using the off-line computed values. Note that the speed choice must not affect the feasibility of the schedule. For tasks with fixed execution time, the only modification of the non-DVS run-time algorithms resides in adding a speed switching sequence. The MRS technique can be applied to a number of classic real-time strategies, including fixed priority scheduling.
For RM scheduling, one may choose to use as a limit the utilization imposed by the condition proposed by Liu and Layland in Ref. [44]. With this approach the MRS is unique for all tasks and equal to
At a closer look, the schedule feasibility condition proposed in Ref. [44] is a sufficient one and covers the worst possible case for the task group characteristics. An exact analysis as proposed in Ref. [69] may reveal further possibilities for stretching tasks while still meeting the deadlines. On the basis of this, Ref. [59] describes a method to compute the maximum required frequency (speed) for a task set. We go even further, and instead of computing a single common maximum required speed for the whole task set {ti}i=1,…,N, as in Ref. [59], we compute individual speeds for each task ti. Note that the speed required by a task is inverse proportional to the task stretching factor. Finding the MRS is in fact equivalent to finding the minimal stretching factors {ai}i=1,…,N . We focus on computing the a factors.
As introduced in Section 18.4.2, a task model includes its deadline Di and period Ti . Since MRS is a static method, the third relevant task parameter in our case is the WCET. The task WCET, denoted by Ci in the following, refers to the time required by the worst case execution pattern (WCE) at the reference (and fastest) frequency fref : Ci = WCEi /fref . Note that for a task with a unique execution pattern, where BCE = WCE = C, WCET can also be written as Ci = Ci /fref . Furthermore, we consider that the tasks in the group are indexed according to their priority, computed as in RM scheduling (1/Ti).
We compute the stretching factors in an iterative manner, starting from the highest priority tasks and continuing with lower priority tasks. Consider that index q points to the latest task which has been assigned a stretching factor. Initially, q = 0. Each of the tasks {ti}q < i £ N has to be executed before one of its scheduling points Si as defined in Ref. [69]
For a concrete example on how to compute the MRS for a set five tasks, refer Example 18.2.
Maximum Required Speeds for EDF Scheduling
EDF strategy, as a dynamic priority scheduling method, is more successful than RM, being able to utilize the processor up to 100%. Intuitively, allowing tasks to run slower until processor utilization reaches 100% should be the preferred method. Nevertheless, determining MRS for off-line tasks is only easy for particular cases, that can be successfully handled by classic real-time analysis. For a generic hybrid task set, Theorem 3.11 from Ref. [45] states a sufficient for EDF schedule feasibility:
(a) Di ³ Ti . In this case, the above condition is also necessary, the left side becoming the classic expression for processor utilization. The recommended (and optimal) unique speed for all tasks is then sEDF–MRS = U, or the worst-case processor utilization at the highest clock frequency. Since this technique is straightforward, it is commonly adopted in EDF with DVS scheduling [56,66].
(b) Di < Ti . Unfortunately, in this case the feasibility analysis becomes intractable [70,71]. Conse- quently, finding optimal speeds—which is equivalent to examining families of task sets—is an even more difficult problem. Yet, upper bounds for maximum required speeds can be found using the left side of the sufficiency condition. Nevertheless, it is possible that this upper bound computes to a value >1, even if the task set can be scheduled under EDF. For these situations, other methods have to be employed for finding better speed bounds.
(c) Di £ Ti , Ti = T. For sets of tasks with the same period, the EDF schedule feasibility problem is solvable in polynomial time (sequencing with release times and deadlines, SS1, with preemption from Ref. [72]). For tasks with different arrival times (asynchronous), the method presented in Section 18.4.3.2 can be used. A similar but simpler strategy can be applied to sets of tasks with the same arrival times (synchronous) [62].
This example contains the results of MRS for the set of five tasks described in Table 18.2. For this set, the task deadlines are equal to the task periods. For the RM-scheduling method, the stretching factors are computed individually. Note that tasks 3 and 4 can be stretched off-line more than 1 and 2, while 5 has the largest stretching factor. The processor utilization changes from 0.687 to 0.994. Observe also that the stretching factors for the lower priority tasks require more iterations to compute. For the EDF scheduling, there is a single stretching factor, common to all tasks, equal to 1/0.687. The maximum required processor speeds relative to the reference speed are obtained by inverting the a factors.
If we consider that the tasks have fixed execution pattern, we can easily compute the energy consumptions for the RM–MRS and EDF–MRS. For this we found out the number of executed instances of each task over the task set hyperperiod, computed as the least common multiplier (lcm) of the task periods. For our example, lcm(5,11,45,130,370) is 476190. Next, assuming that the energy consumed during a clock cycle is dependent on the square of the processor speed, the energy of a task instance is proportional to Ci s 2. Finally, we can sum up the energy consumption after the number of instances for each task. The numerical results are detailed in Table 18.3. Note that, for this example, we assumed that no power is consumed during idle and speed switching. Also, the processor is ideal in the sense that it can run at any speed under the reference speed. It is interesting to note that, for this case, the energy consumed using RM–MRS is very close to that using EFD–MRS. Both approaches manage to save about 52% of the energy consumed by using only the classic RM and EDF employing the same reference speed for all tasks. Moreover, the EDF–MRS energy is minimal, as all tasks execute at the same speed, fully using the processor.
The approaches mentioned before employed a rather simplistic view of the system, which is often sufficient. Nevertheless, more realistic models can be used along with more refined methods, as briefly reviewed below.
Task-Specific Power Characteristics. For tasks with different power characteristics (different switching capacitance), the techniques presented above are not optimal, as tasks consuming more power should be run slower than tasks that consume little power. In Ref. [57] an optimal approach is described similar to the RM–MRS (Section 18.4.4.1) for EDF-scheduled tasks with different power characteristics.
Scheduling with Synchronization. Task synchronization and blocking due to accessing common resources is yet another case for which using the same speed for all tasks is not optimal. Again, based on a real-time analysis similar to the one in Section 18.4.4.1, the authors of Refs. [58,60,73] describe a method for deter- mining off-line maximum required speeds for tasks with synchronization, scheduled with RM and EDF.
Variable Execution Patterns. All the approaches described earlier, work either on tasks with fixed execution patterns or use the worst-case execution exclusively. Nevertheless, for tasks with variable execution pattern, knowing something about the stochastic behavior of the tasks can help to derive better off-line schedules. One approach that employs the expected execution time for this purpose is the uncertainty-based ordering (UBO) [62,63].
UBO is based on the observations that scheduling short tasks or tasks with large variations (uncertainties) in execution early, allows the run-time speed manager to select a low processing speed early. In contrast, allowing for uncertainties to persist, forces the run-time manager to keep selecting high speeds, in order to accommodate even the worst-case behavior.
In this context, Ref. [63] defines a new priority function for sets of independent tasks with variable execution pattern, unique period, and deadline. This priority function sets in fact an order among those tasks whose order does not affect the real-time behavior of the task set. Going further on this idea, Ref. [62] presents a UBO method for EDF-scheduled jobs with synchronous release times. Moreover, by examining the ready tasks between two successive deadlines, the approach splits certain tasks by introducing preemption points, if the execution order can be improved in this manner.
Comments
Post a Comment