使用动态计划时在执行循环时等待很长时间

Question

我正在做一个项目，我必须创建一个并行的 for 循环和矩阵乘法。该代码由 3 public 个变量 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] 代替它，但我必须保持这样的代码。所以谁能告诉我我是否可以做得更好，或者动态计划中的那些时间是否在第三个循环中是正确的

OS : linux
核心数：4

Answer 1

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

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

Am using critical sections there because threads are updating the same possitions of the array.

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

So my question is , is it normal with dynamic schedule this average time ?

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

If its not how could I make it faster or better.

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

Its important to mention that in the code below when i was trying to parallel the first or the second loop i had logical average times with dynamic scheduling, why is this happening here ?

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

正如 Jim Cownie

在评论（针对此答案）中所指出的

One minor additional fact to know about is that if you're using an up top date (i.e. OpenMP 4.5 or later) compliant compiler you can use schedule(nonmonotonic:dynamic) which can significantly reduce the overhead of schedule(dynamic) openmp.org/wp-content/uploads/SC18-BoothTalks-Cownie.pdf

使用动态计划时在执行循环时等待很长时间

Waiting long time in execution of loop when using dynamic schedule

c

parallel-processing

performance

multithreading

openmp