JPH06102659A

JPH06102659A - マスク・レイアウト生成方法

Info

Publication number: JPH06102659A
Application number: JP25318392A
Authority: JP
Inventors: Nobu Matsumoto; 展松本; Shojiro Mori; 祥次郎森
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1992-09-22
Filing date: 1992-09-22
Publication date: 1994-04-15
Also published as: US5493509A; KR970004102B1; KR940007724A

Abstract

(57)【要約】【目的】この発明の目的は、通常の設計支援装置を使用
して、大規模集積回路のコンパクションを可能とすると
ともに、チップ面積の損失を抑えることが可能なマスク
・レイアウト生成方法を提供することである。【構成】集積回路のマスク・レイアウト１１を示す図形
データを、先ず、複数の縦断線１３に沿って複数の断片
１１_x〜１１_{x +3}に分割した後、それぞれをコンパクシ
ョンし、これらコンパクションした断片１１_x〜１１
_{x +3}全体を複数の横断線１４に沿って複数の断片１１_y
〜１１_{y +3}に分割した後、それぞれをコンパクション
し、これらコンパクションした断片１１_y〜１１_{y +3}を
つなぎ合わせている。したがって、コンパクションは各
断片毎に行うため処理上限が存在せず、大規模なマスク
・レイアウトを現行の設計支援装置によって処理でき
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、集積回路のマスク・
パターン（マスク・レイアウトとも言う）を、例えばＣ
ＡＤ(Computer Added Design) によって生成するマスク
・レイアウト生成方法に関わり、特に、シンボリック・
レイアウトのコンパクション方法に関する。

【０００２】

【従来の技術】一般に、コンパクションあるいはスペー
シングと称する技術は、図８（ａ）に示すような集積回
路のレイアウトにおいて、コンタクト・シンボル８１や
ワイヤ８２等からなる構成要素を移動することにより圧
縮し、図８（ｃ）に示すように、コンタクト・シンボル
８１、８１の相互間隔ｌを、設計ルールが許す限り短縮
した集積密度の高いレイアウトを得たり、設計ルールを
満たしていないレイアウトから、設計ルールを満足する
レイアウトを生成する処理を言う。また、通常、集積回
路のレイアウトは、シンボル（記号）によって表現され
ており、シンボリック・レイアウトと呼ばれている。

【０００３】前記コンパクションは、構成要素を２次元
的に移動させる２次元コンパクションと、１次元的な移
動をｘ、ｙの各方向に対して行う、１次元コンパクショ
ンに大別される。２次元コンパクションは多大な処理時
間を要するため、一般的ではなく、通常は１次元コンパ
クションが用いられている。図８（ｂ）は、図８（ａ）
に示すレイアウトをｘ方向に１次元コンパクションした
結果を示している。同図から明らかなように、１次元コ
ンパクションでは、一度のコンパクションによって、構
成要素のｘ座標、あるいはｙ座標のみが変化し、他方の
座標は変化しない。

【０００４】また、１次元コンパクションは、さらに、
シア・ライン（または、コンプレッション・リッジと称
す）、バーチャル・グリッド、およびコンストレイント
・グラフ（または、レラティブ・グリッドと称す）の３
つの方法に分類され、コンストレイント・グラフが最も
多く用いられている。尚、これら方法の技術的内容につ
いては、本願発明と関係がないため省略する。

【０００５】

【発明が解決しようとする課題】ところで、上記従来の
コンパクションの問題は、大規模なデータ、すなわち、
大規模なシンボリック・レイアウトを扱えないことであ
る。このため、大規模化されてきた集積回路の全チップ
を一括して圧縮することができないものであった。この
理由は、一度に行うべき処理の計算機資源使用量、特
に、主記憶装置の使用量が、処理すべき集積回路の規模
の増大とともに多くなるにも係わらず、主記憶装置の容
量には上限が存在するためである。

