3.5 処理速度の向上

実行時間の大部分を占めるプログラム部分が並列化できない場合、速度の向上は期待できません。これは、基本的にアムダールの法則の結果から言えることです。たとえば、プログラム実行の 5% 部分に相当するループしか並列化できない場合、全体的に速度を向上できる限界は 5% です。しかし、実際には、負荷の量と並列実行に伴うオーバーヘッドによって、まったく速度が向上しないこともあります。

したがって、一般的な規則として、プログラムの並列化される部分が大きくなればなるほど、大幅な速度の向上を期待できます。

それぞれの並列ループには、起動時と終了時にわずかなオーバーヘッドがあります。起動時のオーバーヘッドには作業を分散するためのものがあり、終了時には、バリアでの同期によるものがあります。ループによって実行される作業量が比較的小さい場合には、速度の向上を期待できません。実際にループの実行が遅くなることもあります。したがって、プログラム実行の大部分が小さな並列ループから構成されている場合には、全体の実行速度は上がらず、かえって遅くなることがあります。

コンパイラは、いくつかのループ変換を実行することで、ループの規模を大きくしようとします。この変換には、ループの交換およびループの融合が含まれます。したがって、一般的には、プログラム中の並列化部分が少ない場合や小さな並列化部分に分割される場合には、速度の向上を期待できません。

プログラムサイズが大きくなると、プログラムの並列度が向上することがあります。たとえば、あるプログラムが順次実行する部分がプログラムサイズの 2 乗に増加し、並列化可能な部分が 3 乗に増加するものとします。このプログラムでは、並列化された部分の作業量が順次実行する部分よりも速い勢いで増加します。したがって、資源の限界に達しないかぎり、ある時点で速度向上の効果が明確に表れます。

一般に並列 C の能力を有効利用するには、コンパイル指令を実験したり、プログラムの大きさやプログラムを再構成するといった調整を行う必要があります。

3.5.1 アムダールの法則

決まったサイズの問題の処理速度の向上度は、一般にアムダールの法則によって予測されます。アムダールの法則は単純に、特定の問題に対して並列化がもたらす速度の向上は、問題の逐次処理部分によって制限されると説明しています。次の式は、逐次処理領域で費やされる時間の割合が F であり、時間のうち残りの割合が P 個のプロセッサの間で一様に費やされる状況における問題の速度向上について説明します。この式からわかるように、式の 2 番目の項の値がゼロになると、値が決まっている 1 番目の項によって全体的な速度の向上度が制限されます。

次の図に、この概念を示します。灰色の部分がプログラム中の逐次処理部分を表現しています。この部分は 1、2、4、8 プロセッサ各々の場合で一定であるのに対し、斜線部分がプログラムの並列処理部分で、複数のプロセッサ間で一様に分割され、処理時間が短くなっています。

図 3-3 固定された問題の処理速度の向上

プロセッサの数が増加するにつれ、各プログラムの並列処理部分の所要時間は減少していますが、各プログラムの逐次処理部分は同じままです。

ただし実際には、複数のプロセッサに作業を分散し通信するためのオーバーヘッドが存在します。このようなオーバーヘッドは、プロセッサの数に対して一定であったり、そうでなかったりします。

次の図には、プログラムに逐次処理部分がそれぞれ 0%、2%、5%、10% 含まれる場合の理想的な速度向上が示されています。この図では、オーバーヘッドは想定されていません。

図 3-4 アムダールの法則による処理速度向上の曲線

グラフは、オーバーヘッドがないと想定した場合、0%、2%、5%、および 10% の逐次処理部分を含むプログラムでの理想的な速度向上を示しています。横軸はプロセッサの数、縦軸は速度を表しています。

3.5.1.1 オーバーヘッド

モデルにオーバーヘッドの影響を取り入れると、速度向上の曲線は大幅に変わります。ここでは、説明上 2 つの部分、つまり、プロセッサの数には無関係な固定部分と、使用されるプロセッサの 2 乗で増加する可変部分から成るオーバーヘッドを想定します。

S 分の 1 は、{F プラス (1 マイナス P 分の F) プラス K1 プラス K2 P 二乗} 分の 1 に等しいです。

この式で K₁ と K₂ は一定の係数です。この仮定では、速度向上の曲線は次の図のようになります。この場合、速度の向上にピーク点があることに注目してください。ある点を越えると、プロセッサを増加させてもパフォーマンスが下がり始めます。

図 3-5 オーバーヘッドがある場合の速度向上の曲線

グラフは、すべてのプログラムで 5 プロセッサのときにもっとも処理速度が早く、8 プロセッサまで増えると徐々に遅くなることを示しています。横軸はプロセッサの数、縦軸は速度を表しています。

3.5.1.2 ガスタフソンの法則

アムダールの法則では、実際の問題を並列化するときの速度向上の効果を正しく予測できません。プログラムの逐次処理部分に費やされる時間の割合は、問題のサイズに依存することがあります。つまり、問題のサイズが増加すると、速度向上の可能性が大きくなる場合があります。例を使って説明します。

例 3-12 問題サイズの拡大により速度向上の可能性が大きくなることがある

/*
* initialize the arrays
*/
for (i=0; i < n; i++) {
    for (j=0; j < n; j++) {
            a[i][j] = 0.0;
            b[i][j] = ...
            c[i][j] = ...
    }
}
/*
* matrix multiply
*/
for (i=0; i < n; i++) {
    for(j=0; j < n; j++) {
            for (k=0; k < n; k++) {
                a[i][j] = b[i][k]*c[k][j];
            }
    }
}

理想的にオーバーヘッドがゼロで、2 番目に入れ子にされたループが並列に実行されると仮定すると、問題のサイズが小さい場合 (すなわち n の値が小さい) と、プログラムの順次実行部分と並列実行部分の大きさがそれほど違わないことがわかります。ところが、n が大きくなると、並列実行部分に費やされる時間が順次実行の部分に対するものよりも早い勢いで大きくなります。この問題の場合は、問題のサイズが大きくなるにつれてプロセッサの数を増やす方法が有効です。