多核環(huán)境下基于圖模型的實(shí)時(shí)規(guī)則調(diào)度方法?

王娟娟,喬 穎,熊金泉,王宏安

1(中國科學(xué)院 軟件研究所,北京 100190)

2(中國科學(xué)院大學(xué),北京 100049)

3(南昌師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,江西 南昌 330032)

實(shí)時(shí)反應(yīng)式系統(tǒng)[1]被廣泛應(yīng)用在醫(yī)療、工業(yè)、軍事、通信、交通等安全攸關(guān)領(lǐng)域.這類系統(tǒng)有主動行為,其運(yùn)行受外部事件驅(qū)動.系統(tǒng)通過一系列傳感器采集外部環(huán)境數(shù)據(jù),對連續(xù)不斷的事件流進(jìn)行監(jiān)視,從中識別出需要關(guān)注的場景(該場景是由一系列事件的發(fā)生所喻示的),實(shí)時(shí)地對識別出的場景做出響應(yīng).隨著實(shí)時(shí)反應(yīng)式系統(tǒng)應(yīng)用環(huán)境的日趨復(fù)雜,人們對這類系統(tǒng)智能化的需求也越來越高,這就要求復(fù)雜反應(yīng)式系統(tǒng)必須具有強(qiáng)大的推理能力,能夠根據(jù)外部環(huán)境中發(fā)生的事件,自動決策如何對這些事件進(jìn)行響應(yīng).因此,將規(guī)則推理系統(tǒng)應(yīng)用于實(shí)時(shí)反應(yīng)式系統(tǒng)就成為必然趨勢.

實(shí)時(shí)反應(yīng)式系統(tǒng)通常是安全攸關(guān)系統(tǒng),具有硬實(shí)時(shí)約束.即當(dāng)某些需要關(guān)注的事件發(fā)生后,系統(tǒng)必須在給定截止期內(nèi)完成相應(yīng)的動作,對這些事件進(jìn)行響應(yīng);否則會產(chǎn)生嚴(yán)重后果.這就要求規(guī)則推理需要具有時(shí)間約束.學(xué)者們?yōu)榇颂岢隽藢?shí)時(shí)推理方法,如迭代推理[2](如Anytime算法)、多重方法推理[3](如Design-to-Time算法)和漸進(jìn)式推理[4,5](如GREAT算法和PRIMES算法).這些方法為整個(gè)推理過程定義了截止期約束,通過對推理運(yùn)行時(shí)間與推理結(jié)果質(zhì)量進(jìn)行折中來滿足這個(gè)截止期約束.此外,學(xué)者們還通過改進(jìn)傳統(tǒng)規(guī)則匹配算法 RETE縮短了OPS5產(chǎn)生式系統(tǒng)的匹配時(shí)間,從而降低了整個(gè)專家系統(tǒng)的響應(yīng)時(shí)間[6,7].同時(shí),李想等人[8,9]提出了估算實(shí)時(shí)規(guī)則推理程序最大響應(yīng)時(shí)間的方法.李娜等人[10,11]針對實(shí)時(shí)感知數(shù)據(jù)流,為復(fù)雜事件檢測的整個(gè)過程引入了截止期,并提出啟發(fā)式調(diào)度算法對檢測過程進(jìn)行調(diào)度,縮短了復(fù)雜事件檢測的平均時(shí)間.由于上述研究忽略了各規(guī)則不同的緊迫度與資源需求,很可能會在資源受限的情況下獲得不可接受的推理結(jié)果質(zhì)量.

為此,我們在前期工作中提出了一種新的實(shí)時(shí)推理模式[12]:實(shí)時(shí)規(guī)則推理.在實(shí)時(shí)規(guī)則推理中,我們?yōu)槊織l規(guī)則(規(guī)則的形式為:IF 〈EVENTPATTERN〉 THEN 〈ACTION〉.其語義為:若〈EVENTPATTERN〉定義的目標(biāo)事件發(fā)生,則執(zhí)行〈ACTION〉定義的動作)引入了截止期(規(guī)則截止期為該規(guī)則響應(yīng)時(shí)間的上界(規(guī)則響應(yīng)時(shí)間是指從與規(guī)則相關(guān)的所有原子事件實(shí)例到達(dá)系統(tǒng)開始到響應(yīng)動作執(zhí)行完畢為止的時(shí)間間隔)),并提出了軟實(shí)時(shí)規(guī)則調(diào)度算法[13,14].但這些方法只是盡可能地使規(guī)則在其截止期前執(zhí)行完畢,無法預(yù)測實(shí)時(shí)規(guī)則推理對資源的動態(tài)需求,也就難以保證各規(guī)則的截止期,從而無法滿足安全攸關(guān)系統(tǒng)的硬實(shí)時(shí)約束.規(guī)則調(diào)度是保證規(guī)則截止期的關(guān)鍵.因此,本文將對該問題進(jìn)行研究.具體來說,規(guī)則調(diào)度問題(rule scheduling problem,簡稱RSP)是找到一種實(shí)時(shí)調(diào)度策略,能夠合理安排各規(guī)則的匹配與執(zhí)行順序,使得每條規(guī)則的響應(yīng)時(shí)間不超過其截止期.

由于處理數(shù)據(jù)規(guī)模的不斷增大和計(jì)算復(fù)雜度的持續(xù)上升,安全攸關(guān)系統(tǒng)需要運(yùn)行在計(jì)算能力更強(qiáng)、更有彈性的多核環(huán)境下.多核計(jì)算具有更強(qiáng)的并行處理能力、更高的計(jì)算密度,同時(shí)具有更低的時(shí)鐘頻率,減少散熱和功耗,因此,研究在多核環(huán)境下安全攸關(guān)系統(tǒng)的規(guī)則調(diào)度問題十分必要(多核環(huán)境是指“單機(jī)多核”,也就是說,安全攸關(guān)系統(tǒng)運(yùn)行在單機(jī)上,只有1個(gè)處理器,但該處理器包括了多個(gè)處理器核).為了解決多核環(huán)境下安全攸關(guān)系統(tǒng)中的規(guī)則調(diào)度問題,本文提出了一種基于圖模型的實(shí)時(shí)規(guī)則調(diào)度(graph-based real-time rule scheduling,簡稱GBRRS)方法.該方法首先對基于事件圖的推理過程進(jìn)行建模,將規(guī)則調(diào)度問題轉(zhuǎn)化成基于圖的端到端推理任務(wù)調(diào)度.并給出了多核環(huán)境下端到端推理任務(wù)的調(diào)度算法,一方面通過調(diào)度端到端推理任務(wù)來合理安排規(guī)則匹配與執(zhí)行的順序;另一方面,通過提出準(zhǔn)入控制算法,對推理過程所需資源進(jìn)行預(yù)測,以保證每一條觸發(fā)規(guī)則都在其截止期之前完成(若規(guī)則〈EVENTPATTERN〉部分所定義的目標(biāo)事件發(fā)生,則該規(guī)則被稱為觸發(fā)規(guī)則),從而保障了多核環(huán)境下規(guī)則推理的實(shí)時(shí)性,進(jìn)而保證了安全攸關(guān)系統(tǒng)的硬實(shí)時(shí)約束.

