JPH04239747A - 集積回路の配線設計方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、集積回路の配線設計方
法に利用され、特に、二つの端子の間の経路を求めると
きに用いる線分探索法に関する。

【０００２】

【従来の技術】従来、集積回路の配線設計段階で用いら
れる線分探索法は、図６に示す処理フローに従い、行わ
れていた。いま、二つの端子としての点Ａと点Ｂの間の
経路を求める場合について考える。

【０００３】点Ａからレベル０の仮線分として、水平お
よび垂直方向の線分を発生する（ステップＳ２１）　。 ステップＳ２１で発生させた線分が点Ｂに到達したか否
かを判定する。到達していれば経路が見出されたことに
なりステップＳ３５へ（ステップＳ２２）　。障害物に
ぶつかっている場合はエスケープ点（障害物を越えられ
て点Ａに最も近い点）を登録する。障害物にぶつかって
いない場合は以後仮線分をたてない（ステップＳ２３）
　。点ＢからステップＳ２１と同様にレベル０の仮線分
を発生させる（ステップＳ２４）　。点Ａからの仮線分
と交差しているか否かを判定する。交差していればステ
ップＳ３５へ（ステップＳ２５）　。ステップＳ２３と
同様にエスケープ点を登録する。 ｉ　を１とする（ステップＳ２６）　。

【０００４】点Ａ側のエスケープ点から障害物を越すレ
ベルｉの仮線分を発生できるか否か判定する。できなけ
れば、経路が見つからなかったので終了し（ステップＳ
２７）　、発生の可能性のある場合はレベルｉの仮線分
を発生する（ステップＳ２８）　。

【０００５】ステップＳ２８で発生した仮線分が点Ｂ側
の仮線分と交差しているか否かを判定する。交差してい
ればステップＳ３５へ（ステップＳ２９）　。交差して
いなければレベルｉ−１の仮線分上にエスケープ点を登
録する（エスケープ点が定義できないときは、いまたて
た仮線分上で障害物とぶつかる直前の点を新たなエスケ
ープ点とする。）（ステップＳ３０）　。点Ｂ側のエス
ケープ点から障害物を越すレベルｉの仮線分を発生でき
るか否か判定する。できなければ、経路が見つからなか
ったので終了（ステップＳ３１）　。発生の可能性のあ
る場合はレベルｉの仮線分を発生する（ステップＳ３２
）　。ステップＳ３２で発生した仮線分が点Ａ側の仮線
分と交差しているか否かを判定する。交差していればス
テップＳ３５へ（ステップＳ３３）　、交差していなけ
ればレベルｉ−１の仮線分上にエスケープ点を登録する
。（エスケープ点が定義できないときは、いまたてた仮
線分上で障害物とぶつかる直前の点を新たなエスケープ
点とする。）ｉをｉ＋１とし、ステップＳ２７へ（ステ
ップＳ３４）　。仮線分を交差点から逆にたどることに
より点Ａと点Ｂを結ぶ経路を構成して（ステップＳ３５
）　、終了する。

【０００７】このようにして、二つの端子間の経路を求
める。この配線方法を全ての端子のペアに対して適用し
、配線設計を行う。

【０００８】図７は図６に示した処理手順により、図４
に示す集積回路について点Ａと点Ｂ間の配線を行った結
果を示す図である。図４および図７において、１は端子
に対応する点を示し、２はマクロなどの障害物を示す。

【０００９】図７において、Ｐｉ　（ｉ＝１〜５）およ
びＱｉ　（ｉ＝１〜４）は、それぞれ点Ａ側および点Ｂ
側におけるレベルｉの仮線分を発生するエスケープ点で
ある。そして、求まった経路を太線で示してある。この
場合仮線分は１１本発生されて、その内の７線分で経路
が構成されている。すなわち、この従来の配線方法は、
仮線分を発生させるときに開始点の距離の最小性を優先
しているため、目標点から遠くなる方向への余分な探索
が行われる。

【００１０】図８は同様に図６に示した処理手順により
、図５に示す集積回路について、点Ａと点Ｂ間の配線を
行った結果を示す図であり、求まった経路は太線で示さ
れる。

