多核处理器中任务调度与负载均衡的研究.pdf
版权申诉
13 浏览量
2021-09-25
19:37:21
上传
评论
收藏 323KB PDF 举报
２８卷 第１１期
２０１１年 １１月
微 电 子 学 与 计 算 机
ＭＩＣＲＯＥＬＥＣＴＲＯＮＩＣＳ＆ ＣＯＭＰＵＴＥＲ Ｖｏ１．２８ Ｎｏ．１１
Ｎｏｖｅｍｂｅｒ ２０１ ｌ
多核 处理器 中任 务调度与负载均衡 的研究
彭蔓蔓，黄 亮
（湖南大学 计算机与通信学 院 ，湖南 长沙 ４１００８２）
摘 要：针对多核处理器系统的特点，对任务分配及调度模型进行改进，提高各处理器相对均衡负载度，并在此基
础上提 出一种均衡种群遗传算法（ＢＰＧＡ）．算 法在任务节 点的高度约束条 件下，达到任务 节点在处理核上 随机分
配，而任务节点数均衡分配．采用随机生成图法进行模拟实验，与其他算法相 比，ＢＰＧＡ 算 法有更小 的调度长度 和
较少 的执行 时间．
关键词 ：多核处理器系统 ；任务调度；负载均衡；遗传算法
中图分类号：ＴＰ３１２ 文献标识码：Ａ 文章编号 ：１０ｏ０—７１８０（２０１１）ｌｌ－－００３５－－０５
Ｔａｓｋ Ａｌｌｏｃａｔｉｏｎ ａｎｄ Ｌｏａｄ Ｂａｌａｎｃｅ ｏｎ Ｍ ｕｌｔｉ—ｃｏｒｅ Ｐｒｏｃｅｓｓｏｒｓ
ＰＥＮＧ Ｍ ａｎ－ｍａｎ。ＨＵＡＮＧ Ｌｉａｎｇ
（Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ＆ Ｃｏ ｍｍｕｎｉｃａｔｉｏｎ，Ｈｕｎａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ ４１００８２，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｍｕｌｔｉ－ｃｏｒｅ ｐｒｏｃｅｓｓｏｒ ｓｙｓｔｅｍ，ｔｈｉｓ ｐａｐｅｒ ｉｍｐｒｏｖｅｓ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ ａｎｄ
ｓｃｈｅｄｕｌｉｎｇ ｍｏｄｅｌ ｔＯ ｉｍｐｒｏｖｅ ｔｈｅ ｒｅｌａｔｉｖｅ ｂａｌａｎｃｅ ｏｆ ｔｈｅ ｌｏａｄ ｏｎ ｔｈｅ ｐｒｏｃｅｓｓｏｒｓ，ａｎｄ ｐｕｔｓ ｆｏｒｗａｒｄ ａ ｂａｌａｎｃｅｄ ｐｏｐｕｌａ－
ｔｉｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ （ＢＰＧＡ）．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｕｎｄｅｒ ｔｈｅ ｃｏｎｓｔｒａｉｎｔｓ ｏｆ ｔｈｅ ｈｅｉｇｈｔ ｏｆ ｔａｓｋ ｎｏｄｅｓ ｃａｎ ａｌｌｏｃａｔｅ ｔａｓｋ
ｎｏｄｅｓ ｒａｎｄｏｍ ｌｙ ａｎｄ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｎｏｄｅｓ ｂａｌａｎｃｅｄ ｏｎ ｅａｃｈ ｐｒｏｃｅｓｓｉｎｇ ｃｏｒｅ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ ｕｓｅｄ ｒａｎｄｏｍｌｙ ｇｅｎｅｒａｔｅｄ
ＤＡＧ ｇｒａｐｈ，ｃｏｍｐａｒｅｄ ｗｉｔｈ ｏｔｈｅｒ ａｌｇｏｒｉｔｈｍｓ，ｔｈｅ ＢＰＧＡ ｈａｓ ｌｅｓｓ ｍａｋｅｓｐａｎ ａｎｄ ｌｅｓｓ ｅｘｅｃｕｔｉｏｎ ｔｉｍｅ．
Ｋｅｙ ｗｏｒｄｓ：ｍｕｌｔｉ—ｃｏｒｅ ｐｒｏｃｅｓｓｏｒｓ ｓｙｓｔｅｍ；ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ；ｌｏａｄ ｂａｌａｎｃｉｎｇ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ
１ 引言
随着多核处理器在大规模并行系统 中的应用 ，
计算性能的提高将更多地依赖于处理器核的数量的
增加．为了充分地利用这些数量庞大的处理器核 ，应
用程序 的进程／线程个数也将 比过去多得多．同时 ，
多核处理器也使得系统层次结构变得更为复杂．
任务分配和调度 问题通常被认 为是 ＮＰ～ｃｏｒｎ—
ｐｌｅｔｅ问题［１］．任务调度通常分为静态调度和动态调
度 ；在动态调度 中，事先无法知道任务执行 的信息 ，
根据当前的任务运行情况对任务进行调度 ；而在静
态调度 中，调度方法安排在任务运行之前且无法改
变 ，将一串任务集合分配到指定数 目的处理器上 ，达
到最优的参考标准，例如使得调度长度最小，通信代
价最低及 ＣＰＵ 的利用效率最大化等．目前 ，已有许
收稿日期：２Ｏｌｌ－０１－１８；修回日期：２Ｏ１ｌ～Ｏ２—１５
基金项 目：国家 自然科 学基 金项 目（６０９７３０３０）
多研究者提出了大量 的任务调度算 法，其中主要分
为启发式算法和随机搜索算法 ，启发式算法具有较
高的精确性 ，但 随着问题规模 的扩大将会耗费大量
的时间，典型的如表调度算法 ；随机搜索算法是近来
调度研究 中比较青 睐的方法 ，它具有快速搜索次优
解的特性和执行效率，典型的如遗传算法．
文中主要研究任务的静态调度．首先对文献［２—
３］中任务分配模 型进行改进，综合 考虑复合节点平
均执行时间和进程 间通信代价两个 因素 ，并充分考
虑任务分配的负载均衡性；其次 ，在每个任务子集分
配对应 的处理器后 ，调用均衡 种群遗传算法 （Ｂａｌ—
ａｎｔｅｄ Ｐｏｐｕｌａｔｉｏｎ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，ＢＰＧＡ），该算
法将遗传算法种群采用均衡构造 ，有效地提高了初
始种群的质量 ，做到任务节点随机分配，进一步提高
了处理核间的负载均衡度，为遗传算法提供 了一个
数据资源
- 粉丝: 113
- 资源: 23万+
下载权益
C知道特权
VIP文章
课程特权
VIP享7折，此内容立减4.47元 开通VIP
相关推荐
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0
最新资源