OpenMPのメモリモデル
前項で少し触れましたが、OpenMPは共有メモリ方式を採用しています。共有メモリ方式は、逐次処理をしている間は普通のプログラミングをしていれば特に考慮する必要がありませんでしたが、並列処理を行う際には注意をせねばなりません。なぜならば、複数のスレッドで一つのメモリにある変数を読み書きするからです。
複数のスレッドが並列的処理をする場合、何も規定がないと並列プログラミングが困難になってしまいます。そこで、共有メモリをどのように扱うかを表すメモリモデルが定められています。
OpenMPのメモリモデルはrelaxed-consistencyです。relaxed-consistencyは、メモリへのリードとライトの実行順序を必ずしも守らないメモリモデルです。何のためにリードやライトの実行順序を守らないのかというと、主な理由はパフォーマンスを上げるためです。普段意識することはありませんが、コンパイラは命令の実行順序を変えて最適化しています。もし、実行順序を変えないようにすると、このような最適化が行えなくなりますし、厳格に実行順序を保障するためのオーバーヘッドが生じることになります。 OpenMPのメモリモデルはrelaxed-consistencyですので、実行順序に依存する処理をプログラミングしてはなりません。また、ライト処理には細心の注意を払わねばなりません。
OpenMPの並列処理モデル
OpenMPは従来のスレッドプログラミングによる並列化を抽象化した技術ですので、どのようにプログラムが並列化されているのかを理解する必要があります。仕様書によるとOpenMPはfork-joinモデルを採用しています。
fork-joinモデルをコードで表現すると次のようになります。以降サンプルコードをもとに解説しますので、まず下記のコードを見てください。
#include <stdio.h>
#include <windows.h>
#include <winnt.h>
#include <process.h>
typedef unsigned (__stdcall *PTHREAD_START) (void *);
/*タスクを表す構造体*/
struct task
{
int start; /* 開始インデックス値 */
int end; /* 終了インデックス値 */
int sum; /* 合計値 */
int size; /* 値の個数 */
int* values; /* 値 */
int granularity; /* 粒度 */
};
/**********************************************************
fork/joinモデルで並行的に合計値を算出します。
***********************************************************/
DWORD WINAPI fork( PVOID pvParam )
{
/* 変数の設定 */
int i;
HANDLE hThreads[2];
DWORD dwThreadID;
struct task tsk1, tsk2;
struct task* tsk;
tsk = pvParam;
/* fork/joinで合計値を算出する */
if ( tsk->size <= tsk->granularity ) { /* 値を算出 */
tsk->sum = 0;
for ( i = tsk->start; i < tsk->end + 1; i++ )
tsk->sum += tsk->values[ i ];
return 0;
} else { /* 問題を2つのタスクに分割して算出 */
/* タスク1 */
tsk1.granularity = tsk->granularity;
tsk1.size = tsk->size / 2;
tsk1.start = tsk->start;
tsk1.end = tsk1.start + ( tsk1.size - 1 );
tsk1.values = tsk->values;
/* タスク2 */
tsk2.granularity = tsk->granularity;
tsk2.size = tsk->size - tsk1.size;
tsk2.start = tsk1.end + 1;
tsk2.end = tsk2.start + ( tsk2.size - 1 );
tsk2.values = tsk->values;
/* 問題を2分割して行う */
hThreads[ 0 ] = ( HANDLE ) _beginthreadex (
( void * ) NULL,
( unsigned ) 0,
( PTHREAD_START ) fork,
( void * ) ( PVOID ) &tsk1,
( unsigned ) 0,
( unsigned * ) &dwThreadID );
hThreads[ 1 ] = ( HANDLE ) _beginthreadex (
( void * ) NULL,
( unsigned ) 0,
( PTHREAD_START ) fork,
( void * ) ( PVOID ) &tsk2,
( unsigned ) 0,
( unsigned * ) &dwThreadID );
/* 処理結果を合計する */
WaitForMultipleObjects( 2, hThreads, TRUE, INFINITE );
CloseHandle( hThreads[ 0 ] );
CloseHandle( hThreads[ 1 ] );
tsk->sum = tsk1.sum + tsk2.sum;
return;
}
}
/**********************************************************
任意の数の数値の合計値を求めて表示します。
***********************************************************/
int main()
{
struct task tsk;
int sum, i, count;
int* values;
/* 初期値を設定 */
count = 10;
tsk.start = 0;
tsk.end = count - 1;
tsk.sum = 0;
tsk.size = count;
tsk.granularity = 2;
values = ( int* ) malloc( count * sizeof( int ) );
for( i = 0; i < count; i++ )
values[ i ] = i + 1;
tsk.values = values;
/* 合計値を並行的に算出する */
fork( &tsk );
/* メッセージを表示 */
printf( "次の数値の合計を算出します・・・\n" );
for( i = 0; i < tsk.size; i++ )
printf( "%d " , tsk.values[ i ] );
printf( "\n計算結果%d\n\n", tsk.sum);
}
このサンプルは、配列に格納された任意の数値を合計するものです。注目するべき点はfork関数です。fork関数内で、処理する範囲を二分割し、個別に算出して合計することを再帰的に行っています。つまり、fork-joinモデルとは、問題を分割して解決するタイプの並列化技法なのです。このことからいくつかのOpenMPの特徴が分かります。
第1に、問題を分割できなければ実現不可能だということが分かります。fork-joinモデルは、問題を分割して解決する方式ですので、そもそも問題が分割できない場合にはどうすることもできません。例えば、任意の数の数値が互いに干渉し合う場合、数値を並列的に正しく計算することはできません。この場合は、各数値がどのように計算されるのかをよく調べ、どのような基準で処理を分割できるのかを考える必要があるでしょう。
第2に、逐次プログラミングでは必要のなかった余分な処理が必ずいることが分かります。これがコア数と同じ処理効率を達成できない理由です。先ほどのサンプルでは、_beginthreadex関数の呼び出し、WaitForMultipleObjects関数の呼び出し、CloseHandle関数の呼び出しなどのコードがそれに該当します。
第3に、処理する内容が少ないと処理速度が落ちるということです。元々単純でデータ量が少ないプログラムを並列処理化すると、先ほど述べた余分な処理があるので処理速度が遅くなります。
以上でfork-joinモデルに関する解説は終わりです。ただし、これはあくまでも概念を理解するためのサンプルであり、実際にコンパイラが出力するコードは、より高度に最適化されている点に注意して下さい。具体的に言いますと、このサンプルでは、簡潔かつ、処理が分割される事を強調化したいと考えて、タスクの粒度を細かく設定しておりますが（tsk.granularity = 2;の部分）通常は動的にCPUのコア数を算出して適切な粒度を決定します。また、並列処理ではCPUのキャッシュラインの調節が重要です。CPUのキャッシュラインを意識しないと、並列処理のパフォーマンスが悪くなります。ですから、コンパイラはCPUのキャッシュラインを意識したコードを出力します。その他にも色々な工夫をコンパイラは行っています。
