Dynamic task-level voltage scheduling optimizations

Energy versus delay trade-offs are explored for systems that must manage energy expenditure as well as computation deadlines. The focus is execution of a single process on a single processor. Two probabilistic process models are considered, along with a family of power dissipation models. The first process model assumes that process complexity is exactly c cycles with probability p(c). The second model considers the detailed branching and loop structure of the code. Probabilities are attached at branch points. The power models assume that energy dissipation per cycle is proportional to v(m) and that execution time for a cycle is proportional to v(-n), where v is supply voltage. The energy versus delay trade-off is implemented using dynamic voltage and clock adjustments. The problems solved include 1) minimize expected execution time given a hard energy budget and 2) minimize expected energy expenditure given a hard deadline. The problem of minimimizing the expected value of Q(E,T) where Q is a penalty function and E and T are, respectively, total energy and total time, is also solved using the first process model. Analysis determines theoretical conditions where it may be profitable to switch voltage or modify an a priori voltage schedule.