1、中文 5900 字 出处： Hunold S, Lepping J. Evolutionary Scheduling of Parallel Tasks Graphs onto Homogeneous ClustersJ. 2011:344-352. 同类 集群 上 并行 任务 图的进化调度 Sascha Hunold， Joachim Lepping 摘要： 当 并行 程序 组合成较大的应用程序时， 任务 图（ PTGs） 出现 ，例如，科学工作流 。 调度 这些 PTGs 到集群上是一个具有挑战性的问题 ， 是由于可塑性任务产生的并行性的附加开销。大多数 算法是 基于这样 的 假设：并行任
2、务 的 执行时间随着处理器的数量增加而增加 。 但是 ， 这假设并不完全通用 ， 因为 如果 处理器的数目是多的内部 使用 的块大小 ， 并行程序的性能经常表现的更好。在这 篇 文章中，我 们介绍了 EMTS 算法 静态 调度 PTGs 到集群上。 我 们应用一种渐进式的方法确定每个 任务分配处理器。进化 调度 策略保证了 EMTS 可以用于任何底层模型 ， 用于预测可塑性任务的执行时间。可以 快速 找到解决方案的目的， EMTS 考虑其它启发式结果（ 例如 ， HCPA， MCPA） 作为 起始解决方案。实验结果 表 明 ， EMTS 显著减少 PTGs 的完成时间 ， 相比其它启发式两个非
3、单调和 单调 递减模式。 关键词 ： 任务 调度 ； 并行 任务 ； 进化 算法；集群 1 概述 科学 工作流是并行 任务图 的一个重要类型，并 在 计算网格上处理。许多 科学工作流仅仅包含几个并行任务 。 然而 ， 正如 Cirne 等人所说，提交给就是那集群的 并行 任务几乎 98%是 可塑性的 。 一个 可塑性 的任务的处理器的数量在执行 之前被确定，并且执行期间保持不变 。 如果 这些 并行 任务 结合起来，并且任务图（ PTGs）出现。 几种 算法 可以表示为 PTGs，如 Strassen 的矩阵乘法和快速 傅里叶 变换（ FFT） 。 一个 PTG 的节点表示计算，边表示数据或控
4、制的以来。执行 PTG 导致混合并行时间调度 ，因为 节点以一种数据并行的 方式 实现，独立的任务可以同时执行。 让 我们以两种矩阵的大小考察 ScaLAPACK并行矩阵 乘法例程 DGEMM的执行时间， 我 们就可以看到 ， 执行时间不单调递减 ， 但大多数的调度算法假设 单调 递减的执行时间模型 。因此 ， 施加 一个非单调 递减 模型 会 导致这些算法 低效的 执行。 出于 这个原因 ， 我们专注于这个问题的进化算法，我们引入算法 EMTS，其可以再任意的执行时间 模型 中使用。我 们 发现， EMTS 相比于其他启发式算法，对于完工时间产生更 好 的时间表现，这适用于非单调和单调递减的
5、执行时间模型。 本文 的 结构 如下 ： 第二章讨论细节问题，并讨论了相关的方法，在第三章中提出进化算法 EMTS，方法和实验的设置在第四章中描述，实验结果将在第五章讨论 和第六章得出结论。 2 问题描述 和相关工作 2.1 应用 和平台模型 一个 PTG 可以 通过 有向 无环图（ DAG） 表示 ，其中节点代表 任务 ，边代表任务的相互依赖性 。 一个 PTG可以 在 通用网络中互联的 P个相同 的处理器上来执行，以使每对处理器进行通信 。 据推测 ， 并行任务的可塑性 ， 即可 由 处理器的任意数量 执行。 2.2 相关 工作 调度 PTGs 的 算法必须取决于（ 1） 有 多少处理器被
6、分配给任务（ 2） 以 该处理器设置任务映射。 大 多数 算法可分为两类： 一步 算法回答这 两 个问题 （分配 和映射） 。 算法 挑选 要执行的下一个任务，确定它的分配 ， 并最终将其映射到平台上 。两步 算法将分配和映射阶段分为两个不用的步骤。 首先 ，所有任务的分配被确定， 第二 ，这些分配被映射到集群，这种 方法 的 优点 是，它比一 步 算法计算少，但是它 产生 的时间调度稍长 。 TSAS 算法是第一类 算法 。 TSAS 使用 凸 规划来解决分配 问题， 这需要很高的计算 成本。通过 最小化 PTG 的 关键路径的长度 CPR 和 CPA 确定处理器分配。几个CPA 的扩展已经提出 ， 因为它提供了计算成本和所 产生 的完工时间之间的良好折中。 大多数 调度算法使用两种不同的模型之一来预测并行 任务 的执行时间。第一是 基于 Downey 的 加速模式，而第二个使用 Amdahl 定律 。 这 两种 模式中，任务的执行时间随着处理器 数量的 增加而减少。 在 Downey 的 模型中，每个任务的 特点是用一个参数
