展开将如何影响每个元素计数 CPE 的周期
how will unrolling affect the cycles per element count CPE
- 如何使用这些代码片段计算 CPE（每个元素的周期数）？
- 2 个给定代码片段的 CPE 有何不同？
我有这段代码
void randomFunction(float a[],float Tb[],float c[],long int n){
int i,j,k;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
for(k=0;k<n-1;k++){
temp+= a[i*n+k] * Tb[j*n+k];
}
}
这是最内层循环的程序集，来自 GCC10.3 -O2 (https://godbolt.org/z/cWE16rW1r)，对于具有局部 float temp=0; 的函数版本，它 returns 所以循环不会被优化掉：
.L4:
movss (%rcx,%rax), %xmm0
mulss (%rdx,%rax), %xmm0
addq , %rax
addss %xmm0, %xmm1
cmpq %rax, %rsi
jne .L4
现在我正在尝试 'optimise it' 使用展开。
void randomUnrollingFunction(float a[],float Tb[],float c[],long int n){
int i,j,k;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
for(k=0;k<n-1;k+=2){//this is the unrolled portion by 2
temp+= a[i*n+k] * Tb[j*n+k];
temp+= a[i*n+k+1]* Tb[j*n+k+1];
}
}
我想知道按因子 2 展开后将实现的估计 CPE 是多少。
CPE 是周期数/指令数
这是延迟信息：
提前感谢您的帮助！
您的循环在 addss 延迟（浮点加法）上完全成为瓶颈，每 1 个元素 3 个周期。无序的 exec 让另一个工作 运行 在这个的“影子”中。假设您的类似 Haswell CPU 的内存带宽可以跟上1
这种展开的方式根本没有帮助，不会改变串行依赖链除非你用-ffast-math编译或者让编译器把它变成
temp1 += a[...+0]* Tb[...+0];
temp2 += a[...+1]* Tb[...+1];
或者在将它们输入该串行依赖项之前添加对，例如
temp += a[]*Tb[] + a[+1]*Tb[+1];
一个长的串行依赖链是最糟糕的，而且在数值上也不是很好：成对求和（或者尤其是使用多个累加器朝那个方向迈出一步）在数值上会更好并且性能也会更好。 ().
（如果您的多个累加器是 SIMD 向量的 4 个元素，则可以使用相同的 asm 指令模式完成 4 倍的工作量。但是您需要展开多个 向量，因为 addps 与现代 x86 CPUs 上的 addss 具有相同的性能特征。）
脚注 1：每 3 个周期各 4 个字节的两个顺序读取流；当然，台式机 Haswell 可以跟上，甚至 Xeon 可能会与许多其他内核竞争内存带宽。但是从 a[] 的读取可能会命中缓存，因为 a[i*n+k] 是重复的同一行，直到我们进入下一个外循环迭代。因此，当我们扫描一行 Tb 时，只有 1 行 a[] 必须在缓存中保持热（以便在下一次中间迭代中获得命中）。因此，如果 n 不是 巨大的 ，a[] 必须从 DRAM 进入一次总计，但我们循环遍历整个 Tb[]，以便 n次。
更详细的版本
参见 What considerations go into predicting latency for operations on modern superscalar processors and how can I calculate them by hand? - look for the dependency chains (in this case the addss into %xmm1). Also A whirlwind introduction to dataflow graphs。
然后在后端和前端寻找吞吐量瓶颈。在您的情况下，延迟占主导地位。 （假设前端与这个 Haswell 后端匹配，尽管跟上这个后端延迟瓶颈并不需要太多时间。另外，我讨厌他们给他们的“功能单元”从 1 开始，而不是遵循英特尔对具有 ALU 的端口 0、1、5、6 的编号。Haswell 的 FP 加法器在端口 1 上，端口 2/3 是 load/store-AGU 单元等）
ADDSS有3个周期延迟，所以temp += ...每3个周期只能执行一次。加载/MULSS操作只是独立地为ADDSS准备输入，循环开销也是独立的。
请注意，如果不是延迟瓶颈，您的循环将在真正的 Haswell（每个周期 4 个融合域 uops）的前端出现瓶颈，而不是在后端功能单元上。循环是 5 个融合域 uops，假设 cmp/jne 的宏融合，并且 Haswell 可以保持内存源地址微融合，尽管索引寻址模式。 (Sandybridge would un-laminate it.)
在一般情况下，了解后端功能单元是不够的。前端也是一个常见的瓶颈，尤其是在必须存储某些东西的循环中，例如实际的 matmul。
但是由于对 ADDSS 的串行依赖（实际上跨外循环），唯一重要的是依赖链。
即使分支在内部循环的最后一次迭代中预测错误（当分支未被采用而不是正常采用时），这只会给后端更多时间来咀嚼那些挂起的 ADDSS 操作，而前端-end 自行整理并开始下一个内部循环。
由于您以不改变串行依赖性的方式展开，因此它对性能的影响为零，除了 tiny n。（对于 tiny n，整个事情可能会与调用者 before/after 调用中的独立工作重叠一些这项工作。在这种情况下，保存指令可能会有所帮助，还允许乱序执行“看得更远” “。 是 OoO exec 可以（部分）重叠两个独立的 imul dep 链的情况，它们在程序顺序中是一个接一个。
当然，此时您正在考虑所显示内容之外的代码。即使对于 n=10，也就是 10^3 = 1000 次内部迭代，Haswell 的 ROB 只有 192 微指令大，RS 为 60 个条目。 (https://www.realworldtech.com/haswell-cpu/3/).
以有用的方式展开
另见 回复：以 做 的方式展开，创建更多指令级并行性，隐藏 FP 依赖链。
以不同的方式展开，每次循环迭代只对 temp 求和一次，将在每次迭代中保持相同的循环，同时仍然使您处理的元素数量加倍。
for(k=0;k<n-1;k+=2){//this is the unrolled portion by 2
temp += (a[i*n+k] * Tb[j*n+k] +
a[i*n+k+1]* Tb[j*n+k+1]);
}
显然，您可以继续这样做，直到 运行 进入前端或后端吞吐量限制，例如每个时钟添加一个。上面的版本每 3 个时钟执行两次加法。
您的“功能单元”table 没有列出 FMA（融合乘加），但真正的 Haswell 有它，其性能与 FP mul 相同。如果有的话，它也无济于事，因为您当前的循环结构每个 mul+add 执行 2 个负载，因此将其减少到 2 个负载和一个 FMA 仍然会成为负载瓶颈。可能有助于提高前端吞吐量？
可能有助于减少负载的方法是展开一个外循环，同时使用 a[i*n+k] 和 a[(i+1)*n+k] 以及一个 Tb[j*n+k]。这当然会改变计算的顺序，因此对于没有 -ffast-math 的编译器来说是不合法的，因为 FP 数学不是严格关联的。
这是 matmul 的缩减，允许更好的优化
（错误等等，您的代码没有显示 temp 在哪里重新初始化，或者 c[] arg 的用途。我只是假设它是全局的或其他东西，但可能你实际上屠杀了一个普通的 matmul 函数，它在每次内部迭代后存储一个单独的 temp 到 c[] 通过取出它。在那种情况下，单独的中间循环迭代 之间的 OoO exec 是 与中型 n 相关。但是您没有显示调度程序/ROB 大小，这不是您可以轻松建模的东西；您需要实际进行基准测试。所以本节可能仅适用于问题我发明的，不是你想问的！）
您的循环似乎在对 matmul 结果的元素求和，但结构仍然像 matmul。即做行 x 列点积，但不是将其存储到 N x N result[...] 矩阵中，您只是对结果求和。
这相当于对两个矩阵之间元素的每个成对乘积求和。由于我们不再需要将单独的行 x 列点积分开，因此可以实现 很多 优化！ （这个求和顺序没有什么特别或理想的；其他顺序会有不同但可能不会更糟的舍入误差。）
例如，您不需要将 b 转置为 Tb，只需使用 b（除非它已经自然转置，在这种情况下没问题）。您的矩阵是正方形的，所以 完全没有关系。
此外，您可以简单地从 a[] 加载一个或几个元素并循环遍历 Tb[]，使用 FMA 运算执行这些乘积，每个 FMA 加载一次，进入 10 或 12 个向量累加器。 （或者当然缓存块循环遍历 Tb 的连续部分，该部分可以在 L1d 缓存中保持热。）
这可能接近 Haswell 的最大 FLOPS 吞吐量，即每个时钟 2x 256 位 FMA = 8（每个 YMM 向量 float 个元素）x 2 FMA/时钟 x 2 FLOP/FMA = 32 FLOP/时钟.
- 如何使用这些代码片段计算 CPE（每个元素的周期数）？
- 2 个给定代码片段的 CPE 有何不同？
我有这段代码
void randomFunction(float a[],float Tb[],float c[],long int n){
int i,j,k;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
for(k=0;k<n-1;k++){
temp+= a[i*n+k] * Tb[j*n+k];
}
}
这是最内层循环的程序集，来自 GCC10.3 -O2 (https://godbolt.org/z/cWE16rW1r)，对于具有局部 float temp=0; 的函数版本，它 returns 所以循环不会被优化掉：
.L4:
movss (%rcx,%rax), %xmm0
mulss (%rdx,%rax), %xmm0
addq , %rax
addss %xmm0, %xmm1
cmpq %rax, %rsi
jne .L4
现在我正在尝试 'optimise it' 使用展开。
void randomUnrollingFunction(float a[],float Tb[],float c[],long int n){
int i,j,k;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
for(k=0;k<n-1;k+=2){//this is the unrolled portion by 2
temp+= a[i*n+k] * Tb[j*n+k];
temp+= a[i*n+k+1]* Tb[j*n+k+1];
}
}
我想知道按因子 2 展开后将实现的估计 CPE 是多少。
CPE 是周期数/指令数
这是延迟信息：
提前感谢您的帮助！
您的循环在 addss 延迟（浮点加法）上完全成为瓶颈，每 1 个元素 3 个周期。无序的 exec 让另一个工作 运行 在这个的“影子”中。假设您的类似 Haswell CPU 的内存带宽可以跟上1
这种展开的方式根本没有帮助，不会改变串行依赖链除非你用-ffast-math编译或者让编译器把它变成
temp1 += a[...+0]* Tb[...+0];
temp2 += a[...+1]* Tb[...+1];
或者在将它们输入该串行依赖项之前添加对，例如
temp += a[]*Tb[] + a[+1]*Tb[+1];
一个长的串行依赖链是最糟糕的，而且在数值上也不是很好：成对求和（或者尤其是使用多个累加器朝那个方向迈出一步）在数值上会更好并且性能也会更好。 (
（如果您的多个累加器是 SIMD 向量的 4 个元素，则可以使用相同的 asm 指令模式完成 4 倍的工作量。但是您需要展开多个 向量，因为 addps 与现代 x86 CPUs 上的 addss 具有相同的性能特征。）
脚注 1：每 3 个周期各 4 个字节的两个顺序读取流；当然，台式机 Haswell 可以跟上，甚至 Xeon 可能会与许多其他内核竞争内存带宽。但是从 a[] 的读取可能会命中缓存，因为 a[i*n+k] 是重复的同一行，直到我们进入下一个外循环迭代。因此，当我们扫描一行 Tb 时，只有 1 行 a[] 必须在缓存中保持热（以便在下一次中间迭代中获得命中）。因此，如果 n 不是 巨大的 ，a[] 必须从 DRAM 进入一次总计，但我们循环遍历整个 Tb[]，以便 n次。
更详细的版本
参见 What considerations go into predicting latency for operations on modern superscalar processors and how can I calculate them by hand? - look for the dependency chains (in this case the addss into %xmm1). Also A whirlwind introduction to dataflow graphs。
然后在后端和前端寻找吞吐量瓶颈。在您的情况下，延迟占主导地位。 （假设前端与这个 Haswell 后端匹配，尽管跟上这个后端延迟瓶颈并不需要太多时间。另外，我讨厌他们给他们的“功能单元”从 1 开始，而不是遵循英特尔对具有 ALU 的端口 0、1、5、6 的编号。Haswell 的 FP 加法器在端口 1 上，端口 2/3 是 load/store-AGU 单元等）
ADDSS有3个周期延迟，所以temp += ...每3个周期只能执行一次。加载/MULSS操作只是独立地为ADDSS准备输入，循环开销也是独立的。
请注意，如果不是延迟瓶颈，您的循环将在真正的 Haswell（每个周期 4 个融合域 uops）的前端出现瓶颈，而不是在后端功能单元上。循环是 5 个融合域 uops，假设 cmp/jne 的宏融合，并且 Haswell 可以保持内存源地址微融合，尽管索引寻址模式。 (Sandybridge would un-laminate it.)
在一般情况下，了解后端功能单元是不够的。前端也是一个常见的瓶颈，尤其是在必须存储某些东西的循环中，例如实际的 matmul。
但是由于对 ADDSS 的串行依赖（实际上跨外循环），唯一重要的是依赖链。
即使分支在内部循环的最后一次迭代中预测错误（当分支未被采用而不是正常采用时），这只会给后端更多时间来咀嚼那些挂起的 ADDSS 操作，而前端-end 自行整理并开始下一个内部循环。
由于您以不改变串行依赖性的方式展开，因此它对性能的影响为零，除了 tiny n。（对于 tiny n，整个事情可能会与调用者 before/after 调用中的独立工作重叠一些这项工作。在这种情况下，保存指令可能会有所帮助，还允许乱序执行“看得更远” “。imul dep 链的情况，它们在程序顺序中是一个接一个。
当然，此时您正在考虑所显示内容之外的代码。即使对于 n=10，也就是 10^3 = 1000 次内部迭代，Haswell 的 ROB 只有 192 微指令大，RS 为 60 个条目。 (https://www.realworldtech.com/haswell-cpu/3/).
以有用的方式展开
另见
以不同的方式展开，每次循环迭代只对 temp 求和一次，将在每次迭代中保持相同的循环，同时仍然使您处理的元素数量加倍。
for(k=0;k<n-1;k+=2){//this is the unrolled portion by 2
temp += (a[i*n+k] * Tb[j*n+k] +
a[i*n+k+1]* Tb[j*n+k+1]);
}
显然，您可以继续这样做，直到 运行 进入前端或后端吞吐量限制，例如每个时钟添加一个。上面的版本每 3 个时钟执行两次加法。
您的“功能单元”table 没有列出 FMA（融合乘加），但真正的 Haswell 有它，其性能与 FP mul 相同。如果有的话，它也无济于事，因为您当前的循环结构每个 mul+add 执行 2 个负载，因此将其减少到 2 个负载和一个 FMA 仍然会成为负载瓶颈。可能有助于提高前端吞吐量？
可能有助于减少负载的方法是展开一个外循环，同时使用 a[i*n+k] 和 a[(i+1)*n+k] 以及一个 Tb[j*n+k]。这当然会改变计算的顺序，因此对于没有 -ffast-math 的编译器来说是不合法的，因为 FP 数学不是严格关联的。
这是 matmul 的缩减，允许更好的优化
（错误等等，您的代码没有显示 temp 在哪里重新初始化，或者 c[] arg 的用途。我只是假设它是全局的或其他东西，但可能你实际上屠杀了一个普通的 matmul 函数，它在每次内部迭代后存储一个单独的 temp 到 c[] 通过取出它。在那种情况下，单独的中间循环迭代 之间的 OoO exec 是 与中型 n 相关。但是您没有显示调度程序/ROB 大小，这不是您可以轻松建模的东西；您需要实际进行基准测试。所以本节可能仅适用于问题我发明的，不是你想问的！）
您的循环似乎在对 matmul 结果的元素求和，但结构仍然像 matmul。即做行 x 列点积，但不是将其存储到 N x N result[...] 矩阵中，您只是对结果求和。
这相当于对两个矩阵之间元素的每个成对乘积求和。由于我们不再需要将单独的行 x 列点积分开，因此可以实现 很多 优化！ （这个求和顺序没有什么特别或理想的；其他顺序会有不同但可能不会更糟的舍入误差。）
例如，您不需要将 b 转置为 Tb，只需使用 b（除非它已经自然转置，在这种情况下没问题）。您的矩阵是正方形的，所以 完全没有关系。
此外，您可以简单地从 a[] 加载一个或几个元素并循环遍历 Tb[]，使用 FMA 运算执行这些乘积，每个 FMA 加载一次，进入 10 或 12 个向量累加器。 （或者当然缓存块循环遍历 Tb 的连续部分，该部分可以在 L1d 缓存中保持热。）
这可能接近 Haswell 的最大 FLOPS 吞吐量，即每个时钟 2x 256 位 FMA = 8（每个 YMM 向量 float 个元素）x 2 FMA/时钟 x 2 FLOP/FMA = 32 FLOP/时钟.