マルチコアCPUの登場により、マルチコアプログラミングの側面がプログラマの課題になってきます。 昔からマルチCPUマシンはあったし、マルチCPUマシンでのプログラミングの経験も業界に蓄積されているし、マルチコアCPUでのプログラミングもほとんど変わらないはずで、マルチタスクプログラミングや並列プログラミング、並列アルゴリズムのこれまでの経験を生かせば十分だと考えていた古参プログラマも多いはずです。
私が言いたいのは、マルチコアマシンは、以前のマルチCPUマシンとは大きく異なり、サーバーのような特定の分野や、大規模な並列計算が可能な分野では、マルチCPUの利点を生かしやすかったのですが、現在のマルチコアマシンは、一般ユーザーのあらゆるレベルで使用されており、特にクライアントマシンでは、マルチコアCPUを使用する必要があるのに対し、多くのクライアント側のソフトウェアは、サーバーや超並列コンピューティングの特定の分野ほど、マルチコアの並列性を利用するのは簡単ではありません。
困難I：シリアライゼーションへの挑戦
1) 加速係数
マルチプロセッサ・システムの性能を測定するために一般的に使用される指標の1つは、アクセラレーション・ファクターと呼ばれるもので、次のように定義されます：
S(p)＝1プロセッサの実行時間／pプロセッサの所要実行時間
2) アムルダの法則
並列処理には、以下の式で表されるアムルダの法則があります：
S(p) = p / *f)
ここでS(p)は加速度係数
pはプロセッサ数
fは、プログラム全体におけるシリアル部分の実行時間の割合を表します。
f=5%、p=20の場合、S(p)=約10.256
f=5%、p=100の場合、S(p)=約16.8
つまり、5パーセントの直列部分がある限り、プロセッサの数が20から100に増えたとき、アクセラレーション・ファクターは10.256から16.8くらいにしか増やせず、プロセッサの数は5倍に増えたのに、速度は60パーセントちょっとしか上がらないのです。プロセッサ数が無限に増えても、アクセラレーション・ファクターの限界値は20でしかありません。
アムルダの法則によれば、マルチコアの面ではほとんど発展の見込みがないと言え、ソフトウエアに並列化できない部分が1％しかないとしても、最大加速系は100にしか達せず、これ以上CPUを増やしても速度性能は向上しません。この法則に従えば、マルチコアCPUの開発は、ムーアの法則が限界に達するまで何年も続けられないといえます。
3) グスタフソンの法則
Gustafsonは、高速化係数がAmrdaの法則の限界を超えられることを証明するために、Amrdaの法則とは異なる仮定を行いました。Gustafsonは、ソフトウェアのシリアル部分は固定であり、サイズが大きくなっても増加しないと仮定し、並列処理部分の実行時間は固定であると仮定しました。Gustafsonの法則は、以下の式で表されます：
S(p) = p + *fts
ここで、ftsはシリアル実行のパーセンテージを表します。
直列比率が5パーセント、プロセッサー数が20の場合、アクセラレーション・ファクターは20 + * 5パーセント = 19.05
直列比率が5パーセント、プロセッサー数が100の場合、アクセラレーション・ファクターは100 + * 5パーセント = 95.05
グスタフソンの法則における高速化係数はプロセッサ数にほぼ比例しており、現実がグスタフソンの法則の仮定通りであれば、ソフトウェアの性能はプロセス数に応じて向上させることが可能です。
4) 実践的な状況における連載分析
アムルダの法則とグスタフソンの法則の差があまりにも大きいので、現実はどちらの法則に従っているのでしょうか？個人的には、現実はアムダの法則ほど悲観的でもなく、グスタフソンの法則ほど楽観的でもないと思います。なぜそう言えるのでしょうか？簡単な分析をしてみましょう。
まず、直列部分の割合を推定するために、ソフトウェアのどの部分が並列化できないかを正確に判断する必要があります。1960年代にバーンスタインは、並列計算が実行できない3つの条件を示しました：
条件1：C1がメモリセルに書き込んだ後、C2がそのセルのデータを読み出すこと。これを「書き込みと読み出し」の競合と呼びます。
条件2：C1がメモリセルを読み、C2がそのセルに書き込み。これを「読み書き」競争と呼びます。
条件1：C1がメモリ・セルを書き込んだ後にC2が書き込むこと。これは「書き込み後書き込み」競争と呼ばれます。
この3つの条件のいずれかが満たされると並列実行はできません。残念なことに、実際のソフトウェアではこれらの条件を満たすケースが非常に多く、よく「共有データをロックで保護する問題」と呼ばれます。
タスク数が固定であれば、ソフトウェア・サイズが大きくなるにつれてシリアライゼーションの割合は減少しますが、残念ながらタスク数が増えるにつれて増加します。つまり、プロセッサ数が増えれば増えるほど、ロック競合によるシリアライゼーションはより深刻になり、プロセッサ数が増えるにつれてシリアライゼーションの割合は劇的に増加します。したがって、シリアライゼーションはマルチコア・プログラミングの大きな問題です。
5）考えられる解決策
直列化問題の最初の解決策は、ロックの数を減らすこと、あるいはロックフリーのプログラミングをすることですが、ロックフリーのプログラミングのアルゴリズムは複雑すぎるため、一般的なプログラマーには難しい作業です。また、専門誌に発表されたロックフリーのアルゴリズムの多くが間違っていることが証明されており、その難しさは想像に難くありません。
2つ目の解決策は、ロックの代わりにアトミック演算を使用することです。 アトミック演算を使用することで、シリアライズの問題が本質的に解決されるわけではありません。しかし、チップ・ベンダーが提供するアトミック演算は非常に限定的で、一部の場所でしか動作しません。 チップ・ベンダーはこの分野で努力を続け、より多くの場所でロックの使用を回避するため、より強力なアトミック演算を提供する必要があるかもしれません。
3つ目の解決策は、設計やアルゴリズムレベルで直列化の割合を減らすことです。ロックの使用を減らすためには、実用的な並列設計パターンを見つけることが必要かもしれません。この分野では、タスク分解パターン、データ分解パターン、データ共有パターンなど、業界はすでにある程度の経験を蓄積していますし、将来的にマルチコアCPUが大規模に使用されるようになれば、さらに新しい効果的な並列設計パターンやアルゴリズムが登場すると思います。
