以下に概説するような固定数のスレッドを使用した同時反復処理シナリオで最高のパフォーマンスを提供する可能性が高い Java 同期構造はどれですか? しばらく自分で (ExecutorService と CyclicBarrier を使用して) 実験し、その結果に少し驚いた後、専門家のアドバイスや新しいアイデアをいただければ幸いです。ここでの既存の質問は、主にパフォーマンスに焦点を当てているようには見えないため、この新しい質問です。前もって感謝します!
アプリのコアは単純な反復データ処理アルゴリズムで、OS X 10.6 と Java 1.6.0_07 を実行している Mac Pro の 8 つのコアに計算負荷を分散するために並列化されています。処理されるデータは 8 つのブロックに分割され、各ブロックは Runnable に送られ、固定数のスレッドの 1 つによって実行されます。アルゴリズムの並列化はかなり簡単で、機能的には期待どおりに機能しますが、そのパフォーマンスはまだ私が考えているほどではありません. アプリはシステム コールの同期に多くの時間を費やしているようです。そのため、いくつかのプロファイリングの後、最も適切な同期メカニズムを選択したかどうか疑問に思います。
アルゴリズムの重要な要件は、段階的に進行する必要があるため、各段階の最後にスレッドを同期する必要があることです。メインスレッドは作業を準備し (非常に低いオーバーヘッド)、それをスレッドに渡し、作業をさせ、すべてのスレッドが完了すると処理を進め、作業を再配置し (これも非常に低いオーバーヘッド)、サイクルを繰り返します。マシンはこのタスク専用であり、事前に割り当てられた項目のスレッドごとのプールを使用することでガベージ コレクションが最小限に抑えられ、スレッドの数を固定できます (着信要求などはなく、CPU コアごとに 1 つのスレッドのみ)。
V1 - ExecutorService
私の最初の実装では、8 つのワーカー スレッドを持つ ExecutorService を使用しました。プログラムは、作業を保持する 8 つのタスクを作成し、大まかに次のように作業させます。
// create one thread per CPU
executorService = Executors.newFixedThreadPool( 8 );
...
// now process data in cycles
while( ...) {
// package data into 8 work items
...
// create one Callable task per work item
...
// submit the Callables to the worker threads
executorService.invokeAll( taskList );
}
これは機能的にはうまく機能し (本来あるべきことを行います)、実際、非常に大きな作業項目の場合、処理アルゴリズムが許容できる限り、8 つの CPU すべてに高い負荷がかかります (一部の作業項目は他の作業項目よりも速く終了し、その後アイドル状態になります)。 . ただし、作業項目が小さくなると (これは実際にはプログラムの制御下にはありません)、ユーザーの CPU 負荷は劇的に減少します。
blocksize | system | user | cycles/sec
256k 1.8% 85% 1.30
64k 2.5% 77% 5.6
16k 4% 64% 22.5
4096 8% 56% 86
1024 13% 38% 227
256 17% 19% 420
64 19% 17% 948
16 19% 13% 1626
凡例: - ブロック サイズ = ワークアイテムのサイズ (= 計算ステップ) - システム = OS X アクティビティ モニター (赤いバー) で示されるシステム負荷 - ユーザー = OS X アクティビティ モニター (緑のバー) で示されるユーザー負荷- サイクル/秒 = メインの while ループの繰り返し、多いほど良い
ここで主に懸念されるのは、システムで費やされる時間の割合が高いことです。これは、スレッド同期呼び出しによって引き起こされているようです。予想どおり、小さい作業項目の場合、ExecutorService.invokeAll() は、各スレッドで実行される作業の量に対して、スレッドを同期するためにより多くの労力を必要とします。しかし、ExecutorService は、このユース ケースで必要とされるよりも一般的であるため (コアよりも多くのタスクがある場合、スレッドのタスクをキューに入れることができます)、より無駄のない同期構造が存在する可能性があります。
V2 - CyclicBarrier
次の実装では、大まかに次のように、CyclicBarrier を使用して、作業を受け取る前と完了した後にスレッドを同期させました。
main() {
// create the barrier
barrier = new CyclicBarrier( 8 + 1 );
// create Runable for thread, tell it about the barrier
Runnable task = new WorkerThreadRunnable( barrier );
// start the threads
for( int i = 0; i < 8; i++ )
{
// create one thread per core
new Thread( task ).start();
}
while( ... ) {
// tell threads about the work
...
// N threads + this will call await(), then system proceeds
barrier.await();
// ... now worker threads work on the work...
// wait for worker threads to finish
barrier.await();
}
}
class WorkerThreadRunnable implements Runnable {
CyclicBarrier barrier;
WorkerThreadRunnable( CyclicBarrier barrier ) { this.barrier = barrier; }
public void run()
{
while( true )
{
// wait for work
barrier.await();
// do the work
...
// wait for everyone else to finish
barrier.await();
}
}
}
繰り返しますが、これは機能的にはうまく機能し (本来あるべきことを行います)、非常に大きな作業項目の場合、以前と同様に 8 つの CPU すべてに高い負荷がかかります。ただし、作業項目が小さくなると、負荷は依然として劇的に縮小します。
blocksize | system | user | cycles/sec
256k 1.9% 85% 1.30
64k 2.7% 78% 6.1
16k 5.5% 52% 25
4096 9% 29% 64
1024 11% 15% 117
256 12% 8% 169
64 12% 6.5% 285
16 12% 6% 377
大規模な作業項目の場合、同期は無視でき、パフォーマンスは V1 と同じです。しかし予想外に、(高度に専門化された) CyclicBarrier の結果は、(一般的な) ExecutorService の結果よりもはるかに悪いように見えます: スループット (サイクル/秒) は V1 の約 1/4 にすぎません。これは CyclicBarrier の宣伝されている理想的な使用例のように見えますが、一般的な ExecutorService よりもパフォーマンスがはるかに悪いというのが暫定的な結論です。
V3 - 待機/通知 + CyclicBarrier
最初の循環バリア await() を単純な待機/通知メカニズムに置き換えてみる価値があるように思われました。
main() {
// create the barrier
// create Runable for thread, tell it about the barrier
// start the threads
while( ... ) {
// tell threads about the work
// for each: workerThreadRunnable.setWorkItem( ... );
// ... now worker threads work on the work...
// wait for worker threads to finish
barrier.await();
}
}
class WorkerThreadRunnable implements Runnable {
CyclicBarrier barrier;
@NotNull volatile private Callable<Integer> workItem;
WorkerThreadRunnable( CyclicBarrier barrier ) { this.barrier = barrier; this.workItem = NO_WORK; }
final protected void
setWorkItem( @NotNull final Callable<Integer> callable )
{
synchronized( this )
{
workItem = callable;
notify();
}
}
public void run()
{
while( true )
{
// wait for work
while( true )
{
synchronized( this )
{
if( workItem != NO_WORK ) break;
try
{
wait();
}
catch( InterruptedException e ) { e.printStackTrace(); }
}
}
// do the work
...
// wait for everyone else to finish
barrier.await();
}
}
}
繰り返しますが、これは機能的にうまく機能します (本来あるべきことを行います)。
blocksize | system | user | cycles/sec
256k 1.9% 85% 1.30
64k 2.4% 80% 6.3
16k 4.6% 60% 30.1
4096 8.6% 41% 98.5
1024 12% 23% 202
256 14% 11.6% 299
64 14% 10.0% 518
16 14.8% 8.7% 679
小さな作業項目のスループットは、ExecutorService よりもはるかに劣りますが、CyclicBarrier の約 2 倍です。CyclicBarrier を 1 つ削除すると、ギャップの半分が削除されます。
V4 - 待機/通知の代わりにビジー待機
このアプリはシステム上で実行されている主要なアプリであり、コアが作業項目でビジーでない場合はとにかくアイドル状態であるため、CPU を不必要に回転させても、各スレッドで作業項目をビジー状態で待機してみませんか。ワーカー スレッド コードは次のように変更されます。
class WorkerThreadRunnable implements Runnable {
// as before
final protected void
setWorkItem( @NotNull final Callable<Integer> callable )
{
workItem = callable;
}
public void run()
{
while( true )
{
// busy-wait for work
while( true )
{
if( workItem != NO_WORK ) break;
}
// do the work
...
// wait for everyone else to finish
barrier.await();
}
}
}
また、機能的にもうまく機能します(本来あるべきことを行います)。
blocksize | system | user | cycles/sec
256k 1.9% 85% 1.30
64k 2.2% 81% 6.3
16k 4.2% 62% 33
4096 7.5% 40% 107
1024 10.4% 23% 210
256 12.0% 12.0% 310
64 11.9% 10.2% 550
16 12.2% 8.6% 741
小さな作業項目の場合、これにより、CyclicBarrier + 待機/通知バリアントよりもスループットがさらに 10% 向上しますが、これは重要ではありません。ただし、ExecutorService を使用した場合でも、V1 よりもはるかにスループットが低くなります。
V5 - ?
では、そのような (おそらく珍しいことではない) 問題に最適な同期メカニズムは何でしょうか? ExecutorService を完全に置き換える独自の同期メカニズムを作成するのにうんざりしています (それがあまりにも一般的であり、より効率的にするためにまだ取り出すことができるものが必要であると仮定します)。それは私の専門分野ではなく、不確実な利益のためにデバッグに多くの時間を費やすことになるのではないかと心配しています(待機/通知およびビジー待機バリアントが正しいかどうかさえわからないため)。
アドバイスをいただければ幸いです。