kd—tree并行化创建方法研究

《kd—tree并行化创建方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、KD—Tree并行化创建方法研究　　摘要：针对KD-Tree的串行创建效率不高的问题，文中对KD-Tree创建的并行化方法进行了研究。首先通过分析串行创建的方法；结合GPU的并行特性，改进了原有方法；并对三种不同的并行化方法进行了对比，其中基于GPU构建的并行化方法既保证了稳定性和性能，又具有比较满意的时间复杂度。关键词：KD-Tree；并行化；GPU；算法中图分类号：TM391文献标识码：A文章编号：1009-3044（2013）23-5338-03通常，KD-Tree创建算法基于CPU的串行进行设计，并且采用数据结构

2、——栈的前序遍历方法。在单核CPU中，尽管KD-Tree串行创建算法的理论时间复杂度为O（nlog（n）），但是对于复杂的元素集合，KD-Tree的创建仍然不能满足很多应用的要求。文中结合GPU的并行特性，充分改进原有算法，发掘其中可以并行计算的部分，从而大大优化KD-Tree创建算法的性能。2.1CPU与GPU5异构并行设备的计算能力，主要体现在三个方面[5]：线程并发数、线程存储资源、线程计算资源。CPU的现场并发数很低，但每一个线程的存储资源很多，计算资源丰富。这意味着，其算法更适合分配数据，然后各线程相对独立的处

3、理数据，即MIMD算法模式。因此通常称CPU的线程是一种相对重量级的现场。而对于GPU，由于其流处理器数量庞大，要充分利用这些流处理器，就需要很高的线程并发度，如果并发模型无法达到高度并发，则难以发挥GPU的性能。但每一个线程的存储资源少，计算资源少。这意味着，无法采用为各线程分配数据的方法，必须逐模块协同执行，即SIMD算法模式，所以称GPU的线程是一种相对轻量级的线程。当然CPU亦可执行SIMD算法模式，但就同价位GPU来说，其计算能力却相对低下。2.2在多核CPU中——采用多线程通过线程的方式，可以在双核、四核CP

4、U上进行一定程度的并行化。但由于当前CPU计算核心数量的限制，如果采用上述类似方式对KD-Tree的第四层进行并行化，将达不到理想的优化效果。因为第四层的KDTree中有8个节点，需要创建8个线程（包括主线程），则线程的数量大于CPU的物理计算核心的数量。在每个周期内，实际上只有一半的线程在工作，并且CPU的线程需要进行频繁切换，线程间的不断切换大大降低了KD-Tree的创建降低速度。2.3在CPU和GPU中——采用多线程和GPU特性5利用CPU构建KD-Tree的前几层，当KD-Tree的层数达到可以并行的时候，再利用

5、GPU来创建KD-Tree剩下的层数。与传统算法比较，此算法的并行度有很大的改进，但其运行速度相当。主要原因有以下两点：1）在从CPU切换到GPU创建的过程中，有大量的内存数据从主存传输到了显存。由于PCIE的带宽有限，传输将花费大量的时间。2）CPU创建算法的终止条件是所有节点数量小于一定的阈值。如果阈值设置不合理，CPU有可能停止运行，此时GPU的个别线程将遍历大量的数据。由于CPU包含多级Cache系统，可以用于隐藏内存访问延迟，但GPU是通过线程切换来隐藏的，如果个别线程的行为时间过于长，则其他线程也要被迫等待，

6、并处于闲置状态，这将浪费大量硬件资源。综合上述原因，该算法很难在实际中得到推广。2.4在GPU中-采用GPU特性3结论针对传统的KD-Tree的串行创建算法进行逐步优化，深入地探讨了三种KD-Tree的并行创建算法，分别为：在多核CPU中采用了多线程方法、多线程和GPU特性结合、GPU特性，其中第三种并行方法理论上可以极大的提高KD-Tree的创建速度。参考文献：[1]TimFoleyandJeremySugerman，KD-TreeaccelerationstructuresforaGPU5raytracer[J].G

7、raphicsHardware，2005（7）：15-17.[2]SebastianBindick*，MaikStiebler，ManfredKrafczyk.Fastkd-tree-basedhierarchicalradiosityforradiativeheattransportproblems，2011，86（9）：1082-1100.[3]杜振鹏，李德华.基于KD-Tree搜索和SURF特征的图像匹配算法研究[J].计算机与数字工程，2012，2（2）：96-97.[4]熊云艳，毛宜军，闵华清.有序的KD-Tr

8、ee在图像特征匹配上的应用[J].化工自动化及仪表，2012（10）：84-87.[5]李勇.光线跟踪加速算法在异构多核平台上的设计与实现[D].南京邮电大学，2011（03）：18-38.[6]卢贺奇.基于OpenCL的实时KD-Tree与动态场景光线跟踪[D].浙江大学，2011.2：15-45.[7]范文山，王