这讲介绍一些运算算法。
从 step,work 的概念开始:

reduce


reduce 是两个元素的操作,同时需要满足结合律。

使用 block shared memory 的代码实现:
https://github.com/udacity/cs344/blob/master/Lesson%20Code%20Snippets/Lesson%203%20Code%20Snippets/reduce.cu
使用 global 的内存访问时间会变长。

scan


注意 scan 最后的一个元素是不会使用的。
下面这张图解释了为什么最后一个元素不用,因为有两种 scan:

Hillis Steele Scan:

Blelloch Scan:


GPU 的计算用的是这个算法。

scan 算法对比:

Histogram

直方图的定义:

可以通过 scan 解决直方图的问题。
直方图用简单的串行化思想写的代码用多线程是没有太大意义的。
因为判断放在哪个区间是需要条件判断的,每个线程访问的空间会随着输入变化。
当 bin 小的时候,可以通过分别处理每个 bin 并行来实现:

关于直方图的算法总结:

compat

神经网络里面应该没有什么需要 compat 的点吧。
如果硬要说的话,Int8 算是一种优化。CUDA 11 和新的安培架构有针对稀疏化的优化。
但是不妨碍了解一下实现步骤:

稀疏矩阵的表达:

最后一行表示行对应的 column 起始地址。

稀疏矩阵乘法:

排序:


并行计算通常使用的排序是归并排序:

顶层需要跨 SM,提升性能。
https://blog.csdn.net/abcjennifer/article/details/47110991
这篇文章讲的很棒,第三步的算法描述很清晰。

双调排序:

radix sort(基数排序)

https://blog.csdn.net/Mrhiuser/article/details/51997640
参考这篇文章吧。

快排


百度搜到这篇,CUDA 5.5 支持快排:
https://blog.csdn.net/niexiao2008/article/details/9622461
具体好不好用,需要用的时候再说。

排序总结:


↙↙↙阅读原文可查看相关链接,并与作者交流