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

Task scheduling algorithm for heterogeneous multi-core processor

作　　者：蒋建春[1,2] 汪同庆[1] 

机构地区：[1]重庆大学光电技术及系统教育部重点实验室,重庆400044 [2]重庆邮电大学自动化学院,重庆400065

出　　处：《计算机工程与应用》2009年第33期52-56,共5页Computer Engineering and Applications

基　　金：国家科技支撑计划项目No.2007BAG06B06;重庆市教委科学技术研究项目No.KJ090526~~

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

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

分 类 号：TP316.4[自动化与计算机技术—计算机软件与理论]