JPH07122648A - 配線経路処理方法 - Google Patents

Abstract

(57)【要約】 【目的】 本発明の目的は、迷路法の特徴を損なうこと
なく、配線経路処理の高速化を図ることにある。 【構成】 マトリックスマップ１０１に、各格子毎に隣
接する格子への配線可否情報を設定し、設定された配線
可否情報を参照して基点展開を行うことにより、基点展
開処理の高速化を図る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、自動配置配線技術に関
し、例えばゲートアレイ方式やスタンダードセル方式の
半導体集積回路、さらにはＣＡＤ（コンピュータ・エイ
ディッド・デザイン）やＤＡ（デザイン・オートメーシ
ョン）を用いたカスタムＬＳＩの自動配置配線に適用し
て有効な技術に関する。

【０００２】

【従来の技術】半導体集積回路（以下単にＬＳＩとも記
す）の自動レイアウト、すなわち自動配置配線等におい
ては、予めレイアウト設計されたセルを使用して、半導
体基板へのセルの配置並びにセルの端子間の配線などが
行われる。上記セルのレイアウトは、予め設計された回
路図を基に、人手あるいは自動プログラムを介して生成
される。例えばセルレイアウト自動生成プログラムは、
回路図情報と、ＬＳＩの加工プロセス上のレイアウトル
ール、さらにはトランジスタの幅や長さ（Ｗ／Ｌ）とい
った指定情報を基にしてセルの実体パターンを発生す
る。このような実体パターンとして定義されるセルを利
用してＬＳＩを自動レイアウトするには、実体パターン
から認識可能なセルの形状、端子位置、及び配線禁止域
等の情報が必要になる。

【０００３】ところで、ＬＳＩやボード（プリント基
板）における自動配置配線処理方法の代表的なものとし
て、迷路法（Ｌｅｅアルゴリズム）を挙げることができ
る。この迷路法は、配線領域を格子状に分割し、その格
子に配線禁止域を設定し、始点から配線可能な格子を波
状に広げていき、目的点に達したならば、その目的点か
ら逆に経路をたどり経路を決定するようにしている。す
なわち、始点、目的点、及び配線禁止域の情報を、例え
ば図５に示されるようにマトリックスマップ１００にセ
ットし（ステップ１）、上記始点を基点としてこの基点
から各隣接格子への配線可能な格子に、基点コストをイ
ンクリメントしてそれを基点待ちテーブルにセットし
（ステップ２）、目的点に到達していなければ、最小コ
ストを基点待ちテーブルから取出し、それを基点として
再び上記処理を繰返す（ステップ３）。ここで、上記ス
テップ２，３の処理は一つの経路決定されるに当り、数
十万回繰返されるため、どうしても処理時間が長くなっ
てしまう。

【０００４】尚、自動配置配線技術について記載された
文献の例としては、日刊工業新聞社から昭和６２年９月
２９日に発行された「ＣＭＯＳデバイスハンドブック
（Ｐ１５９〜Ｐ１６４）」がある。

【０００５】

【発明が解決しようとする課題】配線経路処理時間を短
縮するための手法として、試行範囲を限定して、この限
定された範囲のみ探索するようにした方式や、目的点に
近づく方向を優先するように基点展開を制御する方式が
考えられる。しかし、それについて本発明者が検討した
ところ、基点の展開個数を絞り込み、無駄な探索を減ら
すことで、高速化を図っており、そのように基点の展開
回数を減らすことは、経路があれば必ずそれを発見する
ことができるという、迷路法の特徴点でもある探索能力
が、ある程度犠牲にされてしまうことが見いだされた。

【０００６】本発明の目的は、迷路法の特徴を損なうこ
となく、配線経路処理の高速化を図ることにある。

【０００７】本発明の前記並びにその他の目的と新規な
特徴は本明細書の記述及び添付図面から明らかになるで
あろう。

【０００８】

【課題を解決するための手段】本願において開示される
発明のうち代表的なものの概要を簡単に説明すれば下記
の通りである。

【０００９】すなわち、配線経路処理方法において、マ
トリックスマップの設定ステップとして、各格子毎に隣
接する格子への配線可否情報を設定し、設定された配線
可否情報を参照して基点展開を行う。

【００１０】

【作用】上記した手段によれば、マトリックスマップの
設定ステップとして、各格子毎に隣接する格子への配線
可否情報を設定し、設定された配線可否情報を参照して
基点展開を行うことは、当該基点展開において、他基点
の参照を不要とし、このことが、基点展開処理の高速化
を達成する。

【００１１】

【実施例】図６には本発明の一実施例方法である自動配
置配線を含むレイアウトの全体的な処理の流れが示され
る。特に制限されないが、本実施例ではＣＡＤ（コンピ
ュータ・エイディッド・デザイン）システムによって自
動配置配線が行われる。

【００１２】ＬＳＩの設計を行う際には、設計に要する
時間や労力の減少を図るため、素子（例えばトランジス
タ）等をチップ上に１個ずつレイアウトするのではな
く、ある程度の論理機能を有する単位ブロック（機能セ
ル）毎のレイアウトを予め完成しておき、これらに基本
セル間のレイアウトを行いつつ、全体チップにおける配
置配線を完成のが、普通とされる。

【００１３】セルレイアウトライブラリ２４の情報は、
ブロック自動配置、ブロック内配置配線、ブロック間配
線のそれぞれの処理で使用され、全体的なレイアウトが
最終的に決定されると、マスクデータに変換され、マス
ク描画データとして保管される。

【００１４】尚、図６にはセルレイアウトライブラリを
専ら人手によって生成する処理の流れも参考として示さ
れている。この場合には、設計者はセルの実体パターン
を見ながら数値の拾い出しなどを行ってセルレイアウト
ライブラリ仕様書を作成し、その後これを見ながらコー
ディングし、それを更にチェックし、必要に応じて修正
してはじめてセルレイアウトライブラリ８０が完成す
る。

【００１５】図６に示される手順に従ってＬＳＩのレイ
アウトを行っていくとき、セルの配置場所に応じて同一
論理のセルを縦長に配置したり横長に配置したりする必
要性が生じた場合に、また、信号の伝播遅延の不揃いや
設計値との相違を補正したりするためにセルのパターン
を配置場所に応じて変更して用いなければならない場合
に、それらの要求を満足するセルが予め用意されていな
いなら、レイアウト途上でセル自動設計プログラムを起
動すると共に、所定の性能パターンを指定することによ
り、必要なセルの実体パターンを作成する。このよう
に、レイアウト途上においてパターンや論理の追加変更
された新たなセルが必要になるとき、言い換えるなら、
レイアウト途上においてパターンや性能の異なるセルを
使い分ける必要があるとき、そのレイアウトライブラリ
は、上記手順を介することにより容易に得られる。

【００１６】本実施例において、端子間を接続するため
の配線経路は、迷路法によって求められる。迷路法を採
用する配線経路処理においては、特に制限されないが、
マトリックスマップを設定する第１ステップと、このマ
トリックスマップに始点、及び目的点を設定する第２ス
テップと、マトリックスマップを参照しながら経路探索
を行う第３ステップと、バックトレースにより経路を決
定する第４ステップと、決定された経路を禁止するため
にマトリックスマップを更新する第５ステップとを含
む。

【００１７】上記第１ステップには、各格子毎にそこか
らの隣接格子への配線可否情報を設定するステップが含
まれる。つまり、一つの格子から隣接格子へ配線可能で
あるか否かの情報が設定される。

【００１８】図１にはそのようにして設定されたマトリ
ックスマップ１０１が示される。特に制限されないが、
そのようなマトリックスマップ１０１は、ＣＡＤシステ
ムに含まれるＲＡＭ（ランダム・アクセス・メモリ）な
どの適宜の記憶装置を利用することによって形成され
る。

【００１９】具体的には、先ず、マトリックスマップ全
体を、各格子毎に全方向配線可能としてイニシャライズ
し、しかる後に、外縁部の格子に対してマトリックスマ
ップの外へ向かう方向を配線不可とする。図１において
は、格子１０〜３３が外縁部に属し、当該格子１０〜３
３において、外側に向かう矢印は削除されている。当該
格子１０〜３３より外部に向けて配線経路が形成される
ことはなく、そのような外側への経路探索が無意味とな
るからである。さらに、配線禁止等の情報を参照して、
対応する格子を配線禁止にするとともに（図１において
ハッチングで示される部分）、それに隣接する格子にお
いて上記配線禁止格子に向かう方向を配線不可とする。
図１では、配線禁止域の周囲の格子において、当該禁止
領域に向かう矢印が削除されている。配線禁止域への経
路探索は無意味となるからである。そのようにしてマト
リックスマップの初期設定が行われる。

【００２０】各格子毎にそこからの隣接格子への配線可
否情報が設定されたマトリックスマップを参照して処理
することによって、基点展開処理の高速化を図ることが
できる。以下、本実施例における基点展開処理を、従来
方式との比較において説明する。

