通过实验将OpenMP线程排序到NUMA节点中的问题

Question

我正在尝试为每个 NUMA 节点创建一个包含一组的 std::vector<std::set<int>>，其中包含使用 omp_get_thread_num() 获得的线程 ID。

拓扑:

想法:

创建大于三级缓存的数据，
使用线程 0 设置第一次触摸，
进行多次实验以确定每个线程的最小访问时间，
根据排序的访问时间和有关拓扑的信息将线程提取到节点中。

代码：（英特尔编译器，OpenMP）

    // create data which will be shared by multiple threads
    const auto part_size = std::size_t{50 * 1024 * 1024 / sizeof(double)}; // 50 MB
    const auto size = 2 * part_size;
    auto container = std::unique_ptr<double>(new double[size]);
    
    // open a parallel section
    auto thread_count = 0;
    auto thread_id_min_duration = std::multimap<double, int>{};
    #ifdef DECIDE_THREAD_COUNT
    #pragma omp parallel num_threads(std::thread::hardware_concurrency())
    #else
    #pragma omp parallel
    #endif
    {
        // perform first touch using thread 0
        const auto thread_id = omp_get_thread_num();
        if (thread_id == 0)
        {
            thread_count = omp_get_num_threads();
            for (auto index = std::size_t{}; index < size; ++index)
            {
                container.get()[index] = static_cast<double>(std::rand() % 10 + 1);
            }
        }
        #pragma omp barrier
        
        // access the data using all threads individually
        #pragma omp for schedule(static, 1)
        for (auto thread_counter = std::size_t{}; thread_counter < thread_count; ++thread_counter)
        {
            // calculate the minimum access time of this thread
            auto this_thread_min_duration = std::numeric_limits<double>::max();
            for (auto experiment_counter = std::size_t{}; experiment_counter < 250; ++experiment_counter)
            {
                const auto* data = experiment_counter % 2 == 0 ? container.get() : container.get() + part_size;
                const auto start_timestamp = omp_get_wtime();
                for (auto index = std::size_t{}; index < part_size; ++index)
                {
                    static volatile auto exceedingly_interesting_value_wink_wink = data[index];
                }
                const auto end_timestamp = omp_get_wtime();
                const auto duration = end_timestamp - start_timestamp;
                if (duration < this_thread_min_duration)
                {
                    this_thread_min_duration = duration;
                }
            }
            #pragma omp critical
            {
                thread_id_min_duration.insert(std::make_pair(this_thread_min_duration, thread_id));
            }
        }
    } // #pragma omp parallel

此处未显示的是输出排序到多映射中的最小访问时间的代码。

环境。和输出

OMP_PLACES 和 OMP_PROC_BIND 是如何工作的？

我试图通过 export OMP_PLACES=cores OMP_PROC_BIND=spread OMP_NUM_THREADS=24 不使用 SMT。但是，我得到了这个输出：

令我困惑的是我在所有线程上的访问时间都相同。因为我试图将它们分布在 2 个 NUMA 节点上，所以我希望能清楚地看到 12 个具有访问时间的线程，比如 x 和另外 12 个具有访问时间的线程 ~2x.

为什么会出现上述情况？

附加信息

更令人费解的是以下环境及其输出：

export OMP_PLACES=cores OMP_PROC_BIND=spread OMP_NUM_THREADS=26
export OMP_PLACES=cores OMP_PROC_BIND=spread OMP_NUM_THREADS=48

如果能帮助理解这种现象，我们将不胜感激。

Answer 1

简而言之，基准测试存在缺陷。

perform multiple experiments to determine the minimum access time of each thread

此处术语“最短访问时间”不明确。我假设你的意思是“延迟”。问题是您的基准测试不会衡量延迟。 volatile 告诉编译器从内存层次结构中读取存储数据。处理器可以自由地将值存储在其缓存中，而 x86-64 处理器实际上会这样做（就像几乎所有现代处理器一样）。

How do OMP_PLACES and OMP_PROC_BIND work?

