分布式内存多处理机上并行任务静态调度

发布时间：2020-08-21 01:10

【摘要】：在分布式内存多处理机系统上，对于中、细粒度并行程序而言，不同处理机之间的通信开销在整个程序的执行时间中所占的比重仍然很大，有时可能会抵消多处理机并行所带来的好处。为了使并行程序能得到高效地执行，必须采用合理的静态任务调度技术将不同的任务分配给合适的处理机去执行。静态任务调度的目标是最小化并行程序的执行时间。静态任务调度的实现方法有两种：1)．程序员／用户手工地将任务分配给处理机；2)．采用调度算法自动地将任务分配给处理机。在应用较为规则或划分后的应用拓扑与处理机系统的拓扑相一致时，采用手工的方法去分配任务是可行的。但对于一些不规则应用，尤其当问题的规模较大时，应当采用一些专门的算法去自动调度任务。本文重点讨论如何采用算法去自动调度并行任务，主要贡献有： 1．对于完全互连的系统，提出了一个基于动态关键路径的调度算法('NF。算法('NF的特点有：(1)根据任务调度过程中关键路径的动态变化相应地调整关键路径。(2)总是优先调度关键路径上的任务。(3)当参与调度的任务只有一个子任务时，则采用一种试探法来选择处理机；当参与调度的任务有多个子任务时，则为这样的任务选择能最早地开始执行的处理机。本文还将该算法与其它三种典型的算法在调度长度上进行了比较，结果表明本文中提出的算法平均调度长度最短。另外，本文还提出了一种有效的可以节省任务调度中所需使用处理机数目的方法。 2．对于非完全互连系统，给出了任务调度问题的形式化描述。针对一些典型的系统，如线性阵列、环、二维Mesh网与超立方体，将不同处理机之间的链路看成是资源，提出了一个基于静态关键路径的调度算法。算法中重点解决的问题是如何为消息分配路由，该问题按存储转发与虫道寻径两种不同的寻径技术分别进行了讨论。在针对总线互连的多处理机系统的调度算法中，本文首次考虑了消息广播对任务调度的影响。 3．移植了一个基于任务级并行的编程环境(?)RAPID系统。为了实现进程之间的通信，该系统原先调用了('RAY T3E上提供的共享内存库，而移植后系统的底层通信环境完全建立在MPI之上。目前，算法('NF已被成功
【学位授予单位】：中国科学院研究生院（计算技术研究所）
【学位级别】：博士
【学位授予年份】：1999
【分类号】：TP338.6
【图文】：

任务聚类,任务调度程序

.:5程序串行执行Gatllt图(11二512)图6.6:自动任务调度程序执行Gallt.t图(n二512)图(，了:手工任务聚类程序执行(;alltt图(n二512)

任务调度程序,任务聚类,并行任务,多处理机

分布式内存多处理机上并行任务静态调度图6.:5程序串行执行Gatllt图(11二512)图6.6:自动任务调度程序执行Gallt.t图(n二512)图(，了:手工任务聚类程序执行(;alltt图(n二512)

【引证文献】