This book addresses the urgent issue of massive and inefficient energy consumption by data centers, which have become the largest co-located computing systems in the world and process trillions of megabytes of data every second. Dynamic provisioning algorithms have the potential to be the most viable and convenient of approaches to reducing data center energy consumption by turning off unnecessary servers, but they incur additional costs from being unable to properly predict future workload demands that have only recently been mitigated by advances in machine-learned predictions.
This book explores whether it is possible to design effective online dynamic provisioning algorithms that require zero future workload information while still achieving close-to-optimal performance. It also examines whether characterizing the benefits of utilizing the future workload information can then improve the design of online algorithms with predictions in dynamic provisioning. The book specifically develops online dynamic provisioning algorithms with and without the available future workload information. Readers will discover the elegant structure of the online dynamic provisioning problem in a way that reveals the optimal solution through divide-and-conquer tactics. The book teaches readers to exploit this insight by showing the design of two online competitive algorithms with competitive ratios characterized by the normalized size of a look-ahead window in which exact workload prediction is available.
Author(s): Minghua Chen, Sid Chi-Kin Chau
Series: Synthesis Lectures on Learning, Networks, and Algorithms
Publisher: Springer
Year: 2022
Language: English
Pages: 84
City: Cham
Acknowledgements
Contents
About the Authors
1 Introduction
1.1 Background
1.2 Dynamic Provisioning in Datacenters
1.3 Related Studies
1.4 Summary of Contributions
1.5 Organization of the Book
2 Preliminaries of Online Algorithms and Competitive Analysis
[DELETE]
2.1 Introduction
2.2 Model of Online Optimization
2.2.1 Arrival Models
2.2.2 Offline Optimization Versus Online Optimization
2.2.3 Competitive Analysis
2.2.4 Definitions
2.3 Ski-Rental Problem
2.3.1 Optimal Offline Algorithm
2.3.2 Deterministic Threshold-Based Online Algorithm
2.3.3 Lower Bound for Deterministic Online Algorithms
2.3.4 Randomized Threshold-Based Online Algorithm
2.3.5 Lower Bound for Randomized Online Algorithms
2.4 Summary
3 Modeling and Problem Formulation
[DELETE]
3.1 Settings and Models
3.1.1 Workload Model
3.1.2 Server Energy Model
3.1.3 Power Conditioning System Model
3.1.4 Cooling System Model
3.1.5 Power Grid Model
3.2 Problem Formulation
3.2.1 Operating Cost
3.2.2 Datacenter Capacity Provisioning Problem
3.2.3 Discussion
3.3 Summary
4 The Case of A Single Server
[DELETE]
4.1 Ski-Rental Approach
4.1.1 Offline Solution
4.1.2 Online Solution
4.1.3 Online Solution with Prediction
4.2 Optimal Offline Algorithm
4.3 Deterministic Online Algorithm
4.4 Deterministic Prediction-Aware Online Algorithm
4.5 Randomized Online Algorithm
4.6 Randomized Prediction-Aware Online Algorithm
4.7 Summary
5 The General Case of Multiple Servers
[DELETE]
5.1 Workload Decomposition and Cost Minimization Subproblems
5.1.1 Workload Decomposition Incurs No Optimality Loss Under the Offline Setting
5.1.2 Online Algorithm Design Following the Divide-and-Conquer Approach
5.2 Optimal Offline and Online Algorithms
5.3 Discussions
6 Experimental Studies
[DELETE]
6.1 Settings
6.2 Performance of the Proposed Online Algorithms
6.3 Impact of Prediction Error
6.4 Impact of Peak-to-Mean Ratio (PMR)
6.5 Discussion
7 Conclusion and Extensions
[DELETE]
7.1 Extensions for Practical Datacenters
7.2 Online Algorithms using Machine Learning
7.2.1 Deterministic Online Algorithm
7.2.2 Randomized Online Algorithm
7.2.3 Empirical Evaluation
7.3 Other Online Scheduling Problems
Appendix