您可以找到 here and there. Put it shortly, I strongly advise you to set OMP_PROC_BIND=TRUE and OMP_PLACES="{0},{1},{2},..." based on the values retrieved from hw-loc. More specifically, you can get this from hwloc-calc 的文档，这是一个非常棒的工具（考虑使用 --li --po 和 PU，而不是 CORE，因为这就是 OpenMP运行时期望）。例如，您可以查询给定 NUMA 节点的 PU 标识符。请注意，某些机器的 non-linear OS PU 编号非常奇怪，而且 OpenMP 运行时有时无法正确映射线程。 IOMP（ICC 的 OpenMP 运行时）应该在内部使用 hw-loc，但我在过去发现了一些与此相关的错误。要检查映射是否正确，我建议您使用 hwloc-ps。请注意，OMP_PLACES=cores 不能保证线程不会从一个内核迁移到另一个内核（即使一个内核在不同的 NUMA 节点上），除非设置了 OMP_PROC_BIND=TRUE（或类似设置）。请注意，您还可以使用 numactl 来 控制进程的 NUMA 策略 。例如，您可以告诉 OS 不要使用给定的 NUMA 节点或交错分配。第一次接触策略不是唯一的，也可能不是所有平台上的默认策略（在某些 Linux 平台上，OS 可以在 NUMA 节点之间移动页面以改善局部性）。

Why is the above happening?

代码在每个线程中读取 50 MiB 内存需要 4.38 毫秒。这意味着假设应用了第一个触摸策略，从节点 0 读取 1200 MiB。因此，吞吐量应该约为 267 GiB/s。虽然乍一看这似乎很好，但对于这样的处理器来说这是一个相当大的吞吐量，特别是假设只使用 1 个 NUMA 节点。这当然是因为部分提取是从 L3 缓存而不是 RAM 完成的。事实上，缓存可以部分保存数组的一部分，并且由于 缓存关联性 和良好的 缓存策略 ，确实会导致更快的提取。尤其如此，因为缓存行不会失效，因为数组仅被读取。我建议你使用一个大得多的数组来防止这种复杂的效果发生。

由于远程 NUMA 内存访问，您当然希望一个 NUMA 节点具有较小的吞吐量。这在实践中并不总是正确的。事实上，这在现代 2 插槽系统上通常是错误的，因为插槽互连通常不是限制因素（这是 NUMA 系统上吞吐量下降的主要原因）。

由于不平衡的 NUMA 内存节点饱和和 non-uniform 延迟，现代平台上出现了 NUMA 效应。前者在您的应用程序中不是问题，因为所有 PU 使用相同的 NUMA 内存节点。由于线性内存访问模式、CPU缓存和硬件预取器，后者也不是问题：延迟应该完全隐藏.

Even more puzzling are the following environments and their outputs

在 24 核机器上使用 26 个线程意味着 4 个线程必须在两个内核上执行 。问题是 hyper-threading 在这种情况下应该没有多大帮助。结果，共享同一核心的多个线程将变慢。因为 IOMP 肯定会将线程固定到核心和 不平衡的工作负载 ，4 个线程将慢两倍左右。

拥有 48 个线程会导致所有线程变慢，因为工作量增加了一倍。

Answer 2

让我谈谈你的第一句话。 C++ std::vector 不同于 C malloc。 Malloc'ed space 不是“实例化的”：只有当您触摸内存时才会建立 physical-to-logical 地址映射。这被称为“第一次接触”。这就是为什么在 C-OpenMP 中并行初始化一个数组，以便接触数组部分的套接字获取该部分的页面。在 C++ 中，向量中的“数组”是由单个线程创建的，因此页面在该线程的套接字上结束。

这是一个解决方案：

template<typename T>
struct uninitialized {
  uninitialized() {};
  T val;
  constexpr operator T() const {return val;};
  double operator=( const T&& v ) { val = v; return val; };
};

现在您可以创建一个 vector<uninitialized<double>> 并且数组内存在您显式初始化之前不会被触及：

