[發(fā)明專利]一種分布式實(shí)時(shí)規(guī)則推理調(diào)度方法

有效

• 申請?zhí)枺?/td>: 202010581392.0
• 申請日: 2020-06-23
• 公開（公告）號: CN111814981B
• 公開（公告）日: 2021-03-30
• 發(fā)明（設(shè)計(jì)）人: 彭程;喬穎;劉鴻儒;王宏安
• 申請（專利權(quán)）人: 中國科學(xué)院軟件研究所
• 主分類號: G06N5/04
• 分類號: G06N5/04
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理有限公司 11200
• 代理人: 司立彬

1.一種分布式實(shí)時(shí)規(guī)則推理調(diào)度方法，其步驟包括：

1)建立產(chǎn)生式規(guī)則集所對應(yīng)的規(guī)則圖；

2)將所述規(guī)則圖轉(zhuǎn)化成數(shù)據(jù)操作圖；

3)規(guī)則推理系統(tǒng)根據(jù)收到的事實(shí)對象將所述數(shù)據(jù)操作圖切分為多個(gè)子圖，并為每個(gè)子圖生成一個(gè)推理作業(yè)；

4)根據(jù)推理作業(yè)的處理時(shí)間長短設(shè)置推理作業(yè)的優(yōu)先級，并在規(guī)則推理系統(tǒng)中創(chuàng)建n個(gè)調(diào)度隊(duì)列，得到一調(diào)度隊(duì)列集合Q＝{q₁,q₂,…,q_n}；其中n為規(guī)則數(shù)，每條規(guī)則對應(yīng)一個(gè)調(diào)度隊(duì)列，q_n為第n條規(guī)則對應(yīng)的調(diào)度隊(duì)列，分別為每個(gè)調(diào)度隊(duì)列設(shè)置不同的權(quán)值屬性，根據(jù)優(yōu)先級與權(quán)值的對應(yīng)關(guān)系將推理作業(yè)調(diào)入對應(yīng)的調(diào)度隊(duì)列中，其中優(yōu)先級越高的推理作業(yè)放入權(quán)值越大的調(diào)度隊(duì)列；其中對生成的推理作業(yè)進(jìn)行優(yōu)先級設(shè)置的方法為：41)將每一子圖作為一推理作業(yè)Job執(zhí)行圖，設(shè)規(guī)則推理系統(tǒng)中執(zhí)行器進(jìn)行一次計(jì)算的時(shí)間為μ；對于第i個(gè)推理作業(yè)Job執(zhí)行圖，即推理作業(yè)Job_i執(zhí)行圖，從當(dāng)前推理作業(yè)Job_i執(zhí)行圖的起始頂點(diǎn)開始寬度優(yōu)先遍歷：設(shè)置初始數(shù)據(jù)元組個(gè)數(shù)為0，若后繼頂點(diǎn)由前驅(qū)頂點(diǎn)經(jīng)過filter操作而來，則直接將初始數(shù)據(jù)元組個(gè)數(shù)累加前驅(qū)頂點(diǎn)中元組個(gè)數(shù)；若后繼頂點(diǎn)由前驅(qū)頂點(diǎn)經(jīng)過cartesian操作而來，則將數(shù)據(jù)元組個(gè)數(shù)加上其前驅(qū)頂點(diǎn)中元組的乘積，直到遍歷到當(dāng)前推理作業(yè)Job_i執(zhí)行圖的終止頂點(diǎn)結(jié)束，最后的元組數(shù)目總和表示執(zhí)行完該推理作業(yè)Job_i執(zhí)行圖總共需要計(jì)算的次數(shù)C_i；42)統(tǒng)計(jì)該推理作業(yè)Job_i執(zhí)行圖中涉及的所有輸入頂點(diǎn)的數(shù)據(jù)元組總和e_i，則該推理作業(yè)Job_i執(zhí)行圖對應(yīng)的推理作業(yè)的優(yōu)先級為filter操作為數(shù)據(jù)集過濾操作，用于過濾數(shù)據(jù)集中不符合給定條件的約束的數(shù)據(jù)；cartesian操作用于對兩個(gè)數(shù)據(jù)集進(jìn)行笛卡爾積計(jì)算，形成新的數(shù)據(jù)集，并在此新的數(shù)據(jù)集中過濾不符合不同條件元素間屬性約束的數(shù)據(jù)；

5)當(dāng)不同調(diào)度隊(duì)列中同時(shí)有就緒任務(wù)提交時(shí)，規(guī)則推理系統(tǒng)從有任務(wù)就緒的調(diào)度隊(duì)列中選擇權(quán)值最大的調(diào)度隊(duì)列q_i中的推理作業(yè)，創(chuàng)建并執(zhí)行推理任務(wù)；

6)推理任務(wù)執(zhí)行結(jié)束時(shí)將其對應(yīng)的推理作業(yè)從所屬調(diào)度隊(duì)列中刪除，并判斷所屬調(diào)度隊(duì)列是否為空隊(duì)列：若不是空隊(duì)列則繼續(xù)執(zhí)行步驟5)，直至所有調(diào)度隊(duì)列都為空。

2.如權(quán)利要求1所述的方法，其特征在于，所述規(guī)則圖為RETE網(wǎng)絡(luò)；所述數(shù)據(jù)操作圖為有向無環(huán)圖，即DAG圖；將規(guī)則圖轉(zhuǎn)化成相應(yīng)的數(shù)據(jù)操作圖的方法為：

21)創(chuàng)建一個(gè)根節(jié)點(diǎn)root；

22)依次處理RETE網(wǎng)絡(luò)中的α節(jié)點(diǎn)，在數(shù)據(jù)操作圖中加入一個(gè)新頂點(diǎn)表示當(dāng)前α節(jié)點(diǎn)對應(yīng)的α內(nèi)存中的事實(shí)；

23)依次處理RETE網(wǎng)絡(luò)中的β節(jié)點(diǎn)，在數(shù)據(jù)操作圖中加入一個(gè)新頂點(diǎn)表示當(dāng)前β節(jié)點(diǎn)對應(yīng)的β內(nèi)存中的部分匹配。

3.如權(quán)利要求2所述的方法，其特征在于，步驟22)中，對于RETE網(wǎng)絡(luò)中的兩個(gè)α節(jié)點(diǎn)x,y，若兩節(jié)點(diǎn)x,y之間存在邊x,y，則在數(shù)據(jù)操作圖中添加邊V_x,V_y；其中V_x表示節(jié)點(diǎn)x對應(yīng)的α內(nèi)存中所有事實(shí)形成的數(shù)據(jù)集D_x對應(yīng)的頂點(diǎn)，V_y表示節(jié)點(diǎn)y對應(yīng)的α內(nèi)存中的所有事實(shí)形成的數(shù)據(jù)集D_y對應(yīng)的頂點(diǎn)。

4.如權(quán)利要求3所述的方法，其特征在于，邊V_x,V_y所對應(yīng)的操作為filter操作，filter操作用于過濾數(shù)據(jù)集D_x中不符合節(jié)點(diǎn)y所對應(yīng)約束的事實(shí)，從而得到數(shù)據(jù)集D_y。