计算机体系结构 · 第 3 课

Little 定律与内存级并行:延迟很高,怎样才能跑满带宽?

2026 年 10 月 22 日|第一周|约 18 分钟

归档说明: 此篇依据当日授课主题与课程规划重新整理为完整教学版,并非旧聊天消息的逐字恢复。测验独立存为 JSON,不在本课稿中泄露答案。

本课目标

理解内存吞吐为何同时受通道带宽、请求延迟和在途容量限制;亲手推导 $N=\lambda W$、$B\le Hs/W$ 与相应的工作量时间下界;区分指针追踪与无依赖数组扫描,并通过一个数值案例理解 MLP(Memory-Level Parallelism)。

一、先从延迟与吞吐的冲突开始

假设处理器一次从 DRAM 读 64 Byte 的 Cache Line,往返延迟 100 ns。若每次都必须等前一个请求返回才能确定下一个地址,则一秒内最多约发出 $10^7$ 个顺序相关请求,对应 $64\times10^7$ Byte/s,即 0.64 GB/s。即使 DRAM 通道标称 100 GB/s,也无法靠一条依赖链填满。

原因不是内存每秒“搬不动”,而是处理器在任一时刻只能等待一个尚未完成的请求。若软件可以暴露 H 条独立请求,处理器就能在一次请求的等待期间让其他请求并行在途。

工作负载 地址依赖 可暴露并发 可能出现的瓶颈
链表指针追踪 下一节点地址依赖当前读取结果 接近 1 延迟受限
多独立数组流 地址能提前计算 可能很多 带宽/请求槽位
大量随机独立访问 地址独立但空间局部性差 取决于并发容量 MSHR/DRAM Bank/带宽

这解释了“同样是 DRAM Miss,访问模式却影响巨大”的现象。

二、从请求驻留时间推导 Little 定律

设系统处于足够长的稳定统计窗口,平均每秒完成 $\lambda$ 个请求,每条请求从发出到完成平均驻留 $W$ 秒,时间平均在途请求数为 $N$。

直观做法:在时间轴上画每个请求“发出到完成”的区间。把这些区间的长度累加,等于在途曲线 $n(t)$ 下的总面积。如果观测窗口足够长且边界影响可忽略,单位时间内完成请求数乘以平均驻留时间等于平均同时在途数:

\[N=\lambda W.\]

量纲检验:请求/秒 × 秒 = 请求,右左一致。它不是“请求延迟总和直接作为 CPU stall”,而是稳态计数关系。

如果任意时刻最多允许 H 个在途请求,那么 $N\le H$,所以

\[\lambda\le\frac H W.\]

假设每请求恰好传输 s Byte(并且没有合并、重试、不同大小事务),带宽 $B_{\mathrm{MLP}}=\lambda s$,得

\[\boxed{B_{\mathrm{MLP}}\le\frac{Hs}{W}.}\]

与此同时,真实 DRAM 通道本身还有可持续带宽上限 $B_{\mathrm{channel}}$。因此

\[\boxed{B_{\mathrm{effective}}\le\min(B_{\mathrm{channel}},Hs/W).}\]

这两个是同时成立的上限。取最小值是上界,而不是吞吐性能的保证。

三、可以拖动的请求并发图

[[viz:little]]

图示分五步把“槽位→完成率→请求大小→字节吞吐→总限制”连起来。改变 H 或 W 后观察哪一个屋顶更紧。数值改变只是假设参数变化,不等于 CPU 真能持续占满所有槽位。

四、一个数值案例:如何算 MSHR 需求

假设一次请求 64 Byte、驻留时间 80 ns、整机带宽 100 GB/s,硬件最多在途 32 条独立请求。

第 1 步:请求完成率上限。

\[\lambda\le \frac{32}{80\times10^{-9}}=4\times10^8\text{ requests/s}.\]

第 2 步:换算带宽。

\[B_{\mathrm{MLP}}\le4\times10^8\times64=25.6\times10^9\text{ Byte/s}=25.6\text{ GB/s}.\]

第 3 步:与通道带宽比较。

\[B_{\mathrm{effective}}\le\min(100,25.6)=25.6\text{ GB/s}.\]

第 4 步:反求跑满通道的最低平均在途数。 若想通过 64 Byte 请求在 80 ns 平均延迟下长期达到 100 GB/s,需要

\[N=B W/s=\frac{100\times80}{64}=125.\]

若硬件最多只有 32 槽位,在该简化模型中不可能达到 100 GB/s。需要注意实际延迟可能随负载排队而变化,不能把空载延迟与满载吞吐拼在一起。

五、有限工作量:为什么 T≥MW/H?

如果 Kernel 总共必须完成 M 个没有合并的请求,所有请求均在主体阶段发起且完成,每条请求的驻留时间分别为 $W_i$,平均 $W=(1/M)\sum W_i$,则

\[\int_0^T n(t)\,dt=\sum_{i=1}^M W_i=MW.\]

