Elamur Research⌕
☰
home / papers / 2019 / Themis: Fair and Efficient GPU Cluster Scheduling

Themis: Fair and Efficient GPU Cluster Scheduling

Paper · 2019 · Kshiteej Mahajan, Arjun Balasubramanian, Arjun Singhvi et al.

Summary

Organizations increasingly pool GPUs into shared clusters for ML training, but fair-sharing schedulers built for big-data analytics, such as DRF, handle these workloads poorly. ML jobs hold resources for a long time, must have all their tasks started together (gang scheduling), and run faster or slower depending on how their tasks are placed. The authors studied a production trace from a large internet company and built THEMIS, a two-level scheduler for ML "apps" (groups of related hyper-parameter jobs).

THEMIS introduces finish-time fairness. This metric compares an app's completion time in the shared cluster with its completion time on a private 1/N slice of that cluster. GPUs are leased, and when a lease expires a new auction round begins. The apps that are currently treated least fairly bid for GPU subsets according to their placement preferences, and a central arbiter selects winners using a truthfulness-inducing partial allocation auction. THEMIS runs on Apache YARN 3.2.0. On a replayed trace it improved fairness by more than 2.25X and cluster efficiency by 5–250% over state-of-the-art schedulers.

Key points

  • Trace scale: the analyzed trace covers a GPU cluster with over 5000 users. The study uses a subset of 85 apps submitted through a hyper-parameter tuning framework.
  • App structure: about 10% of apps contain a single job. The rest explore hyper-parameters with up to 100 jobs, with a median of 75.
  • Run lengths: the median app consumes 11.5 GPU days and the median task 3.75 GPU hours. Both are far longer than typical analytics jobs.
  • Fairness metric and auction: finish-time fairness (ρ) is minimized in its worst case across apps. The partial allocation auction is designed to provide Pareto efficiency, envy-freeness and strategy-proofness.
  • Tuning and truthfulness: sensitivity analysis led to a fairness knob of f = 0.8 and a 10-minute lease. In a 64-GPU simulation, an app that misreported its slowdown gained nothing. Once its exaggeration exceeded 34%, it lost a large share of its resources.

Interesting ideas

  • I1. Fairness as relative slowdown. Measuring fairness by how much slower a user finishes compared with owning a fair private slice captures long-term outcomes better than instantaneous resource shares. The same idea suits any shared compute pool, including a common GPU box used by several NLP projects.
  • I2. Bidding limited to the worst-off. Only the apps currently furthest from fair are offered resources. The parameter f then becomes a single dial between fairness and packing efficiency. Setting it too strict (f = 1) backfires because only one app is left to bid.
  • I3. Leases on long-running work. Time-limited leases turn long, non-preemptible training jobs into periodic reallocation points. Shorter leases improve fairness, while longer ones avoid frequent checkpointing, which makes the lease length a clear tunable cost.
  • I4. Losses build priority automatically. An app that loses a round sees its fairness metric worsen, so its later bids rise. This yields long-term fairness without explicit priority bookkeeping, while each individual round can still favor good placement.
  • I5. Testing incentives with a simulated liar. Strategy-proofness is checked empirically by inserting one misreporting agent and sweeping how much it lies. This evaluation pattern transfers to any system that depends on self-reported estimates.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢MicrosoftRedmond · United States378 works · 161,630 citations🎓University of Wisconsin–MadisonMadison · United States54 works · 49,089 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksInformation Systems · 1,730 worksHardware and Architecture · 167 worksComputer Networks and Communications · 100 works

🧭 Topics 2Research subjects and languages the work is about.Bias, fairness & safety · 587 worksGPU & parallel computing · 41 works

Cite

Cite as Kshiteej Mahajan, Arjun Balasubramanian, Arjun Singhvi, Shivaram Venkataraman, Aditya Akella, Amar Phanishayee and Shuchi Chawla. 2019. Themis: Fair and Efficient GPU Cluster Scheduling. arXiv:1907.01484.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1907.01484 · arXiv 1907.01484

@misc{mahajan2019themis,
  title = {{Themis: Fair and Efficient GPU Cluster Scheduling}},
  author = {Kshiteej Mahajan, Arjun Balasubramanian, Arjun Singhvi, Shivaram Venkataraman, Aditya Akella, Amar Phanishayee and Shuchi Chawla},
  year = {2019},
  doi = {10.48550/arxiv.1907.01484},
  eprint = {1907.01484},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1907.01484}
}

References

