配線コストによる伝搬遅延を用いた並列経路探索法

概要

論文の詳細を見る
配線領域を格子状にして, この格子単位で並列処理処理を行う経路探索手法は専用回路化に向いており, 迷路法を用いたL-マシンをはじめとする多くの並列配線マシンで採用されている。VLSI等により専用回路化を行う場合, チップ内にどれだけの配線格子(グリッド)が実装実装できるかは回路規模に依存する。しかし, グリッドサイズが大きくなるにつれてゲート数の制約よりもパッド数の制約が顕著になる場合がある。特に迷路法ベースの経路探索手法では探索波にラベル値を使用して経路探索を行う。ラベル値の比較によりグリッドの更新が行われることから, 高品位の配線経路を生成する配線コストの組み込みが容易であり, また配線グリッドを矩形領域に分割して並列処理または仮想化して処理する場合, 領域周囲の何れがのグリッドのラベル値が概値であれば全体としての経路探索が正しく処理できる特長がある。しかしながら, 1-2アルゴリズム等を使用しても最低2ビットが必要となり, 配線コストを考慮した経路探索法では更に多くのビット数が必要となる。一方伝搬遅延を用いる経路探索では, 各方向に対して1ビットの信号線で探索波を伝搬するため信号線の節約が期待でき, 専用回路化により1クロック毎の伝搬を仮定すると, 探索された配線経路長は探索に要したクロック数で表現できる。この点ではラベル値伝搬と同様であるが, 各グリッドでは最初に到着した探索波が最短経路となるため, 矩形領域分割による仮想化処理は困難である。幸い概略配線処理により特定領域を通過するネットを決定できることかち前述の欠点をカバーできると考えられる。このような背景から本研究では配線コストを探索波伝搬遅延としし表現し, 専用回路による並列処理を考慮した, VLSIやプリント基板における配線経路の並列自動配線処理のための経路探索手法を提案する。迷路法ベースの経路探索において探索波として用いられるラベル伝搬に代わり, 配線コストを遅延で表現した信号の伝搬を探索波とすることにより経路探索を行うものである。
一般社団法人情報処理学会の論文
1997-09-24

配線コストによる伝搬遅延を用いた並列経路探索法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク