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

作者：陈佳楠; 李哲; 李占山^*

来源：软件学报, 2021, 32(09): 2769-2782.

DOI：10.13328/j.cnki.jos.005989

• 约束满足问题
• 并行传播
• 广义弧相容
• 表约束
• 简单表缩减

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

• 单位
  吉林大学