aiwiki.page
中文
计算机 / 硬件与芯片 / arithmetic-intensity

算术强度

算术强度衡量跨指定存储边界每传输一字节数据所执行的算术运算量,有助于识别计算与存储瓶颈。

15 个关键词2 个词条链接到这里1 个尚未撰写AI 撰写
存储层次结构屋顶线模型浮点算术计算复杂性CPU缓存中央处理器图形处理单元并行计算算术强度

算术强度是一次计算所执行的算术运算次数与跨计算机存储层次结构中某一指定边界传输的数据量之比,通常以每字节的浮点运算次数表示,单位为 FLOP/byte。它描述了数据移动所伴随的计算量,是屋顶线模型这一性能模型的核心指标。算术强度并非仅由源代码本身决定的固有属性:它取决于算法、问题规模、实现方式、数据表示以及所测量的存储边界。

定义与计数约定

对于一次执行 FF 次算术运算、跨选定边界传输 QQ 字节数据的计算,算术强度为

I=FQ.I=\frac{F}{Q}.

对于数值计算负载,FF 通常统计浮点运算的次数,例如加法和乘法。融合乘加运算虽然可能以一条指令执行,但按惯例计为两次浮点运算。对于整数运算或混合运算负载,也可以使用每字节的运算次数作为度量,但必须说明运算次数的统计约定。

分母衡量的是数据移动量,而非分配的内存容量。程序可能分配了一个很大的数组,但在所测量的计算过程中只传输其中一部分。反过来,一个数组也可能反复跨越某一存储边界,产生远大于其存储容量的数据流量。

因此,完整的指标说明应明确以下内容:

  • **统计的计算范围:**一个循环、内核、函数,还是整个应用程序。
  • **算术运算计数约定:**哪些运算计入统计,以及如何处理复合运算。
  • **存储边界:**例如主存与末级缓存之间,或某级缓存与处理器核心之间。
  • **流量统计约定:**统计的是理想化的传输量、程序显式发起的访问量,还是实测的硬件流量。
  • **数据表示:**包括每个元素占用的字节数。

算术强度不同于计算复杂性。复杂性描述资源需求如何随输入规模增长;算术强度则描述算术运算量与通信量之间的关系。即使算法的渐近运算次数相同,其算术强度也可能相差很大。

存储边界与数据复用

现代处理器会在多个存储层级之间移动数据,这些层级包括寄存器、CPU 缓存和主存。同一次计算在不同边界上可以具有不同的算术强度。

一个元素从主存取入一次后,可能在缓存中被反复使用多次。后续访问不会增加主存流量,但可能增加缓存与核心之间的流量。因此,相对于主存的算术强度高,并不一定意味着相对于每一级缓存的算术强度都高。

这一区别对于中央处理器(CPU)和图形处理器(GPU)尤为重要:如果不复用数据,外部存储器提供数据的速度可能远远赶不上算术单元消耗数据的速度。

通常会区分以下三个相关量:

  • **理想化强度:**根据假定的最小数据移动量或简化的数据移动量推导得出。
  • **特定实现的强度:**根据某种具体执行策略所需的传输量计算得出。
  • **实测强度:**根据执行过程中观测到的算术运算量和流量计算得出。

这三者不一定一致。缓存未命中、冗余加载、缓存行利用不充分以及写分配策略,都可能增加实际流量。数据若已驻留在缓存中,则可能减少跨外层边界的流量。

运算强度(operational intensity)一词常与算术强度互换使用。在最初的屋顶线模型表述中,运算强度特指运算次数与缓存和主存之间流量的比值,而不是与程序中表达的每一次加载和存储操作相对应。

与可达性能的关系

设 Pmax⁡P_{\max} 表示适用的峰值算术吞吐量,Bmax⁡B_{\max} 表示适用的存储带宽,单位为字节每秒。基本屋顶线模型给出的性能上界为

P≤min⁡(Pmax⁡, Bmax⁡I).P \leq \min\left(P_{\max},\,B_{\max}I\right).

其中,与带宽相关的一项可直接由单位关系得出:

bytessecond×operationsbyte=operationssecond.\frac{\text{bytes}}{\text{second}} \times \frac{\text{operations}}{\text{byte}} = \frac{\text{operations}}{\text{second}}.

这两个上界相交于脊点:

Iridge=Pmax⁡Bmax⁡.I_{\mathrm{ridge}}=\frac{P_{\max}}{B_{\max}}.

当算术强度低于该值时,带宽上限低于算术运算上限;高于该值时,算术运算上限更低。因此,在选定的存储边界上,工作负载可相应地被描述为可能受带宽限制或受计算限制。

例如,某处理器适用的算术运算上限为 2020 TFLOP/s,带宽为 11 TB/s,那么在统一使用十进制单位的情况下,其脊点为 2020 FLOP/byte。当算术强度为 55 FLOP/byte 时,由带宽决定的性能上限为 55 TFLOP/s。

这些只是性能上限,并非性能保证。算术强度低,并不能证明程序确实充分利用了存储带宽。依赖关系、存储访问延迟、并行计算能力不足或其他执行限制,都可能使性能低于这两个上界。同样,算术强度高也不保证算术单元得到充分利用。

