软件学报

作者：陈佳楠，李哲，李占山

单位：陈佳楠，吉林大学软件学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001211,李哲，吉林大学计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001202,李占山，吉林大学软件学院, 吉林 长春 130012;吉林大学计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001203

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

基金：国家自然科学基金（61802056）；吉林省自然科学基金（2018010143JC）；吉林省发展和改革委员会产业技术研究与开发项目（2019C053-9）；中国科学院太空应用重点实验室开放基金课题（LSU-KFJJ-2019-08）

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

来源：2021年第9期

《软件学报》期刊编辑部

查看软件学报杂志2021年第9期