@inproceedings{grandl2016graphene,
author = {Grandl, Robert and Kandula, Srikanth and Rao, Sriram and Akella, Aditya and Kulkarni, Janardhan (Jana)},
title = {Graphene: Packing and Dependency-aware Scheduling for Data-Parallel Clusters},
organization = {USENIX},
booktitle = {Operating Systems Design and Implementation},
year = {2016},
month = {October},
abstract = {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 online 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%.},
url = {http://approjects.co.za/?big=en-us/research/publication/graphene-packing-dependency-aware-scheduling-data-parallel-clusters/},
}