Online Resource Allocation With Machine Variability: A Bandit Perspective
| Autor: | Jun Guo, Huanle Xu, Wing Cheong Lau, Alex X. Liu, Tiantong Zeng, Yang Liu |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
Computer Networks and Communications Computer science business.industry Big data 020206 networking & telecommunications Regret 02 engineering and technology Computer Science Applications Scheduling (computing) Computer cluster Convex optimization 0202 electrical engineering electronic engineering information engineering Task analysis Resource allocation Resource management Electrical and Electronic Engineering Cluster analysis business Software |
| Zdroj: | IEEE/ACM Transactions on Networking. 28:2243-2256 |
| ISSN: | 1558-2566 1063-6692 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|