License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.10
URN: urn:nbn:de:0030-drops-66336
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6633/
Go to the corresponding LIPIcs Volume Portal

Im, Sungjin ; Kulkarni, Janardhan ; Moseley, Benjamin ; Munagala, Kamesh

A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints

pdf-format:
LIPIcs-APPROX-RANDOM-2016-10.pdf (0.5 MB)

Abstract

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].

BibTeX - Entry

@InProceedings{im_et_al:LIPIcs:2016:6633,
  author =	{Sungjin Im and Janardhan Kulkarni and Benjamin Moseley and Kamesh Munagala},
  title =	{{A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6633},
  URN =		{urn:nbn:de:0030-drops-66336},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.10},
  annote =	{Keywords: Polytope constraints, average flow time, multi-clusters, online scheduling, and competitive analysis}
}

Keywords: Polytope constraints, average flow time, multi-clusters, online scheduling, and competitive analysis
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI