コードは並列処理を行っているように見えるかもしれませんが、実際にはそうではありません。基本的に、データのコピーとメモリ アロケータ アクセスのキューイングに時間を費やしています。
さらに、保護されていないiループ インデックスを何もないかのように使用しているため、画像の美しいスライスではなくランダムなジャンクがワーカー スレッドに供給されます。
いつものように、C++ はこれらの悲しい事実をシンタックス シュガーの分厚い皮の下に隠しています。
しかし、あなたのコードの最大の欠陥はアルゴリズムそのものです。
この例は、並列処理の教科書的なケースのように思えますが、「教育的な」分析を見たことがないので、試してみます。
機能解析
すべての CPU コアを使用して、マンデルブロ集合のピクセルをクランチします。これは、各ピクセルの計算を個別に実行できるため、並列化可能な計算の完璧なケースです。
したがって、基本的に、マシンに N 個のコアがある場合、1/N の処理を実行するコアごとに正確に 1 つのスレッドが必要です。
残念ながら、各プロセッサが必要な処理の 1/N を実行するように入力データを分割することは、見かけほど明白ではありません。
指定されたピクセルは、計算に 0 ～ 255 回の反復を行うことができます。「黒」のピクセルは、「白」のピクセルの255 倍のコストがかかります。
したがって、単純に画像を N 個の等しいサブサーフェスに分割すると、「黒い」領域を這うプロセッサを除いて、すべてのプロセッサが「白い」領域を通過する可能性があります。その結果、最も遅い領域の計算時間が支配的になり、並列化は実質的に何も得られません。
実際のケースでは、これはそれほど劇的ではありませんが、それでも計算能力が大幅に失われます。
負荷分散
負荷のバランスを改善するには、画像をより小さなビットに分割し、各ワーカー スレッドが前のビットの処理が完了するとすぐに次の使用可能なビットを選択して計算する方が効率的です。そうすれば、「白い」チャンクを処理しているワーカーは最終的にその仕事を終了し、「黒い」チャンクを選んで不幸な兄弟を助け始めます。
理想的には、大きなチャンクの線形コストが合計計算時間に追加されるのを避けるために、チャンクは複雑さを減らしてソートする必要があります。
残念ながら、マンドルブロー集合の混沌とした性質のため、特定の領域の計算時間を予測する実用的な方法はありません。
チャンクが画像の水平方向のスライスになると判断した場合、それらを自然なy順序で並べ替えるのは明らかに最適ではありません。その特定の領域が一種の「白から黒へ」の勾配である場合、最もコストのかかる行はすべてチャンク リストの最後にまとめられ、最もコストのかかるビットを最後に計算することになります。これは負荷分散の最悪のケースです。
考えられる解決策は、チャンクをバタフライ パターンでシャッフルすることです。これにより、「黒い」領域が最後に集中する可能性が低くなります。
もう 1 つの方法は、単純に入力パターンをランダムにシャッフルすることです。
概念実証の実装の 2 つの出力を次に示します。
ジョブは逆の順序で実行されます (ジョブ 39 が最初で、ジョブ 0 が最後です)。各行は次のようにデコードされます。
t ab : プロセッサ b のスレッド番号 a
b : 開始時間 (画像計算の開始から)
e : 終了時間
d : 継続時間 (すべての時間はミリ秒)
1) バタフライオーダーで40ジョブ
job 0: t 1-1 b 162 e 174 d 12 // the 4 tasks finish within 5 ms from each other
job 1: t 0-0 b 156 e 176 d 20 //
job 2: t 2-2 b 155 e 173 d 18 //
job 3: t 3-3 b 154 e 174 d 20 //
job 4: t 1-1 b 141 e 162 d 21
job 5: t 2-2 b 137 e 155 d 18
job 6: t 0-0 b 136 e 156 d 20
job 7: t 3-3 b 133 e 154 d 21
job 8: t 1-1 b 117 e 141 d 24
job 9: t 0-0 b 116 e 136 d 20
job 10: t 2-2 b 115 e 137 d 22
job 11: t 3-3 b 113 e 133 d 20
job 12: t 0-0 b 99 e 116 d 17
job 13: t 1-1 b 99 e 117 d 18
job 14: t 2-2 b 96 e 115 d 19
job 15: t 3-3 b 95 e 113 d 18
job 16: t 0-0 b 83 e 99 d 16
job 17: t 3-3 b 80 e 95 d 15
job 18: t 2-2 b 77 e 96 d 19
job 19: t 1-1 b 72 e 99 d 27
job 20: t 3-3 b 69 e 80 d 11
job 21: t 0-0 b 68 e 83 d 15
job 22: t 2-2 b 63 e 77 d 14
job 23: t 1-1 b 56 e 72 d 16
job 24: t 3-3 b 54 e 69 d 15
job 25: t 0-0 b 53 e 68 d 15
job 26: t 2-2 b 48 e 63 d 15
job 27: t 0-0 b 41 e 53 d 12
job 28: t 3-3 b 40 e 54 d 14
job 29: t 1-1 b 36 e 56 d 20
job 30: t 3-3 b 29 e 40 d 11
job 31: t 2-2 b 29 e 48 d 19
job 32: t 0-0 b 23 e 41 d 18
job 33: t 1-1 b 18 e 36 d 18
job 34: t 2-2 b 16 e 29 d 13
job 35: t 3-3 b 15 e 29 d 14
job 36: t 2-2 b 0 e 16 d 16
job 37: t 3-3 b 0 e 15 d 15
job 38: t 1-1 b 0 e 18 d 18
job 39: t 0-0 b 0 e 23 d 23
いくつかの小さなジョブを処理したスレッドが、独自のチャンクを処理するのにより多くの時間を要した別のジョブを追い越すときに、負荷分散が機能していることがわかります。
2) 線形順序付けの 40 ジョブ
job 0: t 2-2 b 157 e 180 d 23 // last thread lags 17 ms behind first
job 1: t 1-1 b 154 e 175 d 21
job 2: t 3-3 b 150 e 171 d 21
job 3: t 0-0 b 143 e 163 d 20 // 1st thread ends
job 4: t 2-2 b 137 e 157 d 20
job 5: t 1-1 b 135 e 154 d 19
job 6: t 3-3 b 130 e 150 d 20
job 7: t 0-0 b 123 e 143 d 20
job 8: t 2-2 b 115 e 137 d 22
job 9: t 1-1 b 112 e 135 d 23
job 10: t 3-3 b 112 e 130 d 18
job 11: t 0-0 b 105 e 123 d 18
job 12: t 3-3 b 95 e 112 d 17
job 13: t 2-2 b 95 e 115 d 20
job 14: t 1-1 b 94 e 112 d 18
job 15: t 0-0 b 90 e 105 d 15
job 16: t 3-3 b 78 e 95 d 17
job 17: t 2-2 b 77 e 95 d 18
job 18: t 1-1 b 74 e 94 d 20
job 19: t 0-0 b 69 e 90 d 21
job 20: t 3-3 b 60 e 78 d 18
job 21: t 2-2 b 59 e 77 d 18
job 22: t 1-1 b 57 e 74 d 17
job 23: t 0-0 b 55 e 69 d 14
job 24: t 3-3 b 45 e 60 d 15
job 25: t 2-2 b 45 e 59 d 14
job 26: t 1-1 b 43 e 57 d 14
job 27: t 0-0 b 43 e 55 d 12
job 28: t 2-2 b 30 e 45 d 15
job 29: t 3-3 b 30 e 45 d 15
job 30: t 0-0 b 27 e 43 d 16
job 31: t 1-1 b 24 e 43 d 19
job 32: t 2-2 b 13 e 30 d 17
job 33: t 3-3 b 12 e 30 d 18
job 34: t 0-0 b 11 e 27 d 16
job 35: t 1-1 b 11 e 24 d 13
job 36: t 2-2 b 0 e 13 d 13
job 37: t 3-3 b 0 e 12 d 12
job 38: t 1-1 b 0 e 11 d 11
job 39: t 0-0 b 0 e 11 d 11
ここでは、コストのかかるチャンクがキューの最後に集まる傾向があるため、パフォーマンスが著しく低下します。
3) コアごとに 1 つのジョブのみを実行し、1 ～ 4 個のコアをアクティブ化する
reported cores: 4
Master: start jobs 4 workers 1
job 0: t 0-0 b 410 e 590 d 180 // purely linear execution
job 1: t 0-0 b 255 e 409 d 154
job 2: t 0-0 b 127 e 255 d 128
job 3: t 0-0 b 0 e 127 d 127
Master: start jobs 4 workers 2 // gain factor : 1.6 out of theoretical 2
job 0: t 1-1 b 151 e 362 d 211
job 1: t 0-0 b 147 e 323 d 176
job 2: t 0-0 b 0 e 147 d 147
job 3: t 1-1 b 0 e 151 d 151
Master: start jobs 4 workers 3 // gain factor : 1.82 out of theoretical 3
job 0: t 0-0 b 142 e 324 d 182 // 4th packet is hurting the performance badly
job 1: t 2-2 b 0 e 158 d 158
job 2: t 1-1 b 0 e 160 d 160
job 3: t 0-0 b 0 e 142 d 142
Master: start jobs 4 workers 4 // gain factor : 3 out of theoretical 4
job 0: t 3-3 b 0 e 199 d 199 // finish at 199ms vs. 176 for butterfly 40, 13% loss
job 1: t 1-1 b 0 e 182 d 182 // 17 ms wasted
job 2: t 0-0 b 0 e 146 d 146 // 44 ms wasted
job 3: t 2-2 b 0 e 150 d 150 // 49 ms wasted
ここでは 3 倍の改善が得られますが、負荷分散を改善すれば 3.5 倍になる可能性があります。
これは非常に穏やかなテスト ケースです (計算時間は約 2 倍しか変化しないことがわかりますが、理論的には 255 倍も変化する可能性があります!)。
いずれにせよ、何らかの負荷分散を実装しなければ、あなたが書いた光沢のあるマルチプロセッサ コードはどれも、まったくひどいパフォーマンスしか得られません。
実装
スレッドが妨げられずに機能するには、外部の世界からの干渉を受けないようにする必要があります。
そのような干渉の 1 つがメモリ割り当てです。メモリを 1 バイトでも割り当てるたびに、グローバル メモリ アロケータへの排他的アクセスのためにキューに入れられます (そして、割り当てを行うために CPU を少し浪費します)。
また、画像の計算ごとにワーカー タスクを作成することも、時間とリソースの無駄です。この計算は、インタラクティブなアプリケーションでマンドルブロ集合を表示するために使用される可能性があるため、ワーカーを事前に作成して同期し、連続する画像を計算することをお勧めします。
最後に、データのコピーがあります。いくつかのポイントの計算が完了するたびにメイン プログラムと同期すると、結果領域への排他的アクセスの待ち行列にかなりの時間を費やすことになります。さらに、大量のデータを無用にコピーすると、パフォーマンスがさらに低下します。
明白な解決策は、コピーを完全に省き、元のデータで作業することです。
デザイン
ワーカー スレッドが妨げられずに動作するために必要なすべてを提供する必要があります。そのためには、次のことが必要です。
- システムで利用可能なコアの数を決定する
- 必要なすべてのメモリを事前に割り当てます
- 各ワーカーに画像チャンクのリストへのアクセスを許可します
- コアごとに正確に 1 つのスレッドを起動し、ジョブを実行するために自由に実行させます
ジョブ キュー
派手なノーウェイトやギズモは必要ありませんし、キャッシュの最適化に特別な注意を払う必要もありません。
ここでも、ピクセルを計算するのに必要な時間は、スレッド間の同期コストとキャッシュ効率の問題を小さくします。
基本的に、キューは画像生成の開始時に全体として計算できます。ワーカーはそこからジョブを読み取るだけで済みます。このキューでは読み取り/書き込みアクセスが同時に行われることはありません。そのため、ジョブ キューを実装するための多かれ少なかれ標準的なコードは最適ではなく、目の前のジョブには複雑すぎます。
2 つの同期ポイントが必要です。
- ワーカーがジョブの新しいバッチを待つようにする
- マスターに絵の完成を待たせる
ワーカーは、キューの長さが正の値に変わるまで待機します。その後、それらはすべてウェイクアップし、キューの長さをアトミックに減らし始めます。キューの長さの現在の値は、関連するジョブ データ (基本的には、計算するように設定された Mandlebrot の領域と、計算された反復値を格納するための関連するビットマップ領域) への排他的アクセスを提供します。
ワーカーの終了にも同じメカニズムが使用されます。仕事の新しいバッチを見つける代わりに、貧しい労働者は目を覚まして終了する命令を見つけます.
画像の完成を待っているマスターは、最後のジョブの処理を終了するワーカーによって起こされます。これは、処理するジョブ数のアトミック カウンターに基づきます。
これが私がそれを実装した方法です：
class synchro {
friend class mandelbrot_calculator;
mutex lock; // queue lock
condition_variable work; // blocks workers waiting for jobs/termination
condition_variable done; // blocks master waiting for completion
int pending; // number of jobs in the queue
atomic_int active; // number of unprocessed jobs
bool kill; // poison pill for workers termination
void synchro (void)
{
pending = 0; // no job in queue
kill = false; // workers shall live (for now :) )
}
int worker_start(void)
{
unique_lock<mutex> waiter(lock);
while (!pending && !kill) work.wait(waiter);
return kill
? -1 // worker should die
: --pending; // index of the job to process
}
void worker_done(void)
{
if (!--active) // atomic decrement (exclusive with other workers)
done.notify_one(); // last job processed: wakeup master
}
void master_start(int jobs)
{
unique_lock<mutex> waiter(lock);
pending = active = jobs;
work.notify_all(); // wakeup all workers to start jobs
}
void master_done(void)
{
unique_lock<mutex> waiter(lock);
while (active) done.wait(waiter); // wait for workers to finish
}
void master_kill(void)
{
kill = true;
work.notify_all(); // wakeup all workers (to die)
}
};
すべてをまとめる：
class mandelbrot_calculator {
int num_cores;
int num_jobs;
vector<thread> workers; // worker threads
vector<job> jobs; // job queue
synchro sync; // synchronization helper
mandelbrot_calculator (int num_cores, int num_jobs)
: num_cores(num_cores)
, num_jobs (num_jobs )
{
// worker thread
auto worker = [&]()
{
for (;;)
{
int job = sync.worker_start(); // fetch next job
if (job == -1) return; // poison pill
process (jobs[job]); // we have exclusive access to this job
sync.worker_done(); // signal end of picture to the master
}
};
jobs.resize(num_jobs, job()); // computation windows
workers.resize(num_cores);
for (int i = 0; i != num_cores; i++)
workers[i] = thread(worker, i, i%num_cores);
}
~mandelbrot_calculator()
{
// kill the workers
sync.master_kill();
for (thread& worker : workers) worker.join();
}
void compute(const viewport & vp)
{
// prepare worker data
function<void(int, int)> butterfly_jobs;
butterfly_jobs = [&](int min, int max)
// computes job windows in butterfly order
{
if (min > max) return;
jobs[min].setup(vp, max, num_jobs);
if (min == max) return;
jobs[max].setup(vp, min, num_jobs);
int mid = (min + max) / 2;
butterfly_jobs(min + 1, mid );
butterfly_jobs(mid + 1, max - 1);
};
butterfly_jobs(0, num_jobs - 1);
// launch workers
sync.master_start(num_jobs);
// wait for completion
sync.master_done();
}
};
コンセプトのテスト
このコードは、Microsoft Dev Studio 2013 でコンパイルされた 2 コア / 4 CPU Intel I3 @ 3.1 GHz でうまく動作します。
1280x1024 ピクセルのウィンドウで平均 90 回/ピクセルのセットを少し使用します。
計算時間は、ワーカーが 1 つだけの場合は約1.700 秒で、ワーカーが 4 つの場合は0.480 秒に低下します。
可能な最大ゲインは係数 4 になります。係数 3.5 が得られます。悪くない。
違いの一部はプロセッサ アーキテクチャによるものだと思います (I3 には「実際の」コアが 2 つしかありません)。
スケジューラの改ざん
私のプログラムは、スレッドをそれぞれ 1 つのコアで実行するように強制します ( MSDN を使用SetThreadAffinityMask)。
スケジューラが自由にタスクを割り当てられる場合、ゲイン係数は 3.5 から 3.2 に低下します。
これは重要なことですが、それでも Win7 スケジューラはそのままにしておくと非常にうまく機能します。
同期オーバーヘッド
「白い」ウィンドウ (r < 2 領域の外側) でアルゴリズムを実行すると、システム コールのオーバーヘッドがよくわかります。
代表的な領域の 480 ミリ秒と比較して、この「白い」領域の計算には約 7 ミリ秒かかります。
ジョブ キューの同期と計算の両方を含めて、1.5% 程度です。これは、1024 個のジョブのキューで同期を行っています。
まったく無視できると思います。それは、周りのすべての待ち時間なしのキュー狂信者に考えさせるかもしれません.
反復の最適化
反復が行われる方法は、最適化の重要な要素です。
何度か試行錯誤した結果、次の方法に落ち着きました。
static inline unsigned char mandelbrot_pixel(double x0, double y0)
{
register double x = x0;
register double y = y0;
register double x2 = x * x;
register double y2 = y * y;
unsigned iteration = 0;
const int max_iteration = 255;
while (x2 + y2 < 4.0)
{
if (++iteration == max_iteration) break;
y = 2 * x * y + y0;
x = x2 - y2 + x0;
x2 = x * x;
y2 = y * y;
}
return (unsigned char)iteration;
}
純利益: OP の方法と比較して +20%
（registerディレクティブは少しの違いはありません。それらは装飾のためにあるだけです）
各計算後にタスクを強制終了する
ワーカーを有効にしておく利点は、計算時間の約 5% です。
バタフライ効果
私のテスト ケースでは、「バタフライ」注文は非常にうまく機能しており、極端なケースでは 30% 以上の利益が得られ、最も大量のリクエストを「デバンチング」することで通常は 10 ～ 15% の利益が得られます。