JPH0644596B2 - Ｃｍｏｓセル・レイアウトの形成方法 - Google Patents

Description

【発明の詳細な説明】 以下の順序で本発明を説明する。

Ａ．産業上の利用分野 Ｂ．従来技術 Ｃ．発明が解決しようとする問題点 Ｄ．問題点を解決するための手段 Ｅ．実施例 ｅ１．概要 ｅ２．ブール関数 ｅ３．チップ上の結線構造 ｅ４．ブール表現のグラフ ｅ５．別の結線構造 ｅ６．別のブール関数に対応する結線構造 ｅ７．スタック配向技術 ｅ８．コンピュータによるレイアウト作成動作 Ｇ．発明の効果 Ａ．産業上の利用分野 この発明は、設計の自動化システムに関し、特に半導体
を処理するためのデータを準備するためのすぐれた方法
に関するものである。

特にこの発明は、相補的金属酸化半導体（ＣＭＯＳ）デ
バイスに関する。

Ｂ．従来技術 大規模集積回路（ＬＳＩ）が世に出たことにより、単一
の半導体ウェーハ・チップ上に何千もの回路を製造する
ことが可能となった。このとき、単一の半導体チップ上
に製造されるＬＳＩ回路の数に比例して、それらの回路
の結線と分離を正しく配置するための手続の複雑さが増
してくる。この複雑さのため、コンピュータ支援の自動
化設計システム（ＣＡＤ）が必要になってきた。

自動化回路設計システムの典型的な従来技術として、米
国特許第３４７５６２１号及び米国特許第３５６７９１
４号に記載されているものがある。これらの従来技術
は、典型的には、直交座標を設け、これらの座標を利用
して、製造すべき回路中の論理素子の接続点を与えるた
めの技術を開示している。この技術はセル的な論理設計
(Clllular logic design)と呼ばれることがあり、その
論理素子はセルと呼ばれる。この方法においては、論理
素子を記述するデータと、直交座標と、論理素子の接続
点とがデータ処理ユニットに入力され、回路生成プログ
ラムがデータ処理ユニットを作動して回路素子またはセ
ルの間の接続を与える。しかし、これら従来技術のシス
テムは、製造できる回路の複雑さに限界がある。という
のは、単一パス内で論理機能の形成を可能ならしめるた
めに、各回路には、セル間のすべての可能な接続点に使
用されるすべての可能な論理セルの記述が必要だからで
ある。例えば、２入力のＮＡＮＤゲートは、固定された
入出力位置につき垂直及び水平結線をはかるだけでも、
１２の可能な入出力結線パターンの組み合わせを有す
る。従来技術のシステムでは、完全な内容としてこれら
の可能なＮＡＮＤゲートの構成の各々を記述するデータ
は、システムに記憶されなくてはならない。そして、そ
の各構成がセルと考えられる。また、入出力結線配置に
加えて、この技術には多重電力レベルも必要となる。。
もし２つの電力が利用可能であるなら、必要とされるセ
ルの数は２４まで増加する。このＮＡＮＤゲートは、例
えばＯＲ、ＡＮＤ、ＮＯＲ及びＮＯＴなどの他の基本的
な論理セルと組み合わせて使用することができる。これ
らの回路の各々は個別の構成を要し、回路の多様性はさ
らに増大する。このことにより、従来技術は、比較的簡
単な構成または、より複雑な構成のきわめて特殊な実施
例、例えば米国特許第３９８７２８７号に開示されてい
るような高集積密度論理アレイに限定される。さらに、
従来技術を利用して構成される回路パターンは、改変に
役立たない。すなわち、回路の任意のセルにおけるどの
ような変更も、全く新しい回路の製造を要するのであ
る。

米国特許第４３７７８４９号の技術は、後でより大きい
マクロな回路を構成すべく結合され得るような基本的な
セルの記述を可能とすることにより、レイアウトが階層
的に作成され得るような方法を簡単に与えるように思わ
れる。このセルは、自動的に生成れるのではなくて手書
きで設計される。これらのセルは、相当に小さい格子上
にレイアウトされる基本的な物理ユニットである。そし
て、回路のブール式または関数的な記述からのレイアウ
トの生成はない。この特許に記述されている単一のプロ
グラマブル論理アレイ（ＰＬＡ）においてすら、ＰＬＡ
自身の最小の機能的形式がそのパッケージの外側で実行
されているように見える。

他の関連がある米国特許として番号だけを掲げておく：
４２１２０２６；４２１８６９３；４２３３５２６；４
４０２０４４；及び４４１２２４０。

上述の特許に記載された方法のうち、スタティックＣＭ
ＯＳブック・レイアウトの生成に利用し得るものはな
い。

Ｃ．発明が解決しようとする問題点 この発明の目的は、スタティックＣＭＯＳブック・レイ
アウトを自動的に形成するための方法を提供することに
ある。

Ｄ．問題点を解決するための手段 本発明によれば、機能的回路のレイアウトが、ブール式
から生成される。コンピュータ・プログラムは、そのブ
ックの高レベルの機能的な記述からＣＭＯＳブックのレ
イアウトを生成する。そのようなプログラムは２つの点
で有利である。第１にそのプログラムは、最小の時間で
ブック・セットを設計するのに使用できる。第２に、そ
のプログラムは、最小の時間でブック・セットを設計す
るのに使用できる。第２に、そのプログラムは、フロン
トエンドが論理を一組の直列並列ネットワークにマップ
し、プログラムがそのような各ネットワークのレイアウ
トを生成するような合成システムの一部として使用する
ことができる。そのプログラムへの入力は、出力にイン
バータを有するＡＮＤ及びＯＲ機能としてのネットワー
クの論理記述である。

尚、結線の労力を最小限にとどめるために、ｎ側上のト
ランジスタのポリシリコン・ゲートをもつチップの影像
はＰ側上のトランジスタのポリシリコンゲートに垂直に
整合される。ソース及びドレインの間の接続線はゲート
に垂直であり、金属の１つの層に沿って走行している。

Ｅ．実施例 ｅ１．概要 以下の記載は、シリコンにおけるＣＭＯＳ論理ネットワ
ークのレイアウトの設計自動化技術であり、特に、ブッ
クの高レベル機能的記述からＣＭＯＳブックのレイアウ
トを生成するコンピュータ・プログラムが記載される。
このプログラムへの入力は、ある場合には出力に単一の
インバータを有するようなＡＮＤ及びＯＲ機能として実
現され得るネットワークの論理のブール表現である。こ
のプログラムは、ＩＢＭシステム３７０などのような任
意の汎用コンピュータ上で走らせることができる。

ＣＭＯＳ回路のブックを支持することになるシリコン・
チップの影像は、ｎ側にあるトランジスタのポリシリコ
ン・ゲートがｐ側にあるトランジスタのポリシリコン・
ゲートとは垂直に整合され、以てブック内の結線労力が
低減されるという事実によって特徴づけられる。さら
に、トランジスタのソースとドレイン間の内部結線は、
ゲートに垂直で、金属の１つの層にのみ沿って走行して
いる。第２のレベルの金属は、ｐ側の出力をｎ側の出力
と相互接続するために使用される。しかし、このことは
必須ではない。なぜなら、その両側の出力が隣接するト
ラック上にあって重なり、以て直接接続を可能ならしめ
ることをプログラムが保証するからである。

多くの場合、レイアウトにおいて別のトランジスタに隣
接するトランジスタは、ｐ側においてもｎ側においても
その隣接するトランジスタのソースに接続されたドレイ
ンを有している。この場合、それらの拡散領域が共有さ
れるようにこれらのトランジスタを方向づけることが好
都合である。これにより開孔接点に関連する金属結線が
回避されるし、多くの場合、水平方向の結線トラックを
減少することもできる。

拡散領域の共有化を極大化することの問題として、ｐ側
をあらわすグラフを経由する一組の経路をも形成するよ
うな、ｎ側をあらわすグラフを経由する一組の経路を決
定することがある。しかし、拡散領域の切れ目の数を最
小限に減らすことは、拡散領域の切れ目の数の増大を許
す場合に比較して水平方向により多の結線を要求するこ
とになる。さらに詳しく分析を行うと、このことは特
に、グラフの所与のノードに接続されたトランジスタ
が、互いに遠くに拡がりすぎている場合に起こることが
分かる。そこでコンピュータ・プログラムは、拡散領域
の切り目の数を最適化するときに、グラフの局所領域を
視察することによって、この観察結果を利用する。

さらなる観察により、直列及び並列の結合グループを計
算することは、グラフの論理関数を変更しないけれど
も、よりよいレイアウト特性をもたらすということがわ
かる。プログラムは、このことも考慮する。もし、いく
つかのグループの順序を計算し、またはいくつかのグル
ープを配向することによって拡散領域の切れ目が減少す
るなら、プログラムはそれを実行する。

多くの場合、アースとＶＤＤ結線は、金属線と平行でト
ランジスタに直交して走行するバスのかたちで与えられ
る。このことは、結線接続の問題の性質を変更する。な
ぜなら、グリーディ(greedy)アルゴリズムによって最適
な結果をもたらす通常のスティック・パッキング(stick
-packing)は最早十分でないからである。このときは、
よりよい結果が得られるかどうか調べるために、出力ラ
インをｐ側のＶＤＤラインと交換するか、出力ラインを
ｎ側のアース・ラインと交換することが必要である。こ
のプログラムは、この種のチェックをも行う。

さらに、経路の割り付けも両側の出力を接続を容易なら
しめる効果を及ぼす。プログラムは、迷路追跡手段(maz
e runner)を用いて、出力を接続するための可能な最善
の方法をチェックする。このプロセスにおいては、スタ
ックされた貫通孔、すなわち金属から拡散領域への貫通
孔上に金属から金属への貫通孔が来ることが回避され
る。

プログラムのこのフェーズの結果は、接続経路と、必要
なすべての切れ目を有するレイアウトの置き換えをあら
わすスティック図である。この結果は次に、レイアウト
の位相幾何的規則を含む別のプログラムに送られる。こ
のプログラムの出力は、レイアウトの位相幾何的記述で
ある。この技術的規則はさまざまな影像に適合するよう
に容易に変更可能である。このプログラムはまた、例え
ばバッファや、異なるトランジスタの寸法や、接続され
た接点や、拡散領域の切れ目の代わりの分離デバイスを
もつブック・レイアウトを付加的に与えるように容易に
変更可能である。

