DAG-Duplication:TDCA 报告

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

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

解决的问题

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

重要性

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

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

作者没注意的问题

通信是否需要保证接收方任务有条件开始执行

通信时间问题 =300x

该图中,T4、T5 与 T6 存在通信消耗,考虑“通信是否需要接收方任务有条件开始执行”的两种情况,能够产生两个 makespan:

  1. 通信不需要下一任务有条件开始执行,即发送方计算结束后,就可以发送给下一任务所在 Processor,不管下一任务是否可以开始执行。这种情况下,有可能能在下一任务开始执行前,通信结束:1+5+1+1=8
  2. 通信需要下一任务有条件开始执行,即发送方计算结束后,需等待下一任务能够执行后,再发送给下一任务:1+5+1.5+1+1=9.5

使用的什么解决方案?有没有更好的方案

TDCA 将调度分为 5 个阶段:参数计算、任务分组、任务复制、分组合并、任务插入。

参数计算

共计算 6 个参数:通信时间 !$\delta$、最早开始时间 !$est$、最早完成时间 !$ect$、第 r 个合适的处理器 !$fproc$、关键前驱 !$cpred$、任务优先级 !$level$

  • level 采用的 B-level:从当前任务到终点任务考虑通信耗时的最长路径。
  • 递归 cpred 可得到关键前驱路径。

任务分组

任务分组是调度的初始化工作,后续任务复制、分组合并、任务插入都是在此基础上进行优化。

在本文中,主要是以 level 升序为遍历依据(优先级),添加任务主要前驱路径为方法,来完成分组。按照 B-level 的定义,B-level 是距离终点节点的上限时间,因此,level 升序大致与 DAG 层序倒序相当,level 最小的肯定是终点节点,按倒序分配,先将终点节点分配,然后分配距离终点近的任务节点,能够使一个组内的任务尽可能的多,不会造成额外的分组;选中任务节点后,按照节点的关键前驱路径来分组,这是合理且有效的,因为非关键前驱,时间有一定的活动性,而关键前驱对当前任务影响较大,应当优先满足。

Task-scheduling Procedure =400x

第1行:将 Task 数组按照 level 递增顺序排序。
第2行:遍历所有 Task。
第3-7行:从 fproc(i, 1) 至 fproc(i, m) 中寻找 Task(i) 合适的处理器 curProc,并分配。
第8-19行:添加 Task(i) 的前驱任务至当前处理器,优先考虑 cpred,如果 cpred 已被分配,或者在 curProc 的最早完成时间 ect 晚于在最优处理器的 ect 与通信时间的加和,则挑选一个在 curProc 最早完成时间最小的 Task 分配至 curProc,直至没有合适的 Task 或者到达开始 Task。

==问:== 在考虑 8 号不等式时,直接考虑的 Task(j) 最合适的处理器 fproc(j, 1),但是 Task(j) 能有多大可能性分配至该处理器?
答: 文中提到该问题,但没有直接进行证明,而是实验结果显示这种估计是合适的。

任务复制

在该阶段,针对两种情况进行任务复制(一个 Processor 包含的任务集合为 !$X_p=(x_1, x_2, ..., x_k)$):

  1. !$cpred(x_i) \ne x_{i-1}, i \in [2, k]$:将 x~1~-x~i-1~ 转移到合适的 Processor,并将 x~i~ 的关键前驱路径添加到当前 Processor,如果 makespan 减小,则更新。
  2. !$x_1 \ne entry-task$:将 x~1~ 的关键前驱路径添加到当前 Processor,如果 makespan 减小,则更新。

Task-Duplication Procedure =400x

第1行:迭代 K 次,迭代优化
第2行:依次遍历 m 个 Processor,即上一阶段的分组(顺序对结果有影响)
第3行:从后往前遍历组内任务
第4-17行:判断当前任务是否满足第一类情况,如果满足,选择合适的 nextProc 进行复制操作。
第19-22行:判断当前分组是否满足第二类情况,如果满足,进行复制操作。

分组合并

因为在上述两个阶段,都是优先考虑未分配的 Processor,这有可能造成某些任务分配到了极不合理的 Processor 上,通过分组合并,减小因为处理器性能差异太大造成的影响。

Processor-Merging Procedure =400x

完整做法应该是将当前分组 p(=fproc(x, r))与 fproc(x, 1)-fproc(x, r-1)进行合并尝试,为降低计算量,TDCA 只与 fproc(x,1)进行尝试合并,如果合并后 makespan 减小,则更新。

