1

100000 x 100000のような巨大なバイナリ マトリックスがあります。

この記事http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdfを読んで、バイナリマトリックスを記憶して操作するための最良のトレードオフはboost::dynamic_bitsetsを使用することであることを理解したようです。

「表 2: データ構造を実装したプログラムの相対時間パフォーマンス」では、 std :: vector<bool>が最後の位置にあり、boost::dynamic_bitsetが最初の位置にあります。

また、「表 3: データ構造を実装したプログラムの相対的なメモリ使用量」では、 std ::vector<bool>が最初の位置にありますが、boost::dynamic_bitsetは 2 番目の位置にあります。

また、論文の7ページ目に次のような記述があります。

「std::vector の印象的なメモリ パフォーマンスにもかかわらず、その悲惨な時間パフォーマンスにより、大規模なアプリケーションでは使用できなくなります。」

そして結論では：

「boost::dynamic_bitset は、実行速度の点で他のほとんどの実装よりもかなり効率的であることを示しましたが、std::vector<char> を使用した実装は、メモリ効率の点で他の実装よりも優れていました。」

私の場合、ターゲットマシンはXEON PHIです。
私のターゲット アプリケーションはGame Of Lifeです。
バイナリ行列を ROWS x COLS セルのバイナリ配列として表現しました。

-O3最適化フラグを指定したicpcコンパイラを使用して、3 つの異なる構成でコードを試しました。

  1. ブール値の配列
  2. ブール値の配列 + ベクトル化、つまり、ここで説明されているように配列表記を使用してコードを変更します

  3. boost::dynamic_bitsets . この場合、配列表記を使用してコードを変更できませんでした。試行すると、次のエラーが発生するためです。

    error: base of array section must be pointer or array type

    std::vector<bool>を使用した場合と同じエラー。

100000 x 100000 サイズのマトリックスのゲーム メイン ループの 1 回だけの反復のパフォーマンスを調べると、ソリューション 2はソリューション 1よりもほぼ 6 倍高速に動作することがわかりましたが、予想外にソリューション 1はソリューション 3よりも 2 倍高速に動作します。

結論として、次の質問をする必要があります。

  1. 一般に、HUGE MATRIXを格納/操作するための最も効率的なデータ構造は何ですか?
  2. ターゲット マシンがXEON PHIであることを知っていれば、 「1 に答える」よりもうまくできるでしょうか?
  3. vector<bool>またはboost::dynamic_bitsetsにベクトル化を適用することは可能ですか?

特定のターゲット アプリケーションである Game Of Life について回答していただきありがとうございます。
しかし、他のコンテキストで巨大なバイナリ マトリックスを操作する場合はどうでしょうか。

4

1 に答える 1