An Optimal Parallel Prefix-Sums Algorithm on the Memory Machine Models for GPUs
An Optimal Parallel Prefix-Sums Algorithm on the Memory Machine Models for GPUs
复制标题
GPU内存机模型上的最优并行前缀和算法
DOI：
10.1007/978-3-642-33078-0_8
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
K. Nakano
中科院分区：
文献类型：
--
作者：
K. Nakano
本文的主要贡献在于给出了在离散内存机(DMM)和统一内存机(UMM)两种内存机模型上计算和和及前缀和的优化算法。DMM和UMM是理论上的并行计算模型，它们抓住了GPU的共享内存和全局内存的本质。这些模型有三个参数：线程数、内存宽度和内存访问延迟。我们首先证明了n个数的和可以在DMM和UMM上以时间单位计算。然后，我们继续说明时间单位是计算总和所必需的。最后，我们给出了一个在DMM和UMM上以时间为单位计算n个数的前缀和的最优并行算法。
The main contribution of this paper is to show optimal algorithms computing the sum and the prefix-sums on two memory machine models, the Discrete Memory Machine (DMM) and the Unified Memory Machine (UMM). The DMM and the UMM are theoretical parallel computing models that capture the essence of the shared memory and the global memory of GPUs. These models have three parameters, the numberpof threads, the widthwof the memory, and the memory access latencyl. We first show that the sum ofnnumbers can be computed intime units on the DMM and the UMM. We then go on to show thattime units are necessary to compute the sum. Finally, we show an optimal parallel algorithm that computes the prefix-sums ofnnumbers intime units on the DMM and the UMM.