並列配線アルゴリズム

本配線プログラムは、線分をプロセスに対応させているので、配線経路探索の
基本アルゴリズムとして、予測線分探索法を採用した。この手法は、線分探索に
”先読み”を加えた逐次配線手法で、二重探索を避けるフラグとバックトラック
などを導入し、経路が存在すれば必ず発見できることを保証している。
本プログラムでは、2種類の並列性を実現している。一つは、複数ネットの同
時配線、もう一つは、“先読み"処理の並列化である。




期待位置の並列計算 


１ネット探索での”先読み”処理の並列化の様子を以下に示す。Sを始点、T
を目標点とする。Sから垂直方向に探索を始める場合、Sを含む未配線領域のラ
イン・プロセスは、自分と直交する同じく未配線領域のライン・プロセスに対し
て、各領域中で目標点に最も近い位置、すなわち期待位置の計算を依頼する(es-
timateメッセージ）。


					- 49 -