欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

GPU算子Reduce和Scan算法原理

终于开始学习GPU的开发了,里面算法的知识比想象的有趣,不少地方还是很考验编程基本功的。

这里介绍的两个操作的实现很有意思,对于理解GPU并行计算的「思维模式」很有帮助。

Reduce

reduce操作的定义很简单,输入一个数组和作用在数组中的运算符,输出一个结果。使用一个函数表示就是: \(y=f(array,op)\) ,CPU中实现这个计算就是扫描一下array中的每一个元素,在O(n)的时间复杂度完成计算,具体的伪代码为:

使用GPU实现就是如何利用其「并行」的特性,可以考虑每一个block计算一部分,然后将不同block的合并到一起。在一个block内部,可以通过「树」的结构对数据划分,具体如下图:

QQ20170126-0

核心实现代码(通过share memory实现):

QQ20170126-1

Scan

scan的定义也很简单,使用当前位置之前的元素和一个操作作为输入,获得当前位置的输出,使用函数表示为:

\(output_{pos}=f(input_1,input_2,...,input_{pos - 1}, op) \)

实现方式有两个有名的算法。

Hillis Steele Scan

祭上论文(我没有看):戳我

思想很像树状数组的结构,就是想分解子问题方便利用GPU强大的并行计算单元。具体实现就是每一步的跨度为 \(2^k\) ,进行元素合并,最多层数就是log(n)。

下图是一个16个元素的例子:

QQ20170126-3

Blelloch Scan

实现exclusive scan,分两步走:

  1. 一次reduce过程,生成所有 \(2^k\) 位置的和(利用了全部thread)
  2. 一次downsweep过程(其实就是树状数组的分解过程,每一个数字都可以分解为2的幂的和的形式)

两个阶段算法的示意图,第一个阶段:

QQ20170126-4

第二个阶段:

QQ20170126-5

官方文档

https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_pref01.html

 

未经允许不得转载:大数据算法 » GPU算子Reduce和Scan算法原理

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站