【００２１】例えば、図３及び図４には従来方式による
基点展開処理の流れが示される。図３及び図４におい
て、Ａ，Ａは処理が継続されていることを示している。
従来方式において、一つの基点（Ｘ，Ｙ，Ｚ）が基点待
ちテーブルから取出され（ステップ３０１）、Ｘ方向に
＋１された試行点（Ｘ＋１，Ｙ，Ｚ）が配線可能か否か
の判別が行われる（ステップ３０２）。この判別におい
て配線不可能であると判断された場合には、Ｘ方向に−
１された試行点（Ｘ−１，Ｙ，Ｚ）が配線可能か否かの
判別が行われる（ステップ３０４）。また、上記ステッ
プ３０２の判別において配線可能と判断された場合に
は、その試行点（Ｘ＋１，Ｙ，Ｚ）が基点待ちテーブル
にセットされた後に（ステップ３０３）、上記ステップ
３０４の判別が行われる。そして、上記ステップ３０４
の判別において、試行点（Ｘ−１，Ｙ，Ｚ）が配線不可
能であると判断された場合には、次の判別（ステップ３
０６）へ移り、また、上記ステップ３０４の判別におい
て、配線可能であると判断された場合には、試行点（Ｘ
−１，Ｙ，Ｚ）が基点待ちテーブルにセットされた後に
（ステップ３０５）、ステップ３０６の判別に移行され
る。

【００２２】それ以降、Ｙ方向に＋１された試行点
（Ｘ，Ｙ＋１，Ｚ）が配線可能か否かの判別、及びその
判別結果に応じた基点待ちテーブルセットが行われ（ス
テップ３０６，３０７）、Ｙ方向に−１された試行点
（Ｘ，Ｙ−１，Ｚ）が配線可能か否かの判別、及びその
判別結果に応じた基点待ちテーブルセットが行われ（ス
テップ３０８，３０９）、Ｚ方向に＋１された試行点
（Ｘ，Ｙ，Ｚ＋１）が配線可能か否かの判別、及びその
判別結果に応じた基点待ちテーブルセットが行われ（ス
テップ３１０，３１１）、Ｚ方向に−１された試行点
（Ｘ，Ｙ，Ｚ−１）が配線可能か否かの判別、及びその
判別結果に応じた基点待ちテーブルセットが行われる
（ステップ３１２，３１３）。

【００２３】それに対して本実施例では、図２に処理の
流れが示されるように、ＣＡＤシステムのＲＡＭ等の記
憶装置を利用して形成される基点待ちテーブルから、基
点（Ｘ，Ｙ，Ｚ）が取出され（ステップ２０１）、その
基点（Ｘ，Ｙ，Ｚ）が展開可能か否かの判別が行われ
（ステップ２０２）、この判別において展開可能である
と判断された場合には、つまり、当該基点から隣接する
格子に向けて配線可能であると判断された場合には、展
開可能な点が基点待ちテーブルにセットされ（ステップ
２０３）、当該基点（Ｘ，Ｙ，Ｚ）についての処理が終
了される。基点待ちテーブルにセットされた点は、それ
以降の処理の対象とされる。また、上記ステップ２０２
の判別において展開不可能と判断された場合にも、当該
基点についての処理が終了される。このように、本実施
例での基点展開処理が、図３及び図４に示される従来方
式に比べて著しく簡単化されるのは、本実施例の場合、
各格子毎にそこからの隣接格子への配線可否情報が設定
されたマトリックスマップ１０１を参照して処理するた
め、基点テーブルから取出された基点の１点のみを参照
すれば、それに隣接する格子への配線可否の判別が可能
であり、図３に示される場合のように、試行可能なＸ方
向，Ｙ方向，Ｚ方向のそれぞれについて、個別的にチェ
ックする必要がないからである。換言すれば、上記マト
リックスマップ１０１を参照して基点展開を行うことに
より、他基点の情報を参照すること無しに、隣接格子へ
の配線可否判別が可能となるため、配線経路探索処理の
処理時間を大幅に短縮することができる。

【００２４】上記実施例によれば以下の作用効果が得ら
れる。

【００２５】（１）マトリックスマップ１０１の設定ス
テップとして、各格子毎に隣接する格子への配線可否情
報を設定し、設定された配線可否情報を参照して基点展
開を行うことにより、当該基点展開において、基点から
隣接点への配線可否が直ちに判断でき、他基点の参照が
不要とされるので、配線経路探索処理の高速化を図るこ
とができる。

【００２６】（２）しかも、試行範囲を限定して当該範
囲のみを探索する方式や、目的点方向を優先して探索す
るような方式のように、基点の展開個数を絞り込むこと
によって処理の高速化を図るものではないので、迷路法
の特徴である探索能力を犠牲にしないで済む。

