米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 電気素子 -> 株式会社日立製作所

発明の名称 階層化配線方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平6−45443
公開日 平成6年(1994)2月18日
出願番号 特願平4−193656
出願日 平成4年(1992)7月21日
代理人 【弁理士】
【氏名又は名称】小川 勝男
発明者 菊池 淳 / 小川 泰
要約 目的
本発明は半導体集積回路の自動配線処理において、配線混雑を均一化し、更に最適化アルゴリズムを用いた径路決定処理において、ネット数及びネット通過位置を限定することで処理時間を短縮する階層化手法を提供することにある。

構成
配線領域の4分割を再帰的に繰り返し(105)、4分割領域上でのネットの形状(径路パターン)を決定し(103)、4分割線上でのネットの通過位置を決定する(104)。
特許請求の範囲
【請求項1】配線領域の再帰的な分割を繰り返し、各々の分割階層において、分割線上における同電位の回路端子(以後、ピンと呼ぶ)の集合(以後、ネットと呼ぶ)の径路の通過位置を、最適化アルゴリズムを用いて決定する、半導体集積回路の自動配線方法において、配線領域を縦横同時に4分割し、4つの分割線上でのネットの径路の通過位置を決定する階層化配線方法。
【請求項2】配線すべき各ネットについて4分割された領域を単位とする配線径路形状(以後、径路パターンと呼ぶ)を与え、各ネットは与えられた径路パターンに従い、概径路パターンと交差する分割線上において通過位置を決定する請求項1記載の階層化配線方法。
【請求項3】4分割領域上でネットピンがどの領域に存在しているかの情報から一意に決めることができる、ネットの径路パターンの候補集合に対するポインタを予め用意しておき、実際にはネットピンの位置から、径路パターン候補を容易に引き出すことができる請求項2記載の階層化配線方法。
【請求項4】4つの分割線上における、配線通過可能本数に対する径路パターンの通過本数の割合が均一になるように、各ネットに径路パターンを与える請求項2、または3記載の階層化配線方法。
【請求項5】隣接する分割領域間におけるネットの結び付きの強さ(結合度)を算出する手段を有し、算出された結合度の強い分割領域間の分割線を通過するような径路パターンを選択し、ネットに付与する請求項2、3、または4記載の階層化配線方法。
【請求項6】4分割された領域内でのネットピンの詳細な位置から、配線長を短くするような径路パターンを選択し、ネットに付与する請求項2、3、4または5記載の階層化配線方法。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は半導体集積回路の配線領域を階層的に分割しながら、配線径路を自動的に決定する方法に関する。
【0002】
【従来の技術】従来の配線領域の分割を行なう階層化配線手法では、配線領域の分割数は2で、各分割段階において、最適化アルゴリズムを用いて、分割線上の各ネットの通過位置を決定していた。
【0003】図2(a)の例では、まず、配線領域201の2分割を行ない(同図(b))、分割線207を横切るネット204及び205の分割線207上での通過位置208、209を最適化アルゴリズムを用いて決定する。更に、2分割された配線領域210及び211の2分割を行ない(同図(c))、各々の領域の分割線212、213上でのネット204〜206の通過位置214〜216を208、209の場合と同様に決定する。この配線領域分割及び通過位置決定を、配線領域の大きさが配線領域の分割最小単位203となるまで再帰的に繰り返す(同図(d))ことにより、同図(e)に示すようなネット204〜206の配線径路217〜219を得ることができる。
【0004】
【発明が解決しようとする課題】従来の2分割階層化配線方法では、配線径路が分割順序に依存するという問題があった。図3(a)に示すような、配線混雑部304を含むような配線領域301に配線すべきネットピン302及び303がある例を考える。同図(b)のように配線領域に対して横方向の分割から行ない、分割線305上でのネット通過位置306を決定し、更に縦分割を行ない、分割線307上での通過位置308を決定すると配線径路309は配線混雑部304を通過しない。しかし、同図(c)のように縦方向の分割から始め、分割線310上の通過点311を決定し、更に横分割を行ない、分割線312上での通過点313を決定すると、配線径路314は配線混雑部304を通過せざるを得ない。
【0005】また、図4に示すような例を考える。この場合、同図(a)のように配線領域401の縦分割を行ない、分割線405上での通過位置406を決定すると、このネットピン402〜404の位置関係においては、配線径路407が迂回部408を持ち、配線長が長くなる。しかし、同図(b)のように横分割から始め、分割線409上の通過位置410を決定することによって求められる配線径路411は、迂回部を持たず、配線長も短い。
【0006】更に、従来技術ではネットの通過位置決定に最適化アルゴリズムを使用していることから、実用的な面で処理時間の問題があった。
【0007】本発明の目的は、(1)領域分割順序の依存性をなくし、(2)処理時間を短縮できる、配線方法を提供することにある。
【0008】
【課題を解決するための手段】配線領域を4分割し、各ネットの4分割領域上での径路パターンを割り当てることにより、上記課題を解決する。すなわち、図3(d)に示すように、まず、配線領域301を4分割線315〜318によって4分割し、4分割領域上でのネットの形状(径路パターン)319を割り当てる。次に4分割線315〜318の中から、径路パターン319と交差する4分割線315及び318上でのネットの通過位置320、321を決定する。
【0009】
【作用】本発明によれば、4分割処理、及び径路パターン割り当てを用いることにより、分割順序に依存しない配線径路を得ることが可能となる。例えば、図3(d)では、4分割線315〜318上での配線混雑を各々考慮するため、配線混雑部304を避ける径路パターン318が決定され、配線径路322もこれに従って決定される。
【0010】また、図4(c)に示すように、分割線412で区切られた領域内でのネットピンの位置を考慮して、径路パターン413が割り付けられるために、配線径路414に迂回は無い。
【0011】更に、上記手段により、ネットの通過位置と通過ネットを限定できるため、処理時間の短縮を図ることができる。
【0012】図5(a)に示すように、配線領域501の大きさが横L1、縦L2であるとき、2分割処理では、第1段階での分割におけるネット502の通過位置504は、分割線503の長さL1から探索され、第2段階では分割線505上で長さL2/2の範囲で通過位置506は探索される。一方、同図(b)における4分割処理では、分割線507で分割された4配線領域上での径路パターン508に従い、ネット通過位置511及び512は長さL1/2、L2/2を持つ4分割線509、510上から探索される。
【0013】
【実施例】図1は、本発明による階層化配線処理の流れの一例を示すPAD図である。同図(a)は、処理の大きな流れを、同図(b)は、本発明の一つの技術である径路パターン決定処理の詳細な流れを示している。また、図6は処理の流れの結果を絵で示したものである。
【0014】まず、初期設定101において、配線領域601の大きさ、分割の最小単位602の大きさを設定し、各ネットピン603の位置を分割最小単位領域の座標で置き換える。分割最小単位602は各境界辺に配線の通過可能本数を容量として持っており(以後、単に容量と呼ぶ)、配線は容量を超過して割り付けることはできない。
【0015】与えられた配線領域601の大きさが、分割最小単位602よりも大きい場合(102)、各ネットについて4分割領域上での径路パターン608を、4分割線604〜607上の配線使用率(配線通過可能本数に対する径路パターン通過数の割合)が均一になるように決定する(103、図6(b))。
【0016】更に、図6(c)に示されるように、4分割線604〜607上における各ネットの通過位置609〜613を、最適化アルゴリズム(例えば、線形割り当て法)を用いて決定する(104)。
【0017】配線領域601を、4つの分割領域614〜617に分割し(105、図6(d))、各々の分割領域について、領域の大きさが最小単位となるまで径路パターン決定処理103、ネット通過位置決定処理104を繰り返し行なう。図6では、(e)において、分割領域614〜617上での径路パターン決定106を行なっている。
【0018】分割領域の大きさが最小単位602となったとき、各ネットの配線径路618〜620が求まる(図6(f))。
【0019】次に、径路パターン決定処理103について詳細な説明を行なう。
【0020】径路パターン決定処理103は、4つの処理(ネットグループ化処理106、ネット処理順序決定処理107、径路パターン初期割り付け処理108、割り付け改善処理109)から構成される。
【0021】各処理の説明を図7(a)の問題を用いて行なう。701は配線領域、702はネットピンで、配線すべきもの同士は同じアルファベットで示されている。703〜706は4分割線であり、各々2本の配線を通過させることができるものとする。
【0022】ネットのグループ化処理106では、ネットピンが4つの分割領域のどこに存在するか(ネットピンパターン、図8−804参照)に従って、各ネットを分類し、グループ化を行なう。各ネットグループは、ネットピンパターンに対応した径路パターン候補805を引き出すことができる。図7の例では、ネットaは図8の項番3、ネットbは項番2、ネットcは項番1に分類される。
【0023】次に、ネットの径路パターンの割り付け処理順序を決定する(107)。各ネットグループから引き出される径路パターン候補には、4分割線と径路パターンとの交差数(以後、単に交差数と呼ぶ)の少ない順に、優先順位が付けられている。例えば、図8の項番1のネットグループにおいては、径路パターン804の交差数は、1であるが、805の交差数は3となる。従って、優先順位は、径路パターン804に1、805に2が付与される。一方、項番2では、径路パターン806の交差数、807の交差数、共に2であり、優先順位も共に1が付与される。径路パターン候補間における交差数の差が大きいグループは、先に処理されるべきである。項番1、2、3、4における交差数の差は、各々2、0、1、0である。従って、各々のネットグループの処理順序は、項番1、3、2、4(項番2及び4は同時)となる。この順番は、予め各項番について与えられている(803)。これに従えば、図7の例では、ネットc、ネットa、ネットbの順に処理順序が決定される。
【0024】更に、同一ネットグループ内のネットについては、4分割領域に含まれるネットピンの数から結合度を算出して、処理順序を決定する。図9の例では、同図(a)、(b)共に図8の項番1に分類、グループ化される。しかし、図9(a)のネット902の結合度905は、同図(b)のネット906の結合度907よりも大きい。従って、ネット905は906に先んじて、処理される。
【0025】ネットの処理順序は、このようにネットグループ間、ネットグループ内の2段階処理によって決定される。
【0026】径路パターンの初期割り付け処理108では、先に決められた処理順序に従い、各ネットについての径路パターン707を割り付ける。ここでは、各ネットの径路パターン候補802の中から優先順位の高いものを、4分割線の容量を超過しないように割り付ける。図7の例では、同図(b)が初期割り付け結果を示している。まず、ネットcに804を、次にネットaに径路パターン808を、最後にネットbに806を割り付けた結果である。ここで、4分割線703、704、705、706と交差する径路パターンの数は、各々0(708)、2(709)、2(710)、1(711)である。
【0027】最後に、配線利用率の均一化を図るために、初期割り付け結果に対する改善処理109を行なう。各々のネットに対し、優先順位の同じ径路パターン候補の中に、4分割線の配線利用率が均一化するようなものがあれば、径路パターン候補間の入れ換えを行なうものである。図7(c)に割り付け改善の例を示す。ネットbの初期径路パターン707(806)と同じ優先順位の径路パターン候補807をネットbの改善径路パターン712とすることで、4分割線703、704、705、706における交差数は、1(713)、1(714)、1(715)、2(716)となり、配線利用率が均一化される。
【0028】
【発明の効果】本発明によれば、階層化配線処理において、2分割処理の分割順序の問題を解決することで、自動配線のできないネット(未配線)の数を削減し、未配線の人手による追加工数を削減する。また、2分割処理に比べ、ネット通過位置、通過ネット数を限定することで、処理時間の短縮を図ることができる。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013