配線可能性検証
Routability Checking

詳細配線と概略配線

配線問題は概略配線処理と詳細配線処理に分けて解くことが多いようです．概略配線処理は配線の太さを気にせずに，電線がどこを通るかを決める処理です．詳細配線はその概略的な経路の実際の位置を決める問題です．電線と電線が接触しないように間隔を空けたり，電線そのものの太さを考慮して電線の位置を決めます．

概略配線と詳細配線

配線可能性検証とは？

そこでこのような配線処理を高速に行うためには，概略配線処理をしている段階で，詳細配線へ変換できるかどうかを知ることが重要です．概略配線処理がすべて終わって詳細配線をしたら，配線が実現できなかったということになったら処理をはじめからやり直さなければならなくなってしまいます．そこで，「配線可能性検証」の登場です．配線可能性検証は概略配線から詳細配線へ変換できるかどうかを判定する処理です．概略配線の途中で行えば，いま発見した概略経路は後々無駄になるかどうかを速い段階で知ることができ，配線処理全体を高速に実現できるようになります．

配線可能性検証の基本

配線可能性検証はいたって単純です．端子点や部品（セル）の端点どうしを結ぶ線分について，そこを通過する概略配線の数（フロー）とそこを実際に（詳細配線が）通過できる数（容量）を比較すれば良いのです．フローが容量より大きいときは，その概略配線は詳細配線へ変換することができません．

調べなければならない線分

それでは調べなければならない線分はどれでしょうか？まず一番単純なのはお互いに見える端点どうしを結ぶ線分すべてを列挙することです．しかしこれはものすごい数になるはずです（可視グラフの辺を列挙することと同じ）．

単純な方法で調べなければならないカット
（１点から発生する線分しか表示していません）

ちょっとしたアイデア

もちろん，可視グラフを求めてそのすべての辺を調べてもよいのですが，それはかなり効率が悪そうです．計算機にとっても相当つらい作業になりそうです．人間の場合はやる気も起きないでしょう．それで，ちょっとしたアイデアを適用してみることにしましょう．結果として調べなければならない線分の数をぐっと減らすことができます．その方法は辺に向かい合った点からのチェックは，その点から下ろした垂線に相当する線分だけ調べれば良いことを利用しています．

辺に面した端子点からチェックしなければならない線分

ひとつめのアイデアを適用した時に調べなければならない線分

水平垂直方向配線の場合

さらに，詳細配線が水平または垂直方向のみだけ許される場合はどうなるでしょうか．これもあるアイデアを適用すると，さらに調べなければならない線分の数を減らすことができます．

線分acと線分bcは調べなければならないが，線分pqは調べる必要がない

ふたつめのアイデアも適用した時に調べなければならない線分

アルゴリズムの重要性

このように，ちょっとしたアイデアを加えることで，非常に効率の良い配線可能性検証アルゴリズムを作成することができます．今まで，数日間計算機を動かし続けていた作業が，たったの数秒で終わってしまうのです．計算機がいくら速くなろうともアルゴリズムの効率の良さにはかないません．その意味でアルゴリズムは重要なのです．

1999.09.19.
fmiso@sccs.chukyo-u.ac.jp

配線可能性検証 Routability Checking