当数组达到一定大小时，OpenMP 会明显变慢
Pat*_*igl 5 c openmp dependency-analysis
我正在尝试解决并行计算的作业示例。这是给定的代码片段：
for (int i=0; i < n-1; i++) {
x[i] = (y[i] + x[i+1]) / 7;
}
我们必须分析有关依赖关系的代码片段，并尝试并行化给定的片段并使用适当的样本大小对其进行基准测试。我的第一次尝试只是复制x并删除此处的反依赖：
double *x_old = malloc(sizeof(*x_old) * n); // the plain "copy" of x
memcpy(x_old, &x[1], (n - 1) * sizeof(*x)); // to prevent i + 1 in loop we start x[1] and copy n - 1 elements
#pragma omp parallel for
for (int i = 0; i < n-1; i++) {
x[i] = (y[i] + x_old[i]) / 7;
}
这段代码有效，我检查了数组的串行和并行校验和，它们都是相同的。对于100_000_00 - 400_000_000 数组元素，不计算 in 的加速memcpy()比在1.6 - 2之间。但是，如果我进一步增加数组大小（大约470_000_000 个元素），加速会显着降低，而在500_000_000 个数组元素时，加速为0.375。我使用多少个线程无关紧要。
我在 3 个不同的设备上对其进行了基准测试，结果相同（加速方面）：
联想Ideapad 5
桌上型电脑
在我们的集群节点 PC 上
为什么加速比会下降并且下降得这么快？为什么在特定大小的数组下会发生这种情况？
我在这里提供了该程序的最小示例：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include "omp.h"
void init(double *arr, int size);
double sum(double *arr, int size);
int main(int argc, char **argv){
if(argc != 3){
printf("Wrong use of program! (1) Size of array, (2) num threads\n");
return EXIT_FAILURE;
}
int n = atoi(argv[1]);
int threads = atoi(argv[2]);
omp_set_num_threads(threads);
double *x = malloc(sizeof(*x) * n);
double *y = malloc(sizeof(*y) * n);
init(x, n);
init(y, n);
double start = omp_get_wtime();
for (int i = 0; i < n-1; i++) {
x[i] = (y[i] + x[i+1]) / 7;
}
double end = omp_get_wtime();
double elapsed_s = end - start;
printf("single elapsed: %fs\n", elapsed_s);
double checksum_s = sum(x, n);
printf("single checksum: %f\n", checksum_s);
init(x, n); //reinit
init(y, n); //reinit
double *x_old = malloc(sizeof(*x_old) * n); // the plain "copy" of x
memcpy(x_old, &x[1], (n - 1) * sizeof(*x)); // to prevent i + 1 in loop we start x[1] and copy n - 1 elements
start = omp_get_wtime();
#pragma omp parallel for
for (int i = 0; i < n-1; i++) {
x[i] = (y[i] + x_old[i]) / 7;
}
end = omp_get_wtime();
double elapsed_p = end - start;
printf("omp threads %d Thread(s) elapsed: %fs\n", omp_get_max_threads(), elapsed_p);
double checksum_p = sum(x, n);
printf("omp threads %d Thread(s) single checksum: %f\n", omp_get_max_threads(), checksum_p);
printf("%s\n", fabs((checksum_p - checksum_s)) < __DBL_EPSILON__ ? "OK" : "FAILED");
printf("Speedup: %.3f\n", elapsed_s / elapsed_p);
}
void init(double *arr, int size){
for(int i = 0; i < size; ++i){
arr[i] = 1.0;
}
}
double sum(double *arr, int size){
double sum = 0.0;
for(int i = 0; i < size; ++i){
sum += arr[i];
}
return sum;
}
这是一个示例基准：
问题肯定来自交换内存。事实上，代码分配了 3 个包含 500_000_000 个项目的数组，导致每个数组需要 4 GiB 的 RAM，总共需要 12 GiB。问题是两台基准测试机器只有 16 GiB 的可用 RAM，而操作系统以及运行的应用程序通常已经需要 1-4 GiB 的 RAM。当可用物理内存量变小时，操作系统开始在称为交换内存的空间上移动内存页面，该空间通常映射到比普通 RAM 慢得多的存储设备上。请注意，某些操作系统（例如 Windows）已经使用 ZRAM，以便在可用内存量变小时压缩数据。主流操作系统（Windows、Linux和MAC也需要一些额外的缓冲区空间（例如存储设备缓冲区、网络缓冲区等）。当内存量变小时，内存页面的分配也会变得更慢。另请注意，页面是仅在第一次接触主流系统时分配在RAM中。有关这方面的更多信息，请阅读这篇文章。
分配一个巨大的x_old数组效率不高（在时间和空间上）。事实上，memcopy 将花费大量时间来复制内存中的数据，并且此操作受到 RAM 吞吐量的限制，而 RAM 的吞吐量通常较低。您可以通过对chunk进行操作来加快操作速度。这个想法是在每个线程中复制一个小数据块（比如说 16 KiB），以便可以在每个核心的 L1 缓存中完成操作。这意味着成本memcpy几乎消失，因为 CPU 缓存比 RAM 快得多（延迟和吞吐量）。事实上，笔记本/台式计算机的 L1 CPU 缓存应 >100 GiB/核心，从而导致累积吞吐量 >600 GiB，而 RAM 的吞吐量实际上不应超过 40 GiB/s（慢 15 倍）。
对于集群节点来说，情况要复杂一些，因为它会受到 NUMA 的影响。NUMA 架构相当复杂。如需了解更多信息，我建议您先阅读本文，然后阅读解释为什么在添加 CPU 时有效 DRAM 带宽会降低（包括相关链接）和通过实验将 OpenMP 线程排序到 NUMA 节点的问题。简而言之，您需要关心页面分配到哪里（分配策略）。关键是控制页面上的第一次触摸（在大多数平台上）。