【０００６】また、コンパクションを行うソフトウェ
ア、すなわち、コンパクタの規模依存生がオーダ（ｎ）
（以下、Ｏ（ｎ）と記す）より悪いため、これをＯ（ｆ
（ｎ））とすると、コンパクション可能な回路規模の上
限はあまり大きくない。具体的には、通常の設計支援装
置、例えば３２ＭＢ程度の主記憶装置を有するＥＷＳ
（エンジニアリング・ワーク・ステーション）を使用し
た場合、従来の例えばコンストレイント・グラフ法によ
るコンパクタが一度に扱える集積回路の規模は、約１万
トランジスタが限界である。但し、この数値には１オー
ダ程度の誤差が含まれている。現在、大規模集積回路は
数十万トランジスタを含んでいる。このため、１万トラ
ンジスタという数値は、これにくらべると著しく小さい
ものである。

【０００７】このように、従来のコンパクタは、大規模
集積回路を一括処理することが困難であるため、階層的
に処理する方法が提案されている。この階層的処理方法
としては、ボトムアップ法とピッチマッチング法の２つ
がよく知られている。前記ボトムアップ法は、図９に示
すように、シンボリック・レイアウトを複数の断片９
１、９２に分割して下位の階層データとし、これら断片
９１、９２をコンパクションした後に各断片９１、９２
の接続端子をワイヤ９３によって接続する方法である。

【０００８】また、前記ピッチマッチング法は、図１０
に示すように、シンボリック・レイアウトを複数の断片
１０１、１０２に分割し、これら断片１０１、１０２を
接続するワイヤ１０３のピッチを考慮しつつコンパクシ
ョンする方法である。

【０００９】上記階層的処理方法の第１の問題は、別の
階層間あるいは同一の階層の異なるブロックの間の圧縮
が不十分なこと、すなわち、面積損失が生じることであ
る。例えば、図９に示すボトムアップ法の場合、無駄な
配線領域が生じるものである。第２の問題は、インプリ
メントが複雑且つ困難なことであり、このため実用に耐
え得る商用システムは未だ存在していない。

【００１０】従来のコンパクション方法に対する他の問
題点は、パフォーマンス、すなわち、コンパンション処
理の結果が予測困難なことである。特に、従来の方法で
は、シンボルとシンボルの相対位置が元の位置と大きく
異なってしまうおそれがある。この場合、ワイヤの遅延
時間は予想を越えて増大してしまう。したがって、シン
ボルの移動を阻止する何等かの手段をとらない限り、チ
ップのパフォーマンスの予想が困難である。

【００１１】この発明は、上記課題を解決するためにな
されたものであり、その目的とするところは、通常の設
計支援装置を使用して、大規模集積回路のコンパクショ
ンを可能とするとともに、チップ面積の損失を抑えるこ
とが可能なマスク・レイアウト生成方法を提供しようと
するものである。

【００１２】

【課題を解決するための手段】この発明は、上記課題を
解決するため、集積回路のマスク・レイアウトを示す図
形データを複数の第１の断線に沿って複数の第１の断片
データに分割し、これら分割した第１の断片データをそ
れぞれ圧縮処理し、これら圧縮処理した第１の断片デー
タ全体を複数の第２の断線に沿って複数の第２の断片デ
ータに分割し、これら分割した第２の断片データをそれ
ぞれ圧縮処理し、これら圧縮処理した第２の断片データ
をつなぎ合わせている。

【００１３】

【作用】すなわち、この発明は、集積回路のマスク・レ
イアウトを示す図形データを、先ず、複数の第１の断線
に沿って複数の第１の断片データに分割した後、それぞ
れを圧縮処理し、これら圧縮処理した第１の断片データ
全体を複数の第２の断線に沿って複数の第２の断片デー
タに分割した後、それぞれを圧縮処理し、これら圧縮処
理した第２の断片データをつなぎ合わせている。したが
って、圧縮処理は各断片毎に行うため、マスク・レイア
ウトの規模に応じて分割数を増やことにより、処理上限
が存在せず、大規模なマスク・レイアウトを現行の設計
支援装置によって処理できる。また、図形データを断片
データに分割して圧縮するため、シンボル等の移動範囲
は断片データの範囲内である。したがって、チップのパ
フォーマンスの予想が可能である。

