[發明專利]一種面向內存受限環境的高性能規則匹配方法

有效

• 申請號: 201910347564.5
• 申請日: 2019-04-28
• 公開（公告）號: CN110175676B
• 公開（公告）日: 2021-04-20
• 發明（設計）人: 王宏安;姚媛;喬穎
• 申請（專利權）人: 中國科學院軟件研究所;國網遼寧省電力有限公司電力科學研究院
• 主分類號: G06N5/04
• 分類號: G06N5/04
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 司立彬

1.一種面向內存受限環境的高性能規則匹配方法，其步驟包括：

1)將目標領域的規則集解析生成RETE網絡；在RETE網絡中，對于每一條規則，從β網絡根節點到規則終止節點路徑上的β節點構成了該規則的規則路徑；每條規則都對應一塊規則內存單元RMU，用于增量存儲該規則路徑上每個β節點的PM數據，共同構成一條規則約束的PM之間使用邊進行相連；同一規則路徑上的所有β節點共享對應規則的規則內存單元RMU；每個β節點設有一β內存，分為左存儲區和右存儲區，左存儲區用來存儲從其前驅β節點傳遞來的PM結果及其在RMU中的位置，右存儲區用來存儲從與該β節點相連的α節點處傳遞來的AM數據；其中PM為滿足β節點對應約束的事實數據；

2)對于一待處理的事實數據F，將該事實數據F依次與該RETE網絡中各個節點的約束進行匹配，直至葉子節點或沒有滿足約束的節點，獲取與該事實數據F匹配的推理結果；具體方法為：

21)將該事實數據F與該RETE網絡中的α網絡內的α節點進行匹配，得到與該事實數據F的事實類型所對應的α節點，然后根據得到的每一α節點對應的約束對該事實數據F的屬性和值進行判斷，若滿足約束，則將該事實數據F封裝成為AM傳遞到滿足約束的α節點所有后繼β節點中，并且將這些β節點激活并加入到相應的激活隊列中等待調度，并啟動調度機制；

22)調度機制從激活隊列中選取節點進行調度處理；若當前所選β節點接收到的是AM，則獲取該β節點和對應的AM后，將AM存儲在該β節點右存儲區中；

23)β節點將新收到的AM與已有的PM進行約束匹配，得到與該AM成功匹配的PM；

24)如果有成功匹配的PM，則將該AM添加到該PM所在的規則內存單元RMU中，并將該AM與對應的PM相連，然后將該AM及其在RMU中的位置封裝成新的PM傳遞給所有后繼β節點，并且將這些后繼β節點激活，按照設置的放置機制加入到相應的激活隊列中等待調度，并啟動調度機制；

25)調度機制從激活隊列中選取節點進行調度處理，若當前所選β節點接收到的是PM，則獲取β節點和對應的PM后，將PM存儲在β節點的左存儲區中；

26)β節點將新收到的PM與已有的AM進行約束匹配，得到與該PM成功匹配的AM，然后在該PM所在的規則內存單元RMU中往當前β節點所在層上添加該AM，并與與之匹配成功的上一層PM數據相連，然后將該AM及其在RMU中的位置封裝成新的PM傳遞給所有后繼β節點，并且將這些β節點激活，按照放置機制加入到相應的激活隊列中等待調度，并啟動調度機制；

27)重復步驟25)～26)，將每次新生成的PM沿著規則路徑不斷往后繼節點傳遞，直至抵達規則終止節點，得到與該事實數據F匹配的推理結果。

2.如權利要求1所述的方法，其特征在于，將β節點激活并加入到相應的激活隊列中的方法為：

31)根據RETE網絡構建一張任務關系圖；其中，RETE網絡中的β網絡內節點對應任務關系圖中的節點，根據β網絡中節點相連關系連接在任務關系圖中的節點；該任務關系圖為無向圖；

32)將β網絡的根節點在任務關系圖中對應的節點作為源點，從源點開始依次對任務關系圖中節點進行著色，將源點著為紅色，與源點相連的節點著為黑色，每當遇到還未著色的節點，選取與之相連的已著色節點的對立顏色對該節點進行著色，直至整個任務圖都著色完畢，得到紅黑兩種顏色的節點集合，即兩個互斥節點集；同種顏色的節點集合里任意一對節點所對應的任務并行執行，不同顏色的節點集合里至少有一對節點所對應的任務不能并行執行；

33)設置兩激活隊列，每一激活隊列對應一種顏色的節點集合；當β網絡中任一β節點被激活時，根據該β節點所屬的節點集合將其加入到對應的激活隊列中。

3.如權利要求2所述的方法，其特征在于，調度機制從激活隊列中選取節點進行調度處理的方法為：調度機制先比較兩個激活隊列中的節點數量，選擇其中節點更多的激活隊列，再按照節點進入所選激活隊列時的先后順序，從隊首取出N個節點，分配給N個CPU核去完成匹配任務；當被選擇的激活隊列為空時，調度機制選擇另一激活隊列進行調度；其中，N為可并發執行的線程個數。