OpenMP 中的“静态”和“动态”调度有什么区别？

我开始使用 C + + 使用 OpenMP。

我有两个问题:

  1. 什么是 #pragma omp for schedule？
  2. dynamic和 static有什么不同？

请举例说明。

109753 次浏览
小开

循环划分方案是不同的。静态调度器将 N 个元素上的循环划分为 M 个子集，然后每个子集将严格包含 N/M 个元素。

这种动态方法可以动态地计算子集的大小，如果子集的计算时间不同，这种方法将非常有用。

如果计算时间变化不大，则应采用静态方法。

小开

我认为这个误解是因为你没有抓住 OpenMP 的要点。 在一个句子中，OpenMP 允许您通过启用并行性来更快地执行程序。 在程序中，并行性可以通过许多方式实现，其中之一就是使用线程。 假设你有和 array:

[1,2,3,4,5,6,7,8,9,10]

并且希望将此数组中的所有元素增加1。

如果你要用

#pragma omp for schedule(static, 5)

这意味着每个线程将被分配5个连续迭代。在这种情况下，第一个线程将采用5个数字。第二个线程需要另外5个线程，以此类推，直到没有更多的数据需要处理，或者达到线程的最大数量(通常等于内核的数量)。工作负载共享是在编译期间完成的。

以防万一

#pragma omp for schedule(dynamic, 5)

工作将在线程之间共享，但此过程将在运行时发生。因此涉及更多的开销。第二个参数指定数据块的大小。

我对 OpenMP 不是很熟悉，所以当编译的代码运行在与编译代码的系统配置不同的系统上时，我可能会认为动态类型更合适。

我建议在下面的页面中讨论用于并行化代码、前提条件和限制的技术

Https://computing.llnl.gov/tutorials/parallel_comp/

附加链接 :
Http://en.wikipedia.org/wiki/openmp
C 中 openMP 中静态调度与动态调度的区别
Http://openmp.blogspot.se/

小开
最佳答案

其他人已经回答了大部分问题，但是我想指出一些特定的情况，在这些情况下，特定的调度类型比其他类型更适合。调度控制如何在线程之间划分循环迭代。选择正确的时间表可以对应用程序的速度产生很大的影响。

static调度意味着迭代块以循环方式静态映射到执行线程。静态调度的好处是 OpenMP 运行时保证，如果您有两个具有相同迭代次数的独立循环，并且使用静态调度使用相同数量的线程执行它们，那么每个线程将在两个并行区域接收完全相同的迭代范围。这在 NUMA 系统中非常重要: 如果在第一个循环中触及某些内存，它将驻留在执行线程所在的 NUMA 节点上。然后在第二个循环中，相同的线程可以更快地访问相同的内存位置，因为它将驻留在相同的 NUMA 节点上。

假设有两个 NUMA 节点: 节点0和节点1，例如一个双套接字 Intel Nehalem 板，两个套接字中都有4核 CPU。然后，线程0、1、2和3将驻留在节点0上，而线程4、5、6和7将驻留在节点1上:

|             | core 0 | thread 0 |
| socket 0    | core 1 | thread 1 |
| NUMA node 0 | core 2 | thread 2 |
|             | core 3 | thread 3 |


|             | core 4 | thread 4 |
| socket 1    | core 5 | thread 5 |
| NUMA node 1 | core 6 | thread 6 |
|             | core 7 | thread 7 |

每个核心都可以从每个 NUMA 节点访问内存，但远程访问比本地节点访问慢(Intel 上为1.5 x-1.9 x)。如果你这么做:

char *a = (char *)malloc(8*4096);


#pragma omp parallel for schedule(static,1) num_threads(8)
for (int i = 0; i < 8; i++)
memset(&a[i*4096], 0, 4096);

在这种情况下，如果不使用巨大的页面，4096字节是 x86上 Linux 上一个内存页面的标准大小。这段代码将整个32KiB 数组 a归零。malloc()调用只保留了虚拟地址空间，但实际上并没有“触及”物理内存(这是默认行为，除非使用其他版本的 malloc，例如像 calloc()那样对内存进行归零)。现在这个数组是连续的，但只在虚拟内存中。在物理内存中，它的一半位于连接到套接字0的内存中，另一半位于连接到套接字1的内存中。这是因为不同的部分被不同的线程归零，这些线程位于不同的核心上，有一个叫做 第一次接触 NUMA 策略的东西，这意味着内存页分配在 NUMA 节点上，第一个“接触”内存页的线程所在的节点上。

|             | core 0 | thread 0 | a[0]     ... a[4095]
| socket 0    | core 1 | thread 1 | a[4096]  ... a[8191]
| NUMA node 0 | core 2 | thread 2 | a[8192]  ... a[12287]
|             | core 3 | thread 3 | a[12288] ... a[16383]


