RETE網路之平行化處理

Abstract

本論文提出一個新的平行化方法，加速目前最有名的Production System 演算法：RETE。從 CPU 中常用的方法中，發現我們可以將Pipeline 的技術應用在 RETE 匹配演算法、Conflict Resolution、平行執行中。基本想法雖然簡單，但實作上會碰到一些問題，例如：資料互相干擾、語境管理等等問題。 在我們的方法中，首先我們把從 Drools 系統取得的 RETE 網路轉換成適合 Pipeline 演算法運行的版本。再來使用我們新設計的 runtime 以 Pipeline 的形式執行 Fact Propagation。我們使用Spark 實作此演算法。因分散式平行系統Spark能直接在記憶體中執行。在我們的實驗結果中，我們發現在 pipeline 技術的幫助下，我們可以減少運行跌代次數。 本論文敘述我們提出的方法、設計、我們如何解決碰到的問題以及實作上的細節。

This thesis purposes a novel parallel method to speed up the most famous production system algorithm: RETE. Inspired by the pipeline method commonly used in CPU, we apply the pipeline concept to the RETE matching algorithm and also the steps of conflict resolution and parallel firing. This idea is simple, but there are several problems that exist to apply the pipeline technology such as the data interference problem and the context management of each phase of the pipeline. In our approach, we convert the RETE created by Drools to the version needed by our pipeline algorithm. We also create a new runtime that perform the propagation with pipeline manner. We consider the distributed parallel programming system Spark as our platform of implementation, according to the properties: in-memory, distributed. In our experiment, we found that this method can reduce the iteration of execution. The thesis describes the methodology, the design, the problem we conquered and the implementation of our approach.