ISO C の別名を使用すると、ループを並列化できなくなることがあります。別名とは、2 個の参照が記憶領域の同じ位置を参照する可能性のある場合に発生します。次の例を考えてみましょう。
void copy(float a[], float b[], int n) { int i; for (i=0; i < n; i++) { a[i] = b[i]; /* S1 */ } } |
変数 a および b は引数であるため、次のように呼ばれる場合には、a および b が重なりあった記憶領域を参照している可能性があります。次のようなルーチン copy が呼び出される例を考えてみましょう。
copy (x[10], x[11], 20); |
呼び出された側では、copy ループの連続した 2 回の繰り返しが、配列 x の同じ要素を読み書きしている可能性があります。しかし、ルーチン copy が次のように呼び出された場合には、実行される 20 回の繰り返しループで、重なりあう可能性がなくなります。
copy (x[10], x[40], 20); |
一般的に、ルーチンがどのように呼び出されるかをコンパイラが知っていないかぎり、この状況を正しく解析することは不可能になります。ANSI/ISO C では、ANSI C に対する拡張キーワードを装備することで、このような別名の問題に対して指示することが可能になっています。詳細については、「3.8.2 制限付きポインタ」を参照してください。
別名の問題の一因は、配列参照とポインタ計算演算を定義できる C 言語の性質にあります。効率的にループを並列化するためには、プラグマを自動的または明示的に使用して、配列として配置されているすべてのデータを、ポインタではなく C の配列参照の構文を使用して参照する必要があります。ポインタ構文が使用されると、コンパイラはループの異なる繰り返し間でのデータの関係を解析できなくなります。そのため、安全性を考慮してループを並列化しなくなります。
コンパイラが効率よくループを並列化できるようにするには、左辺値が記憶領域の特定の領域を示していなければいけません。別名とは、記憶領域の決まった位置を示していない左辺値のことです。オブジェクトへの 2 個のポインタが別名であるかどうかを判断することは困難です。これを判断するにはプログラム全体を解析することが必要であるため、非常に時間がかかります。次の関数 vsq() を考えてみましょう。
void vsq(int n, double * a, double * b) { int i; for (i=0; i<n; i++) { b[i] = a[i] * a[i]; } } |
ポインタ a および b が異なるオブジェクトをアクセスすることをコンパイラが知っている場合には、ループ内の異なる繰り返しを並列に実行することができます。しかし、ポインタ a および b でアクセスされるオブジェクトが重なりあっていれば、ループを安全に並列実行できなくなります。コンパイル時に関数 vsq() を単純に解析するだけでは、a および b によるオブジェクトのアクセスが重なりあっているかどうかを知ることはできません。この情報を得るには、プログラム全体を解析することが必要になります。
制限付きポインタを使ってオブジェクトを明確に区別すると、コンパイラによるポインタ別名の解析が実行可能になります。次に、vsq() の関数パラメータを制限付きポインタとして宣言した例を示します。
void vsq(int n, double * restrict a, double * restrict b) |
ポインタ a および b が制限付きポインタとして宣言されているので、a および b で示された記憶領域が区別されていることがわかります。この別名情報によって、コンパイラはループの並列化を実行することができます。
キーワード restrict は volatile に似た型修飾子で、ポインタ型に対して有効です。なお、restrict は -Xs モードでコンパイルする場合を除き、-xc99=all を使用する場合に有効なキーワードです。ソースコードを変更しない場合があります。その場合、次のコマンド行オプションを使用して、ポインタ型の値をとる関数の引数を restrict ポインタとして扱うように指定できます。
-xrestrict=[func1,…,funcn] |
関数リストが指定されている場合、指定された関数内のポインタパラメータは制限付きとして扱われます。指定されていない場合は、C ファイル全体のすべてのポインタパラメータが制限付きとして扱われます。たとえば、-xrestrict=vsq を使用すると、前述の関数 vsq() についての最初の例では、ポインタ a および b がキーワード restrict によって修飾されます。
restrict を正しく使用することはとても重要です。区別できないオブジェクトを指しているポインタを制限付きポインタにしてしまうと、ループを正しく並列化することができなくなり、不定な動作をすることになります。たとえば、関数 vsq() のポインタ a および b が重なりあっているオブジェクトを指している場合には、b[i] と a[i+1] などが同じオブジェクトである可能性があります。このとき a および b が制限付きポインタとして宣言されていなければ、ループは順次実行されます。a および b が間違って制限付きであると宣言されていれば、コンパイラはループを並列実行するようになりますが、この場合 b[i+1] の結果は b[i] をを計算したあとでなければ得られないので、安全に実行することはできません。
すでに述べたように、並列化の適用や有効性をコンパイラだけで決めるには、情報が不十分なことがあります。コンパイラはプラグマをサポートしており、コンパイラだけでは不可能なループの並列化を効率よく実行することができます。この節の残りの部分で説明する Sun 固有の MP プラグマは、OpenMP 規格に準拠するため非推奨になりました。標準命令については、『OpenMP API ユーザーズガイド』を参照してください。
Sun 固有の MP プラグマは推奨されず、サポートされません。代わりに、OpenMP 3.0 規格で規定された API をサポートします。標準命令への移植については、『OpenMP API ユーザーズガイド』を参照してください。
直列プラグマには 2 通りあり、どちらも for ループに適用されます。
#pragma MP serial_loop
#pragma MP serial_loop_nested
#pragma MP serial_loop は、次に存在する for ループを自動的に並列化しないことを指示します。
#pragma MP serial_loop_nested は、次に存在する for ループ、およびその for ループの中で入れ子になっている for ループを自動的に並列化しないことを指示します。
これらのプラグマのスコープは、そのプラグマから始まり、次のブロックの始まりか現在のブロック内のプラグマに続く最初の for ループ、または現在のブロックの終わりのいずれか先に達したところで終わります。
Sun 固有の MP プラグマは推奨されず、サポートされません。代わりに、OpenMP 3.0 規格で規定された API をサポートします。標準命令への移植については、『OpenMP API ユーザーズガイド』を参照してください。
並列プラグマは 1 つだけあります。#pragma MP taskloop [options]
MP taskloop プラグマは、オプションとして、次の引数を取ることができます。
maxcpus (プロセッサ数)
private (スレッド固有変数リスト)
shared (共有変数リスト)
readonly (読み取り専用変数リスト)
storeback (ストアバック変数リスト)
savelast
reduction (縮約変数リスト)
schedtype (スケジューリング型)
このプラグマのスコープは、プラグマから始まり、次のブロックの始まりか現在のブロック内のプラグマに続く最初の for ループ、または現在のブロックの終わりのいずれか先に達したところで終わります。プラグマは、スコープの終端に到達した時点で最初に見つかった for ループに適用されます。
オプションは、1 つの MP taskloop pragma に 1 つだけ指定できます。ただし、プラグマは蓄積されて、スコープ内の最初に見つかった for ループに適用されます。
#pragma MP taskloop maxcpus(4) #pragma MP taskloop shared(a,b) #pragma MP taskloop storeback(x) |
これらのオプションは、for ループの前に複数回指定できます。オプションが衝突を起こす場合には、コンパイラによって警告メッセージが出力されます。
MP taskloop プラグマは、現在のブロック内にある次の for ループに適用されます。Sun ANSI/ISO C によって並列化された for ループに入れ子は存在しません。
MP taskloop プラグマは、for ループを並列化するように指示します。
不規則なフロー制御や、一定しない増分による繰り返しを持った for ループに対しては、正当な並列化を実行できません。たとえば、setjmp、longjmp、exit、abort、return、goto、labels、break を含んだ for ループは並列化に適しません。
特に重要なこととして、繰り返し間の依存性を持った for ループでも、明示的に並列化できる点に注意してください。すなわち、このようなループに対して MP taskloop プラグマが指定されていると、for ループが並列化に適していないと判断されないかぎり、単にこの指示に従って並列化を実行してしまいます。このような明示的な並列化を行なった場合は、不正確な結果が発生しないかを確認してください。
1 つの for ループに対して serial_loop または serial_loop_nested と taskloop の両方のプラグマが指定されている場合には、最後の指定が優先的に使用されます。
次の例を考えてみましょう。
#pragma MP serial_loop_nested for (i=0; i<100; i++) { # pragma MP taskloop for (j=0; j<1000; j++) { ... } } |
この例では、i ループは並列化されませんが、j ループは並列化されます。
#pragma MP taskloop maxcpus (プロセッサ数) は、指定が可能であれば、現在のループに対して使用されるプロセッサの数を指定します。
maxcpus に指定する値は正の整数でなければいけません。maxcpus が 1 であれば、指定されたループは直列に実行されます。なお、maxcpus を 1 に指定した場合には、serial_loop プラグマを指定したことと同等になる点に注意してください。また、maxcpus の値か PARALLEL 環境変数のどちらか小さい方の値が使用されます。環境変数 PARALLEL が指定されていない場合には、この値に 1 が指定されているものとして扱われます。
1 つの for ループに複数の maxcpus プラグマが指定されている場合には、最後に指定された値が優先的に使用されます。
ループに使用される変数は、private、shared、reduction、または readonly のどれかに分類されます。1 つの変数は、これらの種類のうち 1 つにのみ属します。変数の種類を reduction または readonly にするには、明示的にプラグマで指示しなければいけません。#pragma MP taskloop reduction および #pragma MP taskloop readonly を参照してください。変数を private または shared にするには明示的にプラグマを使用するか、または次のスコープの規則に基づいて決まります。
スレッド private 変数は、for ループのある繰り返しを処理するためにそれぞれのプロセッサが専用に使用する値を保持します。別の言い方をすれば、for ループのある繰り返しでスレッド private 変数に割り当てられた値は、for のループの別の繰り返しを処理しているプロセッサからは見えません。これに対して shared 変数は、for ループの繰り返しを処理しているすべてのプロセッサから現在の値にアクセスできる変数のことです。ループのある繰り返しを処理しているプロセッサが shared 変数に代入した値は、そのループの別の繰り返しを処理しているプロセッサからでも見ることができます。共有変数を参照しているループを #pragma MP taskloop 指令によって明示的に並列化する場合には、値の共有によって正確性に問題が起きないことを確認しなければいけません (競合条件の確認など)。明示的に並列化されたループの共有変数へのアクセスおよび更新では、コンパイラによる同期はとられません。
明示的に並列化されたループの解析において、変数がスレッド private と shared のどちらであるかを決定するために、次の「デフォルトのスコープの規則」が使用されます。
変数がプラグマによって明示的に分類されていない場合には、その変数がポインタまたは配列として宣言されていて、かつループ内では配列構文を使用して参照しているかぎり、その変数はデフォルトで shared 変数として分類されます。これ以外の場合は、スレッド private 変数として分類されます。
ループのインデックス変数は常にスレッド private 変数として扱われ、また常に storeback 変数です。
明示的に並列化された for ループ内で使用されているすべての変数を、shared、private、reduction、または readonly として明示的に指定し、「デフォルトのスコープの規則」が適用されないようにしてください。
コンパイラは、共有変数に対するアクセスの同期を一切実行しないので、たとえば、配列参照を含んだループに対して MP taskloop プラグマを使用する前には、十分な考察が必要になります。このように明示的に並列化されたループで、繰り返し間でのデータ依存性がある場合には、並列実行を行うと正しい結果を得られないことがあります。コンパイラによって、このような潜在的な問題を検出し、警告メッセージを出力することもできますが、一般的にこれを検出することは非常に困難です。なお、共有変数に対する潜在的な問題を持ったループでも、明示的に並列化を指示されると、コンパイラはこの指示に従います。
#pragma MP taskloop private (スレッド固有変数)
このプラグマは、現在のループでスレッド固有変数として扱われる必要のあるすべての変数を指定するために使用します。ループで使用されている別の変数は、それ自体が明確にshared、readonly、または reduction であることが指定されていないかぎり、デフォルトのスコープの規則に従って、shared またはスレッド private のどちらかに分類されます。
スレッド private 変数は、ループのある繰り返しを処理するためにそれぞれのプロセッサが専用に使用する値を保持します。別の言い方をすれば、ループのある繰り返しを処理しているプロセッサによってスレッド private 変数に代入された値は、そのループの別の繰り返しを処理しているプロセッサから見ることはできません。スレッド private 変数には、ループの繰り返しの開始時に初期値は代入されず、繰り返し内で最初に使用される前に、その繰り返し内で値が代入されなければいけません。値が設定される前にその値を参照するように明確に宣言されたスレッド private 変数を持つループを実行すると、その動作は保証されません。
#pragma MP taskloop shared (共有変数リスト)
このプラグマは、現在のループでスレッド shared 変数として扱われる必要のあるすべての変数を指定するために使用します。ループで使用されている別の変数は、それ自体が明確にスレッド private、 readonly、storeback、または reduction であることが指定されていないかぎり、デフォルトのスコープの規則に従って、shared またはスレッド private のどちらかに分類されます。
shared 変数とは、ある for ループの繰り返しを処理しているすべてのプロセッサから現在の値を見ることのできる変数のことです。ループのある繰り返しを処理しているプロセッサが shared 変数に代入した値は、そのループの別の繰り返しを処理しているプロセッサからでも見ることができます。
#pragma MP taskloop readonly (読み取り専用変数リスト)
readonly 変数は、ループの繰り返しで変更されない共有変数の特殊なクラスです。変数を読み取り専用として指定すると、ループの繰り返しを処理しているそれぞれのプロセッサに対して、個々にコピーされた変数値が使用されます。
#pragma MP taskloop storeback (ストアバック変数リスト)
このプラグマは、現在のループで storeback 変数として扱われる必要のあるすべての変数を指定するために使用します。
storeback 変数とは、ループの中で変数値が計算され、その値がループの終了後に使用される変数のことです。ループの最後の繰り返しにおける storeback 変数の値が、ループの終了後に利用可能になります。このような変数は、その変数が明示的な宣言やデフォルトのスコープ規則によってスレッド固有変数となっている場合には、この指令を使用して明示的に storeback 変数として宣言するとよいでしょう。
なお、storeback 変数に対する最終的な戻し操作 (ストアバック操作) は、明示的に並列化されたループの最後の繰り返しにおいて、その中で実際に storeback の値が変更されたかどうかには関係なく実行される点に注意してください。すなわち、ループの最後の繰り返しを処理するプロセッサと、storeback 変数の最終的な値を保持 ているプロセッサとは、異なる可能性があります。次の例を考えてみましょう。
#pragma MP taskloop private(x) #pragma MP taskloop storeback(x) for (i=1; i <= n; i++) { if (...) { x=... } } printf (“%d”, x); |
前述の例では、printf() 呼び出しによって出力される storeback 変数 x の値は、i ループを直列に実行した場合の出力値とは異なる可能性があります。なぜならば、明示的に並列化されたループでは、ループの最後の繰り返し (すなわち i==n のとき) を処理し、x に対してストアバック操作を行うプロセッサは、現在最後に更新された x の値を保持するプロセッサとは同じでないことがあるからです。このような潜在的な問題に対し、コンパイラは警告メッセージを出力します。
明示的に並列化されたループでは、配列として参照される変数を storeback 変数としては扱いません。したがって、このような変数にストアバック処理が必要な場合 (たとえば、配列として参照される変数がスレッド固有変数として宣言されている場合) には、その変数を ストアバック変数リストに含める必要があります。
#pragma MP taskloop savelast
このプラグマは、ループ内のすべてのスレッド固有変数をストアバック変数として扱うために使用します。このプラグマの構文を次に示します。
#pragma MP taskloop savelast
各変数をストアバック変数として宣言するときには、それぞれのスレッド固有変数をリストするよりも、この形式が便利であることがよくあります。
#pragma MP taskloop reduction (list_of_reduction_variables) このプラグマは、縮約変数リストにあるすべての変数が、そのループに対して reduction 変数として扱われるために使用します。reduction 変数とは、ループのある繰り返しを処理している個々のプロセッサによって、その値が部分的に計算され、最終値がすべての部分値から計算される変数のことをいいます。reduction 変数リストにより、そのループが縮約ループであることをコンパイラに指示し、適切な並列縮約用のコードを生成できるようにします。次の例を考えてみましょう。
#pragma MP taskloop reduction(x) for (i=0; i<n; i++) { x = x + a[i]; } |
ここでは変数 x が (sum) 縮約変数であり、i ループが (sum) 縮約ループになっています。
Sun ISO C コンパイラには、指定されたループのスケジューリングを戦略的に制御するために、taskloop プラグマと同時に使用するいくつかのプラグマが用意されています。このプラグマの構文を次に示します。
#pragma MP taskloop schedtype (スケジューリング型)
このプラグマによって、並列化されたループをスケジュールするためのスケジューリング型を指定することができます。スケジューリング型には、次のいずれかを指定できます。
static
static スケジューリングでは、ループのすべての繰り返しが、そのループを処理するすべてのプロセッサに均等に配分されます。次の例を考えてみましょう。
#pragma MP taskloop maxcpus(4) #pragma MP taskloop schedtype(static) for (i=0; i<1000; i++) { ... } |
前述の例では、4 個のプロセッサが、ループの繰り返しを 250 ずつ処理します。
self [(chunk_size)]
self スケジューリングでは、ループのすべての繰り返しが処理されるまで、固定された回数の繰り返しチャンクサイズを、そのループを処理するそれぞれのプロセッサで処理します。オプションの chunk_size には、使用するチャンクサイズを指定します。chunk_size は、正の整定数か、もしくは整数型の変数でなければいけません。変数の chunk_size が指定された場合は、そのループを開始する前に、その変数が正の整数値であるかどうかが評価されます。最小チャンクサイズが指定されていない場合、もしくは、この値が正でない場合、チャンクサイズはコンパイラによって決められます。次の例を考えてみましょう。
#pragma MP taskloop maxcpus(4) #pragma MP taskloop schedtype(self(120)) for (i=0; i<1000; i++) { ... } |
前述の例では、ループを処理するそれぞれのプロセッサに割り当てられる繰り返し数は、割り当て順に解釈すると次のようになります。
120、120、120、120、120、120、120、120、40。
gss [(min_chunk_size)]
guided self スケジューリングでは、ループのすべての繰り返しが処理されるまで、可変数の繰り返し (「最小チャンクサイズ」) を、そのループを処理するそれぞれのプロセッサで処理します。オプションの min_chunk_size を指定すると、可変なチャンクサイズが最低でも min_chunk_size になるように設定されます。min_chunk_size は、正の整定数か、もしくは整数型の変数でなければいけません。変数の min_chunk_size が指定された場合は、そのループを開始する前に、その変数が正の整数値であるかどうかが評価されます。最小チャンクサイズが指定されていない場合、もしくは、この値が正でない場合、チャンクサイズはコンパイラによって決められます。次の例を考えてみましょう。
#pragma MP taskloop maxcpus(4) #pragma MP taskloop schedtype(gss(10)) for (i=0; i<1000; i++) { ... } |
前述の例では、ループを処理するそれぞれのプロセッサに割り当てられる繰り返し数は、割り当て順に解釈すると次のようになります。
250、188、141、106、79、59、45、33、25、19、14、11、10、10、10。
factoring [(min_chunk_size)]
factoring スケジューリングでは、ループのすべての繰り返しが処理されるまで、可変数の繰り返し (「最小チャンクサイズ」) を、そのループを処理するそれぞれのプロセッサで処理します。オプションの min_chunk_size を指定すると、可変なチャンクサイズが最低でも min_chunk_size になるように設定されます。min_chunk_size は、正の整定数か、もしくは整数型の変数でなければいけません。変数の min_chunk_size が指定された場合は、そのループを開始する前に、その変数が正の整数値であるかどうかが評価されます。最小チャンクサイズが指定されていない場合、もしくは、この値が正でない場合、チャンクサイズはコンパイラによって決められます。次の例を考えてみましょう。
#pragma MP taskloop maxcpus(4) #pragma MP taskloop schedtype(factoring(10)) for (i=0; i<1000; i++) { ... } |
前述の例では、ループを処理するそれぞれのプロセッサに割り当てられる繰り返し数は、割り当て順に解釈すると次のようになります。
125、125、125、125、62、62、62、62、32、32、32、32、16、16、16、16、10、10、10、10、10、10