【００１４】

【実施例】以下、図面を参照してこの発明の一実施例に
ついて説明する。先ず、この発明のマスク・レイアウト
方法の原理について説明する。

【００１５】図１（ａ）は処理対象としてのシンボリッ
ク・レイアウトを示すものであり、このシンボリック・
レイアウト１１には、ワイヤ１２が設けられるととも
に、複数の縦断線１３、および複数の横断線１４が定義
されている。このコンパクションにおいては、先ず、シ
ンボリック・レイアウト１１を、同図（ｂ）に示すよう
に、複数の縦断線１３に沿って分割し、複数の断片１１
_x〜１１_{x +3}を生成する。

【００１６】次に、前記生成した複数の断片１１_x〜１
１_{x +3}を、例えばコンストレイント・グラフ法によっ
て、同図（ｃ）に示すように、ｘ方向に１次元コンパク
ションを行う。ここで、注意すべきは、圧縮された断片
におけるワイヤ１２の切り口の高さは圧縮により変わら
ないため、断片１１_x〜１１_x+3を合せば、ワイヤ１２
は元通り接続される。

【００１７】次に、コンパクションした断片１１_x〜１
１_{x +3}を合せ、同図（ｄ）に示すように、横断線１４に
沿って分割し、複数の断片１１_y〜１１_{y +3}を生成す
る。この生成した複数の断片１１_y〜１１_{y +3}を、前記
と同一の方法によって、同図（ｅ）に示すように、ｙ方
向に１次元コンパクションを行う。この後、コンパクシ
ョンした断片１１_y〜１１_{y +3}を、同図（ｆ）に示すよ
うに合せると、ワイヤ１２は元通り接続される。

【００１８】以上の処理手順において、縦を横とし、ｘ
をｙとしても処理は可能である。また、縦断線１３は直
線に限定されるものではなく、シンボル・レイアウトの
上端と下端を結ぶ経路であれば、図２に示すように、折
曲部を含む線とすることも可能である。但し、縦断線が
折曲部を含む場合、縦断線と直交する水平部分１３ａに
おいて垂直方向のワイヤ、すなわち、縦断線に沿ったワ
イヤと交わってはならない。また、縦断線はコンタクト
やトランジスタのシンボルを横切ってはならない。横断
線も同様に、シンボリック・レイアウトの左端と右端を
結ぶ経路として定義され、縦断線と同様に折曲部を含む
線とすることも可能である。

【００１９】図３は、この発明に使用される設計支援装
置を示すものである。この設計支援装置は、通常のＥＷ
Ｓによって構成されている。すなわち、ＣＰＵ３１には
各種の情報を入力するためのキーボード３２が接続され
るとともに、各種データを表示するためのディスプレイ
３３が接続されている。さらに、ＣＰＵ３１には、シン
ボリック・レイアウトを示す図形データやコンパクタ等
のプログムが記憶された磁気ディスク装置３４、および
前記プログラムがロードされ、実行される主記憶装置３
５が接続されている。

【００２０】前記磁気ディスク装置３４に記憶されたシ
ンボリック・レイアウトは、標準フォーマットのＣＩＦ
（Caltec Intermidiate Format）によって記載されてい
る。ＣＩＦの場合、トランジスタ、コンタクト、端子の
シンボルおよびワイヤ等からなる各構成要素は、１つの
文（コマンド）によって記述されている。また、ここで
は、１文が１レコード（1024 byte ）からなり、ワイヤ
は全て両端を有する直線に分解して記述されている。さ
らに、シンボリック・レイアウトを分割するための複数
の縦断線、および複数の横断線はＣＩＦの文法に従っ
て、特殊な層によって記載されているものとする。尚、
ここでは、単純化するため、縦断線、横断線は直線とす
る。上記原理および構成において、図４に示すフローチ
ャートを参照してこの発明のマスク・レイアウト方法に
ついて説明する。

