Residential College | false |
Status | 已發表Published |
Optimal Job Scheduling with Resource Packing for Heterogeneous Servers | |
Xu, Huanle1; Liu, Yang1; Lau, Wing Cheong2 | |
2021-08-01 | |
Source Publication | IEEE/ACM Transactions on Networking |
ISSN | 1063-6692 |
Volume | 29Issue:4Pages:1553-1566 |
Abstract | Jobs in modern computing clusters have highly diverse processing duration and heterogeneous resource requirements. In this paper, we consider the problem of job scheduling for a computing cluster comprised of multiple servers with heterogeneous computation resources, while taking the different resource demands of the jobs into account. Our focus is to achieve a low overall job response time for the system (which is also referred to as the job flowtime) while providing fairness between small and large jobs. Since the job flowtime minimization problem under multiple (even homogeneous) servers are known to be NP-hard, we propose an approximation algorithm to tackle the original online scheduling problem by adopting the recently-proposed notion of fractional job flowtime as a surrogate objective for minimization. For the general online job arrival case with multi-dimensional resource requirements, we apply Online Convex Optimization (OCO) techniques to design the corresponding scheduling algorithm with performance guarantees. In the single-dimensional resource setting, we show that the dynamic fit of the online version of our approximate algorithm grows only sublinearly with respect to time and derive a bound for its dynamic regret when comparing to its offline counterpart. While the baseline version of our proposed scheduling algorithm assumes the possibilities of job preemption and job migration across different servers, we show that the extent of job preemption and migration can be well controlled by augmenting the objective function with the corresponding switching costs. |
Keyword | Dynamic Regret Online Convex Optimization Online Job Scheduling Resource Packing Switching Cost |
DOI | 10.1109/TNET.2021.3068201 |
URL | View the original |
Indexed By | SCIE |
Language | 英語English |
WOS Research Area | Computer Science ; Engineering ; Telecommunications |
WOS Subject | Computer Science, Hardware & Architecture ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic ; Telecommunications |
WOS ID | WOS:000685891800012 |
Publisher | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC445 HOES LANE, PISCATAWAY, NJ 08855-4141 |
Scopus ID | 2-s2.0-85103796408 |
Fulltext Access | |
Citation statistics | |
Document Type | Journal article |
Collection | DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE |
Corresponding Author | Xu, Huanle |
Affiliation | 1.Department of Computer and Information Science, University of Macau, Taipa, Macao 2.Department of Information Engineering, The Chinese University of Hong Kong, Hong Kong |
First Author Affilication | University of Macau |
Corresponding Author Affilication | University of Macau |
Recommended Citation GB/T 7714 | Xu, Huanle,Liu, Yang,Lau, Wing Cheong. Optimal Job Scheduling with Resource Packing for Heterogeneous Servers[J]. IEEE/ACM Transactions on Networking, 2021, 29(4), 1553-1566. |
APA | Xu, Huanle., Liu, Yang., & Lau, Wing Cheong (2021). Optimal Job Scheduling with Resource Packing for Heterogeneous Servers. IEEE/ACM Transactions on Networking, 29(4), 1553-1566. |
MLA | Xu, Huanle,et al."Optimal Job Scheduling with Resource Packing for Heterogeneous Servers".IEEE/ACM Transactions on Networking 29.4(2021):1553-1566. |
Files in This Item: | There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment