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

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） この発明は、配線処理を実行しながら自動的に調整さ
れるパラメータ値を用いて配線処理がなされる集積回路
の自動配線方法に関する。

（従来の技術） 近年、半導体技術の急激な発展にともなって、集積回
路の大規模化、多機能化が進んでいる。これにより、１
チップには膨大な数の素子が集積化されることになる。

このように、集積回路が大規模化すると、人手による
開発には限界が生じるため、設計等を自動的に行なう各
種のプログラムをツールとして備えたCAD（Computer Ai
ded Design）が多用される。

集積回路を開発するCADツールの１つとして、例えば
集積回路の結線を自動的に行なう自動配線プログラムで
は、プログラムの開発段階にあっては、プログラムが適
用される対象の状態変化を予測してこれ対処することは
不可能であるため、状態変化を決定する要素としてパラ
メータが与えられる。このパラメータは、その値が固定
されておらず、後に実験を行なって必要なデータを収集
し、収集したデータに基づいて調整される。

このようなパラメータを含む自動配線プログラムにあ
っては、同じプログラムであっても、パラメータの値を
変えるだけで、格段に良い配線結果が得られることがあ
る。このため、パラメータの調整にあっては、数多くの
実験を繰り返し行なわなければならず、多大な労力と時
間を要し、極めて困難な作業であった。また、パラメー
タ値は通常平均的なモデルに適合するように調整される
ため、複雑なモデルや条件の変化等によって、パラメー
タ値は再調整が必要となる。

一方、パラメータ値はその調整が不十分であると、プ
ログラムを運用した際に十分に満足のいく結果が得られ
ず、プログラムが有効に機能しないことになる。

（発明が解決しようとする課題） 以上説明したように、集積回路の開発に用いられてい
る従来の自動配線プログラムにあっては、プログラムの
中で設定されるパラメータ値の調整が極めて手間を要す
る作業であるとともに、パラメータ値の最適化は困難で
あった。

また、パラメータ値が調整されてから再調整がなされ
る間は、パラメータ値が最適化されていない固定された
状態でプログラムが運用されるため、良好な配線結果を
安定して得ることはできなかった。

そこで、この発明は、上記に鑑みてなされたものであ
り、その目的とするところは、パラメータ値を自動的か
つ最適に調整することを可能とし、良好な配線結果を得
ることができる集積回路の自動配線方法を提供すること
にある。

［発明の構成］ （課題を解決するための手段） 上記目的を達成するために、この発明は、集積回路の
配線処理をパラメータにより制御して自動的に配線する
際に、前記パラメータは所定範囲内で連続的に変化する
連続パラメータ値を有し、このパラメータ値の中で離散
的に抽出された複数の離散パラメータ値に従って配線決
定処理を実行し、実行された配線決定処理における配線
決定結果を評価基準にしたがって評価し、得られた評価
結果に応じて、前記連続パラメータ値の評価結果を求
め、この連続パラメータ値の評価結果を既に求められた
連続パラメータ値に対応する評価結果に累積更新し、こ
の累積更新された評価結果の中で所定の基準を満足する
パラメータ値ほど選択され易くなるような確率で次の配
線決定処理のパラメータ値を決定するように構成され
る。

（作用） 上記構成において、この発明は、配線処理を実行する
毎に得られる配線処理の評価結果にしたがって更新され
るパラメータ値の中から、評価結果の良いパラメータ値
ほど高い確率で選択される様な条件で選択されたパラメ
ータ値を用いて次の配線処理を行なうようにしている。

（実施例） 以下、図面を用いてこの発明の実施例を説明する。

第１図はこの発明の一実施例に係わる集積回路の自動
配線方法によって集積回路の配線を自動的に行なう装置
の要部構成を示す図であり、第２図は第１図に示す装置
の動作フローチャートである。

第１図に示す実施例の構成では、パラメータの値を予
め設定された配線領域の配線終了毎に配線結果に応じて
更新するようにしている。

第１図において、装置は配線処理部１、配線記憶部
２、出力部３、評価部４、評価値決定部５、評価値記憶
部６、パラメータ値決定部７を備えている。

配線処理部１は、配線処理を行なうために必要な配線
情報及びパラメータ値を入力して、これらの情報にした
がって配線処理を実行する。

この実施例に示す自動配線処理では、第３図に示すよ
うに１つのチップを多数の配線領域21に分割し、各々の
配線領域21を順次配線することによってチップ全体の配
線を完成させるようにしている。また、この実施例に示
す配線処理の手順は、各々の配線領域21における具体的
な配線経路を決定するものである。配線領域21を適宜に
分割する各々の概略配線格子22の内、どの格子を配線が
通過するかを示す概略配線経路は、別の配線プログラム
によって決定される。