本文第 1節(jié)對面向安全攸關(guān)反應(yīng)式系統(tǒng)的實(shí)時(shí)規(guī)則推理系統(tǒng)和基于事件圖的實(shí)時(shí)規(guī)則推理過程加以描述.第2節(jié)給出多核環(huán)境下基于圖模型的實(shí)時(shí)規(guī)則調(diào)度方法.第3節(jié)的模擬實(shí)驗(yàn)對GBRRS方法的性能進(jìn)行驗(yàn)證.第4節(jié)對全文進(jìn)行總結(jié),介紹下一步的研究工作.

1 實(shí)時(shí)規(guī)則推理系統(tǒng)

本節(jié)將描述面向安全攸關(guān)反應(yīng)式系統(tǒng)的實(shí)時(shí)規(guī)則推理系統(tǒng),重點(diǎn)介紹其系統(tǒng)結(jié)構(gòu)與實(shí)時(shí)規(guī)則推理引擎所采用的實(shí)時(shí)規(guī)則推理過程.

1.1 實(shí)時(shí)規(guī)則推理系統(tǒng)結(jié)構(gòu)

面向安全攸關(guān)反應(yīng)式系統(tǒng)的實(shí)時(shí)規(guī)則推理系統(tǒng)為S=(R,E,I),其系統(tǒng)結(jié)構(gòu)[15]如圖1所示.其中,R是規(guī)則庫,存放可描述專家知識的規(guī)則集R={R1,R2,…,Rn},每條規(guī)則Ri(1≤i≤n)具有截止期Di;E是由外部環(huán)境產(chǎn)生并進(jìn)入實(shí)時(shí)規(guī)則推理系統(tǒng)的原子事件實(shí)例所形成的事件流,E={e1,e2,…,ek,…}.事件檢測器將事件流中被規(guī)則Ri(1≤i≤n)涉及的原子事件實(shí)例輸入實(shí)時(shí)規(guī)則推理引擎I.

Fig.1 Real-time rule reasoning system圖1 實(shí)時(shí)規(guī)則推理系統(tǒng)

實(shí)時(shí)規(guī)則推理引擎I根據(jù)輸入的事件流,從規(guī)則庫中匹配出相應(yīng)的規(guī)則(規(guī)則匹配:給定規(guī)則集R={R1,…,Rn},根據(jù)到達(dá)系統(tǒng)的原子事件流,對R中每條規(guī)則Ri,判斷其所定義的目標(biāo)事件是否發(fā)生),并在其截止期前執(zhí)行該規(guī)則所定義的響應(yīng)動作指令(簡稱為規(guī)則執(zhí)行),其核心包括規(guī)則調(diào)度器與規(guī)則執(zhí)行器.規(guī)則調(diào)度器運(yùn)行相應(yīng)的規(guī)則調(diào)度方法將基于事件圖的實(shí)時(shí)規(guī)則推理過程轉(zhuǎn)化為一組并發(fā)的實(shí)時(shí)推理任務(wù),并對這組推理任務(wù)進(jìn)行調(diào)度;規(guī)則執(zhí)行器負(fù)責(zé)執(zhí)行被調(diào)度器選中的推理任務(wù).這樣,實(shí)時(shí)規(guī)則推理引擎即可通過合理安排規(guī)則匹配與執(zhí)行的順序來保證規(guī)則的截止期,使安全攸關(guān)反應(yīng)式系統(tǒng)可以在截止期前對其所關(guān)注的場景做出響應(yīng).本文將對規(guī)則調(diào)度器所運(yùn)行的規(guī)則調(diào)度方法進(jìn)行研究.第1.2節(jié)將介紹基于事件圖的實(shí)時(shí)規(guī)則推理過程.

1.2 基于事件圖的實(shí)時(shí)規(guī)則推理過程

在基于事件圖的推理過程[16]中,規(guī)則集R={R1,R2,…,Rn}可用有向無環(huán)圖(directed acyclic graph,簡稱DAG)來描述.該有向無環(huán)圖稱為規(guī)則圖GR.GR=(V,A,E),其中,V表示事件節(jié)點(diǎn)(包括原子事件和復(fù)合事件),A表示響應(yīng)動作指令的節(jié)點(diǎn)(簡稱為動作節(jié)點(diǎn)),E表示節(jié)點(diǎn)間時(shí)序關(guān)系(方向代表了時(shí)序先后)的有向邊.

若存在規(guī)則集R={R1,R2,R3},其中,

則R所對應(yīng)的規(guī)則圖GR如圖2(a)所示,其中,沒有直接前驅(qū)的節(jié)點(diǎn)是源節(jié)點(diǎn),表示原子事件(如e1,…,e11),也稱原子節(jié)點(diǎn);沒有直接后繼的節(jié)點(diǎn)是終節(jié)點(diǎn),表示響應(yīng)動作指令(如A1、A2、A3),也稱動作節(jié)點(diǎn);其他節(jié)點(diǎn)為中間節(jié)點(diǎn),表示復(fù)合事件;原子節(jié)點(diǎn)和中間節(jié)點(diǎn)都表示事件,也稱事件節(jié)點(diǎn);動作節(jié)點(diǎn)的父節(jié)點(diǎn)表示目標(biāo)事件(如E1、E2、E3),稱為目標(biāo)節(jié)點(diǎn).

