8

私は、既存のシングル スレッド モンテカルロ シミュレーションを使用して最適化する任務を負っています。これは ac# コンソール アプリです。db アクセスはありません。データは csv ファイルから 1 回読み込まれ、最後に書き出されます。そのため、ほとんど CPU バウンドであり、約 50 MB のメモリしか使用しません。

Jetbrains dotTrace プロファイラーで実行しました。合計実行時間の約 30% が一様乱数の生成であり、24% が一様乱数から正規分布乱数への変換です。

基本的なアルゴリズムは、多数のネストされた for ループであり、中心に乱数呼び出しと行列乗算があり、各反復は double を返し、結果リストに追加されます。このリストは定期的にソートされ、いくつかの収束基準についてテストされます (チェック時)。総反復回数の 5% ごとにポイントします) 許容できる場合、プログラムはループから抜け出し、結果を書き込みます。そうでない場合は、最後に進みます。

開発者に検討してもらいたい:

  • 新しい Thread v ThreadPoolを使用する必要がありますか
  • Microsoft Parallels Extension ライブラリを確認する必要があります
  • AForge.Net Parallel.For、http://code.google.com/p/aforge/他のライブラリを見る必要がありますか?

並列コードやマルチスレッド コードを書いたことがないので、上記のチュートリアルへのリンクは大歓迎です。

  • 大量の正規分布乱数を生成し、それらを消費するための最良の戦略。一様乱数は、アプリによってこの状態で使用されることはなく、常に正規分布に変換されてから消費されます。
  • 乱数生成のための優れた高速ライブラリ (並列?)
  • このパラレルを使用する際のメモリの考慮事項、必要な追加の量。

現在のアプリは 500,000 回の反復に 2 時間かかります。ビジネスではこれを 3,000,000 回の反復にスケーリングし、1 日に複数回呼び出す必要があるため、かなりの最適化が必要です。

特に、Microsoft Parallels ExtensionまたはAForge.Net Parallelを使用したことのある方からのご意見をお待ちしております

これはかなり迅速に製品化する必要があるため、.net 4 ベータ版は公開されていますが、同時実行ライブラリが組み込まれていることはわかっています。.net 4 がリリースされたら、後でトラックに移行することを検討できます。今のところ、サーバーには .Net 2 があり、私の開発ボックスにある .net 3.5 SP1 へのアップグレードを審査のために提出しました。

ありがとう

アップデート

Parallel.For の実装を試してみましたが、奇妙な結果が得られました。シングルスレッド:

IRandomGenerator rnd = new MersenneTwister();
IDistribution dist = new DiscreteNormalDistribution(discreteNormalDistributionSize);
List<double> results = new List<double>();

for (int i = 0; i < CHECKPOINTS; i++)
{
 results.AddRange(Oblist.Simulate(rnd, dist, n));
}

に：

Parallel.For(0, CHECKPOINTS, i =>
        {
           results.AddRange(Oblist.Simulate(rnd, dist, n));
        });

Simulate 内で rnd.nextUniform() への呼び出しが多数あります。同じ値を多数取得していると思いますが、これは現在並列になっているため発生する可能性がありますか?

また、List AddRange 呼び出しがスレッド セーフではないという問題もありますか? 私はこれを見る

System.Threading.Collections.BlockingCollection は使用する価値があるかもしれませんが、AddRange のない Add メソッドしかないため、その結果を調べて、スレッド セーフな方法で追加する必要があります。Parallel.For を使用したことのある方からの洞察をお待ちしております。Mersenne Twister の実装で nextUniform を呼び出すときに例外が発生したため、一時的にSystem.Randomに切り替えました。おそらく、特定の配列が範囲外のインデックスを取得していたため、スレッドセーフではありませんでした....

4

3 に答える 3

1

List<double>は間違いなくスレッドセーフではありません。System.Collections.Generic.List ドキュメントの「スレッド セーフ」セクションを参照してください。その理由はパフォーマンスです。スレッド セーフの追加は無料ではありません。

乱数の実装もスレッドセーフではありません。この場合、同じ数値を複数回取得することは、まさに期待どおりです。rnd.NextUniform()何が起こっているのかを理解するために、次の単純化されたモデルを使用してみましょう。

  1. オブジェクトの現在の状態から疑似乱数を計算する
  2. オブジェクトの状態を更新して、次の呼び出しで別の数値が返されるようにする
  3. 疑似乱数を返す

ここで、2 つのスレッドがこのメソッドを並行して実行すると、次のようなことが起こる可能性があります。

  • スレッド A は、手順 1 と同様に乱数を計算します。
  • スレッド B は、手順 1 と同様に乱数を計算します。スレッド A はまだオブジェクトの状態を更新していないため、結果は同じです。
  • スレッド A は、手順 2 のようにオブジェクトの状態を更新します。
  • スレッド B は、ステップ 2 のようにオブジェクトの状態を更新し、A の状態変更を踏みにじるか、同じ結果をもたらす可能性があります。

rnd.NextUniform()ご覧のとおり、2 つのスレッドが互いに干渉しているため、機能することを証明するために行うことができる推論はもはや有効ではありません。さらに悪いことに、このようなバグはタイミングに依存し、特定のワークロードまたは特定のシステムで「グリッチ」としてまれにしか発生しない場合があります。悪夢のデバッグ！

考えられる解決策の 1 つは、状態の共有をなくすことです。各タスクに、別のシードで初期化された独自の乱数ジェネレーターを与えます (インスタンスが何らかの方法で静的フィールドを介して状態を共有していないと仮定します)。

別の (劣った) 解決策は、次のようにクラスにロック オブジェクトを保持するフィールドを作成することです。MersenneTwister

private object lockObject = new object();

MersenneTwister.NextUniform()次に、実装でこのロックを使用します。

public double NextUniform()
{
   lock(lockObject)
   {
      // original code here
   }
}

これにより、2 つのスレッドが NextUniform() メソッドを並行して実行できなくなります。あなたのリストの問題はParallel.For、同様の方法で対処できます:Simulate呼び出しと呼び出しを分離し、呼び出しのAddRange周りにロックを追加しAddRangeます。

私の推奨事項: 可能な限り、並列タスク間で変更可能な状態 (RNG 状態など) を共有することは避けてください。変更可能な状態が共有されていない場合、スレッドの問題は発生しません。これにより、ボトルネックのロックも回避されます。「並列」タスクが、並列でまったく機能しない単一の乱数ジェネレーターで待機することは望ましくありません。特に、時間の 30% が乱数の取得に費やされている場合。

AddRange状態の共有とロックは、(呼び出しのように) 並列実行の結果を集約する場合など、避けられない場所に限定してください。

于 2009-07-13T10:56:22.597 に答える