配線処理部１は、上述した各々の配線領域における配
線処理を、短形領域の外周に配置された端子間を結線す
る一種の「スイッチボックスルータ」と見なして実行す
る。すなわち、配線処理部１は、配線領域内部の端子間
を線分探索法により逐次結線して配線処理を行なう。

線分探索法等の逐次配線法では、それまでに敷設され
た配線がこれから敷設しようとする配線に妨害を与える
可能性があるといった欠点を有している。特に、配線が
引出されていない端子の近傍に他の配線が敷設された場
合には、配線が引出されていない端子の配線経路は制約
を受け、配線を困難にしている。

このような不具合を解消するために、配線処理部１で
実行される配線処理のルータにあっては、第４図に示す
ように、配線領域21内に配置されたそれぞれの端子31,3
2から“勢力範囲"33,34と称する領域を仮想的に引出
し、配線しようとする端子以外の端子から引出された勢
力範囲を配線禁止領域とするようにしている。このよう
な勢力範囲を設定することによって、配線されていない
端子の近傍に他の配線の接近を抑制して、将来の配線引
出しを容易にするようにしている。

このような勢力範囲において、この実施例では、勢力
範囲の長さをパラメータとし、このパラメータの値が後
述するパラメータ値決定部７から配線処理部１に与えら
れる。ここで、パラメータの値は、例えば配線領域の一
辺の長さに対する割合（％）として与えらる。

したがって、配線処理部１は、１つの配線領域に対し
て、配線情報となるネットリスト、端子の形状と位置、
第４図に示す配線禁止領域35の形状と位置及び、概略配
線結果を入力とし、勢力範囲の長さとして与えられるパ
ラメータ値を変化させながらショート箇所がなくなる
か、あるいは予め設定された配線処理の試行回数に達す
るまで配線処理を繰り返し実行する。

配線記憶部２は、配線処理部１で実行された配線の配
線結果を格納して記憶する。格納された配線結果は出力
部３に与えられる。

出力部３は配線記憶部２から与えられる配線結果を統
合して出力する。さらに、出力部３は後述する評価値記
憶部６に格納されて記憶された内容を出力する。

評価部４は、配線処理部１で実行された配線結果を、
配線結果の良否の判定基準となる“ショート箇所の個
数”を評価項目として評価する。評価部４は、与えられ
たパラメータ値に対して実行された配線処理毎にその配
線結果を評価する。評価結果は評価値決定部５に与えら
れる。

評価値決定部５は、評価部４から与えられる評価結果
にしたがって、試行されたパラメータ値に対してスコア
（評価値）を与える。例えばショート箇所の数をそのま
まパラメータ値に対するスコアとする。したがって、こ
のようなスコアの与え方では、スコアが小さいパラメー
タ値が用いられた配線処理の方が良好な配線結果を得て
いることになる。

また、１つの配線領域に対する配線処理の試行回数、
すなわち試行されるパラメータ値の数は限られているた
め、実際に試行されたパラメータ値に対してのみ評価さ
れてスコアが与えられるのでは、評価が不十分となる。
したがって、パラメータ値は前述したことから、０〜10
0％の範囲で変化する連続量となることに着目して、評
価値決定部５は、実際に試行されなかったパラメータ値
に対するスコアを、試行されたパラメータ値のスコアか
ら例えば線形補間法によって補間するようにしている。

このような補間処理において、試行された最大のパラ
メータ値より大きいパラメータ値及び最小のパラメータ
値よりも小さいパラメータ値を補間する場合には、試行
されたパラメータ値の中で最も近いパラメータ値と同じ
スコアを与える。例えば、１つの配線領域において、30
％のパラメータ値に対するスコア（ショート箇所）が
“3",60％のパラメータ値に対するスコアが“1"である
場合には、30％以下のパラメータ値に対するスコアは
“3",60％以上のパラメータ値に対するスコアは“1"と
なり、30％〜60％のパラメータ値に対するスコアは線形
補間によって第５図に示すように割当られる。

また、評価値決定部５は、１つの配線領域の配線処理
が終了する毎に得られるスコアを、同一のパラメータ毎
に１つの配線領域の配線処理が終了する毎に順次累積し
て、累積スコアを算出する。算出された累積スコアは、
対応するパラメータ値とともに評価値記憶部６に与えら
れる。

評価値記憶部６は、評価値決定部５から与えられる累
積スコアとパラメータ値を格納して記憶する。格納され
た内容は必要に応じて出力部３に与えられるとともに、
パラメータ値決定部７に与えられる。

パラメータ値決定部７は、評価値記憶部６から与えら
れる累積スコアを用いて、次の配線処理におけるパラメ
ータ値を決定する。パラメータ値決定部７は、良い累積
スコアを持つパラメータ値ほど選択され易くなるような
確率でパラメータ値を確率的に選択して決定する。

