c - OpenMP 上的工作不平衡

Question

我正在尝试并行化这种循环

#pragma omp parallel for private(i,j)
for(i=0;i<N;i++){  //N is very large
 for(j=0;j<i;j++){
   //do some work here
 }
}

使用 OpenMP 指令。

主要问题是随着i变大，最里面的循环有更多的工作要做。因为默认情况下，循环通过为每个线程分配一个连续的主体 for 循环迭代 block 来并行化(即，如果使用 2 个线程，则只有线程 1 被分配 i=0..N/2-1 并且线程 2 被分配 i=N/2..N-1) 最后一个线程总是比第一个线程有更多的工作，导致线程之间的负载不平衡。

我读到控制这种行为的一种方法是通过调度子句 schedule(type,chunk) 其中 type 可以是静态的、动态的或引导。问题是我不理解 schedule 子句的行为及其不同类型，所以我无法正确使用它。 (说明性示例可以解决问题)

特别是，我有兴趣为每个线程分配交替的迭代 block ，以便所有线程都从 i 的较低范围接收迭代，只要从其较高范围接收迭代，就等于每个线程正在做的工作。例如，如果使用 4 个线程，我希望发生这样的事情

thread1: i=0,4,8...
thread2: i=1,5,9...
thread3: i=2,6,10...
thread4: i=3,7,11...

尽管也欢迎使用其他方法解决该问题。

Answer 1

当您的内部循环取决于外部循环的迭代次数时，我认为您需要使用 schedule(guided)。 编辑:我现在认为 `schedule(static,1) 可能是最好的，因为它可以平衡负载并且比动态调度程序具有更少的开销。请参阅答案的结尾。我的意思是

for(i=0;i<N;i++) {
    for(j=0;j<i;j++){
       //do some work here
    }
}

或

for(i=0;i<N-1;i++) {
    for(j=i+1;j<N;j++){
       //do some work here
    }
}

这两个都运行在一个三角形的数字上(自上而下或自下而上)并进行 N*(N+1)/2 次迭代。让我们看看当您使用 schedule(static) 并在您的代码中使用 2 个线程 N = 8 时会发生什么。

schedule (static): thread 1 i = 0-3, thread 2 i = 4-7
thread 1: chunck_size = 4
    i = 1, j = 0
    i = 2, j = 0, 1
    i = 3, j = 0, 1, 2
    iterations = 1+2+3 = 6
thread 2: chunck_size = 4
    i = 4, j = 0, 1, 2, 3
    i = 5, j = 0, 1, 2, 3, 4
    i = 6, j = 0, 1, 2, 3, 4, 5
    i = 7, j = 0, 1, 2, 3, 4, 5, 6
    iterations = 4+5+6+7 = 22

第一个线程执行 6 次迭代，第二个线程执行 22 次迭代，因此负载不平衡(假设每次迭代的工作量相等)。现在让我们看看schedule(guided)。通过引导，每个连续的线程都会获得 number_of_iterations_remaining/number_of_threads。

schedule (guided):
thread 1: chunk size = 8/2 = 4
    i = 1, j = 0
    i = 2, j = 0, 1
    i = 3, j = 0, 1, 2
    iterations = 1+2+3 = 6
thread 2: chunk size = 4/2 = 2
    i = 4, j = 0, 1, 2, 3
    i = 5, j = 0, 1, 2, 3, 4
    iterations = 4+5 = 9
thread 1: chunk size = 2/2 = 1
    i = 6, j = 0, 1, 2, 3, 4, 5
    iterations = 6
thread 2: chunk size = 1
    i = 7, j = 0, 1, 2, 3, 4, 5, 6
    iterations = 7 

现在负载均衡了。随着 i 的增加，j 的迭代次数也会增加，但随着 guided 的增加， block 大小会随着每个线程的增加而减小，因此这些的组合有两件事使每个线程的迭代次数变平。

编辑:

schedule (static,1):
thread 1: i = 1, j = 0
thread 2: i = 2, j = 0, 1
thread 1: i = 3, j = 0, 1, 2
thread 2: i = 4, j = 0, 1, 2, 3
thread 1: i = 5, j = 0, 1, 2, 3, 4
thread 2: i = 6, j = 0, 1, 2, 3, 4, 5
thread 1: i = 7, j = 0, 1, 2, 3, 4, 5, 6

线程 1 执行 1+3+5+7 = 16 次迭代线程 2 执行 2+4+6 = 12 次迭代。
如果我们定义 n = N/num_threads 那么通常线程 1 执行 n^2 迭代(因为奇数之和是一个平方)和线程 2将进行 (n-1)*n 次迭代。在本例中，n = 4。因此线程 1 进行了 4^2=16 次迭代，而线程 2 进行了 3*4=12 次迭代，因此我们看到公式是正确的。例如，如果 N = 200 且 num_threads=2，则线程 1 将执行 100^2 =10000 次迭代，线程 2 将执行 99*100=9900 次迭代。所以负载或多或少是平衡的。