Online Resource Allocation With Machine Variability: A Bandit Perspective
Online Resource Allocation With Machine Variability: A Bandit Perspective
复制标题
DOI：
10.1109/tnet.2020.3006906
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Huanle Xu;Yang Liu;W. Lau;Tiantong Zeng;Jun Guo;A. Liu
中科院分区：
文献类型：
--
作者：
Huanle Xu;Yang Liu;W. Lau;Tiantong Zeng;Jun Guo;A. Liu
近似作业允许部分执行许多任务以获得有价值的结果，在当今的大规模数据分析中发挥了重要作用。通过为每个近似作业选择适当的调度任务，可以利用这一事实来最大化大数据计算集群的系统效用。然而，这里的一个基本挑战是，机器服务能力在作业的生命周期中可能会有很大的波动，这使得很难将有价值的任务分配给性能良好的机器。此外，集群调度器需要根据机器的可用性在不知道未来作业到达的情况下做出在线调度决策。本文针对并行计算集群中近似作业的在线资源分配问题进行了研究。具体地说，我们将具有不同机器的集群建模为多臂强盗，其中每台机器都被视为一条手臂。通过在平衡勘探与开采权衡的同时对机器服务率进行估计，从强盗的角度设计了一种高效的在线资源分配算法。该算法扩展了已有的在线凸优化技术，并给出了次线性的遗憾界。此外，我们还通过大量的跟踪驱动的仿真来检验所提出的算法的性能，并证明了它的性能大大优于基线。
Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today’s large-scale data analytics. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job’s lifetime, which makes it difficult to assign valuable tasks to well-performing machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially.