Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (33): 52-56.DOI: 10.3778/j.issn.1002-8331.2009.33.017

• 研究、探讨 • Previous Articles     Next Articles

Task scheduling algorithm for heterogeneous multi-core processor

JIANG Jian-chun1,2,WANG Tong-qing1   

  1. 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

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

蒋建春1,2,汪同庆1   

  1. 1.重庆大学 光电技术及系统教育部重点实验室,重庆 400044
    2.重庆邮电大学 自动化学院,重庆 400065
  • 通讯作者: 蒋建春

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)

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

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

CLC Number: