GRAPHENE: Packing and Dependency-Aware Scheduling for Data-Parallel Clusters


Robert Grandl, Microsoft and University of Wisconsin—Madison; Srikanth Kandula and Sriram Rao, Microsoft; Aditya Akella, Microsoft and University of Wisconsin—Madison; Janardhan Kulkarni, Microsoft


We present a new cluster scheduler, GRAPHENE, aimed at jobs that have a complex dependency structure and heterogeneous resource demands. Relaxing either of these challenges, i.e., scheduling a DAG of homogeneous tasks or an independent set of heterogeneous tasks, leads to NP-hard problems. Reasonable heuristics exist for these simpler problems, but they perform poorly when scheduling heterogeneous DAGs. Our key insights are: (1) focus on the long-running tasks and those with tough-to-pack resource demands, (2) compute a DAG schedule, offline, by first scheduling such troublesome tasks and then scheduling the remaining tasks without violating dependencies. These offline schedules are distilled to a simple precedence order and are enforced by an online component that scales to many jobs. The online component also uses heuristics to compactly pack tasks and to trade-off fairness for faster job completion. Evaluation on a 200-server cluster and using traces of production DAGs at Microsoft, shows that GRAPHENE improves median job completion time by 25% and cluster throughput by 30%.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {199394,
author = {Robert Grandl and Srikanth Kandula and Sriram Rao and Aditya Akella and Janardhan Kulkarni},
title = {{GRAPHENE}: Packing and {Dependency-Aware} Scheduling for {Data-Parallel} Clusters},
booktitle = {12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)},
year = {2016},
isbn = {978-1-931971-33-1},
address = {Savannah, GA},
pages = {81--97},
url = {},
publisher = {USENIX Association},
month = nov

Presentation Audio