网格计算中资源负载均衡问题的优化调度模型及其算法.doc

2008 年 3 月Journal on CommunicationsMarch 2008 第 29 卷第 3A 期通 信 学 报Vol 29 No 3A 网格计算中资源负载均衡问题的优化调度模型及其算法 舒万能 中南民族大学 计算机科学学院 湖北 武汉 430074 摘 要 针对网格计算中多个独立任务在多个异构的资源上处理时 资源的负载均衡为最小非抢先调度的问题 建立了一类资源负载均衡问题的优化调度模型 该模型引入了资源的动态负载权值表示方案 并采用量子遗传 模拟退火算法对模型进行求解 该算法采用量子编码来表征染色体 先通过选择 交叉 变异等遗传操作来产 生一组新的个体 然后再独立地对所产生的各个个体进行模拟退火 直到退火温度不能再降低为止 从而求得 问题的最优解 理论分析和实验结果表明这种算法优于其他调度算法 关键词 网格计算 负载均衡 量子遗传模拟退火算法 遗传算法 模拟退火算法 中图分类号 TP393 文献标识码 A 文章编号 1000 436X 2008 3A 0048 06 Optimal scheduling model and its algorithm for resource load balancing problems in grid computing SHU Wan neng College of Computer Science South Central University for Nationalities Wuhan 430074 China Abstract A novel optimal scheduling model and its algorithm were developed for a kind of resource load balancing problems in which many independent tasks should be scheduled many isomerous available resources to make the whole task fulfilled in the shorten time This model introduced dynamic load weight of resource nodes and quantum genetic simulated annealing algorithm was applied to solve the scheduling model By adopting the qubit chromosome as a representation it first generated a new group of individuals through genetic operation such as reproduction crossover mutation etc and than simulated annealing independently all the generated individuals respectively When the temperature in the process of cooling no longer falls the result was the optimal solution on the whole From the analysis and experiment result it concluded that this algorithm was superior to other algorithm Key words grid computing load balancing quantum genetic simulated annealing algorithm genetic algorithm simulated annealing algorithm 1 引言 在网格计算中 任务调度的实质就是将 n 个 相互独立的元任务分配到 m 个异构的资源上 使 得总的任务完成时间最小 资源得到充分的利用 定义为任务 i 的最后完成时间 定义跨度为 X i F 则调度就是在个 max X max X 1 2 i FFin 2m 可能的资源子集空间中寻找最优集 使得跨度 和最小 同时实现网格系统资源 max X F X i F 负载均衡 这是一个 NP 难题 1 不可能找到一个 多项式时间最优算法 因此只能求有效的次最优 算法 收稿日期 2008 01 04 基金项目 国家自然科学基金资助项目 60473085 Foundation Item The National Natural Science Foundation of China 60473085 第 3A 期舒万能 网格计算中资源负载均衡问题的优化调度模型及其算法 49 若实现了网格环境下资源的负载均衡 则不 会出现某个资源负载过重而导致无法继续提交任 务或者负载过轻导致资源闲置的情况 从而有利 于和达到最小这一理想目标 为 max X F X i F 实现网格计算中资源的负载均衡 目前采用的比 较著名的算法有遗传算法 2 4 蚂蚁算法 5 蜂群 算法 6 误差极小化算法 7 遗传模拟退火算法 8 等 但这些算法在问题的描述和处理过程中 没 有考虑到网格计算系统具有可扩展性特征 导致 计算资源的负载权值是动态变化的 因此 本文 引入了动态负载权值计算方案对负载均衡问题进 行描述和建模 并基于量子遗传模拟退火算法给 出了模型的求解方法 2 问题定义 资源负载均衡指在网格计算环境中 通过什 么样的逻辑来保证各个资源节点的计算量与其自 身性能之比尽量相等 从而在提高资源的利用率 基础上 减少整体任务完成时间 为了便于分析 问题 我们特作如下形式化描述 定义 1 假设用四元组表示一 GR Q L D 个网格系统 其中 代表 m 个计 12 m Rr rr 算资源的集合 表示 n 个相互独立 12 n Qq qq 的元任务 表示 m 个资源节点的动 12 m Ll ll 态负载权值 i j D是任务在资源上的执行时间 D i j D i q j r 1 2 1 2 in jm 定义 2 假定资源节点当前的 CPU 利用率 j r 内存利用率 当前网络流量 磁盘 I O 访问率 进 程总数等负载参数分别用 j C j M j N 表示 则资源节点动态负载权值可以 j Io j P j r 表示为 其 12345 jjjjjj lCMNIoP 中 反映各个负载参数的重要程度 1 j j 1 2 jm 定义 3 假设 是一个 m n 矩阵 其元素 表示任务分配到资源节点上 否则 1 i j i q j r 0 i j 定义 4 假定 X 代表调度方案集中的一种 调度策略 则在该策略下 任务的最后完成时 i q 间为 m m 1 1 X ijiji i X j i j Dl F l 是常量 1 2 1 2 in jm 定义 5 网格计算的资源负载均衡问题 就是 以下式为目标函数的最优化问题 1 max max X min X X max X 1 2 min X n i X i i X FF FFin F 其中 为总的任务完成时间 为跨 X F max X F 度 上面的目标函数就是要调整为每个资源节点 分配的任务数 使资源负载均衡 任务完成时间 最小 我们可以利用量子遗传模拟退火 QGSAA quantum genetic simulated annealing algorithm 算法在考虑资源节点现有负载情况的基 础上 求解出最优的预分配方案 3 基于 QGSAA 算法的求解 3 1 染色体编码 在 QGSAA 中 利用量子染色体进行编码 最小的信息单元用量子位表示 量子位又称为量 子比特 一个量子比特的状态可表示为 9 0 1 其中和满足下列归一化条件 22 1 把满足上式的一对复数和称为一个量子比特 的概率幅 因此量子比特可以用概率幅表示为 T在 QGSAA 中 在第 代的染色体种群为 t 为定义如下的染色体 12 ttt M Q tqqq t i q 12 12 coscoscos sinsin sin N t j N ttt q ttt 其中 2 random 0 1 i t rr 为量子染色体的1 2 iN 1 2 jM N 长度 为种群大小 为进化代数 Mt 3 2 适应度函数 模型的目标函数为求最小值问题 需要将其 50 通 信 学 报第 29 卷 转化为求最大值的适应度函数 定义以下惩罚函 数和惩罚系数 为一个较大的正整数 惩 x 罚函数为 x 当时mn 1 1 0 0 n i j j x 其他 当时mn 1 1 1 0 n i j j x 其他 适应度函数可以表示为 1 f xF xx 3 3 选择操作 选择是将父代的个体信息传递到子代 每代 中的每一个个体按照适应度函数的大小决定它能 够复制到下一代的概率 采取 轮盘赌 式的选 择策略 1 计算所有个体的选择概率 其中 f i 分别为个 1 M i P if if i iP 体的选择概率和适应度值 M 为种群规模 t i q 2 随机生成一个数 r random 0 1 3 若 P 0 P 1 P i 1 r P 0 P 1 P i 则个体被选择到下一代 t i q 3 4 变异操作 在量子理论中 各个状态的转移是通过量子 门变换矩阵实现的 在 QGSAA 中 用量子旋转 门的旋转角来表征量子染色体中的变异操作 进 而在变异中加入最优个体的信息 加快算法收敛 下面是本文设计的量子变异算子 10 令 cos sin sin cos U 表示量子旋转门 旋转变异的角度可以参 考文献 10 cos sin sin cos iiiii iii ii U 其中 为量子染色体中第 i 个量子位 T ii 为变异后量子染色体中第 i 个量子位 T ii 3 5 交叉操作 在 QGSAA 中 我们采用全干扰交叉操作 种 群中所有染色体均参与交叉 这种量子交叉可以充 分利用种群中的尽可能多的染色体的信息 改进普 通交叉的局部性与片面性 在种群进化出现早熟时 它能够产生新的个体 给进化过程注入新的动力 这种交叉操作借鉴的是量子的相干性 可以克服普 通染色体在进化后期的早熟现象 表1 列出的是种 群规模为3 染色体长度为5 的一种具体交叉操作 表 1全干扰交叉 个体标号染色体 1A 1 C 2 B 3 A 4 C 5 2 3 B 1 C 1 A 2 B 2 C 3 A 3 B 4 C 4 A 5 B 5 在表 1 中 每个大写字母表示交叉后的一个 新染色体 如 A 1 C 2 B 3 A 4 C 5 3 6 QGSAA 算法的求解过程 本文设计的 QGSAA 算法描述为 1 初始化控制参数 种群大小 100 量M 子染色体长度 9 进化代数 0 交叉概率为Nt 0 85 变异概率为 0 05 初始温度 0 1T 2 初始化种群 Q t 3 由生成 Q t P t 4 评价群体的适应度 用选择操作将当 P t 前最好解用 b 存储 5 用量子旋转门更新 产生新的群 U P t 体 P t 6 对执行选择 交叉操作产生下一代群体 P t P t 7 令 若 1 1 tt TTt M 1tt 0 t T 进化过程结束 输出最优解 b 否则 转到 4 在第 2 步中 12 ttt M Q tqqq 都被初始 12 12 coscoscos sinsin sin N t j N ttt q ttt cos i tsin i t 化为 表明所有可能的线性叠加态以相同的1 2 概率出现 其中 1 2 iN 1 2 jM 第 3A 期舒万能 网格计算中资源负载均衡问题的优化调度模型及其算法 51 在第 3 步中 每个 12 ttt M P txxx 是长度为的串 它 t j x1 2 jM N 12N x xx 是由量子比特幅度或 2 cos i t 2 sin i t1 2 iN 得到的 具体过程如下 随机产生一个数 r random 0 1 若 01r 2 cos i rt 取 1 否则取 0 t j x 4 QGSAA 的可行性分析 1990 年 Eiben 提出 GA 的一种抽象表示 将 进化过程定义为马尔可夫链 利用转移概率矩阵 相乘来进行状态的变换 分析得出 GA 收敛到最 优解的条件 QGSAA 与 GA 类似 仅多出了由 Q 生成和进化 Q 的过程 假设染色体长度为P 种群规模为 对于染色体的取值是离散的N M 0 1 的 GA 种群所在的状态空间大小是 2MN 由于 Q 的取值是连续的 理论上 QGSAA 中种群 所在的状态空间是无限的 但 Q 是有限精度的 设其维数为 则种群所在的状态空间大小为v 算法的状态转换过程可以用如下的 MN v Markov 链来描述 1 Q tP tP tP t Q t Q t 生成变异交叉 保留最优解 更新 算法的整个过程可表示为 1 111 tt C M SU t UF p tt q pq M 1 222 tt qqC M S 其中为维的量子染色体的概率分布 t q1 MN v 向量 均为维的普通染色体的 t p t 1 1 2 MN 概率分布向量 为由量子染色体生成普通染色 q M 体的维的概率转移矩阵 M2 S2均2 MNMN v 2 C 为维随机矩阵 为 MNMN vv 111 C M S U 阶的块对角矩阵 1 1 22 MNMN 设中间种群的规模为 则种群和中间种群 M 所在的状态空间分别为 讨论解空 0 1 MN 0 1 M N 间 为讨论方便 令 此时每一 1 0 1 MN MM 状态均由M 1 个串长N 的个体组成 第一个个体 被成为超个体 状态空间中状态依次为 0 1 MN 中的个体按适应度大小排列为 1 2 0 1 MN N XX 则经过遗传算子的作用 空间 1 2 N xx 中的状态变为状态 1 0 1 MN im xX j x 的概率由矩阵确定 其中 n X 111 PC M S 1 C 分别为块 C M S 组成的块对角矩阵 11 M S2N 1 C C C C 1 M M M M 1 S S S S 由于经算法中的 最优保持 后 如果当前 代产生的最优个体优于超个体 则 用当前最优个 体代替超个体 否则保持不变 所以引入 阶随机矩阵 U 来表示这种升级运 1 1 22 MNMN 算 其中矩阵的每行仅有一个元素为 1 其余U 元素均为 0 它可表示为 2 22 2 11 2122 2 1 L LLL U UU U UUU 则算法的状态转移矩阵为 111 11 2122 2 12 22 2 NNNN PPUC M SU CMSU CMSUCMSU CMSUCMSUCMSU 以上过程均与GA 类似 不同的是 这里的升 级运算U 不仅受P 自身进化过程的影响 而且受到 Q 的作用 当通过新的Q 产生的P 中出现了优于当 前代的超个体的解时 便更新超个体 因为 CMS 为 一正的随机矩阵 由上文可知 为 I 代表 11 U 22 MNMN I 单位阵 是至少有一个对角元素为0 的下三角阵 ii U 则 11 0CMSUCMS 21 2 1 0 N CMSU CMSU 2 2 21 2 1 0 N NN CMSU CMSUCMSU 52 通 信 学 报第 29 卷 与初始分布 12 2 lim 0 0 L n n Pp pp 向量的初值无关 因为已知中前 0 1 0 1 MN 个状态的第一个个体均为取全局最优值的个体2N 若记为 时刻算法处于状态 的概率 并且 1 x t i pti 记为其中适应度最高的个体为的所有状态的集A 1 x 合 则 从而 t ti iA p ffp lim t n p f 1 2 1 N pp 即此时算法是收敛的 f 5 仿真实验与结果分析 基于上述网格资源调度算法 QGSAA 设计了 算法的仿真实验 实验平台由表 2 所示的 3 个高 性能计算资源组成 表 2资源配置 资源名资源类型节点数 资源 1 资源 2 资源 3 Dell PowerEdge 2600 HP Superdome Server SMP HP Rx2600 集群 30 20 20 图 1 为计算资源在QGSAA 算法部署前的负载 统计情况 图2 为该算法部署后 计算资源的负载 统计情况 从图1 可以看出 在网格计算资源优化 调度模型部署前 资源3 由于任务过多导致资源负 载过重 以致于部分网格用户无法继续提交任务 而资源 1 和资源 2 的负载过低 资源没有得到充分 地利用 从图2 可以看出 系统部署后 虽然资源 3 的负载有所降低 但是资源1 和资源 2 的负载有 了很大的提高 从整体上做到了对资源的负载均衡 图 1 QGSAA 算法部署前资源的负载统计 图 2 QGSAA 算法部署后资源的负载统计 图 3 图 4 所示的是算法的静态性能曲线 分 别列举了算法在不同进化代数时所找到的最优解 和时间跨度 图 3 图 4 有效显示了本文 QGSAA 算法有较好的收敛速度和较合理的选择机制 保 证了最好解性能的不降低性 图 3 任务完成时间 m 3 n 50 图 4 任务调度的跨度 m 3 n 50 第 3A 期舒万能 网格计算中资源负载均衡问题的优化调度模型及其算法 53 6 结束语 针对网格计算中资源负载均衡问题建立了调 度模型 并基于量子遗传模拟退火算法给出了模 型的求解办法 在算法的应用过程中 采用量子 比特编码 并在遗传进化过程中 融入模拟退火 的算法 提高了运算效率 参考文献 1 ULLMAN J NP complete scheduling problems J Journal of Computer and System Science 1975 10 2 384 393 2 吴雄奇 曾文华 基于改进遗传算法的网格资源调度算法 J 微电子 学与计算机 2006 23 9 26 28 WU X Q ZENG W H Grid resource scheduling based on improved genetic algorithm J Microelectronics Computer 2006 23 9 26 28 3 林剑柠 吴慧中 基于遗传算法的网格资源调度算法 J 计算机研 究与发展 2004 41 12 2195 2199 LIN J N WU H Z Scheduling in grid computing environment based on genetic algorithm J Journal of Computer Research and Development 2004 41 12 2195 2199 4 YUAN S D XIAO L W Optimal resource allocation on grid systems for maximizing service reliability using a genetic algorithm J Reliability Engineering and System Safety 2006 9 1 1071 1082 5 许智宏 孙济洲 基于蚂蚁算法的网格计算任务调度方法设计 J 天 津大学学报 2004 37 5 414 418 XU Z H SUN J Z An ant algorithm based grid computing and task scheduling J Journal of Tianjin University 2004 37 5 414 418 6 李慧贤 程春田 庞辽军 网格环境下的高效动态任务调度算法 J 华 南理工大学学报 自然科学版 2006 34 1 83 86 LI H X CHENG C T PANG L J High efficiency dynamic task scheduling algorithm for grids J Journal