68

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

我有两个问题：

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

请举例说明。

4

3 回答 3

145

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

staticschedule 意味着迭代块以循环方式静态映射到执行线程。静态调度的好处在于，OpenMP 运行时保证如果您有两个具有相同迭代次数的独立循环并使用静态调度以相同数量的线程执行它们，那么每个线程将接收完全相同的迭代范围（ s) 在两个平行区域中。这在 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 倍 - 1.9 倍）。你运行这样的东西：

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 上一个内存页面的标准大小。此代码会将整个 32 KiB 数组归零a。该malloc()调用仅保留虚拟地址空间，但实际上并没有“触及”物理内存（这是默认行为，除非使用其他版本malloc，例如像calloc()这样将内存归零的版本）。现在这个数组是连续的，但只在虚拟内存中。在物理内存中，一半位于连接到套接字 0 的内存中，另一半位于连接到套接字 1 的内存中。这是因为不同的部分被不同的线程归零，并且这些线程位于不同的内核上，并且有一种叫做first touch的东西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（代替使用时会观察到相同的行为）

如果本节中的示例代码static是使用调度运行的，dynamic那么将只有 1/70 (1.4%) 的机会会保留原始位置，而 69/70 (98.6%) 的机会会发生远程访问。这一事实经常被忽视，因此实现了次优性能。

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

由于预编译代码可以在各种平台上运行，如果最终用户可以控制调度，那就太好了。这就是 OpenMP 提供特殊schedule(runtime)子句的原因。通过runtime调度，类型取自环境变量的内容OMP_SCHEDULE。这允许在不重新编译应用程序的情况下测试不同的调度类型，并且还允许最终用户针对他或她的平台进行微调。

于 2012-06-01T15:10:02.537 回答
27

我认为误解来自于你错过了关于 OpenMP 的观点。一句话 OpenMP 允许您通过启用并行性来更快地执行您的程序。在程序中，可以通过多种方式启用并行性，其中一种是使用线程。假设你有和数组：

[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/

于 2012-06-01T12:48:34.833 回答
13

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

动态方法动态计算子集的大小，如果子集的计算时间不同，这可能很有用。

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

于 2012-06-01T12:26:16.893 回答