Scan Stack: A Search-based Concurrent Stack for GPU
Scan Stack: A Search-based Concurrent Stack for GPU
复制标题
DOI：
10.1145/3564746.3587018
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
Noah South;B. Jang
中科院分区：
文献类型：
--
作者：
Noah South;B. Jang
并发数据结构在GPGPU应用的整体性能中起着至关重要的作用。堆栈是基本的数据结构之一，并发现了许多应用程序，其中数据以后进先出（LIFO）方式处理。虽然多核CPU的并发堆栈已经得到了很好的研究，但很少有研究指出CPU堆栈转换为GPU友好的形式。在本文中，我们提出了一个并发搜索为基础的GPU堆栈扫描堆栈。所提出的堆栈被设计为利用GPU存储器访问模式、存储器合并和线程结构（即，翘曲）以增加吞吐量。我们在NVIDIA RTX 3090上的实验表明，我们提出的扫描堆栈显着提高了吞吐量和可扩展性的所有基准时，减少搜索区域。然而，最大的改进是在可以消除的情况下，这种改进达到了非优化结构的近39倍。
Concurrent data structures play a critical role in the overall performance of GPGPU applications. Stack is one of the basic data structures and finds numerous applications where data is processed in a Last In First Out (LIFO) fashion. Although concurrent stack is well researched for multi-core CPUs, there is little research pointing to the conversion of CPU stacks into a GPU-friendly form. In this paper, we propose a concurrent search-based GPU stack named Scan Stack. The proposed stack is designed to take advantage of GPU memory access patterns, memory coalescence, and thread structures (i.e., warps) to increase throughput. Our experiments on an NVIDIA RTX 3090 show that our proposed scan stack significantly improves the throughput and scalability for all benchmarks when reducing the search area. However, the greatest improvements are shown when elimination is possible, and this improvement reaches nearly 39 times what a non-optimized structure is capable of.