vector<uninitialized<double>> x(N),y(N);

#pragma omp parallel for
for (int i=0; i<N; i++)
  y[i] = x[i] = 0.;
x[0] = 0; x[N-1] = 1.;

现在，我不确定如果你有一个集合向量会怎样。只是想我会指出这个问题。

Answer 3

经过更多调查，我注意到以下几点：

work-load 集群上的管理器可以并且将会 disregard/reset OMP_PLACES/OMP_PROC_BIND,
内存页面迁移是现代 NUMA 系统上的事情。

在此之后，我开始使用 work-load 经理自己的线程 binding/pinning 系统，并调整我的基准以锁定我的数据所在的内存页面。此外，屈服于我的程序员的偏执狂，我放弃了 std::unique_ptr，因为担心它可能会在分配内存后进行自己的第一次接触。

    // create data which will be shared by multiple threads
    const auto size_per_thread = std::size_t{50 * 1024 * 1024 / sizeof(double)}; // 50 MB
    const auto total_size = thread_count * size_per_thread;
    double* data = nullptr;
    posix_memalign(reinterpret_cast<void**>(&data), sysconf(_SC_PAGESIZE), total_size * sizeof(double));
    if (data == nullptr)
    {
        throw std::runtime_error("could_not_allocate_memory_error");
    }
    
    // perform first touch using thread 0
    #pragma omp parallel num_threads(thread_count)
    {
        if (omp_get_thread_num() == 0)
        {
            #pragma omp simd safelen(8)
            for (auto d_index = std::size_t{}; d_index < total_size; ++d_index)
            {
                data[d_index] = -1.0;
            }
        }
    } // #pragma omp parallel
    mlock(data, total_size); // page migration is a real thing...
    
    // open a parallel section
    auto thread_id_avg_latency = std::multimap<double, int>{};
    auto generator = std::mt19937(); // heavy object can be created outside parallel
    #pragma omp parallel num_threads(thread_count) private(generator)
    {
        // access the data using all threads individually
        #pragma omp for schedule(static, 1)
        for (auto thread_counter = std::size_t{}; thread_counter < thread_count; ++thread_counter)
        {
            // seed each thread's generator
            generator.seed(thread_counter + 1);
            
            // calculate the minimum access latency of this thread
            auto this_thread_avg_latency = 0.0;
            const auto experiment_count = 250;
            for (auto experiment_counter = std::size_t{}; experiment_counter < experiment_count; ++experiment_counter)
            {
                const auto start_timestamp = omp_get_wtime() * 1E+6;
                for (auto counter = std::size_t{}; counter < size_per_thread / 100; ++counter)
                {
                    const auto index = std::uniform_int_distribution<std::size_t>(0, size_per_thread-1)(generator);
                    auto& datapoint = data[thread_counter * size_per_thread + index];
                    datapoint += index;
                }
                const auto end_timestamp = omp_get_wtime() * 1E+6;
                this_thread_avg_latency += end_timestamp - start_timestamp;
            }
            this_thread_avg_latency /= experiment_count;
            #pragma omp critical
            {
                thread_id_avg_latency.insert(std::make_pair(this_thread_avg_latency, omp_get_thread_num()));
            }
        }
    } // #pragma omp parallel
    std::free(data);

有了这些变化，我注意到了我预期的不同。

补充说明：

这个实验表明 non-local 访问的延迟是我正在使用的集群上本地访问的 1.09 - 1.15 倍，
没有可靠的 cross-platform 方法（需要 kernel-APIs），
OpenMP 对线程的编号似乎与 hwloc/lstopo、numactl 和 lscpu 对它们的编号完全相同（逻辑 ID？）

最令人惊讶的是延迟差异非常小，并且可能会发生内存页面迁移，这引出了一个问题，我们为什么要关心 first-touch 和所有其他 NUMA 问题完全没有？

通过实验将OpenMP线程排序到NUMA节点中的问题

Problem of sorting OpenMP threads into NUMA nodes by experiment

c++

multithreading

openmp

affinity

numa