java - N 個のスレッドがほぼ同じ速度で実行されるようにするにはどうすればよいですか?

Question

私は、各物理要素が独自のスレッドでシミュレートされる物理シミュレーションソフトウェアを作成するというアイデアをいじっています。

このアプローチにはいくつかの利点があります。概念的には、現実世界の仕組みに非常に近いでしょう。システムを複数のマシンに拡張する方がはるかに簡単です。

ただし、これが機能するには、すべてのスレッドが同じ速度で実行されることを確認する必要があります。「同じ」という解釈はかなり自由です。お互い1%以内で言ってください。

そのため、必ずしも Thread.join() のようなソリューションは必要ありません。私は、すべてのスレッドが定期的に相互に同期することを保証する、超制御の学校の愛人を望んでいません。必要なのは、ランタイム (Java、Erlang、またはこの問題に最も適したもの) に、ほぼ同じ速度でスレッドを実行するように要求できることだけです。

どんな提案でも大歓迎です。

更新 2009-03-16

この質問に答えてくれたすべての人、特に答えが本質的に「これをしないでください」だったすべての人に感謝したいと思います. 皆さんのコメントのおかげで、私は自分の問題をよりよく理解できるようになりました。それにもかかわらず、ピーターの答えが質問自体に対する最良の答えだと感じたので、それを受け入れました。

score 13 · Accepted Answer

調整なしでは、これを行うことはできません。ある要素が別の要素よりも安価な計算を必要とすることになったらどうしますか (潜在的に明白でない方法で)?

