対話型2点問配線プログラムの開発

概要

論文の詳細を見る
人手レイアウト設計は今日でも必要不可欠であり、特にアナログLSIのレイアウト設計は大部分を人手で行なっているのが現状である。人手レイアウト設計では配線に要する時間の占める割合が大きい。従って、人手レイアウトを行なう場合、配線の効率化は設計時間の短縮にとって極めて効果的である。しかし、これまでに実験用化されている自動配線プログラムのほとんどは対話的な指定ができなかったり、レイアウト以外に回路図や接続情報を必要とするため、人手レイアウトに適用するのは難しい。そこで、我々は、人手レイアウト設計効率化のための対話型2点間配線プログラム(以下、2点間ルータ)を開発し、レイアウトエディタから呼び出すことのできる。コマンドとして実現した。2点間ルータは、ユーザが対話的に指定する2点間の一層配線を自動生成するものであり、オプションとして認配線の途中経路や、配線が可能な範囲や、配線を禁止する領域をユーザが指定することもできる。これらの指定をすることにより、ユーザである設計者は、人手で行なうのと同じぐらい柔軟に配線を行なうことができる。2点間配線のアルゴリズムは大別すると、迷路法線分探索法、線分展開法、タイル探索法などがある。このうち、迷路法は計算時間とメモリを大量に消賀する。これは対話処理を行なうには致命的である。線分探索法の場合、混雑したレイアウトでは迷路法よりも計算時間が長くなる。線分展開法とタイル探索法は共に、経路が存在すれば必ず配線可能であるし、計算時間やメモリ便用量もそれほど大きくない。タイル上探索法は、配線領域を長方形分割し対長方形探索により配線経路を見つけるものである。タイル探索法ではデータとして基本的に長方形しか必要としないので、インプリメンテーションが容易である。このため、我々は配線アルゴリズムにタイル探索法を採用した。特に、2点間ルータでは、高速処理を実現するために、長方形探索の各時点で始点からの経路長が最短の長方形を選択するアルゴリズムを用いた。これは、グリーティなアルゴリズムであり、最短経路を必ずしも保証しないが、経路長の計算を各長方形について一回しか行なわないので、計算時間が短くなる。この緒果、2点間ルータは、約100素子からなる回路ブロックに対しても10秒以内で配線可能であり、大規模回路に対しても適用可能である。
一般社団法人情報処理学会の論文
1993-03-01

対話型2点問配線プログラムの開発

スポンサーリンク

概要

著者

関連論文

スポンサーリンク