【００１１】

【発明が解決しようとする課題】前述のように、従来の
集積回路の配線設計方法で用いられる線分探索法では、
発生させた線分が障害物にぶつかればエスケープ点の候
補の中から開始点に最も近いものを登録し、エスケープ
点から次のレベルの線分を発生することによって経路を
求める。仮線分を発生させるときに目標点の位置を考慮
せず、開始点からの距離のみに基づいているため、障害
物の数が多く、煩雑に位置しているような状況では、多
くの余分な仮線分を発生してしまう場合がある。このと
き、経路の探索に要する処理時間が増加し、さらに、発
生した全ての仮線分のデータを保持するために必要な記
憶容量が増加する課題がある。

【００１２】本発明の目的は、前記の課題を解決するこ
とにより、処理時間を短縮し、データ保持用の記憶容量
を削減できる線分探索法を有する集積回路の配線設計方
法を提供することにある。

【００１３】

【課題を解決するための手段】本発明は、集積回路の配
線設計を行うときに用いる線分探索法として、開始点で
ある端子側から発生させた線分上で、目標となる端子の
位置ならびにその端子に接続している部分的な経路の位
置に近い点を起点とし、探索のための次の線分を発生し
て行き経路を求めることを特徴とする。

【００１４】

【作用】本発明で用いる線分探索法においては、開始点
である端子側から発生させた線分上で、目標となる端子
の位置ならびにその端子に接続している部分的な経路の
位置に近い点を起点とし、探索のための次の線分を発生
して行き、経路を求める。すなわち、従来の開始点に最
も近いエスケープ点を起点として仮線分を発生していく
に対し、目標端子に最も近い点（以下、ターゲット点と
いう。）を起点として仮線分を発生していく。

【００１５】従って、探索は常に目標点に近づくように
行われることになり、仮線分の発生数を少なくして、よ
り距離の短い経路を設定することができ、処理時間を短
縮し、データ保持用の記憶容量を削減することが可能と
なる。

【００１６】

【実施例】以下、本発明の実施例について図面を参照し
て説明する。

【００１７】始めに、本発明における線分探索法におけ
る仮線分を発生させる点の求め方を説明する。

【００１８】いま、レベルｉの仮線分ｒが障害物にぶつ
かっているとする。仮線分ｒが障害物にぶつかる直前の
ｒ上の点をｔ１およびｔ２とする。レベルｉ−１の仮線
分上において、この障害物を越えるような仮線分を発生
できる点の候補の集合をＳとする。レベルｉ＋１の仮線
分が発生できる点の候補の集合Ｔ＝ＳＲ｛ｔ１、ｔ２｝
の中から、ある評価関数ｆ（ｔ、Ｐ）が最小となる点を
ターゲット点と定義する。ここで、ｔは集合Ｔの要素で
あり、Ｐは目標の点である。集合Ｔを候補点集合と呼ぶ
。ターゲット点より次の仮線分を発生させる。

【００１９】図１は本発明の一実施例の処理手順を示す
流れ図である。

【００２０】点Ａからレベル０の仮線分として、水平お
よび垂直方向の線分を発生する（ステップＳ１）。ステ
ップＳ１で発生させた線分が点Ｂに到達したか否かを判
定する。到達していれば、経路が見出されたことになり
ステップＳ１５へ（ステップＳ２）。障害物にぶつかっ
ている場合は評価関数ｆ（ｔ、Ｂ）が最小となるターゲ
ット点ｔを登録する。障害物にぶつかっていない場合は
以後仮線分をたてない（ステップＳ３）。点Ｂからステ
ップＳ１と同様にレベル０の仮線分を発生させる（ステ
ップＳ４）。点Ａからの仮線分と交差しているか否かを
判定する。交差していればステップＳ１５へ（ステップ
Ｓ５）。そして交差していない場合は、ステップＳ３と
同様に、評価関数ｆ（ｔ、Ａ）が最小となるターゲット
点ｔを登録する。ｉを１とする（ステップＳ６）。