したがって、累積スコアは小さいほど良い配線結果を
示すことになるので、パラメータ値が選択される確率
は、そのパラメータ値の累積スコアの逆数に比例するこ
とになり、パラメータ値が連続量であることから確率分
布として与えられる。このようにして決定されたパラメ
ータ値は、配線処理部１に与えられる。

次に、上記構成における作用を第２図に示すフローチ
ャートを参照して説明する。

まず、試行しようとする各パラメータ値に対して初期
値（例えば“1"）を配線処理部１にセットする（ステッ
プ100）。続いて、配線しようとする配線領域の配線情
報を配線処理部１に入力した後（ステップ110）、試行
回数が“1"にセットされ（ステップ120）、試行回数が
予め設定され最大試行回数と比較される（ステップ13
0）。

試行回数が最大試行回数を越えない場合には、それま
でに得られた蓄積スコアの逆数に比例する確率で次の配
線処理のパラメータ値がパラメータ値決定部７によって
選択される（ステップ140）。ここで、第１回目のパラ
メータ値の選択にあっては、それまでの累積スコアがな
いので、各パラメータ値は均等な確率で選択されること
になる。

選択されたパラメータ値は、パラメータ値決定部７か
ら配線処理部１に与えられ、配線領域の配線処理が、入
力された配線情報及び選択されたパラメータ値に基づい
て配線処理部１で行なわれる（ステップ150）。配線処
理が終了すると、その配線結果が配線記憶部２に格納さ
れて記憶される（ステップ160）。

また、配線結果は評価部５に与えられ、配線結果から
ショート箇所が探し出され、その数が対応するパラメー
タ値とともに評価値決定部５に与えられ、ショート箇所
の個数が試行されたパラメータ値のスコアとして与えら
れ記憶される（ステップ170）。

配線結果の評価において、ショート箇所がある場合に
は、試行回数をインクリメントして（ステップ180,19
0）、上述したステップ130〜ステップ170に示したよう
に、同一の配線領域において、別のパラメータ値が選択
されて配線処理が再び行なわれる。

このように、同一の配線領域においてパラメータ値を
変化させて実行される配線処理にあって、試行回数が最
大試行回数に達するか、あるいは配線結果にショート箇
所がなくなった場合には、それまで試行されたパラメー
タ値に対して得られたスコアから試行されていないパラ
メータ値に対するスコアが補間によって算出される（ス
テップ130,180,200）。算出されたスコアは、それまで
得られた同一のパラメータ値に対応する累積スコアに加
算されて累積され、評価値記憶部６に記憶される（ステ
ップ210）。

このようにして、１つの配線領域における配線処理が
終了して、次の配線領域の配線処理を行なう際には、評
価値記憶部６に記憶された累積スコアに対応するパラメ
ータ値がパラメータ値決定部７に与えられてパラメータ
値が選択され、前述したステップ110〜ステップ210の動
作が実行される。

このようにして、１チップのすべての配線領域におけ
る配線処理が終了すると（ステップ220）、得られた配
線結果を統合して出力部３から出力する（ステップ23
0）。

以上説明した自動配線方法を用いて集積回路の自動配
線を実際に行なった実施例の結果を以下に示す。

上述した自動配線方法が適用されたチップは、5700の
ネットを有し、546の配線領域に分割されて配線処理が
行なわれた。

まず、546の配線領域のうち無作為に抽出された４つ
の配線領域21（４種類の線分で示す）でのみ人手により
パラメータ値を０〜100％まで10％刻みに変化させて配
線処理を行なった時のショートの個数を評価すると、第
６図に示すような評価結果が得られた。第６図から明ら
かなように、パラメータ値としては30％の値で最も良好
な結果が得られている。

次に、546のすべての配線領域において、パラメータ
値を“0"すなわち勢力範囲がない場合と、パラメータ値
を上述した評価結果から得られた30％値に固定した場合
と、前述したこの発明の実施例に示したパラメータ値を
自動的に調整する場合の３通りのパラメータ値の設定方
法で配線処理を行なった。このような３通りの配線処理
では、第７図に示すような配線結果が得られた。

第７図において、勢力範囲がない場合にはショート箇
所は324ケ所、パラメータ値を30％に固定した場合のシ
ョート箇所は79ケ所、パラメータ値を自動的に調整する
場合のショート箇所は34ケ所である。このことから、勢
力範囲を設定した方が良好な配線を行なうことができ
る。さらに、勢力範囲の長さを固定してすべての配線領
域の配線を行なうよりも、パラメータ値を自動的に調整
する場合の方が、ショート箇所の個数が半分以下に低減
され、良好な配線結果を得ることができる。なお、配線
処理時間をCPUが動作した時間とすると、パラメータ値
を自動的に調整する方法では、いくつか配線領域におい
て試行錯誤的な配線処理が必要となるので、パラメータ
値を固定した場合よりも配線処理時間は60％程度長くな
っている。

