Abstract: Aiming at the processors load imbalance problem in shared memory multiprocessor system, this paper provides a new task scheduling algorithm——Multiple Wave Front Method(MWFM). MWFM improves the original Wave Front Method(WFM) by the way of hierarchical scheduling based on dividing the task graphs. It traverses and reallocates task sequences to reduce the error, improves the accuracy of the results of task scheduling by cyclic scheduling algorithm, and gives the implementation of the parallel algorithm. Experimental results prove that the algorithm can significantly reduce errors and improve the efficiency of the parallel systems.

Key words: multi-processor system, task graph, parallel scheduling, load balance

摘要： 针对共享存储多处理机系统中各处理机负载不均衡的问题，提出一种新的任务调度算法——多重波前法。在任务图划分的基础上，采用分层调度方式对原波前法进行改进，通过对任务序列进行多重遍历和重组以降低各处理器的分配误差，利用循环调度算法提高任务调度结果的精度，并给出该算法的并行实现。实验结果证明，该算法具有较低的任务分配误差和较高的系统并行效率。

关键词: 多处理器系统, 任务图, 并行调度, 负载均衡

CLC Number: 

• TP39