在規(guī)則圖GR中,事件節(jié)點(diǎn)的入度表示了組成該節(jié)點(diǎn)的事件個(gè)數(shù).如圖2(a),事件節(jié)點(diǎn)b=e3∧e4∧e5,即e3～e5通過事件復(fù)合形成了b,則b的入度是3;事件節(jié)點(diǎn)e=a→b,則e的入度是2.目標(biāo)節(jié)點(diǎn)以外的事件節(jié)點(diǎn),其出度表示了該節(jié)點(diǎn)參與生成復(fù)合事件的次數(shù).若A是GR中的動作節(jié)點(diǎn),且表示規(guī)則Ri(1≤i≤n)所定義的動作,那么規(guī)則Ri的規(guī)則子圖是A可達(dá)的所有節(jié)點(diǎn)(包括A在內(nèi))組成的子圖,如圖2(b)～圖2(d)所示.規(guī)則的高度是其規(guī)則子圖從原子節(jié)點(diǎn)到動作節(jié)點(diǎn)的最大層數(shù),如圖2所示,R1、R2和R3的高度分別為5、4和6.

Fig.2 Rule graph圖2 規(guī)則圖

基于事件圖的推理過程是以到達(dá)系統(tǒng)的原子事件實(shí)例為依據(jù),通過對規(guī)則圖的搜索及規(guī)則子圖的匹配來完成的.該推理過程的具體步驟如下.

· 步驟1:原子事件實(shí)例到達(dá)系統(tǒng)后按照時(shí)間先后被送往規(guī)則圖中的原子節(jié)點(diǎn).

· 步驟2:原子節(jié)點(diǎn)接收原子事件實(shí)例后,將對其事件類型進(jìn)行匹配,而后將匹配結(jié)果送往其所有直接后繼的事件節(jié)點(diǎn).

· 步驟3:目標(biāo)節(jié)點(diǎn)以外的事件節(jié)點(diǎn)在接收到送來的事件實(shí)例后,將根據(jù)事件復(fù)合的算法[17-19]處理這些事件實(shí)例并進(jìn)行匹配,以判斷當(dāng)前節(jié)點(diǎn)的事件實(shí)例是否生成:若匹配成功,將生成新的事件實(shí)例,并把該實(shí)例送往其直接后繼的事件節(jié)點(diǎn);若匹配失敗,則轉(zhuǎn)到步驟2接收新的原子事件實(shí)例進(jìn)行匹配.

· 步驟4:若當(dāng)前的事件節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn),且該節(jié)點(diǎn)的事件實(shí)例復(fù)合并匹配成功,則將生成的事件實(shí)例送往動作節(jié)點(diǎn);若匹配失敗,則轉(zhuǎn)到步驟2接收新的原子事件實(shí)例進(jìn)行匹配.

· 步驟5:如果動作節(jié)點(diǎn)成功接收到目標(biāo)節(jié)點(diǎn)送來的事件實(shí)例,則輸出響應(yīng)動作指令,表明以該目標(biāo)節(jié)點(diǎn)為終節(jié)點(diǎn)的規(guī)則子圖已匹配完成;否則,轉(zhuǎn)到步驟2接收新的原子事件實(shí)例進(jìn)行匹配.

· 步驟6:重復(fù)步驟2～步驟5,直至所有的原子事件實(shí)例都被處理完畢.

可以看出,規(guī)則圖GR中每個(gè)節(jié)點(diǎn)上的推理操作是接收一次事件實(shí)例,對其進(jìn)行匹配并向其直接后繼節(jié)點(diǎn)傳輸;每條規(guī)則上的推理操作是對規(guī)則圖GR中相應(yīng)規(guī)則子圖的一次匹配.

2 多核環(huán)境下基于圖模型的實(shí)時(shí)規(guī)則調(diào)度方法

本節(jié)將重點(diǎn)描述如何解決多核環(huán)境下規(guī)則調(diào)度問題的難點(diǎn):(1)如何對基于事件圖的推理過程對規(guī)則調(diào)度問題進(jìn)行建模,即如何將實(shí)時(shí)規(guī)則推理過程轉(zhuǎn)化成基于圖的端到端推理任務(wù);(2)如何為推理任務(wù)合理安排執(zhí)行順序,并提出準(zhǔn)入控制算法,對推理過程中所需資源進(jìn)行預(yù)測,保證每條規(guī)則一旦被處理都能在其截止期前完成,從而保障了安全攸關(guān)系統(tǒng)中規(guī)則的實(shí)時(shí)性.

為此,本節(jié)將給出一種基于圖模型的實(shí)時(shí)規(guī)則調(diào)度方法.該方法首先通過圖映射方法為規(guī)則調(diào)度建立基于圖的端到端推理任務(wù)模型,并提出多核環(huán)境下的推理任務(wù)調(diào)度算法,從而解決多核環(huán)境下的規(guī)則調(diào)度問題.

2.1 實(shí)時(shí)規(guī)則推理過程建模

實(shí)現(xiàn)規(guī)則上的推理操作與推理任務(wù)之間的映射有兩種方法:一是直接映射,簡稱 DM;二是圖映射(graph-based mapping),簡稱 GM.

在DM方法中,把每條規(guī)則Ri(Ri∈R)上的推理操作直接映射成推理任務(wù)τi,規(guī)則集的推理過程就轉(zhuǎn)化成推理任務(wù)集τ={τ1,…,τn},τi=(ri,Ci,Di).其中,τi的參數(shù)如下.

ri是τi的就緒時(shí)間,即Ri相關(guān)聯(lián)的所有原子事件實(shí)例均到達(dá)系統(tǒng)的時(shí)間;Ci是τi的執(zhí)行時(shí)間,其數(shù)值可通過規(guī)則匹配的最壞執(zhí)行時(shí)間分析技術(shù)來獲得[20];Di是τi的相對截止期,等于Ri的相對截止期(可由應(yīng)用給定).

此外,si是τi開始執(zhí)行的時(shí)間;Ci(t)是t時(shí)刻τi的剩余執(zhí)行時(shí)間;fi是τi的完成時(shí)間,fi=min{t|Ci(t)=0};RSi是τi的響應(yīng)時(shí)間,RSi=fi-ri,RSi≤Di;di是τi的絕對截止期,di=ri+Di,fi≤di.

