配線可能性検証
Routability Checking

詳細配線と概略配線

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

概略配線と詳細配線

配線可能性検証とは?

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

配線可能性検証の基本

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

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

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

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

ちょっとしたアイデア

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

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


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

水平垂直方向配線の場合

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

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


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

アルゴリズムの重要性

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