JPS6159752A

JPS6159752A - 配線方法

Info

Publication number: JPS6159752A
Application number: JP59183169A
Authority: JP
Inventors: Itaru Kojima; 小嶋　格; Masaki Hayashi; 正樹林; Hiroshi Yoneda; 米田　浩; Noboru Kubo; 登久保
Original assignee: Sharp Corp
Current assignee: Sharp Corp
Priority date: 1984-08-30
Filing date: 1984-08-30
Publication date: 1986-03-27

Abstract

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

Description

【発明の詳細な説明】〈発明の技術分野〉本発Ｆ！Ｊ４ハ集積回路あるいはプリント基板等におけ
る配線方法の改良に関し、更に詳細には集積回路あるい
はプリント基板等における多数のネット（等電位に結ば
れるべきいくつかの端子の集合）から構成される端子の
集合において、端子が機能セルの外囲上に適当な間隔を
おいて位置しており、そのセルは少くとも配線領域を小
さくするという目的を含°んで配置されている状況で、
配線に必要な領域を極少に保つような配線パターンで各
ネッ゛トの配＃！全行ない得るようにした配線方法に関
するものでらる。

〈発明の技術的背景とその問題点〉近年の半導体加工技術の進歩に伴ない、ＬＳＩチップに
搭載される素子の数も飛躍的に増加している。このよう
なＬＳＩの集積化に伴ない、チップ内の高密度配置、配
線を実現するための自動レイ、アウトシステムが種々開
発されてｈる。

ところでＬＳＩ、プリント基板等の大量の配線を行なう
場合の自動配線方法として現在広く用いられている方法
に２段階配線方法がある。この方法では、配線対象を大
幅に単純化したモデル上で、大まかな配線（グローバル
配線）を行ない、その後に各配線径路の詳細な座標値を
定める配線（詳細配置５）ｔ−行なっておシ、このよう
な２段階に分は次処理を行なうことにより、バランスあ
良い配線、即ち、局所的な配線の集中が生じない配線を
得ている。

このグローバル配線において、従来は単純モデルの作ｒ
ｉ！ｃ（第１段階）、ネットの配線順序の決定（第２段
階）、及びネット毎の配線（第３段階）の手順で行なわ
れるのが一般的であり、本発明に関連する第２及び第３
段階において、まずネットの配線順序を決定する＄２段
階ではネットを囲む最゛小の矩形の面積全ネット中の端
子数で割った値を“配線の自由度”と名付け、この配線
自由度の小さいネットから順次配線全していく方法が提
案されている。

ま几ネット毎の配線を行なう第２段階では２点間を迷路
法、線分探索法等で結ぶ方法が基本であシ、その具体的
な方法としては、即に配線された端子または配線線分に
最も近い点を選び出して、その点と結線するというのが
一般的である。また他の方法として、ネット中の全端子
を通る径路を、重複全許して設定しておいて、不要な径
路線分を消去していく冗長径路消去法が提案されている
。

しかし、上記したいずれの方法においても、その配線パ
ターンを決定するに際し、多くの手順と時間全装すると
いう問題点を有しておシ、パターン配線の高速化及びニ
ジ良い配線経路の得られる配線方法の提案が望まれてい
た。

く発明の目的〉本発Ｆ！Ａは上記従来の問題点を除去した、グローバル
配線にふけるパターン配線の高速化及びより良い配線経
路の得られる配線方法を提供すること金目的とし、この
目的を達成するため、本発Ｆ！Ｉ４ゆ、回路素子の同電
位に互いに結線されるべき端子の集合として形成された
多数のネットから構成される端子の集合に対して、端子
間の結線が最適配線パターンとなるＩうに上記の各ネッ
トの配線・パターンを決定する配線方法において、上記
のネットまたはこのネットの一部全端子の分布形状に従
って複数のタイプに分類し、この複数のタイプに分類さ
れたタイプに応じて上記のネット毎またはネットの部分
毎の配線順序を定めると共に、上記の分類されたタイプ
のうち、特定の配線パターンによシ、ネットの配線が完
了するようなタイプのネットに関してその配線パターン
を優先的に適用して上記のネットの配線パターン全決定
するようにｊＩｌｔｒｙ、されている。