從第 1.2節(jié)可知,基于事件圖的實(shí)時(shí)規(guī)則推理過程是動態(tài)的.一條規(guī)則的匹配有可能因?yàn)槠湟?guī)則子圖上的任一節(jié)點(diǎn)匹配不成功而終止,其運(yùn)行時(shí)間無法事先預(yù)測.而DM方法中,只能使用規(guī)則匹配的最壞執(zhí)行時(shí)間作為推理任務(wù)的執(zhí)行時(shí)間,這過度估計(jì)了推理任務(wù)所需資源,從而降低了推理任務(wù)的調(diào)度成功率,導(dǎo)致了規(guī)則調(diào)度成功率的下降.為了更為精確地對動態(tài)的實(shí)時(shí)規(guī)則推理過程進(jìn)行描述,本文提出了GM方法,將實(shí)時(shí)規(guī)則推理過程轉(zhuǎn)化為一組基于圖的端到端推理任務(wù)(end-to-end reasoning task graph,簡稱E2ERTG).

在GM方法中,把每條規(guī)則Ri(Ri∈R)上的推理操作映射成一個(gè)端到端推理任務(wù)τi,把規(guī)則子圖中每個(gè)節(jié)點(diǎn)上的推理操作定義成τi的子任務(wù){(diào)τi,1,…,τi,j,…},則規(guī)則集的推理過程就轉(zhuǎn)化成推理任務(wù)集τ.如圖3所示,R1～R3所對應(yīng)的端到端推理任務(wù)為τ1～τ3,其中,τ1={τ1,1,…,τ1,13},τ2={τ2,1,…,τ2,7},τ3={τ3,1,…,τ3,12}.

Fig.3 Graph-based mapping圖3 圖映射

推理任務(wù)τi=(Di,{τi,j|1≤j≤ni},Gi)有以下參數(shù):Di是τi的相對截止期;{τi,j|1≤j≤ni}是τi的子任務(wù)集合;Gi是τi的子任務(wù)圖,是個(gè)有向無環(huán)圖,代表了ni個(gè)子任務(wù)之間的偏序關(guān)系.

在Gi中,若存在有向邊從τi,u指向τi,v,則τi,v是τi,u的直接后繼,τi,u是τi,v的直接前驅(qū).τi,j的直接前驅(qū)集合記為preddt(τi,j),其直接后繼集合記為succdt(τi,j).若存在τi,u到τi,v的路徑,則τi,v稱為τi,u的后繼,τi,u稱為τi,v的前驅(qū).τi,j的前驅(qū)集合記為pred(τi,j),其后繼集合記為succ(τi,j).在Gi中,沒有直接前驅(qū)的節(jié)點(diǎn)是源節(jié)點(diǎn),其代表的子任務(wù)稱為源任務(wù);沒有直接后繼的節(jié)點(diǎn)是終節(jié)點(diǎn),其代表的子任務(wù)稱為終任務(wù);其余節(jié)點(diǎn)是中間節(jié)點(diǎn),其代表的子任務(wù)稱為中間任務(wù).

值得注意的是,不同端到端推理任務(wù)的子任務(wù)可能執(zhí)行相同的操作.如圖3所示,τ1的子任務(wù)τ1,3和τ2的子任務(wù)τ2,1都執(zhí)行的是對事件e3的推理操作;τ1的子任務(wù)τ1,9和τ2的子任務(wù)τ2,5均執(zhí)行的是對事件b的推理操作.

定義1.設(shè)τi,τi+1,…,τj為一組端到端推理任務(wù),若其子任務(wù)τi,p,τi+1,l,…,τj,q所執(zhí)行的推理操作相同且任務(wù)參數(shù)也相同,則稱τi,p,τi+1,l,…,τj,q互為關(guān)聯(lián)的子任務(wù).

顯然,根據(jù)第 1.2節(jié)的實(shí)時(shí)規(guī)則推理過程,在一組互為關(guān)聯(lián)的子任務(wù)中,若其中任一子任務(wù)執(zhí)行完畢并獲得計(jì)算結(jié)果,則其余子任務(wù)便可獲得相同的執(zhí)行結(jié)果.因此,在調(diào)度中只需為其中任意一個(gè)子任務(wù)分配處理器資源即可.為此,本文引入關(guān)聯(lián)節(jié)點(diǎn)來表示互為關(guān)聯(lián)的所有子任務(wù),形成了推理任務(wù)集τ的推理任務(wù)圖Gτ,如圖4所示.

定義2(關(guān)聯(lián)子任務(wù)集Ψ).設(shè)V是Gτ中的關(guān)聯(lián)節(jié)點(diǎn)集合(節(jié)點(diǎn)個(gè)數(shù)是c),Vr(1≤r≤c)是V中的關(guān)聯(lián)節(jié)點(diǎn),則ψ(r)是Vr所表示的推理子任務(wù)集合,且.

如圖4 所示,Vr={e3,e4,e5,b,e6,e7,c,e8},其中,ψ(1)={τ1,3,τ2,1},ψ(2)={τ1,4,τ2,2},ψ(3)={τ1,5,τ2,3},ψ(4)={τ1,9,τ2,5},ψ(5)={τ1,6,τ3,1},ψ(6)={τ1,7,τ3,2},ψ(7)={τ1,10,τ3,7},ψ(8)={τ3,3,τ2,4},則

Fig.4 Reasoning task graph圖4 推理任務(wù)圖

在推理任務(wù)圖Gτ中,每個(gè)推理任務(wù)?τi(i≥1)及其子任務(wù)的參數(shù)見表1.其中可參見DM方法中的相關(guān)定義.的定義與和Ci(t)的定義類似.在此不再贅述.

Table 1 Parameters of tasks and sub-tasks表1 任務(wù)及子任務(wù)參數(shù)

若τi,k是源任務(wù),則ri,k是原子事件實(shí)例到達(dá)其相應(yīng)源節(jié)點(diǎn)的時(shí)間(即原子事件實(shí)例到達(dá)系統(tǒng)的時(shí)間);否則,ri,k是其所有直接前驅(qū)任務(wù)的最晚完成時(shí)間,即ri,k=max{fi,j},?τi,j∈preddt(τi,k).ri是所有源任務(wù)的最晚就緒時(shí)間,即ri=max{ri,k},τi,k是源任務(wù).Ci,k是τi,k在Gτ中相應(yīng)節(jié)點(diǎn)上推理操作的執(zhí)行時(shí)間;Ci是τi的最壞執(zhí)行時(shí)間,即τi所有推理子任務(wù)的最壞執(zhí)行時(shí)間之和:.若τi,k為終任務(wù),則有.

