JP3078739B2 - トランジスタ概略配置方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ＣＭＯＳ等の電気
回路に使用されるスタンダードセル及びデータパス・リ
ーフセル等のＬＳＩにおけるリーフセルのレイアウト合
成方法に関し、特にレイアウト合成方法のうちのトラン
ジスタ概略配置方法に関する。

【０００２】

【従来の技術】昨今の半導体システムの設計自動化技術
の進展は、システム設計者に製造ファンドリの選択の自
由を与えるようになってきた。すなわち、システム設計
者及び設計ヴェンダーは、共通の設計データを基に、最
も低コストで、かつ、最も高度なプロセス技術を提供す
る製造ファンドリを選択することが可能となってきた。
この傾向により、各半導体メーカーのプロセス技術の差
がそのままＬＳＩの受注競争力に直結することとなり、
オープンな立場でのプロセス技術の競争が激化する様相
を示してきた。

【０００３】すなわち、プロセス技術競争の激化は、プ
ロセス技術革新を加速させることとなり、高性能なシス
テムの設計及び開発が、近い将来に実用化されるであろ
うプロセス技術に照準を合わせて計画又は実行されると
いった事態をも引き起こしている。

【０００４】プロセスの技術革新が次々に行なわれ、そ
れに呼応して高性能システムの設計開発が行われれば、
当然ながら、セル・ライブラリの開発頻度は非常に増大
してくる。例えば、５年前には２年に１シリーズのライ
ブラリを作成するという程度の開発であったのが、最近
では、以前の倍程度の規模のライブラリを半年に１シリ
ーズという頻度で開発しなければならなくなっている。

【０００５】また、プロセス技術の進歩によってディー
プ・サブミクロン時代に突入し、マスク設計ルールが一
層複雑化していることもセル・ライブラリ開発をさらに
難しくしている。マスク設計ルールについては、例え
ば、５年前には３０個程度のルール数で十分であったの
が、現在では１００個を超えるルールを必要とするた
め、また、製造コストや歩留りに大きく影響を与えるル
ールも多く、早期にマスク設計ルールを決定することが
難しくなってきている。

【０００６】従って、セル・ライブラリの開発は、セル
・ライブラリを期限内に開発又は提供するために、マス
ク設計ルールが確定しないうちにセル設計をスタートさ
せ、マスク設計ルールが確定した時点で最終のレイアウ
ト修正を行なうといった方法を採らざるを得なくなって
きている。セル・ライブラリ開発に対するこのような状
況の変化は今後も一層進むものと考えられており、特に
セルのレイアウト設計をほとんど人手のみに頼っている
現状では、近い将来においてセル・ライブラリ開発に課
せられる要求に対して、十分な対応ができなくなること
は明らかである。

【０００７】以上説明した背景をもとにして、セルのレ
イアウト設計を自動化するためのセル・レイアウト合成
技術の重要性が強く認識されるようになってきた。セル
・レイアウト合成技術にとっての一番の課題は、いかに
して人手並みの集積度を達成するかである。

【０００８】以下、従来のセル・レイアウト合成方法を
図面を参照しながら説明する。

【０００９】図１５は、従来の代表的なセル・レイアウ
ト合成方法であって、図１５（ａ）はコンパクション技
術を用いないセル・レイアウト合成方法であり、図１５
（ｂ）はコンパクション技術を用いたセル・レイアウト
合成方法である。

【００１０】図１５（ａ）に示すセル・レイアウト合成
方法は、レイアウト完成時と全く等しいマスク設計ルー
ルに従ったトランジスタの配置位置を導出するトランジ
スタ配置ＳＵ１と、配置が完了したトランジスタの接続
端子間の配線を行なうトランジスタ間配線ＳＵ２とによ
りレイアウトを完成させる。この方法の例として、「T.
Uehara and W.M.vanCleemput, "Optimal Layout of
CMOS Logic Cells," 25th ACM/IEEE Trans. Co
mputer Vol.c-30, pp.305-312, May 1981」に開示さ
れるように、Ｐ型ＭＯＳトランジスタとＮ型ＭＯＳトラ
ンジスタをそれぞれ１列に同じ向きに配置して、グラフ
のアルゴリズムを用いることにより、できるだけ多くの
トランジスタ拡散領域の共有化を行なえるように、配置
の順番とＭＯＳトランジスタのソース及びドレインの向
きとを最適化するという方法がある。

【００１１】図１５（ｂ）に示すセル・レイアウト合成
方法は、あらかじめ配置要素であるトランジスタのおお
よその位置を決定するトランジスタ概略配置ＳＵ１１
と、トランジスタ間配線ＳＵ１２と、トランジスタの配
置を最も密に充てんするコンパクションＳＵ１３により
レイアウトを完成させる。

【００１２】最終レイアウトをマスク設計ルールに合わ
せるための処理は全てコンパクションＳＵ１３により行
なうため、トランジスタ概略配置ＳＵ１１は、トランジ
スタ同士の位置的相対関係について大局的に最適化した
結果を導くことを目的とする。ここにいうコンパクショ
ンＳＵ１３の例として、「Hyunchul Shin, AlbertoL.
Sangiovanni-Vincentelli, "Two-Dimensional Comp
action by 'ZoneRefining' ," 23rd DAC, pp.115-
119, 1986」または、「特願平６−２２０１３４」に記
されている方法があり、後者は配線機能を含めたコンパ
クタを提案している。

【００１３】図１５（ａ）に示すセル・レイアウト合成
方法と図１５（ｂ）に示すセル・レイアウト合成の方法
とを比較すると、トランジスタのレイアウト形態を決め
る際に主たる役割を担うトランジスタ配置又はトランジ
スタ概略配置の工程においてマスク設計ルールに強く縛
られる必要がない、図１５（ｂ）に示す方法の方が、図
１５（ａ）に示す方法よりも多様なレイアウト形態に容
易に対応できる。

【００１４】また、トランジスタのレイアウトを最適化
するには、トランジスタを縦向きか横向きかのいずれの
向きに配置することも可能であって、各チャネルは部分
的にトランジスタが２列以上配置されても構わない等の
形態に対する柔軟性が必要である。このような柔軟性を
実現するにはコンパクションＳＵ１３を備えた図１５
（ｂ）に示すセル・レイアウト合成方法の方が有利であ
り、実際前記「特願平６−２２０１３４」に記されてい
るような、人手並みの多様なレイアウト形態に対応でき
るコンパクタは既に実現されている。

【００１５】

【発明が解決しようとする課題】しかしながら、前記従
来のトランジスタ概略配置方法は、各チャネル内におい
てトランジスタを１列に配置するという制約を設けるこ
と及びトランジスタ間の拡散領域の共有を最大にすると
いう配置目的を設けることによって配置の条件を単純化
しているため、人手設計に比較してセル面積の最小化が
困難であるという問題を有していた。人手を用いた設計
によりセル・レイアウトを行なう際には、チャネル内に
トランジスタを２列以上配置したり、トランジスタの縦
横の向きを変えたりなどしてセル面積の最小化を図って
いる場合が多く、また、トランジスタの拡散領域の共有
面積を最大にすることが必ずしもセル面積の最小化に結
び付かない場合も同様に数多く見られる。

【００１６】本発明は前記従来の問題を解決し、計算機
を用いてセル内のトランジスタの概略配置を人手設計並
みに最適化することを目的とする。

【００１７】

【課題を解決するための手段】前記の目的を達成するた
め、本発明は、セルを行列表現とするモデル化、該モデ
ルを用いた最適化のための配置評価関数の定義及び前記
モデル上での最適化のための配置改善方法を導入するも
のである。

【００１８】具体的に請求項１の発明が講じた解決手段
は、半導体製造技術から導かれるマスク設計ルール並び
に、セルの入出力端子及びトランジスタの電極の各接続
要求情報と前記トランジスタのサイズ情報とからなるネ
ットリストを用いて、計算機により前記セルをレイアウ
トするセル・レイアウト合成方法のうちの前記トランジ
スタのおおよその配置を決定するトランジスタ概略配置
方法を対象とし、前記セルを、該セルにおけるＰチャネ
ル領域とＮチャネル領域との境界線に対して平行な直線
と前記境界線に対して垂直な直線とにより方形に区切っ
て、前記方形を要素とする方形行列を生成する第１の工
程と、前記ネットリストに登録されている前記セルの入
出力端子及びトランジスタを配置要素として、各配置要
素を前記方形行列の１つの方形に互いに重複することな
く割り当てて初期配置する第２の工程と、前記方形行列
上の配置結果が最適化されているか否かを評価するため
の配置評価関数を定義して、該配置評価関数の出力結果
を評価する第３の工程と、前記出力結果に基づいて、前
記配置結果が最適化されているか否かを判定した後、前
記配置結果が最適化されていない場合は、前記方形行列
上における各配置要素の配置を変更して配置改善を行な
う第４の工程とを備えており、前記第３及び第４の工程
を、前記配置評価関数の出力結果が最適化されるまで繰
り返す構成とするものである。

【００１９】請求項１の構成により、セルはＰチャネル
領域とＮチャネル領域との境界線に対して平行な直線と
前記境界線に対して垂直な直線とにより方形に区切られ
た方形行列からなる２次元配置モデルとされ、定義され
た配置評価関数は方形行列上の配置結果が最適化されて
いるか否かを評価すると共に、配置改善方法により配置
評価関数の出力結果が最適化されるまで配置変更が繰り
返されるため、多様なトランジスタ・レイアウト形態を
自動合成できる。

【００２０】請求項２の発明は、請求項１の構成に、前
記第１の工程は、前記方形行列の方向を、該方形行列の
行番号が増す方向を下向き、前記行番号が減る方向を上
向き、前記方形行列の列番号が増す方向を右向き及び前
記列番号が減る方向を左向きとして定義されると共に、
前記方形行列の行数を、前記トランジスタのゲート幅方
向が前記左向き又は右向きとなる横置きトランジスタを
前記方形行列の列方向に並べられる最大個数から求め、
且つ、前記方形行列の列数を、前記ネットリストに登録
されている前記トランジスタの個数から求めることによ
り生成する工程と、前記トランジスタからなる配置要素
が前記方形行列に配置される方向を、ゲートに対して上
側にドレインが位置し且つ前記ゲートに対して下側にソ
ースが位置する方向を上向きと、前記トランジスタのゲ
ートに対して上側にソースが位置し且つ前記ゲートに対
して下側にドレインが位置する方向を下向きと、前記ト
ランジスタのゲートに対して右側にドレインが位置し且
つ前記ゲートに対して左側にソースが位置する方向を右
向きと、前記トランジスタのゲートに対して右側にソー
スが位置し且つ前記ゲートに対して左側にドレインが位
置する方向を左向きと定義する工程とを含む構成を付加
するものである。

