CUDA Prefix Sum 的 bank conflict：如何理解图 39-5？

bank 编号会循环，题目中的 bank 行有误

假设有 16 个 bank，每个元素占一个 32-bit word，数组起始位置对应 bank 0。未加 padding 时，bank 编号的计算方式是：

bank = ai % 16;

因此，ai = 16 对应 bank 0，ai = 18 对应 bank 2，ai = 30 对应 bank 14。题目中的 bank 行应改为：

thid   0  1  2  3  4  5  6  7 |  8  9 10 11 12 13 14 15
ai     0  2  4  6  8 10 12 14 | 16 18 20 22 24 26 28 30
bank   0  2  4  6  8 10 12 14 |  0  2  4  6  8 10 12 14

每个被访问的 bank 都要处理两个不同地址，因此会产生 2-way bank conflict。

这里还需要区分原始索引和填充后的索引。GPU Gems 第 39 章的图 39-5 展示了 padding 如何改变访问模式，而题目给出的两行代码还没有执行 padding。

bank 如何从数组下标计算出来？

一个 bank 可以容纳多个 word。连续的 32-bit word 按 bank 编号轮流分配：

题目中的 ai 序列对应 offset = 1：

int ai = offset * (2 * thid + 1) - 1;
// offset == 1 时：ai == 2 * thid

当 8 <= thid <= 15 时，各线程访问的下标和 bank 为：

数组下标可以继续增加，bank 编号始终在 0 到 15 之间循环。如果数组起始位置对应其他 bank，所有 bank 编号会整体平移，冲突程度不变。

为什么这是 2-way conflict？

以 bank 0 为例：

线程 0：读取 temp[0]  → bank 0
线程 8：读取 temp[16] → bank 0

两个线程读取同一个 bank 中的两个不同 word，这两个访问需要分开处理。其他被访问的 bank 也各有两个这样的访问，所以冲突程度是 2，不是 8，也不是 16。

分析冲突时，只计算同一条 shared memory 指令所涉及的线程组。GPU Gems 使用早期 NVIDIA 8 Series GPU 的模型，按 16 个线程的 half-warp 分析，不能把整个 thread block 的访问合在一起计数。

下面这条语句包含对不同数组位置的读写：

temp[bi] += temp[ai];

读取 temp[ai]、读取 temp[bi] 和写入 temp[bi] 的访问模式应分别分析，不能把 ai 和 bi 的访问总数相加来计算冲突程度（degree）。offset = 1 时，bi = 2 * thid + 1，对应的奇数 bank 也各被访问两次。

随着 offset 增大，访问步长也会增大。例如，offset = 2 时：

ai    1  5  9 13 17 21 25 29 33 37 41 45 49 53 57 61
bank  1  5  9 13  1  5  9 13  1  5  9 13  1  5  9 13

如果这 16 个线程都活跃，就会产生 4-way conflict。继续增大步长可能产生更高程度的冲突。不过，scan 接近树根时，活跃线程会减少，不能始终按 16 个线程计算。

图 39-5 中的 padding 改变了什么？

padding 调整了逻辑下标对应的 shared memory 实际存储位置。对于这里的前 32 个逻辑元素，规则可以写成：

physical_index = logical_index + logical_index / 16;

其中 / 是整数除法。逻辑下标 0 到 15 保持原位，下标 16 到 31 整体后移一个 word，实际位置 16 留作 padding。

线程 8 到 15 的映射随之变为：

前 8 个线程仍访问偶数 bank，后 8 个线程改为访问奇数 bank：

thid          0  1  2  3  4  5  6  7 |  8  9 10 11 12 13 14 15
逻辑 ai       0  2  4  6  8 10 12 14 | 16 18 20 22 24 26 28 30
实际下标      0  2  4  6  8 10 12 14 | 17 19 21 23 25 27 29 31
bank          0  2  4  6  8 10 12 14 |  1  3  5  7  9 11 13 15

这次读取访问了 16 个不同的 bank，消除了原来的 2-way conflict。padding 改变了元素的存储位置，bank 的硬件映射规则保持不变。

代码应怎样修改？

对于上述访问范围，索引变换可以写成：

int ai = offset * (2 * thid + 1) - 1;
int bi = offset * (2 * thid + 2) - 1;

// 简单 padding，用于解释图中的映射。
int physical_ai = ai + ai / 16;
int physical_bi = bi + bi / 16;

temp[physical_bi] += temp[physical_ai];

完整实现还需要满足两个条件：

• 初始化、up-sweep、down-sweep、根节点清零和结果读取都采用一致的索引变换。
• 分配的 shared memory 空间足以容纳 padding 后的数据。

i + i / 16 足以解释这里的访问模式，但不能保证任意数组长度、任意树层都无冲突。处理更大范围时，可能需要加入更高层的偏移，例如 i / 256，并根据实际访问模式检查冲突情况。

同地址读取与现代 GPU 的注意事项

判断冲突还要看同一 bank 内被访问的 word 是否不同。多个线程读取同一个 shared memory 地址时，可以通过 broadcast 满足请求，不能直接按线程数计算冲突程度。同地址并发写入涉及另外的正确性问题，不能套用读取广播的解释。CUDA 官方文档 对此有说明。

现代 GPU 仍然存在 bank conflict。上述官方文档对 compute capability 5.x 及更新设备的描述是：共有 32 个 bank，连续的 32-bit word 依次映射到各 bank，按整个 32 线程 warp 分析访问。

在这个模型下，32 个活跃线程读取 temp[2 * thid]，仍会产生 2-way conflict。例如，线程 0 和 16 分别读取下标 0 和 32，两者都会落到 bank 0。如果只有前 16 个线程活跃，同样的访问步长会落到 16 个不同的 bank。

复现示例时，应先确定 bank 数量、元素宽度和活跃线程范围，再计算每条访问指令的地址映射。16-bank 示例中的常量不能直接照搬到其他设备。

备注：内容仅供参考。