顯然,通過GM方法建立基于圖的端到端推理任務(wù)模型E2ERTG,可將多核環(huán)境下的規(guī)則調(diào)度問題RSP轉(zhuǎn)化為基于圖的端到端推理任務(wù)調(diào)度問題,即:

給定m個(gè)處理器核P={P1,P2,…,Pm}及推理任務(wù)集τ={τ1,τ2,…,τn},其中,τi=(Di,{τi,j|1≤j≤ni},Gi);任意子任務(wù)τi,j(τi,j∈τi,τi∈τ)可被分配到任意的處理器核Pi(Pi∈P)上執(zhí)行,并允許其在處理器核之間遷移.找到一種實(shí)時(shí)調(diào)度方法,使?τi(τi∈τ),fi≤di,i∈{1,2,…,n};其中,fi是端到端推理任務(wù)τi的完成時(shí)間,di是τi的絕對截止期.

為解決上述問題,下一節(jié)將給出基于圖的端到端推理任務(wù)(E2ERTG)的調(diào)度算法,通過保證所有的推理任務(wù)都在其截止期之前完成執(zhí)行,來保證規(guī)則的截止期.

2.2 推理任務(wù)調(diào)度算法

多核環(huán)境下,對基于圖的端到端推理任務(wù)進(jìn)行調(diào)度的關(guān)鍵點(diǎn)是:(1)如何實(shí)現(xiàn)推理子任務(wù)之間的同步,使其滿足子任務(wù)間的時(shí)序約束;(2)如何分配推理子任務(wù)的全局動態(tài)優(yōu)先級;(3)如何對新到達(dá)的推理子任務(wù)進(jìn)行準(zhǔn)入控制,以保證所有準(zhǔn)入的推理任務(wù)一旦執(zhí)行都將在其截止期前完成.為此,我們將提出基于圖的端到端推理任務(wù)調(diào)度算法(end-to-end reasoning task graph-based scheduling,簡稱ERTGS).

2.2.1 同步協(xié)議

同步協(xié)議的目的是為了保證推理任務(wù)圖中子任務(wù)之間由有向邊指定的時(shí)序關(guān)系,其策略為:除源任務(wù)外的子任務(wù)就緒時(shí)間等于其直接前繼任務(wù)的最晚完成時(shí)間.即

圖5是實(shí)現(xiàn)同步協(xié)議的偽代碼.對于推理任務(wù)圖中除終任務(wù)外的其他子任務(wù),將其就緒時(shí)間初始化為無窮大的整數(shù)值;鄰接矩陣adj_G存儲的是推理任務(wù)圖中子任務(wù)之間的時(shí)序關(guān)系.從鄰接矩陣adj_G獲取所有子任務(wù)的直接后繼和直接前驅(qū)任務(wù)列表(參見圖5的第3行和第5行).當(dāng)任意一個(gè)推理子任務(wù)完成時(shí),通知該子任務(wù)的所有直接后繼任務(wù)更新其直接前驅(qū)任務(wù)的完成情況(參見圖5的第7行和第12行).τi,s的所有直接前驅(qū)任務(wù)均完成時(shí),根據(jù)公式(1)更新τi,s的就緒時(shí)間(參見圖5的第9行和第13行).

Fig.5 Synchronization protocol圖5 同步協(xié)議

2.2.2 優(yōu)先級分配

ERTGS根據(jù)緊迫度和影響度為每個(gè)就緒的推理子任務(wù)τi,k分配全局的動態(tài)優(yōu)先級.

設(shè)τi,k的緊迫度為urgency(τi,k),其計(jì)算方法如下:

由公式(2)可見:對于推理任務(wù)圖Gτ中非關(guān)聯(lián)節(jié)點(diǎn)所代表的推理子任務(wù)τi,k,urgency(τi,k)是其所屬推理任務(wù)τi絕對截止期di的倒數(shù);對于Gτ中關(guān)聯(lián)節(jié)點(diǎn)Vr所代表的任意τi,k,urgency(τi,k)是ψ(r)中任意τj,l所屬推理任務(wù)τj絕對截止期的最小值之倒數(shù)(ψ(r)是Vr上所有互相關(guān)聯(lián)的推理子任務(wù)集合).推理子任務(wù)的緊迫度越大,其優(yōu)先級也越高.

當(dāng)緊迫度相同時(shí),按其影響度來決定優(yōu)先級高低.影響度越大,優(yōu)先級越高.設(shè)τi,k的影響度為effect(τi,k),對于Gτ中非關(guān)聯(lián)節(jié)點(diǎn)所代表的τi,k,effect(τi,k)是τi,k在Gτ中的出度;對于Gτ中關(guān)聯(lián)節(jié)點(diǎn)Vr所代表的任意τi,k,effect(τi,k)是ψ(r)中推理子任務(wù)的個(gè)數(shù).effect(τi,k)的計(jì)算方法如下.

其中,cnt(A)是集合A中的元素個(gè)數(shù).effect(τi,k)取值為τi,k出度和succ(τi,k)出度的最大值.

就緒的推理子任務(wù)根據(jù)公式(2)、公式(3)分配優(yōu)先級,按照遞減的順序形成優(yōu)先級隊(duì)列.若處理器核出現(xiàn)空閑,則將隊(duì)首的推理子任務(wù)從隊(duì)列中移除,并分配到該處理器核上執(zhí)行.若推理子任務(wù)執(zhí)行完畢或者有新的推理任務(wù)被準(zhǔn)入系統(tǒng)(準(zhǔn)入控制的具體方法可參見下小節(jié)),則根據(jù)公式(2)、公式(3)重新分配各就緒推理子任務(wù)的優(yōu)先級,并更新優(yōu)先級隊(duì)列.重復(fù)上述操作,直至優(yōu)先級隊(duì)列為空.

2.2.3 準(zhǔn)入控制

當(dāng)新的推理任務(wù)就緒時(shí),ERTGS將對其進(jìn)行準(zhǔn)入控制來保證所有推理任務(wù)一旦被準(zhǔn)入系統(tǒng),必將在截止期前完成,即所有被準(zhǔn)入的推理任務(wù)必定會被成功地調(diào)度,從而保證了規(guī)則集進(jìn)行調(diào)度的安全性.

