A Specialized Concurrent Queue for Scheduling Irregular Workloads on GPUs
A Specialized Concurrent Queue for Scheduling Irregular Workloads on GPUs
复制标题
DOI：
10.1145/3337821.3337837
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
David Troendle;T. Ta;B. Jang
中科院分区：
文献类型：
--
作者：
David Troendle;T. Ta;B. Jang
持久线程模型为加速图形处理单元（GPU）上的数据不规则工作负载提供了可行的解决方案。然而，随着活动线程数量的增加，对共享资源的争用和重试限制了持久线程之间的任务调度效率。为了解决这个问题，我们提出了一个高度可扩展的，非阻塞并发队列适合用作GPU持久线程任务调度器。所提出的并发队列具有两个新颖的性质：1）支持的入队/出队队列操作从来没有遭受重试开销，因为原子操作不会失败，队列空异常已被重构;和2）队列操作任意数量的队列条目相同的成本作为一个单一的条目。每个线程组中的代理线程代表组中的所有线程执行所有原子操作。这两个新的属性大大减少了GPU的锁步单指令多线程（SIMT）执行模型引起的线程争用。为了证明所提出的队列的性能和可扩展性，我们实现了一个自顶向下的广度优先搜索（BFS）的持久线程模型的基础上，使用1）提出的并发队列，2）传统的并发队列，并分析其性能和可扩展性的特点，在不同的输入图数据集和硬件配置。我们的实验表明，基于我们提出的队列的BFS实现的性能不仅优于传统队列的基础上，而且在文献中发现的最先进的BFS实现的最小的1.26倍，最大的36.23倍。我们还观察到，对于高端离散GPU支持的最大线程数（实验中为14 K线程），我们提出的队列的可扩展性在理想线性加速比的10%以内。
The persistent thread model offers a viable solution for accelerating data-irregular workloads on Graphic Processing Units (GPUs). However, as the number of active threads increases, contention and retries on shared resources limit the efficiency of task scheduling among the persistent threads. To address this, we propose a highly scalable, non-blocking concurrent queue suitable for use as a GPU persistent thread task scheduler. The proposed concurrent queue has two novel properties: 1) The supporting enqueue/dequeue queue operations never suffer from retry overhead because the atomic operation does not fail and the queue empty exception has been refactored; and 2) The queue operates on an arbitrary number of queue entries for the same cost as a single entry. A proxy thread in each thread group performs all atomic operations on behalf of all threads in the group. These two novel properties substantially reduce thread contention caused by the GPU's lock-step Single Instruction Multiple Threads (SIMT) execution model. To demonstrate the performance and scalability of the proposed queue, we implemented a top-down Breadth First Search (BFS) based on the persistent thread model using 1) the proposed concurrent queue, and 2) two traditional concurrent queues; and analyzed its performance and scalability characteristics under different input graph datasets and hardware configurations. Our experiments show that the BFS implementation based on our proposed queue outperforms not only ones based on traditional queues but also the state-of-the-art BFS implementations found in the literature by a minimum of 1.26× and maximum of 36.23×. We also observed the scalability of our proposed queue is within 10% of the ideal linear speedup for up to the maximum number of threads supported by high-end discrete GPUs (14K threads in our experiment).