Elamur Research⌕
☰
home / papers / 2020 / Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads

Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads

Paper · 2020 · Deepak Narayanan, Keshav Santhanam, Fiodar Kazhamiaka et al.

Summary

Deep learning training clusters now mix accelerators of different generations, and models benefit unequally from newer hardware. Schedulers such as Gandiva, Tiresias and Themis ignore this. The few that account for it (AlloX, Gandiva fair) are each tied to a single objective. The authors build Gavel, a scheduler that turns many standard cluster policies into heterogeneity-aware versions. Examples include least attained service, FIFO, makespan, cost under SLOs, finish-time fairness, shortest job first and hierarchical policies.

Each policy becomes an optimization problem stated in terms of job throughputs. The decision variable is a matrix giving the share of time each job spends on each resource configuration, including space sharing on one GPU. Many of these problems reduce to one or more linear programs. A separate preemptive, round-based mechanism then places jobs so that their actual time shares track the computed allocation. When throughputs are unknown, an online estimator fills them in.

Compared with heterogeneity-agnostic policies, Gavel sustains higher cluster load and improves objectives by up to 3.5× in simulation. This shows that hardware-aware scheduling can raise the value of existing accelerators without restricting which policy an operator chooses.

Key points

  • Speedups across GPU generations vary widely: ResNet-50 runs nearly 10× faster on a V100 than on a K80, while A3C gains only about 2×. Measured per dollar at GCP on-demand prices, the older P100 is often as good or cheaper.
  • In a large-scale simulation, Gavel cuts mean job completion time 3.5×, shortens makespan 2.5× and lowers cost 1.4×. On a smaller physical cluster, gains reach 1.4×.
  • Explicitly modeling space sharing improves objectives by up to 2.2× over Gandiva's ad-hoc colocation.
  • With 6-minute rounds, the scheduling mechanism behaves almost identically to an ideal baseline that grants each job exactly its computed allocation.
  • Jobs in PyTorch or TensorFlow need only small code changes to be moved between devices. Colocated throughputs are estimated with a Quasar-style method that combines profiling and matrix completion against reference models profiled offline.

Interesting ideas

  • I1. Decouple policy from mechanism. One component decides the ideal time fractions, and a separate round-based executor approximates them. This lets new objectives be added without rewriting the placement logic, which suits any shared-resource system, such as a pool of annotation or inference servers.
  • I2. Use effective throughput. A job's speed is defined as the time-weighted average over the mix of resources it receives. This one substitution turns a hardware-blind objective into a hardware-aware one, and the trick carries over to any setting with interchangeable but unequal workers.
  • I3. Recast familiar heuristics as optimization problems. For example, fairness becomes "maximize the minimum scaled throughput," and makespan becomes "minimize the maximum duration." Doing so makes it possible to claim optimality and to compose policies into multi-level hierarchies, such as dividing resources first between departments and then between jobs.
  • I4. Fill in missing measurements with matrix completion. Unknown performance values are inferred from a few profiled reference cases. This is useful wherever exhaustively benchmarking every job–resource pair is too costly.
  • I5. Report results normalized by price, not only raw speed. Ranking hardware by work done per dollar can change which option looks best, which is a useful check for any compute-budgeting decision.

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

🎓Stanford UniversityStanford · United States506 works · 330,052 citations🏢MicrosoftRedmond · United States378 works · 161,630 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

Cite

Cite as Deepak Narayanan, Keshav Santhanam, Fiodar Kazhamiaka, Amar Phanishayee and Matei Zaharia. 2020. Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads. arXiv:2008.09213.

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

@misc{narayanan2020heterogeneity,
  title = {{Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads}},
  author = {Deepak Narayanan, Keshav Santhanam, Fiodar Kazhamiaka, Amar Phanishayee and Matei Zaharia},
  year = {2020},
  doi = {10.48550/arxiv.2008.09213},
  eprint = {2008.09213},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2008.09213}
}

