障害となる既配線の押し退け可能性を考慮した自動配線手法

概要

論文の詳細を見る
ゼネラルエリア配線(general area rouring)では、各ネツトを配線する際、既に引かれている配線が邪魔になって配線できないことが起こる。この時、既配線と短絡を起こす経路をまず見つけ、後に(直後とは限らないが)経路上の既配線を移動させる手法がよく用いられる。これらの手法は大きく2つに分けられる。1つは、配線経路を見つけるときに既配線との短絡を"touch"と"cross"に区別するもの、他の1つは区別しないものである。[Figer]図1は1層の配線問題の例で、細線で区切られた小さなマスがlつの配線グリッドを表す。今、ネットB,Cの既配線が存在し、さらに、ネットAを配線したいとする。破線1の経路はネットCの配線とcrossを起こす経路、2の経路はネットBの配線とtouchを起こす経路である。2の経路を見つければ、ネットBの配線を右側に押し退けるだけで、ネットAを見つけた経路で配線することができる。一般に、touchを起こす経路を見つけた場合、邪魔になっている既配線を押し退けるだけで配線できる可能性が高いが、crossを起こす経路を見つけた場合には、その経路で配線しようとすると、既配線を大幅に移動させなければならず、全ネットを配線できる可能性が低い(既配線を他の層に移動させることも考えられるが、その可能性は層の数が限られていることから低い)。よって、touchとcrossを区別し、crossよりtouchを起こす経路を優先的に見つける方が正しい経路を見つけられる可能性が高いと言える。しかし、図2の問題の場合、touchとcrossを区別しtouchを優先しただけでは(一度の経路探索では)1の経路か2の経路のどちらを見つけるかは分らない。そこで、著者らは押し退け可のtouch (押し退けられる可能性の高い既配線とのtouch)、押し退け不可のtouch(押し退けられる可能性の低い既配線とのtouch)という概念を導入した。図2の1の経路は押し退け不可のtouch、2の経路は押し退け可のtouchを起こす経路である。押し退け不可のtouchより押し退け可のtouchを起こす経路を優先的に見つけることにより、従来何度も経路探索を(例えば、一度見つけた経路を見つけにくくして)繰り返して初めて正しい経路を見つけることができた問題に対して、経路探索の回数を減らすことができ、計算時間を短縮することができる。また、実用的な時間では正しい経路を見つけられず、解けなかった問題に対しても解くことができると期待できる。
一般社団法人情報処理学会の論文
1994-03-07

障害となる既配線の押し退け可能性を考慮した自動配線手法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク