基于任务图的并行调度MEWFM算法

摘要

随着多核处理器体系结构在计算机领域的广泛应用，如何合理地对计算任务进行调度成为人们广泛讨论的问题。目前已经有针对多处理器的任务调度算法，但是这些算法在执行时要经过多次迭代，执行效率比较低。提出一种改进的波前调度算法MEWFM，它是一种执行时间短，加速比接近处理器核数的一种算法。这种算法主要包括任务图分层，层内调度和误差下降调度三个子算法。详细分析了这些算法的特点和执行流程。实验评测表明，算法在多处理器环境下的任务调度方面具有执行速度快，性能高等优势。%Abatract:With multi-core processor architecture is widely used in the field of computer, how to reasonably distribute computing task scheduling is being discussed. There are multiprocessor task scheduling algorithms, but these algorithms need many iterations when executed, and execution efficiency is low. This paper proposes an improved wavefront WEWFM scheduling algorithms. It is an algorithm of short execution time and speed ratio close to the number of processor cores, mainly including the task graph layer, layer scheduling and error falling scheduling three child algorithms. This paper analyzes in detail the characteristics of these algorithms and implementation process. Experimental evaluation shows the advantage of the algorithm in task scheduling in a multiprocessor environment.