Tight Bounds for Online Vector Scheduling
Tight Bounds for Online Vector Scheduling
复制标题
DOI：
10.1109/focs.2015.39
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
Sungjin Im;Nathaniel Kell;Janardhan Kulkarni;Debmalya Panigrahi
中科院分区：
文献类型：
--
作者：
Sungjin Im;Nathaniel Kell;Janardhan Kulkarni;Debmalya Panigrahi
现代数据中心面临的一个关键挑战是如何有效地服务在线用户请求。这样的请求本质上是多维的，并且其特征在于在多个资源（诸如处理器周期、存储空间和网络带宽）上的需求向量。通常，不同的资源需要不同的目标进行优化，和负载的Lr范数是最流行的目标考虑。此外，服务器集群通常也是异构的，这使得调度问题更具挑战性。为了解决这些问题，我们考虑在线向量调度问题在本文中。由Chekuri和卡纳（SIAM J. of Comp.2006）提出的向量调度是经典负载平衡的推广，其中每个作业具有向量负载而不是标量负载。由Graham在1966年提出的标量问题及其许多变体（相同和不相关的机器，完工时间和Lr范数优化，离线和在线作业等）。在过去的50年里被广泛研究。在本文中，我们解决了在线复杂性的向量调度问题及其重要的推广-所有的Lr规范和在相同和不相关的机器设置。我们的主要结果是：·对于相同的机器，我们通过给出一个在线下界和一个具有渐近匹配竞争比的算法，证明了最优竞争比是Θ（log d/ log log d）。下界是技术上具有挑战性的，并通过一个在线的最小单色团问题的下界，使用一种新的在线着色游戏和随机编码方案。我们的技术也扩展到渐近紧的上限和下限一般Lr规范。·对于不相关的机器，我们通过给出一个与先前已知的上界相匹配的在线下界，证明了最优竞争比是Θ（log m + log d）。然而，与相同的机器不同，将这些结果，特别是上界，推广到一般的Lr规范需要新的想法。特别是，我们使用一个精心构造的潜在功能，平衡个人Lr的目标与整体（convexified）最小最大的目标，以指导在线算法和跟踪潜在的变化，以限制竞争比。
Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multi-dimensional and characterized by demand vectors over multiple resources such as processor cycles, storage space, and network bandwidth. Typically, different resources require different objectives to be optimized, and Lr norms of loads are among the most popular objectives considered. Furthermore, the server clusters are also often heterogeneous making the scheduling problem more challenging. To address these problems, we consider the online vector scheduling problem in this paper. Introduced by Chekuri and Khanna (SIAM J. of Comp. 2006), vector scheduling is a generalization of classical load balancing, where every job has a vector load instead of a scalar load. The scalar problem, introduced by Graham in 1966, and its many variants (identical and unrelated machines, makespan and Lr-norm optimization, offline and online jobs, etc.) have been extensively studied over the last 50 years. In this paper, we resolve the online complexity of the vector scheduling problem and its important generalizations - for all Lr norms and in both the identical and unrelated machines settings. Our main results are: · For identical machines, we show that the optimal competitive ratio is Θ(log d/ log log d) by giving an online lower bound and an algorithm with an asymptotically matching competitive ratio. The lower bound is technically challenging, and is obtained via an online lower bound for the minimum mono-chromatic clique problem using a novel online coloring game and randomized coding scheme. Our techniques also extend to asymptotically tight upper and lower bounds for general Lr norms. · For unrelated machines, we show that the optimal competitive ratio is Θ(log m + log d) by giving an online lower bound that matches a previously known upper bound. Unlike identical machines, however, extending these results, particularly the upper bound, to general Lr norms requires new ideas. In particular, we use a carefully constructed potential function that balances the individual Lr objectives with the overall (convexified) min-max objective to guide the online algorithm and track the changes in potential to bound the competitive ratio.