Document Open Access Logo

A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints

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

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.10.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Sungjin Im
Janardhan Kulkarni
Benjamin Moseley
Kamesh Munagala

Cite As Get BibTex

Sungjin Im, Janardhan Kulkarni, Benjamin Moseley, and Kamesh Munagala. A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.10

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

Subject Classification

Keywords
  • Polytope constraints
  • average flow time
  • multi-clusters
  • online scheduling
  • and competitive analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Faraz Ahmad, Srimat T. Chakradhar, Anand Raghunathan, and T. N. Vijaykumar. Tarazu: optimizing mapreduce on heterogeneous clusters. In ASPLOS, pages 61-74. ACM, 2012. URL: http://dx.doi.org/10.1145/2150976.2150984.
  2. Amazon EC2-Spot-Instances. URL: http://aws.amazon.com/ec2/spot-instances/.
  3. Jivitej S. Chadha, Naveen Garg, Amit Kumar, and V. N. Muralidhara. A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation. In STOC, pages 679-684, 2009. Google Scholar
  4. R. Cole, V. Gkatzelis, and G. Goel. Mechanism design for fair division: allocating divisible items without payments. In ACM EC, pages 251-268, 2013. Google Scholar
  5. Jeff Edmonds and Kirk Pruhs. Scalably scheduling processes with arbitrary speedup curves. In ACM-SIAM Symposium on Discrete Algorithms, pages 685-692, 2009. Google Scholar
  6. Kyle Fox, Sungjin Im, and Benjamin Moseley. Energy efficient scheduling of parallelizable jobs. In SODA, pages 948-957, 2013. Google Scholar
  7. N. Garg and A. Kumar. Better algorithms for minimizing average flow-time on related machines. In ICALP (1), 2006. Google Scholar
  8. A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, I. Stoica, and S. Shenker. Dominant resource fairness: Fair allocation of multiple resource types. In NSDI, 2011. Google Scholar
  9. Robert Grandl, Ganesh Ananthanarayanan, Srikanth Kandula, Sriram Rao, and Aditya Akella. Multi-resource packing for cluster schedulers. In ACM SIGCOMM 2014 Conference, SIGCOMM'14, Chicago, IL, USA, August 17-22, 2014, pages 455-466, 2014. URL: http://dx.doi.org/10.1145/2619239.2626334.
  10. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. In STOC, 2014. Google Scholar
  11. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive flow time algorithms for polyhedral scheduling. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 506-524, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.38.
  12. Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, and Kirk Pruhs. Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 531-540, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.63.
  13. Sungjin Im, Benjamin Moseley, and Kirk Pruhs. A tutorial on amortized local competitiveness in online scheduling. SIGACT News, 42(2):83-97, 2011. URL: http://dx.doi.org/10.1145/1998037.1998058.
  14. Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. JACM, 47(4):617-643, 2000. Google Scholar
  15. Gunho Lee, Byung-Gon Chun, and Randy H Katz. Heterogeneity-aware resource allocation and scheduling in the cloud. In Proceedings of the 3rd USENIX Workshop on Hot Topics in Cloud Computing, HotCloud, volume 11, 2011. Google Scholar
  16. J. Nash. The bargaining problem. Econometrica, 18(2):155-162, 1950. Google Scholar
  17. Lucian Popa, Gautam Kumar, Mosharaf Chowdhury, Arvind Krishnamurthy, Sylvia Ratnasamy, and Ion Stoica. Faircloud: sharing the network in cloud computing. In ACM SIGCOMM, pages 187-198, 2012. Google Scholar
  18. Matei Zaharia, Andy Konwinski, Anthony D. Joseph, Randy Katz, and Ion Stoica. Improving mapreduce performance in heterogeneous environments. In OSDI, pages 29-42, Berkeley, CA, USA, 2008. USENIX Association. URL: http://dl.acm.org/citation.cfm?id=1855741.1855744.
  19. S. M. Zahedi and B. C. Lee. REF: resource elasticity fairness with sharing incentives for multiprocessors. In ASPLOS, pages 145-160, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact