• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Li Zhe, Li Zhanshan, Li Ying. A Constraint Network Model and Parallel Arc Consistency Algorithms Based on GPU[J]. Journal of Computer Research and Development, 2017, 54(3): 514-528. DOI: 10.7544/issn1000-1239.2017.20150912
Citation: Li Zhe, Li Zhanshan, Li Ying. A Constraint Network Model and Parallel Arc Consistency Algorithms Based on GPU[J]. Journal of Computer Research and Development, 2017, 54(3): 514-528. DOI: 10.7544/issn1000-1239.2017.20150912

A Constraint Network Model and Parallel Arc Consistency Algorithms Based on GPU

More Information
  • Published Date: February 28, 2017
  • Constraint satisfaction problem is a popular paradigm to deal with combinatorial problems in artificial intelligence. Arc consistency (AC) is one of basic solution compression algorithms of constraint satisfaction problem, which is also a core algorithm of many excellent advanced algorithms. When constraints are considered independently, AC corresponds to the strongest form of local reasoning. An effective underlying AC can improve the efficiency of reducing the search space. Recent years, GPU has been used for constituting many super computers, which solve many problems in parallel. Based on GPU's computation, this paper proposes a constraint networks presentation model N-E and its parallel generation algorithm BuildNE. According to fine-grained arc consistency AC4, a parallel edition AC4\+GPU and its improved algorithm—AC4\+GPU, are proposed. The two parallel algorithms extend arc consistency to GPU. Experimental results verify the feasibility of these new algorithms. Compared with AC4, the parallel versions have made the 10% to 50% acceleration in some smaller instances, and obtained 1 to 2 orders of magnitude in some bigger instances. They provide a core algorithm to other constraint satisfaction problem solving in parallel for further study.
  • Related Articles

    [1]Sun Qingxiao, Yang Hailong. Generalized Stencil Auto-Tuning Framework on GPU Platform[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440612
    [2]Li Maowen, Qu Guoyuan, Wei Dazhou, Jia Haipeng. Performance Optimization of Neural Network Convolution Based on GPU Platform[J]. Journal of Computer Research and Development, 2022, 59(6): 1181-1191. DOI: 10.7544/issn1000-1239.20200985
    [3]Zhang Shuai, Li Tao, Jiao Xiaofan, Wang Yifeng, Yang Yulu. Parallel TNN Spectral Clustering Algorithm in CPU-GPU Heterogeneous Computing Environment[J]. Journal of Computer Research and Development, 2015, 52(11): 2555-2567. DOI: 10.7544/issn1000-1239.2015.20148151
    [4]Luo Xinyuan, Chen Gang, Wu Sai. A GPU-Accelerated Highly Compact and Encoding Based Database System[J]. Journal of Computer Research and Development, 2015, 52(2): 362-376. DOI: 10.7544/issn1000-1239.2015.20140254
    [5]Tang Liang, Luo Zuying, Zhao Guoxing, and Yang Xu. SOR-Based P/G Solving Algorithm of Linear Parallelism for GPU Computing[J]. Journal of Computer Research and Development, 2013, 50(7): 1491-1500.
    [6]Cai Yong, Li Guangyao, and Wang Hu. Parallel Computing of Central Difference Explicit Finite Element Based on GPU General Computing Platform[J]. Journal of Computer Research and Development, 2013, 50(2): 412-419.
    [7]Wang Zhuowei, Xu Xianbin, Zhao Wuqing, He Shuibing, Zhang Yuping. Parallel Acceleration and Performance Optimization for GRAPES Model Based on GPU[J]. Journal of Computer Research and Development, 2013, 50(2): 401-411.
    [8]Wu Xiaoxiao, Liang Xiaohui, Xu Qidi, and Zhao Qinping. An Algorithm of Physically-based Scalar-fields Guided Deformation on GPU[J]. Journal of Computer Research and Development, 2010, 47(11): 1857-1864.
    [9]Wang Jing, Wang Lili, and Li Shuai. Pre-Computed Radiance Transport All-Frequency Shadows Algorithm on GPU[J]. Journal of Computer Research and Development, 2006, 43(9): 1505-1510.
    [10]Hu Wei and Qin Kaihuai. A New Rendering Technology of GPU-Accelerated Radiosity[J]. Journal of Computer Research and Development, 2005, 42(6): 945-950.

Catalog

    Article views (1174) PDF downloads (494) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return