JPH06203104A - アナログ大規模集積回路のレイアウトコンパクション方法 - Google Patents

Abstract

(57)【要約】 【目的】 無効領域を削減した詳細配置・詳細配線を決
定でき、面積の小さいレイアウトパターンを得ることが
できると共にコンパクション時に配線面積を削減できる
アナログＬＳＩのレイアウトコンパクション方法を提供
する。 【構成】 素子の初期配置及び初期配線を所定のグラフ
に表現し（ステップＳ１）、グラフを維持しながらグラ
フ中の所定の位置に存在するノ−ドから順次注目して移
動する（ステップＳ２〜Ｓ９）ことによりコンパクショ
ンを行なって無効領域を削減した詳細配置及び詳細配線
を決定する（ステップＳ１０）。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、バイポーラプロセスに
よるアナログ大規模集積回路（ＬＳＩ）の機能ブロック
のレイアウトパターンを設計自動化できるレイアウトコ
ンパクション方法に関する。

【０００２】

【従来の技術】アナログ回路のレイアウト設計は、電気
的特性に対する制約が多く、自動化が困難であるため、
人手により行なわれてきた。

【０００３】しかし、近年の回路の大規模化、設計期間
の短縮化に伴い、その自動化が強く望まれており、これ
までにも従来のディジタルＬＳＩを対象にした自動配置
配線手法にアナログ回路特有の電気的特性等による制約
条件を組み入れた自動配置手法「アナログセル自動配置
手法」（電子情報通信学会１９８９年秋期全国大会、１
９８９−９）が報告されている。

【０００４】更に、回路設計者によって作成された回路
図に基づいて素子の相対位置を決定し、縦方向の配線を
考慮してコンパクションを行なう「二次元コンパクショ
ン手法を応用したアナログ素子配置手法」（電子情報通
信学会１９８９年秋期全国大会、１９８９−９）も報告
されている。しかし、このように縦横すべての配線作業
の終了前にコンパクションを行なうと、コンパクション
後の素子配置に対しての未配線の結線処理が困難とな
る。

【０００５】また、全ての配線を考慮したコンパクショ
ン手法としては、Ｘ方向・Ｙ方向の一次元コンパクショ
ンを交互に繰り返すことにより疑似的に二次元コンパク
ションを実現する手法「バイポーラアナログＬＳＩのブ
ロック内レイアウトＣＡＤシステム」（電子情報通信学
会技術研究報告ＶＬＤ９０−２３、１９９０−６）が報
告されている。

【０００６】

【発明が解決しようとする課題】しかしながら、上述し
た従来の方法では、素子の形状と初期配置、初期配置さ
れた素子を接続するための全ての配線についての初期配
線が予め与えられた場合に、初期配置・初期配線に基づ
いて二次元コンパクションを行ない、無効領域を削減し
た詳細配置・詳細配線を決定して、面積の小さいレイア
ウトパターンを得ることができないという問題点があっ
た。

【０００７】また、上述した従来の方法では、コンパク
ション時に配線面積を削減することができないという問
題点があった。

【０００８】本発明の目的は、上記従来の方法における
問題点に鑑み、無効領域を削減した詳細配置・詳細配線
を決定でき、面積の小さいレイアウトパターンを得るこ
とができると共にコンパクション時に配線面積を削減で
きるアナログＬＳＩのレイアウトコンパクション方法を
提供することである。

【０００９】

【課題を解決するための手段】本発明の目的は、素子の
初期配置及び初期配線を所定のグラフに表現し、グラフ
を維持しながらグラフ中の所定の位置に存在するノ−ド
から順次注目して移動することによりコンパクションを
行なって無効領域を削減した詳細配置及び詳細配線を決
定するアナログ大規模集積回路のレイアウトコンパクシ
ョン方法によって達成される。

【００１０】

