TY - GEN

T1 - Algorithms for right-sizing heterogeneous data centers

AU - Albers, Susanne

AU - Quedenfeld, Jens

N1 - Publisher Copyright:
© 2021 Owner/Author.

PY - 2021/7/6

Y1 - 2021/7/6

N2 - Power consumption is a dominant and still growing cost factor in data centers. In time periods with low load, the energy consumption can be reduced by powering down unused servers. We resort to a model introduced by Lin, Wierman, Andrew and Thereska (23,24) that considers data centers with identical machines, and generalize it to heterogeneous data centers with d different server types. The operating cost of a server depends on its load and is modeled by an increasing, convex function for each server type. In contrast to earlier work, we consider the discrete setting, where the number of active servers must be integral. Thereby, we seek truly feasible solutions. For homogeneous data centers (d=1), both the offline and the online problem were solved optimally in (3,4) In this paper, we study heterogeneous data centers with general time-dependent operating cost functions. We develop an online algorithm based on a work function approach which achieves a competitive ratio of 2d + 1 + ϵ for any ϵ > 0. For time-independent operating cost functions, the competitive ratio can be reduced to 2d + 1. There is a lower bound of 2d shown in (5), so our algorithm is nearly optimal. For the offline version, we give a graph-based (1+ϵ)-approximation algorithm. Additionally, our offline algorithm is able to handle time-variable data-center sizes.

AB - Power consumption is a dominant and still growing cost factor in data centers. In time periods with low load, the energy consumption can be reduced by powering down unused servers. We resort to a model introduced by Lin, Wierman, Andrew and Thereska (23,24) that considers data centers with identical machines, and generalize it to heterogeneous data centers with d different server types. The operating cost of a server depends on its load and is modeled by an increasing, convex function for each server type. In contrast to earlier work, we consider the discrete setting, where the number of active servers must be integral. Thereby, we seek truly feasible solutions. For homogeneous data centers (d=1), both the offline and the online problem were solved optimally in (3,4) In this paper, we study heterogeneous data centers with general time-dependent operating cost functions. We develop an online algorithm based on a work function approach which achieves a competitive ratio of 2d + 1 + ϵ for any ϵ > 0. For time-independent operating cost functions, the competitive ratio can be reduced to 2d + 1. There is a lower bound of 2d shown in (5), so our algorithm is nearly optimal. For the offline version, we give a graph-based (1+ϵ)-approximation algorithm. Additionally, our offline algorithm is able to handle time-variable data-center sizes.

KW - Approximation algorithm

KW - Competitive analysis

KW - Discrete setting

KW - Energy conservation

KW - Heterogeneous machines

KW - Online algorithm

UR - http://www.scopus.com/inward/record.url?scp=85109517668&partnerID=8YFLogxK

U2 - 10.1145/3409964.3461789

DO - 10.1145/3409964.3461789

M3 - Conference contribution

AN - SCOPUS:85109517668

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 48

EP - 58

BT - SPAA 2021 - Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

T2 - 33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021

Y2 - 6 July 2021 through 8 July 2021

ER -