43 references, 12 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Apache Hadoop NextGen MapReduce (YARN). Retrieved 9/24/2013, URL: http://hadoop.apache.org/docs/current/hadoop-yarn/ hadoop-yarn-site/YARN.html, 2013. ↗
  2. Apache Hadoop Submarine. apache.org/submarine/, 2019. https://hadoop. find
  3. J. Bergstra, B. Komer, C. Eliasmith, D. Yamins, and D. D. Cox. Hyperopt: a python library for model selection and hyperparameter optimization. Computational Science & Discovery, 8(1), 2015. find
  4. J. Chen, X. Pan, R. Monga, S. Bengio, and R. Jozefowicz. Revisiting distributed synchronous sgd. arXiv preprint arXiv:1604.00981, 2016. — [arXiv:1604.00981](https://arxiv.org/abs/1604.00981) find
  5. R. Cole, V. Gkatzelis, and G. Goel. Mechanism design for fair division: allocating divisible items without payments. In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 251–268. ACM, 2013. find
  6. Common Voice Dataset. https://voice.mozilla.org/. ↗
  7. J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009. find
  8. A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In NSDI, 2011. find
  9. D. Golovin, B. Solnik, S. Moitra, G. Kochanski, J. Karro, and D. Sculley. Google vizier: A service for black-box optimization. In KDD, 2017. find
  10. R. Grandl, G. Ananthanarayanan, S. Kandula, S. Rao, and A. Akella. Multi-resource packing for cluster schedulers. ACM SIGCOMM Computer Communication Review, 44(4):455–466, 2015. find
  11. R. Grandl, M. Chowdhury, A. Akella, and G. Ananthanarayanan. Altruistic scheduling in multi-resource clusters. In 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16), pages 65–80, 2016. find
  12. R. Grandl, S. Kandula, S. Rao, A. Akella, and J. Kulkarni. GRAPHENE: Packing and Dependency-Aware Scheduling for Data-Parallel Clusters. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 81–97, 2016. find
  13. J. Gu, M. Chowdhury, K. G. Shin, Y. Zhu, M. Jeon, J. Qian, H. Liu, and C. Guo. Tiresias: A {GPU} cluster manager for distributed deep learning. In 16th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 19), pages 485–500, 2019. find
  14. Gurobi Optimization. http://www.gurobi.com/. ↗
  15. A. Hannun, C. Case, J. Casper, B. Catanzaro, G. Diamos, E. Elsen, R. Prenger, S. Satheesh, S. Sengupta, A. Coates, et al. Deep speech: Scaling up end-to-end speech recognition. arXiv preprint arXiv:1412.5567, 2014.
  16. K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  17. B. Hindman, A. Konwinski, M. Zaharia, A. Ghodsi, A. D. Joseph, R. H. Katz, S. Shenker, and I. Stoica. Mesos: A platform for fine-grained resource sharing in the data center. In NSDI, 2011. find
  18. M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar, and A. Goldberg. Quincy: fair scheduling for distributed computing clusters. In Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles, pages 261–276. ACM, 2009. find
  19. M. Jeon, S. Venkataraman, A. Phanishayee, J. Qian, W. Xiao, and F. Yang. Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads. In USENIX ATC, 2019.
  20. M. Jeon, S. Venkataraman, A. Phanishayee, J. Qian, W. Xiao, and F. Yang. Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads. In USENIX ATC, 2019.
  21. A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097–1105, 2012.
  22. L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. arXiv preprint arXiv:1603.06560, 2016. — [arXiv:1603.06560](https://arxiv.org/abs/1603.06560) find
  23. M. Marcus, B. Santorini, and M. A. Marcinkiewicz. Building a large annotated corpus of english: The penn treebank. 1993.
  24. Microsoft Azure. https://azure.microsoft.com/en-us/. ↗
  25. Microsoft Philly Trace. https://github.com/msr-fiddle/philly-traces, 2019. ↗
  26. A. v. d. Oord, S. Dieleman, H. Zen, K. Simonyan, O. Vinyals, A. Graves, N. Kalchbrenner, A. Senior, and K. Kavukcuoglu. Wavenet: A generative model for raw audio. arXiv preprint arXiv:1609.03499, 2016.
  27. K. Ousterhout, P. Wendell, M. Zaharia, and I. Stoica. Sparrow: distributed, low latency scheduling. In SOSP, pages 69–84, 2013. find
  28. Y. Peng, Y. Bao, Y. Chen, C. Wu, and C. Guo. Optimus: an efficient dynamic resource scheduler for deep learning clusters. In Proceedings of the Thirteenth EuroSys Conference, page 3. ACM, 2018. find
  29. P. Rajpurkar, J. Zhang, K. Lopyrev, and P. Liang. Squad: 100,000+ questions for machine comprehension of text. arXiv preprint arXiv:1606.05250, 2016.
  30. J. Rasley, Y. He, F. Yan, O. Ruwase, and R. Fonseca. Hyperdrive: Exploring hyperparameters with pop scheduling. In Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference, pages 1–13. ACM, 2017. find
  31. M. Schwarzkopf, A. Konwinski, M. Abd-El-Malek, and J. Wilkes. Omega: flexible, scalable schedulers for large compute clusters. In Eurosys, 2013. find
  32. M. Seo, A. Kembhavi, A. Farhadi, and H. Hajishirzi. Bidirectional attention flow for machine comprehension. arXiv preprint arXiv:1611.01603, 2016.
  33. K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
  34. C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2818–2826, 2016. find
  35. H. R. Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63 – 91, 1974. find
  36. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998–6008, 2017.
  37. A. Verma, L. Pedrosa, M. Korupolu, D. Oppenheimer, E. Tune, and J. Wilkes. Large-scale cluster management at google with borg. In Eurosys, 2015. find
  38. WMT16 Dataset. http://www.statmt.org/wmt16/. ↗
  39. Y. Wu, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun, Y. Cao, Q. Gao, K. Macherey, et al. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144, 2016. find
  40. W. Xiao, R. Bhardwaj, R. Ramjee, M. Sivathanu, N. Kwatra, Z. Han, P. Patel, X. Peng, H. Zhao, Q. Zhang, et al. Gandiva: Introspective cluster scheduling for deep learning. In 13th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 18), pages 595–610, 2018. find
  41. J. Yamagishi. English multi-speaker corpus for cstr voice cloning toolkit. URL http://homepages.inf. ed. ac. uk/jyamagis/page3/page58/page58. html, 2012. ↗
  42. W. Zaremba, I. Sutskever, and O. Vinyals. Recurrent neural network regularization. arXiv preprint arXiv:1409.2329, 2014.
  43. H. Zhang, L. Stafman, A. Or, and M. J. Freedman. Slaq: quality-driven scheduling for distributed machine learning. In Proceedings of the 2017 Symposium on Cloud Computing, pages 390–404. ACM, 2017. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/mahajan-2019-themis-fair-efficient-gpu-cluster/