并行粗粒度任务的动态分布算法(PTDD)及其鲁棒性  

A DYNAMIC DISTRIBUTION ALGORITHM (PTDD) OF PARALLEL COARSE GRAIN TASKS AND ITS ROBUST PROPERTY

作　　者：沈美明[1] 田新民[1] 王鼎兴[1] 郑纬民[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机学报》1993年第1期13-21,共9页Chinese Journal of Computers

基　　金：高等学校博士学科点专项科研基金;国家高技术项目

摘　　要：并行计算系统发展所面临的主要问题之一是怎样在各处理器上更有效地分布并行任务并协调它们的高效执行,使并行任务总的完成时间最短.本文揭示和探讨了并行多机系统中并行粗粒度任务的粒度变化对静态任务分布的影响,给出了基于预分布的并行粗粒度任务的动态分布算法PTDD,理论上严格地定义和证明了PTDD算法的鲁棒性(Robust Property).研究结果η~*(t~*)≤η(t~*)表明PTDD算法通过局部调整预分布方案,可以稳定地、有效地获得近似最优的并行任务分布.In this paper, effects of execution time variation of parallel coarse-grain tasks to static task distribution in parallel multiprocessor systems are revealed and discussed in detail. An algorithm based on pre-distribution scheme for Parallel coarse grain Tasks Dynamic Distribution (PTDD) is presented. The robustness of PTDD algorithm has been strictly defined and proved. The result η*(t*)≤η(t*) shows that, by transposing tasks among processors partly, PTDD can achive an approximative optimal task distribution scheme.

关 键 词：鲁棒性 粗粒度任务 动态分布算法 

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