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

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

作　　者：田新民[1] 王鼎兴[1] 

机构地区：[1]清华大学

出　　处：《小型微型计算机系统》1991年第8期7-14,共8页Journal of Chinese Computer Systems

基　　金：国家"863"高技术项目资助

摘　　要：本文揭示和探讨了并行多机系统中粗粒度并行任务的时间变化对静态任务调度机制的影响,给出了基于预调度的粗粒度并行任务的动态调度算法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.

关 键 词：并行任务 调度 算法 有效性证明 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]