Improving TAS Adaptability with a Variable Temperature Threshold
Anthony Dowling Ming-Cheng Cheng Yu Liu








dowlinah@clarkson.edu


Department of Electrical and Computer Engineering, Clarkson University, 8 Clarkson Ave., Potsdam, 13699, New York, USA


   
    Thermal-Aware Scheduling (TAS) provides methods to
    manage the thermal dissipation of a computing chip
    during task execution. These methods aim to avoid issues
    such as accelerated aging of the device, premature
    failure and degraded chip performance. In this work, we
    implement a new TAS algorithm, VTF-TAS, which makes use
    of a variable temperature threshold to control task
    execution and thermal dissipation. To enable adequate
    execution of the tasks to reach their deadlines, this
    threshold is managed based on the theory of fluid
    scheduling <cit.>. Using an evaluation
    methodology as described in <cit.>, we
    evaluate VTF-TAS using a set of 4 benchmarks from the
    COMBS benchmark suite <cit.> to examine its
    ability to minimize chip temperature throughout schedule
    execution. Through our evaluation, we demonstrate that
    this new algorithm is able to adaptively manage the
    temperature threshold such that the peak temperature
    during schedule execution is lower than POD-TAS, with
    no requirement for an expensive search procedure to
    obtain an optimal threshold for scheduling.



 Thermal Aware Scheduling Proper Orthogonal Decomposition High Resolution Thermal Modelling CPU Thermal Management Real-Time Scheduling 







§ INTRODUCTION



POD-TAS <cit.>, is a TAS algorithm that relies
on a pair of static temperature thresholds. Through
evaluation, this algorithm proved to be very capable of
controlling the CPU temperature within the defined maximum
temperature. However, this algorithm carries a limitation in
its requirement for a fixed threshold. Requiring the
threshold to be static invokes a need for a search to obtain
an optimal value for the threshold. This search carries high
computational cost to find the optimal threshold values.
Instead, if the algorithm were able to find an optimal or
nearly optimal threshold during scheduling, this would avoid
the high cost of searching for the optimum. This could be
achieved with a number of granularities; the simplest would
be to make a more intelligent search capability for the
algorithm to perform scheduling as little as possible while
finding the optimum threshold for a given task set and CPU,
but this would still involve a great deal of cost. Moving to
finer granularities, the threshold could be optimized per
scheduling period, using the threshold found in the previous
period as an initial value as to a potential optimum when
starting a search. However, both of these methods would
require a search mechanism which would invoke high
computational cost.  Instead, a purely variable threshold
would be preferable.

In this work, we utilize concepts from
POD-TAS <cit.>, including the TAS notation, to
define, implement, and test an algorithm that is capable of
dynamically optimizing the temperature threshold during
schedule creation.  To achieve dynamic adjustment of the
temperature threshold, a heuristic is developed based on
fluid scheduling <cit.>.  Fluid scheduling is a
scheduling methodology that aims to maintain a constant rate
of execution for tasks so that execution completes exactly
at the task's deadline.  Our heuristic aims to maintain a
nearly fluid execution rate for all of the scheduled tasks,
maintaining their execution rate by adjustment of the
temperature threshold. If the tasks need to execute more to
maintain a fluid execution rate, the temperature threshold
is increased; but if the tasks are executing faster than
their fluid execution rate, the threshold is lowered.



§ VTF-TAS: A VARIABLY THRESHOLDED FLUID TAS ALGORITHM


The control flow of the VTF-TAS algorithm is similar to the
flow of POD-TAS.  However, the ASSIGN_TASKS and
UPDATE_STATES algorithm are both changed to meet the needs
of this new algorithm. Furthermore, the SELECT_TASKS
algorithm is integrated into the new ASSIGN_TASKS_VTF
algorithm to allow for greater control over task to core
assignments.







To start, a key difference between VTF-TAS and
POD-TAS <cit.> begins with its use of CPU core
states. In POD-TAS, there were three thermal states: cold,
warm, and hot. In VTF-TAS, we do not use the T_C
threshold; thus, we only have cold and hot for available
thermal states. Idle and running remain for execution
states, however, giving us 4 possible CPU core states. The
CPU core states used in VTF-TAS and their transitions are
shown in Figure <ref>. Again, the
(H,R) state is unreachable, because as soon as the
temperature of a core is detected to have exceeded T_H, it
is idled.  Algorithm <ref> demonstrates
this logic in the for of pseudocode to construct the set
Ψ, which is used in other algorithms to denote the CPU
core states.



