我写了这个简单的程序，可以乘以矩阵。 我可以指定如何 许多操作系统线程用于使用环境变量运行它OMP_NUM_THREADS. 当线程计数得到时，它会减慢很多 比我的 CPU 的物理线程还大。
这是程序。
static double a[DIMENSION][DIMENSION], b[DIMENSION][DIMENSION],
c[DIMENSION][DIMENSION];
#pragma omp parallel for schedule(static)
for (unsigned i = 0; i < DIMENSION; i++)
for (unsigned j = 0; j < DIMENSION; j++)
for (unsigned k = 0; k < DIMENSION; k++)
c[i][k] += a[i][j] * b[j][k];
我的 CPU 是 i7-8750H。 它有 12 个线程。 当矩阵很大时 足够了，该程序在大约 11 个线程上最快。 它是 4 倍 线程数达到 17 时速度较慢。 然后运行时间停留在 和我增加线程数一样。
这是结果。 顶行是DIMENSION. 左列是 线程计数。 时间以秒为单位。 带有*的列是 用-fno-loop-unroll-and-jam编译。
1024 2048 4096 4096* 8192
1 0.2473 3.39 33.80 35.94 272.39
2 0.1253 2.22 18.35 18.88 141.23
3 0.0891 1.50 12.64 13.41 100.31
4 0.0733 1.13 10.34 10.70 82.73
5 0.0641 0.95 8.20 8.90 62.57
6 0.0581 0.81 6.97 8.05 53.73
7 0.0497 0.70 6.11 7.03 95.39
8 0.0426 0.63 5.28 6.79 81.27
9 0.0390 0.56 4.67 6.10 77.27
10 0.0368 0.52 4.49 5.13 55.49
11 0.0389 0.48 4.40 4.70 60.63
12 0.0406 0.49 6.25 5.94 68.75
13 0.0504 0.63 6.81 8.06 114.53
14 0.0521 0.63 9.17 10.89 170.46
15 0.0505 0.68 11.46 14.08 230.30
16 0.0488 0.70 13.03 20.06 241.15
17 0.0469 0.75 20.67 20.97 245.84
18 0.0462 0.79 21.82 22.86 247.29
19 0.0465 0.68 24.04 22.91 249.92
20 0.0467 0.74 23.65 23.34 247.39
21 0.0458 1.01 22.93 24.93 248.62
22 0.0453 0.80 23.11 25.71 251.22
23 0.0451 1.16 20.24 25.35 255.27
24 0.0443 1.16 25.58 26.32 253.47
25 0.0463 1.05 26.04 25.74 255.05
26 0.0470 1.31 27.76 26.87 253.86
27 0.0461 1.52 28.69 26.74 256.55
28 0.0454 1.15 28.47 26.75 256.23
29 0.0456 1.27 27.05 26.52 256.95
30 0.0452 1.46 28.86 26.45 258.95
循环中的代码在 gcc 9.3.1 上编译为此-O3 -march=native -fopenmp.rax从 0 开始，增加 64 每次迭代。rdx指向c[i].rsi指向b[j].rdi指向b[j+1].
vmovapd (%rsi,%rax), %ymm1
vmovapd 32(%rsi,%rax), %ymm0
vfmadd213pd (%rdx,%rax), %ymm3, %ymm1
vfmadd213pd 32(%rdx,%rax), %ymm3, %ymm0
vfmadd231pd (%rdi,%rax), %ymm2, %ymm1
vfmadd231pd 32(%rdi,%rax), %ymm2, %ymm0
vmovapd %ymm1, (%rdx,%rax)
vmovapd %ymm0, 32(%rdx,%rax)
我想知道为什么线程计数时运行时间增加这么多 增加。
我的估计是，当DIMENSION是4096时，情况不应该是这种情况。
我之前的想法我记得编译器j在 一时间。j循环的每次迭代都需要行c[i]和b[j]。 它们总共为 64KB。 我的 CPU 有一个 32KB L1 数据缓存和一个 256KB L2 每 2 个线程缓存。 两个硬件线程正在工作的四行 不适合 L1，但适合 L2。 因此，当j前进时，c[i]从 L2 读取。 当程序在 24 个操作系统线程上运行时，数量 非自愿上下文切换约为 29371。 每个线程都得到 在有机会完成j的一次迭代之前中断 圈。 由于 L2 缓存中可以容纳 8 个矩阵行，因此其他软件 线程的 2 行在恢复时可能仍在 L2 中。 所以 执行时间应该与 12 线程情况没有太大区别。 然而，测量表明它的速度是它的 4 倍。
现在我已经意识到一次完成 2 个j循环。 这样每个j迭代在 96KB 内存上工作。 所以其中 4 个不适合 256KB 二级缓存。 为了验证这是否减慢了程序的速度，我 用-fno-loop-unroll-and-jam编译了该程序。 我得到了
vmovapd ymm0, YMMWORD PTR [rcx+rax]
vfmadd213pd ymm0, ymm1, YMMWORD PTR [rdx+rax]
vmovapd YMMWORD PTR [rdx+rax], ymm0
结果在表中。 它们就像在 2 行完成时一样 时间。 这让我更加疑惑。 当DIMENSION为 4096 时，4 当每个线程在 1 上工作时，软件线程的 8 行适合 L2 缓存 一次行，但当每个线程时 12 行不适合 L2 缓存 一次处理 2 行。 为什么运行时间相似？
我想也许是因为 CPU 在运行时预热 线程，必须放慢速度。 我多次运行测试，都在 增加线程数和减少线程数的顺序。 他们 产生类似的结果。dmesg不包含任何与 热或时钟。
我尝试将 4096 列分别更改为 4104 列并设置OMP_PROC_BIND=true OMP_PLACES=cores，结果相似。
此问题似乎来自CPU 缓存(由于内存局部性错误)或操作系统调度程序(由于线程数超过硬件可以同时执行的线程数)。
我无法在我的 i5-9600KF 处理器(6 个内核和 6 个线程)和大小为 4096x4096 的矩阵上完全重现相同的效果。但是，也会发生类似的效果。
以下是性能结果(GCC 9.3 在 Linux 5.6 上使用-O3 -march=native -fopenmp)：
#threads | time (in seconds)
----------------------------
1 | 16.726885
2 | 9.062372
3 | 6.397651
4 | 5.494580
5 | 4.054391
6 | 5.724844 <-- maximum number of hardware threads
7 | 6.113844
8 | 7.351382
9 | 8.992128
10 | 10.789389
11 | 10.993626
12 | 11.099117
24 | 11.283873
48 | 11.412288
我们可以看到，计算时间在 5 到 12 个内核之间开始显着增长。
此问题是由于从RAM获取的数据更多。事实上，161.6 Gio 是用 6 个线程从内存加载的，而 424.7 Gio 是用 12 个线程加载的！在这两种情况下，都会将 3.3 Gio 写入 RAM。因为我的内存吞吐量大约是 40 Gio/s，所以 RAM 访问占 12 个线程的总执行时间的 96% 以上！
如果我们深入挖掘，我们可以看到，无论使用的线程数量如何，L1 缓存引用和 L1 缓存未命中的数量都是相同的。同时，还有更多的 L3 缓存未命中(以及更多引用)。以下是 L3 缓存统计信息：
With 6 threads: 4.4 G loads
1.1 G load-misses (25% of all LL-cache hits)
With 12 threads: 6.1 G loads
4.5 G load-misses (74% of all LL-cache hits)
这意味着内存访问的位置显然随着线程的增加而变差。我想这是因为编译器不够聪明，无法进行可以降低 RAM 压力的高级基于缓存的优化(尤其是在线程数很高的情况下)。您必须自己进行平铺以改善内存局部性。你可以在这里找到一个很好的指南。
最后，请注意，使用硬件可以同时执行的更多线程通常效率不高。一个问题是操作系统调度程序经常错误地将线程放置在核心并频繁移动它们。解决此问题的常用方法是使用OMP_PROC_BIND=TRUE将软件线程绑定到硬件线程并设置OMP_PLACES环境变量。另一个问题是线程是使用共享资源(例如缓存)的抢占式多任务执行的。
PS：请注意，BLAS库(例如。OpenBLAS、BLIS、Intel MKL 等)比此代码优化得多，因为它们已经包含智能优化，包括目标硬件的手动矢量化、循环展开、多线程、平铺和需要时的快速矩阵转置。对于 4096x4096 矩阵，它们的速度大约快 10 倍。