==问:== 为什么只用最后一个任务作比较?
答: 一个分组的最终完成时间是由最后一个任务的完成时间决定的,如果能够将分组移动到最后一个任务的最优处理器上(最优处理器是任务 ect 最小的处理器),意味着这个分组的完成时间都能减小,如果此时 makespan 减小,那么这次分组合并是合适的。

任务插入

在上述阶段中,对每一个分组都是考虑的单一任务链,所以一个任务的多个前驱任务基本不可能存在于同一分组中。任务在等待前驱节点计算或通信时,可能产生空闲 Processor 时间,通过在空闲时间加入合适的前驱任务,如:通信大于计算的任务,可能可以使 makespan 减小。

Task Insertion =400x

本文贡献有哪些?

考虑反应链,提出迭代优化

在 TDCA 中提到,在当前状态下低效的任务复制可能会在另一个复制下变得有效。

这句话的意思是:在当前状态下,进行有效的任务复制进入新的状态,之前没有被采用的低效任务复制,可能在这新的状态中变得有效,即:针对当前状态进行任务复制后的状态,可以再一次进行优化。

因此,TDCA 在进行任务复制时,通过迭代 K 次,来使得 makespan 进一步减小。

详细的实验方案:包括环境、数据和实验步骤

DAG 随机生成器产生不同的 DAG 任务,对子任务数量、通信与计算时间比率(CCR)、层级数和处理器的异构性等方面与其他算法进行比较评估。并对针对任务复制设计实验,分析 K 的取值。

DAG 随机生成器

生成 DAG 任务共分四步:

  1. 在每一层内生成任务节点,第一层和最后一层始终为一个节点
  2. 相邻层的节点之间生成边,保证每个任务至少一个前驱、一个后继
  3. 生成计算耗时(点权),在生成 T(i, p) 时间时,考虑 Processor 异构性,且服从统一分布。
  4. 生成通信耗时(边权),在生成该时间时,考虑通信与计算耗时比率。

比较评估

在该部分,作者进行了两组实验,一组实验是比较各算法在 makespan 上的表现情况,另一组实验是比较各参数对各算法的影响情况。

参数 m 是 Processor 的数量,在实验中,该量等于 DAG 任意两层之间最大边数 maxWidth(G),这保证在任务分组时,不会出现没有空闲 Processor 的情况。

Makespan 比较

作者限制参数在下图范围内,随机生成了 50625 个 DAG 任务,然后使用 TDCA, DCPD, TANH, HEFT 四个算法来计算 makespan,最终以 Rank 的方式描述结果,体现了 TDCA 的优越性。

参数调整范围 =400x

各参数对算法的影响

作者以下表参数为基准,依次调整各个参数(参数范围如上),进行控制变量对比实验,为避免偶然性,作者生成多组样本,计算平均 makespan,以此观察各参数对算法的影响。

基准参数 =300x

任务数量 n

在 30-100 范围内调整 n,计算平均 makespan,绘制折线图,发现各算法都与 n 大致呈线性关系,TDCA 表现最好。

通信计算耗时比率 CCR

在 0-15 范围内调整 CCR,计算平均 makespan,绘制折线图,发现在 0.1-0.3 范围内,各算法表现差异不大,在 0.3-13 TDCA 表现突出,但是在 13 之后,DCPD表现更好。

因此,应根据实际应用情况做出合理判断。

异构性 h

在 0-1.4 范围内调整 h,计算平均 makespan,绘制折线图,发现 TDCA, DCPD, HEFT 大致与 h 成反比,意味着能够比较好的适应异构性,且 TDCA 表现最好。而 TANH 波动较大,不能够处理异构情况。

层数 L

在 30-100 范围内调整 L,计算平均 makespan,绘制折线图,发现各算法都与 L 大致呈线性关系,TDCA 表现最好。

任务复制的分析 ☆

生成各种不同类型的 DAG 任务,记录各 DAG 优化至“最优”需要迭代的次数。实验发现,任务数为 30 时,大多数两轮以内即可优化至最优,当任务数达到 100 时,需要更多的迭代次数。由结果可得,4 轮迭代能够满足 97.48% 的测试用例。

作者还做了另一个非常有价值的实验工作,记录了每一次迭代的优化效果,实验表明,第一次迭代优化效果最佳,能够达到 12%,第二次迭代仅能达到 2%,之后迭代不足 1%,这也从侧面证明了 4 轮迭代是比较合适的。

对控域的任务调度有什么启发

控域内存在多个设备,每个设备都可以发起任务,而 DAG 调度是针对单一强依赖应用进行的内部调度,因此,DAG 调度与控域内任务的总体调度关系不大,但是,与下面几类应用的内部调度关系较大:

  1. 函数式编程语言
  2. FaaS
  3. 大数据处理,如 Spark
  4. 神经网络