並列度の抽出

上の疑似アルゴリズムを見てもわかるように, 一つの を求める処 理は, ※が満たされている限り全てを並列に行なって良いため, これを処理の 単位として並列化するのが自然であり, 今回我々が実装した並列アルゴリズム では, 実際にそれを行なっている. を求める処理はさらに細かく, 各 を求める処理に細分化され, これらの間の並列性を抽出する(つ まり, 異なるkに対して, 異なるプロセッサを割り当てる)可能性もある. し かし後に述べるようにオーバーヘッドを考えるとこれを行なうべきかどうかは 自明ではない.

※を満たすために, を求める際に, 「 と が求 まるまで待つ」という生産者消費者同期を行なった上で, データが到着しだい それらを用いて を求める. 最初に異なるkに対する を, 逐次に処理するversionを示す. 疑似コードで書くと図5.4のようになる.

ただし, 上の5行目,

foreach i < k < j

に関して, kを処理する順序は, [2] において提案されている順序づけで, 以下のようで あるとする.

つまり,i < k < jなるk全てに対して を計算するが, その時に k = (i+j)/2付近のkから順に始め, 両端, つまり, や を最後に求めるようにする.

上のアルゴリズムにおいて, の要素としては,

となり, であるものは排除している. これは同じ記号を に複数 入れないようにするための処理を, を求める時点で行なっている ことになる. その結果, 最終的に に入らないものはいち早く捨てら れ, 無駄なデータの生成(集合をlistで表現する場合には, cons)がさけられ, かつ, を にmergeする時に, 余分な検査がいらなくなる. これは複数のkに対する処理を逐次的に行なうことに依存しており, kのルー プを並列化したい場合には変更の必要がある.