アーキテクチャ

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

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

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

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

• プロセッサ本体

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

強く順序付けられたメモリー (たとえば、あるプロセッサのメモリーへの変更が他のプロセッサにただちに伝わるようなメモリー) では、この方法は成立します (BSIZEが 1 ワードで表現できる最大整数より小さい限り、in と out が最終的にオーバフローしても成立します) 。

共有メモリー型のプロセッサは、必ずしも強く順序付けられたメモリーをもつ必要はありません。つまり、あるプロセッサによるメモリーへの変更が、他のプロセッサにただちに伝わるとは限りません。あるプロセッサによって、メモリーに 2 つの変更が加えられた場合、メモリーの変更がただちに伝わらないので、他のプロセッサから参照できる変更の順序は最初の順序と同じであるとは限りません。

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

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

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

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

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

最近は、メモリーの順序付けが弱くされる傾向にあります。このため、プログラマは広域データや共有データをロックで保護することに一層注意してください。

例 10-5 と例 10-6 で示すようにロックは重要です。

Peterson のアルゴリズム

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

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

例 10-6 2 つのスレッド間での相互排他が成立するか

void mut_excl(int me /* 0 または 1 */) {
    static int loser;
    static int interested[2] = {0, 0};
    int other; /* 局所変数 */
   
    other = 1 - me;
    interested[me] = 1;
    loser = me;
    while (loser == me && interested[other]);

    /* 危険領域 */
    interested[me] = 0;
}

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

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

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

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

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

このとき Peterson のアルゴリズムでは、それぞれ別のプロセッサで実行されている 2 つのスレッドが自分のスロットにデータを格納し、別のスロットからデータをロードしています。両方のスレッドは以前の値 (0) を見て相手がいないものと判定し、両方が危険領域に入ってしまいます。(この種の問題は、プログラムのテスト段階では明らかにならず、後になって判明することがあるので注意してください。)

この問題は、スレッドの同期プリミティブを使用すると回避できます。それらのプリミティブには、ストアバッファをキャッシュに強制的にフラッシュする特別な命令が含まれているからです。

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

多くのアプリケーション、特に数値計算関係のアプリケーションでは、他の部分が本質的に逐次的であっても、while 部分のアルゴリズムを並列化できます (詳細は、例 10-7 を参照してください)。

例 10-7 マルチスレッドの協調動作 (バリア同期)

スレッド 1

スレッド 2 〜 スレッド n

while(many_iterations) {

    sequential_computation
    --- バリア ---
    parallel_computation
}

while(many_iterations) {


    --- バリア ---
    parallel_computation
}

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

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

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