ｅ２．ブール関数 所与のブール関数は、複数の異なる論理構成により実施
可能である。例えば、第１図に示すように、関数ｆ＝ａ
＋ｂｃ＋ｄｅは、ＯＲゲート２及び３と、ＡＮＤゲート
４を用いて実現され、こうして得られた信号は、出力端
子６で関数ｆを与えるためにインバータ５により反転さ
れる。また別の構成例が第２図に示されている。第２図
においては、ＮＡＮＤゲート７、８及び９を用いて、関
数ｆが得られ、その関数は出力端子１０に供給される。
ある種の例ではこれらは受容できる実施例であるけれど
も、スタティックＣＭＯＳ技術は、全体の関数を、以下
で論理セルと呼ぶ単一のゲートで実行することを可能な
らしめる。

ｅ３．チップ上の結線構造 第３図は、第２図に示す論理ネットワークのＮＡＮＤ回
路によるチップ上の結線構造である。この図において
は、ｎ拡散領域１１とｐ拡散領域１２が存在し、ＶＤＤ
バス１３はｐ拡散領域に、アース・バス１４はｎ拡散領
域に、それぞれ接続されている。金属から拡散領域への
接点１５は、ライン１６におけるように、同タイプの個
々の拡散領域を接続するために利用される。ライン１７
のような垂直方向の第２レベルの金属線は、ｐ拡散領域
とｎ拡散領域との間に接続をはかるために必要である。
ポリシリコン条片１８は、さまざまな入力関数をｐ拡散
領域１２とｎ拡散領域１１の両方に与えるためのゲート
として機能する。ポリシリコンから金属への接点１９も
また、ゲート・ソース及びドレイン間にさまざまな接続
をはかるために必要である。さらに、接点２０などの、
第１レベル金属から第２レベル金属への接続接点もやは
り必要である。これらの回路構成において、各拡散領域
の間には、“切れ目”２１があり、この結果、チップ上
で関数を実現するために必要な面積が増大することが見
てとれる。

これよりも有効な回路結線構造もＣＭＯＳ技術で実現す
ることができる。関数＝ａ＋ｂｃ＋ｄｅのＣＭＯＳに
よる実現は第４図に示されており、これはｎ拡散領域２
２をもつｎチャネル・デバイスの組と、それに対応して
ｐ拡散領域２３をもつｐチャネル・デバイスの組の存在
によって特徴づけられる。これらの各組は、相異するが
関連づけられた方法で相互接続されている。この構造
は、ｎ拡散領域に接続された金属アース条片２４と、ｐ
拡散領域に接続された金属ＶＤＤ条片２５とを有してい
る。ポリシリコン条片２６は、ネットワークに入力信号
を供給するための個々のゲートを構成する。金属から拡
散領域への接点２７は、個々の拡散領域の間で金属条片
２８を接続するために利用される。垂直方向の第２レベ
ル金属条片２９は、デバイスの出力バスとして機能す
る。このネットワークにも“切れ目”の領域３０及び３
１が存在し、特にデバイスのｎ側とｐ側の両方に４個の
そのような切れ目の領域が存在することが見てとれる。
第４図における切れ目領域の数は第３図よりも４つ少
い。従って、切れ目領域の数が減少するにつれて、回路
の物理的寸法がより小さくなることが見てとれる。

ｅ４．ブール表現のグラフ 第５図及び第６図は、それぞれｎチャネル・デバイスと
ｐチャネル・デバイスのブール表現のグラフである。こ
れらのグラフは、デバイス中の個々の結線をあらわし、
これらのグラフからは２つの事実が観察される。第１に
どちらのグラフも性質上直並列でありそれゆえ平面的で
ある。第２に、グラフ理論的な意味で、一方のグラフが
他方と双対である。すなわち、一方のグラフで直列であ
るものは他方のグラフで並列である。第１図と比較する
と、第５図の要素が直列であるとき、それに対応する第
６図の要素は並列である。さらに、これらの要素は、第
１図におけるＡＮＤゲートの入力に対応する。

次の性質をもつことは、すべてのスタティックＣＭＯＳ
複合論理セルにとって典型的である： （１）それらが実行する論理機能が、一組のＯＲゲート
に信号を与えるＡＮＤゲート、またはＡＮＤゲートに信
号を与えるＯＲゲート及びインバータに信号を与える最
終ステージによって特徴づけられること。

（２）ｐ側でのデバイスの接続をあらわすグラフがｎ側
の対応する接続と双対であること。

ｅ５．別の結線構造 第７図は第４図と同様の機能を行う別の結線構造を示す
図である。ただし、第７図においては、拡散領域が互い
に接触するようにデバイスを十分に近づけることによ
り、２つの拡散領域を接続する金属接続セグメント３２
が省略されている点が異なる。すなわち、チップ上にあ
らわれる切れ目３３の数が減少している。第４図におい
てはデバイスのｎ側とｐ側で４つづつの切れ目があった
が、第７図においてはデバイスのｎ側とｐ側とで切れ目
が１つづつであることが見てとれる。この操作の結果、
回路全体の幅が低減され以て回路動作が速くなることが
明らかである。結線に要するラインの本数の減少によ
り、セルの高さにも減少が見られる。このことは、より
大きいシステムにおいてセルの入出力を別のセルに接続
する余地が増大するという点で好ましい。