定義3(t時(shí)刻的活動任務(wù)).若τa已就緒,但在t時(shí)刻未完成且未到其截止期,則τa是t時(shí)刻的活動任務(wù).

定義4(t時(shí)刻的活動任務(wù)集).在t時(shí)刻,所有的活動任務(wù)所組成的集合是t時(shí)刻的活動任務(wù)集.

定義5.基于圖的端到端推理任務(wù)集τ={τi|1≤i≤n}在推理任務(wù)調(diào)度算法 ERTGS下是可調(diào)度的任務(wù)集,當(dāng)且僅當(dāng)對于?τi(τi∈τ)均有fi≤di,fi是τi的完成時(shí)間,di是τi的絕對截止期.

定理 1.基于圖的端到端推理任務(wù)集τ={τi|1≤i≤n}在推理任務(wù)調(diào)度算法 ERTGS下是可調(diào)度的任務(wù)集,當(dāng)且僅當(dāng)對于?τi,j(i∈[1,n],j∈[1,ni])均有fi,j≤di,fi,j是τi,j的完成時(shí)間.

證明:如果對于?τi,j(i∈[1,n],j∈[1,ni])均有fi,j≤di,則根據(jù)第 2.1節(jié)中所述的推理任務(wù)模型,顯然有fi,ni=fi;因此,?τi(τi∈τ)均有fi≤di,根據(jù)定義3可知,基于圖的端到端推理任務(wù)集τ在ERTGS下是可調(diào)度的任務(wù)集.

如果基于圖的端到端推理任務(wù)集τ在ERTGS下是可調(diào)度的任務(wù)集,則根據(jù)定義3,對于?τi(τi∈τ)均有fi≤di.根據(jù)第2.1節(jié)中所述的推理任務(wù)模型,顯然有fi,j≤fi,那么fi,j≤di.

綜上所述,基于圖的端到端推理任務(wù)集τ={τi|1≤i≤n}在推理任務(wù)調(diào)度算法 ERTGS下是可調(diào)度的任務(wù)集,當(dāng)且僅當(dāng)對于?τi,j(i∈[1,n],j∈[1,ni])均有fi,j≤di,fi,j是τi,j的完成時(shí)間. □

假設(shè)τ(t)={τ1,τ2,…,τu}是t時(shí)刻可調(diào)度的活動任務(wù)集,如果t時(shí)刻新任務(wù)τr就緒,則準(zhǔn)入控制操作如下.

根據(jù)定理 1 判斷:若{τ1,τ2,…,τu}∪{τr}為可調(diào)度任務(wù)集,則τr被準(zhǔn)入;否則,τr被拒絕.

在此,τi的完成時(shí)間可如下計(jì)算:

不妨設(shè){τ1,τ2,…,τv}是按當(dāng)前優(yōu)先級遞減排序的活動任務(wù)集,處理器核個(gè)數(shù)為m,那么,

· 如果v

· 如果v≥m,則

其中,公式(5)的迭代計(jì)算方法可參見文獻(xiàn)[21],在此不再贅述.

ERTGS的準(zhǔn)入控制偽代碼如圖6所示.在此,假設(shè)τ為可調(diào)度的活動任務(wù)集,τnew為就緒的新任務(wù).

Fig.6 Admission control圖6 準(zhǔn)入控制

若處理器核的個(gè)數(shù)為m,實(shí)時(shí)規(guī)則的個(gè)數(shù)為N,則端到端推理任務(wù)的類型也有N種,不妨設(shè)所需調(diào)度的推理任務(wù)實(shí)例個(gè)數(shù)是n(實(shí)時(shí)規(guī)則可被觸發(fā)多次而產(chǎn)生多個(gè)規(guī)則推理任務(wù)的實(shí)例),基于圖的端到端推理任務(wù)模型下,推理子任務(wù)實(shí)例個(gè)數(shù)總和為w,那么DM-EDF方法時(shí)序約束控制的復(fù)雜度是O(1)(DM-EDF方法是用DM方法把規(guī)則上的推理操作映射成推理任務(wù)后用全局EDF算法[22]對其進(jìn)行調(diào)度),GBRRS方法雖然引入圖模型,其時(shí)序約束控制的復(fù)雜度仍是O(1);DM-EDF方法優(yōu)先級排序的復(fù)雜度是O(n×log2n),GBRRS方法優(yōu)先級排序的復(fù)雜度是O(w×log2w);DM-EDF方法準(zhǔn)入控制的復(fù)雜度是O(m×n2),GBRRS方法準(zhǔn)入控制的復(fù)雜度是O(m×w2).于是,DM-EDF方法的復(fù)雜度是O(1)+O(n×log2n)+O(m×n2),而GBRRS方法的復(fù)雜度是O(1)+O(w×log2w)+O(m×w2).在此,由于處理器核的個(gè)數(shù)事先給定,m為常數(shù);同時(shí),由于規(guī)則也是事先給定的,規(guī)則圖的結(jié)構(gòu)及其所包含的節(jié)點(diǎn)數(shù)也是固定的,對于每個(gè)基于圖的端到端推理任務(wù)實(shí)例來說,其子任務(wù)實(shí)例數(shù)都是它的常數(shù)倍,因此,w最多是n的常數(shù)倍,引入圖后規(guī)則調(diào)度方法的復(fù)雜度并沒有本質(zhì)提高(引入圖后規(guī)則調(diào)度方法能提高 10%以上的規(guī)則調(diào)度成功率,而這種程度的成功率提高在實(shí)際應(yīng)用中的意義是比較大的,因此還是值得引入圖來對推理任務(wù)進(jìn)行建模).

2.3 調(diào)度舉例

設(shè)處理器核的個(gè)數(shù)m=2,用DM-EDF方法和GBRRS方法來調(diào)度圖2所示的規(guī)則集R(R={R1,R2,R3}).

DM-EDF方法將R轉(zhuǎn)化成τ={τ1(3,40,42),τ2(3,19,43),τ3(4,39,43)}進(jìn)行調(diào)度,τ中推理任務(wù)的執(zhí)行順序如圖7(a)所示.其中,τ3因?yàn)橥瓿蓵r(shí)刻(為 61)錯過其絕對截止期(為 47)而被拒絕進(jìn)入系統(tǒng),即其相應(yīng)的規(guī)則R3在DMEDF方法調(diào)度下被系統(tǒng)拒絕執(zhí)行規(guī)則匹配操作.