【００２１】先ず、磁気ディスク装置３４から主記憶装
置３５に構成要素を１つずつ読込む（ＳＴ１）。この読
込んだ各構成要素から縦断線のみを取出す。縦断線はそ
の層により他と区別できるため、縦断線のｘ座標のみを
テーブル４１に格納する（ＳＴ２）。これらｘ座標が断
片１１_x〜１１_{x +3}にほぼ対応する。尚、同じ座標の線
が複数個存在する場合、１つのみをテーブル４１に格納
し、このテーブル４１に格納したｘ座標は昇順にソート
しておく。

【００２２】次に、前記各構成要素を１つずつ読込み、
それらをｘ座標に従って各断片１１_x〜１１_{x +3}（レコ
ードの集合）に仕分けする（ＳＴ３）。シンボルの場
合、その参照点、例えばシンボルの中心のｘ座標が、前
記テーブル４１に格納した座標のｉ番目とｉ＋１番目め
の間に入るならば、それをｉ＋１番目の断片に追加す
る。すなわち、テーブル４１のｉ＋１番目にシンボルの
中心のｘ座標を格納する。ワイヤについても同様である
が、ワイヤが複数の断片に跨がる場合それらを分断し、
この分断した座標を、それぞれ対応する断片に追加す
る。そして、その分断した切り口に端子を発生させ、こ
の端子の座標をテーブルに格納する。

【００２３】次に、前記ＳＴ３で生成された断片を、例
えばコンストレイント・グラフ法によって、１つずつｘ
方向に１次元コンパクションする（ＳＴ４）。この結
果、各断片がｘ方向に圧縮される。

【００２４】次に、上記圧縮した断片をつなぎ合わせる
（ＳＴ５）。すなわち、ストリーム・フォーマットで記
載されたファイルをつなぎ合わせる。このとき、ファイ
ルの途中に含まれる不要な“ＥＮＤ”コマンドを除去す
るとともに、前記ＳＴ３で発生した端子を除去する。

【００２５】次に、上記ｘ方向に圧縮された各構成要素
からＳＴ１と同様にして、横断線のみを取出し、横断線
のｙ座標のみをテーブル４２に格納する（ＳＴ６）。こ
れらｙ座標が断片１１_y〜１１_{y +3}にほぼ対応する。

【００２６】次に、前記読込んだ各構成要素から各構成
要素を１つずつ読込み、ＳＴ２と同様にして、それらを
ｙ座標に従って各断片１１_y〜１１_{y +3}に仕分けする
（ＳＴ７）。

【００２７】次に、前記ＳＴ６で生成された断片を、例
えばコンストレイント・グラフ法によって、１つずつｙ
方向に１次元コンパクションする（ＳＴ８）。この結
果、各断片がｙ方向に圧縮される。

【００２８】次に、上記圧縮した断片をＳＴ５と同様に
してつなぎ合わせる（ＳＴ９）。この処理は、圧縮され
た各断片の各構成要素を１つずつ読み込み、断片につい
て定められている一定値だけｙ座標を増加して書出せば
よい。このようにして、ｘ、ｙ方向に圧縮したシンボリ
ック・レイアウトを得ることができる。

【００２９】ここで、上記処理に必要な時間を推定す
る。工程ＳＴ３、ＳＴ５、ＳＴ６、ＳＴ７、ＳＴ９は、
いずれもトランジスタやコンタクト等の各構成要素を１
つ読込み、所定の処理を行ってテーブル４１、４２に書
込むストリーム処理である。この処理は、レコード単位
であるため、極めて少ない記憶容量だけですみ、主記憶
装置３５に全てのデータを記憶できる。したがって、各
工程の処理時間は、規模ｎ、すなわち、レコード数に依
存しない上限値が定められる。よって、全体の処理時間
は、Ｏ（ｎ）である。一方、工程ＳＴ４とＳＴ８は、断
片に対するコンパクションである。各断片に規模がほぼ
等しいと仮定し、断片の数をｍとすると、その処理時間
はＯ（ｆ（ｎ／ｍ））である。これらの工程はｍ回ずつ繰り返されるため、全
体ではＯ（ｍｆ（ｎ／ｍ））

