与OpenMP并行填充直方图（减少数组），而无需使用关键部分

Question

我想使用OpenMP并行填充直方图。我想出了两种使用C / C ++中的OpenMP进行此操作的方法。第一种方法为每个线程proccess_data_v1创建一个私有直方图变量hist_private，将其填充成小节，然后将私有直方图求和成hist一个critical部分中的共享直方图。第二种方法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;}

Answer 1

我创建了一种改进的方法，称为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);

}

Answer 2

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

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系统上进行错误共享，又可以防止对远程内存的访问（但不能在最后的还原阶段）。

Answer 3

这实际上取决于所使用的内存管理器。例如，在某些发行版中，glibc配置为使用每个线程的竞技场，并且每个线程都有自己的堆空间。较大的分配通常实现为匿名mmap，因此总是获得新的页面。但是，哪个线程分配了内存并不重要。哪个胎面首先接触每个特定页面很重要-Linux上当前的NUMA策略是“首次接触”，即物理内存页面来自NUMA节点，在该节点中，第一次接触该页面的代码在此运行。