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

doi:10.3969/j.issn.0372-2112.2018.03.004

电子学报 ›› 2018, Vol. 46 ›› Issue (3): 537-543.DOI: 10.3969/j.issn.0372-2112.2018.03.004

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

牛当当¹, 刘磊¹, 吕帅^1,2

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

收稿日期:2016-07-15 修回日期:2016-12-15 出版日期:2018-03-25
- 通讯作者:
- 吕帅
- 作者简介:
- 牛当当,男,1990年2月出生,陕西周至人.现为吉林大学计算机科学与技术学院博士研究生,主要研究方向为自动推理和抽象论辩.E-mail:ddniu15@mails.jlu.edu.cn;刘磊,男,1960年8月出生,吉林长春人.现为吉林大学计算机科学与技术学院教授、博士生导师,主要研究方向为软件理论与技术.E-mail:liulei@jlu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61300049，No.61502197，No.61503044）; 教育部高等学校博士学科点专项科研基金 (No.20120061120059）; 吉林省青年科研基金项目 (No.20140520069JH，No.20150520058JH）; 吉林省自然科学基金项目 (No.20150101054JC）

Parallel Knowledge Compilation Algorithms for EPCCL Theory

NIU Dang-dang¹, LIU Lei¹, LÜ Shuai^1,2

1. College of Computer Science and Technology, Jilin University, Changchun, Jilin 130012, China;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Ministry of Education, Changchun, Jilin 130012, China

Received:2016-07-15 Revised:2016-12-15 Online:2018-03-25 Published:2018-03-25
- Corresponding author:
- LÜ Shuai

摘要/Abstract

摘要： 基于超扩展规则，证明了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）和impP-UKCHER（UKCHER with imp-PUAE）.实验结果表明：P-UKCHER算法虽然没有提升UKCHER算法的效率，但能够提升UKCHER算法编译结果的质量，最好情况下可提升4倍；而impP-UKCHER算法能够提高UKCHER算法的效率，同时也能够提升编译结果的质量，同样最好情况下可提升4倍.

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

Abstract: 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.

Key words: knowledge compilation, extension rule, hyper extension rule, EPCCL theory, parallel compilation

中图分类号:

TP301
TP181

牛当当, 刘磊, 吕帅. EPCCL理论的并行知识编译算法[J]. 电子学报, 2018, 46(3): 537-543.

NIU Dang-dang, LIU Lei, LÜ Shuai. Parallel Knowledge Compilation Algorithms for EPCCL Theory[J]. Acta Electronica Sinica, 2018, 46(3): 537-543.

参考文献

[1] Darwiche A,Marquis P.A knowledge compilation map[J].Journal of Artificial Intelligence Research,2002,17(1):229-264.
[2] Fargier H,Marquis P,Niveau A.Towards a knowledge compilation map for heterogeneous representation languages[A].Proceedings of the 23rd International Joint Conference on Artificial Intelligence[C].Beijing,China:IJCAI,2013.877-883.
[3] Fargier H,Marquis P,Niveau A,Schmidt N.A knowledge compilation map for ordered real-valued decision diagrams[A].Proceedings of the 28th National Conference on Artificial Intelligence[C].Québec,Canada:AAAI Press,2014.1049-1055.
[4] Fargier H,Marquis P.Disjunctive closures for knowledge compilation[J].Artificial Intelligence,2014,216(16):129-162.
[5] Kazemi S M,Poole D.Knowledge compilation for lifted probabilistic inference:Compiling to a low-level language[A].Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning[C].Cape Town,South Africa:AAAI Press,2016.561-564.
[6] Lai Y,Liu D Y,Wang S S.Reduced ordered binary decision diagram with implied literals:A new knowledge compilation approach[J].Knowledge and Information Systems,2013,35(3):665-712.
[7] 申元霞,曾传华,王喜凤,江小燕.并行协作骨干粒子群优化算法[J].电子学报,2016,44(7):1643-1648. SHEN Yuan-Xia,ZENG Chuan-Hua,WANG Xi-Feng,JIANG Xiao-Yan.A parallel-cooperative bare-bone particle swarm optimization algorithm[J].Acta Electronica Sinica,2016,44(7):1643-1648.(in Chinese)
[8] Huang Y F,Xiao J H,Jiang K Q,Chen Z H.Parallel solution for maximum independent set problem by programmable tile assembly[J].Chinese Journal of Electronics,2016,25(2):203-208.
[9] 王伟,余玉揆,郝燕玲.一种新型混合并行粒子滤波频率估计方法[J].电子学报,2016,44(3):740-746. WANG Wei,YU Yu-Kui,HAO Yan-Ling.A novel parallel particle filter for frequency estimation[J].Acta Electronica Sinica,2016,44(3):740-746.(in Chinese)
[10] Katsirelos G,Sabharwal A,Samulowitz H,Simon L.Resolution and parallelizability:Barriers to the efficient parallelization of SAT solvers[A].Proceedings of the 27th National Conference on Artificial Intelligence[C].Bellevue,Washington:AAAI Press,2013.481-488.
[11] Lin H,Sun J G,Zhang Y M.Theorem proving based on the extension rule[J].Journal of Automated Reasoning,2003,31(1):11-21.
[12] Lin H,Sun J G.Knowledge compilation using the extension rule[J].Journal of Automated Reasoning,2004,32(2):93-102.
[13] 谷文祥,王金艳,殷明浩.基于MCN和MO启发式策略的扩展规则知识编译方法[J].计算机研究与发展,2011,48(11):2064-2073. GU Wen-Xiang,WANG Jin-Yan,YIN Ming-Hao.Knowledge compilation using extension rule based on MCN and MO heuristic strategies[J].Journal of Computer Research and Development,2011,48(11):2064-2073.(in Chinese)
[14] 刘大有,赖永,林海.C2E:一个高性能的EPCCL理论编译器[J].计算机学报,2013,36(6):1254-1260. LIU Da-You,LAI Yong,LIN Hai.C2E:An EPCCL compiler with good performance[J].Chinese Journal of Computer,2013,36(6):1254-1260.(in Chinese)
[15] 刘磊,牛当当,李壮,吕帅.基于超扩展规则的动态在线推理算法[J].哈尔滨工程大学学报,2015,36(12):1614-1619. LIU Lei,NIU Dang-Dang,LI Zhuang,LÜ Shuai.Dynamic online reasoning algorithm based on the hyper extension rule[J].Journal of Harbin Engineering University,2015,36(12):1614-1619.(in Chinese)
[16] 刘磊,牛当当,吕帅.基于超扩展规则的知识编译方法[J].计算机学报,2016,39(8):1681-1696. LIU Lei,NIU Dang-Dang,LV Shuai.Knowledge compilation methods based on the hyper extension rule[J].Chinese Journal of Computers,2016,39(8):1681-1696.(in Chinese)
[17] 牛当当,刘磊,吕帅.EPCCL理论的求交知识编译算法[J].软件学报,2017,28(8):2096-2112. NIU Dang-Dang,LIU Lei,LV Shuai.Knowledge compilation algorithm based on computing the intersection for EPCCL theories[J].Journal of Software,2017,28(8):2096-2112.(in Chinese)

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

Parallel Knowledge Compilation Algorithms for EPCCL Theory

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	王金艳, 胡春, 牛当当, 李先贤. 基于IAPS的扩展规则局部搜索算法[J]. 电子学报, 2020, 48(5): 899-905.
[2]	牛当当, 吕帅, 王金艳, 刘斌. 基于MACR和CAL启发式的求差知识编译算法[J]. 电子学报, 2020, 48(2): 285-290.
[3]	牛当当, 吕帅, 王金艳. 基于MOVR启发式的求差知识编译算法[J]. 电子学报, 2019, 47(11): 2299-2303.