DAG-Duplication:TDCA 报告

Paper: A Novel Task-Duplication Based Clustering Algorithm for Heterogeneous Computing Environments

解决的问题是什么?为什么重要?有没有作者没注意到的问题?

解决的问题

关注了 Processor 的异构性问题,指出了之前只通过一次任务复制提升调度性能的不足,采用迭代优化进一步降低了 DAG 任务调度的 makespan。

重要性

DAG 调度是强依赖分布式应用调度的理想抽象:一个分布式应用可划分为多个子任务,子任务之间存在依赖关系,且所需资源、执行时间各不相同,在任务拓扑已知,不考虑处理器级并行、节点通信开销等因素的理想状态下,将子任务分配至合适的节点,使应用整体执行时间 makespan 最短。

因此,DAG 调度适用于分布式应用子任务调度的理论研究,可应用于分布式系统、GPU 线性代数计算等领域。

PULL/PUSH 调度策略

PUSH调度

PUSH调度是由调度器主动分发任务到指定的节点。
依据任务找节点

Global Scheduler 源码分析

调度

代码中还是兼容了之前对node-heartbeat的调度方式,同时也提供了对node节点集的调度。

Global调度分为两部分,(1)确定可分配的容器(2)确认分配的容器

确定可分配的容器

在确定可分配容器的过程中,并没有实际分配容器,只是把这种可能记录下来,然后提交给Commiter。该过程大体分为三部分:

  1. 准备节点集。按照当前node的Partition获取所有属于Partition的node
  2. 自顶向下选择APP至Resource Request。与之前最大的区别是,在选择队列或者APP时,需要考虑当前队列是否可以访问当前Partition。
  3. 根据Resource Requset选择Node。首先根据Resource Request对Node进行排序,按照排序结果顺序遍历,直至找到第一个可以完成分配的Node。

确定分配容器

  1. 首先检查是否当前策略中的容器已被处理
  2. 然后从APP开始自底向上检查时候当前策略是否可行
  3. 如果可行,从APP开始自底向上进行分配容器。

Global Scheduler 设计与实现

现有的调度算法

现有调度算法都是基于node-heartbeats。意思是,每一次做调度策略时只针对当前节点,选择针对当前节点的最合适应用的最合适资源请求,没有应用对集群节点的偏好情况。

调度过程就像如下伪代码所示:

1
2
3
4
5
for nodeHeartBeating:
Go to parentQueue
Go to leafQueue
for application in leafQueue.applications:
for resource­request in application.resource­requests

在伪代码中可以直观的看出,在选择应用直至选择资源请求的过程中,没有关注节点的具体信息,在源代码中可以知道,在选择应用的过程中传递的是clusterResource,只在最后判断节点是否能够支持分配,显然可能会做很多无效的工作。

并且,这样每一次心跳分配一次得到的是次优解,而不是最优解,例如:对一个应用而言,根据心跳分配,类似是依次遍历所有节点的过程,再分配过程中,匹配是否可以在当前节点执行,当可以执行时,该应用就被执行了,但是,此时对APP来说,可能不是最优解的情况,并且可能对locality等限制不能很好的满足,而且效率较低。

Global Schedule

思路

改变针对一个节点进行分配的方式,改用针对一组节点分配,并与节点心跳异步。即按照调度策略根据全局信息,选择应用以及资源请求,然后根据资源请求信息,对节点集进行排序,按照排序的结果遍历节点,找到第一个可以分配的节点,然后进行分配。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×