Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints

被引:20
作者
Im, Sungjin [1 ]
Kulkarni, Janardhan [2 ]
Munagala, Kamesh [3 ]
机构
[1] Univ Calif Merced, Elect Engn & Comp Sci, Merced, CA 95343 USA
[2] Microsoft Res, One Microsoft Way, Redmond, WA 98052 USA
[3] Duke Univ, Comp Sci Dept, Durham, NC 27708 USA
基金
美国国家科学基金会;
关键词
Online scheduling; polytope constraints; total completion time; total flow time; non-clairvoyant; market equilibrium; proportional fairness; adversarial input; PROPORTIONAL FAIRNESS;
D O I
10.1145/3136754
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We introduce and study a general scheduling problem that we term the Polytope Scheduling problem (PSP). In this problem, jobs can have different arrival times and sizes, and the rates assigned by the scheduler to the jobs are subject to arbitrary packing constraints. The PSP framework captures a variety of scheduling problems, including the classical problems of unrelated machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from individual computer architectures to data centers. More concretely, PSP models multidimensional resource requirements and parallelizability, as well as network bandwidth requirements found in data center scheduling. We show a surprising result-there is a single algorithm that is O(1) competitive for all PSP instances when the objective is total completion time, and O(1) competitive for a large sub-class of PSP instances when the objective is total flow time. This algorithm simply uses the well-known Proportional Fairness (PF) algorithm to perform allocations each time instant. Though PF has been extensively studied in the context of maximizing fairness in resource allocation, we present the first analysis in adversarial and general settings for optimizing job latency. Further, PF is non-clairvoyant, meaning that the algorithm doesn't need to know jobs sizes until their completion. We establish our positive results by making novel connections with Economics, in particular, the notions of market clearing, Gross Substitutes, and Eisenberg-Gale markets. We complement these positive results with a negative result: We show that for the total flow time objective, any non-clairvoyant algorithm for general PSP has a strong lower bound on the competitive ratio unless given a poly-logarithmic speed augmentation. This motivates the need to consider sub-classes of PSP when studying flow time. The sub-class for which we obtain positive results not only captures several well-studied models, such as scheduling with speedup curves and related machine scheduling, but also captures as special cases hitherto unstudied scheduling problems, such as single source flow routing, routing multicast (video-on-demand) trees, and resource allocation with substitute resources.
引用
收藏
页数:33
相关论文
共 60 条
[1]   Dissemination-based data delivery using broadcast disks [J].
Acharya, S ;
Franklin, M ;
Zdonik, S .
IEEE PERSONAL COMMUNICATIONS, 1995, 2 (06) :50-60
[2]  
Ahmad Faraz., 2012, ACM SIGARCH Computer Architecture News, V40, P61
[3]   RxW: A scheduling approach for large-scale on-demand data broadcast [J].
Aksoy, D ;
Franklin, M .
IEEE-ACM TRANSACTIONS ON NETWORKING, 1999, 7 (06) :846-860
[4]  
Anand S., 2012, P 23 ANN ACM SIAM S, P1228, DOI 10.1137/1.9781611973099.97
[5]   Primal-Dual and Dual-Fitting Analysis of Online Scheduling Algorithms for Generalized Flow Time Problems [J].
Angelopoulos, Spyros ;
Lucarelli, Giorgio ;
Nguyen, Kim Thang .
ALGORITHMS - ESA 2015, 2015, 9294 :35-46
[6]  
[Anonymous], 2003, COMBINATORIAL OPTIMI
[7]  
[Anonymous], 2011, P 8 USENIX S NETW SY
[8]  
[Anonymous], 2008, 8 USENIX S OP SYST D
[9]  
Azar Y, 2013, PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013), P85
[10]  
Azar Y, 2011, PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1070