【００２１】請求項２の構成により、方形行列の方向が
規定され、方形行列の行数はトランジスタのゲート幅方
向が前記左向き又は右向きとなる横置きトランジスタが
方形行列の列方向に並べられる最大個数から求められ、
列数はネットリストに登録されている前記トランジスタ
の個数から求められると共にトランジスタからなる配置
要素が配置される向きが定義されているため、トランジ
スタの２次元的かつ多様な配置形態に柔軟に対応でき
る。

【００２２】請求項３の発明は、請求項２の構成に、前
記第３の工程における前記配置評価関数は、前記配置要
素が前記方形行列上の１つの方形にのみ割り当てられ、
前記配置要素に対応するトランジスタの前記ネットリス
ト内のゲート幅を表わしているトランジスタのサイズに
応じて、割り当てられた前記１つの方形からゲート方向
に延びる一連の方形に隣接する他の方形に対して割り当
ての影響力が及ぶ割り当て状態を表現して、前記割り当
て状態に基づいて、互いに隣接する配置要素同士がトラ
ンジスタの拡散領域を共有できる場合には共有させるこ
とにより、前記配置要素間の上下方向及び左右方向の隣
接関係を求めて、前記隣接関係に基づいて、各配置要素
がそれぞれ割り当てられた方形の上下方向及び左右方向
の長さと、互いに隣接する前記方形間の距離とを求め
て、前記配置要素間の全ての配線についての総和を前記
長さ及び距離を用いて計算する構成を付加するものであ
る。

【００２３】請求項３の構成により、他の方形に対して
割り当ての影響力が及ぶ割り当て状態を表現すると共に
拡散領域の共有化を考慮する配置評価関数は、割り当て
状態に基づいて隣接関係を求めた後、該隣接関係に基づ
いて各配置要素が割り当てられた方形の上下左右の各方
向の長さと、互いに隣接する方形間の距離とを求めて、
配置要素間の全ての配線についての総和を計算するた
め、実際のレイアウトにおける配線長を適確に反映す
る。

【００２４】請求項４の発明は、請求項３の構成に、前
記配置評価関数は、前記セル内を流れる信号の方向をあ
らかじめ指定すると共に、同一の電位に接続されるべき
前記セル内の配置要素の集合であるネットに対して前記
配置要素の配置状態から前記ネット内を流れる信号の方
向を求めて、前記ネット内を流れる信号方向が前記セル
内を流れる信号方向と一致していない場合は、一致する
場合よりも前記配置要素間の配線の長さを一定の割合で
延長して評価する構成を付加するものである。

【００２５】請求項４の構成により、配置評価関数は、
ネット内の信号方向がセル内の信号方向と一致していな
い場合は、一致する場合よりも配置要素間の配線の長さ
を一定の割合で延長して評価するため、ネット内の信号
方向がセル内の信号方向と一致するまで配置改善を繰り
返す可能性を高くする。

【００２６】請求項５の発明は、請求項１〜４の構成
に、前記第４の工程における前記配置改善は、選択され
た配置要素を９０度を単位に回転させる回転と、選択さ
れた配置要素と該配置要素とは異なる他の配置要素との
交換と、選択された配置要素を配置要素が割り当てられ
ていない空方形に移動させる移動と、選択された配置要
素を方形間の境界線上に移動させる境界線上への移動と
の４つの形式を用いて行なわれ、前記方形間の境界線上
への移動は、選択された配置要素を前記境界線に隣接す
る方形のいずれか１つの方形に割り当てた後、前記方形
を含めて隣接する一連の方形に対して前記方形上に配置
されていた配置要素を、割り当てられた配置要素が重複
しなくなるまで１方形ずつ順にずらすことにより、前記
方形行列上の各配置要素をいずれか１つの方形に割り当
てる形式とする構成を付加するものである。

【００２７】請求項５の構成により、配置改善を、配置
要素の向きを９０度を単位に回転させる回転と、配置要
素と他の配置要素との交換と、配置要素を他の配置要素
が割り当てられていない空方形に移動させる移動と、方
形間の境界線上への移動との４つの形式を用いて行なう
ため、多様なトランジスタの配置形態に柔軟に対応でき
る。

【００２８】請求項６の発明は、半導体製造技術から導
かれるマスク設計ルール並びに、セルの入出力端子及び
トランジスタの電極の各接続要求情報と前記トランジス
タのサイズ情報とからなるネットリストを用いて、計算
機により前記セルをレイアウトするセル・レイアウト合
成方法のうちの前記トランジスタのおおよその配置を決
定するトランジスタ概略配置方法を対象とし、前記セル
を、該セルにおけるＰチャネル領域とＮチャネル領域と
の境界線に対して平行な第１の直線と前記境界線に対し
て垂直な第２の直線とにより方形に区切って、前記方形
を要素とする方形行列を生成する第１の工程と、前記ネ
ットリストに登録されている前記セルの入出力端子及び
トランジスタ並びに該トランジスタの各サイズの総和に
対して所定の割合により個数が求められる基板コンタク
トを配置要素として、各配置要素を前記方形行列の１つ
の方形に互いに重複することなく割り当てて初期配置す
る第２の工程と、前記方形行列上の配置結果が最適化さ
れているか否かを評価するための配置評価関数を定義し
て、該配置評価関数の出力結果を評価する第３の工程
と、前記出力結果に基づいて、前記配置結果が最適化さ
れているか否かを判定した後、前記配置結果が最適化さ
れていない場合は、前記方形行列上における各配置要素
の配置を変更して配置改善を行なう第４の工程とを備え
ており、前記第３及び第４の工程を、前記配置評価関数
の出力結果が最適化されるまで繰り返す構成とするもの
である。

【００２９】請求項６の構成により、セルはＰチャネル
領域とＮチャネル領域との境界線に対して平行な直線と
前記境界線に対して垂直な直線とにより方形に区切られ
た方形行列からなる２次元配置モデルとされ、定義され
た配置評価関数はトランジスタの各サイズの総和に対し
て所定の割合により基板コンタクトの個数を求めた後、
該基板コンタクトをも配置要素として追加して方形行列
上の配置結果が最適化されているか否かを評価すると共
に、配置改善方法により配置評価関数の出力結果が最適
化されるまで配置変更が繰り返されるため、、基板コン
タクトを含めた多様なトランジスタ・レイアウト形態を
自動合成できる。

【００３０】請求項７の発明は、請求項６の構成に、前
記第１の工程は、前記方形行列の方向を、該方形行列の
行番号が増す方向を下向き、前記行番号が減る方向を上
向き、前記方形行列の列番号が増す方向を右向き及び前
記列番号が減る方向を左向きとして定義すると共に、前
記方形行列の行数を、前記トランジスタのゲート幅方向
が前記左向き又は右向きとなる横置きトランジスタを前
記方形行列の列方向に並べられる最大個数から求め、且
つ、前記方形行列の列数を、前記ネットリストに登録さ
れている前記トランジスタの個数から求めることにより
生成する工程と、前記トランジスタからなる配置要素が
前記方形行列に配置される方向を、ゲートに対して上側
にドレインが位置し且つ前記ゲートに対して下側にソー
スが位置する方向を上向きと、前記トランジスタのゲー
トに対して上側にソースが位置し且つ前記ゲートに対し
て下側にドレインが位置する方向を下向きと、前記トラ
ンジスタのゲートに対して右側にドレインが位置し且つ
前記ゲートに対して左側にソースが位置する方向を右向
きと、前記トランジスタのゲートに対して右側にソース
が位置し且つ前記ゲートに対して左側にドレインが位置
する方向を左向きと定義する工程とを含む構成を付加す
るものである。

【００３１】請求項７の構成により、方形行列の方向が
規定され、方形行列の行数はトランジスタのゲート幅方
向が前記左向き又は右向きとなる横置きトランジスタが
方形行列の列方向に並べられる最大個数から求められ、
列数はネットリストに登録されている前記トランジスタ
の個数から求められると共にトランジスタからなる配置
要素が配置される向きが定義されているため、トランジ
スタの２次元的かつ多様な配置形態に柔軟に対応でき
る。

【００３２】請求項８の発明は、請求項７の構成に、前
記第２の工程は、前記基板コンタクトからなる前記配置
要素を、前記Ｐチャネル領域においてはソースが電源配
線に接続されるトランジスタからなる前記配置要素に隣
接して配置すると共に、前記Ｎチャネル領域においては
ソースがグランド配線に接続されるトランジスタからな
る前記配置要素に隣接して配置し、且つ、前記トランジ
スタのゲート長方向に隣接する場合は該トランジスタの
ソース側に隣接するように配置する工程を含む構成を付
加するものである。

【００３３】請求項８の構成により、基板コンタクトか
らなる配置要素は、Ｐチャネル領域においてはソースが
電源配線に接続されるトランジスタからなる配置要素に
隣接して配置されると共に、Ｎチャネル領域においては
ソースがグランド配線に接続されるトランジスタからな
る配置要素に隣接して配置され、且つ、トランジスタの
ゲート長方向に隣接される場合は該トランジスタのソー
ス側に隣接するように配置されるため、配置要素として
基板コンタクトを付加した場合にも確実に対応できる。

