JPH04336449A - 集積回路の自動配線方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】［発明の目的］

【０００２】

【産業上の利用分野】本発明は、線分展開法を用いた集
積回路の自動配線方法に関する。

【０００３】

【従来の技術】集積回路の自動配線に用いられる方法の
ひとつとして線分展開法が知られている。この線分展開
法は当初は１層配線を想定した配線方法として提案され
たものである。１層配線における線分展開法の論文とし
ては、小島、佐藤、大附著「線分展開法の改良とその評
価」情報処理学会　　設計自動化研究会　　研究報告、
Ｖｏｌ．４８、Ｎｏ．６、ｐｐ．１−８（１９８９年）
がある。

【０００４】線分展開法は、まず配線領域内に配置され
た端子の周辺に補助線分を発生し、これを線分と垂直方
向に端子から離れる方向へ掃引することにより配線領域
内に長方形領域を得る。さらに、この長方形領域の辺上
に新たな補助線分を設け、同様に長方形領域の探索を続
ける。そして、最終的に得られた長方形領域の組み合わ
せによる配線領域内で、端子間を配線している。

【０００５】２層以上の配線領域を探索するには、隣接
する層にも新たな補助線分を発生しなければならない。 このとき、ある層を縦方向の配線用に、他の層を横方向
の配線用に決定して（これを縦横原則と呼ぶ）配線する
のが効率のよい方法である。例えば、２層配線の場合に
は、第１層を横方向専用、第２層を縦方向専用にすると
、線分間の交差が容易となり、先に配線されたものが後
に配線されるものを妨げない。

【０００６】縦横原則に従って線分展開法を実行するに
は、縦方向に探索するための補助線分は縦方向の層のみ
に、横方向に探索するための補助線分は横方向の層のみ
に発生させればよい。このとき発生する補助線分の数は
１層の場合とほとんど変わらず、処理時間に関しても大
きな増加はみられない。

【０００７】しかしながら、縦横原則に従って単純に線
分展開法を適用したのでは、如何なる場合にも縦横原則
に従う径路しか発見できない。例えば第１層を横方向の
配線のみ、第２層を縦方向の配線のみとすると、図２（
ａ）が第１層、（ｂ）が第２層の場合には、縦横原則に
従わない径路が必要なのにも拘らず、これを発見するこ
とができない。従って、このように縦横原則を単純に線
分展開法に応用しても品質のよい配線はできない。

【０００８】そこで、縦横原則に従うか否かに関わらず
、全ての補助線分を同時に各層の配線領域に発生すると
いう方法が考えられる。このときの状態を図４に示す。 図４（ａ）のように、第２層の配線禁止領域２２に向っ
て探索する補助線分３０を発生する。図４（ｂ）のよう
に、補助線分３０が展開した結果、第２層には配線領域
内に長方形領域が得られ、新たな補助線分７１，７２が
発生し、隣接する第１層には新たな補助線分６０，６１
，６２が発生する。

【０００９】ここで、第１層と第２層を接続するビアが
配線禁止領域２２とショートするのを防ぐため、補助線
分６０，６１，６２は長方形領域の内側に発生している
。また、第２層では第１層の補助線分６１，６２に対応
する位置には補助線分７１，７２が発生する。配線禁止
領域２２があるため、補助線分６０に対応する位置には
新たな補助線分は発生しない。

【００１０】このように、縦横原則に従う補助線分３０
，６１，６２が、そうでない補助線分６０，７１，７２
よりも優先的に展開されるような工夫をしてやることで
、比較的縦横原則に従う径路が得られると考えられるが
、この方法には次のような欠点がある。

【００１１】１．発生する補助線分の数が層の数に比較
して多くなり、処理時間、使用メモリの増加が著しい。 ２．単純に縦横原則に従う径路が求められる場合にも多
数の補助線分が発生し、処理に無駄が多くなる。 ３．一度探索した配線領域を二重に探索しないための例
外処理が複雑になり、処理時間の点で不利である。

【００１２】

【発明が解決しようとする課題】このように、従来の線
分展開法では、縦横原則に従う径路しか発見できず、品
質の良い配線が得られないという問題があった。また、
全ての補助線分を同時に各層の配線領域に発生する方法
では、処理時間がかかるという欠点があった。

