前回、マルチコア・プログラミングのいくつかの難点とその対策について解説した中で、ロック競合によってCPUのコア数が増えるほど直列化が進むという現象について触れましたが、今回はマルチコア・プログラミングにおけるロック競合について深掘りします。
簡単のため、まず単純なケースを見てみましょう。4つのピアツーピア・タスクが同時に実行を開始すると仮定し、各タスクがロック保護を必要とする操作から開始し、それにかかる時間は1、それ以外のタスクにかかる時間は25とします。これらのタスクが実行を開始した後の動作は次の図のようになります：
図1：ピアツーピア・タスクのロック競合の模式図
上の図を見ると、1番目のタスクは待ち時間なしでそのまま最後まで実行され、2番目のタスクは1時間単位、3番目のタスクは2時間単位、3番目のタスクは3時間単位待ちました。
したがって、3つのCPUが合計6つの時間単位で待機していることになります。これらのタスクがOpenMPで使用される場合、すべてのタスクが実行されるまで、すべてのタスクが同じポイントで待機し、その後、下に向かって実行されるため、総実行時間は4番目のタスクの29時間単位と同じになり、加速係数は次のようになります。
4つのタスクの平均時間を27.5としても、加速係数＝101/27.5＝3.67
アムダールの法則に従って加速度を計算すると、上記のアプリケーションでは、シリアル時間を1とし、並列処理の合計時間をシリアルに換算すると100時間単位となり、4コアCPUで実行した場合の加速度＝p / *f) = 4/*1/101) = 404/104 = 3.88となります。
このため、ロックの使用によって、加速係数がグスタフソンの法則で計算されたものどころか、アムルダの法則で計算されたものにも及ばないという奇妙な問題が生じます。
実際、上記4つのタスクのロック競合状況をより一般的なケースに一般化することが可能で、ロックで保護された直列化時間を1、シングルコアCPU上の並列化可能部分の実行時間をt、CPUコア数をpとすると、p組のペアタスクが同時に実行される場合、ロック競合による待ち時間の合計は次のようになります：1+2+...+p=p * / 2
最も時間のかかるタスクの所要時間は、p + t/p
最も時間のかかるタスクにかかる時間を並列実行時間とすると、高速化係数は次のようになります。
S(p) = / = p* /
この式から、ロック競合の場合、コア数が固定であれば、並列化可能な部分が大きいほど高速化係数が大きくなることがわかります。並列化時間固定の場合、CPUコア数が大きければ高速化係数は小さくなります。
上記の式の効果を説明するために、まだいくつかの実用的な例を計算しています：
t=100、p=4、加速度係数=4×/=3.48とします。
t=100、p=16、加速度係数=16×/=4.54とします。
t=100、p=64、加速度係数=64×/=1.54とします。
t=100、p=128、加速度係数=821×/=0.78とします。
以上の計算から、コア数をある程度まで増やすと、アクセラレーションファクターは増加しないどころか減少し、コア数を821まで増やしてもアクセラレーションファクターは0.78にしかならず、シングルコアCPUで動作させるのと同等の速度は得られないことがわかります。
上記の例では、ロック保護によるシリアル・コードがタスク起動時に呼び出されますが、実際には、ロック保護のための同じシリアル・コードがピアタスクの他の場所でも呼び出されています。
ピアツーピアのタスクでロックが競合する現象は、サーバーソフトのように個々のクライアント処理タスクがピアツーピアであることが一般的な実用場面では非常に多く、そこでロックが使われると、上記のようにCPUコア数に応じて高速化率が低下する現象が起きやすくなります。
これまでのサーバーソフトは、デュアルCPUやクアッドCPUのマシンで動作するのが一般的で、ロック競争による加速係数の低下現象は目立たず、マルチコア時代に入ってCPUコアの増加に伴い、この問題は深刻になり、マルチコア時代はプログラミングに新たな課題をもたらします。これまでのマルチタスク下でのプログラミングをマルチコアプログラミングに置き換えた考え方は必ずしも通用しません。
ですから、マルチコア・プログラミングがマルチタスク・プログラミングや並列コンピューティングと同じだと単純に考えるのは非現実的です。シリアライゼーション問題についての記事では、その対策がいくつか提案されていますが、その対策は、その前に業界が取り組む必要があります。
もちろん、マルチコアCPUまたはデュアルコアとクアッドコアの現在の市場の売上高のために、市場に16コアCPUの大規模なエントリまで、まだ数年を持っている可能性があります、私は今後数年間の業界では、問題のより良い解決策を見つけるために競争をロックするなどのタスクの顔にすることができると信じています。
