Plausible story behind YDS paper circa mid 90's:

Speed Scaling Technology

Faster processor = less energy efficient, better performance


***********************************
Notes on "A static power model for architects" by Butts and Sohi

Power = Dynamic Power + Static Power = P_dyn + P_static

Definition: Dynamic power is power used to do computations, 
that is when switching

Definition: Static power is power used even if not switching

Fact: Static power as a percentage of total power is increasing 
(see figure 1)

Equation: P_dyn =  supply voltage^2 * frequency
      = V_cc * frequency  

Minimum value of V_CC is roughly linear with f (This fact is not in the paper)

Fact: P_dyn = f^3, sometimes called cube-root rule 


Equation: P_static = design constant * number of of transistors * 
           suppply voltage * subthreshold leakage
         = k_design * N * V_cc * I_leak


(For subthreshold leakage see figures 2 and 3 in the paper)

Definition: Constant field scaling = reduces supply voltage by 
the same factor as device dimensions and speed increases

Equation: switching time = Supply Voltage/ Drain current 
                         = V_cc/I_sat

So under constant field scaling, let us say you are halving
V_cc and switching time. Then I_sat must remain constant.

Equation: I_sat = (supply voltage - threshold voltage)^1.5
      = (V_cc - V_t)^1.5

Definition: Threshold voltage = voltage to turn on transistor

So in order to keep I_sat constant when V_cc is halved, 
then V_t has to be reduced

Definition: Subthreshold leakage = e^(-V_T/temperature)

***********************************


Not obvious how to get interesting problem

YDS contribution = Look at scheduling

Algorithms:
SRPT, SJF, FCFS, EDF, SETF, RR=PS, MTF

Machine environment= single processor
Job environment: each job i has release time r_i and work w_i
	schedule with preemption

QoS Objective:

Average flow/waiting/response time = (sum_{i=1}^n C_i - r_i)/n

Maximum Lateness: each job has a deadline d_i, and you want
to minimize max_i C_i  - d_i

For speed scaling, you have a power related objective


Energy
Temperature
Maximum Power



Dual optimization problem: 
One approach is to fix one objective (make it a constraint) and
optimize the other objective.

YDS take this approach. Deadline feasibility (Lateness <=0)
and Energy Optimization

Deadline feasibility as a (pseudo) LP
w_j,t is how much work you do on job j at time t


sum_t w_j,t = w_j
sum_j w_j,t <= 1

w_j,j >= 0


Theorem: EDF is optimal for maximum lateness
Proof: By contradiction. Consider the first deadline d_i missed,
and the last time t before d_i when EDF was running a job with deadline > d_i.
Then during (t, d_i) there was more than (d_i - t) work that has to be
done. 


KEY POINT: Only unit processing time is available at each time.

YDS problem as a (pseudo) convex program
w_j,t is how much work you do on job j at time t

min sum_t s_t^3

sum_t w_j,t = w_j
s_t = sum_j w_j,t 

w_j,j >= 0


Intuition for YDS algorithm:
1 job
2 jobs r_i < r_j < d_j < d_i
2 jobs r_i < r_j < d_i < d_j


Online algorithms:
AVR
OA
qOA
...
BKP

Fact: YDS analysis of AVR complicated global analysis


BKP analysis of OA