【每周论文】Graphene： Packing and Dependency-aware Scheduling for Data-Parallel Clusters（OSDI 2016）
论文的一作Robert Grandl在OSDI 2016斩获两篇论文，非常的高产，这里先介绍他其中的一篇论文，关于集群调度有关的。
作者提出了一个全新的集群调度器——Graphene，它主要用于调度那些有很复杂的依赖关系和有异构资源需求的作业。
现在的作业执行可以抽象为一个DAG（有向无环图），其中图的点代表要执行的作业，有向的边代表数据的流向（依赖）。调度异构DAG作业或者调度各自独立的异构作业是一个NP难问题，先前的工作大部分使用启发式方法来调度作业，比如着重优化关键路径或者使用贪心算法来最大化资源利用率，但是当它们遇到异构的DAGs时性能就会表现的很差，而本文通关注长作业来挖掘DAG中潜在的并行性来提高整个集群的运行时间和资源利用率。
对一系列的依赖任务，整个调度过程分为两个部分：Offline的离线分析，Online的在线调度。
首先在整个作业集中找出麻烦任务集（Troublesome tasks，那些会运行非常长时间的任务，或者那些很难去pack的任务，如上图的红色），并对其他任务进行打包，将整个DAG分为四部分：麻烦任务（troublesome，T）、父任务（parents，P）、子任务（children，C）和同辈任务（siblings，S） ；之后对四个任务集T、P、C、S在时间-资源的空间上进行放置（如上图右边），首先放置T，之后在T的周围放置其他作业，Graphene选择四种顺序，TSCP、TSPC、TPSC或TCSP，因为作者通过分析发现，只有先方式T任务，才能避免dead-ends（dead-ends的定义是在作业放置的最后存在一些作业不能被放置，除非这些作业能打破依赖）。在离线的情况下对作业进行模拟放置结束后，进行在线调度。下图以两个作业的调度为例，首先分别对Job1和Job2,进行离线的分析，之后根据离线分析的结果对作业进行调度，最下方为Graphene的方法，可以发现它通过作业的并行提高了资源利用率，缩短了作业的执行时间。
