本文選題：人工智能 + 約束滿足問題��； 參考：《計(jì)算機(jī)研究與發(fā)展》2017年03期

【摘要】：弧相容算法是約束滿足問題的基本壓縮求解空間算法之一,很多優(yōu)秀的高級(jí)算法都以高性能的弧相容算法作為核心.近年來,以GPU為計(jì)算工具加速并行計(jì)算被用來嘗試解決許多問題.基于GPU和基本的并行算法,提出一種適合GPU運(yùn)算的約束網(wǎng)絡(luò)表示模型N-E,給出其生成算法BuildNE.結(jié)合細(xì)粒度的弧相容算法——AC4,基于N-E模型提出AC4的并行化算法AC4~(GPU)與改進(jìn)算法AC4~(GPU)+,使弧相容算法得以擴(kuò)展到GPU上執(zhí)行.實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的可行性,與AC4算法的比較,其在一些規(guī)模較小的問題上取得了10%~50%的加速,在一些規(guī)模較大的問題上則加速1~2個(gè)數(shù)量級(jí).為今后進(jìn)一步在GPU上以并行形式解決其他約束滿足問題提供了一種核心算法方案.
[Abstract]:Arc compatibility algorithm is one of the basic space compression algorithms for constrained satisfaction problems. Many excellent high-level algorithms have high performance arc compatibility algorithm as the core.In recent years, GPU as a computing tool to accelerate parallel computing has been used to try to solve many problems.Based on GPU and basic parallel algorithm, a constrained network representation model N-Ewhich is suitable for GPU operation is proposed, and its build algorithm is given.Combined with fine-grained arc compatibility algorithm AC4, based on N-E model, the parallel algorithm AC4 / GPU of AC4 and the improved algorithm AC4 / GPU) are proposed, so that the arc compatibility algorithm can be extended to execute on GPU.The experimental results show that the algorithm is feasible. Compared with the AC4 algorithm, it has achieved 10% acceleration on some smaller problems and 1 ~ 2 orders of magnitude on some larger problems.This paper provides a core algorithm for solving other constraint satisfaction problems on GPU in parallel.
【作者單位】： 吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué));
【基金】：國(guó)家自然科學(xué)基金項(xiàng)目(61272208,61373052) 吉林省自然科學(xué)基金項(xiàng)目(20140101200JC)~~
【分類號(hào)】：TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 馬伯寧;王晨昊;湯曉安;匡綱要;;基于GPU的二維離散小波變換快速計(jì)算[J];國(guó)防科技大學(xué)學(xué)報(bào);2011年03期

2 ZW;;3D游戲利器 主流嵌入式處理器GPU逐個(gè)看[J];電腦迷;2011年19期

3 王志國(guó);王貴錦;施陳博;苗權(quán);林行剛;;積分圖像的快速GPU計(jì)算[J];計(jì)算機(jī)應(yīng)用研究;2011年10期

4 盧永菁;王東;;基于GPU的高速網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)設(shè)計(jì)[J];計(jì)算機(jī)工程與應(yīng)用;2011年33期

5 儲(chǔ)t熆，

本文編號(hào)：1746301