〈発明の実施例〉以下、図面を参照して本発明の一実施例を詳細に説明す
る。

第１図は本発明に係るグローバル配線方法の概略フロー
を示し、以下に各部分の詳細を説明する。

グローバル配線で川砂る単純化された配線モデルの実現
例を第２図に示す。

第２図において、端子は機能素子セル（以下セルと称す
）】の外囲上に適白な間＠に’Ｊ３いて位置しており、
配線モデル（例えばＬＳＩモデル）ｔ一点線で囲まれた
矩形領域に分割して基板の目状のグリッドで区切られた
グリッドマツプ全形成する。

ここで点線全グリッド線と呼び、グリッドで区切られた
マス目（矩形領域）をウィンド２と呼ぶものとする。　
　　　　゛グリッドマツプの水平グリッドａ３　ａ　ｌｔ！セル列
の中心を通り、垂直グリッド線３ｂは任意の間隔をもっ
てセル行上を通るように引かれる。水平方向の連続した
ウィンドは水平グリッドチャネル４と呼び、水平チャネ
ルに対応している。

グローバル配線はこのグリッドマツプ上で、すベてのネ
ット（等電位に結ばれるべきいくつかの端子の集合）の
配線経路を決定する０すなわち、各々のウィンド２に含
まれる端子はすべてそのウィンド２の中心に置かれてい
るものとし、配線は通過するウィンド２によって記述さ
れる。

ウィンドの各辺には配線容量と配線混雑度金配線自由度
としてそれぞれウィンドの各辺に直交して配線できるネ
ットの最大本数と、実際に各辺に直交して配線されたネ
ットの本数で定義して与え、配線の集中音道ける配線を
行なう際に用い、同じネット名をもつ端子が含まれてい
るウィンド間全配線線分によって連結することによって
配線経路を決定する。

以下、この配線モデルで本発明の配線方法を説明するか
、大きさの全く異なるセル間を配線する際に用いられる
ことの多い、配線領域をチャネルと呼ばれる矩形の集合
とみなし、このチャネル間の接続関係をチャネル制約グ
ラフで表現するような場合でも、本発明を同様に適用す
ることが出来る０ネットのタイプ分け（ｎ２）全てのネットをグリッドマツプ上の端子の位置の分布に
よって、以下の４つのタイプに分類する。

平チャネル１１内で配線できるもの。な右、第８図（ａ
）において１２．１３［セル列、Ｐ、−Ｐ、。ｔｆ電気
的等価端子であり、同図缶）は同図（ａ）の状態をグリ
ッドマツプ上で表現したものであり、１４Ｆｉ水平グリ
フドチヤネルである。

（ｉｔ）タイプ２：第４図（ａ）及び缶）に示すように
、各ネットに含まれる端子は、２つの水平グリッドチャ
ネル１５．１６内に含まれておシ、かつ一方の水平グリ
ッドチャネルに含まれている端子に対し、在するもの。

タイプ３：第５図で示すように、各ネットの端子を２個
以上含むサブネ７　）　Ｓ　１．　Ｓ２．　Ｓｌｌ、・
・・　に分割し九場合、サブネットの幾つかが、以下の
２つの条件を満尺すもの。なお、第５図において２１゜
２２．２３．２４はセル列、２５．２６．２７は水平チ
ャネル、Ｓｌ、Ｓ２．Ｓ３Ｈサブネツトである。

ｌ）タイプ１１またはタイプ２のいずれかである。

２）密度りがある臨界値よシ大きい。

ここで、サブネットの密度りとは、サブネットに含まれ
る端子の数をサブネットの水平方向の長さで割った値の
ことをいう。

タイプ４：上記タイプ以外のもの。

