算法复杂度、内存带宽与 Roofline 模型

有一百万个传感器读数，需要依次进行两项处理：先做标定 ，再加一个修正量 。 是第 个输入， 是对应输出， 是固定的数。下标 从 0 到 ， 表示读数个数。

可以先算完全部 ，存成一个临时数组，再计算 ；也可以读到一个 ，就在处理器中完成两项操作，直接写出 。

两种写法都随 线性增长，也做同样多的算术。现在只能选一项优化：合并这两个循环，或把处理器的浮点算力提高一倍。可以先保留自己的判断。下面先数工作，再数数据，最后算出各项改动在什么条件下有用。

先数工作量，理解复杂度保留了什么

这里把一次浮点加法或乘法各计为 1 次浮点运算，单位写作 FLOP。它是计数；FLOP/s 是每秒完成的浮点运算数，表示吞吐率。一次乘加融合指令 FMA 能计算乘法加加法，按这个惯例计为 2 FLOP，不能把指令数直接当作 FLOP 数。

对一个元素，先乘 、加 ，再加 ，共 3 FLOP。因此，两种实现的浮点工作量都是

表示总浮点运算数。这里按写出的逐元素操作计数，暂不把 预先合并；忽略循环控制、索引和地址计算。真实编译器可能改变这些操作，分析实测程序时要重新核对。

先在实验里改变 ，再改变实现。观察“浮点运算数”“循环体执行次数”和“临时空间”是否一起变化。保留一组结果，再把规模翻倍，检查自己的预测。

规模从 变为 时， 变成 ，增加一倍。复杂度分析通常先采用一个简化的计算模型：固定宽度的数值运算、索引和一次基本存取，各按常数成本计。这样可以研究增长规律，而不必为每台机器写一个不同的算法描述。

大 表示渐近上界，不表示秒数，也不自动表示最坏情况。 对非负成本函数 ，写作 ，意思是存在与 无关的正常数 和门槛 ，使所有 都满足 。若还存在正的常数倍下界，就写作 ，表示同一增长阶。最坏、平均或期望成本，需要另外说明所分析的是哪个函数。MIT 6.006 的渐近记号讲义给出了这些定义。

本例没有由输入数值触发的提前退出，两种实现都处理所有元素，因而在上述模型下时间都是 ，当然也都属于 。忽略常数后，它们看起来一样；这不意味着同一规模下耗时一样。

对比一个不同的任务：枚举 个读数中所有不同的无序二元组。第一个可与其余 个配对，第二个只与后面的 个配对，得到

仅枚举这些对就有 的成本。 翻倍时，计数之比为 ，随 增大趋近 4。这说明复杂度能识别增长阶的差别；这个配对任务与标定任务输出不同，不能拿两者的计数给实现排快慢。

空间也要明确口径。输入和输出各占 个元素，两种写法都需要；分两遍额外保存 ，辅助空间为 ，合并写法只需常数个临时数，辅助空间为 。占用多少空间与累计搬了多少数据是两个量：同一块存储反复读写，占用不变，流量却会增加。

把数据搬运纳入成本

处理器做算术前，需要把数据放进可直接使用的寄存器。主存容量较大；缓存位于它与处理器之间，用来保存近期使用的数据，减少反复访问主存。下面只统计主存与处理器侧缓存之间跨过边界的读写字节。

可以把计算想成工作台，把内存系统想成供料通道。工作台每秒能处理多少份、通道每秒能送多少字节，共同限制任务的完成速度。这个类比只帮助辨认两种吞吐约束，不包含真实机器的延迟、缓存和并行细节。

内存带宽是单位时间传输的数据量，本文记作 ，单位为 byte/s。容量表示能放多少，带宽表示每秒能搬多少，延迟表示一次请求要等多久。容量更大不自动意味着带宽更高；带宽更高也不保证单次请求更快。

先约定一个用于核算的流式模型：

• 输入、输出和中间数组使用互不重叠的连续存储，每个元素为 8 byte 的双精度数； 留在寄存器中，忽略其固定开销。
• 数组足够大，分两遍时，中间数组不能完整留在缓存供第二遍使用；每条列出的数组读写都跨过所选主存边界一次。
• 写入只计最终写出的数据，暂不计写分配引起的额外读流量；这对应一种理想化流量口径，例如适当的流式写入。它不是所有机器的默认行为。

分两遍时，跨边界的四项流量为：读 、写 、读 、写 ，各 byte。合并时， 在寄存器中用完即丢，只读 和写 。

同一标定任务	浮点运算	主存流量	额外临时数组
分两遍	FLOP	byte	byte
合并一遍	FLOP	byte	无

实验中可以逐步追踪四次或两次搬运；箭头表示跨越同一内存边界的读或写，播放速度仅用于讲解，不代表硬件速度。试着切换元素大小，区分“元素个数没变”和“流量没变”。

