《三章节任务分解与调度》由会员分享，可在线阅读，更多相关《三章节任务分解与调度（20页珍藏版）》请在金锄头文库上搜索。
1、三章节任务分解与调度Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望本章内容本章内容1.1.任务分解任务分解2.2.任务分配任务分配3.3.并行调度并行调度4.4.子任务执行时的协调及子任务执行时的协调及结果集成结果集成23.1 任务分解 任务分解的主要功能是将提交的任务分解任务分解的主要功能是将提交的任务分解成多个具有尽可能高并行度的子任务，并决成多个具有尽可能高并行度的子任务，并决定由哪些定由哪些AgentAgent在何时执行它们。经典的算在何时执行它们。经典的算法有：法有：Mc
2、CornockMcCornock的基于聚簇的方法；的基于聚簇的方法；NiizunaNiizuna和和KitahachiKitahachi的基于状态和等价关的基于状态和等价关系的方法。系的方法。33.1.1任务分解的形式化描述任务分解的形式化描述任务分解问题定义为如下五元组任务分解问题定义为如下五元组: : 其中：其中：K K为问题的知识集；为问题的知识集；A A为操作集；为操作集；E E为执行单元集为执行单元集I I为初始条件集；为初始条件集；G G为目标集。为目标集。43.1.1任务分解的形式化描述任务分解的形式化描述于是，可定义任务的可行最优分解为下列条于是，可定义任务的可行最优分解为下列
3、条件的实现：件的实现：所有的操作在执行前都行到了其必要的输所有的操作在执行前都行到了其必要的输入信息；入信息；GG中所有知识都将得到；中所有知识都将得到；所耗费的通信和执行开销最小。所耗费的通信和执行开销最小。53.1.1任务分解的形式化描述任务分解的形式化描述另外，定义一个执行开销函数ExecFun与通信开销函数CommFun:ExecFun: A,ERCommFun: E,E R其中R为实数集。并定义如下二进制向量：Mjq=1若操作j的输入信息中包含知识q;Djq=1 若操作j的输入信息中包含知识q;63.1.1任务分解的形式化描述任务分解的形式化描述Zik=1 若由执行单元k来完成操作i
4、;Xi=1 若在完成任务的过程中执行了操作i;Vi=1 若信息i是完成所必需的;Yij=1 若操作j的输入信息可由操作i的输出信息提供;Wik=1 若执行单元i与执行单元k通信。73.1.1任务分解的形式化描述任务分解的形式化描述根据以上的定义可知：每个操作最多可被执行一次，即：每个操作最多可被执行一次，即： i(i(Zik1) .(1) k i(i(Zik=Xi) .(2) k所有操作的输出信息必须覆盖目标集，即：所有操作的输出信息必须覆盖目标集，即： i(i(DjiXjVi) .(3) j83.1.1任务分解的形式化描述任务分解的形式化描述 每个操作仅当其输入信息存在时才能执行，即：每个操
5、作仅当其输入信息存在时才能执行，即： q q j(j(DiqYijMjqXj) .(4) i所执行的操作序列必须是可行的，即：所执行的操作序列必须是可行的，即： i i j(j(RijYij) .(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) 93.1.1任务分解的形式化描述任务分解的形式化描述完成任务的开销为：完成任务的开销为：ZijExecFun(Ei,E
6、j)+ WijCommFun(Ei,Ej)i j i j.(7)结论：任务分解问题就是在满足(1)-(6)的同时使(7)之值最小的问题。 103.1.2任务分解的启发式算法任务分解的启发式算法定义Ti为操作，INP(Ti)为操作Ti所需要的输入信息，OUT(Ti)为操作Ti的输出信息，INP0为初始输入信息。OUT为完成任务所获得的输出信息。令Beginners=Ti:INP(Ti)INP0，Actions1.N为操作集数组。如果Beginners为空集，同不存在可行的操作集，算法结束。否则从Beginners中选择一操作T0，置Beginners= Beginners- T0，定义输入信息集
7、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的第一个元素K0， 按顺序搜寻Actions,找出操作Ti:OUT(Ti) K0 置Wanted=Wanted-K0,Result=ResultTi。直到Wanted为空.
8、113.1.2任务分解的启发式算法任务分解的启发式算法如果（INPOUT（Ti) INP(Ti)，则算法结束。Result为所需操作集，否则置Wanted=INP (OUT(Ti)- INP(Ti),执行第6步。123.2 任务分配任务分配算法可分为三类：基于图论的分配算法；整数规划算法启发式方法133.3 并行调度 并行调度的含义是指系统并行地收集负载信息并完成任务的调度。 RIPS任务调度策略如图3.1所示增量调度并行调度任务执行执行结束系统阶段用户阶段143.3.1 基于环结构的并行调度算法按顺时针方向为每个节点编号；令Wi为节点i的任务数，每个结点保留一个Wi；主控结点j计算平均任务数
9、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,其余为Wavg.153.3.1 基于环结构的并行调度算法如果：i在j+R之后且Wi=Wavg或i在j+1到j+R之间且Wi=Wavg+1,则该结点不接收也不发送任务，开如用户阶段。i在j+R之后且WiWavg
10、，则该结点准备接收Wavg-Wi个任务，或i在j+1到j+R之间且WiWavg，则该结点准备选择Wi-Wavg个任务向后传递，或i在j+1到j+R之间且WiWavg+1,则准备接收Wi-Wavg -1个任务向后传递。163.3.2 环结构的并行调度算法示例012345W0=6W1=3W2=7W3=1W4=5W5=4122173.3.2 环结构的并行调度算法示例调度方案为：调度方案为：节点节点0 0，向下一节点传递，向下一节点传递2 2个任务；个任务；节点节点1 1，从上一节点接收，从上一节点接收2 2个任务；个任务；节点节点2 2，向下一节点传递，向下一节点传递2 2个任务；个任务；节点节点3
11、 3，向上一节点接收，向上一节点接收3 3个任务；个任务；节点节点4 4，向下一节点传递，向下一节点传递1 1个任务；个任务；节点节点5 5，它是平载的，即不接收，也不，它是平载的，即不接收，也不传递任务；传递任务；183.3.2 环结构的并行调度算法示例193.4 子任务的协调及结果集成 在分布式在分布式AgentAgent系统中，设置一个协调者来系统中，设置一个协调者来完成子任务执行的同步以及负责收集结果。完成子任务执行的同步以及负责收集结果。其提供的处理过程为：其提供的处理过程为：On Finish(Ai) DoOn Finish(Ai) Do Send Agenti Finish(Aj) At Priorty(xxx) Send Agenti Finish(Aj) At Priorty(xxx)20
