http://www.cs.pitt.edu/~kirk/cool.avi

Consider power objective of miminizing the maximum temperature.

Assume for today that P=s^alpha, and we will mostly consider 
the model where jobs have release times, deadlines, and work.

BKP: Assumes software controls speed of the processor
Chroback, Dur, Hurand, Robert assumes hardware controls speed, and 
in particular the speed is halved if a thermal threshold is exceeded.


Newton's Law of Cooling:

Continuous: 
dT/dt = a P - b (T - T_env)

T= temperature
t= time
P= power
T_env = environmental temperature 
a,b constants 

By rescaling energy, wlog a=1 and by rescaling temperature
wlog T_env = 0

dT/dt =  P - b T


Discrete:
T_{t+1} = (P_t + T_t )/b


Understanding Newton's Law:

Question: What happens to temperature if you run at constant speed s? Assume initial temperature 0.

Answer: First note that temperature doesn't go to infinity since cooling rate increases as T rises,
but power doesn't. Temperature rises until some equilibrium is reached. To compute this equilibrium

Using Newton's law, let's rewrite speed in terms of temperature

dT/dt =  P - b T


P = dT/dt + b T

s^alpha =  dT/dt + b T 

Substituting dT/dt = 0,  T = s^alpha /b



Question: If you are at temperature T (say the thermal limit of the device),
how fast can you go while staying below temperature T?

Answer: Using Newton's law, let's rewrite speed in terms of temperature

dT/dt =  P - b T


P = dT/dt + b T

s^alpha =  dT/dt + b T 

s = ( dT/dt + b T )^{1/alpha} 

Note that want that dT/dt = 0 for the constant temperature schedule. 
So speed s = ( b T )^{1/alpha} will keep the temperature fixed to be T.



Question: In the YDS Model, what is the min-max temperature schedule for 1 job with release time 0,
deadline 1, and work w?  Assume initial temperature = 0.

SubQuestion: In particular, is it the schedule where the temperature is constant? 

SubAnswer: Since s = ( dT/dt + b T )^{1/alpha} 

work processed = integral_0^1 s dt = integral_0^1 ( dT/dt + b T )^{1/alpha} 

Note that dT/dt = 0 for the constant temperature schedule, so you are not getting
any benefit in terms of work processed from dT/dt, so this isn't optimal.


SubQuestion: How about the optimal energy schedule where the speed is constantly 1/w? 

SubAnswer: Assume that the maximum temperature is at the end. Then it would be better
to move some work earlier. 


Answer: So basically the speed should decrease geometrically.  
The exact equations are a bit complicated,
and require calculus of variations to derive them.



Pseudo Theorem Relating energy, temperature and power: 
lim_{alpha -> infinity} Energy = lim_{b -> infinity} Temperature = maximum power

Pseudo Proof: lim_{alpha -> infinity} Energy = maximum power since the convexity increases with alpha
lim_{b -> infinity} Temperature = maximum power since energy disappears immediately

Pseudo Theorem Relating energy, temperature and power: 
lim_{b -> 0} Temperature = Energy

Pseudo proof: When b=0,  no energy is lost, and the maximum temperature is at the 
end and is exactly the energy.


So consider the scheduling problem from BKP where the QoS objective/constraint is
deadline feasibility and the power objective is to minimize the maximum power/speed.

The offline optimal schedule is in principle computable in poly time by convex programming,
but is generally complicated.

Theorem: The YDS schedule, which is optimal for maximum power and energy, is 20-competitive
for temperature. So the optimal energy schedule is not ridiculously bad for temperature.


Now consider online scheduling:

Question: Is AVR or OA, which are competitive for energy, competitive for temperature?
Answer: No. Consider the following instance
Release time    Work     Deadline
0                1          1
1/2              1/2        1
3/4              1/4        1
7/8              1/8        1
and so on

The YDS schedule runs at constant speed 2 and has maximum temperature O(1)
ARV will run at speed Omega(log n) right before time 1, giving temperature omega(1)

Conclusion: Not all schedules that are competitive for energy are competitive for temperature


Now consider the case that b=infinite = max power objective

Algorithm design technique: Construct a lower bound to gain intuition

Example:
Let c be presumed competitive ratio

Consider n jobs released at times 0 .. n-1 with deadline n and work 1
So optimal = speed 1 = power 1
speed at time 1 for online <= c/n or it wouldn't be c competitive if the stream of jobs ended here
speed at time 2 for online <= c (1 - c/n  + 1)/(n-1)    
continuing these calculations, you get that online must go at something like speed > 2 toward the end.

Note that the rate of work arrive = optimal speed 
After playing around a bit (or using calculus of variations) you get
that the worst case is if work is increasing exponentially 

Theorem: There is a lower bound of e on the competitive ratio for maximum speed
and hence e^alpha competitive for maximum power
proof: work arrives at rate 1/ (ln (1/epsilon) (1-t)) with deadline 1-epsilon
Follow the reasoning in the example you get the result

Question: What is the "right" algorithm for this lower bound instance?
Answer: BKP, at each time t run at speed

e* max_{t_1 < t < t_2}  w(t, t_1, t_2)/(t_2 - t_1)  

where w(t, t_1, t_2)/(t_2 - t_1) is work that we know about that 
must be done in [t_1, t_2], ie work with release time > t_1 but less than t
and deadline < t_2. So intuitively, this is e times the best lower bound
that we have for YDS at this time. In hindsight, maybe one could have guessed
at this algorithm, but we really got it from the lower bound.


Theorem: BKP is cooling oblivious, ie it is simultaneously competitive for all
b, including b=infinity (max power) and b=0 (energy)
Proof: Complicated

Important point: BKP is oblivious of the current temperature, and the cooling rate.
From a systems point of view this simplifies things greatly as the software scheduler
doesn't need to know physical properties of the underlying hardware