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

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

Thread 1

Thread 2 through Thread n

while(many_iterations) {

    sequential_computation
    --- Barrier ---
    parallel_computation
}

while(many_iterations) {


    --- Barrier ---
    parallel_computation
}

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

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

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