周期性的多趟可分任务调度算法研究.pdf

第 2 9卷第 2期 2 0 0 7年 2月 系统工 程与 电子技术 S y s t e ms En g i n e e r i n g a n d El e c t r o n i e s Vo 1 2 9 No 2 F e b 2 0 0 7 文章 编号 1 0 0 1 5 0 6 X 2 0 0 7 0 2 0 2 9 4 0 6 周期性的多趟可分任务调度算法研究 尚明生 孙世新 傅 彦 电子科技大学计算机学院 四川 成都 6 1 0 0 5 4 摘 要 基于 可分 任务理论 研 究大规 模计算 中的应用调度 问题 利 用线性规 划得到 了周期 性的 多趟调 度算 法的数学模型 针对同构计算平台进行参数优化 得到如下解析结果 1 在处理机选定的情况下得到优化的调 度趟数 2 在趟数给 定的情 况下得到优 化的处理机 选择 方 法 3 对 于给 定的任 务 得到优 化 的 处理 机选择 方法 和相 应的趟数 仿真结果表 明所得 结果的正确性 关键词 可分任务 理论 周期调度 参数优化 算 法 中图分类号 T P 3 0 1 文献标识码 A Pe r i o d i c mu l t i i n s t a l l me n t a l g o r i t hm f o r di v i s i b l e l o a d s c h e d u l i ng SH ANG M i ng s he n g S U N Shi xi n FU Ya n S c h o o l o f C o mpu t e r Sc i e n c e a n d En g i n e e r i n g Un i v o f El e c t r o n i c Sc i e n c e a n d Te c h n o l o g y o f Ch i n a Ch e n g du 6 1 0 0 5 4 C h i n a Ab s t r a c t To s t u d y l a r g e s c a l e a p p l i c a t i o n s c h e d u l i n g p r o b l e m b a s e d o n d i v i s i b l e l o a d t h e o r y W e b u i l t a n o p t i ma l mo d e l f o r p e r i o d i c mu l t i i n s t a l l me n t a l g o r i t h m b y l i n e a r p r o gr a mmi n g Fo r h o mo g e n e o u s s y s t e ms we d e r i v e c l o s e d f o r m e x p r e s s i o n s o f o p t i ma l p a r a me t e r s An a l y t i c a l s o l u t i o ns a r e p r e s e n t e d a s f o l l o ws 1 f o r a g i v e n n u mb e r o f p r o c e s s o r s o p t i ma l n u mb e r o f i n s t a l l me n t s i s d e r i v e d 2 f o r a g i v e n n u mb e r o f i n s t a l l me n t s t h e o p t i ma l n u mb e r o f p r o c e s s o r s i s o b t a i n e d 3 f o r a g i v e n wo r k l o a d t h e o p t i ma l n u mb e r o f i n v o l v e d p r o c e s s o r s a n d t h e a c c o r d i n g n u mb e r o f i n s t a l l me n t s a r e a c h i e v e d Th e r e s u l t s a r e v e r i f i e d b y s i mu l a t i o ns Ke y wo r ds d i v i s i b l e l o a d s t h e o r y p e r i o d i c s c h e d u l i n g o p t i ma l p a r a me t e r s a l g o r i t h m 0 引 言 近年来 基 于 可分任 务理论 d i v i s i b l e l o a d t h e o r y 的应 用调 度是 一个研 究 热 点 可 分任 务 理论 假设 应 用 能被 划 分为任意粒度的子任务 且各子任务之间相互独立 由于 大多数调度问题都是 NP难题 可分任务理论在模型的精 确性 和 问题 的可 解性 之间取 得 了较好 的折衷 它对 应 于经 典 的主从 计算范 例 可 用 于 刻 画众 多 的 大 规模 计 算 问题 如数据 挖掘 科 学计 算 图像 处 理 大规 模实 验仿 真等 问题 一 可分任务调度存在单趟 o n e i n s t a l l me n t 和多趟 mu l t i i n s t a l l me n t 两种基本策 略 单趟调 度 中 应用被划 分成 和 处理机数 目相等的份数 每个处理机计算一份 由于应用 及其涉及 的数 据需 要 事 先 传 递 到相 应 处 理机 才 能 开始 计 算 而网络通常是互斥访问的 这就使得后续处理机存在空 闲等待时间 对于大规模计算 这样的等待时间是难以接 受的 除了较长的空闲等待时间外 大规模计算还需要较 大通信缓存和较大的主存空间 因此 单趟调度不适合大规 模计算问题 多趟调度 中 应用被划分为大于处理机数 目 的份数 并逐 一发送 给各 处理 机 由 于后 续 处理 机空 闲 等 待时间变短 因而可能缩短整个应用的完成时间 而且 多 趟调度 可以解决大规 模 计算 涉及 的通 信缓 存 处 理机 内存 受 限等 问题 当存在通信启动开销 时 单趟调度存在 的资源 处理 机 选择问题仍然是一个开放 o p e n i n g 问题l 3 相对于单 趟调度 多趟调度显然更加困难 3 除了资源选择问题之 外 多趟任务调 度 的难点 在于确定 趟数 i n s t a l l me n t 的 大小 本文对周期性 的多 趟可分任务调 度算法进行 了研 究 得 到 一 些 有 意 义 的结 果 利 用 线 性 规 划 方 法 提 出 了相应的调度模型 针对同构计算平 台 得到 了如下的 解析的优化结果 1 在处 理机选定 的情况下得 到优化 的 调度 趟数 2 在 趟 数 给定 的 情 况 下 得 到优 化 的 处 理 机选择方法 3 对 于给定 的任务 得到优化 的处理机选 收稿日期 2 0 0 5 1 1 1 1 修 回日期 2 0 0 6一O 8 2 9 基金项 目 国家 自然科学基金项 目 1 0 4 7 6 0 0 6 四川省应用基 础研究项 目资助课题 0 5 J Y0 2 9 0 6 7 2 作者简介 尚明生 1 9 7 3 一 男 博士研究生 主要研究方 向为组合优化和网络并行计算研究 E ma i l ms s h a n g u e s t c e d u c a 维普资讯 第 2 期 尚明生等 周期性 的多趟可分任务 调度算法 研究 择 方法 和相应 的趟 数 l 模型和相关 工作 1 1 调度模 型 调度 问题通 常涉及 应 用模 型 计 算平 台模 型和 目标性 能模型 在应用模型方面 我们考虑可分任务模型 在计算 平台模型方面 我们考虑星型网络计算平台 在性能目标模 型方面 我们考虑应用的最短完成时间 ma k e s p a n 星型网络也称单层树网 在简化情形下等价于总线网 络 是得到广泛研究和实际应用的计算平台 如图 1所示 该计算 平台可记 为一 无 向 图 G一 P L E P i E 0 1 表示 1台处 理机 其 中 称 为主处 理机 i E 1 2 称 为从 处理 机 z L i E 1 2 是连 接 和 的通信链路 假设初始应用全部位于主处理机上 其大小为 假设 户 仅负责将应用划分成子任务 并将这 些子任务调度到各从处理机并行计算 自身并不参与计算 任务的传输和计算存在代价 为意义明确 本文考虑的代价 为计算 通信 时间 传输代价定义为 户 传送大小为 a的 任务给 需要时间为 s g a 其中 s 是通信启动时间 g 是链路 z 的通信速度 带宽 的倒数 主处理机的任务分发 采用 1 p o r t 模型 即通信是串行的 每个时刻只能发送一个 任务 计算代价定义为 处理机 户 计算大小为a的任务需 要代价W a 其中 W 是处理机户 的计算速度的倒数 假设 处理机 在完全接收任务后才能开始计算 计算和通信 不 能重叠 如 果 s g 和 W 都分 别是 常 量 则 称该 平 台是 同构的 否则称为 异构 图 1 星 型 网 络 计 算 平 台 上述模型是大多数研究者所采用的 被认为是较现实 的计算模型 3 显然该模型存在若干变体 例如 可以考 虑让 参与计算 或者通信启动开销 s 0 或者为计算 增加一个启 动开销 或者考虑计算和通信重叠等 由于 s O 被认为是不现实的 而其它几种扩展仅仅 为结果 的表达稍 微复 杂 因此 本文仅 考虑 如上 的基 本模 型 该模 型的另一扩展是考虑初始应用存放在多个处理机 这类似 于 多作业 调度 该 模型 下考 虑 目标 为稳 态 s t e a d y s t a t e 更 恰当 和本文欲解决的 单个 应用调度差别较大 因此不 予 讨论 1 2相关 工作 基 于可分任 务理论 的单趟 调 度 已经 得到 深入 研究 文 献 1 3 7 综述了相应 的研究及其结果 其中 的模型 没有考虑启动开销 因此和本文最接近的综述文献是 3 和 7 除了一些解析表达式之外 对于异构计算单趟调度的 两个 重要 问题 是处理机选择 问题和调度 顺序 问题 然而这 两个问题迄今仍是开放问题 B e a u mo n t 等得到的结果是 带宽受 限 的情况下 大规模 应 用 的渐优 调度 是优 先 选择 通 信链路 最 快 的 处 理 机 并 按 照 带 宽 递 减 的顺 序 进 行 任 务 调度 相对于单趟调度的丰硕成果 多趟调度算法的结果较 少 除一些具体应用涉及的多趟调度思想应用 如文献 8 等 外 本文作者搜索的不同结果仅为文献 4 5 9一l 1 除处理 机选择 问题 和调 度顺 序 外 多趟 调度 的问题 主要 是 确定 优化 的趟数 文献 9 是公认最早的关于可分任务多趟调度算法优 化 的研究 该文 的重要结果 包括 1 给 出了异 构平 台优化的多趟调度数学模型 2 在同构的计算平台中 当 趟数给定时 给出了计算任务完成时间的两种方法 3 给 出了当处理机数 目和趟数趋 于无穷时 的渐进性 能分 析 这 些结果基于如下三个假设 1 从任务开始发送直到任务分 发完毕 通信链路不存在空闲时间 2 任意处理机一旦开 始计算 从计算开始到其所分配的任务计算完成的整个时 间段无空闲时间 对计算和通信不重叠的情况 接收负载的 时间不是空闲时间 3 各处理机同时完成计算 这三个 假设 可使用反证 法进行证 明 文献 9 的结果存在如下局限 1 忽略通信启动开 销 2 解析结 果仅 适合 给定趟 数 时 的同构 平 台 3 不 能 得到优化的趟数 忽略通信启动开销通 常被认为是不现 实的 而且不考虑通 信开销导 致优化趟 数是无穷 大 显然也是不实际的 文献 5 提 出的 X MI 和 UMR算法 考虑了这三个 问题 算法 XMI 通过引入通信启动开销 和 计 算启 动 开销 解 决 问题 1 通过 算 法 UMR解 决 问题 2 和 3 文献 5 中的XMI 算法是对文献 9 的直接扩展的 虽 得 到的一 系列 复 杂递 推关 系 但 思 想方 法 是 完全 一 致 的 该文的 UMR算法借鉴 了循环调度中 F a c t o r i n g算法的思 想 同一趟中每个处理机任务大小相同 为减少第一趟 中 后续处理机的空闲等待时间 文献 5 假设块的大小按照几 何级数增长 同时为保证各处理机同时完成计算 最后一 趟单独考虑以实现负载平衡 正如文献 3 4 所言 该算 法仅仅是技术性的用于解决优化趟数的计算问题 我们认 为该算法在考虑算法的鲁棒性和计算平台动态变化时可能 是有 效的 但 不 是针 对 ma k e s p a n的优 化 实 际 上 假设 块 大小 应逐渐递增 然后 到达一个平 衡 然后 再逐 渐减少块 大 小的思想是有误的 文献 1 O 1 1 均有实例表明 优化调度 中的块大小并 不一定 是 严格 递增 的 而 可 能刚好 相 反 此 外 该文也 没有考虑处理 机选择 问题 考虑到问题的复杂性和实际应用的简单性 文献 4 讨 论 了周期 性 的可分 任务 调度 问题 周 期性 的任 务 调度 中 完成 时间被划 分为若 干相 同 的周期 每个 周期 中的处理 机 数 目 任务分发顺序和任务数量完全相同 文献 5 也可看 维普资讯 2 9 6 系统工程与电子技术 第 2 9卷 作周 期调度 问题 不 过 其周 期 大小 是 变化 的 在周 期 性 的 分 任务多趟调度 中 算 法优化 问题简化为 周期大 小 的优化 以及单个周期内任务调度的优化问题 文献 4 的主要贡 献 在于 当应用非 常庞 大 时 得 到异 构 环境 的渐 优调 度算 法 且考虑了资源选择问题 由于算法严重依赖周期大小 该 文在仿真实验 中提 到几 种确 定周 期 的方 法 其 中 自适应 周 期策略最优 在 自适应 策 略 中 周 期 每次 重新 计算 为余 下 任务 的最优 完成时 间的方根 2 周期性任务调 度算 法 周 期性可分 任务调 度 是非 常 自然 的一 种想 法 它 的优 点在于简单实用 在系统参数变化的情况下 可能自适应 的调 整周期大 小从而具 有 一定 的鲁 棒 性 基 于文 献 4 提 出了周期 性任 务调 度 算法 假设 有 m 个处 理 机参 与 计算 且按 照 P P z P 的顺序调 度任务 处理机 P 的任务 数 量 为 a 周期为 T 则其调度 时序如 图 2 所 示 图 2 非重叠的多趟规则周期 可分负载调度 据此可得周期性可分任务多趟调度算法的线性规划 型 反之 r 越小计算速度相对较快 或者应用属于通信密 模 型 集 型 M i n i mi ze S t 二 s m g T 1 s g 口 口 Tp i 1 2 m 2 一 嘶一V 3 口 0 i 1 2 m 4 T 一 n一 1 T 十 m s g 口 口 5 其 中式 1 表 明通 信链 路 是互 斥 访 问 任 务 发送 是 顺 序 进 行 一个周期内完成所有处理机的一次任务传输 式 2 表 明一个周期内每个处理机完成一趟计算 和通信 且计算和 通信 不重叠 式 3 表明所有任 务全部处 理完 毕 式 4 表 明 全部处理机都参与了计算 式 5 为任务完成时间 显然上述线性规划模型是非常简化的 它依赖于两个 前提 1 处理机选择问题 由于网格计算环境可能存在众 多 符合要求 的处 理机 而 优 化调 度可 能 不是 需要 全部 可 用 的处理机都参与计算 此外 不能要求每一趟都是同样的 处理机参与计算且按照同样的顺序调度 对一般的异构计 算平 台 文献E 4 3 提出 带宽 受 限的处 理 机选 择 策略 即按 照 通信链 路递减 的方 式选 择参 与计 算 的处 理 机 即便 如此 处 理机选择 也 远 未 得 到解 决 2 优 化 的周 期 大小 问题 显然上述线性规划模型严重依赖于周期大小 仅在已知周 期大小才能计算 而不同的周期大小将对完成时间和处理 机 利用造成极 大的影 响 3 同构 平台的算法优化 由于问题的复杂 性 我 们首先考 虑同构 的计算 系统 即 s 一s g 一g 叫 一叫 i 一 1 2 m 其 中 s g和 叫 都 是 常量 为方便 分析 定 义 r 一叫 g 它 表示 通 信 计算 比 r越 大表示通信链路相对计算速度越快 或者应用属计算密集 3 1 优化条件 分析 对周 期任务调 度 显 然参 与计算 的处理 机 不可 能同 时 完成计算 由于存在通信启动开销 显然较大的周期将导 致第一 趟 中编号靠 后 的处 理机 存在 较大 的 空 闲时 间 而 最 后一 趟中 由于 负载不平衡导致 编号靠前 的处理机 存在 较多 的空 闲时间 但较 大 的周期 导 致需要 较 少 的趟数 因而 可 以减少通信启动时间的影 响 另一方面 较少周期可能使 得前述情 况刚好相 反 因此存 在优化 的周期 由于系统 同构 调度 顺序不再 是一个 问题 而处理机 选 择问题简化为确定参与计算的处理机个数 我们不直接计 算周期 大小 而 考虑优 化 的趟数 和参 与计 算 的处 理机 数 目m 一 旦 和 m 确 定 则容 易计算 每 个处 理机 每趟 的任 务 大小 a v ran 周 期 T 可直接计算 得到 由于 ma x s g a 咖 m s g a 若 s g a 咖 表明计算能力相对不足 或者通信能力相对过剩 则通 信链 路将 存 在空 闲 时 间 因而 瓶 颈 在 于 计算 资 源 反 之 若 T 一m s g a 表明计 算能力相 对过剩 或者通信 能 力 相 对 不 足 则 处 理 机 存 在 空 闲时 间 因而 瓶 颈 在 于通 信 资 源 计 算瓶颈 的解 决有三种方 法 1 增 加处 理机 数量 m 2 如果处理机数目固定 则适当减少每次分配的任务数量 该方法等价于增加负载分发趟数 3 如果处理机数 目 和趟数均不变 则需要使用快速的通信链路 即更小的 g 通信瓶颈的解决也有三种方法 1 减少处理机数量 m 2 在处 理机数 目不变的情 况 下 适 当增 加每 次分 配 的任务 数 量 a 该 方法等价 于减 少负载分 发趟数 r t 3 如果处 理机数 目和趟数 不变 则需 要提高计算 速度 即更小 的 叫 因此 在计算速度 和通信速度不变 g的情况下 任 务完成时 间的减少只 能采 取增 加处 理 机数 量 m 或者 处理 机数量不 变的情 况 下 选 择恰 当 的 这正 是 本 文完 成 时 间优化 的基本 思想 维普资讯 第 2期 尚明生等 周期性的多趟可分任务调度算法研究 2 9 7 在非 重叠 的 1 p o r t 模型 中 处理 机必 须完 全接 收本 趟 任务后才能开始计算 在全部任务传送完毕后 处理机还需 计算最后一趟分配的任务 因此完成时间一定大于全部任 务的发送时间 如果通信时间存在空闲 完成时间一定会 变长 因此优化的前提是通信不存在空闲 通信无空闲要 求 s g 口 t c 1d 优 s g a 又由于 d V ran 该条件等 价于 s g m 卟 g 6 n m 另一 个等价 的表达 为 优 r 1 或 者 V 7 注意 到式 7 中的 m r 1仅 与计 算系 统 中的处 理机 个数 m和通信计算比r有关 而和启动时间 s 以及负载大小 V 无关 3 2 m和 l固定 由于处理机数 目和趟数均已指定 对给定任务 每趟任 务数也 固定 完 成时间不存 在优化 的问题 由式 7 可得完 成时 间 f c 优 n 1 c g T一 果 优 l m n s g V w V 其 它 8 如果 s 一s 一0 i 1 2 m式 8 可简化 为 f g V 叫 m r 1 g 叫 r 1 3 3 m 固定 求解 l 很多时候需要考虑处理机数目给定的情况下完成时间 的优化问题 如在集群计算 或者基于 MP P的计算 中 处理 机数 目通常是 已知的 在处 理机 数 目 m 给定 情况下 趟数 n较小时将会导致通信空闲 完成时间受限于计算时间 若 趟数较大将会导致处理机空闲等待任务到来 完成时间受 限 于通 信时 间 因此存在 优化 的负载分发趟数 若 m r 1 则 由式 8 得 T g V 榭 s 叫 一 g V 2 1 o 且 当 n一 ms 1 1 时 取等号 若 re r 1 对给定任务 V 由式 7 知 当 n 叫一 优 一 1 g V m m 1 s 时 完成时间 T受限于通信时间 当趟 数 n w 优一1 g V m m一1 S 时 完 成时 间受 限 于计 算时间 由于通信空闲必然导致任务完成时间增加 因此 趟数 满足 n 一 V 7 Vm m s s I l 优 但任务数量达到一定程度时 上式得到的趟数可能导 致 计算时 间起 支配作用 由于 丁 一 1 s g z 优 一 1 s g 叫 优 2 f 优 一 1 s g 叫 优 且当 一 一1 g re X 时取得最 小值 因此 一m in m a X V m m 一 1 g s V 1 m s f 综上可得 f 7 V 优 1 一 m in m a x 1 I l l S J 1 g 1 S v 7 V 1 2 Y I S 由于式 1 2 得 到的 n可能 不是 整数 一 个简单 的优化 技术 是取式 1 2 计 算结 果 最接 近 的整 数 如计 算结 果 加 上 0 5 后取整 如果 S 一s 一0 i 一1 2 m 显 然 优化 的分配 需 要趟 数 n 一 这 和文献 6 1 是一致 的 相应的完成 时间 r g V m r 1 丁 一 g 叫 v 优 0 处 理机数 目的增加使 得启 动 时间 相应增 加 从 而使 得 完成 时 间变 长 因此存在 优化 的处理 机数 目 而且 处理 机数 目和 任务数量 和计算 平台 的 r 有关 由 于非 重叠 的计 算 中总 是 要等到全部任务通信完毕才能开始最后一块的计算 因此 完成时间一定大于全部任务的通信时间 由式 6 有 优 f gV 一1 1 优 g wV 0 li S li S 解此 不等式 并 由 m 1得 优 二 l l 由式 1 1 知 通 信 受 限 时 最 好 的 处 理 机 数 目 优 一 n s 由于 m是整数 所 以 优一x m s o s g v 干 干丽 2m 其中第一项 中的 0 5是取 和 V V n s 最 接近 的 整数 第 维普资讯 2 9 8 系统工程与电子技术 第 2 9 卷 二项表示不小于最小需求的处理机数的整数 如 果 s 一s O 一1 2 m 由式 1 3 知 固定 时显 然需要 优一 此时一定有 优 r 1 故 T g V 1 5 3 5 m和 l 不 定 下 面考虑处理机 数 目和趟 数均属决 策变量 的情 况 如 果通信链 路不存 在空 闲 由式 6 和 1 1 可得 优 1 w V 一 1 w 而 V一 1 1 6 s g q v 上式表 明 对给 定任务数量 优化 的处理 机个数 取满 足式 1 6 的任意 整数 即可 相应 的趟 数可 由式 1 2 计算 由式 1 0 此 时任务的完成 时间 T g 2 删 1 7 式 1 7 得到的完成时间只与计算平台参数中的带宽 计算 速度 启动时间和任务数量有关 而与处理机数 目和趟数 无关 事实上 由于任务必须传送完毕才能进行计算 因此 任意优化调 度算法 的完成时间 T g 1 8 由此可得 g V 一 c m V 上式表 明 由式 1 6 和式 1 2 得 到 的任 何处 理 机数 目与 趟 数都是渐优的 显然 文献 4 9 中提出的处理机个数 优一r r 1 1 9 可由式 1 6 是 取 一 而 得 但 对 给定 任务 式 1 6 和 1 9 不是等价 的 因此 该文结 果 是本 文处 理 机选 择 问题 的 一 个特例 如果 5 5 0 i 一1 2 优 和文献 9 结果相同 显 然优化的处理机和趟数为 优 一 且 一 2 0 相应的任务 完成时间 由式 1 5 计算 可得 4仿 真 为验证上述结果 我们进行了仿真 由于可分任务可 解析分析 没有必要如文献 4 使用额外的仿真器 根据 4 节的表达式 使用任何编程语言都将得到相同的结果 本文 使 用 VC 编程 实现 如未 特别 说 明 任务 数量 启 动 时 间 网络 速度指标 和计算速度指 标假设如 下 一1 0 0 s 一1 g一1 叫一1 O 因此 通信计算 比 r 一1 O 图 3给出了任务完成时间和处理机数目以及趟数的关 系 由图 3可以看 出 趟数 与处 理 机对 完成 时 间 的影响 明 显不 同 处理机 个数对完成 时间影响 明显 而 趟数 对完成 时 间的影 响相对较小 在处 理 机数 目一 定 的情 况下 较小 的 处 理机数 时趟数对完 成 时间影 响 很小 当处 理机 数 目较 多 时 趟数对完成时间的影响较为明显 趟数越多完成时间越 长 原因在于启动时间的增加 在趟数一定的情况下 随着 处理机数 目的增加 完成时 间快速减少 但 当处 理机 数 目增 加到一定程 度后 完成 时 间开 始增 加 而 这个 转 折点 刚好 是 一f 1 1 l 疗 n 1 n 4 4 n 7 一 n l 0 n l 3 星 譬 假 呶 出 一 所 l m 4 一肼 7 l 1 0 e m 1 3 图 3 不 同处理机数 目和趟数时的任务完成时间 表 1给出 了在 处理机 数 目一定 的情况 下 预 计最 优趟 数和实际最优趟数的对比 其中预测趟数 由 1 2 式计算 实 际最 优趟数 是各 种可 能 趟数 中完 成 时 间最 小值 对 应 的 趟数 表 中给出的预计趟数为实数 由于趟数应该 为整 数 因此实 际使 用时我们 取 和它最接 近 的整数 从 表 1可 以看 出 预测的 趟数 和实际趟 数完全 相 同 由表 1 可 以看 出 随着处理机的增加 趟数相应的减少 文献 4 通过仿 真结 果得 到 趟数 为 3即可 但 这 需 要在 处 理 机较 多 时才 成 立 如果处 理机 数 目较 少 趟 数 必 定增 加 多数 情 况要 大 于 3趟 表 1 处理机数 目一定时预测趟数和实际趟数 z s s s s s s 9 4 s s s 舭s s z 6 4 2 4 3 2 2 6 耄 s s s s s z z 图 4给出了不同任务数量时优化的处理机数 目和趟数 的关 系 由图 4可 以看 出 在处理机数 目一 定时 当处 理机 数 目很小时 优化的趟数相应较大 而且随着处理机数目的 增加 最优的趟数也增加 但当处理机数 目增加到一定程度 时 优 化的 趟数 逐渐 减少 此外 任务 数量 越多 相 应 的趟 数越多 在趟数一定时 随着趟数的增加 优化的处理机数 目逐渐 减少 维普资讯 第 2期 尚明生等 周期性的多趟可分任务调度算法研究 2 9 9 v l 0 0 v 2 0 0 v 3 0 0 v 5 0 0 v l 0 0 一 2 0 0 v 3 O O v 5 0 0 图 4 不同任务数时处理机数 目和趟数 的优化 表 2给 出 了不 同 任务 数 量 时最 优 的处 理机 数 目及 其 趟数 从 表 2可 以看 出 优 化 的处 理 机数 目和趟 数 并 无 一 般 规 律 尽 管 优 化 的 处 理 机 数 目没 有 规 律 但 由 式 1 7 知道 相 应 的完 成 时 间 差 距 很 小 而 这 个 差 距 是 由 于对 处理 机 数 目 和趟 数 取 整 造 成 的 而 且 当 任 务 数 量 较大 时 它 们 都 是 渐 优 的 可 从 表 2得 到 的结 论 是 优 化 的完 成 时 间倾 向 于使 用 较 多 的处 理 机 而 不 是 较 多 的 调度 趟 数 表 2 不同任务数时最优 处理机数 目和趟数 5 总 结 本文讨 论了周期 性 的多 趟可 分 任务 调度 的 优化 同题 对处理机选 择和趟数 确定 等 问题 进行 了 分析 得 到 优化 调 度的条件 针对同构计算平台 得到优化参数的解析表达 式 这些结果是以前研究未曾得到的 我们的结果推广了 相关文献 的研究结果 进一 步的研究包 括 将本 文研 究 结果 推广 到 异构 环境 以及在 实际的应 用 中进行 验 证 由于异 构平 台的 复杂性 不能期 望得到解 析 的优 化参数 表 达式 此外 虽然 可 分任 务的线性规划模型可在多项式时间复杂度内求解 但现实 的计算任务往往是 以整数为单位 而整数规划问题是 NP 难的 因此实际应用中可能存在较高的复杂度 如何简单 性 和现实性之间 取得 较好 的折 衷依然是 一个复杂 问题 参 考 文献 1 3 R o b e r t a z z i T G Te n r e a s o n s t o u s e d i v i s i b l e l o a d t h e o r y J Co mpu t e r 2 0 0 3 3 6 5 6 3 6 8 E z B h a r a d wa j V G h o s e D R o b e r t a z z i T G D i v i s i b l e l o a d t h e o r y A n e w p a r a d i g m f o r l o a d s c h e d u li n g i n d i s t r i b u t e d s y s t e ms J Cl u s t e rCo mpu t i n g 2 0 0 3 6 1 7 1 7 I 3 B e a u mo n t O C a s a n o v a H L e g r a n d A e t a 1 S c h e d u l in g d i v i s i b l e l o a d s o n s t a r a n d t r e e n e t wo r k s Re s u hs a n d o p e n p r o b l e ms l J I EE E T r a n s o n P a r a l l e l a n d Di s t r i b u t e d S y s t e ms 2 0 0 5 1 6 3 2 0 7 2 1 8 4 B e a u mo n t O L e g r a n d A Ro b e r t Y S c h e d u l i n g d i v i s i b l e w o r k l o a d s o n h e t e r o g e n e o u s p l a t f o r ms J P a r a l l e l C o mp u t i n g 2 0 0 3 2 9 1 1 2 1 1 1 5 2 5 Ya n g Ya n g K v a n d e r Ra a d t He n r i C a s a n o v a R o u n d a l g o r i t h ms f o r s c h e d u l i n g d i v i s i b l e l o a d s J I EE E Tr a n s o n P a r a l l e l a n d Di s t r i b u t e d Sy s t e ms 2 0 0 5 1 6 1 1 1 0 9 2 1 1 0 2 6 Ca s a n o v a H Ne t w o r k mo d e l i n g i s s u e s f o r g r i d a p p l i c a t i o n s c h e d u li n g J T h e I n t e r n a t i o n a l J o u r n a l o f F