【００２７】（３）全方向配線可能として初期設定し、
各格子毎にそれに隣接する格子のうち、外へ向かう方向
を消去し、配線禁止域、及び当該配線禁止域に隣接する
格子であって当該格子から上記配線禁止域へ向かう方向
を消去する手順によって、マトリックスマップ１０１へ
の配線可否情報の設定を容易に行うことができる。

【００２８】以上本発明者によってなされた発明を実施
例に基づいて具体的に説明したが、本発明はそれに限定
されるものではなく、その要旨を逸脱しない範囲におい
て種々変更可能であることは言うまでもない。

【００２９】例えば、上記実施例において、他の高速化
技術、例えば試行範囲を限定して当該試行範囲のみ探索
する方式や、目的点に近づく方向を優先するように基点
展開を制御する方式を併用するようにしてもよい。

【００３０】また、迷路法を採用する自動配置配線処理
においては、未配線ネットに対して経路探索処理を施
し、もしこの処理で配線経路が発見できないとき、その
障害となる配線を除去した後に再び未配線及び除去した
障害配線について配線処理を行い、その後、再配線前後
の評価値を算出し、有効な方を採用する、という機能が
あり、そのような機能が発揮される場合においても、本
発明は有効である。

【００３１】以上の説明では主として本発明者によって
なされた発明をその背景となった利用分野であるＣＡＤ
（コンピュータ・エイディッド・デザイン）による自動
配置配線について説明したが、本発明はそれに限定され
るものではなく、ＤＡ（デザイン・オートメーション）
を用いた半導体集積回路の自動配置配線に広く適用する
ことができる。

【００３２】本発明は、少なくとも端子間を接続するた
めの配線経路が経路探索によって行われることを条件に
適用することができる。

【００３３】

【発明の効果】本願において開示される発明のうち代表
的なものによって得られる効果を簡単に説明すれば下記
の通りである。

【００３４】すなわち、マトリックスマップの設定ステ
ップとして、各格子毎に隣接する格子への配線可否情報
を設定し、設定された配線可否情報を参照して基点展開
を行うことにより、当該基点展開において、他基点の参
照が不要とされるので、配線経路探索処理の高速化を図
ることができる。また、試行範囲を限定して当該範囲の
みを探索する方式や、目的点方向を優先して探索するよ
うな方式のように、基点の展開個数を絞り込むことによ
って処理の高速化を図るものではないので、迷路法の特
徴である探索能力を犠牲にすることもない。

【図面の簡単な説明】

【図１】本発明の一実施例方法が適用される自動配置配
線処理におけるマトリックスマップの説明図である。

【図２】上記自動配置配線処理における基点展開の流れ
図である。

【図３】上記自動配置配線処理における基点展開と比較
するための従来方式による基点展開処理の流れ図であ
る。

【図４】上記自動配置配線処理における基点展開と比較
するための従来方式による基点展開処理の流れ図であ
る。

【図５】上記自動配置配線処理におけるマトリックスマ
ップと比較するための従来方式によるマトリックスマッ
プの説明図である。

【図６】上記自動配置配線処理を含むレイアウトの全体
的な処理の流れ図である。

【符号の説明】

１０〜３３ マトリックスマップの外縁部に属する格子 ８０ セルレイアウトライブラリ １０１ マトリックスマップ

Claims (3)

【特許請求の範囲】
1. 【請求項１】 マトリックスマップを設定するステップ
   と、このマトリックスマップを参照して配線経路探索を
   行うステップと、この経路探索結果に基づいてバックト
   レースを行うことにより配線経路を決定するステップ
   と、決定された配線経路を配線禁止域として上記マトリ
   ックスマップに反映させるステップと含む配線経路処理
   方法において、上記マトリックスマップの設定ステップ
   は、各格子毎に隣接する格子への配線可否情報を設定す
   るステップを含むことを特徴とする配線経路処理方法。
2. 【請求項２】 上記配線可否情報の設定ステップは、全
   方向配線可能として初期設定するステップと、各格子毎
   にそれに隣接する格子のうち、外へ向かう方向を消去す
   るステップと、配線禁止域、及び当該配線禁止域に隣接
   する格子であって当該格子から上記配線禁止域へ向かう
   方向を消去するステップとを含む請求項１記載の配線経
   路処理方法。
3. 【請求項３】 マトリックスマップを参照して配線経路
   探索を行うステップと、この経路探索結果に基づいてバ
   ックトレースを行うことにより配線経路を決定するステ
   ップと、決定された配線経路を配線禁止域として上記マ
   トリックスマップに反映させるステップと含む配線経路
   処理方法において、上記マトリックスマップは、各格子
   毎に隣接する格子への配線可否情報を含むことを特徴と
   する配線経路処理方法。