EPCCL理论的并行知识编译算法  

Parallel Knowledge Compilation Algorithms for EPCCL Theory

作　　者：牛当当 刘磊[1] 吕帅[1,2] NIU Dang-dang;LIU Lei;LüShuai(College of Computer Science and Technology,Jilin University,Changchun,Jilin 130012,China;Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University),Ministry of Education,Changchun,Jilin 130012,China)

机构地区：[1]吉林大学计算机科学与技术学院,吉林长春130012 [2]符号计算与知识工程教育部重点实验室(吉林大学),吉林长春130012

出　　处：《电子学报》2018年第3期537-543,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61300049;No.61502197;No.61503044);教育部高等学校博士学科点专项科研基金(No.20120061120059);吉林省青年科研基金项目(No.20140520069JH;No.20150520058JH);吉林省自然科学基金项目(No.20150101054JC)

摘　　要：基于超扩展规则,证明了EPCCL(Each Pair Contains Complementary Literal)理论的合并过程是可并行执行的,并设计了针对多个EPCCL理论的并行合并算法PUAE(Parallel computing Union of Any number of EPCCL).通过对EPCCL理论原始子句集的利用,提出了另一种高效的EPCCL理论并行合并算法imp-PUAE(improvement of PUAE).UKCHER(computing Union sets of maximum terms for Knowledge Compilation based on Hyper Extension Rule)是一种可并行的EPCCL理论编译算法,分别利用PUAE和imp-PUAE设计了两个并行知识编译算法P-UKCHER(UKCHER with PUAE)和imp P-UKCHER(UKCHER with imp-PUAE).实验结果表明:P-UKCHER算法虽然没有提升UKCHER算法的效率,但能够提升UKCHER算法编译结果的质量,最好情况下可提升4倍;而imp P-UKCHER算法能够提高UKCHER算法的效率,同时也能够提升编译结果的质量,同样最好情况下可提升4倍.Based on HER(hyper extension rule),we prove that the parallelization of merging multiple EPCCL(each pair contains complementary literal)is feasible,and the corresponding algorithm PUAE(parallel computing union of any number of EPCCL)is proposed.Through using the origin CNF formulae of EPCCL theories,another efficient merging algorithm imp-PUAE(improvement of PUAE)is proposed.UKCHER(computing union sets of maximum terms for knowledge compilation based on hyper extension rule)is a knowledge compilation algorithm for EPCCL,which can be parallelized.Based on the above methods,we proposed two parallel knowledge compilation algorithms i.e.,P-UKCHER(UKCHER with PUAE)and impP-UKCHER(UKCHER with imp-PUAE),which use the PUAE algorithm and imp-PUAE algorithm,respectively.Experimentally,although P-UKCHER does not improve the efficiency of UKCHER,the compilation quality is improved.In the best case,the compilation quality can be improved by 4 times with P-UKCHER.The impP-UKCHER can improve the efficiency and compilation quality of UKCHER at the same time,and the compilation quality can also be improved by 4 times in the best case.

关 键 词：知识编译 扩展规则 超扩展规则 EPCCL理论 并行编译 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TP181[自动化与计算机技术—计算机科学与技术]