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

摘要：

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

关键词：约束满足问题;并行传播;广义弧相容;表约束;简单表缩减

所属期刊栏目：32

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金;吉林省自然科学基金;吉林省发展和改革委员会产业技术研究;开发项目;中国科学院太空应用重点实验室开放基金课题

在线出版日期：2021-09-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：2769-2782