c - 使用原子操作更新 double 数组

Question

我一直在尝试使用 OpenMP 以并行方式在 double 组中写入(更新)。这个想法是，需要更新的元素可以更新不止一次，并且元素本身是即时计算的。这使得它很容易出现竞争条件，除非我“锁定”与正在使用原子操作更新的元素相对应的内存区域。如下例:

#include<omp.h>
#include<stdlib.h>

int main()
{

    double *x=NULL, contribution = 1234.5;
    size_t xlen=1000, i, n;

    if ( (x = (double *) calloc(xlen,sizeof(double)) ) == NULL) exit(-1)

    #pragma omp parallel for shared(x) private(n,contribution)
    for (i=0; i<xlen; i++) {
        n = find_n_on_the_fly(i);

        #pragma omp atomic update
        x[n]+=contribution; // in the more complicated case contributions are different

    }

    return 0;
}

我仍然使用这种方法遇到竞争条件。我尝试使用关键部分，但它完全杀死了我，因为数组很大而且更新次数也很大。

问题:这种方法有什么问题？有没有更好的方法来处理这个问题？

注意:为了处理这个问题，我做了一些愚蠢的事情，为每个线程创建数组的副本并在以后减少它们。但内存限制不允许我走得更远。

Answer 1

对我来说，上面的代码似乎很有效。

但是，您有两种改进方法:

1- 使用名为 _mm_malloc 的内存分配函数，将缓存行大小作为输入之一，而不是您使用的 calloc。你现在面临的最大问题是虚假分享。为了忽略 FS 的影响，通过使用上述方法，您基本上是在强制底层库以每个元素都驻留在高速缓存的一行中的方式分配内存(或您的数组)。这样，线程就不会争夺缓存行来检索两个不同的互变量。换句话说，它将阻止在高速缓存行中分配两个变量。这将提高多线程程序的性能。谷歌 _mm_malloc 了解更多信息。但是，以下是基本用法。在大多数现代计算机中，缓存行是 64。

#if defined(__INTEL_COMPILER) 
#include <malloc.h> 
#else 
#include <mm_malloc.h> 
#endif 

int CPU_Cache_line_size = 64;

int xlen = 100;
double *ptr = _mm_malloc(xlen*sizeof(double), CPU_Cache_line_size); 
/*
  do something ...
*/
_mm_free(ptr); 

__CPU_CACHE_LINE_SIZE__可以通过以下方式查询您的系统:

• Linux 命令:

  getconf LEVEL1_DCACHE_LINESIZE

• 以编程方式:

  int CPU_Cache_line_size = sysconf (_SC_LEVEL1_DCACHE_LINESIZE);

• 关于缓存的详细信息:

  /sys/devices/system/cpu/cpu0/cache/

2- 您自己提到了这一点，但对您的情况来说限制很严重:每个线程使用一个数组，然后减少它们。这种方法效率更高。如果可以，再次考虑使用这种方法。