パラメータ値を自動的に調整する場合の方が固定する
場合よりも良い結果が得られることは、それぞれの配線
領域を順次配線処理していく過程において、パラメータ
値の良さが学習によって習得されていることにほかなら
ない。このような学習の効果は、第８図に示すように、
配線処理が終了した配線領域の数が多くなるにしたがっ
て高まり、パラメータ値は最適値へと収束し、パラメー
タの最適値は35％程度であることが第８図から結論され
る。

また、第８図において、全領域配線後の累積スコアの
値は、そのスコアに対応するパラメータ値を固定して全
配線領域を配線した際のショート箇所の個数の予想値を
示すことになる。しかしながら、第７図においては、パ
ラメータ値が０％でのショート箇所数は324,30％で79で
あるのに対して、第８図における予想値は０％で132,30
％で100.2である。

このように実際の値と予想値との間に差が生じるの
は、線形補間によって予想値がすべて平均化されること
に起因している。

以上述べたように、この実施例にあっては、配線領域
の配線処理が終了する毎にパラメータ値の良さが習得さ
れるので、配線処理が終了した配線領域が増えるにした
がって、良好な配線結果を得ることができるパラメータ
値が高い確率で選択されるようになり、ショート箇所の
少ない良好な配線結果を得ることができる。

なお、この発明は、上記実施例に限定されることはな
く、様々な変形例が考えられる。

例えば、評価項目としては、要求されている内容に応
じて、配線長やビアの数あるいは処理時間等を加えるよ
うにしても良い。

また、スコアの与え方としては、ショート箇所がない
場合の方が１つでもある場合に比して、配線結果として
ははるかに良好といえるので、ショート箇所数が“0"の
場合と“1"の場合のスコアの与え方に差を持たせるよう
にしても良い。

さらに、スコアの与え方は、配線領域の特徴を考慮す
るようにしても良い。ゲートアレイやスタンダートセル
を用いた集積回路の配線領域は概ね均質な配線パターン
であるのに対して、記憶回路はその周辺領域とメモリ領
域とで異なる配線パターンを有するので、このような集
積回路の配線には、配線領域の特徴を認識して、その領
域に応じてパラメータ値を変更するようにしても良い。

さらにまた、この発明は、複数のパラメータの値をそ
れぞれ調整するような場合にあっても適用できることは
勿論である。このような場合には、パラメータにおける
相互干渉の有無に応じてスコアの割当を行なうようにす
れば良い。

［発明の効果］ 以上説明したように、この発明によれば、配線処理毎
に得られた配線結果を評価した評価結果にしたがってパ
ラメータ値を自動的に更新するようにしたので、パラメ
ータ値を最適値に収束調整させるようにすることができ
る。

この結果、このようなパラメータ値を用いて配線処理
を行なうことにより、良好な配線結果を得ることができ
る。

【図面の簡単な説明】 第１図はこの発明の一実施例に係わる集積回路の自動配
線方法によって配線処理を行なう装置の構成を示す図、 第２図は第１図に示す装置の動作を示すフローチャー
ト、 第３図は配線領域の概念を示す説明図、 第４図はパラメータ値となる勢力範囲の概念を示す説明
図、 第５図はパラメータ値におけるスコアの与え方を示す
図、 第６図乃至第８図はパラメータを用いて行なわれた配線
処理における配線結果を示す図である。 １……配線処理部、 ２……配線記憶部、 ３……出力部、 ４……評価部、 ５……評価値決定部、 ６……評価値記憶部、 ７……パラメータ値決定部。

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】集積回路の配線処理をパラメータにより制
   御して自動的に配線する際に、前記パラメータは所定範
   囲内で連続的に変化する連続パラメータ値を有し、この
   パラメータ値の中で離散的に抽出された複数の離散パラ
   メータ値に従って配線決定処理を実行し、 実行された配線決定処理における配線決定結果を評価基
   準にしたがって評価し、 得られた評価結果に応じて、前記連続パラメータ値の評
   価結果を求め、 この連続パラメータ値の評価結果を既に求められた連続
   パラメータ値に対応する評価結果に累積更新し、 この累積更新された評価結果の中で所定の基準を満足す
   るパラメータ値ほど選択され易くなるような確率で次の
   配線決定処理のパラメータ値を決定する ことを特徴とする集積回路の自動配線方法。
2. 【請求項２】前記連続パラメータ値の評価結果は、前記
   パラメータ値より得られた評価結果を補間して求めるこ
   とを特徴とする請求項１記載の集積回路の自動配線方
   法。