使用OpenMP在不使用关键部分的情况下并行填充直方图（数组缩减）

Question

我希望使用OpenMP并行地填充直方图。我已经用C/C++实现了两种不同的OpenMP方法。

第一种方法proccess_data_v1为每个线程创建一个私有直方图变量hist_private，在并行环境下填充它们，然后在critical部分中将私有直方图总和到共享直方图hist中。

第二种方法proccess_data_v2创建了一个大小等于线程数的共享直方图数组，并在并行环境下填充该数组，然后并行地对共享直方图hist进行求和。

对我来说，第二种方法似乎更好，因为它避免了关键部分，并且可以并行地对直方图进行求和。但是，它需要知道线程数并调用omp_get_thread_num()。我通常尽量避免这样做。有没有更好的方法可以在不引用线程号并使用大小等于线程数的共享数组的情况下执行第二种方法？

void proccess_data_v1(float *data, int *hist, const int n, const int nbins, float max) {
    #pragma omp parallel 
    {
        int *hist_private = new int[nbins];
        for(int i=0; i<nbins; i++) hist_private[i] = 0;
        #pragma omp for nowait
        for(int i=0; i<n; i++) {
            float x = reconstruct_data(data[i]);
            fill_hist(hist_private, nbins, max, x);
        }
        #pragma omp critical 
        {
            for(int i=0; i<nbins; i++) {
                hist[i] += hist_private[i];
            }
        }
        delete[] hist_private;
    }
}

void proccess_data_v2(float *data, int *hist, const int n, const int nbins, float max) {
    const int nthreads = 8;
    omp_set_num_threads(nthreads);
    int *hista = new int[nbins*nthreads];
    
    #pragma omp parallel 
    {
        const int ithread = omp_get_thread_num();
        for(int i=0; i<nbins; i++) hista[nbins*ithread+i] = 0;
        #pragma omp for
        for(int i=0; i<n; i++) {
            float x = reconstruct_data(data[i]);
            fill_hist(&hista[nbins*ithread], nbins, max, x);
        }

        #pragma omp for
        for(int i=0; i<nbins; i++) {
            for(int t=0; t<nthreads; t++) {
                hist[i] += hista[nbins*t + i];
            }
        }
        
    }
    delete[] hista;
}

基于 @HristoIliev 的建议，我创建了一个名为 process_data_v3 的改进方法：

#define ROUND_DOWN(x, s) ((x) & ~((s)-1))
void proccess_data_v2(float *data, int *hist, const int n, const int nbins, float max) {
    int* hista;
    #pragma omp parallel 
    {
        const int nthreads = omp_get_num_threads();
        const int ithread = omp_get_thread_num();
        
        int lda = ROUND_DOWN(nbins+1023, 1024);  //1024 ints = 4096 bytes -> round to a multiple of page size
        #pragma omp single
        hista = (int*)_mm_malloc(lda*sizeof(int)*nthreads, 4096);  //align memory to page size

        for(int i=0; i<nbins; i++) hista[lda*ithread+i] = 0;
        #pragma omp for
        for(int i=0; i<n; i++) {
            float x = reconstruct_data(data[i]);
            fill_hist(&hista[lda*ithread], nbins, max, x);
        }

        #pragma omp for
        for(int i=0; i<nbins; i++) {
            for(int t=0; t<nthreads; t++) {
                hist[i] += hista[lda*t + i];
            }
        }

    }
    _mm_free(hista);
}

- user2088790

---

请问您为什么要使用嵌套并行区域呢？（我指的是您的process_data_v1方法）。也许我没有理解到什么地方，但根据您的代码，我觉得您正在请求Nthreads ** 2。也就是说，您正在请求比可用资源更多的资源。这是正确的吗？换句话说，您能否解释一下外部并行区域内部的并行区域的行为？谢谢... - Alejandro

嗨@user2088790，proccess_data_v1不是最快的吗？因为我们不需要共享内存。我尝试了版本2和3，它们比v1慢。有什么建议吗？ - Ardian

Answer 1

您可以在并行区域内分配大数组，这里您可以查询实际使用的线程数：

int *hista;
#pragma omp parallel 
{
    const int nthreads = omp_get_num_threads();
    const int ithread = omp_get_thread_num();

    #pragma omp single
    hista = new int[nbins*nthreads];

    ...
}
delete[] hista;

为了获得更好的性能，建议你将hista中每个线程块的大小舍入为系统内存页大小的倍数，即使这可能会在不同部分直方图之间留下空洞。这样可以防止NUMA系统上的虚假共享和远程内存访问（但在最终减少阶段不会出现此情况）。

- Hristo Iliev

---

谢谢。我实现了你的建议，这绝对是一个更好的解决方案。我需要阅读有关页面大小的信息。我认为确保hista中的块是缓存行大小（64字节）的倍数就足以防止虚假共享。例如，如果nbins是64的倍数（并且hista的地址也是64的倍数），这样不会防止虚假共享吗？ - user2088790

@Hristolliev，我按照你的建议添加了一些代码。我将块大小称为lda，并使其成为64的倍数。我应该使用不同的值吗？例如4KB = 页面大小？ - user2088790

如果不在页面边界上，则还需对齐缓存行边界，否则即使具有正确大小的块也可能导致虚假共享。 - Hristo Iliev

@Hristolliev，我稍微了解了一下NUMA系统（特别是您在https://dev59.com/7Ggv5IYBdhLWcg3wF89P的评论）。我更新了代码，将块大小设置为4096字节。我需要学习更多关于NUMA系统的知识。当您私有地分配内存（例如在process_data_v1中），是否保证在不同的页面中进行分配（如果线程在不同的CPU上）？如果我们将内存分配为共享但不必须执行此操作，则是否需要手动完成此操作？也许我应该在SO上提出这个问题。 - user2088790

这真的取决于所使用的内存管理器。例如，在某些发行版中，glibc 配置为使用每个线程的区域，并且每个线程都有自己的堆空间。较大的分配通常被实现为匿名的 mmap，因此总是获得新鲜页面。但是，无论哪个线程分配了内存都没有关系。重要的是哪个线程首先触摸到每个特定页面 - Linux 上当前的 NUMA 策略是“首次触摸”，即物理内存页面来自于第一次触摸该页面的代码所在的 NUMA 节点。 - Hristo Iliev