因为任何时刻 $n(t)\le H$,有

\[MW\le HT,\qquad \boxed{T\ge MW/H.}\]

这不是简单重复 $N=\lambda W$:它对一个有限执行窗口给出请求占槽位面积的直接证明。若每条请求平均传输 s Byte,总流量 Q=Ms,等价于 $T\ge QW/(Hs)$。

还需考虑至少 $T\ge Q/B_{\mathrm{channel}}$;如果 Kernel 有运算 F、计算资源上限 P,则 $T\ge F/P$。主体计算与内存传输能够重叠时:

\[\boxed{T\ge\max(F/P,Q/B_{\mathrm{channel}},QW/(Hs)).}\]

这个式子是下界而非一个完整的 CPI 预测公式。

六、反例与适用边界

反例 1:MSHR 增加没有收益。 如果程序是一条严格指针追踪链,软件只能生成一个独立未完成请求,那么硬件 H 从 16 加到 64 并不会让实际平均在途数 N 自动增加。

反例 2:更大并发不等于更小延迟。 到达 DRAM 的请求越来越密集可能加重队列排队,使平均 W 增大,因此不能用改变 H 前的 W 机械预测提升。

反例 3:实际 Cache Line 与请求大小不同。 一个逻辑 Load 未必对应一次完整 DRAM 事务:Cache 命中、合并、预取、写回和访问粒度都会改变流量 Q。

在真实实验中建议同时测:平均在途事务数、DRAM bytes、内存访问往返延迟、Miss 数及 MSHR 使用、CPU Cycles、IPC,并保持测量窗口和流量层级一致。观察吞吐低于上界时,不要只从单个指标下结论。

七、学习小结与下一讲

通过请求在途时间面积,已经建立“在途数决定最多每秒完成多少请求,请求大小决定最大字节吞吐”的严谨解释。与通道带宽屋顶取最小值后,性能更接近真实硬件限制,但仍依赖软件可暴露并发。

下一讲第 4 课将把这些约束放进 Roofline 模型,结合计算算术强度、Tiling 和缓存层级分析瓶颈迁移。

四级分级测评(100 分)

前三题客观评分,第四题开放推导由人工/ChatGPT 或自评完成;初次阅读不提供标准答案。

Lv1|稳态吞吐与因果|15 分|约 2 分钟

平均内存访问延迟 W 保持不变且一条在途请求占用一个槽位。在稳定状态下,哪一结论最严谨?

A. 平均在途数 N、完成吞吐率 λ、延迟 W 满足 N=λW;提高槽位上限仅提高可能的吞吐屋顶

B. 只要硬件有 H 个槽位,软件必定始终保持 N=H

C. 访问延迟较高时,所有程序的 DRAM 吞吐一定更高

D. 一条链式依赖访问和 H 条互不依赖访问拥有相同最大并发

可选提示:把平均在途请求数和可持续完成率联系起来;区分容量上限与实际利用。

Lv2|Little 数值计算|20 分|约 4 分钟

在途独立请求最多 H=48 条,每请求恰好传输 64 Byte,平均请求驻留时间 W=120 ns,忽略通道上限且假设可维持满并发。理论带宽上界是多少 GB/s?采用十进制单位。

可选提示:将 Hs/W 以 Byte/ns 计算。1 Byte/ns 等于 1 GB/s。

Lv3|MLP 机制边界|25 分|约 5 分钟

关于 MLP、内存延迟和 DRAM 带宽,以下哪些判断正确?(多选)

A. 单条链表指针追踪通常难以同时发出很多相互独立的内存请求,即使 MSHR 上限较大也可能延迟受限

B. 只要观察到 DRAM 带宽远低于通道峰值,就能断定工作负载是计算受限

C. 在请求大小、平均驻留延迟、实际并发均保持不变时,吞吐率可由 N/W 估算;但改变硬件并发上限不必使实际 N 同步提高

D. 增大 MSHR 数必然降低每条请求的 DRAM 服务延迟

可选提示:判断哪些说法描述公式所允许的结论,哪些把上界当作必然性能。

Lv4|资源下界证明与实验|40 分|约 12 分钟

研究一个固定工作量的 Kernel:需完成 M=24×10^6 个互不合并的 DRAM 请求,每条 64 Byte,平均驻留 W=100 ns,机器并发槽位上限 H=32、通道带宽上限 B=60 GB/s,另需 F=12 GFLOP,计算上限 P=800 GFLOP/s。A(10分)从在途请求数—时间面积推导 T≥MW/H。B(10分)分别计算计算、通道带宽与并发时间下界,组合成总主体时间下界。C(10分)将 H 升到128,保持其他参数不变,重新计算并解释瓶颈迁移。D(10分)设计两项可证伪“并发受限”的实验,控制变量并说明应采集的指标。

可选提示:三个下界都要计算并取最大,且证明应先把每个请求占槽位的时间积分起来;实际运行时间不等于下界。