之前写 Register Tiling 和 Cache Tiling 的时候,提到了 GPU 上的高性能 GEMM kernel 会把输入矩阵的 tile 搬到 Shared Memory。当时只关注了 data reuse 的部分。
后来在看矩阵转置的 CUDA 实现时,碰到了一行让我停下来的代码:
1__shared__ float tile[32][33]; // 为什么是 33?
这是一个经典的 Padding trick,用来消除 Shared Memory 的 Bank Conflict。道理我大概知道,但要我解释清楚——为什么 32 列会冲突?为什么 33 列就不冲突?32 和 33 这两个数字的差异到底对应什么硬件行为?——我发现自己说不出来。
于是往回翻了一步——从最基本的问题开始:为什么不同的内存地址,不一定能同时访问?
不同地址就能同时读吗#
假设有一块 1024 × 32 bit 的 SRAM,我想在同一个周期内同时读 data[0] 和 data[100]。两个不同地址,没有数据依赖。
如果这块 SRAM 是 Single-Port 的——做不到。
一次读取需要经过完整的访问路径:Address Decoder 选中一条 Wordline,激活对应行的存储单元,数据通过 Bitline 传到 Sense Amplifier 读出。Single-Port SRAM 只有一套这样的路径——一个 Decoder,一组 Wordline 驱动,一组 Bitline 和 Sense Amp。一个周期只能选中一行,读出一个字。
问题的根源不是地址是否不同,而是硬件提供了多少条独立的访问路径。
加 Port 的代价#
一个直觉的解法:给 SRAM 加 Port。
Dual-Port SRAM 确实存在,CPU 的 Register File 通常就是多端口设计。但多端口不是免费的。
每增加一个独立的读端口,每个存储单元(Cell)需要额外的 Access Transistor。标准的 Single-Port SRAM 用 6T Cell(6 个晶体管),Dual-Port 通常是 8T,单个 Cell 的面积增加 30%–50%。除了 Cell 本身,每个端口还需要独立的一套 Wordline、Bitline 和 Sense Amplifier。
代价不是线性增长的。从 2 端口到 4 端口,布线越来越拥挤,时序约束越来越难满足。如果要做一个 32 端口的 SRAM——能让 32 个请求同时独立访问任意地址——Cell 面积和布线复杂度会让它在工程上几乎不可行。
于是出现了另一种思路。
用拆分换并行:Memory Banking#
既然把一块 SRAM 做成 32 端口太贵,另一个做法是:把它拆成多块 Single-Port SRAM。每块叫一个 Bank,每个 Bank 有自己独立的 Decoder、Wordline、Bitline、Sense Amp——也就是说,每个 Bank 在每个周期内可以独立处理一个访问请求。
地址映射通常使用 Interleaving——连续地址被交错分布到不同 Bank:
$$ \text{BankIndex} = \text{WordIndex} \bmod N $$$$ \text{BankOffset} = \lfloor \text{WordIndex} / N \rfloor $$以 4 个 Bank 为例:
| Word Index | Bank | Bank 内部地址 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 2 | 2 | 0 |
| 3 | 3 | 0 |
| 4 | 0 | 1 |
| 5 | 1 | 1 |
| 6 | 2 | 1 |
| 7 | 3 | 1 |
如果四个请求分别访问 Word 0、1、2、3,它们落在四个不同 Bank,硬件可以在一个周期内全部完成。
但如果四个请求访问的是 Word 0、4、8、12——它们全部映射到 Bank 0。四个不同的地址,争用同一个 Bank 的访问资源。这就是 Bank Conflict。
Bank Conflict 和地址冲突不是一回事。地址冲突是两个请求访问同一个地址;Bank Conflict 是不同地址碰巧映射到同一个 Bank,导致硬件无法并行处理。
Banking 的 trade-off:
- 比 Multi-Port 便宜:每个 Bank 是普通的 Single-Port SRAM,不需要改 Cell 结构。
- 但并行性受限于地址分布:数据布局和访问模式必须让请求尽量落在不同 Bank。
Banking 也不是零成本——每个 Bank 需要独立的外围电路(Decoder、Sense Amp),还需要 Crossbar 或 Mux 把各 Bank 的输出汇聚到请求方。但它避免了让每一个存储 Cell 都承担多端口的成本,对于需要高并行度的场景,这通常是更经济的选择。
CPU 和 DRAM 中的 Banking#
Banking 不只在 GPU Shared Memory 里出现。CPU Cache 和 DRAM 也大量使用了类似的思路,但具体机制不同。
Cache 里的 Bank Conflict#
现代 CPU 的 L1 Data Cache 通常支持每周期多次访问——比如同时执行两个 Load。实现方式因微架构而异,但一些设计使用了 Banked Cache:把 Cache 的数据阵列分成多个 Bank,每个 Bank 独立服务一个请求。
如果两个 Load 碰巧映射到同一个 Cache Bank,就会产生 Bank Conflict。CPU 通常通过 Replay 处理——冲突的请求延迟一拍重试。
不过 CPU Cache 的 Banking 实现高度依赖具体微架构。Intel、AMD、ARM 的做法各不相同,同一厂商不同代产品也可能不同。这里只是说明 Banking 的思想在 CPU 中也有应用,不是在描述某个通用标准。
DRAM 的层级结构与 Bank-Level Parallelism#
现代 DDR DRAM 有一个多级层次结构:
其中 Bank 是关键层级——每个 Bank 有自己独立的存储阵列和 Row Buffer(由 Sense Amplifier 阵列构成)。不同 Bank 可以各自独立地执行 Activate、Read、Precharge 等内部操作,这就是 DRAM 的 Bank-Level Parallelism。
Row Buffer 相当于 Bank 内部的"Cache"。一行(Row)被 Activate 打开后,其内容被复制到 Row Buffer 里。后续访问同一行的不同列(Column),直接从 Row Buffer 读取——这叫 Row Buffer Hit,速度很快。
但如果接下来要访问同一个 Bank 的另一行——比如 Bank 0 当前打开了 Row 100,现在要读 Row 101——就需要先 Precharge 关闭当前行,再 Activate 新行。这叫 Row Buffer Conflict(或 Row Miss),涉及额外的时序开销。
DRAM 的 Row Buffer Conflict 和 GPU Shared Memory 的 Bank Conflict 不是同一种机制。 前者是 DRAM 时序约束导致的延迟代价(Precharge + Activate),后者是多个线程在同一个周期内争用同一个 Bank 的访问端口。名字里都有"Conflict",但硬件机制完全不同。
三个容易混淆的概念#
在讨论内存并行性的时候,有三个概念容易被混用:
| 概念 | 解决的问题 |
|---|---|
| Multi-Port | 一个存储结构同时接受多少个独立访问请求 |
| Banking | 通过多个独立存储单元提高并行访问能力 |
| Memory-Level Parallelism(MLP) | 系统能同时维持多少个未完成的内存请求 |
Multi-Port 和 Banking 都是存储硬件的物理组织方式。MLP 是一个系统级指标,取决于 Out-of-Order Execution、Load Queue、MSHR(Miss Status Holding Register)等微架构能力——CPU 可以在等待一次 Cache Miss 返回的同时发出更多访存请求。
Banking 提供物理层面的并行访问资源,MLP 是系统利用这些资源的能力。两者互补但不是同一件事。
回到 GPU:Shared Memory 的 32 个 Bank#
之前写过,Shared Memory 是 GPU 每个 SM 内部的片上 SRAM。在经典的 32-bit 访问模型下(以 A100 / Compute Capability 8.0 为例):
- Warp Size = 32
- Shared Memory 分为 32 个 Bank
- 每个 Bank 的基本访问宽度是 4 Bytes(一个 32-bit word)
地址到 Bank 的映射:
$$ \text{BankIndex} = (\text{ByteAddress} / 4) \bmod 32 $$等价地,对于 32-bit word:
$$ \text{BankIndex} = \text{WordIndex} \bmod 32 $$一个 Warp 有 32 个 Lane,它们在同一个周期内各自发出一个 Shared Memory 请求。如果 32 个请求落在 32 个不同 Bank,硬件可以一次全部完成。如果有多个请求落在同一个 Bank 的不同地址,就产生 Bank Conflict——这些请求必须分多轮串行处理。
用几个例子看不同的访问模式:
连续访问:data[lane]。Lane 0 → Bank 0,Lane 1 → Bank 1,…… Lane 31 → Bank 31。32 个不同 Bank——无冲突。
Stride = 2:data[lane * 2]。Lane 0 → Bank 0,Lane 1 → Bank 2,…… Lane 16 → Bank 0。每个 Bank 被访问两次——2-way Bank Conflict。
Stride = 32:data[lane * 32]。全部 32 个 Lane 映射到 Bank 0——32-way Bank Conflict,完全串行。
有一个特殊情况:如果多个 Lane 访问的是同一个地址(不是同一个 Bank 的不同地址),Shared Memory 硬件可以通过 Broadcast 把数据发送给所有请求方,不产生 Bank Conflict。Bank Conflict 专指不同地址争用同一个 Bank。
以上分析基于 32-bit word、4-byte bank width 的默认配置。对于 64-bit 或 128-bit 的向量化访问,Bank 映射规则会有变化,不能直接套用这个简化模型。
tile[32][33]:一个 float 的 Padding 为什么能消除 Bank Conflict#
这是我最初想搞清楚的问题。
矩阵转置是一个经典的 CUDA 优化案例。核心思路是用 Shared Memory 作为中间 tile:从 Global Memory 按行连续读(保证 Coalescing),写入 Shared Memory;再从 Shared Memory 按列读出,按行写回 Global Memory(同样保证 Coalescing)。转置发生在 Shared Memory 的读写坐标交换上。
1// blockDim = (32, 32),输入 M×N,输出 N×M(转置)
2int gx = blockIdx.x * 32 + threadIdx.x;
3int gy = blockIdx.y * 32 + threadIdx.y;
4
5__shared__ float tile[32][32];
6
7// Step 1: Global → Shared(Warp 按行连续读,Coalesced)
8tile[threadIdx.y][threadIdx.x] = input[gy * N + gx];
9__syncthreads();
10
11// Step 2: Shared → Global(转置读取,交换 Block 坐标保证输出 Coalesced)
12int ox = blockIdx.y * 32 + threadIdx.x;
13int oy = blockIdx.x * 32 + threadIdx.y;
14output[oy * M + ox] = tile[threadIdx.x][threadIdx.y];CUDA 的 Warp 由连续的线程索引组成。对于 blockDim = (32, 32) 的配置,一个 Warp 内 32 个线程共享相同的 threadIdx.y,threadIdx.x 从 0 到 31。
输出坐标交换了 blockIdx.x 和 blockIdx.y——ox 用 blockIdx.y,oy 用 blockIdx.x——这保证输出是正确的转置,同时 Warp 内 threadIdx.x 变化使 ox 连续,输出写入 Coalesced。
Step 1 写入 tile[threadIdx.y][threadIdx.x]——Warp 内 threadIdx.y 固定、threadIdx.x 变化,写入同一行的连续列。每个 Lane 落在不同 Bank,没有冲突。
问题出在 Step 2。
tile[32][32]:所有 Lane 撞上同一个 Bank#
读取 tile[threadIdx.x][threadIdx.y] 时,Warp 内 threadIdx.y 固定(设为 col),threadIdx.x 从 0 到 31。也就是访问 tile[0][col]、tile[1][col]、……、tile[31][col]——同一列的所有行。
C/C++ 是 Row-major Layout。float tile[32][32] 中,元素 tile[row][col] 的 Word Index:
因此:
$$ \text{BankIndex} = (\text{row} \times 32 + \text{col}) \bmod 32 = \text{col} $$因为 \( 32 \bmod 32 = 0 \),row * 32 这一项对 BankIndex 没有任何贡献。不管 row 是多少,BankIndex 都等于 col。
假设 col = 5:
| Lane | 访问元素 | WordIndex | BankIndex |
|---|---|---|---|
| 0 | tile[0][5] | 5 | 5 |
| 1 | tile[1][5] | 37 | 5 |
| 2 | tile[2][5] | 69 | 5 |
| … | … | … | 5 |
| 31 | tile[31][5] | 997 | 5 |
32 个 Lane 访问 32 个不同地址,全部映射到 Bank 5。32-way Bank Conflict——最坏情况。
加一列 Padding#
1__shared__ float tile[32][33];逻辑上仍然只使用 32 列。第 33 列是不存储有效数据的 Padding。
每行从 32 个 float(128 Bytes)变成 33 个 float(132 Bytes)。相邻两行的起始地址错开了 1 个 Word。
$$ \text{WordIndex}(\text{row}, \text{col}) = \text{row} \times 33 + \text{col} $$$$ \text{BankIndex} = (\text{row} \times 33 + \text{col}) \bmod 32 $$因为 \( 33 \bmod 32 = 1 \),所以 \( \text{row} \times 33 \equiv \text{row} \pmod{32} \):
$$ \text{BankIndex} = (\text{row} + \text{col}) \bmod 32 $$当 col 固定、row 从 0 到 31 变化时,\( \text{BankIndex} = (0 + \text{col}),\; (1 + \text{col}),\; \ldots,\; (31 + \text{col}) \bmod 32 \)。32 个连续整数对 32 取模,恰好遍历 0 到 31 所有值。
还是以 col = 5 为例:
| Lane | 访问元素 | WordIndex | BankIndex |
|---|---|---|---|
| 0 | tile[0][5] | 5 | 5 |
| 1 | tile[1][5] | 38 | 6 |
| 2 | tile[2][5] | 71 | 7 |
| … | … | … | … |
| 27 | tile[27][5] | 896 | 0 |
| 28 | tile[28][5] | 929 | 1 |
| 29 | tile[29][5] | 962 | 2 |
| 30 | tile[30][5] | 995 | 3 |
| 31 | tile[31][5] | 1028 | 4 |
32 个 Lane → 32 个不同 Bank。无冲突。
Padding 不是为了存储更多数据,而是为了改变地址到 Bank 的映射关系。 多出来的一列永远不会被读写——它唯一的作用是让相邻行的起始地址错开一个 Word,使得列方向的访问不再全部落在同一个 Bank。
换一个角度理解这件事:
- 32 × 32:每行跨度是 32 个 Word,恰好是 Bank 数的整数倍。所有行的同一列 Word 都从同一个 Bank 起步,永远对齐。
- 32 × 33:每行跨度是 33 个 Word,比 Bank 数多 1。每一行的起始 Bank 位置比上一行偏移一格,转一圈之后正好遍历所有 32 个 Bank。
为什么是 33#
33 不是唯一能解决问题的行宽。设物理行宽为 \( S \) 个 word:
$$ \text{BankIndex} = (\text{row} \times S + \text{col}) \bmod 32 $$当 col 固定、row 从 0 到 31 变化时,能覆盖多少个不同 Bank 取决于 \( \gcd(S, 32) \):
| S | gcd(S, 32) | 使用的 Bank 数 |
|---|---|---|
| 32 | 32 | 1 |
| 33 | 1 | 32 |
| 34 | 2 | 16 |
| 35 | 1 | 32 |
| 36 | 4 | 8 |
| 37 | 1 | 32 |
33 是最自然的选择:只多 Padding 一个 float(4 Bytes),就让行宽与 32 互质。35、37 也能达到无冲突,但多浪费空间。34、36 虽然比 32 好,但并没有完全消除冲突。
因为 32 = \( 2^5 \),任何奇数行宽都和 32 互质——所以 33 是最小代价的选择。
这个推导有一个明确的前提条件:32 个 Lane 访问同一列的连续行,32 个 Bank,每 Bank 宽度 4 Bytes(32-bit word)。如果访问模式不同,或者使用了 8-byte bank mode,需要重新分析。
补充几点:
- Padding 优化的是 Shared Memory 的 Bank Mapping。它不会改善 Global Memory Coalescing——后者取决于 Global Memory 地址的连续性,和 Shared Memory 的布局无关。
- 物理存储从 32 × 32 = 1024 个 float 变成 32 × 33 = 1056 个 float,多了 128 Bytes。对于每个 SM 百 KB 量级的 Shared Memory,这个代价很小。
- 整个方案的正确性依赖
__syncthreads()保证写入完成后再读取。
写在最后#
从 Single-Port SRAM 到 GPU Shared Memory 的 Padding trick,核心的脉络是:
内存并行访问能力不是逻辑地址空间天然提供的,而是底层硬件组织决定的。 不同地址不代表能同时访问——真正决定并行性的是硬件提供了多少独立的访问资源。
Banking 是在成本和并行性之间做权衡的一种设计:把存储空间拆分为多个独立 Bank,通过 Interleaved Mapping 让连续访问自然分散。代价是数据布局必须匹配——当访问模式不巧让请求集中到同一个 Bank,就会产生冲突。
tile[32][33] 是这个原理的一个精确应用:不改变逻辑数据,不改变访问代码,只通过改变物理布局(多 Padding 一列),让列方向的访问从 32-way Bank Conflict 变成无冲突。
这个思路不限于 Shared Memory。CPU Cache Locality、Memory Coalescing、分布式系统的 Data Sharding——背后都有类似的问题:数据的物理组织方式,直接决定了访问模式能否高效利用硬件资源。
Good memory layout is not just about where data is stored. It is about which hardware resources are used when data is accessed.
参考资料#
- NVIDIA. CUDA C++ Programming Guide — Shared Memory.
- NVIDIA. An Efficient Matrix Transpose in CUDA C/C++.
- Jacob, B., Ng, S., & Wang, D. Memory Systems: Cache, DRAM, Disk. Morgan Kaufmann, 2007.
- Hennessy, J. L., & Patterson, D. A. Computer Architecture: A Quantitative Approach. 6th edition, 2017.
- 从 Register Tiling 到 Cache Tiling:理解高性能计算中的 Data Reuse
- GPU 的数据存在哪?——从 HBM 到片上存储的存储层级
- GPU Execution Model:为什么大量 Warps 能隐藏内存延迟?