【作用】本発明のアナログ大規模集積回路のレイアウト
コンパクション方法では、素子の初期配置及び初期配線
を所定のグラフに表現し、グラフを維持しながらグラフ
中の所定の位置に存在するノ−ドから順次注目して移動
することによりコンパクションを行なって無効領域を削
減した詳細配置及び詳細配線を決定する。

【００１１】

【実施例】以下、図面を参照して、本発明のアナログ大
規模集積回路（ＬＳＩ）のレイアウトコンパクション方
法を詳細に説明する。

【００１２】図１は、本発明のアナログＬＳＩのレイア
ウトコンパクション方法による処理手順の概略を示すフ
ロ−チャ−トである。

【００１３】次に図１のフロ−チャ−トを参照して、本
発明のアナログＬＳＩのレイアウトコンパクション方法
による処理手順の一実施例を詳細に説明する。

【００１４】まず、素子の初期配置、初期配線を平面グ
ラフに表現し（ステップＳ１）、全てのノードについて
『右外部端子ノードからの距離』を算出し（ステップＳ
２）、配置済み境界線を初期設定し（ステップＳ３）、
平面グラフから詳細座標を決定したいノードを一つ選択
し（ステップＳ４）、ノードの詳細座標を決定し（ステ
ップＳ５）、配置済み境界線を更新し（ステップＳ
６）、配置配線済み領域、初期配置・初期配線領域を更
新する（ステップＳ７）。

【００１５】続いて、配置配線済み領域内に配線を追加
し（ステップＳ８）、未処理のノードがあるかないかを
判別し（ステップＳ９）、上記ステップＳ９で未処理の
ノードがあると判別された場合には上記ステップＳ４へ
進み、上記ステップＳ９で未処理のノードがないと判別
された場合には詳細配置配線結果を出力して（ステップ
Ｓ１０）、処理を終了する。

【００１６】ここで、上述したアナログＬＳＩのレイア
ウトコンパクション方法によって処理するレイアウトモ
デルの一実施例を説明する。

【００１７】図２及び図３は、アナログＬＳＩのレイア
ウトパターンを示す模式図であり、特に、図２は実際の
レイアウトパターンに近い図であり、図３は以下に示す
レイアウトモデルに従って簡略化した図である。

【００１８】図２において、機能ブロックの外形は矩形
であり（Ｋ１）、レイアウトパターンは『素子』（Ｋ
２，Ｋ３）、『配線』（Ｋ４）、『ビア』（Ｋ５）で構
成されている。

【００１９】『端子』は結線要求を示す図形で層情報と
座標を持つが、レイアウトパターンではない。また、
『端子』には、機能ブロックの外部との接続を示す『外
部端子』（Ｋ６）と、『素子の端子』（Ｋ７）とがあ
る。

【００２０】外部端子位置は機能ブロック辺上であれば
任意である。また、端子間の結線は、垂直線分及び水平
線分からなる折れ曲がり線である『配線』（Ｋ４）、
『配線分岐点』（Ｋ８）、『ビア』（Ｋ５）で表現され
る。

【００２１】結線は二層以上を用いてなされ、配線はそ
の端点と折れ曲がり点の座標、そして層情報をもつ。そ
して、配線分岐点は座標と層情報をもつ。

【００２２】ビアは座標と、どの層を接続しているかの
情報をもち、電源の幅広配線は機能ブロックの上下端に
第一層で水平に配線される（Ｋ１０，Ｋ１１）。

【００２３】次に、上述したアナログＬＳＩのレイアウ
トコンパクション方法による入力の一実施例を説明す
る。

【００２４】アナログＬＳＩのレイアウトコンパクショ
ン方法に用いられる入力の種類としては、 （１）機能ブロックの高さ。

【００２５】（２）素子サイズ、素子形状、素子の端子
位置。

【００２６】（３）外部端子位置。

【００２７】（４）設計規則。

【００２８】（５）素子の初期配置、初期配線情報。

【００２９】の５種類が有る。

【００３０】図４及び図５に示すように、素子の初期配
置、初期配線情報は以下の条件により平面グラフに表現
される。

