0

私は python を使用して理想的なガス シミュレーターを作成しています。現在、衝突検出はプログラムの中で最も集中的な部分です。ただし、現時点では、8 つのコアのうちの 1 つしか使用していません。(i7 3770 @ 3.4GHz を使用しています)

最小限のグーグル検索の後、python（2.7.4）のマルチプロセッシングモジュールが見つかりました。そして、私はそれを試しました。少し考えてみると、実際に並行して実行できるのはここだけであることがわかりました。ここでは、すべてのパーティクルをループして衝突を検出します。

for ball in self.Objects:   
        if not foo == ball:
            foo.CollideBall(ball, self.InternalTimestep)

ここで foo は、他のすべての粒子に対してテストしている粒子です。だから私はこれをやってみました：

for ball in self.Objects:   
        if not foo == ball:
            p = multiprocessing.Process(target=foo.CollideBall, args=(ball, self.InternalTimestep))
            p.start()

プログラムの実行速度は少し速くなりましたが、まだ 1.5 コアしか使用していません。残りはアイドル状態であり、衝突も検出されていません。一度に作成するプロセスが多すぎると (コアの数よりも多く)、バックログが発生する (これは 196 個のパーティクルのループです) と読んだことがあります。まだすべてのコアを使用していないという事実を説明していません!

とにかく遅すぎる！！！では、8 つのプロセスを作成し、すでに実行中のプロセスが 8 つ未満の場合にのみ新しいプロセスを作成する方法はありますか? それは私の問題を解決しますか？すべてのコアを使用するにはどうすればよいですか / このコードがまだないのはなぜですか?

昨日、Python でのマルチプロセッシングについて知ったばかりなので、答えを詳しく説明する必要があるのではないかと心配しています。

助けてくれてありがとう！

- -編集 - -

Carson に応えて、p.start の直後に p.join を追加しようとしたところ、プログラムの速度が低下しました。サイクルごとに0.2秒かかる代わりに、サイクルごとに24秒かかります!

4

2 に答える 2

3

私が理解している限りでは、1 つの粒子を他のすべての粒子に対してテストし、その操作を各粒子に対して順番に実行します。これに基づいて、あなたの問題は、コード自体を最適化しようとせずに、すべてのコアで動作するようにコードを最適化しようとすることだと思います.

代わりに、粒子を分割して、互いに近いものだけをチェックすることができます。そのための 1 つの考えられる方法は、四分木です。 http://en.wikipedia.org/wiki/Quadtreeを参照してください。

2 番目のステップでは、すべてを並列化できます。四分木については、手動で最上位レベルを解決し、サブツリーごとに新しいプロセスを作成します。これにより、プロセスは互いに独立し、ブロックされません。クアッド ツリーによる二次速度アップ (現在の実行時間の平方根を考えてください) と、並列化によるさらなる線形速度アップ (プロセス数で割る) が可能になることを期待しています。

申し訳ありませんが、Python で詳しく説明することはできません。

于 2013-11-05T09:38:44.353 に答える
0

クアッド ツリーが機能していれば、スレッド プールを (クラスとして) セットアップし、個々のスレッド (可能であれば、スレッド フレームワークからさらに別のクラス) に割り当てられるジョブ (別のクラス) を定義できます。あなたの場合、ジョブには、検査する必要がある四分木ノードのリストが含まれています。最初は、最上位のクアッド ツリー ノード (2D で 4 つ / 3D で 8 つ) がそれぞれのジョブに存在します。

したがって、最大 4 つ (それぞれ 8 つ) のスレッドを持つことができ、それぞれが四分木の独立したサブツリーを検査します。マシンの処理能力を十分に活用するためにさらに多くのスレッドが必要な場合は、スレッドが多くの深いサブツリーに遭遇した場合に、スレッドのジョブの一部をスレッド プールに戻すことができます。

このために、ジョブからの四分木ノードのリストで BFS (幅優先検索) を使用します。リストが予想よりも長くなった場合は、その一部をスレッド プールに戻します。数学/統計/確率論の知識は、予想される長さの適切なパラメーター化を見つけるのに役立ちます。

また、「ワールド」サイズが与えられ、オブジェクトの平均サイズが計算されると予想されるオブジェクト数に従って自身をパラメータ化するクワッド ツリーの実装も作成しました。

オープン ソース プロジェクト d-collide を検索します。C++ ですが、便利なサンプル コードがいくつかあるはずです。ただし、ライセンスについては考慮してください。これは BSD スタイルであるため、あまり求められません。

これを2番目の回答として追加しました。最初の回答は、暗黙の目標を達成するためにコードを最適化することでした。つまり、実行時間の短縮です（ただし、効率の向上によるものです）

この 2 番目の回答は、記述された目標の達成に関するものです。つまり、より強力な並列化です。ただし、四分木はこの 2 番目のステップを可能にしますが、2 番目のスピードアップが最初のステップほど速くなるとは思わないでください。特に多くのオブジェクトに関しては、最適化されたアルゴリズムに勝るものはありません。ただし、マイクロ最適化に夢中にならないでください。タスクのキャンセルで例外がスローされるというランタイムの説明を参照してください。

于 2013-11-05T16:31:47.090 に答える