基于多核CPU的表约束并行传播模式研究
作者:
作者单位:

作者简介:

陈佳楠(1996-),男,硕士,主要研究领域为约束规划,并行计算.
李占山(1966-),男,博士,教授,博士生导师,CCF专业会员,主要研究领域为机器学习,约束推理.
李哲(1990-),男,博士,主要研究领域为约束规划,并行计算.

通讯作者:

李占山,E-mail:zslizsli@163.com

中图分类号:

TP18

基金项目:

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


Research on Parallel Propagation Mode of Table Constraint Based on Multi-core CPU
Author:
Affiliation:

Fund Project:

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)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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.

    参考文献
    相似文献
    引证文献
引用本文

陈佳楠,李哲,李占山.基于多核CPU的表约束并行传播模式研究.软件学报,2021,32(9):2769-2782

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2019-07-22
  • 最后修改日期:2019-09-11
  • 录用日期:
  • 在线发布日期: 2021-09-15
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号