繰返し処理と並列実行

要点と定義

繰返し処理は、決められた範囲のデータに同じ処理を順に適用する制御構造です。制御変数の初期値、終了条件、更新幅を決め、各回でどのデータを読むか、どこへ書くかを追うと処理を理解しやすくなります。繰返しの範囲を分けて複数スレッドに割り当てる場合も、分割後の各処理が正しい結果を保つかを確かめます。

各反復が異なる配列要素だけを読み、異なる要素だけに書き込むなら、反復同士は独立しやすく、並列実行に向きます。一方、ある反復が別の反復の更新する要素を参照すると、実行順序によって読み取る値が変わります。逐次実行と同じ結果を保証するには、共有データの読書きの依存関係を調べます。

たとえば、反復番号ごとに result[i] だけを書き、left[i] と right[i] だけを読む処理は、添字が重ならない限り並列化しやすい例です。これに対し、隣の要素を読む処理では、別の反復がその要素を更新する可能性があります。読み取りと書き込みが競合すると、どちらが先に実行されるかで結果が変わり得ます。

配列の添字を別の配列から得て書き込む場合も、添字の値を確認します。分割した反復が書き込む先の集合が互いに重ならなければ、書き込みの競合を避けられます。同じ要素を複数スレッドが更新する可能性があれば、更新順序次第で結果が定まらないことがあります。

繰返しの中で合計値を蓄積するときは、処理中の入力の位置と、合計を格納する位置を区別します。たとえば箱詰めの処理では、入力行の重量を、現在の箱の合計重量に加算します。入力の行番号と箱の行番号を取り違えると、別の箱の合計を更新したり、誤った重量を加えたりします。

終了条件が「重量が基準以上、または個数が上限に達したとき」であれば、条件は論理和です。どちらか一方を満たした時点で終了します。両方を満たす必要があると解釈して論理積にすると、片方だけ先に満たした場合に終了できません。基準を「以上」とするか「等しい」とするかも区別します。

条件式やカウンタでは、値を更新する前後のどちらで判定するかが重要です。ファイルから1バイトを読み込んだ後、読み込み総数 cnt は、そのバイトの位置より1大きくなります。位置 from 以降を表示する条件は、この関係を考慮して cnt > from と判定します。表示用の現在の組のバイト数 pos は、1増やした後に幅と比較します。

ビット演算と論理演算は目的が異なります。ビット単位の AND は、対応するビットを比較して一部のビットを取り出す演算です。たとえば値 0x6D に 0x0F をビット単位で AND すると、下位4ビットの値 0x0D が得られます。論理 AND は条件の真偽を組み合わせ、その結果を真または偽にします。数値の下位桁を取り出す用途には使えません。

適用条件と例

並列化する前に、各反復が読み書きする要素を列挙します。たとえば out[i] = x[i] + y[i] なら、反復ごとに異なる out[i] へ書き込み、同じ添字の x と y を読むため、各反復の対象が重ならない範囲では独立しています。これに対し out[i] = out[i+1] + x[i] では、ある反復が読む要素を別の反復が書き換え得ます。並列実行で更新が先行すると、逐次実行で想定した値と異なる値を読む可能性があります。依存関係がある場合は、そのまま範囲を分割してよいとは限りません。