默认 ，分两遍搬运 32 MB，合并后为 16 MB。本文使用十进制单位：1 MB 为 byte，1 GB 为 byte；它们与以 1024 为倍数的 MiB、GiB 不同。

若可持续带宽假设为 GB/s，仅搬运这些字节就分别需要至少 ms 和 ms。计算方式是“总字节数除以每秒字节数”。这些都是教学模型下的下界，尚未计入其他约束，不是当前设备的测速结果。

实际流量还会受缓存行、预取和写策略影响。例如，冷的普通写入可能先把目标缓存行读进来，这叫写分配；之后还要写回。若两种实现中的每次数组写入都多读同样多的字节，上表会分别变成 和 byte。若第二遍直接在缓存命中 ，又不能照搬 的主存流量。要用硬件计数器或明确的缓存分析确认 ，不能只数源代码里的方括号。

STREAM 官方说明把它定位为可持续带宽基准，要求数据规模足够大，并解释了其字节计数约定。实测带宽时应同时记录线程数、访问模式、数据规模和读写计数口径；不要把接口标称速率直接当成应用一定能达到的吞吐。

每搬一个字节，能完成多少计算

用总浮点运算数除以主存流量，得到

是算术强度，单位 FLOP/byte，含义是平均每跨边界搬运 1 byte，完成多少浮点运算。下文统一使用这个名称；Roofline 原始工作强调缓存过滤后的主存流量，称为 operational intensity。必须指定内存层级，不能把主存带宽与寄存器侧的访问计数混用。原始技术报告讨论了这个边界。

代入刚才的流量：

强度翻倍是因为流量减半，工作量没有增加。 在分子分母中约掉了：在这套流式假设下，单纯增大数组不会提高强度。若规模改变导致缓存行为改变，就需要重新估计流量。

还可以通过数据复用提高强度：把同一批数据留在缓存或寄存器中，多完成一些任务本来就需要的计算，再换下一批。反复做无用运算也可能提高 FLOP/byte，但不会帮助原任务更快完成。

从两个时间下界推导 Roofline

假设所选处理器范围内的浮点吞吐上限为 FLOP/s。它要与程序的数值精度、指令种类和线程范围匹配。例如不能用低精度矩阵专用单元的峰值，评估普通双精度加法循环。

完成 FLOP 所需的计算时间至少为 ；传输 byte 所需的时间至少为 。计算和搬运可能重叠，但两种限制都必须满足，因此总耗时 满足

这里取较大值，是因为任务不可能比任一必要环节更早完成。它表示允许理想重叠时的乐观下界；若两者完全串行，时间会接近两项之和，而不是较大值。

对 ，实际浮点吞吐为 ，于是

Roofline 给出的是吞吐上限，而不是保证达到的性能。 将横轴设为算术强度、纵轴设为吞吐， 随强度上升， 保持水平，两者较低的一段构成屋顶形状。Williams、Waterman 与 Patterson 的 Roofline 工作建立了这种把工作量、数据流量与硬件限制联系起来的表示方法。

两条线的交点满足 ，因此转折点为

当 ，带宽给出的上限更低，处在带宽约束区；当 ，计算上限更低，处在计算约束区。这描述哪条屋顶更低，实际程序还可能被延迟、依赖或并行不足限制。

实验默认假设 GFLOP/s、 GB/s，转折点为 FLOP/byte。G 均表示 ，所以直接用这两个数相除即可。先保留默认点，再只提高算力；然后恢复参数，只提高带宽。最后把强度调到 16，重新比较两种改动。

图中两轴都采用以 2 为底的对数刻度，等距刻度表示相同倍数的增长，不是增加相同的绝对数。实心圆表示当前模型上限；保留点使用空心方块。它们都不是测量值。真实分析时，应该把实测点画在对应强度与实测吞吐的位置；上限与实测点之间的距离，才反映还有多少没有解释的损失。

回到数组标定，合并写法的 远低于转折点 10，因此其上限为

只将算力提高到 GFLOP/s，上限仍为 18.75；只将带宽提高到 GB/s，上限变为 37.5。对分两遍写法，原带宽下上限为 9.375 GFLOP/s。于是，在模型假设下，循环合并把上限提高一倍，而翻倍算力没有改变上限。

用时间再核对一次： 时 FLOP，在 FLOP/s 下计算至少需要 ms；两种写法的数据搬运至少需要 ms 和 ms，确实是搬运这一项更大。上限翻倍意味着有这样的潜力，实际加速比仍需测量。

矩阵乘法：复杂度不变，复用可以改变强度

现在换一个任务：把两个 的稠密矩阵相乘，得到第三个矩阵 。矩阵是按行列排列的数表，输出元素满足

