《第三章任务分解与调度.ppt》由会员分享，可在线阅读，更多相关《第三章任务分解与调度.ppt（20页珍藏版）》请在三一文库上搜索。
1、1,第三章 任务分解与调度,2,本章内容,1.任务分解 2.任务分配 3.并行调度 4.子任务执行时的协调及结果集成,3,3.1 任务分解,任务分解的主要功能是将提交的任务分解成多个具有尽可能高并行度的子任务，并决定由哪些Agent在何时执行它们。经典的算法有： McCornock的基于聚簇的方法； Niizuna和Kitahachi的基于状态和等价关系的方法。,4,3.1.1任务分解的形式化描述,任务分解问题定义为如下五元组: 其中： K为问题的知识集； A为操作集； E为执行单元集 I为初始条件集； G为目标集。,5,3.1.1任务分解的形式化描述,于是，可定义任务的可行最优分解为下列条件
2、的实现： 所有的操作在执行前都行到了其必要的输入信息； G中所有知识都将得到； 所耗费的通信和执行开销最小。,6,3.1.1任务分解的形式化描述,另外，定义一个执行开销函数ExecFun与通信开销函数CommFun: ExecFun: A,ER CommFun: E,E R 其中R为实数集。 并定义如下二进制向量： Mjq=1若操作j的输入信息中包含知识q; Djq=1 若操作j的输入信息中包含知识q;,7,3.1.1任务分解的形式化描述,Zik=1 若由执行单元k来完成操作i; Xi=1 若在完成任务的过程中执行了操作i; Vi=1 若信息i是完成所必需的; Yij=1 若操作j的输入信息可
3、由操作i的输出信息提供; Wik=1 若执行单元i与执行单元k通信。,8,3.1.1任务分解的形式化描述,根据以上的定义可知： 每个操作最多可被执行一次，即： i(Zik1) (1) k i(Zik=Xi) (2) k 所有操作的输出信息必须覆盖目标集，即： i(DjiXjVi) (3) j,9,3.1.1任务分解的形式化描述,每个操作仅当其输入信息存在时才能执行，即： q j(DiqYijMjqXj) (4) i 所执行的操作序列必须是可行的，即： i j(RijYij) (5a) i j k(Rik+ Rkj Rij +1) (5b) i (Rii= 0) (5c) 仅当需要传递信息时，才
4、进行通信，即： i j k l(Zik+ Zjl + Yij Wkl +2) (6),10,3.1.1任务分解的形式化描述,完成任务的开销为： ZijExecFun(Ei,Ej)+ WijCommFun(Ei,Ej) i j i j (7) 结论：任务分解问题就是在满足(1)-(6)的同时使(7)之值最小的问题。,11,3.1.2任务分解的启发式算法,定义Ti为操作，INP(Ti)为操作Ti所需要的输入信息，OUT(Ti)为操作Ti的输出信息，INP0为初始输入信息。OUT为完成任务所获得的输出信息。令Beginners=Ti:INP(Ti)INP0，Actions1N为操作集数组。 如果Be
5、ginners为空集，同不存在可行的操作集，算法结束。否则从Beginners中选择一操作T0，置Beginners= Beginners- T0，定义输入信息集INP=INP0OUT(T0),INP=INP0，令Actions1=T0,M=1。 置M=M+1,ActionsM=Ti:INP(Ti)INPINP(Ti) INP,INP=INP，INP=INP OUT(Ti)(TiActionsM。 如果INPOUT,则执行第步；否则，如果（ Actionsi A，则执行第3步，否则执行第2步。 定义操作集Result为空集，临时工作集Wanted=OUT。 重复执行如下操作： 取Wanted的
6、第一个元素K0， 按顺序搜寻Actions,找出操作Ti:OUT(Ti) K0 置Wanted=Wanted-K0,Result=ResultTi。 直到Wanted为空.,12,3.1.2任务分解的启发式算法,如果（INPOUT（Ti) INP(Ti)，则算法结束。Result为所需操作集，否则置Wanted=INP (OUT(Ti)- INP(Ti),执行第6步。,13,3.2 任务分配,任务分配算法可分为三类： 基于图论的分配算法； 整数规划算法 启发式方法,14,3.3 并行调度,并行调度的含义是指系统并行地收集负载信息并完成任务的调度。 RIPS任务调度策略如图3.1所示,增量调度,
7、并行调度,任务执行,执行结束,系统阶段,用户阶段,15,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个任务向后传递。传递完成后，开始用户阶段； 当R0时，从编号j+1开始的R个节点应调度的任务数为Wavg+1,
8、其余为Wavg.,16,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之间且WiWavg+1,则准备接收Wi-Wavg -1个任务向后传递。,17,3.3.2 环结构的并行调度算法示例,0,1,2,3,4,5,W0=6,W1=3,W2=7,W3=1,W4=5,W5=4,1,2,2,18,3.3.2 环结构的并行调度算法示例,调度方案为： 节点0，向下一节点传递2个任务； 节点1，从上一节点接收2个任务； 节点2，向下一节点传递2个任务； 节点3，向上一节点接收3个任务； 节点4，向下一节点传递1个任务； 节点5，它是平载的，即不接收，也不传递任务；,19,3.3.2 环结构的并行调度算法示例,20,3.4 子任务的协调及结果集成,在分布式Agent系统中，设置一个协调者来完成子任务执行的同步以及负责收集结果。 其提供的处理过程为： On Finish(Ai) Do Send Agenti Finish(Aj) At Priorty(xxx),