【００３１】ここで、図４は素子の初期配置及び初期配
線情報、図５はそのグラフ表現をそれぞれ示す。図中、
Ｋ１，Ｋ２，Ｋ４，Ｋ５，Ｋ６はそれぞれ、素子ノー
ド、外部端子ノード、ビアノード、分岐点ノード、交差
点ノードを示している。

【００３２】図中、ａ〜ｅは、同一の素子に属する複数
の『素子の端子』を、図５のようにまとめて『素子』の
ノードに対応させても、素子周辺の配線の順序が正しく
表現できることを示している。また、ノードは素子・外
部端子・ビア・配線の分岐点・層が異なる配線の交差点
であり、層情報及び座標情報を持つ。エッジは配線であ
り、層情報を持ち、配線の折れ曲がりはグラフ表現しな
い。更に、１本のエッジは１本の配線を表現し、エッジ
は交差しない。

【００３３】次に、図６〜図１７を参照して、図１のフ
ロ−チャ−トにおける主要ステップの処理内容を詳述す
る。

【００３４】始めに、図６〜図８を参照して、上記ステ
ップＳ２の処理内容を詳述する。

【００３５】図６〜図８は、『右外部端子ノードからの
距離』の算出例を順を追って示した図である。

【００３６】まず、機能ブロックの右辺に位置する外部
端子に対応する外部端子ノードを距離０で探索済みとす
る（ステップＳ２ａ）。但し、該当する外部端子がない
場合は、上下辺に位置する外部端子のうち、ｘ座標が最
も大きい即ち最も右寄りの外部端子に対応する外部端子
ノードを距離０で探索済みとする。

【００３７】続いて、ｎ←０として設定し（ステップＳ
２ｂ）、ＶＣＣ、ＧＮＤの幅広線に対応するエッジ以外
のエッジで距離ｎのノードに連結するすべての未探索ノ
ードに距離（ｎ＋１）をあたえて探索済みとし（ステッ
プＳ２ｃ）、ｎ←ｎ＋１として設定し（ステップＳ２
ｄ）、未探索のノードが残っていれば上記ステップＳ２
ｃへ進む（ステップＳ２ｅ）。

【００３８】次に、図９及び図１０を参照して、上記ス
テップＳ３の処理内容を詳述する。

【００３９】図９は配置済み境界線の初期状態を示し、
図１０はある中間状態を示す。

【００４０】上記ステップＳ３では、機能ブロックの左
辺に位置する外部端子に対応する外部端子ノードがすべ
て左に、しかもそれ以外のノードはすべて右にくるよう
設定する。また、配置済み境界線がエッジを切断する箇
所をリスト構造に登録する。そして最上位のエッジ切断
箇所はＶＣＣ、最下位のエッジ切断箇所はＧＮＤにそれ
ぞれ設定する。

【００４１】続いて、図１１〜図１５を参照して上記ス
テップＳ４の処理内容を詳述する。図１１〜図１３は選
択の過程を示す図であり、図１１は中間状態におけるノ
ードの候補を示す図で、候補には探索の順に通し番号が
ふられている。

【００４２】図１２は各候補のノードの『境界線と交差
するエッジ数』を示す図である。

【００４３】また、図１３は各候補のノードの『境界線
と交差しないエッジ数』を示す図である。

【００４４】図１４及び図１５はコンパクションのある
中間状態を説明するための図である。選択されるノード
と配置済み境界線の関係を、図１４は平面グラフの表現
で、図１５はレイアウトパターンの模式図でそれぞれ示
している。

【００４５】最上位のエッジ切断箇所に注目し（ステッ
プＳ４ａ）、配置済み境界線に沿って注目箇所から時計
回りにエッジを探索して、次のノード乃至エッジ切断箇
所に注目し（ステップＳ４ｂ）、注目しているのがノー
ドであれば『境界線と交差するエッジ数』と『境界線と
交差しないエッジ数』をそれぞれ算出する（ステップＳ
４ｃ）。

