并行归约算法中的共享内存库冲突

Question

我正在阅读 Nvidia 的幻灯片（在 CUDA 中优化并行缩减）讨论并行缩减算法。

幻灯片 15：

作者在这里讨论了通过使用顺序寻址，我们可以避免共享内存库冲突。我认为这是错误的，这是我的理由：

在幻灯片 10 中，我们假设每个线程块有 128 个线程。在幻灯片上蓝色框中提供的顺序代码中，线程 0 尝试同时使用

sdata[0]

和

sdata[64]

，并且由于我们有 32 个内存库，这 2 个访问会导致内存库冲突。

我的推论哪部分是错误的？

Answer 1

这与读取端

sdata[tid + s]

和写入端

sdata[tid]

之间的库冲突无关。它是关于每个操作（读或写）本身的同一 warp 内的相邻线程之间的存储体冲突。除了在这种情况下不独立的操作之外，warp 无法并行执行读取和写入操作。不并行/锁步发生的操作不会导致存储体冲突。 请记住，warp 中的线程（非常旧的 GPU 中的 half warp）以锁步方式进行内存访问。在第一个代码中，该索引跨度为

2 * s

。例如，对于

2 * s == 32

，每个线程访问同一个存储体，假设有 32 个存储体。在第二个代码中，所有线程都按顺序访问数组元素，没有跨度，并且索引仅因线程 ID 不同而不同。所以他们总是会碰到不同的记忆库。

编辑

快速警告：请注意 Nvidia 的

Volta 调整指南

假设读取和写入对于同一 warp 中的其他线程隐式可见的应用程序需要在通过全局或共享内存在线程之间交换数据的步骤之间插入新的

__syncwarp()

warp 范围屏障同步指令。假设代码以锁步方式执行，或者来自单独线程的读/写在没有同步的情况下跨 warp 可见是无效的。

这会影响幻灯片 22 中的代码（最后一个扭曲的展开）。另外，我很确定使用

Warp Shuffle Functions

可以更好地解决该部分，而不是使用共享内存。

编辑2

GitHub 上相应的

CUDA 示例

已适当更新。某处可能也有网络研讨会的更新版本。

sdata[tid] += sdata[tid+s] 不需要读取sdata[tid]？？？

Answer 2