GBRRS方法則將R轉(zhuǎn)化為推理任務(wù)圖GR如圖4所示.根據(jù)第2.1節(jié)中基于圖的端到端推理任務(wù)模型,可利用任務(wù)及其子任務(wù)的部分參數(shù)(表2中的非粗體數(shù)值)初始化它們的其余參數(shù)(表2中的粗體數(shù)值)并根據(jù)第2.2節(jié)中的推理任務(wù)調(diào)度算法對其進(jìn)行調(diào)度,τ中推理任務(wù)的執(zhí)行順序如圖7(b)所示.

Fig.7 DM-EDF and GBRRS scheduling examples圖7 DM-EDF和GBRRS方法的調(diào)度實(shí)例

從圖7(a)和圖7(b)可以反推出規(guī)則R1(正斜線),R2(橫線)和R3(反斜線)的執(zhí)行順序,由此可見,規(guī)則集R用DM-EDF方法不能被調(diào)度成功,而用 GBRRS方法則能夠被調(diào)度成功.具體來說,圖7的調(diào)度結(jié)果顯示,R1和R3的完成時(shí)間在DM-EDF方法下比GBRRS方法下都提前了17個(gè)時(shí)間單元.這是因?yàn)镚BRRS方法具有以下兩個(gè)優(yōu)點(diǎn).

· 首先,GBRRS方法的調(diào)度單元是推理子任務(wù)τi,j,能夠更充分地利用處理器的空閑資源.具體來說,

(1)GBRRS方法允許已就緒的子任務(wù)τi,j在τi就緒前開始執(zhí)行,更好地利用了處理器的空閑時(shí)間,減少了τi的等待時(shí)間.如圖7(b)中,τ1,5和τ1,6可利用τ1就緒前在t=1到t=3的時(shí)間段占用處理器運(yùn)行.

(2)GBRRS方法可利用推理任務(wù)圖的特點(diǎn),將具有相同直接前繼的多個(gè)推理子任務(wù)并行地占用處理器,提前了τi的完成時(shí)間.如圖7(b)中,τ1,2和τ1,1可并行執(zhí)行,τ3,6和τ3,5也可并行執(zhí)行,則τ1和τ3的完成時(shí)間分別提前了14個(gè)和3個(gè)時(shí)間單元.

· 其次,GBRRS方法可以及時(shí)地反映推理任務(wù)τi執(zhí)行時(shí)間的動態(tài)變化,從而反映規(guī)則對處理器資源需求的動態(tài)變化,提高了規(guī)則調(diào)度成功率.比如,GBRRS方法通過引入關(guān)聯(lián)子任務(wù)集來減少關(guān)聯(lián)子任務(wù)的重復(fù)執(zhí)行,從而提前了推理任務(wù)的完成時(shí)間.如圖7(b)中,子任務(wù)τ1,5執(zhí)行完成,互為關(guān)聯(lián)的τ2,3也執(zhí)行完成.因此,τ2和τ3分別減少了11個(gè)和16個(gè)時(shí)間單元的重復(fù)執(zhí)行,其完成時(shí)間也被提前.

Table 2 Parameter initialization of tasks and sub-tasks表2 任務(wù)和子任務(wù)的參數(shù)初始化

3 模擬實(shí)驗(yàn)

本節(jié)將通過模擬實(shí)驗(yàn)來驗(yàn)證GBRRS方法的性能,并將其與DM-EDF方法進(jìn)行對比.

3.1 模擬實(shí)驗(yàn)設(shè)置與性能指標(biāo)

為了保障測試集的合理性(本文的任務(wù)是基于安全攸關(guān)系統(tǒng)中規(guī)則推理過程建模而產(chǎn)生的,而多核環(huán)境下基于圖的端到端實(shí)時(shí)任務(wù)調(diào)度并沒有被研究,因此,已有的調(diào)度研究中沒有相關(guān)的Benchmark實(shí)例集可用),本文通過泊松分布模擬安全攸關(guān)系統(tǒng)中的原子事件實(shí)例到達(dá)情況,從而模擬出推理任務(wù)的生成,并通過設(shè)定規(guī)則事件匹配子圖相關(guān)的參數(shù)來隨機(jī)生成規(guī)則圖,從而模擬安全攸關(guān)系統(tǒng)的規(guī)則.實(shí)驗(yàn)中涉及的參數(shù)見表3.

Table 3 Parameters表3 參數(shù)

規(guī)則集的生成過程如下.

· 步驟1:隨機(jī)生成penum個(gè)原子節(jié)點(diǎn),為每個(gè)節(jié)點(diǎn)隨機(jī)選取出度(不超過outdegreemax,規(guī)則子圖中,每個(gè)節(jié)點(diǎn)的出度是該節(jié)點(diǎn)被用次數(shù)(即該節(jié)點(diǎn)上的事件被用于生成復(fù)合事件的次數(shù))的最大值)、節(jié)點(diǎn)上推理操作的執(zhí)行時(shí)間(范圍為cminmax)以及節(jié)點(diǎn)上原子事件實(shí)例的到達(dá)時(shí)間(滿足泊松分布,其參數(shù)在100～250范圍內(nèi)),那么初始候選節(jié)點(diǎn)集為這些原子節(jié)點(diǎn)(候選節(jié)點(diǎn)是被用次數(shù)小于出度的事件節(jié)點(diǎn)).

· 步驟2:隨機(jī)選取當(dāng)前規(guī)則子圖的高度(不超過topdowndepthmax),當(dāng)前規(guī)則子圖是當(dāng)前即將生成的規(guī)則所對應(yīng)規(guī)則子圖.

· 步驟3:隨機(jī)選取當(dāng)前事件節(jié)點(diǎn)的入度indegree(事件節(jié)點(diǎn)的入度是復(fù)合生成該節(jié)點(diǎn)上事件的候選節(jié)點(diǎn)的個(gè)數(shù),不超過indegreemax),從當(dāng)前的候選節(jié)點(diǎn)集中選取indegree個(gè)候選節(jié)點(diǎn),通過隨機(jī)的事件操作符復(fù)合生成當(dāng)前節(jié)點(diǎn)上的事件,則當(dāng)前事件節(jié)點(diǎn)生成完畢;更新當(dāng)前規(guī)則子圖的高度,事件節(jié)點(diǎn)的被用次數(shù)和當(dāng)前的候選節(jié)點(diǎn)集.