第８図は、上述した同一のコンパクト化技術を用いて同
一の論理関数ｆをあらわすためのさらに別の結線構造で
ある。この図においては、単一のｎ拡散領域３４及び単
一のｐ拡散領域３５が存在し、従ってこのネットワーク
中には“切れ目”がなく、このことはより高速で動作す
るよりコンパクトなネットワークをもたらす。この結線
構造に対応する直並列グラフは第９図及び第１０図に示
されている。これらのグラフと第５、６図のグラフとの
相違は単なる置換のみである。

ｅ６．別のブール関数に対応する結線構造 第１１図及び第１２図はブール関数＝ａｂｃ（ｄ＋
ｅ）に対応する２つの結線構造である。第１１図ではｎ
側に３本のラインを要し、一方、第１２図ではｎ側に２
本のラインしか要さない。ラインの数が少ないので、第
１２図の構造の方が好ましい。この結線構造は第１３図
及び第１４図のグラフから得られる。第１３図は第１１
図の回路のグラフであり、第１４図は第１２図の回路の
グラフである。第１４図は、第１３図を倒置したグラフ
であるが、これによりｎ側のラインが減少した結線構造
が得られる。

所与のＡＮＤ−ＯＲ−ＮＯＴスタティックＣＭＯＳを実
現するための好適な方法の特徴は次のように要約され
る： （１）デバイスは、接触する拡散領域を有し得るデバイ
スの対の数が最大となるような方法でレイアウトされな
くてはならない。

（２）デバイスは、デバイスの相互結線に必要なトラッ
ク（ライン）の数が最小となるような方法でレイアウト
されなくてはならない。

（３）デバイスは、さまざまな直列の素子や、さまざま
な並列の素子の順序を入れ換えることにより機能の実行
がより高められることのないような最適化された方法で
レイアウトされなくてはならない。

（４）各グラフの方向は、デバイスの接続に要するライ
ンの数を最小限にするような方法で選択されなくてはな
らない。

従来では、これらのうち１つを満足させる方法の試みは
あったが、これらすべてを同時に満足させる試みは知ら
れていない。

ｅ７．スタック配向技術 前述したように、所与の関数をＣＭＯＳで実現すること
は、その関数のブール表現から導かれる。その後記述さ
れるプログラムにおいては、ブール関数は、因数分解さ
れたかたちで与えられることを仮定する。関数のブール
表現は次に、標準的なスタック配向技術を用いて後置あ
るいは逆ポーランド（ＬＯＲＰ）記法に変換される。第
１５図には、スタック配向(Stack-orinted)技術がブー
ル関数ｆ＝ａ＋ｂｃ＋ｄｅに対して示されている。第１
５図において、ステップ４０で、スタックにはオペラン
ドａ（オペランドは文中では小文字であるが図中では大
文字であらわされている）が配置され、ステップ４１で
オペランドｂがスタックの上方に配置され、次にステッ
プ４２でオペランドｃがスタックの上方に配置される。
スタックの上の２つのオペランド、すなわちｂ及びｃは
ｂ＊ｃとして、ステップ４３でスタックの上方に配置さ
れる。次にステップ４４はオペランドｄ及びｅが順次ス
タックの上方に配置される。ｄ及びｅはスタック中の上
方の２つのオペランドであるため、それらはｄ＊ｅとし
て結合され、ステップ４５でスタックの上方に配置され
る。このとき、スタック中の上方２つのオペランドはｂ
＊ｃ＊ｄ＊ｅであるため、それらはｂ＊ｃ＊＋ｄ＊ｅと
して結合され、ステップ４６でスタックの上方に配置さ
れる。ここで、スタック中の上方の２つのオペランドが
ａ及びｂ＊ｃ＋ｄ＊ｅとなり、それらはステップ４７に
示すように関数ａ＋ｂ＊ｃ＋ｄ＊ｅとしてスタックに配
置される。

ｅ８．コンピュータによるレイアウト作成動作 第１６図はブール関数ｆを実現するために使用される手
続の全体的なフローチャートである。尚、ブール関数は
因数分解されたかたちで与えられ、論理ブロック１００
で入力としてコンピュータに供給される。論理ブロック
１０１では、Ａ＋Ｂ＊Ｃ＋Ｄ＊Ｅというブール表現が、
後置または逆ポーランド記法であるＡＢＣ＊ＤＥ＊＋＋
に変換される。

この表現はブロック１０２で、ＡＢＣ（＊２）ＤＥ（＊
２）（＋３）とさらにコンパクト化される。これは、同
一のオペレータの連続するストリング（列）を集め、そ
のストリングを、オペレータとそれに続くオペレータの
長さプラス１の数字によってあらわすことにより得られ
る。この記法は、トランジスタの最適な順序とトランジ
スタ間の最適な結線を決定する論理ブロック１０３の手
続への入力に好都合である。このプログラムの詳細は第
１８〜第２４図とテーブル１に関連して説明される。

付記：ｌ_１ｌ_２ｌ_３はｌ_１の右側にｌ_２を結合し、さら
にｌ_２の右側にｌ_３を結合したものである。