【００３４】請求項９の発明は、請求項８の構成に、前
記第３の工程における前記配置評価関数は、前記配置要
素が前記方形行列上の１つの方形にのみ割り当てられ、
前記配置要素に対応するトランジスタの前記ネットリス
ト内のゲート幅を表わしているトランジスタのサイズに
応じて、割り当てられた前記１つの方形からゲート方向
に延びる一連の方形に隣接する他の方形に対して割り当
ての影響力が及ぶ割り当て状態を表現して、前記割り当
て状態に基づいて、互いに隣接する配置要素同士がトラ
ンジスタの拡散領域を共有できる場合には共有させるこ
とにより、前記配置要素間の上下方向及び左右方向の隣
接関係を求めて、前記隣接関係に基づいて、前記基板コ
ンタクトからなる配置要素を除く各配置要素がそれぞれ
割り当てられた方形の上下方向及び左右方向の長さと、
互いに隣接する前記方形間の第１の距離とを求めると共
に、前記基板コンタクトからなる全ての配置要素と前記
境界線との第２の距離を求めて、前記配置要素間の全て
の配線についての総和を前記長さ、第１の距離及び第２
の距離を用いて計算する構成を付加するものである。

【００３５】請求項９の構成により、他の方形に対して
割り当ての影響力が及ぶ割り当て状態を表現すると共に
拡散領域の共有化を考慮する配置評価関数は、割り当て
状態に基づいて隣接関係を求めた後、該隣接関係に基づ
いて基板コンタクトからなる配置要素を除く各配置要素
が割り当てられた方形の上下左右の各方向の長さと、互
いに隣接する方形間の第１の距離及び基板コンタクトか
らなる配置要素と前記境界線との第２の距離とを求め
て、配置要素間の全ての配線についての総和を計算する
ため、基板コンタクトを含めて実際のレイアウトにおけ
る配線長を適確に反映する。

【００３６】請求項１０の発明は、請求項９の構成に、
前記配置評価関数は、前記セル内を流れる信号の方向を
あらかじめ指定すると共に、同一の電位に接続されるべ
き前記セル内の配置要素の集合であるネットに対して前
記配置要素の配置状態から前記ネット内を流れる信号の
方向を求めて、前記ネット内を流れる信号方向が前記セ
ル内を流れる信号方向と一致していない場合は、一致す
る場合よりも前記配置要素間の配線の長さを一定の割合
で延長して評価する構成を付加するものである。

【００３７】請求項１０の構成により、配置評価関数
は、ネット内の信号方向がセル内の信号方向と一致して
いない場合は、一致する場合よりも配置要素間の配線の
長さを一定の割合で延長して評価するため、ネット内の
信号方向がセル内の信号方向と一致するまで配置改善を
繰り返す可能性を高くする。

【００３８】請求項１１の発明は、請求項６〜１０の構
成において、前記第４の工程における前記配置改善は、
選択された配置要素を９０度を単位に回転させる回転
と、選択された配置要素と該配置要素とは異なる他の配
置要素との交換と、選択された配置要素を配置要素が割
り当てられていない空方形に移動させる移動と、選択さ
れた配置要素を方形間の境界線上に移動させる境界線上
への移動との４つの形式を用いて行なわれ、前記方形間
の境界線上への移動は、選択された配置要素を前記境界
線に隣接する方形のいずれか１つの方形に割り当てた
後、前記方形を含めて隣接する一連の方形に対して前記
方形上に配置されていた配置要素を、割り当てられた配
置要素が重複しなくなるまで１方形ずつ順にずらすこと
により、前記方形行列上の各配置要素をいずれか１つの
方形に割り当てる形式であって、前記第４の工程は、請
求項６〜１０の構成に、前記基板コンタクトからなる前
記配置要素を、前記Ｐチャネル領域においてはソースが
前記電源配線に接続されるトランジスタからなる前記配
置要素に隣接して配置すると共に、前記Ｎチャネル領域
においてはソースが前記グランド配線に接続されるトラ
ンジスタからなる前記配置要素に隣接して配置し、且
つ、前記トランジスタのゲート長方向に隣接する場合は
該トランジスタのソース側に隣接するように配置する工
程を含む構成を付加するものである。

【００３９】請求項１１の構成により、配置改善を、配
置要素の向きを９０度を単位に回転させる回転と、配置
要素と他の配置要素との交換と、配置要素を他の配置要
素が割り当てられていない空方形に移動させる移動と、
方形間の境界線上への移動との４つの形式を用いて行な
うと共に、基板コンタクトからなる前記配置要素を、Ｐ
チャネル領域においてはソースが電源配線に接続される
トランジスタからなる配置要素に隣接して配置し、ま
た、Ｎチャネル領域においてはソースがグランド配線に
接続されるトランジスタからなる配置要素に隣接して配
置し、且つ、前記トランジスタのゲート長方向に隣接す
る場合は該トランジスタのソース側に隣接するように配
置するため、基板コンタクトを含めた多様なトランジス
タの配置形態に柔軟に対応できる。

【００４０】

【発明の実施の形態】本発明はセル・レイアウト合成方
法に関するものであるが、セル・レイアウト合成技術の
中でも特にトランジスタ概略配置技術に関する新しい方
法の提案である。

【００４１】以下、本発明の第１の実施形態を図面に基
づいて説明する。

【００４２】（第１の実施形態）図１は本発明の第１の
実施形態に係るトランジスタ概略配置方法を示すフロー
チャートである。図１において、まず、ステップＳＴ１
は、計算機の記憶装置等からネットリストを読み込ん
で、配置対象となるトランジスタ及びセルの入出力端子
についての接続要求並びに各トランジスタのトランジス
タ・サイズに関する情報を内部に記憶する工程である。

【００４３】次に、ステップＳＴ２は、セル内のＰチャ
ネルとＮチャネルとの境界線に平行な直線と該境界線に
垂直な直線とにより方形群に分割して、トランジスタの
レイアウト領域に１つの行列を形成する工程である。こ
れらの方形群によって形成される行列を方形行列と呼ぶ
ことにする。なお、行番号及び列番号の付け方は一般の
行列に同じとし、１組の行列アドレスが１つの方形に対
応している。

【００４４】次に、ステップＳＴ３は、ステップＳＴ１
において記憶されたトランジスタ及びセルの入出力端子
を配置要素として、各配置要素をステップＳＴ２におい
て生成された方形行列上の１つの方形に互いに重複する
ことなく割り当てる工程である。

【００４５】本実施形態によるトランジスタ概略配置
は、方形行列上の方形に対する配置要素の割り当てを、
一定の評価基準に従って最適化することにより配置する
ものであり、ステップＳＴ３における割り当てはその初
期配置として行なう。また、本実施形態によるトランジ
スタ概略配置は、繰り返し改善アルゴリズムを用いるこ
とによって、以下に示すステップＳＴ４、ステップＳＴ
５、ステップＳＴ６及びステップＳＴ７からなる一連の
処理を繰り返して、配置の最適化を行なう。繰り返し改
善アルゴリズムとして、シミュレーテッド・アニーリン
グ法又はグリーディー法等が考えられるが、特定のアル
ゴリズムに限定されるものではない。

【００４６】次に、ステップＳＴ４は、一定の評価基準
にしたがって、方形行列上の配置状態を評価する工程で
ある。実際のマスクレイアウトが最適化されるように方
形行列上の配置状態を評価するには、方形行列上におけ
る配置評価関数を注意深く定義する必要があるが、配置
評価関数の例については後述する。また、前述したよう
に、本実施形態による配置処理を実行すれば、ステップ
ＳＴ４は何度も繰り返して実行されることになるため、
ステップＳＴ４では常に、１つの配置状態の評価が終わ
った時点で、現状の配置状態とその１つ前の配置状態と
の２つの配置状態についての評価値を記憶して、この評
価値を次の配置状態の評価が終わるまで保持しておく。
ただし、初期配置の直後においては、記憶される評価値
は１つである。

【００４７】次に、ステップＳＴ５は、ステップＳＴ４
において評価された配置状態を新しい配置状態として受
け入れるか否かの判定を行なう工程である。判定の際
に、ステップＳＴ４において保持しておいた２つの配置
状態についての評価値を比較して、繰り返し改善アルゴ
リズムに固有のスケジューリングがされた判定基準に基
づいて、判定を下すことになる。

【００４８】次に、ステップＳＴ６は、繰り返し改善を
続けるか否かの判定を下す工程である。定数を１つ設け
ておいて、ステップＳＴ４において新しく評価された配
置状態の評価値が、１つ前の評価値よりも改善されてい
ないという現象が一定回数以上連続して起こった場合
は、もはや改善が望めないとして改善処理を終了する。

【００４９】次に、ステップＳＴ７は、１回分の配置改
善を行なって、方形行列上の配置要素の配置状態を変更
する工程である。１回の配置改善により可能な変更形式
は、主として配置要素同士の位置交換または配置要素の
空方形への移動であり、その詳細は後述する。

【００５０】次に、方形行列上におけるトランジスタの
表現方法、配置評価関数の定義方法及び方形行列上にお
ける配置改善方法について、特にそれらが前記の処理の
流れの中に用いられることによる効果について、図面を
参照しながら説明する。

【００５１】図２は請求項２及び７に記載のトランジス
タ概略配置方法の方形行列を示す図である。図２に示す
ように、セル１０の内部をＰチャネル領域１１とＮチャ
ネル領域１２とに区切る境界線をチャネル境界線１３と
し、チャネル境界線１３に対して平行な方向を左右方向
とする。Ｐチャネル領域１１の反チャネル境界線側であ
るセル１０の一方の端部に電源配線１４が配設され、Ｎ
チャネル領域１２の反チャネル境界線側であるセル１０
の他方の端部にグランド配線１５が配設された、縦方向
のレイアウト領域が制限されているスタンダード・セル
を例にとる。

【００５２】電源配線１４及びグランド配線１５に挟ま
れた領域に方形１６を要素とする方形行列１７を定義す
る。１８は互いに隣接する方形間の境界線１８である。
方形行列１７の行数及び列数は、配置処理中において変
更可能ではあるが、初期設定として、列数をネットリス
トに記述されたトランジスタの数と同数に設定し、ま
た、行数を、Ｐチャネル領域１１及びＮチャネル領域１
２を合わせた縦方向に、ゲート幅方向が左右方向となる
トランジスタを横置きとして積むことができる最大数と
同数に設定する。なお、縦積みできる最大数はＰチャネ
ル領域１１及びＮチャネル領域１２についてそれぞれ存
在し、方形行列１７上にチャネル境界線１３を設定して
いるため、トランジスタからなる配置要素についてはチ
ャネル境界線１３を越えて移動することはできない。ま
た、方形行列１７上において、行番号が減少する方向を
上向きとし、増加する方向を下向きとする。同様に、列
番号が減少する方向を左向きとし、増加する方向を右向
きとする。

