JPS63225868A - グリツドレス配線経路決定方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［概　要］ 本発明は、グリッドにとられれず、細かいテクノロジー
に柔軟に対応するため、配線領域を長方形領域に分割し
、各長方形間の連続関係を表すデータを用いて配線経路
を決定し、さらにその配線により変更した配線可能領域
を長方形領域に分割して長方形間の連続関係データを更
新して次の配線経路を決定することを繰り返すように構
成したものである。

［産業上の利用分野］ 本発明はＣＡＤ　（計算機援用設計）技術に係わり、特
に高密度集積回路のレイアウト設計における配線経路決
定に関する。

集積回路のＶＬＳ　Ｉ化に伴い、集積度は一層高密度化
し、回路設計側からの要求である細かいテクノロジーに
対応するには、従来のグリッドを基準とする方法には限
界があり、グリッドに拘束されないグリッドレスの配線
経路決定が要求されつつある。

［従来の技術］ 従来の配線経路決定法の一つである迷路法についての概
略を第１０図に示す。

図は、点Ａと点Ｂを結線する場合を示している。

まず、点Ａから隣接グリッドに対して、順次点Ａからの
距離を示すラベルを付けるラベリングという作業を行う
。

ラベリングは、点Ｂヘラベルが届（か、ラベル付けすべ
きグリッドがなくなるまで行う。

ラベルが点Ｂまで届いたときには、点Ａから点Ｂまでの
経路が存在していることを示す。そこで、付けられたラ
ベルを逆に辿ることにより、点Ａから点Ｂへの最短経路
が見つかる。

図は点Ａと点Ｂの間に何もない単純な場合であるが、こ
の間に障害物（配線禁止領域）があれば、これを迂回し
て迷路を探すように配線経路を探索する。

［発明が解決しようとする問題点］ 従来の配線経路決定手法においては、グリッドへのラベ
ル付けを基本としているので、グリッドレス等の細かい
テクノロジーには、そのままでは対応できないという問
題点がある。　　　　　゛本発明は、このような従来の
問題点を解消した新規なグリッドレス配線経路決定方式
を提供しようとするものである。

［問題点を解決するための手段］ 第１図は、本発明のグリッドレス配線経路決定方式の原
理ブロック図を示す、′ 図において、１は長方形領域分割手段であり、配線可能
領域を長方形領域に分割する。

２は連続関係データ作成手段であり、長方形領域分割手
段１により分割した各長方形領域間の連続関係を示すデ
ータを作成する。

３は配線経路決定手段であり、連続関係データ作成手段
２の作成した連続関係データを辿ることにより、指定さ
れた配線端点から配線端点までの配線経路を決定する。

４は配線作図手段であり、配線経路決定手段３により決
定した配線経路に従って配線を作図する。

上記１〜４の手段による処理を、繰り返し行うことによ
り配線経路を作成する。

［作用］ まず、長方形領域分割手段１により、配線可能領域を長
方形領域に分割し、連続関係データ作成手段２により、
各長方形領域関係の連続関係データを作成し、配線経路
決定手段３により、指定された配線端点から配線端点ま
で長方形領域の連続関係を辿り配線経路を決定し、配線
作図手段４により、この経路に従って配線を作図する。

配線作図手段４による配線の作図が終了したならば、再
び長方形領域分割手段１の処理に戻り、新たに作成した
配線部分について、長方形領域分割を更新し、連続関係
データ作成手段２により長方形領域関係の連続関係デー
タを作成し、配線経路決定手段３により次の指定配線端
点から配線端点までの経路を決定し、配線作図手段４に
より配線を作図する。

以上の処理を指定された点のなくなるまで繰り返し行う
。

この長方形分割を利用することにより、細かいテクノロ
ジーにも柔軟に対応することができる。

即ち、従来のように、配線経路も配線幅もグリッドによ
って規制され、例えば１μのグリッドであれば、配線幅
は１μかその整数倍に決められ、グリッドで配線経路が
決められていたものを、長方形領域内に自由に所望の配
線幅で、斜め方向にも配線することが可能となる。

［実施例］ 以下第２図〜第９図に示す実施例により、本発明をさら
に具体的に説明する。

第２図は本発明の一実施例の処理の流れを示すフローチ
ャートである。

第３図〜第８図は、本実施例による処理を説明するデー
タ例である。

以下、第２図のフローチャートに従い、第３図〜第８図
を参照して本実施例の構成を説明する。

ステップ１：初期状態の長方形データの作成第３図に示
すような初期データから、第４図に示す長方形テーブル
を作成する。第３図において、＋１１は第１層の配線領
域を示し、（２）は第２層の配線領域を示す。第１層に
おける太線で囲まれた領域は配線不能領域である。次い
で、長方形テーブルの各長方形間の接続関係を調べ、第
５図に示す長方形量接続関係テーブルを作成する。長方
形間の接続は、同層の場合は長方形の辺に共有部分があ
るかで判断し、他層間は重ねたとき共有の領域があるか
で判断する。第５図の長方形量接続関係テーブルにおい
て、１は接続ありを示し、Ｏは接続なしを示す。同一長
方形同士はＯとする。

