5

有没有办法使用原子操作从多个线程更新最大值？

说明性示例：

std::vector<float> coord_max(128);
#pragma omp parallel for
for (int i = 0; i < limit; ++i) {
    int j = get_coord(i); // can return any value in range [0,128)
    float x = compute_value(j, i);
    #pragma omp critical (coord_max_update)
    coord_max[j] = std::max(coord_max[j], x);
}

在上述情况下，临界区同步访问整个向量，而我们只需要独立同步访问每个值。

4

4 回答 4

6

根据评论中的建议，我找到了一个不需要锁定的解决方案，而是使用 std::atomic / boost::atomic 中的比较和交换功能。我仅限于 C++03，所以在这种情况下我会使用 boost::atomic。

BOOST_STATIC_ASSERT(sizeof(int) == sizeof(float));
union FloatPun { float f; int i; };

std::vector< boost::atomic<int> > coord_max(128);
#pragma omp parallel for
for (int i = 0; i < limit; ++i) {
    int j = get_coord(i);
    FloatPun x, maxval;
    x.f = compute_value(j, i);

    maxval.i = coord_max[j].load(boost::memory_order_relaxed);
    do {
        if (maxval.f >= x.f) break;
    } while (!coord_max[j].compare_exchange_weak(maxval.i, x.i,
        boost::memory_order_relaxed));
}

将浮点值放入整数中涉及一些样板，因为原子浮点数似乎不是无锁的。我不是 100% 使用内存顺序，但限制最少的“放松”级别似乎没问题，因为不涉及非原子内存。

于 2013-02-19T15:10:59.993 回答
1

比如说，声明一个长度为 128 的std::vector<std::mutex>（或boost::mutex）然后使用第jth 个元素创建一个锁对象怎么样？

我的意思是，类似：

std::vector<float> coord_max(128);
std::vector<std::mutex> coord_mutex(128); 
#pragma omp parallel for
for (int i = 0; i < limit; ++i) {
    int j = get_coord(i); // can return any value in range [0,128)
    float x = compute_value(j, i);
    std::scoped_lock lock(coord_mutex[j]);
    coord_max[j] = std::max(coord_max[j], x);     
}

或者，根据Rahul Banerjee 的建议 #3：

std::vector<float> coord_max(128);
const int parallelism = 16;
std::vector<std::mutex> coord_mutex(parallelism); 
#pragma omp parallel for
for (int i = 0; i < limit; ++i) {
    int j = get_coord(i); // can return any value in range [0,128)
    float x = compute_value(j, i);
    std::scoped_lock lock(coord_mutex[j % parallelism]);
    coord_max[j] = std::max(coord_max[j], x);     
}
于 2013-02-18T11:23:28.860 回答
1

不确定语法，但从算法上讲，您有三个选择：

  1. 锁定整个向量以保证原子访问（这是您当前正在做的）。

  2. 锁定单个元素，以便每个元素都可以独立于其他元素进行更新。优点：最大并行度；缺点：需要很多锁！

  3. 中间的东西！从概念上考虑将向量划分为 16 个（或 32/64/...）“banks”，如下所示：bank0 由向量元素 0、16、32、48、64 组成，...bank1 由向量元素 1、17 组成, 33, 49, 65, ... bank2 由向量元素 2, 18, 34, 50, 66, ... ... 现在，在访问元素之前使用 16 个显式锁，您最多可以有 16 路并行性。要访问元素 n，请获取锁 (n%16)，完成访问，然后释放相同的锁。

于 2013-02-18T11:26:25.643 回答
1

只是为了增加我的两分钱，在开始更细粒度的优化之前，我会尝试以下方法来消除对omp critical：

std::vector<float> coord_max(128);  
float              fbuffer(0);
#pragma omp parallel 
{
  std::vector<float> thread_local_buffer(128);  

  // Assume limit is a really big number
  #pragma omp for       
  for (int ii = 0; ii < limit; ++ii) {
   int  jj = get_coord(ii); // can return any value in range [0,128)
   float x = compute_value(jj,ii);
   thread_local_buffer[jj] = std::max(thread_local_buffer[jj], x);
  } 
  // At this point each thread has a partial local vector
  // containing the maximum of the part of the problem 
  // it has explored

  // Reduce the results
  for( int ii = 0; ii < 128; ii++){
    // Find the max for position ii
#pragma omp for schedule(static,1) reduction(max:fbuffer)
    for( int jj = 0; jj < omp_get_thread_num(); jj++) {
      fbuffer = thread_local_buffer[ii];
    } // Barrier implied here
    // Write it in the vector at correct position
#pragma omp single
    {
      coord_max[ii] = fbuffer;
      fbuffer = 0;
    } // Barrier implied here

  }
}

请注意，我没有编译该片段，因此我可能在其中留下了一些语法错误。无论如何，我希望我已经传达了这个想法。

于 2013-02-18T14:23:25.853 回答