第三章任务分解与调度.ppt
《第三章任务分解与调度.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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 任务 分解 调度
链接地址:https://www.31doc.com/p-2597164.html