【００１３】本発明は、上記の問題を解決するため、基
本的には縦横原則に従いながら、例外的に縦横原則に従
わない径路をも短時間で効率的に得ることにより、高性
能な配線処理を行うことが可能な集積回路の自動配線方
法を提供することを目的とする。

【００１４】［発明の構成］

【００１５】

【課題を解決するための手段】上記目的を達成するため
、この発明は、線分展開法を用いて少なくとも２層の配
線を行う際に、前記線分展開法が領域探索のために発生
する補助線分を所定の層に発生し、これを基にした径路
探索を行い、径路探索処理を行った後に、前記所定の層
に隣接する層の配線領域の前記所定の層に発生した補助
線分と対応する位置に新たな補助線分を発生することを
特徴としている。

【００１６】

【作用】本発明は、径路の探索の際に、まずある層に縦
横原則に従った補助線分（優先方向の補助線分）を発生
し、この補助線分と垂直方向に径路探索を行う。このと
き、配線禁止領域によって補助線分の展開ができなけれ
ば、隣接する層の配線領域の対応する位置に縦横原則に
従わない新たな補助線分（非優先方向の補助線分）を発
生している。すなわち、あるレベルの補助線分から隣接
する層へと次レベルの補助線分を発生させ得るとき、縦
横原則に従っている層にまず新たな補助線分を発生させ
、その補助線分が配線領域内に展開できなかった時にの
み、隣接する層に新たな補助線分を発生するようにして
いる。

【００１７】

【実施例】以下に本発明による自動配線方法における線
分展開法を集積回路の自動配線の計算機プログラムに適
用した実施例を説明する。なお、今回の実施例では、開
始点の端子とターゲット点端子は１点で表されている。 また、既に配線がなされていて、新規な配線が禁止され
ている領域は障害物として登録されているものとする。

【００１８】図１は、本発明による自動配線方法の処理
手順を表したフローチャートである。同図において、始
めの３ステップと終わりの３ステップ、すなわち、配線
領域内に開始点を通る補助線分を発生し、記憶領域とな
るヒープに挿入する（ステップ５１）、ヒープから補助
線分を１本とりだす（ステップ５２）、配線領域内で補
助線分を展開する（ステップ５３）、ターゲット点を発
見したか否かをチェックする（ステップ５７）、新たな
補助線分を発生しヒープに挿入する（ステップ５８）、
逆方向探索をして径路を得る（ステップ５９）は、従来
の縦横原則に従う線分展開法と同様である。

【００１９】これ以外のステップ、すなわち、優先方向
の補助線分が展開できなかったときに隣接する層の対応
する位置に非優先方向の補助線分を発生し、ヒープに挿
入するステップ５４，５５，５６が本発明の特徴である
。

【００２０】これらのステップ５４〜５６では、まずス
テップ５３で展開しようとした補助線分が実際に配線領
域内で展開できたかどうかをステップ５４でチェックし
、展開できた場合はステップ５７へ、そうでない場合は
ステップ５５へと続く。ステップ５５ではその補助線分
が優先方向であるかどうかをチェックする。優先方向で
あった場合にのみステップ５６の処理、すなわち隣接す
る層の対応する位置に非優先方向の補助線分を発生しヒ
ープに挿入する処理を行う。その後ステップ５２に戻り
、同様に処理を繰り返す。

【００２１】次に、図２（ａ）、（ｂ）に示すような配
線問題を上記処理手順に従って解決していく実施例を、
図２（ａ）〜（ｄ）および図３（ａ）〜（ｄ）を用いて
説明する。ここで、（ａ），（ｃ）は第１層配線領域、
（ｂ），（ｄ）は第２層配線領域を表している。実際に
は（ａ）と（ｂ）（ｃ、ｄに関しても同様）は重なって
いることになる。なお、この実施例では２層配線を例に
取り上げるが、本発明による自動配線方法はこれに限ら
れるものではなく任意の層数の配線にも勿論適用可能で
ある。

【００２２】図２（ａ），（ｂ）は、探索開始端子１１
と探索のターゲットとなる端子１２、及び第１層配線禁
止領域２１、第２層配線禁止領域２２が示されている。 一般に端子は引き出し可能な層が限定されるが、ここで
は第１層及び第２層のいずれにも引き出し可能であるも
のとする。また第１層を原則として横方向、第２層を原
則として縦方向に用いる縦横原則を採用する。ただし、
径路を発見するためには必ずしもこれに従う必要はない
ものとする。

