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));
}

アトミック float はロックフリーではないように見えるため、int に float 値を入れる際に定型句がいくつかあります。私はメモリの順序について 100% 使用しているわけではありませんが、非アトミック メモリが関与していないため、最も制限の少ないレベル 'relaxed' で問題ないようです。

于 2013-02-19T15:10:59.993 に答える
1

2セントを追加するだけで、よりきめ細かい最適化を開始する前に、次の必要性を排除するアプローチを試してみます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 に答える
1

構文についてはわかりませんが、アルゴリズム的には、次の 3 つの選択肢があります。

  1. ベクトル全体をロックダウンして、アトミックアクセスを保証します (これは現在行っていることです)。

  2. 個々の要素をロックダウンして、すべての要素を他の要素とは独立して更新できるようにします。長所: 最大の並列処理。短所：たくさんのロックが必要！

  3. その中間の何か！次のように、ベクトルを 16 (または 32/64/...) の「バンク」に分割することを概念的に考えます: bank0 はベクトル要素 0、16、32、48、64 で構成されます。 , 33, 49, 65, ... bank2 はベクトル要素 2, 18, 34, 50, 66, ... ... で構成されています。ここで、要素にアクセスする前に 16 の明示的なロックを使用します。並列性。要素 n にアクセスするには、ロック (n%16) を取得し、アクセスを終了してから、同じロックを解放します。

于 2013-02-18T11:26:25.643 に答える
1

たとえば、長さ 128 のa std::vector<std::mutex>(または) を宣言してから、 th 要素を使用してロック オブジェクトを作成するのはどうでしょうか。boost::mutexj

つまり、次のようなものです。

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 に答える