16

問題の約半分を「事前計算」し、この情報をファイルに保存し、それを何度も再利用して問題のさまざまな「インスタンス」を計算できるという利点がある数学の問題に取り組んでいます。問題は、実際の問題を解決するためにこのすべての情報をアップロードすることが大きなボトルネックになることです。

より具体的には、膨大な量の情報 (大量の確率 ( long double)、大量の など) を事前に計算し、std::map<int,int>これらすべてをディスク (数 Gb) に保存できます。

プログラムの後半は、入力引数Dを受け入れます。Dごとに、事前に計算されたデータ (ファイルから) とDに固有のその他のデータの組み合わせを含む非常に多くの計算を実行する必要があります(そのため、問題はDごとに異なります)。

ファイルから事前に計算された情報の特定の部分を選択する必要がある場合があります。また、(大きな) ファイルからすべてのデータをアップロードする必要がある場合もあります。

IO を高速化するための戦略はありますか?

boost::mpi他の理由で既にプログラムを並列化 (MPI、経由) していますが、ディスク上のファイルにアクセスすると、計算時間が耐えられなくなります。

戦略や最適化はありますか?

現在、私はすべてをcstdio、つまり noで行っていますiostream。それは大きな違いを生むでしょうか？

4

10 に答える 10

14

確かに、最速の（しかし最も脆弱な）解決策はmmap、固定アドレスへのデータです。すべてを1つの大きなものに叩きつけ、構造体の最後に接続されたブロックに割り当てるアロケータを使用してstructインスタンス化します。std:::map単純ではありませんが、高速になります。への1回の呼び出しmmapで、データは（仮想）メモリにあります。また、でアドレスを強制しているのでmmap、ポインタなどを保存することもできます。

上記のように、かなりの量の作業を必要とすることに加えて、それは壊れやすいです。アプリケーションを再コンパイルすると、ターゲットアドレスが使用できないか、レイアウトが異なる可能性があります。しかし、これは実際には単なる最適化であるため、これは問題ではない可能性があります。互換性の問題が発生した場合は、古いファイルを削除して最初からやり直してください。互換性を壊す変更後の最初の実行は非常に遅くなりますが、互換性をあまり頻繁に壊さない場合は...

于 2012-04-05T14:45:12.807 に答える
6

地図にないものは簡単です。既知のメモリの連続した 1 つのチャンク (大きな配列、またはポインターのない構造体/クラスなど) にすべてを配置し、それを使用write()して書き出します。後でread()、1 回の操作でそれを読み込むために使用します。サイズが異なる可能性がある場合は、1 つの操作を使用intしてそのサイズのシングルを読み取り、メモリを割り当ててから、シングルread()を使用してそれを取り込みます。

マップの部分は、1 回の操作ですべてを実行できないため、少し難しくなります。ここでは、シリアル化するための規則を考え出す必要があります。I/O をできるだけ速くするための最善の策は、マップから、すべてが 1 つの場所にあるインメモリ形式に変換することです。これにより、マップに簡単かつ迅速に戻すことができます。たとえば、キーが int で、値が一定サイズの場合、キーの配列と値の配列を作成し、キーを一方の配列にコピーし、値を他方の配列にコピーしてからwrite()、2 つの配列をコピーできます。おそらくサイズも書き出すでしょう。繰り返しますが、 を 2 ～ 3 回呼び出すだけで内容を読み取りますread()。

ASCII に変換されたものは何もなく、システム コールの数は最小限であることに注意してください。このファイルは人間が読めるものではありませんが、コンパクトで読み込みが高速です。I/O を遅くする原因は次の 3 つです。2) ASCII との間の変換 (printf、scanf)。3) ディスク速度。3) (SSD 以外) については、多くのことを行うのは困難です。バックグラウンド スレッドで読み取りを行うことができますが、データが入るのをブロックして待機する必要がある場合があります。

于 2012-04-05T14:34:00.997 に答える
4

いくつかのガイドライン:

  • read() への複数回の呼び出しは、単一の呼び出しよりも高価です
  • バイナリ ファイルはテキスト ファイルよりも高速です
  • "multiple" の値が大きい場合、1 つのファイルは複数のファイルよりも高速です。
  • 可能であればメモリ マップト ファイルを使用する
  • 64ビットOSを使用して、OSがメモリを管理できるようにします

理想的には、すべての long double をメモリ マップ ファイルに入れ、すべてのマップをバイナリ ファイルに入れようとします。

分割統治: 64 ビットが選択肢にない場合は、すべてのチャンクが一緒に使用されることがないように、データを大きなチャンクに分割し、必要なときにチャンク全体が必要になるようにします。このようにして、必要なときにチャンクをロードし、そうでないときに破棄することができます。

于 2012-04-05T14:54:50.537 に答える
3

データ全体を RAM にアップロードするこれらの提案は、次の 2 つの条件が満たされている場合に有効です。

  1. 実行中のすべての I/O 時間の合計は、すべてのデータを RAM にロードするコストをはるかに上回っています
  2. アプリケーションの実行中に、全データの比較的大きな部分がアクセスされている

(これらは通常、一部のアプリケーションが異なるデータを処理するために長時間実行されている場合に発生します)