【００２３】図１に示す処理手順にしたがって径路探索
を開始する。ステップ５１で開始点１１を通り、縦横原
則に従う補助線分３０を第２層に発生し、ヒープ（待ち
行列）に挿入する。ここでは参考のため、非優先方向の
補助線分で後に発生する可能性のある第１層の補助線分
３１も図２（ａ）に示している。次に、ステップ５２で
ヒープから補助線分が取り出される。

【００２４】図２（ｃ），（ｄ）は、ステップ５３にお
ける補助線分３０が第２層の配線領域内を展開し、新た
な補助線分を発生した状態を示す。配線領域内で展開で
きた補助線分３０は、展開済みの状態３２となり、逆探
索の際に用いられる。図２（ｃ）における新たに発生し
た補助線分３０のうち、縦方向のものは優先方向の補助
線分であるが、横方向のものは非優先方向である。第２
層での補助線分３０の展開後、第１層に非優先方向の新
たな補助線分３０が直ちに発生した理由は、図２（ｄ）
のように垂直方向の線分展開をして得られた長方形領域
の輪郭で、障害物に接している部分には新たな補助線分
は発生し得ないので、隣接する層の配線領域の対応する
位置に非優先方向の補助線分３０が発生したためである
。第２層で探索した領域中にターゲット点１２はないの
で、処理を続行する。（以上、ステップ５４，５７，５
８）図３（ａ），（ｂ）は、第１層に発生した補助線分
３０の展開を行い、さらに新たな補助線分を第２層に発
生した状態を示す。図２（ｃ）における縦方向の補助線
分（優先方向である）は全く展開できず、従って第２層
配線領域の図２（ｄ）の点線３１の位置に、非優先方向
の新たな補助線分３０が発生している（図３（ｂ）、ス
テップ５４，５５，５６）。図２（ｃ）での展開領域上
部の横方向の補助線分３０は第１層配線領域を展開し（
図３（ａ））、上記と同様に第２層配線領域に新たな補
助線分３０を発生している（図３（ｂ））。ここでも、
探索した領域中にターゲット点１２はないので、処理を
続ける。

【００２５】図３（ｃ），（ｄ）は、第２層で発生した
補助線分３０の展開を行った結果ターゲット点１２に到
達した状態を示す。図３（ｂ）における縦方向の補助線
分３０が第２層配線領域を展開した結果、ターゲット点
１２を発見している（ステップ５７）。ここから逆探索
をするステップ５９は従来の線分展開法とほぼ同じであ
り、その結果図３（ｃ），（ｄ）に示すような配線径路
４１〜４４が得られる。

【００２６】以上のように、この発明の自動配線方法に
より、縦横原則のみに従っていては発見が不可能な径路
４１，４２を少ない手順で見つけだすことができる。

【００２７】

【発明の効果】以上説明したように本発明によれば、優
先方向の補助線分が展開できないときに、隣接する層に
非優先方向の補助線分を発生している。これにより、縦
横原則に従わない配線をも効率的に求めることができ、
品質の良い配線を短時間で得ることが可能である。

【図面の簡単な説明】

【図１】本発明による自動配線方法の処理手順を表した
フローチャートである。

【図２】図１に示す処理手順に従って行われる配線処理
の様子を示す状態図である。

【図３】図２に続けて行われる配線処理の様子を示す状
態図である。

【図４】隣接する層の配線領域内の相対応する位置に発
生した補助線分を示す透視図である。

【符号の説明】

１１　　探索開始端子 １２　　ターゲット端子 ２１　　第１層配線禁止領域 ２２　　第２層配線禁止領域 ３０　　補助線分 ３１　　非優先方向の補助線分が発生する位置を示す線
分３２　　展開済みの補助線分 ４１〜４４　　配線径路

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　線分展開法を用いて少なくとも２層の
   配線を行う際に、前記線分展開法が領域探索のために発
   生する補助線分を所定の層に発生し、これを基にした径
   路探索を行い、径路探索処理を行った後に、前記所定の
   層に隣接する層の配線領域の前記所定の層に発生した補
   助線分と対応する位置に新たな補助線分を発生すること
   を特徴とする集積回路の自動配線方法。