异构多处理机环境下独立任务在线调度研究

Research on Online Scheduling of Independent Tasks in Heterogeneous Multi-Processors Environment

分布式计算系统越来越多地被应用于高性能计算中,面向分布式计算系统的任务调度问题已经证明是一个NP完全问题.基于异构多处理机环境,针对独立任务进行在线任务调度研究.利用一种基于加权最早完成时间的异构多处理机任务调度模型以及相应的任务调度算法(wEFT算法),选择最早完成时间最小或加权链接数最小的处理机执行任务.通过实验证明,对比独立任务调度算法在不同任务数任务调度跨度指标,wEFT算法的性能要明显优于LC算法、wLC算法、RR算法、wRR算法.

Distributed computing systems are increasingly used in high performance computing.Task scheduling for distributed computing systems has proved to be a NP-complete problem.Based on heterogeneous multi-processor environment,this paper studies on-line task scheduling for independent tasks.Using a heterogeneous multi-processor task scheduling model based on weighted earliest completion time and corresponding task scheduling algorithm (wEFT algorithm),the processor with the least earliest completion time or the least number of weighted links is selected to schedule tasks.Experiments show that the performance of wEFT algorithm is better than that of LC algorithm,wLC algorithm,RR algorithm,and wRR algorithm in comparison with task scheduling makespan under different number of tasks.