Page 145 - 《软件学报》2021年第9期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(9):2769−2782 [doi: 10.13328/j.cnki.jos.005989] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
基于多核 CPU 的表约束并行传播模式研究

2,3
1,3
陈佳楠 , 李 哲 , 李占山 1,2,3
1
(吉林大学 软件学院,吉林 长春 130012)
2 (吉林大学 计算机科学与技术学院,吉林 长春 130012)
3 (符号计算与知识工程教育部重点实验室(吉林大学),吉林 长春 130012)
通讯作者: 李占山, E-mail: zslizsli@163.com

摘 要: 并行传播是并行约束程序领域中的一个研究方向,其研究内容是如何并行执行在约束上的过滤算法.根
据维持表约束网络广义弧相容(generalized arc consistency,简称 GAC)的串行传播模式,提出了维持表约束网络临时
广义弧相容(temporary generalized arc consistency,简称 TGAC)的并行传播模式,该模式基于多核 CPU,由并行传播算
法和并行过滤算法两部分组成;之后,给出了并行传播模式的可靠性证明,而且通过对并行传播模式的最坏时间复杂
度分析,可以认为并行传播模式在平均过滤时间较长的实例上要快于串行传播模式;最终的实验结果也验证了上述
结论,并行传播模式在多数实例集上取得了从 1.4~3.4 不等的加速比.
关键词: 约束满足问题;并行传播;广义弧相容;表约束;简单表缩减
中图法分类号: TP18

中文引用格式: 陈佳楠,李哲,李占山.基于多核 CPU 的表约束并行传播模式研究.软件学报,2021,32(9):2769−2782. http://
www.jos.org.cn/1000-9825/5989.htm
英文引用格式: Du RZ, Li MY, Tian JF, Wu WQ. Research on parallel propagation mode of table constraint based on multi-core
CPU. Ruan Jian Xue Bao/Journal of Software, 2021,32(9):2769−2782 (in Chinese). http://www.jos.org.cn/1000-9825/5989.htm

Research on Parallel Propagation Mode of Table Constraint Based on Multi-core CPU
1,3
2,3
CHEN Jia-Nan , LI Zhe , LI Zhan-Shan 1,2,3
1 (College of Software, Jilin University, Changchun 130012, China)
2 (College of Computer Science and Technology, Jilin University, Changchun 130012, China)
3 (Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012,
China)
Abstract: Parallel propagation is a research direction in the field of parallel constraint programming, and its research content is how to
implement filtering algorithms on constraints in parallel. According to the serial propagation mode which enforces generalized arc
consistency (GAC) on table constraint network, this study proposes a parallel propagation mode to enforce temporary generalized arc
consistency (TGAC) on table constraint network. This mode is based on multi-core CPU and consists of parallel propagation algorithm
and parallel filtering algorithm. After that, the reliability of the parallel propagation mode is proved, and through the analysis of the worst
case time complexity of the parallel propagation mode, it is also demonstrated that the parallel propagation mode is faster than the serial
propagation mode in instances of which the average filtering time is longer. Finally, the experimental results also confirm the above
conclusion, and the parallel propagation mode achieves a speed-up ratio ranging from 1.4 to 3.4 on most series.

∗ 基金项目: 国家自然科学基金(61802056); 吉林省自然科学基金(2018010143JC); 吉林省发展和改革委员会产业技术研究与
开发项目(2019C053-9); 中国科学院太空应用重点实验室开放基金课题(LSU-KFJJ-2019-08)
Foundation item: National Natural Science Foundation of China (61802056); Natural Science Foundation of Jilin Province
(2018010143JC); Industrial Technology Research and Development Project of Jilin Development and Reform Commission (2019C053-9);
Open Research Fund of Key Laboratory of Space Utilization, Chinese Academy of Sciences(LSU-KFJJ-2019-08)
收稿时间: 2019-07-22; 修改时间: 2019-09-11; 采用时间: 2019-12-03