我在这个答案的副本上发布了这个答案的改进版本:最终分配的 C 循环优化帮助 https://stackoverflow.com/questions/32000917/c-loop-optimization-help-for-final-assignment。最初只是转发,但后来我做了一些修改来回答该问题的差异。我忘记了有什么不同,但你可能应该读一下那个。也许我应该删除这个。
另请参阅中的其他优化指南x86 /questions/tagged/x86标签维基。
首先,它是一个非常糟糕的示例,因为它没有任何东西可以阻止智能编译器优化整个事情。它甚至不打印总和。甚至gcc -O1
(代替-O3
)丢弃了一些循环。
通常,您会将代码放入函数中,然后在循环中调用它main()
在另一个文件中。并单独编译它们,没有整个程序的跨文件优化,因此编译器无法根据您调用它的编译时常量进行优化。重复循环如此紧密地包裹在数组上的实际循环周围,对 gcc 的优化器造成了严重破坏(见下文)。
Also:
gcc -Wall -O3 -march=native fast-loop-cs201.c -o fl
fast-loop-cs201.c: In function ‘main’:
fast-loop-cs201.c:17:14: warning: ‘help’ is used uninitialized in this function [-Wuninitialized]
long int help;
我不得不同意 EOF 对你教授的贬低言论。给出没有优化的代码,并且带有未初始化的变量,这完全是无稽之谈。
有些人在评论中说“编译器并不重要”,您应该针对 CPU 微体系结构优化 C 源代码,而不是让编译器来做。这很糟糕:为了获得良好的性能,您必须了解编译器可以做什么和不能做什么。有些优化是“脆弱的”,对源代码进行看似无害的小更改将阻止编译器执行某些操作。
我想你的教授提到了一些关于性能的事情。有很多不同的东西可以在这里发挥作用,其中许多我认为在二年级的计算机科学课程中没有被提及。
除了使用 openmp 进行多线程处理之外,还有使用 SIMD 进行矢量化。还有针对现代流水线 CPU 的优化:具体来说,避免拥有一个长依赖链。
进一步的重要阅读:
-
阿格纳·福格的指南 http://agner.org/optimize/用于针对 x86 优化 C 和 asm。其中一些适用于所有 CPU。
- 每个程序员都应该了解的内存知识 http://www.akkadia.org/drepper/cpumemory.pdf
您的编译器手册也很重要,尤其是。对于浮点代码。浮点数的精度有限,not联想的。最后总和does取决于您进行加法的顺序。但是,通常舍入误差的差异很小。因此,如果您使用,编译器可以通过重新排序来获得很大的加速-ffast-math
允许它。这可能是您的 unroll-by-10 所允许的。
不只是展开,保留多个累加器(仅在最后相加)可以使浮点执行单元保持饱和,因为 FP 指令具有延迟!=吞吐量。如果您需要上一个操作的结果在下一个操作开始之前完成,那么您会受到延迟的限制。对于 FP 添加,即每 3 个周期一次。在 Intel Sandybridge、IvB、Haswell 和 Broadwell 中,FP add 的吞吐量为每周期 1 个。因此,您需要保留至少 3 个可以同时运行的独立操作,以使机器饱和。, it's 每周期 2 个,延迟为 4 个时钟 http://users.atw.hu/instlatx64/GenuineIntel00506E3_Skylake_InstLatX64.txt。 (对于 Skylake 来说,好的一面是,FMA 可将延迟降低至 4 个周期。)
在这种情况下,还有一些基本的东西,比如将事情从循环中拉出来,例如help += ARRAY_SIZE
.
编译器选项
我从原来的内循环开始,只是help += ARRAY_SIZE
拉出来,并添加一个printf
最后,所以 gcc 不会优化所有内容。让我们尝试一些编译器选项,看看我们可以使用 gcc 4.9.2 实现什么(在我的i5 2500k 桑迪布里奇 http://ark.intel.com/products/52210/Intel-Core-i5-2500K-Processor-6M-Cache-up-to-3_70-GHz。 3.8GHz 最大睿频(轻微超频),持续 3.3GHz(与这个简短的基准测试无关):
-
gcc -O0 fast-loop-cs201.c -o fl
:16.43s 的性能完全是个笑话。每次操作后变量都会存储到内存中,并在下一次操作之前重新加载。这是一个瓶颈,并且会增加很多延迟。更不用说失去实际的优化了。定时/调谐代码-O0
没有用。
-
-O1
: 4.87s
-
-O2
: 4.89s
-
-O3
:2.453s(使用SSE一次执行2个。我当然使用64位系统,所以硬件支持-msse2
是基线。)
-
-O3 -ffast-math -funroll-loops
: 2.439s
-
-O3 -march=sandybridge -ffast-math -funroll-loops
:1.275s(使用 AVX 一次执行 4 个操作。)
-
-Ofast ...
: 没有收获
-
-O3 -ftree-parallelize-loops=4 -march=sandybridge -ffast-math -funroll-loops
:0m2.375s真实,0m8.500s用户。看起来锁定开销杀死了它。它总共只生成 4 个线程,但内部循环太短,无法获胜(因为它每次都会收集总和,而不是为一个线程提供外部循环迭代的前 1/4)。
-Ofast -fprofile-generate -march=sandybridge -ffast-math
,运行它,然后
-Ofast -fprofile-use -march=sandybridge -ffast-math
: 1.275s
clang-3.5 -Ofast -march=native -ffast-math
:1.070秒。 (clang不支持-march=sandybridge
).
gcc -O3
以一种搞笑的方式进行向量化:内部循环并行执行外部循环的 2(或 4)次迭代,方法是将一个数组元素广播到 xmm(或 ymm)寄存器的所有元素,并执行addpd
关于这一点。所以它看到相同的值被重复添加,但即使-ffast-math
不让 gcc 把它变成乘法。或者切换循环。
clang-3.5 的矢量化效果更好:它矢量化内部循环,而不是外部循环,因此不需要广播。它甚至使用 4 个向量寄存器作为 4 个独立的累加器。然而,它并不假设calloc
返回对齐的内存,并且出于某种原因,它认为最好的选择是一对 128b 加载。
vmovupd -0x60(%rbx,%rcx,8),%xmm4`
vinsertf128 $0x1,-0x50(%rbx,%rcx,8),%ymm4,%ymm4
其实是slower当我告诉它数组已对齐时。 (用一个愚蠢的黑客,比如array = (double*)((ptrdiff_t)array & ~31);
它实际上生成一条指令来屏蔽低 5 位,因为 clang-3.5 不支持 gcc__builtin_assume_aligned
.) 我认为 4x 的紧密循环方式vaddpd mem, %ymmX,%ymmX
对齐看跌期权cmp $0x271c,%rcx
跨越 32B 边界,因此它不能与jne
。不过,uop 吞吐量不应该成为问题,因为根据该代码,每个周期仅获得 0.65insns(以及每个周期 0.93 uops)perf
.
啊,我用调试器检查过,然后calloc
仅返回 16B 对齐的指针。因此,一半的 32B 内存访问会跨越缓存行,从而导致速度大幅下降。我猜is在 Sandybridge 上,当您的指针是 16B 对齐但不是 32B 对齐时,执行两个单独的 16B 加载会稍微快一些。编译器在这里做出了一个很好的选择。
源级别变化
正如我们从 clang 击败 gcc 中看到的,多个累加器非常出色。最明显的方法是:
for (j = 0; j < ARRAY_SIZE; j+=4) { // unroll 4 times
sum0 += array[j];
sum1 += array[j+1];
sum2 += array[j+2];
sum3 += array[j+3];
}
然后直到外循环结束后才将 4 个累加器合为一个。
您的源更改为
sum += j[0]+j[1]+j[2]+j[3]+j[4]+j[5]+j[6]+j[7]+j[8]+j[9];
由于乱序执行,实际上具有类似的效果。每组 10 个都是一个单独的依赖链。操作顺序规则表示j
值首先相加,然后添加到sum
。因此,循环携带的依赖链仍然只是一个 FP add 的延迟,并且每组 10 个都有大量独立的工作。每个组都是一个独立的 9 个 add 依赖链,并且只需要很少的指令即可完成-命令执行硬件以查看下一条链的开始,并找到并行性以保持那些中等延迟、高吞吐量的 FP 执行单元。
With -O0
,正如您愚蠢的作业显然需要的那样,值在每个语句末尾存储到 RAM 中。 (从技术上讲,在每个“序列点”,如 C 标准所称。)编写更长的表达式而不更新任何变量,甚至是临时变量,将使-O0
运行得更快,但这不是一个有用的优化。不要把时间浪费在那些改变上only帮助-O0
,特别是。不以牺牲可读性为代价。
使用 4 个累加器,并且直到外循环结束时才将它们加在一起,从而使 clang 的自动矢量化器失效。它的运行时间仍然仅为 1.66 秒(而 gcc 的非矢量化则为 4.89 秒)-O2
与一个累加器)。甚至gcc -O2
没有-ffast-math
此源更改也需要 1.66 秒。请注意,已知 ARRAY_SIZE 是 4 的倍数,因此我没有包含任何清理代码来处理最后最多 3 个元素(或者避免读取超出数组末尾的内容,这将按照现在的方式发生) 。执行此操作时,很容易出错并读到数组末尾。
另一方面,gcc 确实对此进行了矢量化,但它也将内部循环悲观(未优化)为单个依赖链。我认为它再次对外循环进行多次迭代。
使用 gcc 的平台无关向量扩展,我编写了一个可以编译成明显最佳代码的版本:
// compile with gcc -g -Wall -std=gnu11 -Ofast -fno-tree-vectorize -march=native fast-loop-cs201.vec.c -o fl3-vec
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include <string.h>
// You are only allowed to make changes to this code as specified by the comments in it.
// The code you submit must have these two values.
#define N_TIMES 600000
#define ARRAY_SIZE 10000
int main(void)
{
double *array = calloc(ARRAY_SIZE, sizeof(double));
double sum = 0;
int i;
// You can add variables between this comment ...
long int help = 0;
typedef double v4df __attribute__ ((vector_size (8*4)));
v4df sum0={0}, sum1={0}, sum2={0}, sum3={0};
const size_t array_bytes = ARRAY_SIZE*sizeof(double);
double *aligned_array = NULL;
// this more-than-declaration could go in an if(i == 0) block for strict compliance with the rules
if ( posix_memalign((void**)&aligned_array, 32, array_bytes) ) {
exit (1);
}
memcpy(aligned_array, array, array_bytes); // In this one case: faster to align once and have no extra overhead for N_TIMES through the loop
// ... and this one.
// Please change 'your name' to your actual name.
printf("CS201 - Asgmt 4 - I. Forgot\n");
for (i = 0; i < N_TIMES; i++) {
// You can change anything between this comment ...
/*
#if defined(__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__) >= 407 // GCC 4.7 or later.
array = __builtin_assume_aligned(array, 32);
#else
// force-align for other compilers. This loop-invariant will be done outside the loop.
array = (double*) ((ptrdiff_t)array & ~31);
#endif
*/
assert ( ARRAY_SIZE / (4*4) == (ARRAY_SIZE+15) / (4*4) ); // We don't have a cleanup loop to handle where the array size isn't a multiple of 16
// incrementing pointers can be more efficient than indexing arrays
// esp. on recent Intel where micro-fusion only works with one-register addressing modes
// of course, the compiler can always generate pointer-incrementing asm from array-indexing source
const double *start = aligned_array;
while ( (ptrdiff_t)start & 31 ) {
// annoying loops like this are the reason people use aligned buffers
sum += *start++; // scalar until we reach 32B alignment
// in practice, this loop doesn't run, because we copy into an aligned buffer
// This will also require a cleanup loop, and break our multiple-of-16 doubles assumption.
}
const v4df *end = (v4df *)(aligned_array+ARRAY_SIZE);
for (const v4df *p = (v4df *)start ; p+3 < end; p+=4) {
sum0 += p[0]; // p+=4 increments the pointer by 4 * 4 * 8 bytes
sum1 += p[1]; // make sure you keep track of what you're incrementing
sum2 += p[2];
sum3 += p[3];
}
// the compiler might be smart enough to pull this out of the inner loop
// in fact, gcc turns this into a 64bit movabs outside of both loops :P
help+= ARRAY_SIZE;
// ... and this one. But your inner loop must do the same
// number of additions as this one does.
/* You could argue legalese and say that
if (i == 0) {
for (j ...)
sum += array[j];
sum *= N_TIMES;
}
* still does as many adds in its *INNER LOOP*, but it just doesn't run it as often
*/
}
// You can add some final code between this comment ...
sum0 = (sum0 + sum1) + (sum2 + sum3);
sum += sum0[0] + sum0[1] + sum0[2] + sum0[3];
printf("sum = %g; help=%ld\n", sum, help); // defeat the compiler.
free (aligned_array);
free (array); // not strictly necessary, because this is the end of main(). Leaving it out for this special case is a bad example for a CS class, though.
// ... and this one.
return 0;
}
内循环编译为:
4007c0: c5 e5 58 19 vaddpd (%rcx),%ymm3,%ymm3
4007c4: 48 83 e9 80 sub $0xffffffffffffff80,%rcx # subtract -128, because -128 fits in imm8 instead of requiring an imm32 to encode add $128, %rcx
4007c8: c5 f5 58 49 a0 vaddpd -0x60(%rcx),%ymm1,%ymm1 # one-register addressing mode can micro-fuse
4007cd: c5 ed 58 51 c0 vaddpd -0x40(%rcx),%ymm2,%ymm2
4007d2: c5 fd 58 41 e0 vaddpd -0x20(%rcx),%ymm0,%ymm0
4007d7: 4c 39 c1 cmp %r8,%rcx # compare with end with p
4007da: 75 e4 jne 4007c0 <main+0xb0>
(欲了解更多,请参阅 godbolt 上的在线编译器输出 https://gcc.godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAKxAEZSBnVAV2OUxAHIB6bgajQBbAA54ANpj4B3Qgj7BkyPgFpgKgOoBDMWJUMC6AKQBmACLAAds1q0VAeQBmm/SocXUygsUyZlAN0xkImI8AC9JZUFNNgQTUwtNAjwAvid9ZTFUVGFlZAYAJgAGWgA6AOQSpWVUVLFjf0DDQoBBJtb84zwLZDFmLD4TAGF9fFQS2ONsNsMOrp6%2BySGRsTwAI3GTKZaZzu7e/qWDLAcNyenZvYWB40HnBkxiAlOt9t35g5v9EItgZ%2BmW3h8ACaLD40UkqAsYgAnmCdKgpJh0HwiHwogBrSTIBCaH6YBgomoEBB4AlofrOPgMYSBPAOPBIvirWHErGoQSCTAWAgErp8Qglf7NQEAFQQbP60NBDGYq0EhDRzBcOJSrPuKKkNT82mY%2BMF2w6xy6kgAcgB9EUASQAstgAMp8R2OgBshTdbvOxiNFkkzQASn7mkCzXbLQAtbBO2juwpCroENGaLoQPyoPDoACU0wA7AAhNpOvjoFirCSOgBU0WImlhcT4EGLsok5YzyG0mWQEH9geDoYjpCpYUwqAcDZLEgzWeM%2BZahcbpckVOYgmupj4senBad8cL/JMM9as6dgJBzAEuLB6GR2pCmgXBNWmAIiK5KJJZPZnO5fBKv63jsyH5%2BW/cUxGEVd133IVCwIaEaWOItx0kPwABZ0AcPgzTNRIvDWZgCEwLD6xTQJgjNBgh3rAAOcsUMnKcD0LVD0KXQQN1MQw81jbNTAHGVBFoOJONzbjeNY/IhK4zixP44xJJE6SoO2I9HTQCwXAo8IzQTKsazNZkCIJOtuyDENw2wctNOHUd5wnJTmjnJC%2BErFZLCRbDiGrWszD4E0AFUABkAvs/8%2BEBYlSTREhfGJXFlCwHpokSPBIQEFgxGRYAaj5C86QgPBVzrQoMyZDt0VSEgqVwoI0pEFZcXYaRZDfSRiGYCQGFCul6z4YRUAogAPM1OSiVyLCgVN03LFsZmdbQ8Dc9APK8gdjHyAddOhfToUMkqSuE/4AE5MAGhUIFoBjQsUlS0UwQRkGEaEIHmxblprDbPPesFPq2gz8QYx1AUtCw30iyEsWcDhUmcAjiEJOEFpByFGtxZEVUkdw%2BBOrxND4VAAmIcVNGRBxKvNK1bQdYliBYYA5FZPhMmyaDj34X8SjBCxkQiglwf1Q8HNZvgAAUJEhgQcTxPgwE4KVWD4BJORl%2BG5bhzQgmYbQFc0Tl%2BcLYRvgIUcZnyQY7SKWxlD4ZoGGAQQExQlQ%2BEtDmADESCyghDAAVkGCwTcu5TBcdUm4fyiCN1zflrkGXyLRte19z3fJ8xT/a8xZ3cwv4U9zxB7FcWASRcR2kkgMfZ8fBBnnaq/BN2babhy09brvSRCAsIAcX8wYsP2/JnVm%2Bsu57ojyz4aNCgGFPMLNbu/N761LRNOw/T764ph8lDCmzbO%2BE7wZY5Qkpd8qsREgefmmkOzaIKw1ZmHEJILGwhh%2BMIl6fXQZ6ftW/JA9eJgMQ9wjqAlDuwZQn8Kpw1QKyOGQhRASGIAwDmfAxSRSZjkLoN48C4gTDIHQTJJDFh9HjfCFF%2BgM0wVfQoN8foQTHE2TALZiLCC8PgBwDhtIZlvkPAAfsYC6IUOhcg4W0cs3AhTXzuA8BMEBrYBlMn2SM/AIAoVovtMwdYuyKN7OZGYuZaDexKqo9RdE%2BAAz3uoYhkIZYJnRmCAQYsrDgUwfDSW6AyxSHFN4Fq30vKDnCPyBgFg7GOMEO1JIwgywjgnoPIOoD%2BBzG8HXLoag%2BrxgeGSC8j4oq%2BMwJwvAyAGTfliiDLoWBTpAU2p1ZSh1AT4mEBzVK3h2DfmBgRXQ3iHiSHlMgGmygHBKhSkjKEsJNTEHRASGQxI8Y%2BmUN4YApJYaXnQN4N%2BaSopYFqYeep/BYloFYPcAcDMEHiAeHnOEUgawEiLj6asBFeppm5A8ZQyS7pcmfmoZwK4HA0xXJtN5XMTqbKYKwdgR01IuFspISyBBogJjrJ/dym0Qp1O8ecnqEA2HEA4VwggGZ9AIuns6PggiLEDAznUwsgJcTuGhJszBBIViYlBgScEfjvDOFSjSbIZYlTFzGoyB%2BnCslHULPxae%2BYfJwoRQY%2BVm5aE0v4AwNs584bMG5OIaQrVMDqzkGtKOn867iqFnyA26skjsBOe%2BRmWRwLFnxKEzgCY2oWAHI%2BNsAqdVpUesBVEF5kXIhFQ4B4prAb8HQdM8QuhtBMD4N4AAjo/XxuMeh6pcXa7IG0uZMi5eVFgcMIliCiRIaoDhlC0FJTC9lb9lxsJGTQw610BbXyhQmZiGFyyiIYZ25yGZnpCqWqilOJk9ERgAVnEOlUIDtr4H28s4FtELsJfCx41wo7CAMcYGOWMuZJy3SnOI5iDrUqdPxKeCq1xbu9gpb2HFpyOmvoCQ90rTCO3eXXAkDMMkvLhsyPgjtx5Ab4FRJkO18ThtYrYK9vUfaGJ9g%2BqOWdAQYkkDKXxcs%2BCYkwOBHGyAC0YW8YkPgcsZa%2BM/Z8tJUH%2BL5ClXWG9uYJL3rRYdCVy4d2wcY3JFjirdktsSX4s5SC0QLQQAmXJDAojrq5LTemNRhDtV0DXFgCZYkMy6PcrNW66mAj5E4IIA4FBKAIKwdSbL/U1Fxs6FCqwFSCHxneXm5D0wQgwqsWBcgmV8BAMLI6oFX3GV0WZCMaLg67kBOzTm3NbV8z4LmfCpHC3AS024iJ0KiTiipDrTAoVlUK2XI%2BGBGFib4CSJCWtFnwaIT1FI2hTdgSgkORlb6wBdSM0wMAbQ%2BJi65oYDWN8iRxXdXDkJHyxVKUHmvruUO9YqA/l/FmM9U7JWwdRbeqgiH7JTqzpK5uPlyYJztKxylHFqXj30DGmrlWogWFhKV3k5SeTOWXiabAfo%2BABTsHYYW5YPWJYVFQJUCZHUhLCW6/kOleYOAIv7c7kiboCZuieJrgarxUnZJIekCRdDkkkBXF81dbVCDrgtvW57lyXp8hAC9UroP9yjjT5cdGDGsWMJOinK5YMXvg7Ge9dOee3sEvz1ngumOIYF5T%2BDPGkOhQNvGY2%2BR8irZ8jMb2wAk4BaEvkb2GUfZ%2BxNnxZcA4AuWMBMcPVCZTnskQZfTOqRvCSEHYjFFP0Och0d/WTaZv%2BDuATF8IpBAYQK0CPifrxBoQesCJob1NdIoMx7bEqIyYMyoICnqvwmyFSqegRZ6ktItZtnVJFXGqxiZYwGjraJWPKq4zNk4u4Nq5Pk4jWT6LVWfQ0PC94UzxAQaRxzGd5onAMykDEFwb2nBSAWC4IUKfqAuCDHlTPMFbBFgdFoFPggs%2BR%2Bj/RCAb2hQx9cBQlPmfnA5%2BkAX5wKfDAQBH%2B3xfkfpA4CwCQMJh45BKAf%2BICAYA3sihSB6QS0slKAsIzRChKBR9Vgd9SASdPk7AxlYD8BWkkgAg78n9SAqBk0HhoQuBjASh8gShN8x8uRgBiQ6BSADZMA/A7BVgqBSIwCsJICacwhQgJAjFChjAUIUJaAqJDoqJjAqJnRKBNU250BKAJA7kJDIBvZSAj9OBN96JR8JAfgKD6BqDaD6DGCO5mDKAqAABFXUCPNaaMKiPg/IFCZ0Q6fIYQ4wQoKifIGw2gSgfAakc%2BPAm/UfTSdgzATg7g3g/gwQ4Q0Q4FbHJESQzrUReAOQhQpQ%2BiUgtQpAC6ScK/BtCrLgZQRwGGVwdwTwR3BoIIEgSiSIaIbEOIBINAiIBwAmDze4SBKTW/QtdgOgFQifM/WA6/AaYQ5QGzeQRQPgb2Qg%2BsXAQgSqHYegPgQYG3c5OGCYjMLfHfVI/fQ/Y/TgU/afTorgW/e/UgR/OfVI8fTgfIDozA6/RYp/VIgmCiSEEAFCIAA%3D。注意我必须转换返回值calloc
,因为 godbolt 使用 C++ 编译器,而不是 C 编译器。内循环来自.L3
to jne .L3
. See https://stackoverflow.com/tags/x86/info https://stackoverflow.com/tags/x86/info用于 x86 asm 链接。也可以看看微融合和寻址模式 https://stackoverflow.com/questions/26046634/micro-fusion-and-addressing-modes,因为 Sandybridge 的这一更改尚未纳入 Agner Fog 的手册中。)。
表现:
$ perf stat -e task-clock,cycles,instructions,r1b1,r10e,stalled-cycles-frontend,stalled-cycles-backend,L1-dcache-load-misses,cache-misses ./fl3-vec
CS201 - Asgmt 4 - I. Forgot
sum = 0; help=6000000000
Performance counter stats for './fl3-vec':
1086.571078 task-clock (msec) # 1.000 CPUs utilized
4,072,679,849 cycles # 3.748 GHz
2,629,419,883 instructions # 0.65 insns per cycle
# 1.27 stalled cycles per insn
4,028,715,968 r1b1 # 3707.733 M/sec # unfused uops
2,257,875,023 r10e # 2077.982 M/sec # fused uops. lower than insns because of macro-fusion
3,328,275,626 stalled-cycles-frontend # 81.72% frontend cycles idle
1,648,011,059 stalled-cycles-backend # 40.47% backend cycles idle
751,736,741 L1-dcache-load-misses # 691.843 M/sec
18,772 cache-misses # 0.017 M/sec
1.086925466 seconds time elapsed
我仍然不知道为什么每个周期的指令数如此之低。内部循环使用 4 个独立的累加器,我用 gdb 检查了指针是否对齐。所以缓存库冲突不应该是问题。 Sandybridge L2 缓存可以维持每个周期 1 个 32B 传输,这应该跟上每个周期 1 个 32B FP 向量加法。
从L1加载32B负载需要2个周期(直到Haswell,Intel才将32B加载变成单周期操作)。但是,有 2 个加载端口,因此每个周期的持续吞吐量为 32B(我们尚未达到)。
也许负载需要在使用之前进行管道传输,以最大程度地减少负载停止时 ROB(重新排序缓冲区)被填满的情况?但性能计数器表明 L1 缓存命中率相当高,因此从 L2 到 L1 的硬件预取似乎正在完成其工作。
每个周期 0.65 条指令仅使向量 FP 加法器饱和的一半左右。这令人沮丧。甚至IACA https://software.intel.com/en-us/articles/intel-architecture-code-analyzer表示循环每次迭代应运行 4 个周期。 (即使加载端口和端口 1(FP 加法器所在的位置)饱和):/
更新:我想 L2 延迟毕竟是问题所在。将 ARRAY_SIZE 减少到 1008(16 的倍数),并将 N_TIMES 增加 10 倍,使运行时间减少到 0.5 秒。即每个周期 1.68 个insns。 (内部循环总共有 7 条指令用于 4 个 FP 加法,因此我们最终使向量 FP 加法单元和加载端口饱和。)不知道为什么硬件预取器在一次停顿后无法领先,然后保持领先。软件预取可能有帮助吗?也许以某种方式避免让硬件预取器运行经过数组,而是再次开始预取数组的开头。 (循环平铺是一个更好的解决方案,请参见下文。)
Intel CPU 的 L1 数据和 L1 指令缓存各只有 32k。我认为你的阵列勉强适合 AMD CPU 上的 L1。
Gcc 通过将相同的值广播到并行添加中来进行矢量化的尝试似乎并不那么疯狂。如果它成功做到了这一点(使用多个累加器来隐藏延迟),那么它就可以仅用一半的内存带宽就使矢量 FP 加法器饱和。事实上,这几乎是一次洗礼,可能是因为广播的开销。
而且,这也很愚蠢。这N_TIMES
只是一个重复的工作。我们实际上不想针对多次执行相同的工作进行优化。除非我们想在这样愚蠢的任务中获胜。执行此操作的源级方法是增加i
在我们允许修改的部分代码中:
for (...) {
sum += a[j] + a[j] + a[j] + a[j];
}
i += 3; // The inner loop does 4 total iterations of the outer loop
更现实的是,要处理这个问题,您可以互换循环(循环数组一次,将每个值添加 N_TIMES 次)。我想我已经读到英特尔的编译器有时会为你做这件事。
更通用的技术称为缓存阻塞或循环平铺。这个想法是在适合缓存的小块中处理输入数据。根据您的算法,可以在一个块上执行各个阶段的操作,然后对下一个块重复,而不是让每个阶段循环整个输入。一如既往,一旦你知道了一个技巧的正确名称(并且它确实存在),你就可以在谷歌上搜索大量信息。
你可以通过规则律师的方式将一个交换循环放入一个if (i == 0)
阻止您可以修改的代码部分。它仍然会执行相同数量的添加,但以更缓存优化的顺序进行。