マルチプロセッサへの対応

マルチスレッドでは、主に並列性とスケーラビリティーという点でマルチプロセッサ (マルチコアプロセッサやマルチスレッドプロセッサを含む) を活用できます。プログラマは、マルチプロセッサと単一プロセッサのメモリーモデルの違いを考慮に入れておかなければなりません。

このマニュアルでは、特に断りのない限り、マルチプロセッサの説明はマルチコアプロセッサとマルチスレッドプロセッサにも該当します。

メモリーの一貫性は、メモリーを問い合わせるプロセッサと直接的な相関関係にあります。単一プロセッサの場合、メモリーを参照するプロセッサは 1 つしかないのでメモリーは一貫しています。

マルチプロセッサの性能を高めようとすると、メモリーの一貫性が緩められることになります。あるプロセッサによるメモリーへの変更が、ほかのプロセッサから見たメモリーイメージにただちに反映されるとは限りません。

共有される大域変数を使用するときに同期変数を使用すれば、この複雑さを回避できます。

メモリーバリアー同期を使用すると、マルチプロセッサ上での並列性をうまく制御できる場合があります。

マルチプロセッサに関して、もう 1 つの問題があります。共通の実行ポイントに到達するまで全スレッドが待たなければならないようなケースでは、同期の効率が問題となります。

共有メモリーの場所へのアクセスに常にスレッド同期プリミティブを使用する場合、ここで言及した内容は重要ではありません。第 4 章同期オブジェクトを使ったプログラミングを参照してください。

アーキテクチャー

スレッドは、スレッド同期ルーチンを使用して共有記憶領域へのアクセスを同期します。スレッドを同期することによって、共有メモリー型のマルチプロセッサ上でプログラムを実行することは、単一プロセッサ上でプログラムを実行することと同じことになります。

しかし、プログラマはあえてマルチプロセッサ特有の機能を活用したり、同期ルーチンを迂回する「トリック」を使用したりすることがあります。例 9–5 と例 9–6 に示すように、こうしたトリックは危険性をはらんでいます。

通常のマルチプロセッサアーキテクチャーがサポートしているメモリーモデルを理解することは、この危険性を理解する助けとなります。

マルチプロセッサの主な構成要素は、次のとおりです。

• プログラムを実行するプロセッサ (コアとそれらのスレッドを含む)

• ストアバッファー (プロセッサとキャッシュを接続する)

• キャッシュ (最近アクセスされたまたは変更された記憶領域の内容を保持する)

• メモリー (全プロセッサによって共有される主記憶領域)

従来の単純なモデルでは、各プロセッサがメモリーに直接接続されているかのように動作します。 つまり、あるプロセッサが特定の位置にデータを格納すると同時に別のプロセッサが同じ位置からデータをロードした場合、2 番目のプロセッサは最初のプロセッサが格納したデータをロードします。

キャッシュを使って、平均メモリーアクセス時間を高速化できます。キャッシュ間の整合性が維持されているときは、データの整合性も保たれます。

この単純なモデルの問題点は、データの整合性を保つためプロセッサをしばしば遅延させなければならないことです。最新のマルチプロセッサでは、各種の手法でそうした遅延を回避していますが、メモリーデータの整合性を失わせています。

次の 2 つの例で、それらの手法と効果を説明します。

共有メモリー型のマルチプロセッサ

例 9–5 は、「生産者 / 消費者」問題の代表的な解決方法です。

このプログラムは、現在の SPARC ベースのマルチプロセッサでは正しく動作しますが、すべてのマルチプロセッサが強く順序付けられたメモリーをもつことを想定しています。したがって、このプログラムには移植性がありません。

例 9–5 「生産者 / 消費者」問題 — 共有メモリー型のマルチプロセッサ

char buffer[BSIZE];
unsigned int in = 0;
unsigned int out = 0; 

/* Thread 1 (producer) */

/* Thread 2 (consumer) */

void
producer(char item) {
     do
     {
        ;/* nothing */
     }
     while
         ((in - out) == BSIZE);

     buffer[in%BSIZE] = item;
     in++;
}

char
consumer(void) {
     char item;
     do
     {
        ;/* nothing */
     }
     while
         ((in - out) == 0);
     item = buffer[out%BSIZE];
     out++;
}

このプログラムは、生産者と消費者がそれぞれ 1 つしか存在せず、かつ共有メモリー型のマルチプロセッサ上で動作するときは正しく動作します。in と out の差が、バッファー内のデータ数となります。

生産者はバッファーに新しい項目のための空きができるまで、この差を繰り返し計算しながら待ちます。消費者は、バッファーに項目が入れられるのを待ちます。

強く順序付けられたメモリーでは、一方のプロセッサへの変更が、もう一方のプロセッサのメモリーにただちに伝えられます。強く順序付けられたメモリーでは、in と out が最終的にオーバーフローしても、このソリューションが成立します。このオーバーフローは、BSIZE が 1 ワードで表現できる最大の整数より小さい場合に発生します。

共有メモリー型のプロセッサは、必ずしも強く順序付けられたメモリーをもつ必要はありません。つまり、あるプロセッサによるメモリーへの変更が、ほかのプロセッサにただちに伝わるとは限りません。あるプロセッサによって、異なったメモリー領域 2 箇所に変更が加えられたとき、どうなるか考えてみましょう。もう一方のプロセッサには、メモリーの変更がただちに伝わらないので、このプロセッサから検出できる変更の順序は最初の順序と同じであるとは限りません。

