Online Reclaim Algorithm

The off-line algorithm is based on the worse-case budget. At runtime, slack cycles are generated if a job uses less than the worst-case budget. We can easily adopt our technique to reclaim slack cycles. The idea is that, when a job finishes with δ less cycles compared with the static schedule at time t, this can be interpreted as if t 0 S(x)dx is increased by δ. Beginning at time t, we have the same speed optimization problem with ACF and RCF constraints. In other words, a new optimal solution can be found at any time during run time. Based on the off-line speed function, faster algorithms can be used online. We propose such an algorithm which has time complexity O First, we need to save some additional information: the current speed which may be different from the off-line speed, the accumulated cycles F C up to the curren time and SC which is the accumulated cycles calculated from the off-line speed function. The algorithm follows the off-line speed function and updates the information at each scheduling point; we use scheduling point to refer to any time when a job becomes available, is completed, or is preempted. Normally, F C is increased by the CPU cycles supplied at the current speed. However, when a job finishes earlier, we increase F C further with the slack cycles δ defined above. Thus, F C − SC represents the slack cycles at current time t0. At this point ACF(t0) ≥ F C still holds. If F C > SC, we reduce CPU speed so that F C will approach SC. Once F C = SC again, we can follow the off-line speed function from then on. Since we keep F C ≥ SC all the time and SC ≥ RF C, no job will miss its deadline as long as we keep ACF ≥ F C. Note that the online algorithm tries to find a new speed in the range constrained by ACF and SC. When defining the new speed, we can look ahead at any number of future ACF step points to find a new speed. The more ACF points we check, the smoother the new speed is and the more energy is saved. If we check all ACF points up to the end of a hyper period, we have the optimal solution. This is a trade-off between runtime cost and energy savings. To keep the runtime cost constant, we look at a fixed number of ACF points and assign a constant speed to the new speed.more than three points in the example because we cannot find a constant new speed that causes no extra idle cycles. To our best knowledge, we note that in previous research, a reclaim algorithm can look ahead only one task period. Our method has no such limit, hence more energy reduction can be achieved by our approach. Also note that our algorithm reclaims slack cycles from multiple jobs of different task. Our algorithm depends on ACF and a off-line speed function. Besides the optimal speed function, it applies to any valid speed function defined off-line, including what we call the speculative speed function [