具有非常并行循环的 OpenMP 开销
OpenMP overhead with a very parallel loop
我正在尝试使用 OpenMP 并行化循环，其中每次迭代都是独立的（下面的代码示例）。
!$OMP PARALLEL DO DEFAULT(PRIVATE)
do i = 1, 16
begin = omp_get_wtime()
allocate(array(100000000))
do j=1, 100000000
array(j) = j
end do
deallocate(array)
end = omp_get_wtime()
write(*,*) "It", i, "Thread", omp_get_thread_num(), "time", end - begin
end do
!$END OMP PARALLEL DO
除了这段代码的线性加速之外，我希望每次迭代花费的时间与顺序版本一样多，因为不存在可能的竞争条件或错误共享问题。但是，我在配备 2 个 Xeon E5-2670（每个 8 个内核）的机器上获得了以下结果：
只有一个线程：
It 1 Thread 0 time 0.435683965682983
It 2 Thread 0 time 0.435048103332520
It 3 Thread 0 time 0.435137987136841
It 4 Thread 0 time 0.434695959091187
It 5 Thread 0 time 0.434970140457153
It 6 Thread 0 time 0.434894084930420
It 7 Thread 0 time 0.433521986007690
It 8 Thread 0 time 0.434685945510864
It 9 Thread 0 time 0.433223009109497
It 10 Thread 0 time 0.434834957122803
It 11 Thread 0 time 0.435106039047241
It 12 Thread 0 time 0.434649944305420
It 13 Thread 0 time 0.434831142425537
It 14 Thread 0 time 0.434768199920654
It 15 Thread 0 time 0.435182094573975
It 16 Thread 0 time 0.435090065002441
并且有 16 个线程：
It 1 Thread 0 time 1.14882898330688
It 3 Thread 2 time 1.19775915145874
It 4 Thread 3 time 1.24406099319458
It 14 Thread 13 time 1.28723978996277
It 8 Thread 7 time 1.39885497093201
It 10 Thread 9 time 1.46112895011902
It 6 Thread 5 time 1.50975203514099
It 11 Thread 10 time 1.63096308708191
It 16 Thread 15 time 1.69229602813721
It 7 Thread 6 time 1.74118590354919
It 9 Thread 8 time 1.78044819831848
It 15 Thread 14 time 1.82169485092163
It 12 Thread 11 time 1.86312794685364
It 2 Thread 1 time 1.90681600570679
It 5 Thread 4 time 1.96404480934143
It 13 Thread 12 time 2.00902700424194
知道迭代时间中的 4 倍因子是从哪里来的吗？
我已经使用 GNU 编译器和带有 O3 优化标志的 Intel 编译器进行了测试。
运行速度
do j=1, 100000000
array(j) = j
end do
不受 ALU 速度的限制，而是受内存带宽的限制。通常，您现在每个 CPU 个可用插槽都有几个到主内存的通道，但仍然比核心数量少。
分配和解除分配也受内存访问限制。我不确定 allocate 和 deallocate 是否也需要一些同步。
出于同样的原因，STREAM 基准测试 http://www.cs.virginia.edu/stream/ 给出了与纯算术密集型问题不同的加速。
他们不是独立的。 Allocate/deallocate 将共享堆。
尝试在并行部分之外分配一个更大的数组，然后只对内存访问计时。
这也是一个不统一的内存架构 - 如果所有分配都来自一个 cpu 的本地内存，则从另一个 cpu 访问会相对较慢，因为它们是通过第一个进行路由的cpu。解决这个问题很乏味。
我确定我之前已经讨论过这个话题，但由于我似乎找不到我以前的帖子，所以我再来一次...
Linux（可能还有其他平台）上的大内存分配是通过匿名内存映射处理的。也就是说，通过使用标志 MAP_ANONYMOUS 调用 mmap(2)，在进程的虚拟地址 space 中保留了一些区域。地图最初是空的——没有物理内存支持它们。相反，它们与所谓的零页相关联，这是物理内存中填充零的只读帧。由于零页不可写，因此尝试写入仍由它支持的内存位置会导致分段错误。内核通过在物理内存中找到空闲帧并将其与发生故障的虚拟内存页相关联来处理故障。此过程称为内存故障。
内存故障是一个相对较慢的过程，因为它涉及修改进程的 PTE（页面 table 条目）和刷新 TLB（翻译后备缓冲区）缓存。在多核和多插槽系统上，它甚至更慢，因为它涉及通过昂贵的处理器间中断使远程 TLB 失效（称为 远程 TLB 关闭 ）。释放分配会导致删除内存映射并重置 PTE。因此，整个过程在下一次迭代中重复。
确实，如果您查看串行情况下的有效内存带宽，它是（假设一个双精度浮点数数组）：
(100000000 * 8) / 0.435 = 1.71 GiB/s
如果您的 array 是 REAL 或 INTEGER 元素，则带宽应减半。这根本不是 the very first generation of E5-2670 提供的内存带宽。
对于并行情况，情况更糟，因为内核在错误页面时锁定页面 tables。这就是为什么单个线程的平均带宽从 664 MiB/s 下降到 380 MiB/s 总共 7.68 GiB/s，这几乎比内存带宽慢一个数量级单个 CPU（您的系统有两个，因此是可用带宽的两倍！）。
如果将分配移到循环之外，将会出现完全不同的情况：
!$omp parallel default(private)
allocate(array(100000000))
!$omp do
do i = 1, 16
begin = omp_get_wtime()
do j=1, 100000000
array(j) = j
end do
end = omp_get_wtime()
write(*,*) "It", i, "Thread", omp_get_thread_num(), "time", end - begin
end do
!$omp end do
deallocate(array)
!$omp end parallel
现在第二次和以后的迭代将产生两倍更短的时间（至少在 E5-2650 上）。这是因为在第一次迭代之后，所有内存都已经出现故障。对于多线程情况，收益甚至更大（将循环计数增加到 32 以使每个线程执行两次迭代）。
内存故障时间很大程度上取决于系统配置。在启用了 THP（透明大页面）的系统上，内核自动使用大页面来实现大映射。这将故障数量减少了 512 倍（对于 2 MiB 的大页面）。上面提到的串行情况的 2 倍速度增益和并行情况的 2.5 倍速度增益来自启用了 THP 的系统。仅仅使用大页面就可以将 E5-2650 上第一次迭代的时间减少到你的情况的 1/4（如果你的数组是整数或单精度浮点数，则为 1/8）。
较小的数组通常不是这种情况，它们是通过细分较大且可重复使用的持久内存分配（称为 arena）来分配的。 glibc 中较新的内存分配器通常每个 CPU 核心有一个区域，以促进无锁多线程分配。
这就是为什么许多基准测试应用程序简单地丢弃第一个测量值的原因。
只是为了通过实际测量来证实上述内容，我的 E5-2650 需要 0.183 秒才能对已经出现故障的内存执行连续一次迭代，而需要 0.209 秒才能使用 16 个线程（在双插槽系统上）执行它.
我正在尝试使用 OpenMP 并行化循环，其中每次迭代都是独立的（下面的代码示例）。
!$OMP PARALLEL DO DEFAULT(PRIVATE)
do i = 1, 16
begin = omp_get_wtime()
allocate(array(100000000))
do j=1, 100000000
array(j) = j
end do
deallocate(array)
end = omp_get_wtime()
write(*,*) "It", i, "Thread", omp_get_thread_num(), "time", end - begin
end do
!$END OMP PARALLEL DO
除了这段代码的线性加速之外，我希望每次迭代花费的时间与顺序版本一样多，因为不存在可能的竞争条件或错误共享问题。但是，我在配备 2 个 Xeon E5-2670（每个 8 个内核）的机器上获得了以下结果：
只有一个线程：
It 1 Thread 0 time 0.435683965682983
It 2 Thread 0 time 0.435048103332520
It 3 Thread 0 time 0.435137987136841
It 4 Thread 0 time 0.434695959091187
It 5 Thread 0 time 0.434970140457153
It 6 Thread 0 time 0.434894084930420
It 7 Thread 0 time 0.433521986007690
It 8 Thread 0 time 0.434685945510864
It 9 Thread 0 time 0.433223009109497
It 10 Thread 0 time 0.434834957122803
It 11 Thread 0 time 0.435106039047241
It 12 Thread 0 time 0.434649944305420
It 13 Thread 0 time 0.434831142425537
It 14 Thread 0 time 0.434768199920654
It 15 Thread 0 time 0.435182094573975
It 16 Thread 0 time 0.435090065002441
并且有 16 个线程：
It 1 Thread 0 time 1.14882898330688
It 3 Thread 2 time 1.19775915145874
It 4 Thread 3 time 1.24406099319458
It 14 Thread 13 time 1.28723978996277
It 8 Thread 7 time 1.39885497093201
It 10 Thread 9 time 1.46112895011902
It 6 Thread 5 time 1.50975203514099
It 11 Thread 10 time 1.63096308708191
It 16 Thread 15 time 1.69229602813721
It 7 Thread 6 time 1.74118590354919
It 9 Thread 8 time 1.78044819831848
It 15 Thread 14 time 1.82169485092163
It 12 Thread 11 time 1.86312794685364
It 2 Thread 1 time 1.90681600570679
It 5 Thread 4 time 1.96404480934143
It 13 Thread 12 time 2.00902700424194
知道迭代时间中的 4 倍因子是从哪里来的吗？
我已经使用 GNU 编译器和带有 O3 优化标志的 Intel 编译器进行了测试。
运行速度
do j=1, 100000000
array(j) = j
end do
不受 ALU 速度的限制，而是受内存带宽的限制。通常，您现在每个 CPU 个可用插槽都有几个到主内存的通道，但仍然比核心数量少。
分配和解除分配也受内存访问限制。我不确定 allocate 和 deallocate 是否也需要一些同步。
出于同样的原因，STREAM 基准测试 http://www.cs.virginia.edu/stream/ 给出了与纯算术密集型问题不同的加速。
他们不是独立的。 Allocate/deallocate 将共享堆。
尝试在并行部分之外分配一个更大的数组，然后只对内存访问计时。
这也是一个不统一的内存架构 - 如果所有分配都来自一个 cpu 的本地内存，则从另一个 cpu 访问会相对较慢，因为它们是通过第一个进行路由的cpu。解决这个问题很乏味。
我确定我之前已经讨论过这个话题，但由于我似乎找不到我以前的帖子，所以我再来一次...
Linux（可能还有其他平台）上的大内存分配是通过匿名内存映射处理的。也就是说，通过使用标志 MAP_ANONYMOUS 调用 mmap(2)，在进程的虚拟地址 space 中保留了一些区域。地图最初是空的——没有物理内存支持它们。相反，它们与所谓的零页相关联，这是物理内存中填充零的只读帧。由于零页不可写，因此尝试写入仍由它支持的内存位置会导致分段错误。内核通过在物理内存中找到空闲帧并将其与发生故障的虚拟内存页相关联来处理故障。此过程称为内存故障。
内存故障是一个相对较慢的过程，因为它涉及修改进程的 PTE（页面 table 条目）和刷新 TLB（翻译后备缓冲区）缓存。在多核和多插槽系统上，它甚至更慢，因为它涉及通过昂贵的处理器间中断使远程 TLB 失效（称为 远程 TLB 关闭 ）。释放分配会导致删除内存映射并重置 PTE。因此，整个过程在下一次迭代中重复。
确实，如果您查看串行情况下的有效内存带宽，它是（假设一个双精度浮点数数组）：
(100000000 * 8) / 0.435 = 1.71 GiB/s
如果您的 array 是 REAL 或 INTEGER 元素，则带宽应减半。这根本不是 the very first generation of E5-2670 提供的内存带宽。
对于并行情况，情况更糟，因为内核在错误页面时锁定页面 tables。这就是为什么单个线程的平均带宽从 664 MiB/s 下降到 380 MiB/s 总共 7.68 GiB/s，这几乎比内存带宽慢一个数量级单个 CPU（您的系统有两个，因此是可用带宽的两倍！）。
如果将分配移到循环之外，将会出现完全不同的情况：
!$omp parallel default(private)
allocate(array(100000000))
!$omp do
do i = 1, 16
begin = omp_get_wtime()
do j=1, 100000000
array(j) = j
end do
end = omp_get_wtime()
write(*,*) "It", i, "Thread", omp_get_thread_num(), "time", end - begin
end do
!$omp end do
deallocate(array)
!$omp end parallel
现在第二次和以后的迭代将产生两倍更短的时间（至少在 E5-2650 上）。这是因为在第一次迭代之后，所有内存都已经出现故障。对于多线程情况，收益甚至更大（将循环计数增加到 32 以使每个线程执行两次迭代）。
内存故障时间很大程度上取决于系统配置。在启用了 THP（透明大页面）的系统上，内核自动使用大页面来实现大映射。这将故障数量减少了 512 倍（对于 2 MiB 的大页面）。上面提到的串行情况的 2 倍速度增益和并行情况的 2.5 倍速度增益来自启用了 THP 的系统。仅仅使用大页面就可以将 E5-2650 上第一次迭代的时间减少到你的情况的 1/4（如果你的数组是整数或单精度浮点数，则为 1/8）。
较小的数组通常不是这种情况，它们是通过细分较大且可重复使用的持久内存分配（称为 arena）来分配的。 glibc 中较新的内存分配器通常每个 CPU 核心有一个区域，以促进无锁多线程分配。
这就是为什么许多基准测试应用程序简单地丢弃第一个测量值的原因。
只是为了通过实际测量来证实上述内容，我的 E5-2650 需要 0.183 秒才能对已经出现故障的内存执行连续一次迭代，而需要 0.209 秒才能使用 16 个线程（在双插槽系统上）执行它.