以上の内、タイプｌはネットの配線全行なう場合の最短
経路は１通りであるという特徴金持ち、タイプ２は最短
経路は幾つもあシ、隣シ合う端子間の配線は、上下いず
れの水平グリッドチャネルを用いても同じであるという
特徴を持つ０多くの実験結果によれば、全ネットの４０
〜７０％程度がタイプｌま７’（はタイプ２であること
が確認された。

ネットの配線順序決定（ｎ３）以下の説明では、配ａは混雑音道けて経路を選ぶものと
して説明する。

ネットの配線順序としては、■タイプ１、■タイプ３、
■タイプ４、φタイプ２の順で行ない、各タイプ中では
前述の配線の自由度を用いて、自由度の小さいネットか
ら配線していく。

このタイプ別配線順序を用いることにより、タイプｌは
１通りしか存在しない、その最短経路を通る場合が多く
なり、タイプ３においても、タイプ！と同様の理由から
、タイプ１形のサブネットが最短で配線される可能性が
高められる。

タイプ２はその上下どちらのチャネルを通っても最短経
路か確保できるという性質により、タイプ］、　３．４
の配線で生じ几配線密度の凸凹を平らにするように配線
することが出来、ま几複雑な経路を通ることなしに、換
言すれば配線経路探索にあまり時間金費やすこ七なく、
遠回りもせずに、配線することができる。

以上は、ネット毎配線の場合の配線順序及びその特徴の
説明であるが、配線経路改善の几めに、−産金て配線さ
れ几後に、各ネットの配線を引きはがして再配線を行な
う場合には、■′タイプ４、■′タイプ３、■′タイプ
２、■′タイプｌの順に行な、い、各タイプの中では、
配線の自由度の大きいものから順に再配線を行なう。こ
れは遠回り（最短距離よシも長い配線）を生じることな
く、様々な経路を選ぶことが出来るものから順に再配線
を行なう几めのもので、遠回り配線が少ない方が全体の
配線量が少な（て済むという事実を目指すものである。

友だし、再配線時には、元の経路よりも悪い（混雑し九
ところをより多く通る）経路は発生させないようにして
いる。

ネット毎配線において、上記のネットタイプは配線時の
経路探索時間音大きく減少させることが出来る。

即ち、タイプｌ及びタイプ２のネット、ま７？：ハタイ
ブａ中のタイプ１．２形のサブネットに関して、次のよ
うに高速に配線経路を決定することが出来る。

（ａ）タイプ！ネット、タイプ１形サブネツトについて
、 ■グリッドマツプ上にただ１本の水平線分を割シ曹てる
ことにより、そのネット（サブネット）の全ての配線経
路を決定する。

■上記の■で配線の混雑した部分全通る場合は、左（ま
７ｔは右）から順に隣り合う端子間を結んでいき、混雑
した部分に到達するまでは■と同じ経路をとシ、混雑部
分に関してのみ、マツプの重みを考慮し九線分探索法を
適用し、混雑していない部分を通る遠回り経路を選ぶ。

Ｃ１７）ように配線経路を決定することに工り、上記■
に関しては高速化が図られ、また■に関しても、必要な
所にのみ比較的時間のかかる経路探索全行ない、その他
については左（まｆｃは右）から順に結線するだけで、
最も近い魚業毎回選ぶのと同じ結果が得られる点に関し
て高速化が図られる。

（ｂ）タイプ２、タイプ２形サブネツトについて、■′
グリッ゛ドマップ上で、上下２本の水平線分を割ｌ）◆
２？、結果の良い方を選び、そのネット（サブネット）
の全ての配線経路を決定する。

■′上記の■ヤ混雑した部分を通る場合は、左（７：友
は右）から順に隣シ合う端子間を結ぶ上下２本の最短経
路のうち、混雑していない方を選んでいき、それでも混
雑部分がある場合は、タイプｌと同様に線分探索法を適
用し、混雑していない部分を通る遠回り経路全還ぶ。

このように配線経路を選択決定することにより、上記（
ａ）に記しｔタイプｌと同様に高速化が図られ、かつ経
路を選択する自由金も持つことになる。