The core VTF-TAS algorithm is shown in
Algorithm <ref>.  Initially, the T_H value is
given as an input to the algorithm as T_H0.  This allows
the algorithm to be “hinted” as to a valid initial value
of T_H.  This is also used to improve the algorithm
flexibility later on. The primary loop flows similarly to
POD-TAS <cit.>, iterating through the time domain and constructing
the schedule, σ. However, VTF-TAS checks at each time
step if an assignment is needed using
Algorithm <ref>. This checks the conditions of
the CPU and tasks to ensure that assignments are made when
required. After assignment, T_H is updated depending on
the execution progress of the tasks, temperature prediction
is performed in the same manner as POD, and the CPU core
states are updated using
Algorithm <ref> before moving on to the
next time step. The key improvements of VTF-TAS arise from
the updated task assignment method and the ability for T_H
to be updated as the schedule is constructed.




Algorithm <ref> is used to check the conditions
of the tasks and CPU cores to see if an assignment is needed
either to ensure task completion, or to avoid overheating. It consists
of a set of five condition checks. The first condition checks to see if
any currently assigned tasks have completed, which triggers an
assignment. The second check checks to see if all of the tasks
in τ have completed. If so, no assignment is needed, since the
first condition would have already caused them to be unassigned. The
third condition checks to see if any tasks require an override
to ensure their completion by the end of the period. The fourth
check looks for any overheated cores that aren't currently idle
to trigger an assignment to idle them. Lastly, we check for
incomplete tasks in τ that are not currently assigned. If
such tasks exist, then if any cores are cool and idle, then an
assignment is triggered.

Algorithm <ref> describes the task
assignment algorithm of VTF-TAS. Here, the candidate task
selection operations are integrated into the assignment
algorithm to enable the overriding of threshold restrictions
for tasks that must be executed continuously to meet their
deadline. First, the CPU cores are sorted according to their
temperature to create π_sorted. Also, a second sorted
set of CPU cores, π' is created, excluding overheated
cores.  Next, the tasks are sorted according to their
remaining execution time to prioritize the execution of
tasks with higher remaining run time. τ_Ω is a
set of the tasks that must be constantly executed in order
to meet their deadline, while τ' contains the tasks
without temperature overrides.  After these sets are
constructed, tasks in τ_Ω are assigned to the
coolest available cores first to avoid unnecessary
overheating of the CPU cores. Then, any remaining tasks are
assigned to available cool CPU cores.





The last algorithm used in the implementation of VTF-TAS is
Algorithm <ref>, which describes the process by
which T_H is updated.  First, C, D, and D_prev are
initialized to 0. These are static variables, so they keep
their value between calls to this algorithm. This is needed
to track the state of certain values throughout scheduling.
Then, the percentage of the current scheduling period that
has been completed is calculated to be used in other
calculations. U_τ stores the average of task
utilization of the period. Utilization is calculated as the
WCET of the task divided by the period length. The next
value, U_F stores the remaining utilization of τ if
the tasks have been executing in a fluid manner.  U_σ
is calculated to be the average remaining utilization of the
task set. σ is used for this notation, as this value
is dependent on the schedule.  Remaining utilization is
calculated as the remaining execution time of the task
divided by the period length.  U_σ and U_F are
then used to calculate H, the threshold update heuristic.
H is calculated as the average of the difference and ratio
of U_σ and U_F. We also subtract 0.5 from this
value so that when U_σ=U_F, H=0.  The average is
used to prevent the heuristic from being sensitive to the
ratio becoming too large or the difference becoming too
small at the end of the period. Averaging these two values
helps to keep H stable throughout the period.  H is also
scaled based on the remaining percent of the period, as the
ratio component can cause massive fluctuations in H toward
the end of the period.

The scaled heuristic value is then compared to W_D, which
defines a “dead zone” around 0 for threshold updates. If
H_scaled>W_D, then the threshold is increased, otherwise
if H_scaled<-1*W_D, then the threshold is decreased.
Threshold updates are also dampened using 1/C+1. C
stores the number of consecutive threshold updates in the
same direction. Thus, repeated updates to the threshold
cannot cause T_H to become too large or too small. The
direction of the update is tracked with D, a positive
update results in D=1, while a negative update sets
D=-1. If |H_scaled|<W_D, then D becomes 0 to denote
no update occurring. The final if statement in the algorithm
on line 14 checks to ensure that an update occurred, and that
it is either the first update in a given direction, or that
it is in the same direction as the previous update.

Figure <ref> demonstrates the heuristic
behavior using a simulated execution schedule.
Figure <ref> shows the utilization
of an example synthetic execution schedule (orange) versus
the fluid utilization (blue). When the schedule utilization
is not decreasing, this indicates that no tasks are
executing. Decrease of this value shows active task
execution.  Once the schedule utilization reaches 0, then
all tasks have completed their execution. The worst case
line indicates the point where the tasks would need to
constantly execute in order to complete before their
deadline. Should the schedule utilization exceed this, then
at least one tasks deadline will be breached.
Figure <ref> shows the heuristics
that can be used for controlling the temperature threshold
during scheduling. We can see that the ratio of schedule and
fluid utilization is stable in the beginning of the period,
but suffers rapid fluctuations toward the end of the period.
Conversely, the difference of these values shows a loss of
sensitivity toward the end of the period. These effects are
due to the decreasing magnitude of the utilization as the
period continues. To rectify this issue, we can see that the
average of the ratio and difference gives a heuristic that
remains more stable throughout the entire period. This value
is used as H in Algorithm <ref>.