【００３０】とする。ここで、規模ｎが大きくなった場
合、それだけ数多くの断片に分割すると仮定すると、ｍ
は約ｋｎ（ｋは定数）である。そうすると、ｆ（ｎ／
ｍ）は規模によらない定まった値となるため、全体の処
理時間は、Ｏ（ｎ）となる。したがって、この方法によ
る処理時間は規模に比例することとなる。

【００３１】上記実施例では、工程ＳＴ４において、各
断片１１_x〜１１_{x +3}をｘ方向に圧縮し、工程ＳＴ５に
おいて、これら圧縮した断片をつなぎ合わせた後、横断
線に沿った断片１１_y〜１１_{y +3}に分割したが、これに
限定されるものではない。

【００３２】すなわち、図５に示すように、工程ＳＴ４
において、各断片１１_x〜１１_{x +3}をｘ方向に圧縮した
後、これら断片１１_x〜１１_{x +3}をつなぎ合わせること
なく、横断線１４に沿った断片に分割して圧縮し、最後
に、これら断片をつなぎ合わせるようにしてもよい。

【００３３】また、上記実施例において、処理時間の約
９５％は、工程ＳＴ４、ＳＴ８のコンパクション処理に
費やされている。したがって、これらの処理を並列化す
ることが望ましい。

【００３４】図６は、コンパクションを並列処理する場
合の一例を示すものである。この例は、コンパクション
処理を実行するための複数のプロセッサ６１、６２、６
３と、これらプロセッサ６１、６２、６３と同数のキュ
ー６４、６５、６６と、これらキュー６４、６５、６６
にデータを供給するネットワーク６７と、前記各プロセ
ッサ６１、６２、６３から出力されるコンパクション結
果を転送するためのネットワーク６８とによって構成さ
れている。

【００３５】断片１１_x〜１１_{x +3}あるいは１１_y〜１
１_{y +3}のシンボレック・レイアウトは、プロセッサ６
１、６２、６３に均等に割り当てられ、ネットワーク６
７を介して対応するキュー６４、６５、６６に追加され
る。個々の断片のデータ１つがジョブ１つに対応し、各
プロセッサ６１、６２、６３はジョブを１つずつコンパ
クションする。このコンパクション結果はネットワーク
６８によって転送される。また、コンパクション以外の
処理、例えば縦断線の取出し処理、断片の仕分け処理等
はストリーム処理であるため、パイプライン方式で実行
できる。

【００３６】図７は、パイプライン方式を示すものであ
り、プロセッサ７１は例えば縦断線を取出す処理を実行
し、前記プロセッサ７２は断片を仕分ける処理を実行す
る。プロセッサ７１の前段、プロセッサ７１とプロセッ
サ７２の相互間、およびプロセッサ７２の後段には、そ
れぞれ所謂パイプライン・レジスタ７３〜７５が設けら
れ、これらレジスタ７３〜７５に処理を待つレコードが
記憶されている。このような構成とすることにより、処
理速度を向上できる。

【００３７】上記実施例によれば、コンパクション工程
において、一度にコンパクションするのはシンボリック
・レイアウトの断片であり、シンボリック・レイアウト
を細かく分割すれば、それだけ大きなシンボリック・レ
イアウトを処理できる。したがって、回路規模に比例し
て分割数を増加すれば、論理的に処理上限が存在しな
い。つまり、大規模処理が可能である。現行のコンスト
レイント・グラフ法によるコンパクタが処理し得る回路
規模は約１万トランジスタであるため、例えば縦断線と
横断線を１００ずつ定義すれば、約１００万トランジス
タを現行の設計支援装置によって処理できる。