【００５３】本実施形態においては、トランジスタ配置
の向きについて、ゲート幅方向がセル１０の上下方向に
沿う場合をトランジスタの縦置きとし、ゲート幅方向が
セルの左右方向に沿う場合をトランジスタの横置きと
し、これら２通りの配置方向を許して配置処理を行な
う。すなわち、トランジスタが斜め方向を向くような配
置形態は考えない。ただし、トランジスタを配置する際
に、ソース及びドレインの区別をつける必要があるの
で、トランジスタからなる配置要素には向きの自由度と
して「上、下、左、右」の４つの向きを用意する。

【００５４】図３は請求項２及び７に記載のトランジス
タ概略配置方法のトランジスタの向きを示す図である。
図３に示すように、トランジスタの上向きは、トランジ
スタ２０のゲート２０ｇが左右方向に延び、ゲート２０
ｇに対して上側にドレイン２０ｄが位置し、ゲート２０
ｇに対して下側にソース２０ｓが位置する配置とする。
トランジスタの下向きは、トランジスタ２１のゲート２
１ｇが左右方向に延び、ゲート２１ｇに対して上側にソ
ース２１ｓが位置し、ゲート２１ｇに対して下側にドレ
イン２１ｄが位置する配置とする。トランジスタの左向
きは、トランジスタ２２のゲート２２ｇが上下方向に延
び、ゲート２２ｇに対して左側にドレインス２２ｄが位
置し、ゲート２２ｇに対して右側にソース２２ｓが位置
する配置とする。トランジスタの右向きは、トランジス
タ２３のゲート２３ｇが上下方向に延び、ゲート２３ｇ
に対して右側にドレインス２３ｄが位置し、ゲート２３
ｇに対して左側にソース２３ｓが位置する配置とする。

【００５５】また、トランジスタからなる配置要素に、
各トランジスタのトランジスタ・サイズに応じた大きさ
を与える。すなわち、各配置要素は方形行列１７上にお
いて１つの方形しか割り当てられないが、大きさを持つ
トランジスタからなる配置要素は、この大きさを一連の
方形群に反映させることにより、割り当てられた方形以
外の、前記方形に隣接して連なる方形に対して影響を及
ぼすことができる。

【００５６】図４は第１の実施形態に係るトランジスタ
概略配置方法のトランジスタからなる配置要素の大きさ
を示す図であって、図４（ａ）に示すように、相対的に
ゲート幅の長いトランジスタＡとトランジスタＡよりも
ゲート幅の短いトランジスタＢを方形行列上に配置する
場合を想定する。図４（ｂ）に示すように、方形行列上
において、トランジスタＡは方形３０に割り当てられて
いるが、方形３１及び方形３２に対しても存在の影響力
を及ぼすこととする。方形３０から影響力が及ぼされて
いる状態の方形３１には、第１の占有フラグ３３を与え
ておき、方形３２には、第２の占有フラグ３４を与えて
おく。

【００５７】このように、トランジスタＡからなる配置
要素によって影響を受けている方形３１及び方形３２に
は他の配置要素を割り当てることができないとすること
により、トランジスタからなる配置要素は方形行列上に
おいても、トランジスタ・サイズを主張することが可能
となるため、トランジスタ・サイズを考慮した配置の最
適化を行なうことができる。

【００５８】方形行列上において、トランジスタからな
る配置要素に与えられる向きと大きさとは、本実施形態
のトランジスタ概略配置方法に、トランジスタの２次元
的かつ多様な配置形態を柔軟に最適化する可能性を与え
るという非常に重要な役割を果たす。

【００５９】以下、第１の実施形態に係るトランジスタ
概略配置方法の配置評価関数の定義方法を図面を参照し
ながら説明する。本発明によるトランジスタ概略配置方
法の基本は、配線長の総和を最小化することにより、セ
ル内の信号の流れに沿ったトランジスタ配置を実現する
ことができるため、結果としてトランジスタ配置の最適
化を図ることができるという考えに基づいている。以
下、請求項３及び請求項４に記載の配置評価関数につい
て詳細を説明する。

【００６０】図５は請求項３及び請求項４に記載のトラ
ンジスタ概略配置方法の配置評価関数を定義するための
方形行列上の長さ及び距離を示す図である。図４におい
て説明したように、トランジスタからなる配置要素は大
きさを持ち、隣接して連なる方形に対して影響を及ぼし
ており、影響の及んでいる方形には占有フラグを立てる
ことにより、他の配置要素は占有フラグが立てられてい
る方形に入ることができない。

【００６１】まず、占有フラグについて説明する。

【００６２】図５（ａ）に示すように、トランジスタＡ
とトランジスタＢとが互いに拡散領域を共有して上下方
向（縦置き）に配置されており、トランジスタＣとトラ
ンジスタＤとが互いに拡散領域を共有してトランジスタ
Ｂの右側に同じく上下方向に配置されており、トランジ
スタＥがトランジスタＣ及びトランジスタＤの上側に左
右方向（横置き）に配置されている。

【００６３】図４（ｂ）においても説明したように、方
形行列上において、トランジスタからなる配置要素が割
り当てられている方形に隣接して連なる方形に対して及
ぼす影響を、隣接して連なる方形に立てた占有フラグに
よって表現する。図５（ａ）に示すように、占有フラグ
４１等は記号「↑、↓、←、→」を用いて表わされてお
り、例えば「↑」は、占有フラグ４１の立つ方形が、前
記方形よりも下に位置する配置要素４０から影響を受け
ていることを意味する。さらに、占有フラグ「↑」の立
つ方形の右隣の方形に配置要素４２が存在すると、占有
フラグ４１によって影響を与えている配置要素４０と右
隣の方形に割り当てられた配置要素４２とは、左右方向
に隣接関係を持っていることになる。従って、方形行列
上の配置要素による占有フラグを全ての配置要素につい
て設定した状態から、配置要素間の隣接関係を求めるこ
とができる。

【００６４】次に、方形行列上の配置要素の長さ及び配
置要素間の距離を求める。

【００６５】まず、互いに隣接するトランジスタ間の隣
り合う拡散ノード（ソース又はドレイン）が同電位であ
るならば、拡散領域を共有化させることができるため、
拡散領域を共有化できる隣接関係について、拡散コンタ
クトが必要か又は不要かをも含めてネットリストを探索
しておく。

【００６６】方形行列上への配置要素の配置、トランジ
スタからなる配置要素による占有フラグの設定及び配置
要素間の隣接関係の探索により、方形行列上の各方形の
縦及び横の長さの和である大きさと隣接する方形間の距
離とを定めることができる。なお、長さには、マスク設
計ルールを反映していても反映していなくても構わな
い。

【００６７】次に、本実施形態の特徴として、例えば、
トランジスタからなる配置要素が縦置きに割り当てられ
た方形について、トランジスタの拡散ノードに拡散コン
タクトを形成する必要がなければ、拡散コンタクトが必
要な場合よりも短い長さを前記方形の左右方向の幅とし
て設定する。また、図５（ｂ）に示すトランジスタＡか
らなる配置要素とトランジスタＢからなる配置要素とが
割り当てられた隣接する方形間について、拡散領域が共
有化されていれば、共有化のできない場合よりも短い長
さを前記隣接方形間の距離として設定して、状況による
長さの設定を差別化する。すなわち、図５（ｂ）に示す
ように、互いに拡散領域を共有しているトランジスタＡ
からなる配置要素４０とトランジスタＢからなる配置要
素４２との距離ｘ１は、互いに拡散領域が共有できない
トランジスタＢからなる配置要素４２とトランジスタＣ
からなる配置要素４５との距離ｘ２よりも短く設定す
る。

【００６８】このように、方形上に生成された配置状態
から、実際のレイアウトを反映させた長さ及び距離の情
報を得ることができる。

【００６９】図６は請求項３及び９に記載のトランジス
タ概略配置方法の配置評価関数を説明する図である。本
配置評価関数は、図５において説明した方形行列上の長
さを用いることにより、配置要素間の配線長を数値化し
て、全ての配線の和を求める関数として定義する。配置
要素間の配線は、配置要素の接続端子間の配線であっ
て、その配線長は、ネットごとに各ネットに属する全て
の端子を包含する最小方形の周囲長の半分として評価す
る。ちなみに、ネットとは、同一の電位によって接続さ
れるべき素子の集合をいう。従って、本配置評価関数
は、配線長を、ネットごとの配線長の和として計算する
ことができる。

【００７０】図６において、トランジスタＡからなる配
置要素５０とトランジスタＡの端子５１、トランジスタ
Ｂからなる配置要素５２とトランジスタＢの端子５３、
トランジスタＣからなる配置要素５４とトランジスタＣ
の端子５５、トランジスタＤからなる配置要素５６とト
ランジスタＤの端子５７が方形行列上に配置されている
とする。図６に示すように、１つのネットについてすべ
ての端子５１、５３、５５及び５７を包含する最小方形
５８が求められると、最小方形５８の各辺が通過する方
形及び最小方形５８が内部に含む方形をすべて合わせる
と１つの小方形行列５９が特定できる。

【００７１】このネットの配線長を評価する場合は、小
方形行列５９において縦に最も長くなる列と横に最も長
くなる行とを選択した後、最小方形５８の範囲内にある
行方向の長さ６０及び列方向の長さ６１を計算して、両
者の和をとることによりネット配線長を得ることができ
る。

【００７２】このようにして得られる、方形行列上の配
線長を求める配置評価関数は、実際のレイアウトにおけ
る配線長を的確に反映するため、配置評価関数を用いて
配置の最適化を行なえば、信号の流れる方向及び拡散領
域の共有化が考慮されて、無駄な配線の少ないレイアウ
トを得ることができる。

【００７３】次に、セル・レイアウトに対して信号の流
れる向きをあらかじめ指定しておいて、この信号の流れ
に沿ってレイアウトを最適化したいという場合に有効な
請求項４に記載の配置評価関数を説明する。また、一部
のネットについて、セル・レイアウトに対してネットご
とに信号の流れる向きを指定しておいて、信号の流れに
沿ったレイアウトを行なって最適化したいという場合に
も容易に適応することができる。