References

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

  1. AWS Accelerator Offerings. https://aws.amazon.com/ec2/instance-types/, 2020. ↗
  2. Cloud GPUs on GCP. https://cloud.google.com/gpu, 2020. ↗
  3. Cloud TPUs on GCP. https://cloud.google.com/tpu, 2020. https://github.com/ ↗
  4. ElasticDL. sql-machine-learning/elasticdl, 2020. find
  5. gRPC. https://grpc.io, 2020. ↗
  6. ImageNet Training in PyTorch. https://github.com/pytorch/examples/tree/master/imagenet, 2020. ↗
  7. Implementing Core Scheduler Functionality in Resource Manager (V1) for Hadoop. https://issues.apache.org/jira/browse/HADOOP-3445, 2020. ↗
  8. Job Scheduling in Spark. https://spark.apache.org/docs/latest/job-scheduling. html\#scheduling-within-an-application, 2020. ↗
  9. Linear-fractional Optimization. http://www.seas.ucla.edu/~vandenbe/ee236a/lectures/lfp.pdf, 2020. ↗
  10. Microsoft Philly Trace. https://github.com/msr-fiddle/philly-traces, 2020. https: ↗
  11. NVIDIA Multi-Process Service. //docs.nvidia.com/deploy/pdf/CUDA_Multi_ Process_Service_Overview.pdf, 2020. find
  12. Word-level Language Modeling RNN. https://github.com/pytorch/examples/tree/master/ word_language_model, 2020. ↗
  13. YARN – The Capacity Scheduler. https://blog.cloudera.com/yarn-capacity-scheduler/, 2020. ↗
  14. M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, et al. TensorFlow: A System for Large-Scale Machine Learning. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 265–283, 2016.
  15. D. Amodei, S. Ananthanarayanan, R. Anubhai, J. Bai, E. Battenberg, C. Case, J. Casper, B. Catanzaro, Q. Cheng, G. Chen, et al. Deep Speech 2: End-to-End Speech Recognition in English and Mandarin. In International Conference on Machine Learning, pages 173–182, 2016.
  16. D. P. Bertsekas and R. G. Gallager. Data Networks. 1987. find
  17. E. Boutin, J. Ekanayake, W. Lin, B. Shi, J. Zhou, Z. Qian, M. Wu, and L. 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, 2014. find
  18. E. J. Candes and Y. Plan. Matrix Completion with Noise. Proceedings of the IEEE, 98(6):925–936, 2010. find
  19. S. Chaudhary, R. Ramjee, M. Sivathanu, N. Kwatra, and S. Viswanatha. Balancing Efficiency and Fairness in Heterogeneous GPU Clusters for Deep Learning. In Proceedings of the Fifteenth European Conference on Computer Systems, pages 1–16, 2020. find
  20. W. Chen, J. Rao, and X. Zhou. Preemptive, Low Latency Datacenter Scheduling via Lightweight Virtualization. In USENIX Annual Technical Conference, USENIX ATC 2017, pages 251–263, 2017. find
  21. C. Coleman, D. Kang, D. Narayanan, L. Nardi, T. Zhao, J. Zhang, P. Bailis, K. Olukotun, C. Ré, and M. Zaharia. Analysis of DAWNBench, A Time-to-Accuracy Machine Learning Performance Benchmark. ACM SIGOPS Operating Systems Review, 53(1):14–25, 2019. find
  22. C. Curino, S. Krishnan, K. Karanasos, S. Rao, G. M. Fumarola, B. Huang, K. Chaliparambil, A. Suresh, Y. Chen, S. Heddaya, et al. Hydra: A Federated Resource Manager for Data-Center Scale Analytics. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), pages 177–192, 2019… find
  23. C. Delimitrou and C. Kozyrakis. Quasar: Resource-Efficient and QoS-Aware Cluster Management. In ACM SIGARCH Computer Architecture News, volume 42, pages 127–144, 2014. find
  24. J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 248– 255, 2009. find
  25. S. Diamond and S. Boyd. CVXPY: A Python-Embedded Modeling Language for Convex Optimization. The Journal of Machine Learning Research, 17(1):2909–2913, 2016. find
  26. D. Elliott, S. Frank, K. Sima’an, and L. Specia. Multi30K: Multilingual English-German Image Descriptions. In Proceedings of the 5th Workshop on Vision and Language, pages 70–74. Association for Computational Linguistics, 2016.
  27. J. Fowers, K. Ovtcharov, M. Papamichael, T. Massengill, M. Liu, D. Lo, S. Alkalay, M. Haselman, L. Adams, M. Ghandi, et al. A Configurable Cloud-Scale DNN Processor for Real-Time AI. In 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA), pages 1–14, 2018. find
  28. A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant Resource Fairness: Fair Allocation of Multiple Resource Types. In 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11), pages 24–24, 2011. find
  29. D. Griffis. RL A3C PyTorch. https://github.com/dgriff777/rl_a3c_pytorch, 2020. ↗
  30. 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
  31. F. M. Harper and J. A. Konstan. The MovieLens Datasets: History and Context. ACM Transactions on Interactive Intelligent Systems (TIIS), 5(4):19, 2016. find
  32. K. He, G. Gkioxari, P. Dollár, and R. Girshick. Mask R-CNN. In Proceedings of the IEEE International Conference on Computer Vision, pages 2961–2969, 2017. find
  33. 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.
  34. 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 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11), pages 22–22, 2011. find
  35. Y.-H. Huang. Attention is All You Need: A PyTorch Implementation. https://github.com/jadore801120/attention-is-all-you-need-pytorch, 2018. ↗
  36. 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 Annual Technical Conference, USENIX ATC 2019, pages 947–960, 2019.
  37. N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers, et al. In-Datacenter Performance Analysis of a Tensor Processing Unit. In 2017 ACM/IEEE 44th Annual International Symposium on Computer Architecture (ISCA), pages 1–12, 2017.
  38. A. Krizhevsky, V. Nair, and G. Hinton. The CIFAR-10 Dataset. online: http://www.cs. toronto. edu/kriz/cifar. html, 55, 2014. ↗
  39. T. N. Le, X. Sun, M. Chowdhury, and Z. Liu. AlloX: Compute Allocation in Hybrid Clusters. In Proceedings of the Fifteenth European Conference on Computer Systems, pages 1–16, 2020. find
  40. E. Linder-Norén. PyTorch-GAN. https://github. com/eriklindernoren/PyTorch-GAN\#cyclegan, 2020. find
  41. K. Liu. Train CIFAR-10 with PyTorch. https://github.com/kuangliu/pytorch-cifar, 2020. ↗
  42. K. Mahajan, A. Balasubramanian, A. Singhvi, S. Venkataraman, A. Akella, A. Phanishayee, and S. Chawla. Themis: Fair and Efficient GPU Cluster Scheduling. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 289–304, 2020.
  43. H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan, Z. Meng, and M. Alizadeh. Learning Scheduling Algorithms for Data Processing Clusters. In Proceedings of the ACM Special Interest Group on Data Communication, pages 270–288. 2019. find
  44. S. Merity, C. Xiong, J. Bradbury, and R. Socher. Pointer Sentinel Mixture Models. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
  45. A. Mnih and R. R. Salakhutdinov. Probabilistic Matrix Factorization. In Advances in Neural Information Processing Systems, pages 1257–1264, 2008. find
  46. V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu. Asynchronous Methods for Deep Reinforcement Learning. In International Conference on Machine Learning, pages 1928–1937, 2016. find
  47. A. Moussawi. Towards Large Scale Training of Autoencoders for Collaborative Filtering. In Proceedings of Late-Breaking Results Track Part of the Twelfth ACM Conference on Recommender Systems, RecSys’18, Vancouver, BC, Canada, 2018. find
  48. D. Narayanan, A. Harlap, A. Phanishayee, V. Seshadri, N. R. Devanur, G. R. Ganger, P. B. Gibbons, and M. Zaharia. PipeDream: Generalized Pipeline Parallelism for DNN Training. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pages 1–15, 2019. find
  49. D. Narayanan, K. Santhanam, A. Phanishayee, and M. Zaharia. Accelerating Deep Learning Workloads through Efficient Multi-Model Execution. In NeurIPS Workshop on Systems for Machine Learning (December 2018), 2018. find
  50. A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems, pages 8024–8035, 2019.
  51. B. Radunovic and J.-Y. Le Boudec. A Unified Framework for Max-Min and Min-Max Fairness with Applications. IEEE/ACM Transactions on Networking, 15(5):1073–1083, 2007. find
  52. M. Schwarzkopf, A. Konwinski, M. Abd-El-Malek, and J. Wilkes. Omega: Flexible, Scalable Schedulers for Large Compute Clusters. In Proceedings of the 8th ACM European Conference on Computer Systems, pages 351–364, 2013. find
  53. M. J. Shafiee, B. Chywl, F. Li, and A. Wong. Fast YOLO: A Fast You Only Look Once System for Real-Time Embedded Object Detection in Video. arXiv preprint arXiv:1709.05943, 2017. find
  54. P. Sinha and A. A. Zoltners. The Multiple-Choice Knapsack Problem. Operations Research, 27(3):503–515, 1979. find
  55. X. Sun, T. N. Le, M. Chowdhury, and Z. Liu. Fair Allocation of Heterogeneous and Interchangeable Resources. ACM SIGMETRICS Performance Evaluation Review, 46(2):21–23, 2019. find
  56. A. Tumanov, T. Zhu, J. W. Park, M. A. Kozuch, M. Harchol-Balter, and G. R. Ganger. Tetrisched: Global Rescheduling with Adaptive Plan-Ahead in Dynamic Heterogeneous Clusters. In Proceedings of the Eleventh European Conference on Computer Systems, page 35. ACM, 2016. find
  57. 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.
  58. V. K. Vavilapalli, A. C. Murthy, C. Douglas, S. Agarwal, M. Konar, R. Evans, T. Graves, J. Lowe, H. Shah, S. Seth, et al. Apache Hadoop YARN: Yet Another Resource Negotiator. In Proceedings of the 4th Annual Symposium on Cloud Computing, page 5. ACM, 2013. find
  59. A. Verma, L. Pedrosa, M. Korupolu, D. Oppenheimer, E. Tune, and J. Wilkes. Large-scale Cluster Management at Google with Borg. In Proceedings of the Tenth European Conference on Computer Systems, page 18, 2015. find
  60. 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
  61. M. Zaharia, D. Borthakur, J. Sen Sarma, K. Elmeleegy, S. Shenker, and I. Stoica. Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling. In Proceedings of the 5th European Conference on Computer Systems, pages 265–278. ACM, 2010. find
  62. J.-Y. Zhu, T. Park, P. Isola, and A. A. Efros. Unpaired Image-to-Image Translation using Cycle-Consistent Adversarial Networks. In Proceedings of the IEEE International Conference on Computer Vision, pages 2223– 2232, 2017. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/narayanan-2020-heterogeneity-aware-cluster-scheduling-policies/