引言

随着分布式计算的快速发展 跨多个站点的大型科学计算应用已经变得可行 大规模科学计算在多数情况下需要执行复杂的端到端的工作流程其中伴随着大量的数据移动 计算和资源分配 在异构分布式计算系统中 尤其在这些应用会生成或者需要处理大型数据集时 如何高效地调度这些复杂流程是一个 巨 大 难 题 工作流调度问题首先需要解决任务间 的 依 赖 关 系 每 个 任 务 都 必 须 按 照业务逻辑关系顺序被调度执行 在一个具体时刻系统通常会存在多个就绪任务 如果计算节点的个数少于就绪任务个数 那么这些任务的调度次序就会影响到工作流程的周转时间 同时对于每一个就绪任务同样会有多个与之对应的计算节点 由于网络带宽和计算能力的异构性不同的映射方案也将影响工作流的周转时间

当前工作流调度问题是一个研究热点尤其对于分布式计算而言 为了减少流程周转时间 许多算法 被提 出如 遗 传 算 法 模 拟 退 火 算 法 和 蚁群算法 等 这些算法虽不能保证最优 但能 够 生成一个时间上可以接受的解决方案 在 分 布 式 系统中有研究采用基于 算 法 的 状 态 空 间 搜 索方法来解决 工 作 流 调 度 问 题 该 方 法 假 定 任 务的一些先前通信工作必须在任务执行之前完成也有文献通过放宽这个约束 重新安排任务执行和任务通信顺序以获得最优的调度性能 当 前 的相关算法研究在一定程度上优化了工作流调度算法但还不能有效降低流程周转时间

另外以前的研究假定计算节点应处于执行状态或通信 状 态 任务执行和数据传输二者不能重叠 基于这些 限 制 工 作 流 调 度 问 题 得 以 简 化然而在某些情况下调度结果也不是最优的 计 算节点在执行一个任务的同时接收另外一个任务的输入数据是可行的 并且这些输入数据能够在前一个任务执行完成时间前准备就绪 在此基础上基于 数据 感 知 算 法 通过进一步去除上述约束形成新 的 基 于 的工作流调度改进算法该算法主要特点是允许任务执行和数据处理的重叠操作来减少工作流的周转时间

流程调度问题限定

