竞争条件会降低代码的性能吗？

Question

我运行正在编写以下矩阵乘法代码，我应该测量其性能：

for (int j = 0; j < COLUMNS; j++)
#pragma omp for schedule(dynamic, 10)
    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];

是的，我知道它真的很慢，但这不是重点 - 它纯粹是为了性能测量目的。我运行宁宁 3 个版本的代码取决于我放置 #pragma omp 指令的位置，因此取决于并行化发生的位置。该代码在 Microsoft Visual Studio 2012 的发布模式中为运行，并在 CodeXL 中进行了配置。

我从测量中注意到的一件事是代码片段中的选项（在 k 循环之前并行化）是最慢的，然后是在 j 循环之前带有指令的版本，然后是带有它的版本在 i 循环之前。所提供的版本也是由于竞争条件而计算出错误结果的版本——多个线程同时访问结果矩阵的同一单元格。我理解为什么 i 循环版本是最快的——所有特定线程只处理 i 变量范围的一部分，增加了时间局部性。但是，我不明白是什么导致 k 循环版本最慢 - 它是否与它产生错误结果有关？

Answer 1

当然，竞争条件会降低代码速度。当两个或多个线程访问内存的同一部分（同一缓存行）时，该部分必须一遍又一遍地加载到给定核心的缓存中，因为另一个线程通过写入缓存内容使缓存内容无效。他们争夺共享资源。

当内存中距离太近的两个变量被更多线程写入和读取时，也会导致速度变慢。这被称为 false sharing。你的情况更糟，它们不仅靠得太近，甚至重合了。

Answer 2

你的假设是正确的。但是，如果我们谈论的是性能，而不仅仅是验证您的假设，那么故事就更复杂了。

你的索引顺序是个大问题，multi-threaded或不。鉴于 mat[x][y] 和 mat[x][y+1] 之间的距离是一，而 mat[x][y] 和 mat[x+1][y] 之间的距离是 dim(mat[x]) 您希望 x 是外部索引和 y 内部索引之间的迭代距离最小。给定 __[i][j] += __[i][k] * __[k][j]; 你会发现空间局部性的正确顺序是 i -> k -> j.

无论顺序如何，都有一个值可以保存以备后用。鉴于您的代码段

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];

matrix_b[k][j] 值将从内存中获取 i 次。你可以从

开始

    for (int j = 0; j < COLUMNS; j++)
        for (int k = 0; k < COLUMNS; k++)
            int temp = matrix_b[k][j];
            for (int i = 0; i < ROWS; i++)
                matrix_r[i][j] += matrix_a[i][k] * temp;

但是鉴于你正在写matrix_r[i][j]，优化的最佳访问是matrix_r[i][j]，因为写比读慢

不必要的内存写访问

for (int i = 0; i < ROWS; i++)
    matrix_r[i][j] += matrix_a[i][k] * matrix_b[k][j];

将写入内存 matrix_r[i][j] ROWS 次。使用临时变量会减少对一个的访问。

    for (int i = 0; i < ...; j++)
        for (int j = 0; j < ...; k++)
            int temp = 0;
            for (int k = 0; k < ...; i++)
                temp += matrix_a[i][k] * matrix_b[k][j];
            matrix_r[i][j] = temp;

这将写访问从 n^3 减少到 n^2。

现在您正在使用线程。为了最大限度地提高多线程的效率，您应该将一个线程的内存访问与其他线程隔离开来。一种方法是给每个线程一个列，并完善该列一次。一种简单的方法是对 matrix_b 进行转置，使得
```
matrix_r[i][j] += matrix_a[i][k] * matrix_b[k][j]; becomes 
matrix_r[i][j] += matrix_a[i][k] * matrix_b_trans[j][k];
```

使得 k 上的最内层循环始终处理相应于 matrix_a 和 matrix_b_trans

的连续内存

    for (int i = 0; i < ROWS; j++)
        for (int j = 0; j < COLS; k++)
            int temp = 0;
            for (int k = 0; k < SAMEDIM; i++)
                temp += matrix_a[i][k] * matrix_b_trans[j][k];
            matrix_r[i][j] = temp;

竞争条件会降低代码的性能吗？

Can race conditions lower the code's performance?

c++

parallel-processing

performance

multithreading

openmp