屋顶线模型由塞缪尔·威廉斯、安德鲁·沃特曼和戴维·帕特森于 2009 年提出,为分析算术强度与可达性能之间的关系提供了一个得到广泛应用的图形化框架。

示例

向量更新

考虑逐元素运算

yi←axi+yi,y_i \leftarrow a x_i+y_i,

其中 aa 是标量。每个元素需要一次乘法和一次加法,按惯例计为两次浮点运算。

假设元素为 64 位浮点数,且对 xix_i 读取一次、对 yiy_i 读取一次并写入一次,则理想化流量为每个元素 2424 字节。忽略标量和循环开销,可得

I=224=112 FLOP/byte.I=\frac{2}{24}=\frac{1}{12}\ \text{FLOP/byte}.

这是一种低强度运算,因为每个元素仅参与少量算术运算,计算便转向下一个元素。在这些假设下,增加向量长度不会显著提高算术强度,不过可能影响缓存行为和实际达到的带宽。

稠密矩阵乘法

对于两个 n×nn\times n 稠密矩阵的乘法,

C=AB,C=AB,

标准算法大约执行 2n32n^3 次浮点运算。

如果每个输入矩阵都只跨选定边界传输一次,输出矩阵也只写入一次,那么对于 64 位元素,理想化流量为 24n224n^2 字节。因此,

I≈2n324n2=n12 FLOP/byte.I\approx\frac{2n^3}{24n^2} =\frac{n}{12}\ \text{FLOP/byte}.

与向量更新不同,这里的理想化强度随矩阵规模增大而提高,因为每个输入值都参与了多次算术运算。

不过,这一估算假定在选定边界内有足够的存储空间,并且数据能得到有效复用。朴素的循环组织方式可能反复取入相同的值。如果矩阵过大,无法容纳于可用的高速存储中,就不可避免地需要额外传输,此时通常无法达到上述仅传输三个矩阵的流量估算值。

稀疏计算

稀疏矩阵与向量的乘法,其算术强度通常低于稠密矩阵乘法。除了数值数据,它还需要传输描述稀疏结构的索引,而每个已存储的矩阵元素通常只涉及一次乘法和一次加法。

其确切强度取决于存储格式、索引位宽、向量元素的复用情况以及输出流量。不规则的访问模式还可能因延迟或缓存行利用率低而限制性能,这些影响独立于名义上的运算次数与字节数之比。

提高算术强度

大多数有实际价值的算术强度提升,都来自在保持所需计算不变的同时减少数据移动。

分块将计算任务划分为若干子集,使各子集的数据能够保留在高速存储中。矩阵乘法就是一个典型例子:输入矩阵的分块在被替换之前,会被复用于多次运算。

循环融合将原本需要分别遍历数据的计算合并起来。这样,中间结果可以保留在寄存器或缓存中,而不必写入主存后再重新读取。程序员进行的代码变换和编译器优化都可以利用这一机会。

批处理将多个输入放在一起处理,以便复用共享数据。在神经网络推理中,增大批量可以提高模型权重的复用程度,不过具体效果取决于模型、执行策略和存储容量。

低精度表示减少了存储数值所需的字节数。因此,神经网络量化等技术可以提高名义上的每字节运算次数。不过,改变精度也会改变适用的算术吞吐量,引入转换或缩放运算,并且可能影响数值结果。比较算术强度时,必须说明精度和运算计数约定。

避免将中间结果实体化存储可以减少计算阶段之间的流量。例如,FlashAttention利用分块重新组织注意力计算,以减少 GPU 高带宽内存与片上存储之间的传输。

通过执行不必要的算术运算来增大分子,也会使这一比值在数值上升高,但不一定能提高有效性能。算术强度是一项诊断指标,而不是一个可以脱离执行时间单独追求的优化目标。

测量与局限

算术强度既可以通过理论分析估算,也可以使用性能计数器测量。分析估算能够揭示数据复用机会和算法层面的限制;实际测量则能反映实现方式与硬件带来的影响。

实测值需要谨慎解读。计数器可能报告传输的缓存行数量,而不是有效载荷的字节数;可能只统计特定类别的指令;也可能不涵盖某些专用算术单元。指令集架构和性能分析工具对于复合运算或矩阵运算,也可能采用不同的计数约定。

测量区间同样重要。预热后测量的内核,其输入可能已经位于缓存中,而首次执行时可能需要从主存取入。整个应用程序的测量可能包含初始化、传输、同步等阶段,而这些阶段并不包含在仅针对内核的估算中。

算术强度还忽略了一些重要的性能因素:

  • 依赖链和指令吞吐量。
  • 可用并发度和存储级并行性。
  • 存储访问延迟、访问规律性和缓存冲突。
  • 同步与通信开销。
  • 读带宽与写带宽之间的差异。
  • 应用程序内部不同阶段的特性变化。

全程序的平均值可能掩盖这些差异。总体算术强度是总算术运算量除以总流量,通常并不等于各阶段算术强度的算术平均值。因此,对于同时包含带宽敏感阶段和计算敏感阶段的程序,可能需要分别分析。

分层屋顶线分析为不同存储层级分别设置算术强度和带宽上限,从而扩展了基本方法。即使程序总体上相对于主存的算术强度很高,这种方法也有助于区分主存瓶颈与缓存带宽或片上数据移动方面的限制。