| 基于多核CPU的表约束并行传播模式研究 |
| |
| 引用本文： | 陈佳楠,李哲,李占山. 基于多核CPU的表约束并行传播模式研究[J]. 软件学报, 2021, 32(9): 2769-2782 |
| |
| 作者姓名： | 陈佳楠 李哲 李占山 |
| |
| 作者单位： | 吉林大学软件学院,吉林长春 130012;符号计算与知识工程教育部重点实验室(吉林大学),吉林长春 130012;吉林大学计算机科学与技术学院,吉林长春 130012;符号计算与知识工程教育部重点实验室(吉林大学),吉林长春 130012;吉林大学软件学院,吉林长春 130012;吉林大学计算机科学与技术学院,吉林长春 130012;符号计算与知识工程教育部重点实验室(吉林大学),吉林长春 130012 |
| |
| 基金项目： | 国家自然科学基金（61802056）；吉林省自然科学基金（2018010143JC）；吉林省发展和改革委员会产业技术研究与开发项目（2019C053-9）；中国科学院太空应用重点实验室开放基金课题（LSU-KFJJ-2019-08） |
| |
| 摘 要： | 并行传播是并行约束程序领域中的一个研究方向,其研究内容是如何并行执行在约束上的过滤算法.根据维持表约束网络广义弧相容(generalized arc consistency,简称GAC)的串行传播模式,提出了维持表约束网络临时广义弧相容(temporary generalized arc consistency,简称T...
|
| 关 键 词： | 约束满足问题 并行传播 广义弧相容 表约束 简单表缩减 |
| 收稿时间： | 2019-07-22 |
| 修稿时间： | 2019-09-11 |
Research on Parallel Propagation Mode of Table Constraint Based on Multi-core CPU |
| |
| CHEN Jia-Nan,LI Zhe,LI Zhan-Shan. Research on Parallel Propagation Mode of Table Constraint Based on Multi-core CPU[J]. Journal of Software, 2021, 32(9): 2769-2782 |
| |
| Authors: | CHEN Jia-Nan LI Zhe LI Zhan-Shan |
| |
| Affiliation: | College of Software, Jilin University, Changchun 130012, China;Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012, China;College of Computer Science and Technology, Jilin University, Changchun 130012, China;Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012, China; College of Software, Jilin University, Changchun 130012, China;College of Computer Science and Technology, Jilin University, Changchun 130012, China;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. |
| |
| Keywords: | constraint satisfaction problem parallel propagation generalized arc consistency table constraint simple tabular reduction |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
