Optimality and Fairness in Speed Scaling Systems
Abstract
Dynamic speed-scaling has received significant attention in the recent literature as an effective method for balancing between better performance and the associated cost of energy. In particular, the objective of minimizing the linear combination of average response time and energy consumption in single-server systems is extensively studied. Coupled speed-scaling, in which the speed is a function of the number of jobs in the system, is shown to be robust and optimal for minimizing the linear combination of average response-time and energy consumption in a single-server system. However, there are concerns that coupled speed-scaling may create or magnify unfairness. The goal of this thesis is to further investigate the tradeoffs between optimality and fairness in speed-scaling systems. We investigate the autoscaling properties of coupled speed-scaling systems under distributional assumptions about the workload and structural assumptions about the speed scaler. We observe distinct speed-scaling dynamics for PS and SRPT, which sheds light on the tradeoffs between optimality and fairness in coupled speed-scaling systems. In particular, we observe that the cost under M/GI/1 PS with coupled speed-scaling is near-optimal at high load. Furthermore, we investigate the magnitude of unfairness under SRPT. We observe that the compromise in cost optimality is small for PS in comparison to the significant performance degradation for the largest jobs under the optimal policy SRPT.
We further investigate the possibility of a robust, fair, and near-optimal policy in speed-scaling systems. We show that the FSP policy is not well-defined in the coupled speed-scaling model. To facilitate the analysis of FSP and other scheduling policies on a level ground, an alternative model called decoupled speed-scaling is proposed and evaluated. With decoupled speed-scaling, FSP dominates PS, and is provably efficient. Simulation results demonstrate a notable performance advantage for FSP, compared to PS. Based on our analysis and evaluation, we conjecture that it is possible to achieve fairness, robustness, and near-optimality with decoupled speed-scaling.
Description
Keywords
Computer Science
Citation
Elahi, B. M. (2017). Optimality and Fairness in Speed Scaling Systems (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/27207