时间戳

首页 > 解决方案 > 使用动态调度时等待很长时间执行循环

c - 使用动态调度时等待很长时间执行循环

问题描述

我正在做一个项目，我必须创建一个并行 for 循环和矩阵乘法。代码由 3 个公共变量 A、B、C 组成，其中 A、B 是我将相乘的数组的值，变量 C 是结果所在的数组。例如，当我使用静态调度时，执行时间以秒为单位是正常的

threads | Average (time)
  1     |    89 (sec)
  2     |    58 (Sec)
  3     |    49 (sec)
  4     |    42 (sec)

但是，当我使用动态调度时，我会在执行中等待很长时间，例如使用 4 个线程时，我得到了这些结果，这与线程较少的平均时间有关。

threads    | Average (time)
   4       |   289(sec)

所以我的问题是，这个平均时间动态安排是否正常？如果不是，我怎么能让它更快或更好。值得一提的是，在下面的代码中，当我尝试并行第一个或第二个循环时，我有动态调度的逻辑平均时间，为什么会发生这种情况？我在代码中的解释。我在那里使用临界区，因为线程正在更新数组的相同位置。

代码

for (i = 0; i < N; i++) // loop1
        for (j = 0; j < N; j++) // loop2 
        {
            #pragma omp parallel for  num_threads(NUM_THREADS) \
                      schedule(static) reduction(+:sum) firstprivate(i,j)
            for (k = sum = 0; k < N; k++) // loop3
                sum += A[i][k]*B[k][j];
            #pragma omp critical
            C[i][j] = sum;
        };

我知道我可以忽略 sum 并使用 C[i][j] 代替它，但我必须保持这样的代码。所以谁能告诉我我是否可以做得更好，或者动态时间表中的那些时间是否正好在第三个循环中

操作系统：Linux
内核：4

标签： cmultithreadingperformanceparallel-processingopenmp

解决方案

TL;DR：问题来自导致线程争用的动态调度程序隐式同步。

for (i = 0; i < N; i++) // loop1
        for (j = 0; j < N; j++) // loop2 
        {
            #pragma omp parallel for  num_threads(NUM_THREADS) \
                      schedule(static) reduction(+:sum) firstprivate(i,j)
            for (k = sum = 0; k < N; k++) // loop3
                sum += A[i][k]*B[k][j];
            #pragma omp critical
            C[i][j] = sum;
        };

正如我在上一个问题中提到的那样，并行化最外层循环可能会更有效。

我在那里使用临界区，因为线程正在更新数组的相同位置。

在您当前的版本中，您可以删除#pragma omp critical没有执行任何操作的内容，因为它位于并行区域之外。因此，代码是按顺序执行的。

所以我的问题是，这个平均时间动态安排是否正常？

当存在负载平衡问题时，动态调度程序更合适，即线程执行的工作比其他线程多，这不是您的情况。在您的代码中，线程执行的工作量大致相同。然而，动态调度器的缺点是它增加了额外的同步开销，需要在线程之间原子地分配迭代。

如果不是，我怎么能让它更快或更好。

对于您的情况，静态调度程序是最合适的。尽管如此，您可以通过增加所使用的块大小（例如， 32 而不是默认的 1）来减少动态调度程序的开销。通过增加块大小，您将减少（尤其是）使用的同步量，从而减少其开销。

值得一提的是，在下面的代码中，当我尝试并行第一个或第二个循环时，我有动态调度的逻辑平均时间，为什么会发生这种情况？

因为之前并行任务的粒度更大（即每个并行任务需要更多的时间来执行）。目前的并行化，任务粒度太小了。它太小了，因为您只是在执行，并且动态sum += A[i][k]*B[k][j];调度程序的块大小只有 1，这意味着线程将过于频繁地调用动态调度程序。而且由于动态同步，该同步可能会引入线程争用，当两个或多个线程尝试同时访问同一资源时会发生这种争用。这就是为什么使用 4 个线程时速度会如此缓慢的原因；因为在上述条件下，线程数越多，发生线程争用的可能性就越高。

正如Jim Cownie在评论（对此答案）中所指出的那样

另一个需要了解的小事实是，如果您使用的是最新版本（即 OpenMP 4.5 或更高版本）兼容的编译器，您可以使用 schedule(nonmonotonic:dynamic)，这可以显着减少 schedule(dynamic) openmp.org 的开销/wp-content/uploads/SC18-BoothTalks-Cownie.pdf

推荐阅读