【００７４】図７は請求項４及び１０に記載のトランジ
スタ概略配置方法の配置評価関数を定義するための方形
行列上の長さ及び距離を示す図である。図２において方
形行列を定義した際に用いたスタンダード・セルを例に
とると、トランジスタを縦置きにして各チャネル内に１
列に配置するというトランジスタの配置形態を基本にし
て、セル内の信号の流れを左方向から右方向、又は右方
向から左方向へのいずれかの一方向に定めてセルをレイ
アウトすることによって、容易にレイアウトの最適化を
得られる場合が多い。これは、セル内の信号の流れに沿
ってトランジスタを配置することにより、無駄な配線を
最小限に抑えることができるからであり、ここに説明す
る本配置評価関数は、このような場合に最適解を容易に
見つけることができるという特徴を有している。

【００７５】本配置評価関数は、図６を用いて説明した
請求項３に記載の配置評価関数を基本にしながら、前記
配置評価関数に対して次のような操作を付加する。すな
わち、セル内の信号の流れが指定された向きに対して、
その指定された向きに反する向きを持つネットの配線長
を、方形行列上の実際の長さによる数値よりも大きな値
に設定することにより、例えば２倍の値に設定すること
により評価するという操作を付加する。１つのネット内
の信号の流れの向きを特定するには、セルの入力端子か
らトランジスタのゲートに向かう方向、トランジスタの
ドレインからトランジスタのゲートに向かう方向、トラ
ンジスタのドレインからトランジスタのソースに向かう
方向、又はトランジスタのドレインからセルの出力端子
に向かう方向という信号の流れに関する各端子間の基本
的な関係に基づけばよい。

【００７６】図７（ａ）はトランジスタＡ及びトランジ
スタＢの互いに接続されたドレイン端子同士と、トラン
ジスタＣ及びトランジスタＤの互いに接続されたゲート
端子同士とが接続されたネットを示している。このネッ
ト内の信号の流れ７０はドレイン端子側からゲート端子
側に向かう。

【００７７】図７（ｂ）は図７（ａ）において説明した
各トランジスタを方形行列上に配置した図である。トラ
ンジスタＡからなる配置要素７１のドレイン端子７２及
びトランジスタＢからなる配置要素７３のドレイン端子
７４のドレインの重心位置７５と、トランジスタＣから
なる配置要素７６のゲート端子７７及びトランジスタＤ
からなる配置要素７８のゲート端子７９のゲートの重心
位置８０とを比較して、ドレイン重心位置７５からゲー
ト重心位置８０に向かうベクトルの右向きの成分をもっ
て、このネットのレイアウト上の信号の流れの向きと定
義する。

【００７８】本配置評価関数は、例えば、図７に示すよ
うにセル・レイアウトに対する信号の流れ８１の向きを
左向きと指定したとすると、ネット内の信号の流れ７０
の向きが左向きの場合は、方形行列上のネット配線長の
値をそのままネット配線長の評価値に用いるが、図７
（ｂ）に示すようにネット内の信号の流れ７０の向きが
右向きであるならば、方形行列上のネット配線長の値よ
りも大きな値（例えば２倍の値）をネット配線長の評価
値として採用する。従って、ネット内の信号の流れ７０
の向きが左向きに変わるまで、配置改善が繰り返される
可能性を非常に高くすることができる。

【００７９】このように、請求項３又は請求項４に記載
の配置評価関数を用いた本実施形態のトランジスタ概略
配置方法によると、無駄な配線を最小限に抑えてトラン
ジスタを最適配置することができる。

【００８０】以下、第１の実施形態に係る請求項５に記
載のトランジスタ概略配置方法の配置改善方法を図面を
参照しながら説明する。ただし、本配置改善方法は、シ
ミュレーテッド・アニーリング法等のスケジューリング
・アルゴリズムとしての繰り返し改善アルゴリズムでは
なく、図１に示す繰り返される単位としての配置改善方
法を意味する。本配置改善方法は、方形行列上の配置要
素の配置状態を変更するために、１つの配置要素を選択
してこの配置要素に対して４つの変更形式の中からいず
れか１つの変更形式を選択された配置要素に適応する。

【００８１】これら４つの変更形式とは、配置要素の回
転、配置要素と他の配置要素との交換、配置要素の空方
形への移動及び配置要素の方形間の境界への移動であ
り、以下順に４つの変更形式について説明する。

【００８２】１つ目の配置要素の回転は、図８に示すよ
うにトランジスタＡからなる配置要素９０Ａに対しての
み適応され、「上、下、左、右」の４つの向きの中か
ら、トランジスタＡの現状と異なる向きを選択して適応
する。図８（ａ）の初期姿勢に示すように配置要素９０
Ａの方形行列上に占める位置は動かさずに、配置要素９
０Ａを１８０度回転させて、図８（ｄ）に示すように配
置要素９０Ｄとすることによりトランジスタ間の拡散領
域の共有化を改善できることが期待される。また、図８
（ｂ）に示す９０度の回転、又は図８（ｃ）に示す２７
０度の回転により、トランジスタの縦置きと横置きとの
変更を実現できる。

【００８３】２つ目の配置要素と他の配置要素の交換
は、図９（ａ）の初期配置に示すように方形行列上でト
ランジスタＡからなる配置要素９０及びトランジスタＢ
からなる配置要素９１の２つの配置要素について、図９
（ｂ）に示すように割り当てられている方形を互いに交
換する形式であって、スタンダード・セルによるブロッ
ク・レイアウトの合成の際等に、配置改善の単位として
最も一般に使われる形式である。

【００８４】３つ目の配置要素の空方形への移動は、方
形行列の次元を配置要素の数よりも多く取っておくこと
により可能となる変更形式である。方形行列の次元の設
定の方法については図２を用いて説明したが、例えば、
スタンダード・セルを用いる典型的なデザイン・スタイ
ルを考える場合は、セル内に方形行列を定義することに
より、トランジスタ配置の多様な形態に十分に対応でき
る。図１０に示すように、トランジスタＡからなる配置
要素９０が移動対象に選択された場合を想定すると、１
回の配置改善においては、移動先の候補となる空方形
は、方形９６、９７及び９８を除く方形９２、９３、９
４及び９５のように、いずれかの配置要素が割り当てら
れている方形に隣接する方形、又は、いずれかの配置要
素によって影響を及ぼされている方形に隣接する方形で
なければならないとする。この制限は、配置結果の解空
間を狭めるものではなく、単に、配置改善時の選択範囲
を無意味に大きくして収束に要する時間を増大させない
ためにとる措置である。レイアウト領域のサイズが決め
られている場合は、そのサイズによって移動先の空方形
の候補をさらに絞ればよい。

【００８５】４つ目の配置要素の方形間の境界への移動
は、図１１に示すように、本配置改善方法に独自な方法
であって、方形行列上に互いに隣接する２つの方形の間
に配置要素を移動させることを許す形式である。図１１
に示すように、１つの行にトランジスタＡからなる配置
要素１０１、トランジスタＢからなる配置要素１０２、
トランジスタＣからなる配置要素１０３、トランジスタ
Ｄからなる配置要素１０４及びトランジスタＥからなる
配置要素１０５が割り当てられているとする。配置要素
１０１が選択されて、配置要素１０４が割り当てられて
いる方形１０９と配置要素１０５が割り当てられている
方形１１０との境界である一辺１１１の上に移動させる
とすると、配置要素１０５はこれ以上右側に移動するこ
とができず、配置要素１０４は、一連の配置要素の先頭
となる配置要素１０２が配置要素１０１が割り当てられ
ていた方形１０６に移動することができ、それに連れて
配置要素１０３も配置要素１０２が割り当てられていた
方形１０７に移動することができると共に配置要素１０
４も配置要素１０３が割り当てられていた方形１０８に
移動することができるため、配置要素１０１は配置要素
１０４が割り当てられていた方形１０９に割り当てられ
ることができる。

【００８６】このように、移動の直後に全ての配置要素
がいずれかの方形に重複なく割り当てられるように、一
部関係する配置要素を１方形ずつ移動させることとす
る。すなわち、本移動は配置要素の並びに対して他の配
置要素を割り込ませるのであるから、割り込まれた側の
前記配置要素の並びを形成していた配置要素を１方形ず
つずらす必要が生じる。本移動は、配置要素の交換とい
う形式によると何回も繰り返さなければならない変更
を、１回の変更により達成することができる非常に有効
な変更形式である。

【００８７】本実施形態によるトランジスタ概略配置方
法において、本配置改善方法を用いる場合に、これら４
つの変更形式の使い方を様々に工夫することができる。

【００８８】まず、基本的には４つの変更形式を全く任
意に選択する方法が考えられる。

【００８９】次に、配置要素の回転という１つ目の変更
形式が他の３つの変更形式に比べて変更内容が小規模で
あると考えられるので、トランジスタ概略配置方法の繰
り返し改善アルゴリズムとしてシミュレーテッド・アニ
ーリング法がとられた場合に、スケジューリング・パラ
メータである温度が高温のステージにおいては、他の３
つの変更形式を主な改善方法として用い、低温のステー
ジにおいては、配置要素の回転を主な改善方法として用
いるというようなスケジューリングのステージに合わせ
た変更形式の使い分けも可能である。

【００９０】また、１つ目の変更形式である配置要素の
回転の中でも、配置要素を９０度又は２７０度回転させ
る変更は縦置きと横置きとの間の変換に相当するため、
配置形態を大きく変更することになるとみなし、同様に
シミュレーテッド・アニーリング法による繰り返し改善
のスケジューリングが用いられた場合に、高温のステー
ジにおいては、配置要素を回転させる時の回転角を９０
度又は２７０度とし、低温のステージにおいては、回転
角を専ら１８０度とするという方法も考えられる。

【００９１】さらに、回転角１８０度による変更形式の
みによって繰り返し配置改善を行なうことは、トランジ
スタの位置を動かさずにソースとドレインとを入れ替え
ることによる拡散の共有化の最大化を図ることに直結す
るため、繰り返し改善を一つのまとまりとして、全体の
繰り返し改善処理の中に適宜組み込むという方法も有効
である。

