6

現在、 を使用して 2D 配列を表現しようとしていtbb::concurrent_vector<T>ます。この 2 次元配列は、多くの異なるスレッドによってアクセスされるため、並列アクセスを可能な限り効率的に処理する必要があります。

私は2つの解決策を思いつきました：

  • を使用しtbb::concurrent_vector<tbb::concurrent_vector<T> >て保管してください。

  • すべてを a に格納し、tbb::concurrent_vector<T>w/ で要素にアクセスします。x * width + y

1 つの要素にアクセスするために行全体をロックしたくないため、2 番目の要素を好みました (要素にアクセスするためarray[x][y]に tbb 実装はxth 行をロックし、次にyth 要素をロックすると想定しているため)。

どの解決策があなたにとってより良いと思われるか知りたいです。

4

2 に答える 2

5

まず、について混乱があるのではないかと思いますtbb::concurrent_vector。std::vectorこのコンテナは、スレッドセーフなサイズ変更と似ていますが、内部ストレージレイアウトのため、要素へのアクセスが遅くなります。

あなたはここでそれについてもっと読むことができます。

あなたの場合、あなたが提案した2番目の解決策（x * width + yインデックス付きの1D配列）のために、私はあなたのアルゴリズムが配列の集中的なマルチスレッドのサイズ変更を含まないと仮定しています。tbb::concurrent_vectorしたがって、のようなシングルスレッドコンテナと比較してもメリットはありませんstd::vector。

スレッドセーフな要素アクセスが保証されていると想定していたと思いますがtbb::concurrent_vector、そうではありません-docからの引用：tbb::concurrent_vector::operator[]

指定されたインデックスの要素への参照を取得します。

このメソッドは、呼び出し元のスレッドがそのインデックスをチェックしている限り、同時読み取りに対して、またベクターの拡張中にスレッドセーフです。

配列のサイズを変更しない場合は、最初の部分であるスレッドセーフな同時読み取りのみに関心があります。しかし、std::vectorまたは生のC配列でも同じことができます。一方、どちらもスレッドセーフな任意のアクセス（読み取り/書き込み要素）を提供しません。

ロックを使用して実装するか、これを実行する別のライブラリを見つける必要があります（おそらくstd::vector、STLPortからですが、よくわかりません）。これは非常に非効率的ですが、2D配列から要素にアクセスするたびに、スレッド同期のオーバーヘッドが発生するためです。正確に何を実装しようとしているのかはわかりませんが、同期に実際の計算よりも時間がかかる可能性があります。

質問に答えるために、シングルスレッド設定でも、ND配列を表すために1D配列を使用することをお勧めします。これは、インデックス（x * width + y）の計算が、真のND配列に必要な追加のメモリアクセスよりも高速であるためです。 。同時ベクトルの場合、これはさらに当てはまります。これは、最良のシナリオ（競合する行アクセスがない）では2倍のロックオーバーヘッドがあり、競合がある場合はさらに多くのオーバーヘッドが発生するためです。

したがって、あなたが提案した2つのソリューションのうち、私は躊躇せずに2番目のソリューションを選択しtbb::concurrent_vectorます。要素にアクセスするための適切なロックを備えた1D配列（必須ではありません）です。

アルゴリズムとさまざまなスレッドによるアクセスパターンに応じて、画像編集ソフトウェア（gimp、photoshop ...）で使用される別のアプローチはタイルベースです。

template<typename T> struct Tile {
    int offsetX, int offsetY;
    int width, height;
    Not_ThreadSafe_Vector<T> data;
};
ThreadSafe_Vector< Tile<T> > data

Not_ThreadSafe_Vector要素のアクセスをロックしないコンテナはどこにありますかstd::vector。ThreadSafe_Vectorスレッドセーフな読み取り/書き込み要素アクセスを備えたコンテナです（！ではありませんtbb::concurrent_vector）。このように、アクセスパターンにある程度の局所性がある場合（スレッドは、遠くよりも前のアクセスに近い要素にアクセスする可能性が高い）、各スレッドは、ほとんどの単一タイルからのデータを処理するように作成できます。時間、そして別のタイルに切り替えるときだけ同期オーバーヘッドがあります。

于 2011-11-10T10:15:43.940 に答える
-2

tbb::concurrent_vector要素へのアクセス (読み取り、書き込み、アドレスの取得) およびベクターの拡張に関して完全にスレッドセーフです。Intel の従業員である Arch D. Robison からの回答は、こちら で確認してください。

ただし、ベクトルをクリアまたは破棄する操作はスレッドセーフではありません ($6.2.1 Intel TBB Tutorial pdf ドキュメントを参照してください)。つまり、 でclear()他の操作が進行中の場合は呼び出さないでくださいtbb::concurrent_vector。

Antoine が述べたように、ND 配列を 1D 配列として扱うことは、効率とパフォーマンスのために常に優先されます。

于 2018-11-03T06:31:48.100 に答える