为什么并行版本比较慢？

Question

我想在矩阵上应用特定的过滤器。(从头到尾)

Ai = 0.2 * (Ai + Ai+1 + Ai-1 + Ai + Ai)

例如，如果i，j是(矩阵中的第一个值)，则在左边和上面使用零作为值。

我试图理解为什么并行版本的代码比顺序版本慢。

当我使用多线程进行计算时，我使用的事实是，在对角线上有独立的工作。为了简化滤波器的计算，我有意地将矩阵扩展为两行和两科尔(填充为零)。

我还尝试了各种尺寸的矩阵(高达7000x7000)。

我的问题：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];
        }
    }
}

#语用omp并行调度(静态)- for构造拆分for -循环，以便当前团队中的每个线程处理循环的不同部分。

结果: Paralle版本总是比顺序版本慢。

Answer 1

如果您计算出循环的顺序版本中发生了什么，您将看到内环访问顺序内存地址(或者更准确地说，访问三个内存范围，每个区域的地址按顺序访问)。

现代CPU是非常好的，并通过连续的内存地址。这就是为什么在许多用例中，std::vector可以反直觉地比std::list更快。

现在，对循环的并行版本也这样做。用铅笔在纸上算出每根线最后会碰到什么。看起来它是在垂直遍历矩阵，跨越多个单独分配的行。这不是连续的内存地址，而是到处都是；这不是最优的。

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

更糟的是:在典型的现代体系结构中，内存区域被划分为更大的块，称为“缓存线”。看起来，并行版本将有多个执行线程访问相邻的内存地址，其中许多线程将落入同一缓存线；当多个CPU执行单元必须写入同一高速缓存线时，即使写入每个缓存行中的不同地址，它们也必须执行一个复杂的歌舞例程，以避免踩到对方的脚趾。