· 步驟4:重復(fù)步驟3,直到當(dāng)前規(guī)則子圖的高度達(dá)到topdowndepth-1(此時(shí),目標(biāo)節(jié)點(diǎn)已生成完畢)時(shí),則生成該規(guī)則子圖的動作節(jié)點(diǎn).至此,該規(guī)則子圖生成完畢,隨機(jī)選取該規(guī)則子圖的相對截止期(范圍為dminmax4rule),并更新規(guī)則集的總負(fù)載和平均負(fù)載.

· 步驟5:重復(fù)步驟2～步驟4,直到規(guī)則集的負(fù)載達(dá)到設(shè)定值.

實(shí)驗(yàn)的性能指標(biāo)是規(guī)則調(diào)度成功率:

其中,NSR是在截止期前完成的規(guī)則個(gè)數(shù),NR是被調(diào)度的規(guī)則總數(shù).

3.2 實(shí)驗(yàn)結(jié)果分析

本節(jié)給出了規(guī)則調(diào)度成功率隨規(guī)則集的平均負(fù)載UR而變化的情況,如圖8(在保持m不變的前提下,通過SR遞增使UR遞增)和圖9(在保持SR不變的前提下,通過m遞增使UR遞減)所示.令penum=1000,根據(jù)上一節(jié)所描述的方法來生成隨機(jī)的規(guī)則集,并分別用DM-EDF方法和GBRRS方法對其進(jìn)行調(diào)度.圖8和圖9中每個(gè)點(diǎn)的取值都是進(jìn)行了5次實(shí)驗(yàn)取其平均值后的結(jié)果.

由圖8可見,DM-EDF方法和GBRRS方法下的規(guī)則調(diào)度成功率都隨UR的增加而逐漸減少.GBRRS的規(guī)則調(diào)度成功率比DM-EDF的規(guī)則調(diào)度成功率平均高出14.86%,這是因?yàn)镚BRRS方法能夠及時(shí)反映推理任務(wù)執(zhí)行時(shí)間的動態(tài)變化,從而及時(shí)反映出規(guī)則對處理器資源需求的動態(tài)變化,減少了其響應(yīng)時(shí)間,增加了規(guī)則調(diào)度成功率.當(dāng)UR≤100%時(shí),兩種方法的規(guī)則調(diào)度成功率都是100%;但當(dāng)UR≥100%時(shí),隨UR的增加,兩者之間的差距先增大后減少,這是因?yàn)殛P(guān)聯(lián)子任務(wù)集出現(xiàn)的概率隨UR的增加而增加,因此,GBRRS方法的規(guī)則調(diào)度成功率下降較為平緩,兩者差距逐漸增大;當(dāng)UR≥350%時(shí),關(guān)聯(lián)子任務(wù)集在GBRRS方法中所產(chǎn)生的優(yōu)勢由于處理器資源的緊缺而逐漸不再突出,因而兩者差距又逐漸減少了.可以看出,在UR較高,如350%時(shí),GBRRS仍保持80%以上的規(guī)則調(diào)度成功率.

Fig.8 Average rule scheduling success ratio as a function ofURwhenm=8圖8m=8時(shí)隨UR變化的平均規(guī)則調(diào)度成功率

Fig.9 Average rule scheduling success ratio as a function ofmwhenSR=50圖9SR=50時(shí)隨m變化的平均規(guī)則調(diào)度成功率

圖9表明,DM-EDF方法和GBRRS方法下的規(guī)則調(diào)度成功率都隨m的增加而提高,也就是隨UR減少而提高.GBRRS的規(guī)則調(diào)度成功率比DM-EDF的規(guī)則調(diào)度成功率平均高出13.05%,這是因?yàn)镚BRRS方法的調(diào)度單元是推理子任務(wù)τi,j,能夠更充分地利用處理器的空閑資源.隨著處理器核的個(gè)數(shù)增加,兩者的差距逐漸增大.這是因?yàn)殡S著處理器核的個(gè)數(shù)增加,GBRRS方法中推理任務(wù)并行占用處理器的幾率增大,更容易被調(diào)度成功,因此,兩者的差距逐漸增大.當(dāng)m≥18時(shí),GBRRS可以成功調(diào)度規(guī)則集里的所有規(guī)則,成功率達(dá)到100%.

綜上,無論規(guī)則集的平均負(fù)載如何變化,GBRRS方法都比 DM-EDF方法在規(guī)則調(diào)度成功率上平均高出13%～ 15%;而且GBRRS方法在規(guī)則集的平均負(fù)載較高(如350%)時(shí),仍保持著80%以上的規(guī)則調(diào)度成功率.

4 結(jié)束語

為了解決多核環(huán)境下的規(guī)則調(diào)度問題,本文提出了一種基于圖的規(guī)則調(diào)度方法(GBRRS).

· 首先,GBRRS方法根據(jù)基于事件圖的推理過程,用圖映射方法對規(guī)則調(diào)度進(jìn)行了建模,提出了基于圖的端到端推理任務(wù)模型.

· 然后給出了推理任務(wù)的調(diào)度算法,通過調(diào)度這些推理任務(wù)來合理安排規(guī)則匹配與執(zhí)行的順序,從而保證了規(guī)則調(diào)度的安全性.

· 最后進(jìn)行了模擬實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明,GBRRS方法在規(guī)則調(diào)度成功率上優(yōu)于 DM-EDF方法,且在規(guī)則集的平均負(fù)載較高(如350%)時(shí),其規(guī)則調(diào)度成功率仍保持在80%以上.

在下一步工作中,我們將考慮解決以下兩個(gè)問題.

· 第一,在規(guī)則重要性不同的情況下,進(jìn)行規(guī)則調(diào)度時(shí),還需要考慮規(guī)則在不同重要性之間的切換以及在高重要性模式下截止期的優(yōu)先滿足.

· 第二,在異構(gòu)的多處理器環(huán)境下為規(guī)則分配處理器核,還需要考慮不同處理器核上處理速率的差異性.