任务分解与调度.ppt

任务分解的形式化描述*01结论：任务分解问题就是在满足(1)-(6)的同时使(7)之值最小的问题。完成任务的开销为：∑∑ZijExecFun(Ei,Ej)+∑∑WijCommFun(Ei,Ej)ijij ....(7)020304任务分解的启发式算法*①定义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)INP∩INP(Ti)≮INP’},INP’=INP，INP=INP∪∪OUT(Ti)(Ti∈Actions[M]。④如果INP≥OUT,则执行第⑤步；否则，如果（∪Actions[i]A，则执行第3步，否则执行第2步。⑤定义操作集Result为空集，临时工作集Wanted=OUT。⑥重复执行如下操作：取Wanted的第一个元素K0，按顺序搜寻Actions,找出操作Ti:OUT(Ti)≥{K0}置Wanted=Wanted-{K0},Result=Result∪{Ti}。直到Wanted为空.任务分解的启发式算法*如果（INP∪OUT（Ti)≥∪INP(Ti)，则算法结束。Result为所需操作集，否则置Wanted=INP∪(OUT(Ti))-∪INP(Ti),执行第6步。3.2任务分配*任务分配算法可分为三类：基于图论的分配算法；整数规划算法启发式方法3.3并行调度*并行调度的含义是指系统并行地收集负载信息并完成任务的调度。RIPS任务调度策略如图3.1所示增量调度并行调度任务执行执行结束系统阶段用户阶段*第三章任务分解与调度本章内容*STEP4STEP3STEP2STEP1任务分解任务分配并行调度子任务执行时的协调及结果集成3.1任务分解*任务分解的主要功能是将提交的任务分解成多个具有尽可能高并行度的子任务，并决定由哪些Agent在何时执行它们。经典的算法有：McCornock的基于聚簇的方法；Niizuna和Kitahachi的基于状态和等价关系的方法。任务分解的形式化描述*任务分解问题定义为如下五元组:K,A,E,I,G其中：K为问题的知识集；A为操作集；E为执行单元集I为初始条件集；G为目标集。于是，可定义任务的可行最优分解为下列条件的实现：任务分解的形式化描述*01所有的操作在执行前都行到了其必要的输入信息；G中所有知识都将得到；所耗费的通信和执行开销最小。0203任务分解的形式化描述*另外，定义一个执行开销函数ExecFun与通信开销函数CommFun:ExecFun:A,E?RCommFun:E,E?R其中R为实数集。并定义如下二进制向量：Mjq=1若操作j的输入信息中包含知识q;Djq=1若操作j的输入信息中包含知识q;任务分解的形式化描述*215Zik=1若由执行单元k来完成操作i;Xi=1若在完成任务的过程中执行了操作i;Wik=1若执行单元i与执行单元k通信。4Yij=1若操作j的输入信息可由操作i的输出信息提供;3Vi=1若信息i是完成所必需的;任务分解的形式化描述*根据以上的定义可知：①每个操作最多可被执行一次，即：?i(∑Zik≤1)....(1)k?i(∑Zik=Xi) ....(2) k②所有操作的输出信息必须覆盖目标集，即：?i(∑DjiXj≥Vi) ....(3) j任务分解的形式化描述*③每个操作仅当其输入信息存在时才能执行，即：?q?j(∑DiqYij≥MjqXj) ....(4) i④所执行的操作序列必须是可行的，即：?i?j(Rij≥Yij) ....(5a) ?i?j?k(Rik+Rkj≤Rij+1) ....(5b)?i(Rii=0)