为什么并行版本更慢？

Question

我想在矩阵上应用特定的过滤器。 (从[0][0]个顺序到结束)

A[i][j] = 0.2 * (A[i][j] + A[i+1][j] + A[i-1][j] + A [i][j+1] + A[i][j-1])

如果 [i],[j] 是例如 [0][0]（矩阵中的第一个值），我使用零作为左侧和上侧的值。

我想了解为什么我的代码的并行版本比顺序版本慢。

当我用多线程计算时，我使用的是沿对角线有独立工作的事实。我故意将矩阵扩展两行和两列（用零填充）以简化过滤器的计算。

我还尝试了各种尺寸的矩阵（最大 7000x7000）。

我的问题： http://15418.courses.cs.cmu.edu/fall2017/lecture/progbasics/slide_032

后续版本：

for (int i = 1; i < r-1; i++) {
    for (int j = 1; j < c-1; j++) {
        arr[i][j] = 0.2f * (arr[i][j] + arr[i][j - 1] + arr[i - 1][j] + arr[i][j + 1] + arr[i + 1][j]); 
        }
    }

并行版本：

int n = r - 2;  
for (int slice = 0; slice < 2 * n - 1; ++slice) {     //along the diagonals
        int z = (slice < n) ? 0 : slice - n + 1;
        #pragma omp parallel for schedule(static) //spawns threads 
        for (int j = z; j <= slice - z; ++j) {
            pl_arr[j + 1][slice - j + 1] = 0.2f * (pl_arr[j + 1][slice - j + 1] + pl_arr[j + 1][slice - j] + pl_arr[j][slice - j + 1] + pl_arr[j + 1][slice - j + 1 + 1] + pl_arr[j + 1 + 1][slice - j + 1]);
        }
}

其余代码：

int r = 7000, c = 7000;

r = r + 2;
c = c + 2;

/* initialize random seed: */
srand(time(NULL));

float **arr = (float **)malloc(r * sizeof(float *));
for (int i = 0; i < r; i++)
    arr[i] = (float *)malloc(c * sizeof(float));

float **pl_arr = (float **)malloc(r * sizeof(float *));
for (int i = 0; i < r; i++)
    pl_arr[i] = (float *)malloc(c * sizeof(float));


for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
        if ((i == 0) || (i == (r - 1)) || (j == 0) || (j == (c - 1)) ){
            arr[i][j] = 0;
            pl_arr[i][j] = 0;
        }
        else {
            arr[i][j] = rand() % 99  + 1;
            pl_arr[i][j] = arr[i][j];
        }
    }
}

#pragma omp parallel for schedule(static) - for 构造拆分 for 循环，以便当前团队中的每个线程处理循环的不同部分。

结果：并行版本总是比顺序版本慢

Answer 1

如果你了解循环的顺序版本中发生了什么，你会看到内部循环访问顺序内存地址（或者更准确地说，三个内存范围，每个范围的地址被顺序访问）。

现代 CPUs 非常好，可以遍历连续的内存地址。这就是为什么在许多用例中 std::vector 比 std::list 更快。

现在，对循环的并行版本执行相同的操作。用铅笔在纸上算出每根线最终会碰到什么。看起来它在矩阵中垂直迭代，跨越多个单独分配的行。那不会是连续的内存地址，它们会到处都是；这是不太理想的。

您可以简单地通过让每个线程捕获它正在破坏的原始内存地址，并查看所有执行线程的组合捕获日志来简单地做到这一点；现在将其与顺序版本的相同版本进行比较。

雪上加霜：在典型的现代架构中，内存区域被分成更大的块，称为 "cache lines"。看起来并行版本会有多个执行线程访问相邻的内存地址，其中很多会落入同一个缓存行；而当多个CPU个执行单元要写入同一个缓存行时，即使是每个缓存行内的不同地址，它们也不得不进行复杂的歌舞表演，以避免相互踩到对方的脚趾。

为什么并行版本更慢？

Why is parallel version slower?

c++

parallel-processing

openmp