【００３８】また、コンパクション以外の処理は、全て
ストリーム処理が可能であるため、処理の上限が存在し
ない。しかも、処理時間は前述したようにＯ（ｎ）であ
り、繰り返し等の特殊条件のないもとで最良である。

【００３９】さらに、処理時間のほとんどを占める断片
のコンパクションは、他の断片とは全く独立に処理する
ことができる。したがって、各断片を別々のプロセッサ
によって処理できるため、プロセッサを増加することに
より、実用時間で大規模データを圧縮することができ
る。現行のＥＷＳは１万トランジスタのコンパクション
を数十分〜数時間で処理できるため、例えば、１００台
のＥＷＳを用意すれば、１００万トランジスタのコンパ
クションを数十分〜数時間で処理することができる。ま
た、コストパフォーマンスの良い安価なプロセッサを使
用することが可能であり、コストをさらに引き下げるこ
とができる。

【００４０】また、シンボリック・レイアウトを断片に
分割してコンパクションするため、圧縮によるシンボル
あるいはワイヤの終端の移動範囲はその断片内に限定さ
れる。したがって、ワイヤが予想外に大きく伸びること
がないため、配線の遅延時間の幅が特定され、チップの
パフォーマンスを予測可能となる。

【００４１】尚、本願発明と類似の方法は、本願発明者
の文献(Proc. 27th Design Automation Conference pp.
388-393)に開示されている。この文献に開示されている
方法の場合、入力データはビット規制性のある階層記述
であり、本願発明とは相違するものである。また、この
発明は、上記実施例に限定されるものではなく、発明の
要旨を変えない範囲において、種々変形実施可能なこと
は勿論である。

【００４２】

【発明の効果】以上、詳述したようにこの発明によれ
ば、通常の設計支援装置を使用して、大規模集積回路の
コンパクションを可能とするとともに、チップ面積の損
失を抑えることが可能なマスク・レイアウト生成方法を
提供できる。

【図面の簡単な説明】

【図１】この発明の原理を説明するために示す図。

【図２】縦断線の変形例を説明するために示す図。

【図３】この発明に使用される設計支援装置の一例を示
す構成図。

【図４】この発明の一実施例を示すフローチャート。

【図５】この発明の他の実施例を示す図。

【図６】この発明に適用されるコンパクションの並列処
理方式を示す図。

【図７】この発明に適用されるパイプライン方式を示す
図。

【図８】コンパクションの概念を説明するために示す
図。

【図９】ボトムアップ法による階層コンパクションを説
明するために示す図。

【図１０】ピッチマッチング法による階層コンパクショ
ンを説明するために示す図。

【符号の説明】

３１…ＣＰＵ、３４…磁気ディスク装置、３５…主記憶
装置、６１〜６３、７、７２…プロセッサ。

Claims

【特許請求の範囲】

【請求項１】集積回路のマスク・レイアウトを示す図
形データを複数の第１の断線に沿って複数の第１の断片
データに分割し、これら分割した第１の断片データをそれぞれ圧縮処理
し、これら圧縮処理した第１の断片データ全体を複数の第２
の断線に沿って複数の第２の断片データに分割し、これら分割した第２の断片データをそれぞれ圧縮処理
し、これら圧縮処理した第２の断片データをつなぎ合わせる
ことを特徴としたマスク・レイアウト生成方法。
【請求項２】前記第１の断線は図形データを縦方向に
沿って分割することを特徴とする請求項１記載のマスク
・レイアウト生成方法。
【請求項３】前記第２の断線は図形データを横方向に
沿って分割することを特徴とする請求項１記載のマスク
・レイアウト生成方法。
【請求項４】前記第１、第２の断線は折曲部を含むこ
とを特徴とする請求項１記載のマスク・レイアウト生成
方法。
【請求項５】前記圧縮処理は１つの断片データを１つ
のジョブとして処理する複数のプロセッサによって並列
に処理することを特徴とする請求項１記載のマスク・レ
イアウト生成方法。