任务分解与调度PPT课件.ppt

第三章 任务分解与调度1本章内容本章内容23.1 任务分解 任务分解的主要功能是将提交的任务分解任务分解的主要功能是将提交的任务分解成多个具有尽可能高并行度的子任务，并决成多个具有尽可能高并行度的子任务，并决定由哪些定由哪些AgentAgent在何时执行它们经典的算在何时执行它们经典的算法有：法有：•McCornockMcCornock的基于聚簇的方法；的基于聚簇的方法；•NiizunaNiizuna和和KitahachiKitahachi的基于状态和等价关的基于状态和等价关系的方法系的方法3任务分解的形式化描述任务分解的形式化描述任务分解问题定义为如下五元组任务分解问题定义为如下五元组: : 其中：其中：K K为问题的知识集；为问题的知识集；A A为操作集；为操作集；E E为执行单元集为执行单元集I I为初始条件集；为初始条件集；G G为目标集为目标集4任务分解的形式化描述任务分解的形式化描述于是，可定义任务的可行最优分解为下列条于是，可定义任务的可行最优分解为下列条件的实现：件的实现：①①所有的操作在执行前都行到了其必要的输所有的操作在执行前都行到了其必要的输入信息；入信息；②G②G中所有知识都将得到；中所有知识都将得到；③③所耗费的通信和执行开销最小。

所耗费的通信和执行开销最小5任务分解的形式化描述任务分解的形式化描述另外，定义一个执行开销函数ExecFun与通信开销函数CommFun:ExecFun: A,ERCommFun: E,E R其中R为实数集并定义如下二进制向量：Mjq=1若操作j的输入信息中包含知识q;Djq=1 若操作j的输入信息中包含知识q;6任务分解的形式化描述任务分解的形式化描述Zik=1 若由执行单元k来完成操作i;Xi=1 若在完成任务的过程中执行了操作i;Vi=1 若信息i是完成所必需的;Yij=1 若操作j的输入信息可由操作i的输出信息提供;Wik=1 若执行单元i与执行单元k通信7任务分解的形式化描述任务分解的形式化描述根据以上的定义可知：①①每个操作最多可被执行一次，即：每个操作最多可被执行一次，即： i(i(∑Zik≤1) ....(1) k i(i(∑Zik=Xi) ....(2) k②所有操作的输出信息必须覆盖目标集，即：所有操作的输出信息必须覆盖目标集，即：  i(i(∑DjiXj≥Vi) ....(3) j8任务分解的形式化描述任务分解的形式化描述 ③每个操作仅当其输入信息存在时才能执行，即：每个操作仅当其输入信息存在时才能执行，即：  q q  j(j(∑DiqYij≥MjqXj) ....(4) i④所执行的操作序列必须是可行的，即：所执行的操作序列必须是可行的，即：  i i  j(j(Rij≥Yij) ....(5a)  i i  j j  k(k(Rik+ Rkj ≤ Rij +1) ....(5b)  i i ( (Rii= 0) ....(5c) ⑤仅当需要传递信息时，才进行通信，即：仅当需要传递信息时，才进行通信，即： i i  j j  k k  l(Zl(Zik+ Zjl + Yij ≤ Wkl +2) ....(6) 9任务分解的形式化描述任务分解的形式化描述⑥完成任务的开销为：完成任务的开销为：∑∑ZijExecFun(Ei,Ej)+ ∑∑WijCommFun(Ei,Ej)i j i j....(7)结论：任务分解问题就是在满足(1)-(6)的同时使(7)之值最小的问题。

10任务分解的启发式算法任务分解的启发式算法①定义Ti为操作，INP(Ti)为操作Ti所需要的输入信息，OUT(Ti)为操作Ti的输出信息，INP0为初始输入信息OUT为完成任务所获得的输出信息令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)

直到Wanted为空.11任务分解的启发式算法任务分解的启发式算法⑦如果（INP∪OUT（Ti) ≥ ∪INP(Ti)，则算法结束Result为所需操作集，否则置Wanted=INP ∪(OUT(Ti))- ∪INP(Ti),执行第6步123.2 任务分配任务分配算法可分为三类：•基于图论的分配算法；•整数规划算法•启发式方法133.3 并行调度 并行调度的含义是指系统并行地收集负载信息并完成任务的调度 RIPS增量调度并行调度任务执行执行结束系统阶段用户阶段143.3.1 基于环结构的并行调度算法①按顺时针方向为每个节点编号；②令Wi为节点i的任务数，每个结点保留一个Wi；③主控结点j计算平均任务数Wavg=Wi之和除N最整,余数R=Wi之各模N并把Wavg和R广播到全部节点；④节点i收到Wavg和R后，计算本节点应调度多少任务：当R=0时，每个节点应调度的任务数为Wavg如果：Wi=Wavg,则该节点不接收也不发送任务，开始用户阶段；WiWavg,则该节点选择Wi-Wavg个任务向后传递传递完成后，开始用户阶段；当R≠0时，从编号j+1开始的R个节点应调度的任务数为Wavg+1,其余为Wavg.153.3.1 基于环结构的并行调度算法如果：i在j+R之后且Wi=Wavg或i在j+1到j+R之间且Wi=Wavg+1,则该结点不接收也不发送任务，开如用户阶段。

i在j+R之后且WiWavg，则该结点准备选择Wi-Wavg个任务向后传递，或i在j+1到j+R之间且Wi>Wavg+1,则准备接收Wi-Wavg -1个任务向后传递163.3.2 环结构的并行调度算法示例012345W0=6W1=3W2=7W3=1W4=5W5=4122173.3.2 环结构的并行调度算法示例调度方案为：调度方案为：节点节点0 0，向下一节点传递，向下一节点传递2 2个任务；个任务；节点节点1 1，从上一节点接收，从上一节点接收2 2个任务；个任务；节点节点2 2，向下一节点传递，向下一节点传递2 2个任务；个任务；节点节点3 3，向上一节点接收，向上一节点接收3 3个任务；个任务；节点节点4 4，向下一节点传递，向下一节点传递1 1个任务；个任务；节点节点5 5，它是平载的，即不接收，也不，它是平载的，即不接收，也不传递任务；传递任务；183.3.2 环结构的并行调度算法示例193.4 子任务的协调及结果集成 在分布式在分布式AgentAgent系统中，设置一个协调者来系统中，设置一个协调者来完成子任务执行的同步以及负责收集结果。

完成子任务执行的同步以及负责收集结果其提供的处理过程为：其提供的处理过程为：On Finish(Ai) DoOn Finish(Ai) Do Send Agenti Finish(Aj) At Priorty(xxx) Send Agenti Finish(Aj) At Priorty(xxx)20。