c++ - 不确定如何解释我的并行矩阵乘法代码的一些性能结果

Question

我在 OpenMP 中运行此代码以进行矩阵乘法，并测量了它的结果:

#pragma omp for schedule(static)
for (int j = 0; j < COLUMNS; j++)
    for (int k = 0; k < COLUMNS; k++)
        for (int i = 0; i < ROWS; i++)
            matrix_r[i][j] += matrix_a[i][k] * matrix_b[k][j];

根据我放置 #pragma omp 指令的位置，有不同版本的代码 - 在 j 循环、k 循环或 i 循环之前。此外，对于这些变体中的每一个，我都运行了不同版本的默认静态调度、 block 1 和 10 的静态调度以及相同 block 的动态调度。我还测量了 CodeXL 中的 DC 访问次数、DC 未命中次数、CPU 时钟、失效指令和其他性能指标。以下是 AMD Phenom I X4 945 上大小为 1000x1000 的矩阵的结果:

Results of performance measurements

其中 multiply_matrices_1_dynamic_1 是一个在第一个循环之前带有 #pragma omp 的函数和带有 block 1 的动态调度等。这里有一些我不太了解的东西结果并希望得到帮助:

• 在内部循环之前采用并行化的默认静态版本在 2,512 秒内运行，而顺序版本在 31,683 秒内运行 - 尽管它在 4 核机器上运行，但我认为最大可能的加速将是是 4 倍。这在逻辑上是否可能发生，或者这是某种错误？我该如何解释呢？
  • CodeXL 表示具有静态调度的第三个版本的 DC 访问(和未命中)数量比其他版本低得多。这是为什么？这在很大程度上不是因为所有并行线程都在 b 矩阵的同一个单元格上运行。是吗？
  • 我知道第二个版本是不正确的，因为线程可能在 R 矩阵的同一个单元格上运行，这可能会导致竞争条件。但是，为什么它的性能较低？不正确会以某种方式导致它吗？
  • 我意识到动态调度会导致开销，这就是使用它时代码变慢的原因。此外，对于第 3 个版本(在 i 循环之前使用 pragma)，调度执行了更多次(使用 1000x1000 矩阵执行了十亿次)，因此该算法的性能要低得多。但是，这种调度似乎不会导致第二个版本的速度下降(在第二个循环之前使用 pragma)。这是为什么？

此外，我对 TLB 未命中与高速缓存未命中之间的关系感到困惑。 DTLB具体什么时候使用？我教授的文件说每个 DC 访问都是一个 DTLB 请求，但我不明白它是如何工作的——TLB 未命中的次数通常大于 DC 访问的次数。如何计算 TLB 未命中率？我的教授说这是 TBL 未命中/DC 访问。他还说我可以通过缓存命中率计算时间局部性，通过 TLB 命中率计算空间局部性。这究竟是如何运作的？

Answer 1

Gilles 的想法是正确的，您的代码对缓存不友好，但他的解决方案仍然是 has a similar problem because it does the reduction over k on matrix_b[k][j] .

一个解决方案是计算 matrix_b 的转置，然后你可以在 k 上运行 matrix_bT[j][k]，这是缓存友好的。转置为 O(n^2)) 矩阵乘法为 O(n^3) 因此转置的成本为 1/n。即对于大的 n 它变得可以忽略不计。

但是有一个比使用转置更简单的解决方案。像这样对 j 进行归约:

#pragma omp for schedule(static)
for (int i = 0; i < ROWS; i++ ) {
    for (int k = 0; k < COLUMNS; k++ ) {
        for ( int j = 0; j < COLUMNS; j++ ) {
           matrix_r[i][j] += matrix_a[i][k]*matrix_b[k][j];
        }
    }
}

Gilles 的方法每次迭代需要从内存读取两次，而此解决方案每次迭代需要两次读取和写入内存，但它对缓存更友好，足以弥补写入内存的不足。