【００４６】 （境界線と交差するエッジ数） （探索通過回数）−１ （境界線と交差しないエッジ数） （エッジ総数）−（境界線と交差するエ ッジ数） 続いて、最下位のエッジ切断箇所に到達するまで上記ス
テップＳ４ｂへ戻って処理を繰り返す（ステップＳ４
ｄ）。但し、注目しているのがエッジ切断箇所であれ
ば、探索方向を逆転してからステップＳ４ｂへ進む。

【００４７】そして、最下位のエッジ切断箇所に到達す
れば以下の手順で候補を選択する（ステップＳ４ｅ）。

【００４８】『境界線と交差するエッジ数』が最も多い
ノードを候補とする（ステップＳ４ｆ）。

【００４９】また、候補が複数ある場合は『境界線と交
差しないエッジ数』が少ないノードを候補とする。それ
でも複数ある場合は『右外部端子ノードからの距離』が
遠いノードを候補とする。更にそれでも複数ある場合
は、先に探索したノードを候補とする。

【００５０】候補のノードについて以下のチェックを行
ない（ステップＳ４ｇ）、（条件を満たしておれば）次
に詳細座標を決定するノードとして採用する。また、
（条件を満たしていなければ）このノードの上下のエッ
ジ切断箇所を最上位のエッジ切断箇所、最下位のエッジ
切断箇所とする、新たな探索区間を設定して、かつ、こ
のノードを対象からはずして上記ステップＳ４ａへ戻っ
て候補選択を行なう。

【００５１】次に、上記ステップＳ５の処理内容を詳述
する。

【００５２】まず、評価関数を計算する（ステップＳ５
ａ）。

【００５３】評価関数は、注目しているノードに対応す
る『素子』乃至『ビア』乃至『配線分岐点』乃至『配線
交差点』をある詳細位置（ｘ，ｙ）に配置した際、 （ａ）配置済み領域の配線切断箇所からの配線が占有す
る面積 （ｂ）その座標に配置することにより無効となる面積 （ｃ）初期値配置のｙ座標からの変移量 （ｄ）初期配置・初期配線領域の各ノードへの仮想配線
長 に重みをつけて足し合わせる関数である。

【００５４】次に、評価関数値のもっとも小さくなる座
標にノードを配置する（ステップＳ５ｂ）。

【００５５】上記ステップＳ８の配置配線済み領域内に
配線を追加する処理においては、図１６は配置済み境界
線更新前、図１７は配置済み境界線更新後の例をそれぞ
れ示す。

【００５６】上述したように、本発明のアナログＬＳＩ
のレイアウトコンパクション方法は、素子の初期配置及
び素子間の初期配線が済んだアナログＬＳＩの機能ブロ
ックのレイアウトデータを対象に、素子の形状と配線領
域の確保と配線面積削減とを同時に考慮して機能ブロッ
ク内の詳細配置及び詳細配線を決定する。

【００５７】即ち、本発明のアナログＬＳＩのレイアウ
トコンパクション方法では、まず、初期配置と初期配線
情報を平面グラフで表現する。このとき、素子、外部端
子、ビア、初期配線の分岐点、初期配線の層の異なる配
線の交差点をノードとし、初期配線をエッジに対応づけ
る。こうして得られるグラフは平面グラフで表現でき
る。この平面グラフを維持して、グラフ中のノードを左
端にあるもの（ｘ座標の小さいもの）から順次注目して
移動することにより、コンパクションを実現する。エッ
ジに相当する配線については、エッジの両端に位置する
ノードのいずれもが移動された時点で、その経路の座標
が決定される。

【００５８】更に、エッジに相当する配線は、エッジの
両端に位置するノードのいずれもが移動された時点でそ
の経路の座標が決定されるので、その２つのうち後で注
目されるほうのノードの移動時に決定されるとも云え
る。この時その配線についての配線領域が小さくなるよ
うノード位置を算出して、配線面積を削減する。

