kに関する並列化をする場合のデータ/タスク配置

先にも述べた通りkに関して並列化をする際には, 余分なオーバーヘッドが かかる. つまり, 逐次版で行なっている, を求める最中に 最新の を参照しながら重複を除去する, ということができない. そ のかわりに各プロセッサは自分がこれまでに求めた の和をローカ ルに保持し, それを用いて重複を除去し, 最後に全てのプロセッサの結果を mergeする場所で改めて重複を除去しなくてはならない.

このオーバーヘッドを考えると, 単純に一つのkに対して一つのプロセッ サを割り当てることはできない. 我々が現在行なっているのは, j - iの値 がある与えられた閾値(g)よりも大きいものに関して, を半分に分割し, それぞれを1つのプロセッサで行なわせる, というもので ある. つまり一つの を処理するプロセッサは高々二つである. この 場合の, D(i,j)およびC(i,k,j) (それぞれD'(i,j)およびC'(i,k,j) と呼ぶこと)を, 逐次版を用いて示すと以下のようになる. ただし, 全てのi, jに対して二つのプロセッサを割り当てるとしてある.