任務分解與調(diào)度

《任務分解與調(diào)度》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第三章任務分解與調(diào)度1本章內(nèi)容1.任務分解2.任務分配3.并行調(diào)度4.子任務執(zhí)行時的協(xié)調(diào)及結果集成23.1任務分解任務分解的主要功能是將提交的任務分解成多個具有盡可能高并行度的子任務，并決定由哪些Agent在何時執(zhí)行它們。經(jīng)典的算法有：McCornock的基于聚簇的方法；Niizuna和Kitahachi的基于狀態(tài)和等價關系的方法。33.1.1任務分解的形式化描述任務分解問題定義為如下五元組:其中：K為問題的知識集；A為操作集；E為執(zhí)行單元集I為初始條件集；G為目標集。43.1.1任務分解的形式化描述

2、于是，可定義任務的可行最優(yōu)分解為下列條件的實現(xiàn)：①所有的操作在執(zhí)行前都行到了其必要的輸入信息；②G中所有知識都將得到；③所耗費的通信和執(zhí)行開銷最小。53.1.1任務分解的形式化描述另外，定義一個執(zhí)行開銷函數(shù)ExecFun與通信開銷函數(shù)CommFun:ExecFun:A,E?RCommFun:E,E?R其中R為實數(shù)集。并定義如下二進制向量：Mjq=1若操作j的輸入信息中包含知識q;Djq=1若操作j的輸入信息中包含知識q;63.1.1任務分解的形式化描述Zik=1若由執(zhí)行單元k來完成操作i;Xi=1若在完成任務的過程中執(zhí)行了

3、操作i;Vi=1若信息i是完成所必需的;Yij=1若操作j的輸入信息可由操作i的輸出信息提供;Wik=1若執(zhí)行單元i與執(zhí)行單元k通信。73.1.1任務分解的形式化描述根據(jù)以上的定義可知：①每個操作最多可被執(zhí)行一次，即：?i(∑Zik≤1)....(1)k?i(∑Zik=Xi)....(2)k②所有操作的輸出信息必須覆蓋目標集，即：?i(∑DjiXj≥Vi)....(3)j83.1.1任務分解的形式化描述③每個操作僅當其輸入信息存在時才能執(zhí)行，即：?q?j(∑DiqYij≥MjqXj)....(4)i④所執(zhí)行的操作序列必須是

4、可行的，即：?i?j(Rij≥Yij)....(5a)?i?j?k(Rik+Rkj≤Rij+1)....(5b)?i(Rii=0)....(5c)⑤僅當需要傳遞信息時，才進行通信，即：?i?j?k?l(Zik+Zjl+Yij≤Wkl+2)....(6)93.1.1任務分解的形式化描述⑥完成任務的開銷為：∑∑ZijExecFun(Ei,Ej)+∑∑WijCommFun(Ei,Ej)ijij....(7)結論：任務分解問題就是在滿足(1)-(6)的同時使(7)之值最小的問題。103.1.2任務分解的啟發(fā)式算法①定義Ti為操作，

5、INP(Ti)為操作Ti所需要的輸入信息，OUT(Ti)為操作Ti的輸出信息，INP0為初始輸入信息。OUT為完成任務所獲得的輸出信息。令Beginners={Ti:INP(Ti)≤INP0}，Actions[1..N]為操作集數(shù)組。②如果Beginners為空集，同不存在可行的操作集，算法結束。否則從Beginners中選擇一操作T0，置Beginners=Beginners-{T0}，定義輸入信息集INP=INP0∪OUT(T0),INP’=INP0，令Actions[1]={T0},M=1。③置M=M+1,Actio

6、ns[M]={Ti:INP(Ti)

7、ed為空.113.1.2任務分解的啟發(fā)式算法⑦如果（INP∪OUT（Ti)≥∪INP(Ti)，則算法結束。Result為所需操作集，否則置Wanted=INP∪(OUT(Ti))-∪INP(Ti),執(zhí)行第6步。123.2任務分配任務分配算法可分為三類：基于圖論的分配算法；整數(shù)規(guī)劃算法啟發(fā)式方法133.3并行調(diào)度并行調(diào)度的含義是指系統(tǒng)并行地收集負載信息并完成任務的調(diào)度。RIPS任務調(diào)度策略如圖3.1所示增量調(diào)度并行調(diào)度任務執(zhí)行執(zhí)行結束系統(tǒng)階段用戶階段143.3.1基于環(huán)結構的并行調(diào)度算法①按順時針方向為每個節(jié)點編號；②令Wi

8、為節(jié)點i的任務數(shù)，每個結點保留一個Wi；③主控結點j計算平均任務數(shù)Wavg=Wi之和除N最整,余數(shù)R=Wi之各模N。并把Wavg和R廣播到全部節(jié)點；④節(jié)點i收到Wavg和R后，計算本節(jié)點應調(diào)度多少任務：當R=0時，每個節(jié)點應調(diào)度的任務數(shù)為Wavg。如果：Wi=Wavg,則該節(jié)點不接收也不發(fā)送任務，開始用