上記した本発明の一実施例として配線方法の特徴をまと
めて述べれば次の通りである。

即ち、多数の互いに結ぶべき端子の集合であるネットか
ら構成される端子の集合に対し、端子間を結ぶ配線パタ
ーンに関して定まるような、ある評価関数？最小または
最大にするように各ネットの配線パターンを決定するシ
ステムに右いて、ネットまたはネットの一部全端子の分
布形状にし友がって幾つかのタイプに分類し、この分類
されたタイプに応じて配線順序を定めることにより、ネ
ットまたはネットの部分毎に配線を順次行なう場合に際
し、先に決定した配線パターンか、それ以後に配線する
ネットにとって障害物となり、後者の配線パターンに関
して定まる評価関数値に及ぼす影響が少なくなり、ま友
全て配線し終えた後に、順次ネットま之はネットの部分
毎に配線を引きはがし、再度配線を行なって局所的な配
線の集中（混雑）を避ける場合に際し、全ネットについ
ての配線パターンに関して定まる評価関数の和の値を悪
化することなく配線の混雑全緩和することが可能となり
、また上記の分類されたタイプのうち、特定の配線パタ
ーンにより、ネットの配線が完了するようなタイプのネ
ットに関してはその配線パターンを優先的に適用するこ
とによって、配線に要する手順全大幅に簡略化すること
が出来る心とを特゛徴としている。

〈発明の効果〉以上のように、本発明によれば、ネットま７’Ｃけネッ
トの一部を端子の分布形状にしたがって幾つかのタイプ
に分類し、この分類されたタイプに応じて配線順序を定
めることにより、配線経路の決定処理が単純化され、Ｌ
ＳＩ、プリント基板等の配線経路決定作業の高速化を図
ることが出来る。

【図面の簡単な説明】

第１図は本発明の配線方法の概略フローを示す図、第２
図は本発明に係るグローバル配線で用いる単純化された
配線モデルのグリッドマツプ？示す図、第３６　（ａ）
　、　（ｂ）、第４図（ａ）、　（ｂ）及び第５図はそ
れぞれ本発明にしたがって分類されたネットのタイプ金
説明するための図である。 ■・・・機能素子セル、２・・・ウィンド、３ａ・・・
水平グリッド線、３ｂ・・・垂直グリッド線％４・・・
水平グリッドチャネル、１１・・・水平チャネル、１２
．１３・・・セル列、１４，１５．１６・・・水平グリ
ッドチャネル、２１、２２．２３．２４・・・セル列、
２５．２６．２７・・・水平チャネル、Ｓｌ、Ｓ２．Ｓ
Ｓ・・・サブネット。代理人　弁理士　福　士　愛　彦　（他２名）第１図第２図（ｂ）第３図（ａＬ）Ｃｂ）第４図第５図

Claims

【特許請求の範囲】

１．回路素子の同電位に互いに結線されるべき端子の集
合として形成された多数のネットから構成される端子の
集合に対して、端子間の結線が最適配線パターンとなる
ように上記各ネットの配線パターンを決定する配線方法
において、上記ネットまたは該ネットの一部を端子の分
布形状にしたがって複数のタイプに分類し、上記複数の
タイプに分類されたタイプに応じて上記ネット毎または
ネットの部分毎の配線順序を定めると共に、上記分類さ
れたタイプのうち、特定の配線パターンにより、ネット
の配線が完了するようなタイプのネットに関してその配
線パターンを優先的に適用し、上記ネットの配線パターンを決定するように成したこと
を特徴とする配線方法。
２．前記複数のタイプに分類されたタイプに応じて前記
ネット毎またはネットの部分毎の配線順序を定める段階
は配線し終えた後に、順次ネットまたはネットの部分毎
に配線パターンを引きはがして再度配線を行なって局所
的な配線の集中を避けるように成した段階を含んで成る
ことを特徴とする特許請求の範囲第１項記載の配線方法
。