必ずしも uber-controller が必要なわけではありません。スレッドごとにある種のステップカウンターを保持し、「最も遅い」スレッドを示すグローバルカウンターを持つことができます。(各スレッドが何らかの作業を行ったとき、他のスレッドよりも遅れているかどうかを確認し、遅れている場合はカウンターを更新する必要があります。) スレッドが、最も遅いスレッドよりもはるかに進んでいることに気付いた場合は、しばらく待つことができます (場合によってはモニター上で）。

共有データの競合によるオーバーヘッドが大きくなりすぎないように、これを頻繁に行うだけで、かなりうまくいくと思います。

score 12 · Accepted Answer

ある種の同期が必要になります。CyclicBarrierクラスには、必要なものがあります。

一連のスレッドが互いに共通のバリアポイントに到達するのをすべて待機できるようにする同期支援。CyclicBarriersは、時折互いに待機しなければならない固定サイズのスレッドのパーティを含むプログラムで役立ちます。バリアは、待機中のスレッドが解放された後に再利用できるため、サイクリックと呼ばれます。

各「ティック」の後で、すべてのスレッドに、低速だった他のスレッドを待機させることができます。残りのスレッドがバリアに到達すると、それらはすべて続行されます。

score 6 · Accepted Answer

スレッドは互いに完全に独立して実行されることを意図しています。あなたの場合、各スレッドが同じ量を取得する必要があることをVMに伝える方法がないため、中央の「クロック」が必要です...ええと...何を取得する必要がありますか? 同じ量のRAM？おそらく関係ありません。同じ量のCPU？すべてのオブジェクトが非常に似ているため、それぞれに同じ数のアセンブラー命令が必要ですか?

したがって、私の提案は、クロックティックをすべてのプロセスにブロードキャストする中央クロックを使用することです。各プロセス内のすべてのスレッドは、ティック (絶対値である必要があります) を読み取り、最後のティックとの差を計算し、それに応じて内部モデルを更新します。

スレッドが更新を完了すると、それ自体をスリープ状態にする必要があります。次のティックを待っています。Java では、「tick received」ロックで wait() を使用し、「notifyAll()」ですべてのスレッドを起こします。

score 4 · Accepted Answer

注意しないと後で問題が追加されるだけなので、可能な限りスレッドを使用しないことをお勧めします。物理シミュレーションを行う場合、大規模なシミュレーションには何十万もの個別のオブジェクトを使用できます。私が知っているどの OS でも、これほど多くのスレッドを作成することはできません。

あなたの場合、多数のスレッドを作成し、各スレッドにイベントループを配置できます。「マスター」スレッドは、実行を順序付けし、「プロセス」イベントを各ワーカースレッドにポストして、それを起動し、何らかの作業を行わせることができます。そうすれば、スレッドは動作するように指示されるまでスリープします。

すべてのワーカースレッドが次のティックの前に完了できるレートでマスタースレッドをティックさせることができるはずです。

一連の物理オブジェクトをそれぞれ線形に並べる少数のワーカースレッド (マシン内のコアの数に等しい) に並列化することを除いて、スレッドが問題の解決策になるとは思いません。この方法でマスター/イベント駆動型のアプローチを使用することもできますが、多くのオーバーヘッドを取り除くことができます。

score 3 · Accepted Answer

あなたが言及したように、「これをしないでください」という答えがたくさんあります。ほとんどのスレッドは、Java によって使用される OS スレッドとして読み取られるようです。投稿でErlangについて言及したので、よりErlang中心の回答を投稿したいと思います。

この種のシミュレーションをプロセス (またはアクター、マイクロスレッド、グリーンスレッドと呼ばれることもあります) でモデル化する場合、同期は必ずしも必要ではありません。本質的に、シミュレートする必要がある物理オブジェクトがいくつかあります (ほとんどの場合、数千または数十万)。これらのオブジェクトを可能な限り現実的にシミュレートしたいのですが、おそらく何らかのリアルタイムの側面も関係しているでしょう（そうである必要はありませんが、質問ではこれについて言及していません）。

簡単な解決策は、オブジェクトごとに Erlang プロセスを生成し、それらすべてにティックを送信し、次のティックに進む前にシミュレーションの結果を収集することです。これは実際にはすべてを同期しています。もちろん、これはより決定論的なソリューションであり、リアルタイムのプロパティを保証するものではありません。また、計算に必要なデータを取得するためにプロセスがどのように相互に通信するかも重要です。おそらくそれらを巧妙な方法でグループ化する必要があり (衝突グループなど)、休止中のオブジェクトのプロセスを休止状態にする必要があります (Erlang は適切にサポートしています)。

リアルタイムのプロパティを取得するには、おそらくプロセスによって実行される計算を制限する必要があります (速度と引き換えに精度)。これはおそらく、応答を待たずにティックを送信し、オブジェクトプロセスが現在の位置と必要なその他のデータを各ティックに返信できるようにすることで実行できます (ただし、その時点では概算でしかない場合もあります)。DJClayworthが言うように、これはシミュレーションでエラーが蓄積する可能性があります。

ある意味では、問題は、並行性の強さを利用して、ここで何らかの利点を得ることができるかどうかです。同期が必要な場合は、各物理オブジェクト間の同時実行が不要であることを示す非常に強力な兆候です。他のプロセスを待つことで、本質的に多くの計算時間を無駄にするからです。計算中に並行性を使用することもできますが、それは別の議論だと思います。

注:これらのアイデアはいずれも、実際の物理計算を考慮していません。これは Erlang の強力な側面ではなく、必要な特性のタイプに応じて、おそらく C ライブラリーまたはあなたの空想を刺激するもので実行できます。

注:これが行われたケースを (特に私が行った場合を除いて) 知りません。そのため、これが適切なアドバイスであるとは保証できません。

score 3 · Accepted Answer

しないでください。スレッドは、並列実行の外観を可能にする O/S 抽象化です。複数のマルチコア CPU を使用すると、O/S は異なるコア間でスレッドを分散できます (必須ではありません)。

スケーラビリティのビジョンに最も近いのは、使用可能なコアの数にほぼ一致するようにサイズ設定されたワーカースレッドを使用し、それらの間で作業を分散することです。ラフドラフト: 1 つのパーティクルの更新を行うクラス ActionTick を定義し、ワーカースレッドが共有キューから処理する ActionTick を選択できるようにします。このようなソリューションでも、いくつかの課題があります。

スレッド化のオーバーヘッド: 異なるワーカースレッド間でコンテキスト切り替えのオーバーヘッドが発生します。スレッド自体は高価です (実際にはプロセスほど破滅的ではないにしても): さまざまなスレッドプールサイズでパフォーマンスをテストしてください。コア数を超えてスレッドを追加すると、パフォーマンスが低下する傾向があります。
同期コスト: いくつかの競合点があります: 1 つのワークキューへのアクセスですが、さらに悪いことに、シミュレートされた世界へのアクセスです。各 ActionTick の効果を区切るか、多くのロック/ロック解除を実装する必要があります。
物理学の最適化の難しさ。各 ActionTick が参照するオブジェクト/パーティクルの数を制限したい (距離カットオフ? シミュレーション空間の 3D ツリー細分化?)。シミュレーションドメインによっては、アイテムのサブセットに変更が必要かどうかを調べることで、多くの作業を省略できる場合があります。この種の最適化は、分散アルゴリズムとして実行するよりも、作業項目をキューに入れる前に実行する方が簡単です。しかし、シミュレーションのその部分がスケーラビリティのボトルネックになる可能性があります。
複雑。スレッド化と並行性により、ソリューションにワームの缶がいくつか導入されます。常に他のオプションを最初に検討してください -- ただし、それらが必要な場合は、独自の作業項目のスケジューリング、ロック、および実行戦略を作成する前にスレッドを試してください...

警告: 私は大規模なシミュレーションソフトウェアを使用したことはなく、趣味のコードを使用しただけです。

score 2 · Accepted Answer

Erlangはデフォルトで、利用可能なスレッド全体にプロセスを均等に分散しようとします。また、デフォルトでは、使用可能なすべてのプロセッサでスレッドを実行しようとします。したがって、実行可能なErlangプロセスが十分にある場合は、比較的均等なバランスが得られます。

score 2 · Accepted Answer

完璧なソフトウェアを使用しても、ハードウェアがこれを妨げます。通常、ハードウェアスレッドのパフォーマンスは公平ではありません。短期間で、スレッドが +-10% のパフォーマンス内で実行される場合は幸運です。

もちろん、外れ値です。一部のチップセットは、一部のコアを省電力モードで実行し、他のコアは実行しません。Blue Gene の研究マシンの 1 つには、ロックの代わりにハードウェアスレッドのスケジューリングをソフトウェアで制御していたと思います。

score 1 · Accepted Answer

私はスレッドの専門家ではありませんが、スレッドが互いに独立しており、非決定論的であることがスレッドの全体的なポイントではありませんか?

score 1 · Accepted Answer

あなたの質問には、次のような根本的な誤解があると思います。

概念的には、現実世界の仕組みに非常に近いでしょう

現実の世界は糸のようには機能しません。ほとんどのマシンのスレッドは独立しておらず、実際には同時でもありません (OS代わりにコンテキスト切り替えが使用されます)。多くのIOまたは待機が発生しているときに、それらは最大の価値を提供します。

最も重要なことは、より複雑なことが起こっても、現実世界は「より多くのリソースを消費」しないということです。高所から落下する 2 つの物体の違いを考えてみてください。1 つはスムーズに落下し、もう 1 つはある種の複雑なタンブリングモーションを実行します...

score 0 · Accepted Answer

私はスレッドの専門家ではないことを最初に認めますが、これはシミュレーションへのアプローチとしては非常に間違った方法のように思えます。他の人がすでにコメントしているように、スレッドが多すぎると計算コストが高くなります。さらに、私が考えていることを実行しようとしている場合、シミュレーションがランダムな結果を生成する可能性があります (ゲームを作成している場合は問題にならない場合があります)。

シミュレーションの個別のステップを計算するために使用されるいくつかのワーカースレッドを使用します。

score 0 · Accepted Answer

これを実現するには、2 つのことが必要です。CPUコアごとに同じ数のスレッドがあることを確認する必要があり、ある種の同期が必要です。

計算の実行中に各スレッドの「サイクル完了」変数をチェックするなど、その同期はかなり単純ですが、それを避けることはできません。

java - N 個のスレッドがほぼ同じ速度で実行されるようにするにはどうすればよいですか?

14 に答える 14

Related

Reference