【００９２】このように、本配置改善方法は、これらの
４つの配置変更形式を備えることにより、本実施形態の
トランジスタ概略配置方法に、多様なトランジスタの配
置形態に柔軟に対応できる能力を与えることとなり、非
常に大きな役割を担うものである。

【００９３】以上説明したように、本実施形態のトラン
ジスタ概略配置方法は、方形行列を用いた２次元的で、
且つ、柔軟な配置表現、信号の流れやトランジスタ間の
拡散領域の共有等を反映させた精密な配置評価関数及び
多様な配置形態を実現できる効果的な配置改善方法を備
えているため、セル・レイアウト合成においてトランジ
スタの概略配置を最適化する、非常に高度な効果を有す
るものである。

【００９４】以下、本発明の第２の実施形態を図面に基
づいて説明する。

【００９５】（第２の実施形態）図１２は本発明の第２
の実施形態に係るトランジスタ概略配置方法を示すフロ
ーチャートである。

【００９６】まず、ステップＳＴ１１は、計算機の記憶
装置等からネットリストを読み込んで、配置対象となる
トランジスタ及びセルの入出力端子についての接続要求
並びに各トランジスタのトランジスタ・サイズに関する
情報を内部に記憶する工程である。

【００９７】次に、ステップＳＴ１２は、Ｐチャネル及
びＮチャネルの各チャネルについて、チャネルごとのト
ランジスタ・サイズの和を求める工程である。

【００９８】次に、ステップＳＴ１３は、各チャネルの
トランジスタ・サイズの和に基づいて、各チャネル内に
形成する基板コンタクトの必要数を求める工程である。
トランジスタ・サイズの和を用いてレイアウト面積を見
積もって、基板コンタクトの必要数を決めるのが、容易
かつ妥当であるとの考えに基づいている。本実施形態に
おいて、１つの基板コンタクトはコンタクト・ホールが
１つのみの最小サイズであるとし、必要数分のコンタク
トを後の工程において各チャネルにそれぞれ配置する。

【００９９】次に、ステップＳＴ１４は、配置すべき基
板コンタクトを配置要素に含めて、トランジスタ及びセ
ルの入出力端子による配置要素と共にトランジスタ概略
配置を行なう工程である。

【０１００】次に、ステップＳＴ１５は、基板コンタク
トを最寄りのトランジスタに付加して、基板コンタクト
付トランジスタを生成する工程である。

【０１０１】次に、ステップＳＴ１６で、トランジスタ
及び基板コンタクト付トランジスタの間を配線しする工
程であり、ステップＳＴ１７は、コンパクションを行な
ってレイアウトを完了させる工程である。

【０１０２】このように、本実施形態によるセル・レイ
アウト合成方法は、基板コンタクトの配置まで含めてレ
イアウトの最適化を可能にする。

【０１０３】以下、ステップＳＴ１４のトランジスタ概
略配置について説明する。第２の実施形態によるトラン
ジスタ概略配置方法は、配置要素として基板コンタクト
が追加されたいう点を除けば、用いる配置表現モデルと
処理の流れとのいずれにおいても、図１を用いて説明し
た第一の実施形態によるトランジスタ概略配置方法と全
く一致する。基板コンタクトからなる配置要素が追加さ
れたことによる違いは、初期配置の工程及び配置改善の
工程において制約を設けることと配置評価関数を修正す
ることとの２点である。

【０１０４】初期配置及び配置改善の各工程における制
約は、基板コンタクトがＰチャネルにおいては電源と同
電位になり、Ｎチャネルにおいてはグランドと同電位に
ならなければならないことと、トランジスタの近傍に形
成されなければならないこととに基づいている。図１３
は方形行列上の基板コンタクトからなる配置要素の割り
当て方法を示す図である。図１３において、Ｐチャネル
領域に配置されているトランジスタＴｒからなる配置要
素１２０はソースが電源配線に接続されておりドレイン
が下向きの配置要素であるため、基板コンタクトからな
る配置要素は電源と同電位にならなくてはならないの
で、配置要素１２０のソース側に配置されることとな
り、従って図１３に示す各方形１２１〜１２４のいずれ
か１つの方形に割り当てられることとなる。

【０１０５】このように、基板コンタクトからなる配置
要素は、Ｐチャネルにおいてはソース側が電源に接続さ
れるトランジスタからなる配置要素を選び、また、Ｎチ
ャネルにおいてはソース側がグランドに接続されるトラ
ンジスタからなる配置要素を選んで該配置要素に隣接さ
れる配置とし、しかもトランジスタのゲート長方向に隣
接する場合は、該トランジスタからなる配置要素のソー
ス側に隣接しなければならないとする。

【０１０６】次に、配置評価関数に加える修正は、でき
る限りチャネル境界線の近くに基板コンタクトを配置し
たいという要求に答えるものである。図１４は方形行列
上の基板コンタクトからなる配置要素とチャネル境界線
との距離を示す図である。図１４において、トランジス
タＴｒからなる配置要素１２０と配置要素１２０に隣接
して配置された基板コンタクトからなる配置要素１２５
がＰチャネル領域に配置されているとする。基板コンタ
クトからなる配置要素１２５とチャネル境界線１２６と
の距離は配置要素１２５からチャネル境界線１２６に下
ろした垂線の長さとする。このように、第１の実施形態
において説明した配線長の総和に基づく配置評価関数を
基礎にして、該配置評価関数に対して、基板コンタクト
からなる配置要素とチャネル境界線との距離の評価値を
加えるものである。すなわち、本実施形態におけるトラ
ンジスタ概略配置方法の配置評価関数は、全ての基板コ
ンタクトからなる配置要素を除く他の配置要素における
配線の長さの総和と、全ての基板コンタクトからなる配
置要素のチャネル境界線からの距離の総和とを合わせた
ものである。

【０１０７】本実施形態のトランジスタ概略配置方法に
よると、基板コンタクトを含むトランジスタのレイアウ
ト問題に対して最適化を図ることができる。

【０１０８】なお、ステップＳＴ１５以降の、基板コン
タクトを最寄りのトランジスタに一体化させたトランジ
スタのトランジスタ間の配線及びコンパクションを行な
う方法は、「福井、雑賀、”トランジスタのレイアウト
モデルに柔軟性を持たせたコンパクション手法”、信学
技報VLD95-50, pp.29-36,Jul.,1995」に開示されてい
る。

【０１０９】本実施形態のセル・レイアウト合成方法に
よると、従来難しいとされてきた基板コンタクトを含む
トランジスタのレイアウト問題に対して十分に対応する
ことができる。

【０１１０】

【発明の効果】以上説明したように、請求項１の発明に
係るトランジスタ概略配置方法によると、セルは方形行
列からなる２次元配置モデルとされ、配置評価関数は方
形行列上の配置結果が最適化されているか否かを評価す
ると共に、配置改善方法により配置評価関数の出力結果
が最適化されるまで配置変更が繰り返されるため、多様
なトランジスタのレイアウト形態を自動合成できるの
で、人手に頼らずに実用的かつ最適なレイアウトを得る
ことができる。

【０１１１】請求項２の発明に係るトランジスタ概略配
置方法によると、トランジスタの２次元的かつ多様な配
置形態に柔軟に対応できるため、確実に実用的かつ最適
なレイアウトを得ることができる。

【０１１２】請求項３の発明に係るトランジスタ概略配
置方法によると、各配置要素が割り当てられた方形の上
下左右の各方向の長さと、互いに隣接する方形間の距離
とが隣接関係に基づいて求められて、配置要素間の全て
の配線についての総和が計算されるため、実際のレイア
ウトにおける配線長が適確に反映されるので、無駄な配
線が少ないレイアウトが実現できる。

【０１１３】請求項４の発明に係るトランジスタ概略配
置方法によると、配置評価関数が、ネット内の信号方向
がセル内の信号方向と一致していない場合は、配置要素
間の配線の長さを一定の割合で延長して評価するため、
ネット内の信号方向がセル内の信号方向と一致するまで
配置改善を繰り返す可能性が高くなるので、無駄な配線
が一層少ないレイアウトが実現できる。

【０１１４】請求項５の発明に係るトランジスタ概略配
置方法によると、配置改善を、配置要素の向きを回転さ
せる回転と、配置要素と他の配置要素との交換と、配置
要素を空方形に移動させる移動と、方形間の境界線上へ
の移動との４つの形式を用いて行なうため、多様なトラ
ンジスタの配置形態に柔軟に対応できるので、人手設計
並みの実用的かつ最適なレイアウトを確実に得ることが
できる。

【０１１５】請求項６の発明に係るトランジスタ概略配
置方法によると、請求項１の発明に係るトランジスタ概
略配置方法の効果が得られる上に、基板コンタクトを含
めたトランジスタのレイアウト形態を自動合成できる。

【０１１６】請求項７の発明に係るトランジスタ概略配
置方法によると、トランジスタの２次元的かつ多様な配
置形態に柔軟に対応できるため、確実に実用的かつ最適
なレイアウトを得ることができる。

【０１１７】請求項８の発明に係るトランジスタ概略配
置方法によると、基板コンタクトからなる配置要素を、
Ｐチャネル領域においてはソースが電源配線に接続され
るトランジスタからなる配置要素に隣接して配置すると
共に、Ｎチャネル領域においてはソースがグランド配線
に接続されるトランジスタからなる配置要素に隣接して
配置し、且つ、トランジスタのゲート長方向に隣接する
場合は該トランジスタのソース側に隣接するように配置
するため、確実に基板コンタクトに対応できるので、基
板コンタクトを含めたトランジスタのレイアウト形態を
自動合成できる。 請求項９の発明に係るトランジスタ
概略配置方法によると、基板コンタクトからなる配置要
素を除く各配置要素が割り当てられた方形の上下左右の
各方向の長さと、互いに隣接する方形間の第１の距離及
び基板コンタクトからなる配置要素とチャネル境界線と
の第２の距離とを求めて、配置要素間の全ての配線につ
いての総和を計算するため、基板コンタクトを含めた実
際のレイアウトにおける配線長が適確に反映されるの
で、無駄な配線が少ないレイアウトが実現できる。