ステップ２：配線端子入力 接続すべき配線の端子の位置を、第６図に示すように入
力し、端子テーブルを作成する。このとき、端子のソー
ス（始点）■とターゲット（目標点）■とを決める。接
続すべき配線の入力が無くなれば、処理を終了する。

ステップ３：同層内検索 ソースを含んでいる長方形から同層内の接続関係を、長
方形量接続関係テーブルによりデータ１の長方形を順次
検索し、ターゲットまでの道があるかを調べる。道が見
付かったらステップ５へ飛び、見付からなかったらステ
ップ４へ進む。第５図に示す例では、ソース■を含んで
いる長方形Ａに接続している同層内の長方形は無いので
、ステップ４へ進む。

ステップ４：他層間検索 ソースを含んでいる長方形から他の層へ接続関係を、長
方形量接続関係テーブルにより検索し、ターゲットを含
む長方形までの道があるかを調べる。道が見付かったら
ステップ５へ進み、見付からなかったら「配線経路なし
」を上げる。

第５図に示す例では、長方形Ａは長方形ａに接続し、長
方形ａは長方形Ｂに接続しているから、Ａ−ａ−Ｂの道
が得られる。

ステップ５：配線経路決定 ステップ３、ステップ４で求まった長方形の道の領域内
での配線経路を決定する。ここでの配線経路決定は、単
純に最短経路（マンハッタン経路）による。即ち、２点
を結ぶ直線を対角線とする長方形の辺を経路とする。第
７図は、このようにして求めた配線経路を示す。図にお
いて、ＯはＶＩＡ（バイア）孔を示す。

ステップ６：長方形データの更新 ステップ５で決定され作成された配線経路に従って、所
定の配線幅を持つ配線領域を作成し、これによって配線
された長方形について、さらに長方形分割を行い、長方
形テーブルと長方形量接続関係テーブルを更新して、ス
テップ３へ戻る。第３図〜第７図に示した例では、第８
図に示すように、長方形Ａを長方形ＡＩ、Ａ２゜Ａ３に
分割し、長方形Ｂを長方形Ｂｌ、Ｂ２゜Ｂ３に分割し、
長方形ａを長方形ａｌｌａ２゜ａ３．ａ４に分割し、長
方形テーブル、長方形量接続関係テーブルを更新して、
ステップ２へ戻る。

以上のようにして、ステップ２〜ステツプ６の処理を繰
り返し、接続すべき配線端子の入力を全部終了すれば、
配線経路決定の処理は終了する。

第９図は、第８図に示した長方形量接続関係テーブルの
データをグラフ表現で示したものである。

第９図において、（ａ）は配線板（１）内の接続関係グ
ラフを示し、（ｂ）は配線板（２）内の接続関係グラフ
を示し、（Ｃ）は配線板（１）と（２）の層間接続関係
グラフを示し、（ｄ）はこれら（ａ）、　（ｂｌ、　（
Ｃ１を併合した接続関係グラフを示す。

前記のステップ３およびステップ４の検索処理は、長方
形量接続関係テーブルに替えて、長方形量接続関係グラ
フを作成して、これを辿って行ってもよい。

［発明の効果］ 以上説明のように本発明によれば、グリッドにとられれ
ない細かいテクノロジーに対応することができ、超高密
度化ＣＡＤに寄与する効果は極めて大である。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図は本発明の一実施例の処理の流れを示す図、 第３図は本発明の一実施例における初期データを示す図
、 第４図は長方形テーブルの例を示す図、第５図は長方形
量接続関係テーブルの例を示す図、 第６図は配線端子位置の入力例を示す図、第７図は決定
した配線経路例を示す図、第８図は更新後のデータを示
す図、 第９図は長方形量接続関係グラフ例を示す図、第１０図
は従来技術による配線経路決定を示す図である。 図面において、 ２は連続関係ｆ−ｙ−ＩＰ作成十匡− ３は配線経路決定手段、 ４は配線作図手段、 Ａ、Ｂ、ａ、Ａ１へＡ３．Ｂｌ〜Ｂ３゜ａｌ−ａ４は長
方形、 ■はソース、　　　　　　　　■はターゲット、をそれ
ぞれ示す。 本発明の原理ブロック図 第１図 入力データ 第　　２　　図 本発明の一実施例（＝おける初期データを示す同第　　
３　　図 第４図　　　　　　　第　５　図 第６図 第７図 第　　９　　図

Claims (1)

1. 【特許請求の範囲】 配線可能領域を長方形領域に分割する長方形領域分割手
   段（１）と、 長方形領域分割手段（１）により分割した各長方形領域
   間の連続関係を示す連続関係データ作成手段（２）と、 連続関係データ作成手段（２）の作成した連続関係デー
   タを辿ることにより、指定された配線端点から配線端点
   までの配線経路を決定する配線経路決定手段（３）と、 配線経路決定手段（３）の決定した配線経路に従って配
   線を作図する配線作図手段（４）を備え、上記各手段（
   １）、（２）、（３）、（４）による処理を繰り返して
   配線を作成するよう構成したことを特徴とするグリッド
   レス配線経路決定方式。