第三章 任务分解与调度

《第三章 任务分解与调度》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章任务分解与调度1本章内容1.任务分解2.任务分配3.并行调度4.子任务执行时的协调及结果集成23.1任务分解任务分解的主要功能是将提交的任务分解成多个具有尽可能高并行度的子任务，并决定由哪些Agent在何时执行它们。经典的算法有：McCornock的基于聚簇的方法；Niizuna和Kitahachi的基于状态和等价关系的方法。33.1.1任务分解的形式化描述任务分解问题定义为如下五元组:其中：K为问题的知识集；A为操作集；E为执行单元集I为初始条件集；G为目标集。43.1.1任务分解的形式化描述于是，可定义任务的可行最优分解为

2、下列条件的实现：①所有的操作在执行前都行到了其必要的输入信息；②G中所有知识都将得到；③所耗费的通信和执行开销最小。53.1.1任务分解的形式化描述另外，定义一个执行开销函数ExecFun与通信开销函数CommFun:ExecFun:A,ERCommFun:E,ER其中R为实数集。并定义如下二进制向量：Mjq=1若操作j的输入信息中包含知识q;Djq=1若操作j的输入信息中包含知识q;63.1.1任务分解的形式化描述Zik=1若由执行单元k来完成操作i;Xi=1若在完成任务的过程中执行了操作i;Vi=1若信息i是完成所必需的;Yij=1若操作j的输入

3、信息可由操作i的输出信息提供;Wik=1若执行单元i与执行单元k通信。73.1.1任务分解的形式化描述根据以上的定义可知：①每个操作最多可被执行一次，即：i(∑Zik≤1)....(1)ki(∑Zik=Xi)....(2)k②所有操作的输出信息必须覆盖目标集，即：i(∑DjiXj≥Vi)....(3)j83.1.1任务分解的形式化描述③每个操作仅当其输入信息存在时才能执行，即：qj(∑DiqYij≥MjqXj)....(4)i④所执行的操作序列必须是可行的，即：ij(Rij≥Yij)....(5a)ijk(Rik+Rkj≤Rij+1)

4、....(5b)i(Rii=0)....(5c)⑤仅当需要传递信息时，才进行通信，即：ijkl(Zik+Zjl+Yij≤Wkl+2)....(6)93.1.1任务分解的形式化描述⑥完成任务的开销为：∑∑ZijExecFun(Ei,Ej)+∑∑WijCommFun(Ei,Ej)ijij....(7)结论：任务分解问题就是在满足(1)-(6)的同时使(7)之值最小的问题。103.1.2任务分解的启发式算法①定义Ti为操作，INP(Ti)为操作Ti所需要的输入信息，OUT(Ti)为操作Ti的输出信息，INP0为初始输入信息。OUT为完成任务所获得的输

5、出信息。令Beginners={Ti:INP(Ti)≤INP0}，Actions[1..N]为操作集数组。②如果Beginners为空集，同不存在可行的操作集，算法结束。否则从Beginners中选择一操作T0，置Beginners=Beginners-{T0}，定义输入信息集INP=INP0∪OUT(T0),INP’=INP0，令Actions[1]={T0},M=1。③置M=M+1,Actions[M]={Ti:INP(Ti)

6、NP≥OUT,则执行第⑤步；否则，如果（∪Actions[i]

7、i),执行第6步。123.2任务分配任务分配算法可分为三类：基于图论的分配算法；整数规划算法启发式方法133.3并行调度并行调度的含义是指系统并行地收集负载信息并完成任务的调度。RIPS任务调度策略如图3.1所示增量调度并行调度任务执行执行结束系统阶段用户阶段143.3.1基于环结构的并行调度算法①按顺时针方向为每个节点编号；②令Wi为节点i的任务数，每个结点保留一个Wi；③主控结点j计算平均任务数Wavg=Wi之和除N最整,余数R=Wi之各模N。并把Wavg和R广播到全部节点；④节点i收到Wavg和R后，计算本节点应调度多少任务：当R=0时，每个节点应

8、调度的任务数为Wavg。如果：Wi=Wavg,则该节点不接收也不发送任务，开始用