As datacenters start to support a diverse set of applications, there will be a corresponding increase in the heterogeneity of resources (e.g., hardware accelerators) and requirements (e.g., locality, high availability). Heterogeneity significantly increases the difficulty of scheduling to efficiently utilize resources. This is because applications can now run faster or slower on different sets of resources, and they may even have different objectives (Fig. 1). Current cluster schedulers are unable to deal with and even represent this complexity. Schedulers typically assume homogeneity [4, 7] or hard-code specific constraints (e.g., locality) into the scheduler [2, 3, 1]. Alsched [5] proposes the notion of specifying preferences for heterogeneous resources in a flexible manner, but does not consider any temporal aspects of job runtimes and requirements.
We are taking new steps in building a cluster scheduler to handle both the temporal (i.e., how long) and spatial (i.e., which machine) aspects of scheduling on heterogeneous clusters. Our system, TetriSched [6], allows for a wide range of preferences and requirements to be specified through our specification language. Our system automatically translates job specifications in our language into a Mixed Integer Linear Program (MILP), which we optimize with commercial-grade solvers. TetriSched is integrated with the YARN framework and our experimental results demonstrate significant performance improvements over the state-of-the-art, resulting in a best student paper award at EuroSys 2016.
References
- Eric Boutin, Jaliya Ekanayake, Wei Lin, Bing Shi, Jingren Zhou, Zhengping Qian, Ming Wu, and Lidong Zhou. Apollo: Scalable and coordinated scheduling for cloud-scale computing. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pages 285-300, Broomfield, CO, October 2014. USENIX Association.
- Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. Commun. ACM, 51(1):107-113, January 2008.
- Michael Isard, Vijayan Prabhakaran, Jon Currey, Udi Wieder, Kunal Talwar, and Andrew Goldberg. Quincy: Fair scheduling for distributed computing clusters. In Proceedings of the ACM SIGOPS 22Nd Symposium on Operating Systems Principles, SOSP ’09, pages 261-276, New York, NY, USA, 2009. ACM.
- Kay Ousterhout, Patrick Wendell, Matei Zaharia, and Ion Stoica. Sparrow: Distributed, low latency scheduling. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, pages 69-84, New York, NY, USA, 2013. ACM.
- Alexey Tumanov, James Cipar, Michael A. Kozuch, and Gregory R. Ganger. alsched: algebraic scheduling of mixed workloads in heterogeneous clouds. In Proc. of the 3nd ACM Symposium on Cloud Computing, SOCC ’12, 2012.
- Alexey Tumanov, Timothy Zhu, Jun Woo Park, Michael A. Kozuch, Mor Harchol-Balter, and Gregory R. Ganger. TetriSched: Global Rescheduling with Adaptive Plan-ahead in Dynamic Heterogeneous Clusters. In Proceedings of the Eleventh European Conference on Computer Systems, EuroSys ’16, pages 35:1-35:16, New York, NY, USA, 2016. ACM.
- Carl A. Waldspurger and William E. Weihl. Lottery scheduling: Flexible proportional-share resource management. In Proceedings of the 1st USENIX Conference on Operating Systems Design and Implementation, OSDI ’94, Berkeley, CA, USA, 1994. USENIX Association.