Efficient Batched Predecessor Search in Shared Memory on GPUs
Efficient Batched Predecessor Search in Shared Memory on GPUs
复制标题
GPU 共享内存中的高效批量前驱搜索
DOI：
10.1109/hipc.2015.40
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Nodari Sitchinava
中科院分区：
文献类型：
--
作者：
Ben Karsin;H. Casanova;Nodari Sitchinava
众核图形处理单元（GPU）正被用于通用计算。然而，由于架构的特点，对于许多问题，它是具有挑战性的设计并行算法，充分利用GPU的计算能力。这些特征之一是内存设计。虽然合并全局内存访问的问题已经被广泛地记录和研究，但是另一个重要的体系结构特性是将共享内存组织成存储体。银行冲突如何影响算法性能的研究最近才开始受到关注。在这项工作中，我们研究了前任搜索算法和银行冲突对其执行时间的影响。通过复杂性分析，我们表明，银行冲突造成显着损失的并行性的一个天真的算法。然后，我们提出了两个改进的算法：一个，完全消除银行冲突，但使用工作效率低的线性搜索，和一个是工作最佳的，但经验有限的银行冲突。我们开发这些算法的GPU实现，并在现实世界的硬件上获得的实验结果。这些结果验证了我们的理论分析的朴素算法，并允许我们评估我们的算法在实践中的性能。虽然我们的改进算法优于天真的算法，我们的主要实验发现是，我们的冲突限制算法提供了更大的性能增益。
Many-core Graphics Processing Units (GPUs) are being used for general-purpose computing. However, due to architectural features, for many problems it is challenging to design parallel algorithms that exploit the full compute power of GPUs. Among these features is the memory design. Although the issue of coalesced global memory access has been documented and studied extensively, another important architectural feature is the organization of shared memory into banks. The study of how bank conflicts impact algorithm performance has only recently begun to receive attention. In this work we study the predecessor search algorithm and the effects of bank conflicts on its execution time. Via complexity analysis we show that bank conflicts cause significant loss in parallelism for a naive algorithm. We then propose two improved algorithms: one that eliminates bank conflicts altogether but that uses a work inefficient linear search, and one that is work-optimal but that experiences a limited number of bank conflicts. We develop GPU implementations of these algorithms and present experimental results obtained on real-world hardware. These results validate our theoretical analysis of the naive algorithm and allow us to assess the performance of our algorithms in practice. Although both our improved algorithms outperform the naive algorithm, our main experimental finding is that our conflict-limited algorithm provides a larger performance gain.
影响因子：
8.7
作者：
Lin, Feng;Wang, Gang;Yao, Xin
通讯作者：
Yao, Xin