1

インデックス テーブルからの順序を維持する選択は、シリアル コードでは簡単ですが、マルチスレッドでは、特にリンク リストを回避することによって効率 (マルチスレッドの要点) を維持したい場合は、それほど単純ではありません。シリアルコードを考える

template<typename T>
std::vector<T> select_in_order(
  std::vector<std::size_t> const&keys, // permutation of 0 ... key.size()-1
  std::vector<T> const&data)           // anything copyable
{ // select data[keys[i]] allowing keys.size() >= data.size()
  std::vector<T> result;
  for(auto key:keys)
    if(key<data.size())
      result.push_back(data[key]);
  return result;
}

これをマルチスレッド化するにはどうすればよいdata.size() < key.size()ですか(TBB や OpenMP を使用するなど)。

4

2 に答える 2

3

探している並列計算操作はStream Compactionと呼ばれます。

ストリーム圧縮

アルゴリズムは自明ではありませんが、並行して効率的に実装できます。Thrustなど、すでに実装されているライブラリを使用することをお勧めします。ただし、本当に自分で実装したい場合は、GPU プログラミングの第 39.3.1 章、またはUdacity の並列プログラミング入門コース、レッスン 4.5でアルゴリズムの説明を見つけることができます。

基本的に、配列のブール述語を定義し（例ではkey<data.size()）、それを別の配列にマッピングし、述語配列をスキャンしてからScatterを実行します。

Map()Scatter()並行して簡単に実装できます。の実装はScan()重要な部分です。ほとんどの並列ライブラリにはScan()実装があります。そうでない場合は、上記のリンクの両方で、いくつかの並列スキャン アルゴリズムについて説明しています。

これはすべて、GPU のように多くのコアがあることを前提としています。CPU では、シリアルで実行する方がおそらく高速です。または、配列を大きなチャンクに分割し、チャンクを連続して(異なるコアで並列に)処理し、結果をマージして戻します。どちらのアプローチが最適かは、データによって異なります(ほとんどのキーが最終的な配列にあると予想される場合は、前者の方がうまく機能します)。

于 2013-06-13T16:12:58.623 に答える
2

スレッド間でキーを分割します。たとえば、N スレッドの場合、T1 にキー {0, key.size() / N - 1} を与え、T2 はキー {key.size() / N, 2 * key.size( ) / N - 1} など、TN はキー {(N - 1) / N * keys.size(), keys.size() - 1} を取得します。各スレッドはその結果をスレッド ローカル コンテナーに格納し、スレッドが終了したらコンテナーをマージします。この方法では、スレッド間の同期を実行する必要はありません。

T2 のリストを T1 のリストに追加するのは簡単なので、コンテナを結合する最も効率的な方法は、コンテナをリンク リストにすることです。ただし、あなたが言ったように、リンクされたリストはうまく並列化できないため、避けることをお勧めします。

もう 1 つのオプションは、各スレッドがその結果をスレッド ローカル配列に格納し、スレッドが完了したときにこれらの配列をマージすることです。このマージを並行して実行できます (各スレッドの結果のサイズは T{N}results.size() です。最終的なマージ配列 が与えられるfinal_resultsと、T1 はそのデータをfinal_results[0, T1results.size()-1]にマージし、T2 はそのデータをfinal_results[T1results.size(), T1results.size() + T2results.size()-1]にマージし、T3 はその結果を にマージしますfinal_results[T1results.size() + T2results.size(), T1results.size() + T2results.size + T3results.size()-1]。 ）。

もう 1 つのオプションは、TBB からの共有のconcurrent_hash_mapkeyをキーおよびdata[key]値として使用することです。

于 2013-06-13T15:00:51.707 に答える