Spatio-Temporal Load Deferral Algorithms for Energy Use Optimization

As computation is outsourced to the "clouds" and Mobile platforms, the differences in latency and responsiveness across these platforms presents new challenges in scheduling. To ensure the quality of service (QoS), a variety of workload scheduling techniques have been adopted by the service providers. However, these techniques often ignore the flexibility available in the service level agreements (SLAs) and focus on improving the performance rather than energy efficiency. This thesis explores opportunities for energy savings. For instance, the slackness in the job execution presents a great potential for energy savings. To achieve energy efficiency, we exploit the available slack opportunities from the SLAs to schedule workload under bounded latency requirements. We devise spatio-temporal deferral techniques for load balancing in the Cloud spanning the three layers of geographically distributed data centers, capacity provisioning inside a data center and job scheduling inside a server. Globally, we devise deferral techniques for load balancing by dynamic assignment and migration of jobs to the more available and cheaper sources of energy. Inside a data center, we devise server capacity provisioning techniques utilizing the flexibility of temporal-deferral to dynamically ̀right-size' the cluster of servers for energy proportionality. We also investigate the impact of dynamic deferral on user satisfaction and devise techniques to capture the loss in value of deferred execution by utility functions and make a trade-off between user satisfaction and energy efficiency. In addition, we devise path consolidation techniques to achieve power-proportionality in the data center networks. Integration with renewable energy sources presents another important means to improve energy efficiency. It allows us to not only tradeoff energy use quantity against costs but also makes the "quality" of energy an important consideration. The quality cost may be due to the time energy is used or the source of energy with or without carbon-cost. We devise workload shaping techniques to increase renewable energy usage for computing workload in data centers and EV charging/discharging load for smart grid. We investigate how much renewable power to store and how much workload to delay for increasing renewable usage while meeting latency constraints. In this dissertation, we analytically prove the quality of our proposed techniques for workload scheduling and experimentally show that significant energy savings can be achieved via dynamic deferra