変更内容は、まず「ストアバッファー」に入れられます。このストアバッファーは、キャッシュからは参照できません。

プロセッサは、プログラムの整合性を保証するために、これらのストアバッファーをチェックします。しかし、ほかのプロセッサから、このストアバッファーは参照できません。このため、あるプロセッサが書き込んだ内容は、キャッシュに書き込まれるまで、ほかのプロセッサから参照できません。

同期プリミティブは、特別な命令でストアバッファーの内容をキャッシュにフラッシュしています。第 4 章同期オブジェクトを使ったプログラミングを参照してください。したがって、共有データをロックで保護すればメモリーの整合性が保証されます。

メモリーの順序付けが非常に弱い場合は例 9–5 で問題が発生します。消費者は、対応するバッファースロットへの変更を知る前に、生産者によって in が 1 つ増やされたことを知る場合があります。

あるプロセッサのストア順序が、別のプロセッサからは違った順序で見えることがあるため、このメモリーの順序付けを「弱い順序付け」と呼びます。ただし、同じプロセッサから見たメモリーは常に整合性を保っています。この問題を解決するには、相互排他ロックを使用して、ストアバッファーの内容をキャッシュにフラッシュしなければなりません。

最近は、メモリーの順序付けが弱くされる傾向にあります。このため、プログラマは大域データや共有データをロックで保護するよう注意する必要があります。

例 9–5 と例 9–6 に示すように、ロックは重要です。

Peterson のアルゴリズム

例 9–6 のコードは、2 つのスレッド間の相互排他を処理する Peterson のアルゴリズムの実装例です。このコードは、危険領域に同時に複数のスレッドが存在しないことを保証しようとしています。スレッドは、mut_excl() を呼び出すと、「すばやく」危険領域に入ります。

ここで、スレッドは危険領域に入るとすばやく抜け出るものとします。

例 9–6 2 つのスレッド間での相互排他

void mut_excl(int me /* 0 or 1 */) {
    static int loser;
    static int interested[2] = {0, 0};
    int other; /* local variable */
   
    other = 1 - me;
    interested[me] = 1;
    loser = me;
    while (loser == me && interested[other])
        ;

    /* critical section */
    interested[me] = 0;
}

このアルゴリズムは、マルチプロセッサのメモリーが強く順序付けられているときは成立します。

SPARC ベースのマルチプロセッサを含む一部のマルチプロセッサは、ストアバッファーを装備しています。スレッドがストア命令を実行すると、データがストアバッファーに入れられます。このバッファーの内容は最終的にキャッシュに送られますが、すぐに送られるとは限りません。各プロセッサのキャッシュはデータの整合性を維持していますが、変更されたデータはキャッシュにすぐには送られません。

複数のデータが格納されたとき、その変更はキャッシュ (およびメモリー) に正しい順序で伝わりますが、通常は遅延を伴います。SPARC ベースのマルチプロセッサでは、この性質のことを「トータルストア順序 (TSO) をもつ」と言います。

あるプロセッサが A 番地にデータを格納して次に B 番地からデータをロードして、別のプロセッサが B 番地にデータを格納して次に A 番地からデータをロードした場合、「最初のプロセッサが B 番地の新しい値を得る」と「2 番目のプロセッサが A 番地の新しい値を得る」の一方または両方が成立します。しかし、「両方のプロセッサが以前の値を得る」というケースは起こりえないはずです。

さらに、ロードバッファーとストアバッファーの遅延が原因で、上記の起こりえないケースが起こることがあります。

このとき Peterson のアルゴリズムでは、それぞれ別のプロセッサで実行されている 2 つのスレッドが両方とも危険領域に入ります。各スレッドは特定の配列の自分のスロットにデータを格納し、別のスロットからデータをロードします。両方のスレッドは以前の値 (0) を読み取り、相手がいないものと判定し、両方が危険領域に入ってしまいます。この種の問題は、プログラムのテスト段階では発生せず、あとになって発生する可能性があります。

この問題を回避するには、スレッドの同期プリミティブを使用します。それらのプリミティブには、ストアバッファーをキャッシュに強制的にフラッシュする特別な命令が含まれています。第 4 章同期オブジェクトを使ったプログラミングを参照してください。

共有メモリー型の並列コンピュータでのループの並列化

多くのアプリケーション、特に数値計算関係のアプリケーションでは、ほかの部分が本質的に逐次的であっても、while 部分のアルゴリズムを並列化できます。このアルゴリズムでは、バリアー同期を使用して並列的な部分と逐次的な部分を調整できます。

Thread 1

Thread 2 through Thread n

while(many_iterations) {

    sequential_computation
    --- Barrier ---
    parallel_computation
}

while(many_iterations) {


    --- Barrier ---
    parallel_computation
}

たとえば、完全な線型計算で一組の行列を作成し、それらの行列に対する操作を並列アルゴリズムで実行します。次に、これらの操作結果からもう一組の行列を作成し、それらの行列を並列的に操作するといった処理が考えられます。

こうした計算の並列アルゴリズムの特徴は、計算中はほとんど同期をとる必要がない点にあります。しかし、並列計算を始める前に逐次計算が終了していることを確認するために、すべてのスレッドの同期をとる必要があります。

バリアーには、並列計算を行なっているすべてのスレッドを、関係しているすべてのスレッドがバリアーに達するまで待たせるという働きがあります。スレッドは全部がバリアーに達したところで解放され、一斉に計算を開始します。