邻居搜索问题在CUDA上基于KD-TRIE方法的优化与实现  

Optimization of Neighbor Searching Problem on CUDA Based on KD-TRIE and Its Application

作　　者：包南森[1] 李正杰[1] 柴亚辉[1,2] 徐炜民[1] 

机构地区：[1]上海大学计算机工程与科学学院,上海200072 [2]华东交通大学信息工程学院,南昌330013

出　　处：《上海大学学报（自然科学版）》2012年第3期305-310,共6页Journal of Shanghai University:Natural Science Edition

基　　金：国家高技术研究发展计划(863计划)资助项目(20009AA012201);上海市教委重点学科建设资助项目(J50103)

摘　　要：介绍如何在CUDA上搭建KD—TRIE，并对其进行搜索，使其能适应解决邻居搜索问题．实验结果表明，当搜索半径较小（如整个空间直径的0．01和0．001），数据规模较大（如10^6）时，使用KD-TRIE进行搜索的效果最佳，与蛮力算法相比可以达到加速比5000～15000倍的效果；当搜索半径较大时，加速比会相应减少．采取优化措施，可以提高加速比．This paper describes the construction of a KD-TRIE on CUDA, and the search and preprocessing for solving particle neighbor searching problem. The experimental results show that it is efficient to use KD-TRIE to search the CUDA when the search radius is not very large （ e. g. , 0.01 and 0.001 of the entire problem space diameter） and the data scale is relatively large （e. g. , 10^6）. Compare to the brute force method, the speed-up factor is about 5 000 to 15 000. However, if the search radius is too large, the speed-up factor will drop. Various optimization methods discussed can be used to raise the speed-up factor.

关 键 词：KD—TRIE k最邻近结点算法 CUDA 图形处理器 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构]