粗粒度并行任务的动态调度算法(PTDS)及其有效性证明

A DYNAMIC SCHEDULING ALGORITHM(PTDS) OF COARSE GRAIN PARALLEL TASKS AND ITS EFFECTIVENESS

本文揭示和探讨了并行多机系统中粗粒度并行任务的时间变化对静态任务调度机制的影响,给出了基于预调度的粗粒度并行任务的动态调度算法PTDS,并且严格地定义和证明了PTDS算法的有效性.结果表明PTDS通过局部调整预调度方案,能够有效地获得近似最优的计算任务调度方案.

In this paper, effects of coarse-grain task computing time variation in parallel multiprocessor systems are revealed and discussed in detail. A dynamic coarse grain task scheduling algorithm (PTDS ), which is based on pre-scheduling, is presented. The feasibility of PTDS has been strictly defined and proved. The result shows that PTDS can achieve an approximative optimal scheduling scheme of tasks through adjusting preschedul-ing locally.