【００２１】点Ａ側の候補点集合Ｔが空集合か否かを判
定する。空集合ならば、経路が見つからなかったので終
了し（ステップＳ７）、空集合でない場合は、レベルｉ
の仮線分を発生する（ステップＳ８）。ステップＳ８で
発生した仮線分が点Ｂ側の仮線分と交差しているか否か
を判定する。交差していればステップＳ１５へ（ステッ
プＳ９）。そして交差していない場合は、レベルｉ−１
の仮線分上にターゲット点を登録する（ステップＳ１０
）　。 点Ａ側の候補点集合Ｔが空集合か否かを判定する。空集
合ならば経路が見つからなかったので終了し（ステップ
Ｓ１１）　、空集合でない場合は、レベルｉの仮線分を
発生する（ステップＳ１２）　。ステップＳ１２で発生
した仮線分が点Ａ側の仮線分と交差しているか否かを判
定する。交差していればステップＳ１５へ（ステップＳ
１３）　、交差していない場合は、レベルｉ−１の仮線
分上にターゲット点を登録する。ｉをｉ＋１とし、ステ
ップＳ７へ（ステップＳ１４）。仮線分を交差点から逆
にたどることにより点Ａと点Ｂを結ぶ経路を構成して（
ステップＳ１５）　、終了する。

【００２２】次に、図１に示す処理手順に従って、具体
的に、図４に示す集積回路について、点Ａと点Ｂの経路
を求めることを考える。本発明の方法（ここで、評価関
数ｆを目標点への距離としている）によって求まる経路
、発生した仮線分を図２に示す。図２において、Ｐｉお
よびＱｉは、それぞれ点Ａ側および点Ｂ側におけるレベ
ルｉの仮線分を発生するターゲット点を表してある。 また求まった経路を太線で示している。

【００２３】図２に示すように、本発明の方法では、目
標点への距離が短くなる方向に対して優先的に探索を進
めているため、余分な仮線分を発生していない。具体的
に、図７に示した従来の方法による仮線分の発生は１１
本であったのに対して、本発明の方法では７本である。 さらに、本発明の配線方法の方が折れ曲がり数の少ない
経路を求めることが可能である（従来法では折れ曲がり
が６箇所、本発明の方法では４箇所である）。

【００２４】図３は図５に示すような障害物が存在する
集積回路の場合に、点Ａと点Ｂ間の経路を図１の処理手
順により探索した結果を示す図である。図５は、前述し
た図４に示す場合に比べ、非常に単純である。このよう
な場合においても、図３と従来例の図８を比べると、従
来の方法では、大きく下方に迂回した経路が求まるのに
対し、本発明の配線方法では最短経路を求めていること
が分る。

【００２５】

【発明の効果】以上説明したように、本発明は、目標と
なる端子の位置ならびにその端子に接続している部分的
な経路の位置を考慮することによって、経路探索の過程
で発生させる線分の数を少なく抑えることが可能である
ため、処理時間の短縮化、ならびに記憶容量の削減化を
図ることができる効果がある。

【図面の簡単な説明】

【図１】　　本発明の一実施例の処理手順を示す流れ図
。

【図２】　　実施例による配線結果の一例を示す図。

【図３】　　実施例による配線結果の他の例を示す図。

【図４】　　実施例および従来例の適用対象集積回路の
一例を示す図。

【図５】　　実施例および従来例の適用対象集積回路の
他の例を示す図。

【図６】　　従来例の処理手順を示す流れ図。

【図７】　　従来例による配線結果の一例を示す図。

【図８】　　従来例による配線結果の他の例を示す図。

【符号の説明】

１　　（端子に対応する）点（Ａ、Ｂ）２　　　　障害
物

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　集積回路の配線設計を行うときに用い
   る線分探索法として、開始点である端子側から発生させ
   た線分上で、目標となる端子の位置ならびにその端子に
   接続している部分的な経路の位置に近い点を起点とし、
   探索のための次の線分を発生して行き経路を求めること
   を特徴とする集積回路の配線設計方法。