§ EVALUATION METHODOLOGY


For VTF-TAS, we improve the methodology from <cit.>
to use a more realistic initial condition for temperature
prediction during TAS. By default, POD temperature
prediction begins with the CPU temperature being uniform at
T_amb, or 45^∘C. While this is valid, it
represents a CPU that is entirely without power. This
scenario is not representative of a realistic TAS scenario,
where a CPU would be powered on, but idle, before beginning
schedule execution. Thus, we used the static power
dissipation of the CPU to perform POD prediction until the
output of the ODE solver stabilized. These ODE outputs, when
used to reconstruct the CPU temperature yield the steady
state temperature of the CPU when only static power is
applied.  This thermal state is representative of a CPU that
is idle, but powered on.

Figure <ref> shows this process.
Figure <ref> shows the calculated ODE
coefficients. They appear to stabilize very quickly, but
Figure <ref> shows the maximum
absolute value of the first derivative of the coefficients.
This shows that it takes much longer for their values to
stop changing. Around 600ms, we can see that it drops to a
value of 10^-32 and does not change. In the computed
data, we replaced 0 values with this value to enable
logarithmic scale plotting of the data.  Thus, the ODE
output completely stops changing at this point.
Figure <ref> shows the reconstructed
temperature of the CPU cores in this case. We can see that
they stabilize to nearly the same value. Since our CPU
floorplan is symmetric, this is expected. However, the
values are not perfectly equal due to numerical error during
FEM and POD training.








§ EVALUATING VTF-TAS



To evaluate the VTF-TAS algorithm's scheduling performance,
we have constructed schedules under a number of conditions
to observe the predicted thermal behavior. This evaluation
gives us an understanding of the behavior of VTF-TAS and due
to the accuracy of the POD thermal model, we can assume that
the actual CPU temperature when calculated with FEM will
differ minimally from the temperature predicted during
scheduling.

The first experiment performed is with W_D=0. The results
of this test are shown in Figure <ref>.
The topmost subplot shows the remaining execution time for
each task throughout the scheduling period. The dotted lines
represent the remaining execution times of the task if it
were executing according to a purely fluid schedule. The
black dotted line represents the remaining time in the
period. Should a task's remaining run time meet this line,
then that task is given an override, which disables
threshold updates, and allows that task to execute on any
core, even overheated ones, to ensure its completion before
its deadline. We tend to see overrides occurring towards the
end of each period due to task 1 executing too slowly,
triggering the override mechanism.  The middle plot shows
the scheduling heuristic. In general, if tasks are executing
more quickly than their fluid execution rate, then this
heuristic is below 0, while slower execution brings the
heuristic above 0.  Since in this experiment, W_D=0, when
the heuristic is negative, T_H decreases, and vice versa.
The last plot shows the predicted CPU temperature during
scheduling for each core along with T_H being shown as the
solid black line. T_H tends to be regularly updated in
this scenario, but remains fairly stable throughout
scheduling.



Figure <ref> shows the scheduling
behavior with W_D=0.01. Here, the heuristic is allowed to
vary around 0 before triggering an update to T_H, which
leads to a generally more stable T_H value. However, we
can see that this leads to high variance in T_H since
toward the end of the period, many fast updates to increase
T_H occur, causing a spike, leading to a worse overall
peak temperature, and higher variance in the core
temperatures.



Table <ref> shows the peak CPU temperature
and maximum threshold violations for varying values of
W_D. From this table, we can see that maximum performance
is achieved when W_D=0, meaning that while this mechanism
can help prevent unnecessary changes to T_H, it does have
a slightly negative impact on overall thermal performance of
the constructed schedule. From this evaluation, we can see
that when W_D=0, this algorithm's peak temperature is
lower than POD-TAS' <cit.> peak temperature by
≈1.5^∘C. Plots similar to
Figures <ref> and <ref>
for W_D=0.1 and W_D=0.001 are shown
in <ref>.  We do not perform the final FEM
evaluation of the schedule temperature in this work due to
the high accuracy demonstrated by the POD thermal model used
during scheduling.




§ CONCLUSION



Using the methodology and core concepts put forth with the
POD-TAS algorithm <cit.>, we designed and
evaluated a new algorithm for TAS, VTF-TAS. This algorithm
utilizes concepts from fluid scheduling to enable the
adaptive management of the temperature threshold during task
scheduling. This capability removes the need for the search
process used for POD-TAS <cit.>, removing a high computational
overhead for obtaining optimal thresholds to use during
scheduling. Through our evaluation, we demonstrate that
VTF-TAS is capable of achieving a lower peak temperature
than the POD-TAS algorithm while not violating task
deadlines.



plain




§ VTF-TAS WITH OTHER VALUES OF W_D







