General transformations for GPU execution of tree traversals
General transformations for GPU execution of tree traversals
复制标题
GPU 执行树遍历的一般转换
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Milind Kulkarni
中科院分区：
文献类型：
--
作者：
Michael Goldfarb;Youngjoon Jo;Milind Kulkarni
随着程序员友好的GPU计算环境的冒险，人们对可以利用现代GPU上可用的高度并行性的工作负载有很大的兴趣。在诸如阵列和材料之类的密集数据结构上，在不规则算法的区域中的工作量明显较少，因此当涉及基于指针的动态数据结构时，较少的工作。 KD-Tree遍历已在GPU上实施，但在CPU实现方面产生了显着的性能。在算法结构中利用相似性的GPU，而不是应用特定的知识。
With the advent of programmer-friendly GPU computing environments, there has been much interest in offloading workloads that can exploit the high degree of parallelism available on modern GPUs. Exploiting this parallelism and optimizing for the GPU memory hierarchy is well-understood for regular applications that operate on dense data structures such as arrays and matrices. However, there has been significantly less work in the area of irregular algorithms and even less so when pointer-based dynamic data structures are involved. Recently, irregular algorithms such as Barnes-Hut and kd-tree traversals have been implemented on GPUs, yielding significant performance gains over CPU implementations. However, the implementations often rely on exploiting application-specific semantics to get acceptable performance. We argue that there are general-purpose techniques for implementing irregular algorithms on GPUs that exploit similarities in algorithmic structure rather than application-specific knowledge. We demonstrate these techniques on several tree traversal algorithms, achieving speedups of up to 38× over 32-thread CPU versions.