前処理

一つのスタック領域を頂点, 二つのスタック領域が共存不可能な時, 2頂点間 に辺が存在するようなグラフを考えると, 一つのincompatible isletは, この グラフ上のクリーク(完全部分グラフ)に相当する. 一つのクリークを求めるた めには, 空集合から出発して, 順に一つずつ頂点を検査して, 完全グラフであ り続けるならば加えていけば良い. これにかかる手間は, クリークの大きさを L, スタック領域の数をNとしてO(LN)程度である. したがって全体にか かる時間は, 求まったクリークの大きさを として, 程度である. これは 探索に比べてはるかに小さいため, 最初に1台のプロセッサが行なう. 同時に, 各, isletの中のスタック領域をエネルギーの大きい順にソートし, そのislet 中で最大のエネルギーを持つスタック領域を求めておく. 求まった分割は全プ ロセッサにブロードキャストし, 以後の探索では全てのプロセッサがこの分割 をローカルに参照する.