为了便于算法描述 特对工作流程调度中问题做如下限定和假设任务只有在其获取所有数据之后才能被执行这些数据包括远程数据节点的数据和其先序在计算节点上执行后得到的中间数据每 个 任 务 包 括 两 个 阶 段 一 个 是 计 算 阶段另一个是中间数据传输阶段 一旦任务开始执行直到计算完 成 才 能 停 止 一旦一个中间数据开始传输同样直到该传输完成才能停止只有当任务开始执 行 并且不存在从当前计算节点向指定计算节点进行数据部署时数据部署才立即开始 否则数据部署的请求将被放入等候队列一旦当前任务 完成其计算该计 算 节 点就可以执行另一个就绪任务 任 务 的 计 算 阶段可以与任务 的中间数据传输阶段同时进行我们使用 表 示 任 务 在 计 算 节点 上的执行完成时间 使用 表示节点 与节 点 之间的吞吐量使用 表示任务 与任务 之间的 中 间 数 据 使 用 表 示 从 数 据 节点 上阶段输 入 到 任 务 的 数 据 表 示 从任务 阶段输出到数据节点 的数据算法设计工作流调度问题分析调 度 问 题 实 质 上 是 一 个 带 有 优 先 权 约 束 的 状态空间搜索问题 对于任务而言这些约束可以通过使用拓扑排 序 进 行 实 现 运 用 拓 扑 排 序 得 到 的任务序列并不是唯一的 其他一些已经完成的任务序列也遵守拓扑排序规则 这些符合规范的任务序列 形 成 有 向 无 环 图的一 个 大 拓 扑 树 拓 扑 树 的 深 度 是的任务数树根是第一个可执行任务叶 节 点 是 最后一个可执行任务将工作流程调度映射为一个状态空间首先将根任务分配给所有计算节点 并且检查这种分配的合理性 只有合理的分配被保持以做为进一步的扩展时剩余的叶子任务才会被处理 从任务到计算节点的每一次分配都对应到状态空间的一个节点 状态空间中的每个节点依据合理性约束条件找到拓扑树中的对应节点 并将拓扑树中的子节点分配给所有计算节点 同时将所有这些分配作为子状态空间中节点的子节点 进而检查这些分配的合理性作为下一 步 的 扩 展 重复前面的扩展过程直到找到最优的解决方案的特点算 法 的 特 点 是 将 任 务 执 行 计 算 和 数 据 部 署 操作进行重叠 在以前的研究中 研究人员要么忽略通信成本要么设置一些约束简化这个问题 基于他们的假设当一个计算节点传送或接收数据时该节点将无法执行任何任务 根据这种约束条件很容 易 计 算 出 成 本 函 数 然 而在 许 多 情 况下它并不能保证调度是最优的 此外根据这种约束调度必须考虑到数据传输和任务执行的所有可能次序这将会显著增加搜索空间每个处理器 维护一个与剩余计算节点对应的队列即 和一个与数据节点对应的队列即 当 完成计算任务时对任何任务 将 中 间 数 据传输任 务 插 入 到 队 列 同 样 对 任 何 的 数据 节点 将数据输出任务插入队列 在同一个队列中的数据部署任李 坤 等分布式计算中基于 的工作流调度改进算法研究务会顺次执行同时在不同的队列中的任务可以并行执行 在数据传输过程 计算节点空闲时刻将会执行其他任务实际上实现了任务执行和数据部署的重叠进行启发式函数定义定 义 用 于 表示 中间数据传输的通信时间 其中 分配给了计算节点 分配给了计算节点其中 表示 与 间的直接数据定 义 表示数据 时间其中 分配给了 并且数据存储在远程数据节点定 义 表 示 数 据 传 出时 间其中 分配给了 并且数据上传至远程数据节点 定义 表示 的索引例如 简言之我们得到如下等式表示从开始状态到状态空间中当前状态的部分分配 表示处理器 对 于 的已经明确的处理时间 表示远程数据节点的已经明确的数据传输时 间 是 对 于 分配给处理器 的任务集定义 表示处理器集合 该集合由分配给 前序的处理器构成 而不包括分配给 的处理器定义 表示分配给 处 理 器 的任务集并传输及时数据给定义 表示从 上 的 任 务 中 获 取 或消费及时数据的任务集对应于定义 表示传输 生成数据的最早时间 在基本条件下 我们得到从表达式中得出 传输分配给一个具体计算节点的第一个任务产生数据的最早时间等于任务开始的最早时间和在此节点上任务的执行时间之和这也就意味着第一个任务的数据部署在其执行完成之后就可以立即开始进行对不是第一个分配给计算节点的任务我们得到从表达式得出传输分配给一个计算节点的非第一个任务产生数据的最早时间等于前一个任务的传输完成时间和当前任务的完成时间二者的最大值 当任务已经执行完成 而先前的任务还没有被传输时数据部署将会被放入等待队列 否则数据部署将会立即被执行定义 表示数据节点 集 其 中 数 据 节 点上的数据将会传入计算节点 在 上被调度执行定义 表示任务集其 中 任 务 所 需 数 据需要从远程节点 传入定 义 表 示 从 获 取 数 据的最早时间上述表达式表示从远程节点传入数据的最早时间是前一个任务传入数据的完成时间定义 表示从计算节点 传出数据的数据节点集 其 中 在 计 算 节 点 上 被调度执行定义 表示任务集其中任务产生的直接数据将会从 传出到远程节点定义 表 示 传 出 数 据 到的最早时间那么对于第一个任务 得到于是我们得到了如下的表达式在上式中首先计算时间完成阶段的过程 每计算机工程与科学个任务可能有 多 个 阶 段 的 数 据 将数据传输到这个任务执行前我们需要比较完成的时间阶段这些阶段过程中的数据和获得最新的完成时间 同样对于每一项任务 它可能有多个前辈 这些前辈可能被安排在几个计算节点 在这种情况下我们需要比较完成时间的中间数据传输的所有计算节点获取最新的 完 成 时 间 最早开始时间的任务就是后来的最迟完成时间的阶段 过程和中间数据传输过程在上 式 中对于调度在计算节点上的每个任务结合所有传 出 数 据 节 点 我们需要计算出完成传出处理的最新时间 然后我们计算出每个任务的执行完成时间 比较这两个时间 后者是计算节点明确的周转时间模拟实验算法模拟实验为 了 检 验 在 数 据 感 知 调 度 算 法 中 运 用 重 叠 方案的好处我们实现本文所提算法 并与文献 中所提的最 优 调 度 算 法 简 称 对 状 态 空 间 搜索过程中的周转时间进行了对比 在 模 拟 实 验中我们选择了如图 所示的 结构图图 工 作 流 程 图为了简化模拟操作 对每个计算节点上的每个任务的计算时间做为一个均匀分配 模 拟 实 验 取计算时间的 平 均 值 为 上 下 浮 动 同 样任务之间的中间数据处理也是均匀分配 我 们 考虑 种 情 况其 平 均 值 分 别 为也是上下浮动 图 显 示 了 这 种 情 况下的流程周转时间图 中间数据量对周转时间影响对比为 了 验 证 数 据 感 知 调 度 算 法 中 的 联 合 调 度 策略我们也选择了具有 如 图 所 示 的 结 构 的工作流程 每个任务的计算时间和中间数据量都统一分配为平均值 设 计 阶 段 输 入 和 输 出 的 数据量 为 同 时 考 虑 了网络带宽在数据节点和计算节点之间同构和异构的情况调度算法的模拟实验显示在 同 构 情 况 下使用联合调度算法处理效果不明显 如 图 所 示但在异构情况下 流程运转时间将大大减少如 图所示李 坤 等分布式计算中基于 的工作流调度改进算法研究实验结果分析以 前 的 研 究 都 假 定 计 算 节 点 应 处 于 执 行 状 态或通信状态任务执行和数据传输二者不能重叠论 文 所 提 的 基 于 的工作流调度改进算法该算法主要特 点 是 允 许 任 务 执 行 和数据处理的重叠操作来减少工作流的周转时间 模拟实验将 算法与经典的 算法 进行对比 实验 重点验证两算法在分布式计算中工作流程涉及的每个计算节点上每个任务的计算时间和中间数据量均匀分配情况下对状态空间搜索过程中的周转时间进行的对比 结 果 显 示算法在状态空间搜索中能够较好地处理任务计算和中间数据传输 从而降低工作流程周转时间具体结果如图 所示 实验 和实验 重点验证了论文完善的联合调度策略 模拟实验考虑了网络带宽在数据节点和计算节点之间同构和异构的情况结果显示在异构情况下联合调度策略能够有效协调任务节点计算和中间数据传输之间的流转从而有效降低了工作流程运转时间

结束语

在分布式计算中 工作流程调度直接影响系统的周转时间和运行效 率 在 研 究 基 于 的 工作流调度算法的基础上 论文允许任务重叠执行和数据部署重叠进行 实验结果表明这样做不仅能减少流程 周 转 时 间 同时显著降低算法时间复杂度尤其在异构 网 络 情 况 下 改进算法实现的联合调度方法与现有的调度算法相比流程周转时间将大大减少