TY - JOUR

T1 - Algorithms for Right-sizing Heterogeneous Data Centers

AU - Albers, Susanne

AU - Quedenfeld, Jens

N1 - Publisher Copyright:
© 2023 Copyright held by the owner/author(s)

PY - 2023/12/14

Y1 - 2023/12/14

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 References [3, 4]. In this article, we study heterogeneous data centers with general time-dependent operating cost functions. We develop an online algorithm based on a work function approach that 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 Reference [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 References [3, 4]. In this article, we study heterogeneous data centers with general time-dependent operating cost functions. We develop an online algorithm based on a work function approach that 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 Reference [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 - Heterogeneous machines

KW - approximation algorithm

KW - competitive analysis

KW - discrete setting

KW - energy conservation

KW - online algorithm

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

U2 - 10.1145/3595286

DO - 10.1145/3595286

M3 - Article

AN - SCOPUS:85181849191

SN - 2329-4949

VL - 10

JO - ACM Transactions on Parallel Computing

JF - ACM Transactions on Parallel Computing

IS - 4

M1 - 20

ER -