ｌ_１Ｒは、ストリングｌ_１が結合の前に反転されるべき
ことを示す。

ｌ_１Ｏｌ_２は、そのＯの位置に分離デバイス（または拡
散領域の切れ目）が配置されるべきことを示す。

ブロック１０３の出力は、第１７図に示すＣＭＯＳネッ
トワークの最終レイアウトをあらわす“スティック”表
示である。スティック表示は、第７図に示すような最終
的な構造を形成するために接地規則(ground rule)とと
もに使用するのに必要なすべての情報を有するとして
も、最終的な構造の接地規則に依存しない表示である。
この接地規則は、論理ブロック１０４で示されているよ
うに読み取られ、シリコン・マスクの最終的なトポロジ
ー（幾何形状）がブロック１０５で示すように決定され
る。尚このことは第２６及び２７図に関連してより詳細
に説明する。

第１８図は第１６図の論理ブロックのより詳細なフロー
チャートであり、スティック表示を生成するための処理
が２つの主要なステップからなることを示している。

論理ブロック１１０で示した第１のプロセスは拡散領域
の共有化を極大化するためにトランジスタの最適な順序
を決定すること、すなわち切れ目の除去もしくは最小化
に関与する。論理ブロック１１１で示した第２のプロセ
スは、デバイス間の相互結線とともに、ｐ側とｎ側の各
々のグラフの配向を決定することに関与する。尚、デバ
イスという用語はトランジスタという用語と相互交換的
に使用されている。

ここで、実際的にプログラムが隣接する拡散領域の高度
の共有化を首尾よく達成し、以て連続的に延長された長
い拡散領域を有する回路構成につながるということがし
ばしば観察されていることを述べておくべきであろう。
それゆえ、いくつかの拡散領域の切れ目が介在する大き
い拡散領域というものを考えることは容易である。事
実、拡散領域の切れ目の数が少ないときは、そのことに
より性能が低下することはなく、一方分離デバイスがそ
の切れ目に挿入されると集積密度が向上することが観察
されている。そのような分離デバイスとは、電力バスＶ
ＤＤに接続されたｐ側のトランジスタと、アースに接続
されたｎ側のトランジスタである。

第１９図は、第７図の回路に拡散領域の切れ目ではなく
分離デバイスを使用した回路の構造である。

第２０図は、第１８図のより詳しい論理ブロックを示す
フローチャートである。このフローチャートは、第１６
図または第１８図の論理ブロック１０２から論理ブロッ
ク１２０に後置または逆ポーランド記法で入力ストリン
グが与えられたときにトランジスタの順序を決定するた
めの再帰的な手続きを記述している。論理ブロック１２
１に示されているように、ストリングの最初のトークン
にストリング・ポインタがセットされる。そして、その
トークンがオペレータであるかオペランドであるかを判
断するために、ストリング中の各トークンが調べられ
る。もしトークンがオペランドならば、論理ブロック１
２５で示すように、そのトークンはタイプ値１とともに
スタックされる。一方、もしトークンがＡＮＤまはＯＲ
のオペレータならば、論理ブロック１２３で示されるよ
うに、その添付数字（例えばＢＣ（＊２）における
“２”という数字である）も読み取られる。この添付数
字は、スタックから押し上げ（ＰＯＰ）られるオペラン
ドの数を決定するために使用される。スタックのオペラ
ンドとオペレータは論理ブロック１２４で示すトランジ
スタの順序決定手続に渡される。尚、論理ブロック１２
４については、第２１図でより詳細に説明する。論理ブ
ロック１２６で示されるように、ポインタは各々のトー
クンに対して順次進行される。論理ブロック１２７でポ
インタがストリングの終端に達したかどうかの判断が行
なわれる。もしポインタがストリングの終端に達してい
なければ、ストリングの次のトークンを調べるためにプ
ログラムは論理ブロック１２２に戻る。一方、ポインタ
がストリングの最後のトークンに達していたなら、スタ
ックを押し上げてトランジスタの順序を得るために、論
理ブロック１２８に手続が進む。ゆえに、ストリングか
ら読み出されるＮＯＴである最後のオペレータまでこの
プロセスが継続する。スタックの頂部のオペランドは、
関数全体に対する成分の必要な順序とタイプとから成
る。

第２１Ａ図と第２１Ｂ図の結合である第２１図を参照す
ると、第２０図におけるトランジスタの部分的な順序を
決定するための論理ブロック１２４についてのより詳し
い論理フローチャートが示されている。第２１図におい
て、検査されたトークンがオペレータであることが判定
されると、そのオペレータがＡＮＤかＯＲかを判断する
ために手続は論理ブロック１４０へ進む。そして、もし
トークンがＡＮＤ関数に進み、もしそのオペランドがタ
イプ２ならタイプ５に、タイプ５ならタイプ２に、テー
ブルＩに基づき変換される。この動作に続いて、プログ
ラムは論理ブロック１４２に進み、すべてのオペランド
はタイプによってソートされる。プログラムは次に、ポ
インタをテーブルＩの最初のラインにセットするための
論理ブロック１４３に進み、ここでオペランドはテーブ
ルＩの最初のラインの左半分の基準を満足するオペラン
ドのサブセットが存在するかどうかについて検査され
る。具体的に述べると、このラインは、各々タイプ１で
ある３つのオペランドを要求する。そして、もしタイプ
１の３つのオペランドが見出されると、これらのオペラ
ンドに対応するストリングが、テーブルの右半分に示さ
れるように連結される。さらに、結合されたストリング
のタイプが１であることも示されている。この論理動作
は論理ブロック１４４で実行され、論理ブロック１４５
では、この段で実行された連続的な動作のレコードが結
線入力リストして出力される。そして、もしテーブルの
左半分で一致が存在しなければ、テーブル中のポインタ
を進めるために、プログラムは論理ブロック１４６に進
む。