【００５９】

【発明の効果】本発明のアナログ大規模集積回路のレイ
アウトコンパクション方法は、素子の初期配置及び初期
配線を所定のグラフに表現し、グラフを維持しながらグ
ラフ中の所定の位置に存在するノ−ドから順次注目して
移動することによりコンパクションを行なって無効領域
を削減した詳細配置及び詳細配線を決定するので、配置
配線のトポロジーが保存されたコンパクションが可能に
なる。また、素子間のすきまは実際に配線が必要とする
領域だけあけるので無駄がなく、その結果、よりコンパ
クトなレイアウトパターンを得ることが可能となる。

【図面の簡単な説明】

【図１】本発明のアナログＬＳＩのレイアウトコンパク
ション方法の処理手順を説明するためのフローチャート
である。

【図２】本発明のアナログＬＳＩのレイアウトコンパク
ション方法によるレイアウトモデルにおけるレイアウト
パターン説明図である。

【図３】本発明のアナログＬＳＩのレイアウトコンパク
ション方法によるレイアウトモデルを簡略化した説明図
である。

【図４】本発明のアナログＬＳＩのレイアウトコンパク
ション方法による初期配置・初期配線情報の説明図であ
る。

【図５】本発明のアナログＬＳＩのレイアウトコンパク
ション方法による初期配置・初期配線情報から得られる
平面グラフの説明図である。

【図６】本発明のアナログＬＳＩのレイアウトコンパク
ション方法による各ノードの『右外部端子ノードからの
距離』の算出の説明図である。

【図７】本発明のアナログＬＳＩのレイアウトコンパク
ション方法による各ノードの『右外部端子ノードからの
距離』の算出の説明図である。

【図８】本発明のアナログＬＳＩのレイアウトコンパク
ション方法による各ノードの『右外部端子ノードからの
距離』の算出の説明図である。

【図９】本発明のアナログＬＳＩのレイアウトコンパク
ション方法による配置済み境界線、エッジの切断箇所の
初期状態の説明図である。

【図１０】本発明のアナログＬＳＩのレイアウトコンパ
クション方法による配置済み境界線、エッジの切断箇所
の中間状態の説明図である。

【図１１】本発明のアナログＬＳＩのレイアウトコンパ
クション方法によるある中間状態におけるノード選択の
過程の一部であり、配置済み境界線に沿って行なう探索
の経路の説明図である。

【図１２】本発明のアナログＬＳＩのレイアウトコンパ
クション方法による『境界線と交差するエッジ数』を示
している。

【図１３】本発明のアナログＬＳＩのレイアウトコンパ
クション方法による『境界線と交差しないエッジ数』を
示している。

【図１４】本発明のアナログＬＳＩのレイアウトコンパ
クション方法によるコンパクションのある中間状態の説
明図であり、特に、平面グラフと配置済み境界線の関係
の説明図である。

【図１５】本発明のアナログＬＳＩのレイアウトコンパ
クション方法によるその時点における配置済み領域と初
期配置・初期配線領域、及び選択されたノードに対応す
る初期配置・初期配線領域内の素子の説明図である。

【図１６】本発明のアナログＬＳＩのレイアウトコンパ
クション方法による配置済み境界線更新前の説明図であ
る。

【図１７】本発明のアナログＬＳＩのレイアウトコンパ
クション方法による配置済み境界線更新後の説明図であ
る。

Claims (1)

【特許請求の範囲】
1. 【請求項１】 素子の初期配置及び初期配線を所定のグ
   ラフに表現し、該グラフを維持しながら当該グラフ中の
   所定の位置に存在するノ−ドから順次注目して移動する
   ことによりコンパクションを行なって無効領域を削減し
   た詳細配置及び詳細配線を決定することを特徴とするア
   ナログ大規模集積回路のレイアウトコンパクション方
   法。