文章基本信息

标题：A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints
本地全文：下载
作者：Sungjin Im ; Janardhan Kulkarni ; Benjamin Moseley 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：60
页码：10:1-10:15
DOI：10.4230/LIPIcs.APPROX-RANDOM.2016.10
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Modern data centers consist of a large number of heterogeneous resources such as CPU, memory, network bandwidth, etc. The resources are pooled into clusters for various reasons such as scalability, resource consolidation, and privacy. Clusters are often heterogeneous so that they can better serve jobs with different characteristics submitted from clients. Each job benefits differently depending on how much resource is allocated to the job, which in turn translates to how quickly the job gets completed. In this paper, we formulate this setting, which we term Multi-Cluster Polytope Scheduling (MCPS). In MCPS, a set of n jobs arrive over time to be executed on m clusters. Each cluster i is associated with a polytope P_i, which constrains how fast one can process jobs assigned to the cluster. For MCPS, we seek to optimize the popular objective of minimizing average weighted flow time of jobs in the online setting. We give a constant competitive algorithm with small constant resource augmentation for a large class of polytopes, which capture many interesting problems that arise in practice. Further, our algorithm is non-clairvoyant. Our algorithm and analysis combine and generalize techniques developed in the recent results for the classical unrelated machines scheduling and the polytope scheduling problem [10,12,11].
关键词：Polytope constraints; average flow time; multi-clusters; online scheduling; and competitive analysis