次に論理ブロック１４７は、テーブルの終端に到達した
かどうかを判断する。そして、もしそうでなければ、再
びテーブルの左半分で一致を捜すために論理ブロック１
４４に戻る。もしテーブルの終端に到達したならば、オ
ペレータのタイプを決定するために、プログラムは論理
ブロック１４８に進む。そしてＡＮＤオペレータが見出
されたならば、プログラムは論理ブロック１４９に進
み、タイプが２から５に変換され、タイプ５の結合がタ
イプ２に変換される。次にプログラムは、トランジスタ
の順序を形成する最終結合とともに、タイプ情報を出力
するために論理ブロック１５０に進む。

第２２図は、第１８図の論理ブロック１１１のより詳し
い論理フローチャートであり、これはデバイスの結線を
はかるために結線セグメントをトラックに割り付けるこ
とを関与する手続の概観を示している。論理ブロック１
２８によって与えられるトランジスタの順序と、論理ブ
ロック１４５によって与えられる結線入力リストは、最
適な順序と結線入力リストを作成するために、入力とし
て論理ブロック１６０に加えられる。論理ブロック１６
１で、ｐ側の結線セグメント・リストを決定するために
順序化用のデータが集められ、論理ブロック１６２はデ
バイスのｎ側に対してそれと同一のタスクを遂行する。
これらのセグメント・リストの各々における２つのセグ
メントは、末端セグメントとして識別される。ｐ側で
は、これらのセグメントのうち一方がＶＤＤ電力セグメ
ントとして、他方が出力点として働く。ｎ側では、これ
らのセグメントの一方がＧＮＤ（アース）セグメントと
なり、他方が出力セグメントとなる。末端セグメントの
割に振りは、論理ブロック１６３−１６６で示されるよ
うに、４通りあり、セグメント対トラックの割り振り及
び出力の結線を決定するように選択されている。出力と
さまざまなトランジスタの間の相互接続の数は、論理ブ
ロック１６７−１７０で決定される。各々の末端セグメ
ントの割り振りにはコストが関連づけられている。論理
ブロック１７１−１７４で示されるこのコストは、論理
ブロック１６３−１６６に示されている必要なトラック
の数及びｎ側出力からｐ側出力への接続の複雑さの測定
の関数である。次に、最も低いコストにつながる末端セ
グメントの割り振りが論理ブロック１７５で選択され、
対応するセグメントからトラックへの割り振りが論理ブ
ロック１７６で計算され、関数の必要な最終的なスティ
ック図として出力される。

第２３図は、第２２図の論理ブロック１６１及び１６２
中で実行される詳細な論理ブロックのフローチャートで
あり、これは結線セグメント及び末端セグメントを得る
ための手続である。第２３図において、結線入力リスト
から論理ブロック１８０にラインが読み込まれる。テー
ブル１に関与する結合処理を記憶したこのラインは、要
素ストリング、結合ストリング及びそれに関わるオペレ
ータをあらわす。このオペレータは、論理ブロック１８
１で示すように、ｐ側に由来するものか否かにつき判断
される。もしオペレータがｐ側に由来するなら、プログ
ラムは論理ブロック１８２に進みここでＡＮＤからＯＲ
（またはＯＲからＡＮＤ）に反転される。これは、Ｐ及
びｎ側の双対的な性質による。要素オペランドは、結合
オペランドであるかまたはタイプ１の原始オペランドで
あるかのどちらかである。もしそれが単に原始オペラン
ドであるなら、それらの末端セグメントは、そのオペラ
ンドに関連づけられたトランジスタのソース及びトレイ
ン位置に対応する点に縮退する。非原始的なオペランド
の末端セグメントは再帰的に生成される。尚、セグメン
トは、セグメント自体の両端に対応する一対の点により
決定されることに注意されたい。論理ブロック１８３で
は、末端セグメントが要素のために設定されているかど
うかが判断される。もしそうでなければ、プログラムは
論理ブロック１８４に進み、そこでセグメントは、第１
の要素オペランドの右端及び第２の要素オペランドの左
端に基づきソートされる。その結合が拡散領域の切れ目
を導入しない場合、論理ブロック１８５で示すように、
第１の要素の第２のセグメントの右端と、第２の要素の
第１のセグメントの右端との間に一致が見出されること
になる。論理ブロック１８５で示されるようにもし一致
が見出されないなら、論理ブロック１８７で示されるよ
うに２つの点を結ぶ結線セグメント出力リストに追加が
なされる。さらに、論理ブロック１８８で示すように、
オペレータがＯＲであるなら、論理ブロック１８９で示
すように、２つの末端セグメントを結線することも必要
である。ゆえに、論理ブロック１８８及び１８９は、第
１の要素の第１の末端セグメントの右端から第２の要素
の第２の末端セグメントの左端への結線セグメント・リ
ストに別のセグメントが出力されなくてはならないこと
を示している。

