一种双匹配动态调度算法  

A Both Matched Dynamic Scheduling Algorithm

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

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

出　　处：《信息与控制》2005年第5期532-538,共7页Information and Control

基　　金：国家863计划资助项目(2004AA104340);国家自然科学基金重大研究计划资助项目(90412013);国家杰出青年科学基金资助项目(60125205);上海市科技攻关计划资助项目(03DZ15029)

摘　　要：提出了适于异构环境独立任务调度的双匹配动态调度算法(BM算法).BM算法将任务与处理机实现双匹配,使大部分任务在执行时间最短而且完成时间最早的处理机上执行.对于无法实现双匹配的任务,采用最早完成时间最小者优先的策略进行调度.BM算法可以同时满足负载均衡和高吞吐率两个目标.BM算法与通常用作评测基准的M in-m in算法的比较结果表明,BM算法的运行时间远少于M in-m in算法,其调度跨度比M in-m in算法减少约9%.*This paper presents a new algorithm called both matched （BM） algorithm which is suitable to independent job scheduling on heterogeneous processor platforms. BM algorithm achieves both match between jobs and processes. Most jobs are scheduled to those processes in which the jobs have both minimum execution time （MET） and earliest finish time （EFT）. If both match can not be realized, a job with earliest finish time will be scheduled first. BM algorithm succeeds in load balancing and high throughput. Min-min algorithm is usually used as the benchmark of scheduling algorithms. The experiment data of comparing BM with Min-min algorithms show that the running time of BM algorithm is much less than Min-min algorithm and the makespan of BM algorithm is less than Min-min algorithm by 9%.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]