ただし、他のケースでは、他のオプションが考慮される場合があります。たとえば、アクセス パターンが本当にランダムかどうかを理解することが不可欠です。いいえの場合は、データの並べ替えを検討して、一緒にアクセスできるアイテムが互いに近くにあることを確認してください。これにより、OS キャッシュが最適な状態で実行され、HDD のシーク時間も短縮されます (もちろん SSD の場合ではありません)。

アクセスが完全にランダムで、アプリケーションが 1 回のデータ読み込みコストを償却するのに必要なだけ実行されていない場合、たとえば、このデータ マネージャーを別のモジュールに抽出して、このデータをプリロードしたままにするなど、アーキテクチャを調べます。

Windows の場合はシステム サービスである可能性があり、他の OS の場合は他のオプションが利用可能です。

于 2012-04-05T14:58:19.630 に答える
2

キャッシュ、キャッシュ、キャッシュ。数 GB しかない場合は、memcached などにすべてのデータではないにしても、ほとんどのデータをキャッシュすることが可能です。これは、同じマシン上の複数のプロセッサだけでなく、複数のマシンで MPI を使用している場合に特に優れたソリューションです。

すべてが同じマシン上で実行されている場合、使用可能なメモリがあれば、共有メモリ キャッシュを検討してください。

また、ファイルの書き込みが別のスレッドで行われていることを確認してください。ファイルが書き込まれるのを待っているプロセス全体をブロックする必要はありません。

于 2012-04-05T14:33:28.363 に答える
1

言われたように、あなたがメモリにできる限り多くをキャッシュします。

キャッシュする必要のある量がメモリの許容量よりも多い場合は、仮想メモリページをディスクにスワップする必要がある場合によく行われる方法で、メモリとディスクの間でキャッシュをスワップアウトしてみてください。それは本質的に同じ問題です。

一般的な方法の1つは、スワップされるページを決定するための最も最近使用されていないアルゴリズムです。

于 2012-04-05T14:39:19.147 に答える
1

実際には、使用可能なメモリの量とアクセス パターンによって異なります。

最も簡単な解決策は、メモリ マップ ファイルを使用することです。これには通常、オブジェクトがメモリ内にあるかのようにファイルがレイアウトされている必要があるため、ポインターを使用せずに POD データのみを使用する必要があります (ただし、相対インデックスを使用することはできます)。

アクセス パターンを調べて、一緒に使用されることが多い値をグループ化できるかどうかを確認する必要があります。これは、OS がこれらの値をより適切にキャッシュするのに役立ちます (つまり、常にディスクにアクセスして読み取るのではなく、それらをメモリに保持します)。

別のオプションは、できれば論理的な方法で、ファイルをいくつかのチャンクに分割することです。値の範囲をそれらを含むファイルにマップするインデックス ファイルを作成する必要がある場合があります。

その後、必要なファイルのセットにのみアクセスできます。

最後に、複雑なデータ構造 (メモリ マップされたファイルが失敗する場合) または疎な読み取り (特定のファイルから小さな情報のみを抽出する場合) については、LRU キャッシュについて読むと興味深いかもしれません。

アイデアは、シリアライゼーションと圧縮を使用することです。インデックスを含むいくつかのファイルを作成し、それらすべてを圧縮 (zip) します。次に、起動時に、インデックスをロードしてメモリに保存することから始めます。

値にアクセスする必要があるときはいつでも、最初にキャッシュを試します。そうでない場合は、それを含むファイルにアクセスし、メモリで解凍し、その内容をキャッシュにダンプします。注: キャッシュが小さすぎる場合は、何をダンプするかを慎重にするか、ファイルのサイズを小さくする必要があります。

頻繁にアクセスされる値はキャッシュに保持され、不要なラウンドトリップが回避されます。また、ファイルが圧縮されているため、IO が少なくなります。

于 2012-04-05T16:25:37.087 に答える
0

キャッシュが効果的になるようにデータを構造化します。たとえば、「特定の部分」を読んでいるときに、それらがすべて連続している場合は、それらすべてを収集するためにディスクの周りを探す必要はありません。

ディスクアクセスを別のプロセスと共有している場合は、レコードごとではなく、バッチでの読み取りと書き込みが役立ちます。

于 2012-04-05T14:36:40.420 に答える
0

より具体的には、膨大な量の情報 (大量の確率 (long double)、大量の std::map など) を事前に計算し、これらすべてをディスク (数 Gb) に保存できます。

私が理解している限り、std::mapこれらも事前に計算されており、挿入/削除操作はありません。検索のみ。マップをstd::hash_mapやsparsehashのようなものに置き換えるというアイデアはどうですか。理論的には、パフォーマンスを向上させることができます。

于 2012-04-05T16:52:14.500 に答える
0

より具体的には、膨大な量の情報 (大量の確率 (long double)、大量の std::map など) を事前に計算し、これらすべてをディスク (数 Gb) に保存できます。

車輪を再発明しないでください。berkeley db などのキー値データ ストアを使用することをお勧めします: http://docs.oracle.com/cd/E17076_02/html/gsg/C/concepts.html

これにより、ファイルの保存と共有、実際によく使用する部分のキャッシュ、その他の部分のディスクへの保持が可能になります。

于 2012-04-05T20:08:54.813 に答える