【０１１８】請求項１０の発明に係るトランジスタ概略
配置方法によると、配置評価関数が、ネット内の信号方
向がセル内の信号方向と一致していない場合は、配置要
素間の配線の長さを一定の割合で延長して評価するた
め、ネット内の信号方向がセル内の信号方向と一致する
まで配置改善を繰り返す可能性が高くなるので、無駄な
配線が一層少ないレイアウトが実現できる。

【０１１９】請求項１１の発明に係るトランジスタ概略
配置方法によると、配置改善を、配置要素の向きを回転
させる回転と、配置要素と他の配置要素との交換と、配
置要素を空方形に移動させる移動と、方形間の境界線上
への移動との４つの形式を用いて行なうと共に、基板コ
ンタクトからなる配置要素を、Ｐチャネル領域において
はソースが電源配線に接続されるトランジスタからなる
配置要素に隣接して配置し、また、Ｎチャネル領域にお
いてはソースがグランド配線に接続されるトランジスタ
からなる配置要素に隣接して配置し、且つ、前記トラン
ジスタのゲート長方向に隣接する場合は該トランジスタ
のソース側に隣接するように配置するため、基板コンタ
クトを含めた多様なトランジスタの配置形態に柔軟に対
応できるので、人手設計並みの実用的かつ最適なレイア
ウトを確実に得ることができる。

【図面の簡単な説明】

【図１】本発明の第１の実施形態に係るトランジスタ概
略配置方法を示すフローチャート図である。

【図２】本発明の第１の実施形態に係る記載のトランジ
スタ概略配置方法の方形行列を示す図である。

【図３】本発明の第１の実施形態に係るトランジスタ概
略配置方法のトランジスタの向きを示す図である。

【図４】本発明の第１の実施形態に係るトランジスタ概
略配置方法のトランジスタからなる配置要素の大きさを
示す図であって、（ａ）は配置されるトランジスタの上
面図であり、（ｂ）は（ａ）に示すトランジスタを方形
行列上に配置した図である。

【図５】本発明の第１の実施形態に係るトランジスタ概
略配置方法のトランジスタからなる配置要素の占有フラ
グを示す図であって、（ａ）は配置されるトランジスタ
の上面図であり、（ｂ）は（ａ）に示すトランジスタを
方形行列上に配置した図である。

【図６】本発明の第１の実施形態に係るトランジスタ概
略配置方法の配置評価関数を説明する図である。

【図７】本発明の第１の実施形態に係るトランジスタ概
略配置方法の配置評価関数を定義するための方形行列上
の長さ及び距離を示す図であって、（ａ）は配置される
トランジスタの配線及び配線上の信号の流れの向きを示
す上面図であり、（ｂ）は（ａ）に示すトランジスタを
方形行列上に配置した図である。

【図８】本発明の第１の実施形態に係るトランジスタ概
略配置方法における配置改善方式の１つである回転を示
す図であって、（ａ）は初期姿勢を示す図であり、
（ｂ）は９０度回転を示す図であり、（ｃ）は２７０度
回転を示す図であり、（ｄ）は１８０度回転を示す図で
ある。

【図９】本発明の第１の実施形態に係るトランジスタ概
略配置方法における配置改善方式の１つである交換を示
す図であって、（ａ）は初期配置を示す図であり、
（ｂ）は配置交換後を示す図である。

【図１０】本発明の第１の実施形態に係るトランジスタ
概略配置方法における配置改善方式の１つである移動を
示す図である。

【図１１】本発明の第１の実施形態に係るトランジスタ
概略配置方法における配置改善方式の１つである境界上
への移動を示す図であって、（ａ）は初期配置を示す図
であり、（ｂ）はトランジスタＡが方形間境界へ移動し
た移動後の図である。

【図１２】本発明の第２の実施形態に係るトランジスタ
概略配置方法を示すフローチャート図である。

【図１３】本発明の第２の実施形態に係るトランジスタ
概略配置方法の方形行列上の基板コンタクトからなる配
置要素の割り当て方法を示す図である。

【図１４】本発明の第２の実施形態に係るトランジスタ
概略配置方法の方形行列上の基板コンタクトからなる配
置要素とチャネル境界線との距離を示す図である。

【図１５】従来の代表的なセル・レイアウト合成方法を
示すフローチャート図であって、（ａ）はコンパクショ
ン技術を用いないセル・レイアウト合成方法を示すフロ
ーチャート図であり、（ｂ）はコンパクション技術を用
いたセル・レイアウト合成方法を示すフローチャート図
である。

【符号の説明】

１０ セル １１ Ｐチャネル １２ Ｎチャネル １３ チャネル境界線 １４ 電源配線 １５ グランド線 １６ 方形 １７ 方形行列 １８ 方形間の境界線 ２０ トランジスタ ２０ｄ ドレイン ２０ｇ ゲート ２０ｓ ソース ２１ｄ ドレイン ２１ｇ ゲート ２１ｓ ソース ２２ｄ ドレイン ２２ｇ ゲート ２２ｓ ソース ２３ｄ ドレイン ２３ｇ ゲート ２３ｓ ソース Ａ トランジスタ Ｂ トランジスタ Ｃ トランジスタ Ｄ トランジスタ Ｅ トランジスタ ３０ 方形 ３１ 方形 ３２ 方形 ３３ 第１の占有フラグ ３４ 第２の占有フラグ ４０ 配置要素 ４１ 占有フラグ ４２ 配置要素 ４３ 占有フラグ ４４ 占有フラグ ４５ 配置要素 ４６ 配置要素 ４７ 配置要素 ４８ 占有フラグ ５０ 配置要素 ５１ 端子 ５２ 配置要素 ５３ 端子 ５４ 配置要素 ５５ 端子 ５６ 配置要素 ５７ 端子 ５８ 最小方形 ５９ 小方形行列 ６０ 行方向の長さ ６１ 列方向の長さ ７０ ネット内の信号の流れ ７１ 配置要素 ７２ ドレイン端子 ７３ 配置要素 ７４ ドレイン端子 ７５ ドレインの重心位置 ７６ 配置要素 ７７ ゲート端子 ７８ 配置要素 ７９ ゲート端子 ８０ ゲートの重心位置 ８１ セル内の信号の流れ ９０Ａ 配置要素 ９０Ｂ 配置要素 ９０Ｃ 配置要素 ９０Ｄ 配置要素 ９０ 配置要素 ９１ 配置要素 ９２ 方形 ９３ 方形 ９４ 方形 ９５ 方形 ９６ 方形 ９７ 方形 ９８ 方形 １０１ 配置要素 １０２ 配置要素 １０３ 配置要素 １０４ 配置要素 １０５ 配置要素 １０６ 方形 １０７ 方形 １０８ 方形 １０９ 方形 １１０ 方形 １１１ 方形の境界上の一辺 Ｔｒ トランジスタ １２０ 配置要素 １２１ 方形 １２２ 方形 １２３ 方形 １２４ 方形 １２５ 配置要素 １２６ チャネル境界線

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平４−137661（ＪＰ，Ａ) 特開 平６−332984（ＪＰ，Ａ) 特開 平９−64189（ＪＰ，Ａ) 福井、雑賀、秋濃，“トランジスタの レイアウトモデルに柔軟性を持たせたコ ンパクション手法”，電子情報通信学会 技術研究報告，1995年，ＶＬＤ95，Ｎ Ｏ．171，Ｐ．29−Ｐ．36 福井、秋濃，“ＶＬＳＩのリーフセル 合成に関する一手法”，1994年，ＶＬＤ 94，ＮＯ．315，Ｐ．13−17 Ｆｕｋｕｉ，Ｓｈｉｎｏｍｉｙａ，Ａ ｋｉｎｏ“Ａ Ｎｅｗ Ｌａｙｏｕｔ Ｓｙｎｔｈｅｓｉｓ ｆｏｒ Ｌｅａｆ Ｃｅｌｌ Ｄｅｓｉｇｎ”ＩＥＥＥ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ，29．Ａｕｇ. 1995，ｐ．259−264 (58)調査した分野(Int.Cl.⁷，ＤＢ名) H01L 21/82 G06F 17/50 ＪＩＣＳＴファイル（ＪＯＩＳ)

Claims (11)

(57)【特許請求の範囲】
1. 【請求項１】 半導体製造技術から導かれるマスク設計
   ルール並びに、セルの入出力端子及びトランジスタの電
   極の各接続要求情報と前記トランジスタのサイズ情報と
   からなるネットリストを用いて、計算機により前記セル
   をレイアウトするセル・レイアウト合成方法のうちの前
   記トランジスタのおおよその配置を決定するトランジス
   タ概略配置方法であって、 前記セルを、該セルにおけるＰチャネル領域とＮチャネ
   ル領域との境界線に対して平行な直線と前記境界線に対
   して垂直な直線とにより方形に区切って、前記方形を要
   素とする方形行列を生成する第１の工程と、 前記ネットリストに登録されている前記セルの入出力端
   子及びトランジスタを配置要素として、各配置要素を前
   記方形行列の１つの方形に互いに重複することなく割り
   当てて初期配置する第２の工程と、 前記方形行列上の配置結果が最適化されているか否かを
   評価するための配置評価関数を定義して、該配置評価関
   数の出力結果を評価する第３の工程と、 前記出力結果に基づいて、前記配置結果が最適化されて
   いるか否かを判定した後、前記配置結果が最適化されて
   いない場合は、前記方形行列上における各配置要素の配
   置を変更して配置改善を行なう第４の工程とを備えてお
   り、 前記第３及び第４の工程を、前記配置評価関数の出力結
   果が最適化されるまで繰り返すことを特徴とするトラン
   ジスタ概略配置方法。
