一種EPCCL理論編譯算法
超擴展規則是對擴展規則的擴充，基于超擴展規則能夠求得任意兩個非互補且不相互蘊含的子句所能擴展出極大項集的交集、差集和并集，并將所得結果以EPCCL（each pair of clauses contains complementary literals）理論的形式保存．基于超擴展規則的性質，提出一種EPCCL理論編譯算法：求交知識編譯算法IKCHER（intersection approach to knowledge compilation based on hyper extension rule）．該算法適合難解類SAT問題的知識編譯，也是一種可并行的知識編譯算法．研究了如何實現多個EPCCL理論的求交操作。證明了EPCCL理論的求交過程是可并行執行的，并設計了相應的并行求交算法PIAE（parellel intersection of any number of EPCCL）．通過對輸入EPCCL理論對應普通子句集的利用，設計了一種高效的并行求交算法imp-PIAE（improvement of PIAE）．基于上述算法，還設計了兩種并行知識編譯算法P-IKCHER（IKCHER with PIAE）和impP-IKCHER（IKCHER with imp-PIAE）。分別采用PIAE并行合并算法和imp-PUAE并行合并算法．最后，通過實驗驗證了，大部分情況下，IKCHER算法的編譯質量是目前為止所有EPCCL理論編譯器中最優的．P-IKCHER算法所使用的合并策略并沒有起到加速的效果，反而使得編譯效率和編譯質量有所下降；impP-IKCHER算法提高了IKCHER算法的編譯效率，CPU四核環境下最高可提高2倍．
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%