一種EPCCL理論編譯算法

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