一种适于异构环境的任务调度算法  

A Scheduling Algorithm Suitable for Heterogeneous Computing Environment

作　　者：支青[1] 蒋昌俊[1] 

机构地区：[1]同济大学计算机科学与工程系

出　　处：《自动化学报》2005年第6期865-872,共8页Acta Automatica Sinica

基　　金：国家高技术研究发展计划(863)(2004AA104340);国家重点基础研究发展规划(973)(2003CB316902);国家自然科学基金重大研究计划(90412013);国家杰出青年科学基金(60125205);上海科技攻关研究项目(03DZ15029)资助

摘　　要：针对异构环境独立任务调度问题提出两个调度原则,并基于Min-min算法提出优先级最小最早完成时间算法(Prioritymin-min,PMM).该算法将任务在各处理机上执行时间的标准误差作为任务的优先级.选取最早完成时间较小的k个任务,优先调度其中优先级最高的一个.在实验基础上分析了参数k对PMM算法性能的影响.PMM算法克服了min-min算法单纯追求局部最优的局限性,更适合于异构环境.实验数据表明PMM算法能有效地降低调度跨度,其性能比min-min算法有明显提高.This paper presents two scheduling principles suitable to independent job scheduling in heterogeneous computing environment. A new algorithm named Priority Min-min （PMM） is presented, which computes jobs＇ priorities based on their standard deviation of execution time. PMM chooses k jobs which have smaller earliest finish times, and assigns the job with the highest priority to the corresponding processor. This paper analyses how k influences the performance of PMM by experiment. PMM is more suitable for heterogeneous processor platforms by surmounting the limitation of Min-min. The experimental data show that PMM reduces the makespan effectively and its performance is much better than Min-min.

关 键 词：调度 最早完成时间 最少执行时间 调度跨度 标准误差 

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