2. 【請求項２】 前記第１の工程は、 前記方形行列の方向を、該方形行列の行番号が増す方向
   を下向き、前記行番号が減る方向を上向き、前記方形行
   列の列番号が増す方向を右向き及び前記列番号が減る方
   向を左向きとして定義すると共に、前記方形行列の行数
   を、前記トランジスタのゲート幅方向が前記左向き又は
   右向きとなる横置きトランジスタを前記方形行列の列方
   向に並べられる最大個数から求め、且つ、前記方形行列
   の列数を、前記ネットリストに登録されている前記トラ
   ンジスタの個数から求めることにより生成する工程と、 前記トランジスタからなる配置要素が前記方形行列に配
   置される方向を、ゲートに対して上側にドレインが位置
   し且つ前記ゲートに対して下側にソースが位置する方向
   を上向きと、前記トランジスタのゲートに対して上側に
   ソースが位置し且つ前記ゲートに対して下側にドレイン
   が位置する方向を下向きと、前記トランジスタのゲート
   に対して右側にドレインが位置し且つ前記ゲートに対し
   て左側にソースが位置する方向を右向きと、前記トラン
   ジスタのゲートに対して右側にソースが位置し且つ前記
   ゲートに対して左側にドレインが位置する方向を左向き
   と定義する工程とを含むことを特徴とする請求項１に記
   載のトランジスタ概略配置方法。
3. 【請求項３】 前記第３の工程における前記配置評価関
   数は、前記配置要素が前記方形行列上の１つの方形にの
   み割り当てられ、前記配置要素に対応するトランジスタ
   の前記ネットリスト内のゲート幅を表わしているトラン
   ジスタのサイズに応じて、割り当てられた前記１つの方
   形からゲート方向に延びる一連の方形に隣接する他の方
   形に対して割り当ての影響力が及ぶ割り当て状態を表現
   して、 前記割り当て状態に基づいて、互いに隣接する配置要素
   同士がトランジスタの拡散領域を共有できる場合には共
   有させることにより、前記配置要素間の上下方向及び左
   右方向の隣接関係を求めて、 前記隣接関係に基づいて、各配置要素がそれぞれ割り当
   てられた方形の上下方向及び左右方向の長さと、互いに
   隣接する前記方形間の距離とを求めて、前記配置要素間
   の全ての配線についての総和を前記長さ及び距離を用い
   て計算することを特徴とする請求項２に記載のトランジ
   スタ概略配置方法。
4. 【請求項４】 前記配置評価関数は、前記セル内を流れ
   る信号の方向をあらかじめ指定すると共に、同一の電位
   に接続されるべき前記セル内の配置要素の集合であるネ
   ットに対して前記配置要素の配置状態から前記ネット内
   を流れる信号の方向を求めて、 前記ネット内を流れる信号方向が前記セル内を流れる信
   号方向と一致していない場合は、一致する場合よりも前
   記配置要素間の配線の長さを一定の割合で延長して評価
   することを特徴とする請求項３に記載のトランジスタ概
   略配置方法。
5. 【請求項５】 前記第４の工程における前記配置改善
   は、選択された配置要素を９０度を単位に回転させる回
   転と、選択された配置要素と該配置要素とは異なる他の
   配置要素との交換と、選択された配置要素を配置要素が
   割り当てられていない空方形に移動させる移動と、選択
   された配置要素を方形間の境界線上に移動させる境界線
   上への移動との４つの形式を用いて行なわれ、 前記方形間の境界線上への移動は、選択された配置要素
   を前記境界線に隣接する方形のいずれか１つの方形に割
   り当てた後、前記方形を含めて隣接する一連の方形に対
   して前記方形上に配置されていた配置要素を、割り当て
   られた配置要素が重複しなくなるまで１方形ずつ順にず
   らすことにより、前記方形行列上の各配置要素をいずれ
   か１つの方形に割り当てる形式とすることを特徴とする
   請求項１〜４のいずれか１項に記載のトランジスタ概略
   配置方法。
6. 【請求項６】 半導体製造技術から導かれるマスク設計
   ルール並びに、セルの入出力端子及びトランジスタの電
   極の各接続要求情報と前記トランジスタのサイズ情報と
   からなるネットリストを用いて、計算機により前記セル
   をレイアウトするセル・レイアウト合成方法のうちの前
   記トランジスタのおおよその配置を決定するトランジス
   タ概略配置方法であって、 前記セルを、該セルにおけるＰチャネル領域とＮチャネ
   ル領域との境界線に対して平行な第１の直線と前記境界
   線に対して垂直な第２の直線とにより方形に区切って、
   前記方形を要素とする方形行列を生成する第１の工程
   と、 前記ネットリストに登録されている前記セルの入出力端
   子及びトランジスタ並びに該トランジスタの各サイズの
   総和に対して所定の割合により個数が求められる基板コ
   ンタクトを配置要素として、各配置要素を前記方形行列
   の１つの方形に互いに重複することなく割り当てて初期
   配置する第２の工程と、 前記方形行列上の配置結果が最適化されているか否かを
   評価するための配置評価関数を定義して、該配置評価関
   数の出力結果を評価する第３の工程と、 前記出力結果に基づいて、前記配置結果が最適化されて
   いるか否かを判定した後、前記配置結果が最適化されて
   いない場合は、前記方形行列上における各配置要素の配
   置を変更して配置改善を行なう第４の工程とを備えてお
   り、 前記第３及び第４の工程を、前記配置評価関数の出力結
   果が最適化されるまで繰り返すことを特徴とするトラン
   ジスタ概略配置方法。
7. 【請求項７】 前記第１の工程は、 前記方形行列の方向を、該方形行列の行番号が増す方向
   を下向き、前記行番号が減る方向を上向き、前記方形行
   列の列番号が増す方向を右向き及び前記列番号が減る方
   向を左向きとして定義すると共に、前記方形行列の行数
   を、前記トランジスタのゲート幅方向が前記左向き又は
   右向きとなる横置きトランジスタを前記方形行列の列方
   向に並べられる最大個数から求め、且つ、前記方形行列
   の列数を、前記ネットリストに登録されている前記トラ
   ンジスタの個数から求めることにより生成する工程と、 前記トランジスタからなる配置要素が前記方形行列に配
   置される方向を、ゲートに対して上側にドレインが位置
   し且つ前記ゲートに対して下側にソースが位置する方向
   を上向きと、前記トランジスタのゲートに対して上側に
   ソースが位置し且つ前記ゲートに対して下側にドレイン
   が位置する方向を下向きと、前記トランジスタのゲート
   に対して右側にドレインが位置し且つ前記ゲートに対し
   て左側にソースが位置する方向を右向きと、前記トラン
   ジスタのゲートに対して右側にソースが位置し且つ前記
   ゲートに対して左側にドレインが位置する方向を左向き
   と定義する工程とを含むことを特徴とする請求項６に記
   載のトランジスタ概略配置方法。
8. 【請求項８】 前記第２の工程は、前記基板コンタクト
   からなる前記配置要素を、前記Ｐチャネル領域において
   はソースが電源配線に接続されるトランジスタからなる
   前記配置要素に隣接して配置すると共に、前記Ｎチャネ
   ル領域においてはソースがグランド配線に接続されるト
   ランジスタからなる前記配置要素に隣接して配置し、且
   つ、前記トランジスタのゲート長方向に隣接する場合は
   該トランジスタのソース側に隣接するように配置する工
   程を含むことを特徴とする請求項６に記載のトランジス
   タ概略配置方法。
9. 【請求項９】 前記第３の工程における前記配置評価関
   数は、前記配置要素が前記方形行列上の１つの方形にの
   み割り当てられ、前記配置要素に対応するトランジスタ
   の前記ネットリスト内のゲート幅を表わしているトラン
   ジスタのサイズに応じて、割り当てられた前記１つの方
   形からゲート方向に延びる一連の方形に隣接する他の方
   形に対して割り当ての影響力が及ぶ割り当て状態を表現
   して、 前記割り当て状態に基づいて、互いに隣接する配置要素
   同士がトランジスタの拡散領域を共有できる場合には共
   有させることにより、前記配置要素間の上下方向及び左
   右方向の隣接関係を求めて、 前記隣接関係に基づいて、前記基板コンタクトからなる
   配置要素を除く各配置要素がそれぞれ割り当てられた方
   形の上下方向及び左右方向の長さと、互いに隣接する前
   記方形間の第１の距離とを求めると共に、前記基板コン
   タクトからなる全ての配置要素と前記境界線との第２の
   距離を求めて、前記配置要素間の全ての配線についての
   総和を前記長さ、第１の距離及び第２の距離を用いて計
   算することを特徴とする請求項８に記載のトランジスタ
   概略配置方法。
10. 【請求項１０】 前記配置評価関数は、前記セル内を流
    れる信号の方向をあらかじめ指定すると共に、同一の電
    位に接続されるべき前記セル内の配置要素の集合である
    ネットに対して前記配置要素の配置状態から前記ネット
    内を流れる信号の方向を求めて、 前記ネット内を流れる信号方向が前記セル内を流れる信
    号方向と一致していない場合は、一致する場合よりも前
    記配置要素間の配線の長さを一定の割合で延長して評価
    することを特徴とする請求項９に記載のトランジスタ概
    略配置方法。
11. 【請求項１１】 前記第４の工程における前記配置改善
    は、選択された配置要素を９０度を単位に回転させる回
    転と、選択された配置要素と該配置要素とは異なる他の
    配置要素との交換と、選択された配置要素を配置要素が
    割り当てられていない空方形に移動させる移動と、選択
    された配置要素を方形間の境界線上に移動させる境界線
    上への移動との４つの形式を用いて行なわれ、 前記方形間の境界線上への移動は、選択された配置要素
    を前記境界線に隣接する方形のいずれか１つの方形に割
    り当てた後、前記方形を含めて隣接する一連の方形に対
    して前記方形上に配置されていた配置要素を、割り当て
    られた配置要素が重複しなくなるまで１方形ずつ順にず
    らすことにより、前記方形行列上の各配置要素をいずれ
    か１つの方形に割り当てる形式であって、 前記第４の工程は、前記基板コンタクトからなる前記配
    置要素を、前記Ｐチャネル領域においてはソースが前記
    電源配線に接続されるトランジスタからなる前記配置要
    素に隣接して配置すると共に、前記Ｎチャネル領域にお
    いてはソースが前記グランド配線に接続されるトランジ
    スタからなる前記配置要素に隣接して配置し、且つ、前
    記トランジスタのゲート長方向に隣接する場合は該トラ
    ンジスタのソース側に隣接するように配置する工程を含
    むことを特徴とする請求項６〜１０のいずれか１項に記
    載のトランジスタ概略配置方法。