并行分布计算中的分布式动态任务调度

Distributed Dynamic Task Scheduling in Parallel and Distributed Computing

1.引言并行分布计算中静态的启发式任务调度算法都要求并行分布程序任务在执行前是比较确定的。但一般情况下,实际并行应用程序并不满足这一限制条件,在执行前存在着许多不确定性因素,主要有:并行程序任务中的循环次数事先并不确定;条件分支语句到底执行哪个分支,在程序执行前不能完全了解;每个任务的工作负载大小事先不能确定;任务间的数据通讯量大小只有在运行时才能决定;有些任务是动态产生的。虽然能通过某些技术把这些不确定性转化为确定性,如对条件分支的归纳,但是。

As one of the most fundmental,critical and challengable problems in Parallel Distributed Computing(PDC),task scheduling has great influence on the execution efficiency of PDC. In this paper,we first describe the concept of dynamic task scheduling and the structure of dynamic scheduler in PDC,then propose the distributed dynamic task scheduling based on hybrid driving way,and finally give a set of rules used to design the algorithm of distributed dynamic task scheduling.