这表示从 的第 行与 的第 列依次取数，相乘后累加。每个输出有 次乘法、 次加法，总计 FLOP；若从 0 开始执行 次乘加，按执行操作计为 FLOP。下面采用后者的计数口径，传统算法的算术复杂度为 。

若每次乘加都从主存重新读取两个 8 byte 的输入，且每个 在寄存器中累加后写出，流量约为 byte，强度随 增大接近 FLOP/byte。这是不复用输入的核算情形；普通三重循环也可能因缓存而复用，不能一概断言它必然产生这么多主存流量。

更好的组织方式是分块：把输出矩阵分成小块，每次取相应的输入块到快速存储中，反复使用其中的数。看一个边长为 的块更新， 是每块的行列数：

缓存中的 A 小块 ─┐
                  ├─ 块内元素反复参与乘加 ─→ 累积 C 小块
缓存中的 B 小块 ─┘

若三个 小块能同时放进所用快速存储，一次 做 FLOP。将这一次更新单独核算，输入块各读一次， 块读一次、写一次，共 byte，得到

例如 时为 2， 时为 4。三个双精度块分别需要约 24 KiB、96 KiB 的快速存储。这里假定块传输没有额外流量，且每块完整复用；大块未必放得下，也可能减少并行度。这个计算解释复用潜力，不能直接当成任意矩阵乘法库的实测强度。

整次矩阵乘法的流量为什么不能只按三张矩阵计算

三个矩阵一共有 个元素，但“只读一次 、只读一次 、只写一次 ”要求输入的复用能够在快速存储中实现。矩阵远大于缓存时，这通常做不到。 byte 是理想的必需数据流量口径，不是一般实现自动达到的流量。

若 整除 ，把上述每次块更新都按 byte 独立收费，总共有 次更新，得到 、。这是一个明确但保守的块调度模型。若把同一个 块留住，完成所有 方向更新后才写回，或复用相邻更新的 块，流量还会不同。要判断哪种复用能够实现，需要继续考虑缓存容量、替换行为和循环顺序。

两种组织都没有改变传统矩阵乘法的立方级算术工作量，却可能大幅改变跨内存层级的流量。复杂度分析与 Roofline 正是在回答不同层面的成本问题。

回到 Roofline 实验，选择“块更新 ”，其强度为 4。在默认机器上仍位于带宽约束区；若能实现强度 16 的复用方式，就会进入计算上限更低的一侧。把强度提高到转折点之后，继续增加复用不会再提高这条简单屋顶，但可能仍有其他收益或代价。

用一个条件变化检验判断

考虑同样的标定任务，但这次整个输入和中间数组都很小，能够留在缓存中。此时，分两遍不一定把 写到主存后又从主存读回。前面的 与 主存流量对比还能直接沿用吗？

核对依据：先固定内存边界，再选择屋顶

不能直接沿用。应先确认实际跨过主存边界的数据；中间数组的写和读若都在缓存内完成，就不产生前面所假定的两项主存流量。合并可能仍减少缓存流量、循环开销和临时分配，但主存 Roofline 未必能解释主要耗时。可以进一步分析对应层级的缓存带宽，并使用该层级的流量计算强度。

分层 Roofline 为 L1、L2、主存等边界分别建立带宽线。每条线必须使用对应的 ；同一段程序在不同层级的强度通常不同。Nsight Compute 的分层 Roofline 文档提供了这种分析方式。

再考虑按指针逐个访问、下一次地址依赖上一次结果的结构。即使每步字节数很少、算术强度很低，也可能因为等待请求完成而远低于带宽屋顶。增加带宽不能自动消除这种依赖。数据连续且有足够并发请求的数组流式处理，更符合本文用吞吐上限解释性能的出发点。

实际优化时，先确认输入规模和所需输出，避免做不必要的工作；再统计重要计算与跨层级流量，选用匹配精度、线程范围和访问模式的上限。把实测 与屋顶比较后，才能决定继续减少流量、改善并行，还是优化算术路径。若离屋顶很远，应检查延迟、依赖、线程调度或启动开销，而不是仅凭点位于斜线下就认定带宽已经用满。NERSC 的 Roofline 指南说明了理论与经验屋顶的使用范围。

参考资料

1. MIT 6.006，Recitation 1: Asymptotic Complexity, Peak Finding，2011。课程讲义。
2. Samuel Williams、Andrew Waterman、David Patterson，Roofline: An Insightful Visual Performance Model for Multicore Architectures，Communications of the ACM，52(4)，65–76，2009。DOI；2008 年技术报告。
3. John D. McCalpin，STREAM Benchmark Reference Information。官方说明与计数规则。
4. NERSC，Roofline Performance Model。官方指南。
5. NVIDIA，Nsight Compute User Guide，Roofline Charts。官方文档。