↓ 跳过正文
  1. Posts/

Memory Banking:为什么不同的内存地址,不一定能同时访问?

·5210 字·11 分钟

之前写 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。

Single-Port SRAM 与 Dual-Port SRAM 结构对比

代价不是线性增长的。从 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 IndexBankBank 内部地址
000
110
220
330
401
511
621
731
4-Bank Interleaved Memory 地址映射

如果四个请求分别访问 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 有一个多级层次结构:

DRAM 层级结构:Channel → Rank → Bank Group → Bank

其中 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{WordIndex}(\text{row}, \text{col}) = \text{row} \times 32 + \text{col} $$

因此:

$$ \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访问元素WordIndexBankIndex
0tile[0][5]55
1tile[1][5]375
2tile[2][5]695
………5
31tile[31][5]9975

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访问元素WordIndexBankIndex
0tile[0][5]55
1tile[1][5]386
2tile[2][5]717
…………
27tile[27][5]8960
28tile[28][5]9291
29tile[29][5]9622
30tile[30][5]9953
31tile[31][5]10284

32 个 Lane → 32 个不同 Bank。无冲突。

tile\[32\]\[32\] 的 32-way Bank Conflict 与 tile\[32\]\[33\] Padding 后无冲突的对比

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) \):

$$ \text{Distinct Banks} = \frac{32}{\gcd(S, 32)} $$
Sgcd(S, 32)使用的 Bank 数
32321
33132
34216
35132
3648
37132

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.

参考资料
#

相关文章

Numerical Stability in ML Systems:从浮点误差到 GPU 计算

起因:H20 上 FP64 只有 1 TFLOPS,但计算要的是双精度 # 写这篇笔记的直接原因是一块 H20。业务里有一块对数值精度敏感的计算,需要接近 FP64 的结果,但 H20 的 FP64 算力只有 1 TFLOPS。对照同一张卡的其他规格,这个数字有多别扭很直观:FP32 是 44 TFLOPS,FP16/BF16 Tensor Core 是 148 TFLOPS,FP8 是 296 TFLOPS,FP64 只有 1——不到 FP32 的四十分之一,而满血的 H100 上 FP64 是 34 TFLOPS。

从 Register Tiling 到 Cache Tiling:理解高性能计算中的 Data Reuse

最近在看 CMU 15-442 的 Hardware Acceleration。课件翻到 Register Tiling,一个 2×3 output tile 的例子。我盯着那页 slide 看了一会儿——Register Tiling 这个词不陌生,但要我说清楚它和 Cache Tiling 的区别,以及它们到底在优化什么,我发现自己的理解一直停在"把矩阵切成小块"这个表面。

从 Dense FFN 到 MoE:Router、Token Dispatch 与 Grouped GEMM

·5127 字·11 分钟
上一篇 MoE 笔记把架构家族理了一遍——稀疏、稠密、Soft MoE,gate 在前还是在后,决定了算力形态和适用场景。 但那篇有一段伪代码一直让我不太舒服: 1for prob, idx in zip(topk_probs.unbind(1), topk_idx.unbind(1)): 2 out += prob.unsqueeze(1) * self.experts[idx](x) 逻辑上没问题。但想象一下真实场景:一个 batch 有几千个 token,每个 token 选 2 个 expert,就是上万个 token-expert 计算任务。用 Python for loop 逐个调 expert 的 forward,GPU 利用率会低得离谱。