一种双匹配动态调度算法

A Both Matched Dynamic Scheduling Algorithm

  • 摘要: 提出了适于异构环境独立任务调度的双匹配动态调度算法(BM算法).BM算法将任务与处理机实现双匹配,使大部分任务在执行时间最短而且完成时间最早的处理机上执行.对于无法实现双匹配的任务,采用最早完成时间最小者优先的策略进行调度.BM算法可以同时满足负载均衡和高吞吐率两个目标.BM算法与通常用作评测基准的Min-min算法的比较结果表明,BM算法的运行时间远少于Min-min算法,其调度跨度比Min-min算法减少约9%.

     

    Abstract: 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%.

     

/

返回文章
返回