异构多核处理器的任务调度算法

doi:10.3778/j.issn.1002-8331.2009.33.017

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (33): 52-56.DOI: 10.3778/j.issn.1002-8331.2009.33.017

异构多核处理器的任务调度算法

蒋建春^1，2，汪同庆¹

1.重庆大学光电技术及系统教育部重点实验室，重庆 400044
2.重庆邮电大学自动化学院，重庆 400065

收稿日期:2009-07-23 修回日期:2009-09-21 出版日期:2009-11-21 发布日期:2009-11-21
通讯作者: 蒋建春

Task scheduling algorithm for heterogeneous multi-core processor

JIANG Jian-chun^1，2，WANG Tong-qing¹

1.Key Lab of Optoelectronic Technique and System of Ministry of Education，Chongqing University，Chongqing 400044，China
2.College of Automation，Chongqing University of Posts and Telecommunications，Chongqing 400065，China

Received:2009-07-23 Revised:2009-09-21 Online:2009-11-21 Published:2009-11-21
Contact: JIANG Jian-chun

摘要/Abstract

摘要： 在研究Min-min、Max-min算法和Sufferage算法基础上，针对异构多核处理器的特点，提出一种任务静态调度算法——自适应分段Sufferage算法（Adaptive Segmented Sufferage，ASS）。该算法以最早完成时间和负载均衡为目标进行任务分配，先将任务分配分成两个阶段：在第一个阶段以最少完成时间作为分配原则进行分配，选择单位时间内节省时间最多的任务先分配；在第二个阶段以负载均衡为分配原则进行分配，选择执行时间大的任务先分配。然后选取不同调节参数，对任务进行多次重新分配，以最小的最大完成时间为最后分配结果，实现自适应调节。通过实验验证，该算法在实现最少完成时间的前提下能很好地达到负载均衡。

关键词: 异构多核处理器, 最少完成时间, 负载均衡, 启发式, 自适应分段Sufferage算法（ASS）

Abstract: After studying the Min-min，Max-min and Sufferage algorithms，this paper presents an Adaptive Segmented Sufferage （ASS） algorithm that can be applied to heterogeneous multi-core processors system，and the goal is to assign optimally tasks to different cores to get the minimal Earliest Finish Time（EFT） and optimal load balancing.At first，the algorithm divides the allocating process into two phases：The first phase，the tasks whose saving time is maximum have priority to be selected to a core in the minimal execution time tasks set on the principle of the minimal EFT；the second phase，as the principle of load balancing, the tasks，which have the maximum execution time in the leavings of the tasks set，will be assigned preferentially.And then，selecting the different adjusting parameters on preceding condition，the tasks are reassigned several times until the finish time is minimal.Simulating results show that the ASS algorithm can achieve the good EFT and load balancing in heterogeneous multi-core processor system.

Key words: heterogeneous multi-core processor, Earliest Finish Time（EFT）, load balancing, heuristic, Adaptive Segmented Sufferage（ASS）

中图分类号:

TP316.4

蒋建春^1，2，汪同庆¹. 异构多核处理器的任务调度算法[J]. 计算机工程与应用, 2009, 45(33): 52-56.

JIANG Jian-chun^1，2，WANG Tong-qing¹. Task scheduling algorithm for heterogeneous multi-core processor[J]. Computer Engineering and Applications, 2009, 45(33): 52-56.

[1]	任春慧，刘升，张伟康，张微微. 柯西变异的骆驼算法优化与应用[J]. 计算机工程与应用, 2021, 57(21): 87-94.
[2]	张呈玲，李进金，林艺东. 基于OE-概念格的形式背景属性约简[J]. 计算机工程与应用, 2021, 57(15): 82-89.
[3]	王保剑，胡大裟，蒋玉明. 改进A*算法在路径规划中的应用[J]. 计算机工程与应用, 2021, 57(12): 243-247.
[4]	肖成龙，聂紫阳，王珊珊. 基于ParetoHeu和实例化失败统计的关联启发式方法[J]. 计算机工程与应用, 2020, 56(5): 57-64.
[5]	袁洋，叶峰，赖乙宗，赵雨亭. 结合负载均衡与A*算法的多AGV路径规划[J]. 计算机工程与应用, 2020, 56(5): 251-256.
[6]	牟恩，张贤勇，姚岳松，邓切. 邻域近似条件熵的特定类属性约简及启发算法[J]. 计算机工程与应用, 2020, 56(24): 175-180.
[7]	何锋，曾文，王秉钧. 并行实时测控数据存储系统设计与实现[J]. 计算机工程与应用, 2020, 56(23): 253-258.
[8]	孟鑫，杨琴，郝婷婷，张洁，曹策俊. 不同订单分配和算法下的拣货路径优化组合[J]. 计算机工程与应用, 2020, 56(23): 229-236.
[9]	李雅丽，王淑琴，陈倩茹，王小钢. 若干新型群智能优化算法的对比研究[J]. 计算机工程与应用, 2020, 56(22): 1-12.
[10]	张孝，孙一铭，吴旭峰. 查询感知的关系-图数据库自适应存储技术研究[J]. 计算机工程与应用, 2020, 56(17): 100-108.
[11]	易成岐，郭鑫，童楠楠，窦悦，陈东，王建冬. 基于启发式社团发现模型的创新态势研判算法[J]. 计算机工程与应用, 2020, 56(15): 74-79.
[12]	王莉，赵阿群，赵晨辉. 基于Fat-Tree的虚拟分片负载均衡算法[J]. 计算机工程与应用, 2020, 56(13): 93-99.
[13]	杨瑶，付克昌，蒋涛，张国良，刘甲甲，孟易. 启发式RRT算法的AGV路径规划[J]. 计算机工程与应用, 2020, 56(12): 125-133.
[14]	胡晓敏，梁天毅，王明丰，李敏. 新型树启发式搜索算法的机器人路径规划[J]. 计算机工程与应用, 2020, 56(11): 164-171.
[15]	秦峰，曾浩，林开东. 高负载场景下基于负载均衡的LLN路由协议[J]. 计算机工程与应用, 2020, 56(1): 121-126.

异构多核处理器的任务调度算法

Task scheduling algorithm for heterogeneous multi-core processor

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics