2

私は遺伝的アルゴリズムを作成し、そのパフォーマンスを最適化するために、個人のフィットネステストを並列化することにしました。これが私のアルゴリズムにどのような変更を加えたかを確認するために、並列化の前に行ったテスト実行をやり直して、人口サイズの増加に対するGAのパフォーマンスをテストしました。

GAの並列バージョンは、実際には元のバージョンよりも約50％長くかかりました。並列化のオーバーヘッドが実際に節約するよりも時間がかかる場合があることを認識していますが、それがこの状況に当てはまるとは思えません-私のフィットネステストでは、シェケルのFoxholes関数のグローバル最小値を見つけています（http://extreme.adorio -research.org/download/mvf/html/node51.html）、私の母集団のサイズは10から1000の範囲です。シェケルの狐穴の1000回の実行を並列化すると、節約された時間は並列化のオーバーヘッドを大幅に上回ると予想されます。

だから私の質問は：なぜ並列化がアルゴリズムを（そしてそれほど大幅に）遅くしたのでしょうか？

ちなみに、私はJavaでコーディングしており、続行する前にすべてのスレッド（フィットネステスト）の実行を待機するCountDownLatchを使用して並列化しています。

4

3 に答える 3

3

あなたのコメントに基づくと、おそらくスレッドの数を除いて、かなり合理的に物事を行っているようです。しかし、CountDownLatchを使用していると、私は考えさせられます...

独自のコードの代わりにExecutorService/Executors、並列化にを使用することを強くお勧めします。クラスをaCallableにし、それらの束を作成して、invokeAll（）を呼び出します。そうすれば、高度な訓練を受けた（高給かどうかはわかりません）専門家がコーディングのほとんどを行いました。

を使用Executorsすると、スレッドの最大数を簡単に制御できます。Runtime.availableProcessors()一度に実行するスレッドの数で最初のパスを取得するために呼び出してから、テストと調整を行うことができます。

編集： ExecutorServiceを使用するようにアルゴリズムを変換するための紹介を投稿しました。楽しんでください、そしてコメント/フィードバックを歓迎します。

于 2012-06-14T23:01:21.820 に答える
1

それで私は問題が何であるかを理解しました-私は私のフィットネステストが並列化が価値があるのに十分長い時間がかかっていると思っていました、しかしそれは完全にそうではありませんでした。フィットネステストを埋めて、人為的に長くしました（とにかく、GAのパフォーマンスを監視するために使用しているテストフィットネステストです）。実行時間に大きな違いが見られます。人口が増えると、結果として次のようになります。実行時間を数十秒ではなく、数千秒延長します。そして、推奨されているように、それはエグゼキュータを実装する前であることを指摘する必要があります。

よろしくお願いします！

于 2012-06-16T02:58:46.187 に答える
1

さて、答えは、あなたが思っていたほど並列化されていないということです。問題は「なぜ？」コードを見ずに答えを出すのは難しいでしょう。ただし、いくつかの明らかな場所があります。

  • Thread の正しいエントリ ポイントを使用していることを確認してください (これは嫌いになるでしょう)。スレッドがシリアル化され、何も通知されないことを保証する 1 つの方法は、run()メソッドの代わりにメソッドを呼び出すことですstart()。ばかげているように聞こえますが、私はこれに噛まれました。

  • jconsole などを使用して、スレッドが同時に実行されていることを確認してください。そうでない場合は、予期しないロックがかかっています。

  • 同期するものを確認してください。使用しているコレクション クラスを確認します。まったくスレッドセーフでないものもあれば、内部同期があるためにスレッドセーフになっているものもあります。スレッド間で共有される Collection クラスはすべて、悪意のある可能性があります。

  • それでも何も浮かび上がらない場合は、同僚と一緒に紙にコードの実行をたどり、スレッドを手書きします。

于 2012-06-14T19:25:39.990 に答える