論理ブロック１９０で示すようにもしオペレータがＡＮ
Ｄであるなら、結合の末端セグメントは第１の要素の第
１のセグメント及び第２の要素の第２のセグメントであ
る。これらは、上述の一致に関与しない２つの要素であ
る。ＯＲオペレータの場合、末端セグメントは結線セグ
メント・リストのために上述のように生成された２つの
新しいセグメントである。論理ブロック１８７，１８９
及び１９３により示されるように、結線セグメント・リ
ストは末端リストと相まってこの手続の出力をなす。論
理ブロック１９２で、リストの終端に到達したか否かの
判断が行なわれる。そして、そうでないなら、もう一度
反復するために、プログラムは論理ブロック１８０に戻
る。他方、もしそれがリストの終端であるなら、プログ
ラムは論理ブロック１９３に進み末端セグメントが出力
される。

第２４図は、第２２図の論理ブロック１６３−１６６中
で示されたトラックの割り付けに関するより詳細な論理
フローチャートである。論理ブロック２００において示
されるように、結線セグメント・リストが読み込まれ
る。そしてプログラムは、セグメントのすべての閉集合
を検査するための手続をあらわす論理ブロック２０１及
び２０２に進む。セグメントの閉集合とは、別の閉集合
中のセグメントと端点を共有しないセグメントの集合で
ある。各閉集合は、端部として、その集合内にすべての
セグメントの端点の合併を有する網によってあらわされ
る。次にプログラムは、ｐ側が考慮されているのかどう
かを判断するために論理ブロック２０３に進む。そし
て、もし否ならば、最終結合の接地網をトラック１に割
り当てるために、プログラムは論理ブロック２０５に進
む。また、もしそうであれば、最終結合のＶＤＤ網をト
ラック１に割り当てるために、プログラムは論理ブロッ
ク２０４に進む。どちらの場合にも、トラック１はブロ
ックされる。次にプログラムは、論理ブロック２６に進
み、ここで電力網を除く網のリストが最左端の端子によ
ってソートされる。２から始まる最も小さい数のトラッ
クに各網を割り当てるために、グリーディ(greedy)アル
ゴリズム(greedy)が使用される。これはスティック・パ
ッキング(stick-packing)の従来の問題と同様である。
すべての網に割り当てが行なわれると、論理ブロック２
０７で示すように、ｎ側及びｐ側の各出力網を含むトラ
ックと、最後のトラックが交換される。次にプログラム
は、これがｐ側の動作であるか否かを再び判断するため
に、論理ブロック２０８へと進む。そして、もし否なら
ば、プログラムは論理ブロック２０９に進み、ｎトラッ
ク全体の方向は、ＧＮＤトラックが下になるように変更
される。プログラムは次に論理ブロック２１０に進み、
トラックの割り当てが出力される。

第２２図の論理ブロック１６７〜１７０で概要を示した
ように、ｐ側トラックは、ｎ側トラックの上方に配置さ
れ、これによりその２つの側の出力トラックは互いに近
接する。ここで出力間の接続が決定される。

第２５図及び第２６図は第１７図のステック図を具体化
するための手続の概要を示す論理フローチャートであ
る。これにより、この技術の規則及び影像の記述に従っ
てＣＭＯＳデバイスの全体の構成が得られる。この手続
の入力は論理ブロック２２０中で示されており、この入
力は、トランジスタの順序とｐ側及びｎ側にトラックの
割り付けを与えるスティック表示と、出力接続の経路と
から成っている。さらに、技術の規則と影像も、論理ブ
ロック２２１で示すようにプログラムの入力である。こ
れらは、デバイス間の許容された間隔、拡散領域間の最
小幅、接点のサイズ、バスのサイズなどを含む。プログ
ラムは、トランジスタ順序付けストリングの長さに比例
する幅と、割り付けにおけるトラックの数に比例する高
さをもつｐ型及びｎ型拡散井戸の特定のレイアウトを決
定するために論理ブロック２２２−２２３に進む。この
２つの井戸領域は、ｐ側拡散井戸領域がｎ側拡散井戸領
域よりも上になるように論理ブロック２２３及び２２４
でレイアウトされる。２つの井戸領域の幅は同一であ
り、トランジスタ順序付けストリングの数に正反例し、
一方トランジスタ順序付けストリングの数は、トランジ
スタの数と拡散領域の切れ目の数を加えたものに等し
い。次にプログラムは論理ブロック２２４、２２５及び
２２６に進む。金属条片は、電力を輸送するために、ｐ
側とｎ側に一本づつ、接地規則(ground rule)によって
要求される広さの幅でレイアウトされる。このバスは拡
散領域全体を横切って、ＶＤＤバス位置がｐ型井戸の上
部にありＧＮＤバスがｎ型井戸の下部にあるように延長
される。

