IEICE Trans - 線分展開法を拡張した多層グリッドレス配線手法

線分展開法を拡張した多層グリッドレス配線手法

久保田　和人   石川　拓也   佐藤　政生   大附　辰夫

誌名
電子情報通信学会論文誌 A   Vol.J76-A    No.3    pp.410-420
発行日: 1993/03/25
Online ISSN:
DOI:
Print ISSN: 0913-5707
論文種別: 論文
専門分野: VLSI設計技術
キーワード:
レイアウト設計,  VLSI配線,  PWB配線,  グリッドレスルータ,

本文: PDF(772.8KB)>>

あらまし:
電子回路の逐次配線手法として，配線が通過可能な領域を格子状に分割し，その格子を用いて配線を行う迷路法が広く用いられてきた．しかし，近年においては非常に複雑なレイアウト設計規則を扱う必要が生じてきており，迷路法のように格子を用いる手法では対応しきれなくなってきている．これに対処する一つの手法として，格子を用いない配線手法“グリッドレスルータ”の研究が行われてきている．また，プロセス技術の進歩によりLSIの配線においても3層以上を考慮する必要が生じている．そこで，本論文では，3層以上の多層配線を行う格子構造に基づかない配線手法を提案する．本手法は，改良線分展開法に基づく手法であり，従来の配線手法では扱いにくかった複雑な設計規則に対応することができる．また，設計者のニーズに応じた多様な配線パターンを得ることが可能である．本手法は領域全体に対する図形的な前処理が不要であり，O（klog² n）の時間で径路を発見する．このとき必要なメモリはO（n＋k）となる．ここでnは配線領域内の障害物を表す線分の総数，kはその中で径路探索時に探索される線分数である．