|             | core 4 | thread 4 | a[16384] ... a[20479]
| socket 1    | core 5 | thread 5 | a[20480] ... a[24575]
| NUMA node 1 | core 6 | thread 6 | a[24576] ... a[28671]
|             | core 7 | thread 7 | a[28672] ... a[32768]

现在让我们像这样运行另一个循环:

#pragma omp parallel for schedule(static,1) num_threads(8)
for (i = 0; i < 8; i++)
memset(&a[i*4096], 1, 4096);

每个线程将访问已经映射的物理内存，它将具有与第一个循环中的线程到内存区域相同的映射。这意味着线程将只访问位于其本地内存块中的内存，这将是快速的。

现在假设对第二个循环使用另一种调度方案: schedule(static,2)。这将把迭代空间“砍”成两个迭代块，总共有4个这样的块。将要发生的是，我们将有以下线程到内存位置的映射(通过迭代号) :

|             | core 0 | thread 0 | a[0]     ... a[8191]  <- OK, same memory node
| socket 0    | core 1 | thread 1 | a[8192]  ... a[16383] <- OK, same memory node
| NUMA node 0 | core 2 | thread 2 | a[16384] ... a[24575] <- Not OK, remote memory
|             | core 3 | thread 3 | a[24576] ... a[32768] <- Not OK, remote memory


|             | core 4 | thread 4 | <idle>
| socket 1    | core 5 | thread 5 | <idle>
| NUMA node 1 | core 6 | thread 6 | <idle>
|             | core 7 | thread 7 | <idle>

这里发生了两件坏事:

  • 线程4到7保持空闲，计算能力的一半丢失;
  • 线程2和线程3访问非本地内存，在线程0和线程1保持空闲的时间内，它们将花费大约两倍的时间来完成。

因此，使用静态调度的优点之一是它提高了内存访问的局部性。缺点是调度参数选择不当会影响系统性能。

dynamic调度工作在“先到先得”的基础上。具有相同数量线程的两次运行可能(而且很可能)会产生完全不同的“迭代空间”-> “线程”映射，这一点可以很容易地验证:

$ cat dyn.c
#include <stdio.h>
#include <omp.h>


int main (void)
{
int i;


#pragma omp parallel num_threads(8)
{
#pragma omp for schedule(dynamic,1)
for (i = 0; i < 8; i++)
printf("[1] iter %0d, tid %0d\n", i, omp_get_thread_num());


#pragma omp for schedule(dynamic,1)
for (i = 0; i < 8; i++)
printf("[2] iter %0d, tid %0d\n", i, omp_get_thread_num());
}


return 0;
}


$ icc -openmp -o dyn.x dyn.c


$ OMP_NUM_THREADS=8 ./dyn.x | sort
[1] iter 0, tid 2
[1] iter 1, tid 0
[1] iter 2, tid 7
[1] iter 3, tid 3
[1] iter 4, tid 4
[1] iter 5, tid 1
[1] iter 6, tid 6
[1] iter 7, tid 5
[2] iter 0, tid 0
[2] iter 1, tid 2
[2] iter 2, tid 7
[2] iter 3, tid 3
[2] iter 4, tid 6
[2] iter 5, tid 1
[2] iter 6, tid 5
[2] iter 7, tid 4

(当使用 gcc代替时，观察到相同的行为)

如果使用 dynamic调度来运行来自 static部分的示例代码，那么只有1/70(1.4%)的机会保留原始本地，69/70(98.6%)的机会发生远程访问。这个事实经常被忽视，因此性能达不到最佳。

在 static和 dynamic调度之间进行选择的另一个原因是工作负载平衡。如果每次迭代的完成时间与平均完成时间有很大不同，那么在静态情况下可能会出现高工作不平衡。以完成一个迭代的时间与迭代次数成线性增长的情况为例。如果迭代空间在两个线程之间静态地划分，那么第二个线程的工作量将是第一个线程的三倍，因此在计算时间的2/3时间内，第一个线程将处于空闲状态。动态调度引入了一些额外的开销，但在这种特殊情况下，将导致更好的工作负载分配。一种特殊的 dynamic调度方法是 guided，在这种方法中，随着工作的进展，每个任务都会被赋予越来越小的迭代块。

由于预编译代码可以在不同的平台上运行，所以如果最终用户能够控制调度就更好了。这就是为什么 OpenMP 提供了特殊的 schedule(runtime)子句。使用 runtime调度时，类型取自环境变量 OMP_SCHEDULE的内容。这允许在不重新编译应用程序的情况下测试不同的调度类型，还允许最终用户对其平台进行微调。


提交答案