任务分解与调度.ppt

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任务分解的形式化描述,于是，可定义任务的可行最优分解为下列条件的实现： 所有的操作在执行前都行到了其必要的输入信息； 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的输入信息可由操作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) 仅当需要传递信息时，才进行通信，即： 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为操作集数组。 如果Beginners为空集，同不存在可行的操作集，算法结束。否则从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的第一个元素K0，