順序付けストリングの各“Ｏ”−位置は絶縁デバイスに
対応する。そのような各位置に対して、接地規則によっ
て与えられる、垂直に延長され拡散領域に重なるポリシ
リコン条片がｎ側とｐ側とにレイアウトされる。こうし
て形成されたトランジスタから、ｎ側上のＧＮＤバス及
びｐ側上のＶＤＤバスへ接点が形成される。トランジス
タ順序づけストリング中の“Ｏ”でない各位置に対して
は、垂直ポリシリコン条片がレイアウトされる。この条
片は、論理ブロック２２４で示されるように、ｎ型井戸
の下部からｐ型井戸の上部へ延長されている。

プログラムは論理ブロック２２７に進む。この論理ブロ
ック２２７は、電力バス間のトラックが１つづつレイア
ウトされ、各網には水平の非接触金属セグメントが設け
られる。次にプログラムは論理ブロック２２８に進み、
ここで金属セグメントに対応する網の端子リストに従っ
て、各金属セグメントにおいて拡散領域に接点が形成さ
れる。次にプログラムは論理ブロック２２９に進み、こ
こで最終的に、ｐ側の出力セグメントをｎ側の出力セグ
メントに相互接続するために垂直金属セグメントがレイ
アウトされる。そして、最終的なＣＭＯＳレイアウトが
完成される。

Ｇ．発明の効果 この発明によれば、論理関数から、自動的にコンパクト
化されたＣＭＯＳブック・レイアウトが形成される。

【図面の簡単な説明】

第１図及び第２図は、特定のブール関数を実現する論理
回路を示す図、 第３図及び第４図は、第１図及び第２図の回路に対応す
るチップ上の回路レイアウト及び結線構造の図、 第５図及び第６図は、ブール表現のグラフを示す図、 第７図及び第８図は、コンパクト化されたチップ上の回
路レイアウト及び結線構造の図、 第９図及び第１０図は、ブール表現のグラフを示す図、 第１１図及び第１２図は、さらにコンパクト化されたチ
ップ上の回路レイアウト及び結線構造の図、 第１３図及び第１４図は、ブール表現のグラフを示す
図、 第１５図は、スタック配向技術を示す図、 第１６図は、制御プログラムの全体の概要フローチャー
ト、 第１７図は、レイアウトのスティック図、 第１８図は、第１６図における論理ブロック１０３の詳
細な動作を示すフローチャート、 第１９図は、チップ上の回路レイアウト及び結線構造の
図、 第２０図は、第１８図における論理ブロック１１０の詳
細な動作を示すフローチャート、 第２１図は、第２０図における論理ブロック１２４の詳
細な動作を示すフローチャート、 第２２図は、第１８図における論理ブロック１１１の詳
細な動作を示すフローチャート、 第２３図は、第２２図における論理ブロック１６１及び
１６２の詳細な動作を示すフローチャート、 第２４図は、第２２図における論理ブロック１６３−１
６６の詳細な動作を示すフローチャート、 第２５図及び第２６図は、第１７図のステック表示を実
際のＣＭＯＳレイアウトに変換するための動作を示すフ
ローチャートである。

Claims (3)

【特許請求の範囲】
1. 【請求項１】半導体チップ上にＣＭＯＳセルにより実現
   されるべき関数のブール表現から、および上記ＣＭＯＳ
   セルの表現を構成するデバイスの幅および間隔を規定す
   る所定の技術規則から、半導体チップ上のＣＭＯＳセル
   のレイアウトを演算装置を利用して自動的に生成するた
   めの方法において、 （ａ）上記実現されるべき関数のブール表現を上記演算
   装置中に読み込み、 （ｂ）上記ブール表現を特定の後置記法に変換し、 （ｃ）上記ブール表現の後置記法に応答して、上記ＣＭ
   ＯＳセルのレイアウトの表現を作成するために、回路の
   幅を最小にするように上記ＣＭＯＳセルのレイアウト内
   のトランジスタの最適配置順を決定しかつ上記ＣＭＯＳ
   セルのｐ側及びｎ個の高さが最小になるように水平金属
   トラックのトランジスタ結線セグメントの割り付けを決
   定し、 （ｄ）上記演算装置中に上記技術規則を読み込み、 （ｅ）上記ブール表現に基づき上記ＣＭＯＳセルのため
   のシリコン拡散層及び金属結線層の幾何形状を決定す
   る、 段階を具備するＣＭＯＳセル・レイアウトの形成方法。
2. 【請求項２】上記段階（ｃ）は、上記後置記法で表され
   たストリングの各要素を順に検査し、上記要素がオペラ
   ンドであれば該要素をそのタイプとともにプッシュ／ダ
   ウン・スタックに押し込み、上記要素がオペランドであ
   ればテーブルに記載された規則に従ってスタック中の上
   部オペランドの順序を組み立て、上記組み立てたオペラ
   ンドを上記プッシュ／ダウン・レジスタに押し込み、上
   記後置記法のストリングが全て処理されるまで上記プロ
   セスを続行する段階を含む請求項（１）記載のＣＭＯＳ
   セルのレイアウトの形成方法。
3. 【請求項３】上記段階（ｃ）は、セル上のパワー点と出
   力点とを４つの異なる組み合わせで割り付けし、割り付
   け毎に所定順序でトラックを結線路に割り当て、最小数
   のトラックを占める結果になるような割り付け及び割り
   当てを選択する段階を含む、請求項（１）記載のＣＭＯ
   Ｓセルのレイアウトの形成方法。