JP4953526B2 - タイミング優先でセル配置するｌｓｉのレイアウト方法及びその装置 - Google Patents
タイミング優先でセル配置するｌｓｉのレイアウト方法及びその装置 Download PDFInfo
- Publication number
- JP4953526B2 JP4953526B2 JP2001228373A JP2001228373A JP4953526B2 JP 4953526 B2 JP4953526 B2 JP 4953526B2 JP 2001228373 A JP2001228373 A JP 2001228373A JP 2001228373 A JP2001228373 A JP 2001228373A JP 4953526 B2 JP4953526 B2 JP 4953526B2
- Authority
- JP
- Japan
- Prior art keywords
- cell
- wiring
- cells
- processing
- rearrangement
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は，集積回路（以下ＬＳＩ）のレイアウト方法及びその装置に関し，特に，タイミングを優先してセル配置を行いセル間配線を生成するＬＳＩのレイアウト方法及びそのレイアウト装置に関する。
【０００２】
【従来の技術】
ＬＳＩの設計は，一般にコンピュータを利用して行われる。特に，セミカスタムＬＳＩであるＡＳＩＣ（Application Specific Integrated Circuit)は，目的とする機能を発揮するＬＳＩの論理設計を行い，その論理設計データを基にＬＳＩのレイアウトを行う。論理設計では，あらかじめ登録されているセルライブラリから必要な基本セルを選択し，目的とする機能を実現するための論理回路が設計される。その結果，複数のセルとその入出力端子間の接続を有するネットリストと呼ばれる論理データが生成される。このネットリストに従って，チップ上のセルの配置とセル間の接続配線を生成するレイアウト工程が行われる。
【０００３】
レイアウト工程が終了すると，セルの駆動能力と接続配線の抵抗，容量，インダクタンスなどから信号伝播遅延時間が計算され，ネットリストと遅延時間とを参照して，論理シミュレーションが行われる。論理シミュレーションをパスすると，実際のレイアウトデータの生成，パターンデータの生成に移り，ＬＳＩの前工程に必要なデータが生成される。
【０００４】
近年のＬＳＩの高速化に伴い，信号やクロックのタイミングを考慮したセル配置処理や，信号やクロックのタイミングを最適化する最適化処理が実施されている。特にネットリストをもとにしたセルの自動配置処理では，複数のセルに対して，入力信号やクロックのタイミングがより厳しいセルの順に優先順位を決めて，その優先順位に従ってセルを自動配置することが行われる。
【０００５】
【発明が解決しようとする課題】
しかしながら，信号やクロックのタイミングを重視してセルを配置するあまり，チップ内に局所的なセルの密集領域が形成されることがある。即ち，入力信号端子やクロック入力端子に近い領域に，多くのセルが配置されることがある。その結果，自動セル配置工程の後の自動配線工程において，密集領域で配線が混雑して配線を生成することができなくなることがたびたび起こるようになった。自動配線工程で配線不能になると，タイミング条件や他の条件を変更したうえで，再度，自動セル配置処理と自動配線処理をやり直す必要がある。
【０００６】
近年のＡＳＩＣのゲート数は膨大な数に上り，高速コンピュータを利用しても，自動セル配置処理に数日間，自動配線処理にも数日間が必要になっており，上記の自動セル配置処理と自動配線処理のやり直しは，ＡＳＩＣの設計工程を長期化させ，コストアップにつながるばかりでなく，ＡＳＩＣの短納期という特徴を失わせることにつながる。
【０００７】
そこで，本発明の目的は，タイミングを優先したセル配置後の自動配線を，できるだけ可能にするレイアウト方法及びその装置を提供することにある。
【０００８】
【課題を解決するための手段】
上記の目的を達成するために，本発明の一つの側面によれば，複数のセルを有するＬＳＩのレイアウト方法において，セルとその接続データを有するネットリストとタイミング条件に基づいてセルの自動配置を行い，更に，前記タイミングの最適化処理を行って，チップ内に複数のセルを配置した後に，グローバル配線処理を実施し配線の混雑度を解析する。そして，配線の混雑度が高くて詳細配線処理が困難である判断された小領域内において，セルの再配置処理を実施する。そして，その再配置されたセルに対して詳細配線処理を行う。
【０００９】
上記の発明によれば，セルの再配置を混雑度が高い小領域内に限定して行うことで，タイミングが最適化された全体のセル配置を大幅に変更することなく，詳細配線処理で配線不能になる可能性を減らすことができる。その結果，従来のように，長時間のマシンタイムを要する自動セル配置処理と詳細配線処理が無駄に行われることが抑制または防止される。
【００１０】
上記の発明において，より好ましい実施例では，セルの再配置を行っても配線の混雑度が基準レベルより低くならない場合は，最初の小領域を拡大した新たな小領域内でセルの再配置処理を実施する。その結果，配線の混雑度が基準レベルより低ければ，詳細配線処理を行う。この方法によれば，小領域を拡大してセルの再配置処理を行うので，より高い柔軟性をもってセルの再配置処理を行うことができる。
【００１１】
上記の発明において，より好ましい実施例では，セルの再配置処理は，（１）セルの配置間隔を拡げる，（２）セル列の間隔を拡げる，（３）隣接するセルを上下，左右，斜め，回転方向に入れ替える，（４）セルの向きを変更，反転する，（５）論理特性が同一であって端子位置が異なるセルに置き換えるのいずれかを含む処理であることを特徴とする。かかるセルの再配置であれば，セルの相対的な位置関係が変動せずに，最適化されたタイミング状態を崩すことがなく，配線の混雑度を緩和することができる。
【００１２】
上記の発明において，より好ましい実施例では，配線の混雑度は，小領域内のセルの総面積，セルの接続ピン総数，接続配線総数，通過配線総数の少なくとも一つに応じて決定する。或いは，別の好ましい実施例では，配線の混雑度は，小領域内の接続配線総数をピン総数で除した値に応じて決定する。
【００１３】
【発明の実施の形態】
以下，図面を参照して本発明の実施の形態例を説明する。しかしながら，本発明の保護範囲は，以下の実施の形態例に限定されるものではなく，特許請求の範囲に記載された発明とその均等物にまで及ぶものである。
【００１４】
図１，２，３は，本発明にかかる実施の形態のレイアウト方法を概略的に説明する図であり，以下これらの図にしたがって，そのレイアウト方法を説明する。図１は，ある論理設計されたネットリストにタイミング条件を与えて，自動セル配置処理をした結果のセル配置例を示す。図１のＬＳＩは，一般的なスタンダードセルによるＡＳＩＣを示すものであり，チップ１内に複数のセルアレイ２とその間のチャネル領域３とが交互に配置されている。セルアレイ２内には，例えば縦方向のサイズは共通で，横方向のサイズがセルによって異なる複数のセルが，適宜配置される。
【００１５】
今仮に，ＬＳＩが，クロック入力端子４から入力されるクロックの入力タイミングが厳しいセルCEL1，CEL2，CEL3と，タイミング条件がない他のセルCELnとが混在しているとする。そして，クロックの入力タイミング条件は，セルCEL1，CEL2，CEL3の順番に厳しい（より速く供給されるべき）とする。
【００１６】
上記のタイミング条件を優先してチップ内に複数のセルを自動配置処理すると，図１に示される通り，クロック入力端子４に最も近い位置に，第１のセルCEL1が配置され，その外側に第２のセルCEL2が配置され，更にその外側に第３のセルCEL3が配置される。しかも，これらのセルは，間隔を開けることなく隣接して配置される。また，タイミング条件がない若しくはタイミング条件が緩やかな他のセルCELnは，残ったセルアレイ内に一定の間隔を確保しながら配置される。その結果，クロック入力端子４から一定の距離内の領域５においては，セルの混雑度が高くなり，それに伴い配線の混雑度も高くなる。
【００１７】
図１のようにセルが配置されたチップに対して，詳細配線処理を行うと，混雑度が高い領域５において，詳細配線を形成することができずに，配線不能結果におちいることが予想される。
【００１８】
図２は，チップ内を仮想的に分割した小領域DSR1〜6を示す。図２では，図面の関係上チップ１が６つの小領域に分割されているが，実際にはより多くの小領域に分割されることが好ましい。本実施の形態のレイアウト方法によれば，この分割された小領域DSR毎に配線の混雑度を解析する。自動配置されたセル間の配線を概略的に形成するグローバル配線処理により，接続配線を形成し，そのグローバル配線に従って，小領域毎の配線の混雑度を求める。この混雑度の求め方については，後に詳述する。
【００１９】
そして，小領域での配線混雑度が基準レベルを超える場合は，その小領域内でセルの再配置処理を行う。セルの再配置処理には，種々の手法が考えられるが，より好ましい処理としては，（１）セルの間隔を拡げる，（２）セル列の間隔を拡げる，（３）隣接するセルを上下，左右，斜め，回転方向に入れ替える，（４）セルの向きを変更，反転する，（５）論理特性が同一であって端子位置が異なるセルに置き換えるなどが含まれる。これらのセル再配置処理では，セル間の相対的な位置関係（トポロジー関係）が維持されたまま配置が変更されるので，タイミング条件を優先したセル配置状態が維持される。或いは，セルの位置が僅かに変更されるのみであり，タイミングが最適化された状態が維持される。これらのセル再配置処理についても，後に詳述する。
【００２０】
図１に示した領域５に対応する小領域DSR3において，配線の混雑度が基準レベルより高いことが検出されると，図３に示すように，小領域DSR3内において，セルの再配置処理が行われる。図３の例では，一番下のセルアレイと２番目のセルアレイ内において，隣接していた第１のセルCEL1と第２のセルCEL2との間に間隔１０を新たに設ける再配置処理が行われている。この再配置処理により，小領域DSR3内における配線の混雑度が緩和されることになり，その後の詳細配線処理において，配線不能になる可能性が低くなる。
【００２１】
図４は，本実施の形態例におけるレイアウト装置の構成図である。また，図５は，そのレイアウト方法のフローチャート図である。図４に示したレイアウト装置は，エンジニアリングワークステーションである演算装置２０とその入出力用端末装置２２と，演算装置２０にネットワーク２１を介して接続されるファイルサーバ２３とを有し，ファイルサーバ２３には，複数のデータファイルDF1〜7とプログラムP1〜7が格納される。
【００２２】
データファイルは，あらかじめ複数のセルを登録したセルライブラリDF1と，論理設計により生成された複数のセルとその接続データを有するネットリストデータファイルDF2と，ネットリスト内の特定のセルに対するタイミング条件を有するタイミング条件データファイルDF4と，セル配置プログラムP1により配置されたセルの配置（位置）データを有するセル配置データファイルDF3とを有する。更に，データファイルは，配置されたセルに対してグローバル配線プログラムP2により形成された概略的な配線データを含むグローバル配線データファイルDF5と，クロックツリー生成プログラムP3により生成されたクロックツリーデータファイルDF6と，オプティマイズプログラムP4により生成されたオプティマイズデータファイルDF7とを有する。
【００２３】
上記のデータファイルのうち，データファイルDF1，DF2，DF4は，レイアウト工程の前に生成され，それ以外のデータファイルは本レイアウト装置により生成される。
【００２４】
レイアウト装置のプログラムは，上述のプログラム以外に，チップ内の配線の混雑度を求めて基準値レベルを超えているか否かを解析する混雑度解析プログラムP5と，混雑度が基準値レベルを超えている小領域内においてセルの再配置を行うセル再配置プログラムP6とを有する。この２つのプログラムにより，詳細配線処理において配線不能結果になる可能性を少なくすることができる。そして，レイアウト装置のプログラムには，自動配置されタイミングを最適化された複数のセルに対して，接続配線を自動生成する詳細配線プログラムP7が含まれる。グローバル配線プログラムと詳細配線プログラムの違いについては，後に詳述する。
【００２５】
図５のレイアウト方法のフローチャートにしたがって説明する。チップ内にセルを配置してその間の接続配線を生成するレイアウト工程は，ＬＳＩの目的とする機能を実現するための論理回路デザインの後で行われる。論理デザインが終了した段階で，セルとその接続データを含むネットリストDF2が生成される。
【００２６】
レイアウト工程では，最初にネットリストにしたがって，チップ内にセルの初期配置が行われる（Ｓ１０）。このセル配置処理は，ＬＳＩの高速性を考慮して，入力信号やクロックのタイミング条件を優先してセルを自動配置する。タイミング条件を優先してセル配置することで，その後の論理シミュレーションでフェイル結果に至る可能性を低くすることができる。そのために，オペレータは，入力信号やクロックのタイミング制約が厳しいセルに対して，どの信号またはクロックについて，どのようなタイミングの制約があるかを示すタイミング条件データファイルDF4を生成する。従って，セル配置処理Ｓ１０は，ネットリストDF2とタイミング条件DF4とにしたがって行われ，その結果セルの配置データ（位置データ）を有するセル配置データファイルDF3が生成される。この自動セル配置により，図１に示したような一部でセルが密集した状態のセル配置が生成される。
【００２７】
次に，レイアウト装置は，ネットリストDF2とセル配置データファイルDF3とを参照して，グローバル配線処理を行う（Ｓ１２）。グローバル配線処理Ｓ１２は，チップの入出力端子や複数のセル間の接続配線を，一部短絡を許容しながら生成する処理である。接続配線の条件が緩和されているので，比較的短いコンピュータ演算時間で処理することができる。それに対して，後に行われる詳細配線処理Ｓ３０は，チップ入出力端子や複数のセル間の接続配線を，いっさいの短絡を許容せずに生成する処理である。従って，詳細配線処理は，前述のとおり比較的長いコンピュータ演算時間を要する処理である。
【００２８】
図６は，詳細配線プログラムのフローチャート図である。詳細配線処理では，入出力端子やセルの接続すべき２つのピン（接続端子）の間において，配線の形成が許可されるグリッド上の最短配線ルートを検出する（Ｓ４０）。そして，その検出した配線が，グリッド上にすでに生成されている既配線と重なるか否かがチェックされる（Ｓ４２）。検出した配線が既配線と重なる場合は，配線短絡を招くので，異なる配線ルートが検出される（Ｓ４４）。そして，その新たに検出された配線が既配線と重なるか否かがチェックされる（Ｓ４２）。このように，検出した配線が既配線と重ならないことが確認されるまで，処理Ｓ４２とＳ４４が繰り返される。上記の処理が全ての接続すべき配線ルートに対して終了すると（Ｓ４６），詳細配線処理は完了する。
【００２９】
従って，詳細配線処理では，その配線ルート検出アルゴリズムに従って，短絡のない全ての配線を生成する必要があり，比較的長いコンピュータ演算時間を要する。
【００３０】
それに対して，グローバル配線処理（概略配線処理）では，既配線との短絡禁止条件が詳細配線処理に比較すると緩やかになっており，比較的短いコンピュータ演算時間で行うことができる。
【００３１】
図７は，グローバル配線プログラムのフローチャート図である。図７には２種類のフローチャートＡ，Ｂが示される。ここに示したフローチャートは，図６の詳細配線プログラムのフローチャートとは工程番号S42G，S44Gが異なるのみである。即ち，フローチャートＡでは，工程S42Gにて検出した配線が既配線と１回まで重なることを許可する。従って，グリッド上に形成される配線は，２重に重なることは許容されるが，３重に重なることは禁止される。このように，配線短絡の条件が緩和されているので，チップ内の配線の生成に必要なコンピュータ演算時間は，詳細配線プログラムよりも短くなる。
【００３２】
フローチャートＢでは，最初に２つのピン間のグリッド上の最短配線ルートが既配線と重なっている場合に，異なる配線ルートを検出したら（Ｓ４４），再度既配線との重なりをチェックすることなく，無条件でその異なる配線ルートを採用する（図中Ｓ44G）。従って，この場合も，グリッド上で複数の配線が重なることが許容されるので，配線生成に必要なコンピュータ演算時間は，詳細配線プログラムよりも短くなる。
【００３３】
上記のフローチャートは，配線ルート探索アルゴリズムを概略的に説明したものである。より詳細に説明すれば，例えば，配線ルートは，水平方向の配線と垂直方向の配線とそれらを接続するビアホールとにより構成されるのが一般的であり，一方の接続端子から出発して，最初に垂直方向の配線を検出し，ビアホールを介して次の水平方向の配線を検出し，既存の配線と短絡する場合はそれを避けるようにして別の方向の配線を検出するなどして，他方の接続端子に達する，というアルゴリズムが考えられる。その場合でも，上記のように既存配線との重なりをある程度許容することにより，グローバル配線処理は，短時間で完了することができる。配線ルート探索アルゴリズムは，例えばケイデンス社製の「Silicon Ensemble」に含まれている配線ルート探索ツールにより当業者に知られているので，詳細な説明は省略する。
【００３４】
図５に戻り，グローバル配線処理によりチップ内に配置されたセル間の概略的な配線が生成される。その結果は，グローバル配線データファイルDF5として記録される。このグローバル配線は，一部に配線短絡を含むが，その後のタイミングの最適化処理や配線の混雑度解析には十分利用できる。
【００３５】
次に，クロックツリーの生成処理が行われる（Ｓ１４）。クロックツリーとは，あるクロックが複数のセルに並列に供給される場合，複数のセルに対して同じタイミングで供給できるようにしたクロック供給配線である。この場合のクロック供給配線は一般的にツリー形状であり，供給タイミングをそろえるために，クロック供給配線内にバッファなどを挿入してその伝播遅延時間を同程度にする処理が行われる。
【００３６】
図８は，クロックツリー生成例を示す回路図である。図８（Ａ）に示された回路図は，２入力IN0,IN1のANDゲート３０と，その出力OUTがそれぞれデータ入力として供給される２つのフリップフロップFF1,FF2とからなり，２つのフリップフロップのクロック端子には，共通のクロックCLKがクロック供給端子L0,L1を介してそれぞれ供給される。クロック供給配線は，クロック入力端子から分岐点n1を介して，２つの配線L0,L1に分かれて，それぞれのフリップフロップのクロック端子に接続される。つまり，ツリー形状である。
【００３７】
このような回路の場合，ANDゲートの出力OUTはほぼ同じタイミングで２つのフリップフロップのデータ端子Ｄに供給されるので，それらのクロック端子CKへのクロックCLKの入力タイミングをほぼ同じタイミングにそろえる必要がある。ところが，配線L0は配線L1に比較して分岐ノードn1からの距離が長いので，クロック信号伝播時間が長くなり，２つのフリップフロップFF0,FF1間で，クロックのスキューが発生し，誤動作を招くおそれがある。
【００３８】
そこで，クロックツリー生成処理では，図８（Ｂ）に示されるように，第２のクロック供給配線Ｌ１にバッファ３２を挿入し，２つのフリップフロップFF1,FF2へのクロック入力タイミングをそろえることが行われる。即ち，クロックツリー生成処理では，セル配置処理Ｓ１０によりタイミングを優先したセルの配置が行われた後に，その配置に対してクロックのタイミングの最適化を行うものである。クロックツリー生成処理の結果，クロックツリーデータファイルDF6が生成される。
【００３９】
次に，図５に示されるとおり，インプレースオプティマイズ処理が行われる（Ｓ１６）。この最適化処理は，タイミング優先で配置された複数のセルに対して，セル間の信号のタイミングを最適化するために，配線を駆動するセルを異なる駆動能力のセルに置き換えたり，セルの遅延時間が異なるセルに置き換えたり，セルの入力容量が異なるセルに置き換えたり，配線内にバッファを挿入したり削除したりして信号伝播時間の最適化を図る処理である。
【００４０】
図９は，インプレースオプティマイズ処理の例を示す図である。図９（Ａ）の回路例では，２入力のANDゲート３０の出力OUTが２つのフリップフロップFF1,FF2とそれ以外の図示しない回路にも供給されている。そして，セル配置の結果，ANDゲート３０とフリップフロップFF1との間の配線L10に比較して，フリップフロップFF2への配線L11がかなり長くなっており，更に図示しない回路への配線L12,L13,L14も長くなっている。
【００４１】
その結果，第１に，ANDゲート３０の駆動能力に対して，配線L10〜L14の駆動負荷が大きくなり，ANDゲート３０の駆動能力不足が判明し，更に，配線L10の信号伝播時間が他の配線L11〜L14に比較して短すぎることが判明する。
【００４２】
そこで，図９（Ｂ）に示されるように，セルを配置した状態（インプレース）での最適化処理により，第１に，ANDゲートをより駆動能力の大きいANDゲート30Xに置き換えて駆動能力不足を解消し，第２に，短い配線L10内にバッファ３４を挿入して伝播時間を長くし，複数の配線L10〜L14の信号伝播時間をそろえることが行われる。つまり，論理回路設計の段階では判明しなかったセル配置に伴う修正が，この最適化処理により行われる。インプレースオプティマイズ処理の結果，オプティマイズデータファイルDF7が生成される。
【００４３】
上記のクロックツリー生成処理Ｓ１４やインプレースオプティマイズ処理Ｓ１６の結果，新たなバッファが生成され，セルの置き換えが行われる。従って，それらの処理の後はそれぞれグローバル配線生成処理が行われる。
【００４４】
次に，配線混雑度解析処理が行われる（Ｓ１８）。この配線混雑度解析処理は従来のレイアウトツールにない新たな処理である。本実施の形態では，セル配置とその最適化処理の後，詳細配線処理をする前に，詳細配線処理で配線不能になる可能性を予測するために，配線の混雑度を解析する。
【００４５】
配線の混雑度解析では，チップ内を複数の小領域に分割し，その小領域内での混雑度を求める。複数の小領域への分割は，図２にて示した通りである。配線混雑度は，種々の考え方があるが，例えば，（１）小領域内のセル面積を小領域面積で除したセル面積密度，（２）小領域内のセルの接続ピン数を小領域面積で除した接続ピン密度，（３）小領域内の配線総数（水平方向と垂直方向）をグリッド数で除した配線占有率，（４）小領域内を通過する配線数，（５）小領域内の配線総数を接続ピン総数で除した値などが考えられる。
【００４６】
上記（１）のセル面積密度と（２）の接続ピン密度は，間接的に配線の混雑度を示すものであり，簡単な演算により求めることができる。また，（３）の配線占有率は，より直接的な配線混雑度に関するものであるが，グローバル配線により生成された配線に基づくものであり必ずしも混雑度を直接示すものでもない。（４）の通過配線数は，通過配線数が多くなると，小領域内のセルの配線が困難になり配線混雑度の目安になる。そして，（５）の値は接続ピンあたりの配線数であり，例えば出力ピンに対するファンアウト数が多かったり，通過配線数が多かったりすると配線が困難になり配線混雑度の目安になる。
【００４７】
図１０は，配線混雑度を説明する図である。比較のために，図１０（Ａ）に配線混雑度が低いセルレイアウト例を，図１０（Ｂ）に配線混雑度が高いセルレイアウト例をそれぞれ示す。図１０（Ａ）のセルレイアウト例では，２つの小領域DSR10,11内に，それぞれセルCEL10〜12とCEL13〜16とが配置される。一方，図１０（Ｂ）のセルレイアウト例では，２つの小領域DSR12,13内に，それぞれセルCEL20〜23とCEL24〜27とが配置される。
【００４８】
小領域DSR10とDSR12とを比較すると，小領域DSR10内には３つのセルしか配置されず，それぞれのセルは左辺に２つずつの入力端子と右辺に１つずつの出力端子を有するのみである。それに対して，小領域DSR12内には，４つのセルが配置されていて，それぞれのセルは左辺に３つずつの入力端子と右辺に１つずつの出力端子を有する。従って，上記の配線混雑度のうち，（１）セル面積密度と（２）接続ピン密度とに関する混雑度については，小領域DSR12のほうがDSR10よりも高くなる。
【００４９】
次に，小領域DSR11とDSR13とを比較すると，小領域DSR11内のセルCEL13〜16は全て出力端子のファンアウト数は「１」であり，小領域内を通過する配線はない。それに対して，小領域DSR13内のセルCEL24〜27は出力のファンアウト数が全て「２」であり，小領域内を通過する配線PL1,PL2が存在する。
【００５０】
従って，両小領域DSR11,13について，上記（１）セル面積密度と（２）接続ピン密度については同じであるが，上記（４）通過配線数と（５）接続ピン当たりの配線数については，小領域DSR13のほうが高いレベルになる。このように，小領域内に同じセル数，接続ピン数が含まれても，出力ピンのファンアウト数が多かったり，外部からの通過配線が多かったりすると，配線の混雑度が高くなり，詳細配線処理では配線不能の可能性がある。
【００５１】
上記以外にも配線混雑度に関連する値があるが，適宜採用することができる。配線混雑度解析処理Ｓ１８では，ネットリストDF2と，セル配置データDF3と，クロックツリーデータDF6と，オプティマイズデータDF7と，グローバル配線DF5に従って，上記の混雑度に関連する値を小領域毎に求め，基準レベルに応じて，混雑度マップが表示出力される。例えば，図２に示したように，小領域DSR3が混雑度大と表示され，セルの再配置対象の小領域に指定される。
【００５２】
配線可能な混雑度でない場合は（Ｓ２０），混雑度が高い小領域内でのセルの再配置処理が行われる（Ｓ２６）。このセルの再配置処理では，第１に，小領域内に限定して行われるので，チップ全体のセル再配置処理に比較して，チップ全体のセルのタイミング最適化状態をよりそのままに維持することができる。第２に，小領域内でのセル再配置では，セル間の位置関係を維持しながら行うという制約を課すことにより，小領域内のセルのタイミング最適化状態も，よりそのままに維持することができる。セルの再配置処理については，後に詳述する。
【００５３】
混雑度が高い小領域内に限定してセルの再配置を行った後，再度クロックツリー生成処理が行われる（Ｓ２８）。セルの位置が変更されることにより，タイミング最適化に大切なクロックツリーが再度最適化される。そして，再度配線可能な混雑度か否かが判断され（Ｓ２０），配線可能と判断されれば，詳細配線処理Ｓ３０に移行する。
【００５４】
別の好ましい実施の形態では，図５中に破線で示されるとおり，再度配線可能な混雑度か否か判断することなく，セルの再配置後に詳細配線処理Ｓ３０を行っても良い。その場合，少なくとも配線不能になりそうな小領域内においてセルの再配置を行っているので，従来の方法よりも詳細配線処理で配線不能になる可能性は低くなる。従って，従来例のようにセルの初期配置処理と詳細配線処理をやり直すという可能性は低くなる。
【００５５】
別の好ましい実施の形態では，一旦セルの再配置をおこなった後に，再度配線可能な混雑度になっていないと判断された場合は，再配置対象の小領域を拡大して，再度セルの再配置処理を行う（Ｓ２２，Ｓ２４）。再配置処理の対象領域を大きくすることで，より自由度の高い再配置処理が行えるので，小領域内の配線混雑度を緩和することができる。
【００５６】
次に，セルの再配置処理について説明する。図１１，１２は，セルの再配置において，セル列内における隣接セル間の間隔を拡げる方法を説明する図である。図１１（Ａ）は，セル列2A内に３つのセルCEL30〜32が配置され，別のセル列2Bにもそれらに近接してセルCEL33が配置されている。この場合，図１１（Ｂ）に示すとおり，セル列2A内の隣接する３つのセルCEL30〜32の間隔４０，４１を設けて，そこを通過する配線４５，４６が形成できるようにする。このようなセルの再配置処理では，セルCEL30〜32の相対的な位置関係は維持されながら，わずかな間隔４０，４１を設けるという処理を行うのみである。このような再配置であれば，セルのタイミングが最適化された状態を維持することができる。
【００５７】
図１２には，より具体的に示される。この例では，図１２（Ａ）に示されるように，セルCEL30内に３つの端子が存在し，その一つの端子４２がセルCEL33の端子４４と接続する必要があるとすると，図中破線で示す方向に配線を形成する必要がある。配線は，水平方向の１層目の配線層ＬＩと垂直方向の２層目の配線層ＬＩＩとで構成されるが，セルCE30では垂直方向の２層目の配線層ＬＩＩ内にセルCEL33方向の配線可能なグリッドがないので，端子４２，４４間を接続することができない。
【００５８】
そこで，図１２（Ｂ）のようにセル間隔４０を形成することで，新たに配線が通過できるグリッドが増加し，図１２（Ｃ）に示されるように，端子４２，４４間を接続する２層目の配線４５を形成することができるようになる。このように，セル間隔を設けることで配線不能状態が配線可能状態に変わる。しかも，セル間隔を設けることで，セルのタイミング最適化状態に支障がでる可能性は少なくなる。
【００５９】
図１３は，セルの再配置において，セル列の間隔を生成する方法を説明する図である。図１３（Ａ）では，セル列2A，2Bの間にチャネル領域がなく，セル列2Bと2Cとの間にチャネル領域3Aが存在する例である。そして，セル列2A,2Bの左端には，４個ずつのセルが密集して配置されている。このようなセル配置に対して，セルの再配置処理では，図１３（Ｂ）に示すとおり，セル列2Aと2Bとの間に新たな間隔3Bを設けるようにする。その結果，間隔3Bに新たに配線を形成できるグリッドが発生し，配線を形成することが可能になる。つまり，新たな配線領域を確保して，詳細配線での配線不能の可能性を低くしている。
【００６０】
図１４は，セルの再配置において，隣接するセルの位置を上下或いは左右，斜め方向，回転方向に入れ替える方法を説明する図である。図１４（Ａ）に示されるとおり，隣接するセル列2A,2B内にセルCEL40,41及びCEL42,43が配置されている。そして，これらの４個のセルの塊の両側に，配線領域５０，５１が確保されている。しかしながら，セルCEL40,43は，それぞれ２端子ずつしか有していないが，セルCEL41,42は，それぞれ４端子ずつ有している。従って，配線領域５０には合計で８端子に接続される配線を設ける必要があり，場合によっては配線不能状態になる。
【００６１】
そこで，図１４（Ｂ）に示す通り，４つのセルCEL40〜43を反時計回りに移動して，配線領域５１には，２端子のセルCLE40と４端子のセルCLE41とが並び，配線領域５０にも，２端子のセルCEL43と４端子のセルCEL42とが並ぶように再配置する。このようにセルを再配置することで，配線領域５０に必要な配線数が６本と緩和され，配線不能状態を回避することができる。しかも，隣接するセルの位置を入れ替えるだけであるので，タイミングを優先して配置したセルの相対的な位置関係を維持することができる。つまり，セルCEL40〜43は，再配置後も全て同等の位置を維持することができるので，セルのタイミング最適化された状態を維持することができる。
【００６２】
上記の再配置例において，４つのセルを時計回りに移動しても良いし，セルCEL40とCEL41とを入れ替えることでも，同様に配線の混雑を緩和することができる。
【００６３】
図１５は，セルの再配置において，セルの方向を反転する方法を説明する図である。図１５（Ａ）の例では，セル列内にセルCEL50〜53が配置されている。そして，セルCEL50〜52はそれぞれ４つの端子を有し，セルCEL53のみが２つの端子しか有しない。セル51,52,53の原点OR1,2,3は全て左側に位置している。その結果，セルCEL51，CEL52において接続ピンが密集して配線不能になる可能性がある。
【００６４】
そこで，セルの再配置において，図１５（Ｂ）に示されるように，セルCEL52の方向を反転して，その原点OR2が右側になるように再配置する。その結果，セルCEL52の端子位置（接続ピン位置）が右側になり，セルCEL51での端子密度が緩和されて，配線不能の可能性を少なくすることができる。そして，単にセルCEL52の方向が変わっただけであるので，セルの相対位置に変更はなく，セルのタイミング最適化状態が維持される。
【００６５】
図１６は，セルの再配置において，同じ論理回路及び電気特性を有し端子位置が異なるセルに置き換える方法を説明する図である。図１６（Ａ）の例では，セルCEL60,61が隣接して配置され，更にセルCEL60は２つの接続端子が右辺中央に位置し，セルCEL61は２つの接続端子が左辺中央に位置している。つまり，接続端子が接続領域６２，６３を隔てた位置に集中している。かかる状況では，接続配線が不可能になる可能性がある。
【００６６】
そこで，セルの再配置処理では，図１６（Ｂ）に示されるように，セルCEL60，CEL61と同じ論理回路を有し，出力駆動能力や入出力レベルなどの電気的特性が同等であって，接続端子位置が異なるセルCEL60A，CEL61Aに置き換える。これらのセルCEL60A，CEL61Aは，セルライブラリ内に登録された元のセルCEL60，CEL61に代替え可能なセルである。その結果，両セルCEL60A，CEL61Aの接続端子は，接続領域６２，６３側に位置することになり，また，集中度も緩和されて，配線不可能になる可能性を低くすることができる。しかも，セルの位置に変更はないので，セルのタイミング最適状態を維持することもできる。
【００６７】
以上，６種類のセル再配置方法の例を説明した。これらの再配置は，配線の混雑度が高いことが予想される小領域内に限定して行われる。しかも，セル間の相対的位置関係が維持され，或いはセルの位置の微少変更に止められ，タイミングを優先してセル配置し（S10），クロックツリー生成（S14）とインプレースオプティマイズ処理（S16）した結果生成されたセルのタイミング最適化状態を維持することができる。従って，上記のセルの再配置処理により，最初のセル配置とその後の最適化処理を無駄にすることなく，その後の詳細配線処理での配線不可能の可能性を低くすることができる。しかも，セルの再配置処理は，混雑度の高い小領域内に限られているので，全体のセルの配置状態が維持されると共に，再配置処理の対象セル数が少なくコンピュータの処理時間は短い。
【００６８】
また，上記以外にも，セルのタイミング状態を維持したままセルの再配置を行う方法があるが，いずれの方法でも，セル間の相対的位置を維持し，或いはセルの位置の微少変更のみにすることで，セルの最適化されたタイミング状態を維持することができる。
【００６９】
以上説明したＬＳＩのレイアウト方法は，図４に示すレイアウトプログラムツールを有するコンピュータ装置により行うことができる。尚，各レイアウトプログラムツールは，記録媒体に記憶されている。
【００７０】
以上，実施の形態例をまとめると以下の付記の通りである。
【００７１】
（付記１）複数のセルを有するＬＳＩのレイアウト方法において，
複数のセルとその接続データを有するネットリストとセルのタイミング条件データに基づいてチップ内にセルの自動配置を行うセル配置処理工程と，
前記セル間を接続する配線を，配線間の短絡条件を緩和して生成するグローバル配線処理工程と，
前記自動配置されたセル間を接続する配線の信号伝播時間に応じて最適化するタイミング最適化処理工程と，
前記配線の混雑度を求め，当該混雑度が基準レベルより高い領域を検出する混雑度解析処理工程と，
前記チップを複数に分割した小領域であって，当該混雑度が基準レベルより高い小領域内で，前記セルの再配置処理を行うセル再配置処理工程と，
前記セル再配置処理の後で，セル間を接続する配線を，配線間の短絡を禁止して生成する詳細配線処理工程とを有することを特徴とするＬＳＩのレイアウト方法。
【００７２】
（付記２）付記１において，
前記セルの配置処理後であって，前記セルの再配置処理の前に，配置されたセルに対してクロックツリーを生成するクロックツリー生成工程を有することを特徴とするＬＳＩのレイアウト方法。
【００７３】
（付記３）付記２において，
前記セルの再配置処理の後で，再度クロックツリー生成工程を実行することを特徴とするＬＳＩのレイアウト方法。
【００７４】
（付記４）付記１において，
前記セルの再配置処理工程は，隣接する複数のセル間またはセル列間の間隔を拡げる処理であることを特徴とするＬＳＩのレイアウト方法。
【００７５】
（付記５）付記１において，
前記セルの再配置処理工程は，隣接する複数のセルの左右，上下，斜め，回転方向のいずれかに入れ替える処理であることを特徴とするＬＳＩのレイアウト方法。
【００７６】
（付記６）付記１において，
前記セルの再配置処理工程は，セルの方向を反転する処理であることを特徴とするＬＳＩのレイアウト方法。
【００７７】
（付記７）付記１において，
前記セルの再配置処理工程は，セルを論理特性が同じであって接続ピンの位置が異なる別のセルに置き換える処理であることを特徴とするＬＳＩのレイアウト方法。
【００７８】
（付記８）付記１において，
前記セルの再配置処理は，セルのタイミング関係を維持しながら行われることを特徴とするＬＳＩのレイアウト方法。
【００７９】
（付記９）付記１において，
前記配線の混雑度解析工程は，前記小領域内のセルの総面積，セルの接続ピン総数，接続配線総数，通過配線総数の少なくとも一つに応じて前記混雑度を決定することを特徴とするＬＳＩのレイアウト方法。
【００８０】
（付記１０）付記１において，
前記配線の混雑度解析工程は，前記小領域内の接続配線総数をピン総数で除した値に応じて前記混雑度を決定することを特徴とするＬＳＩのレイアウト方法。
【００８１】
（付記１１）付記１において，
前記タイミング最適化処理は，セルの出力駆動能力，セルの遅延時間，セルの入力負荷容量の少なくとも１つが異なるセルに置き換え，またはセル間を接続する配線内にバッファを追加し，又はセル間を接続する配線内のバッファを削除する処理の少なくとも一つを行うことを特徴とするＬＳＩのレイアウト方法。
【００８２】
（付記１２）付記１において，
前記セルの再配置処理後に，再度配線の混雑度解析を行い，基準レベルを超えていない場合に，前記詳細配線処理を行うことを特徴とするＬＳＩのレイアウト方法。
【００８３】
（付記１３）付記１２において，
前記セルの再配置処理後の混雑度解析の結果，基準レベルを超えている領域が存在する場合は，前記小領域のサイズを大きくして再度セルの再配置処理を行うことを特徴とするＬＳＩのレイアウト方法。
【００８４】
（付記１４）複数のセルを有するＬＳＩのレイアウトを行うレイアウト装置において，
複数のセルとその接続データを有するネットリストとセルのタイミング条件データに基づいてチップ内にセルの自動配置を行う自動配置手段と，
前記セル間を接続する配線を，配線間の短絡条件を緩和して生成するグローバル配線処理手段と，
前記自動配置されたセル間を接続する配線の信号伝播時間に応じて最適化するタイミング最適化処理手段と，
前記配線の混雑度を求め，当該混雑度が基準レベルより高い領域を検出する混雑度解析処理手段と，
前記チップを複数に分割した小領域であって，当該混雑度が基準レベルより高い小領域内で，前記セルの再配置処理を行うセル再配置処理手段と，
前記セル再配置処理の後で，セル間を接続する配線を，配線間の短絡を禁止して生成する詳細配線処理手段とを有することを特徴とするＬＳＩのレイアウト装置。
【００８５】
（付記１５）付記１４において，
前記セルの配置処理後であって，前記セルの再配置処理の前に，配置されたセルに対してクロックツリーを生成するクロックツリー生成手段を有することを特徴とするＬＳＩのレイアウト装置。
【００８６】
（付記１６）付記１５において，
前記セルの再配置処理の後で，再度クロックツリー生成を行うことを特徴とするＬＳＩのレイアウト装置。
【００８７】
（付記１７）付記１６において，
前記セルの再配置処理手段は，セルのタイミング関係を維持しながら行われることを特徴とするＬＳＩのレイアウト装置。
【００８８】
（付記１８）複数のセルを有するＬＳＩのレイアウトをコンピュータに実行させるレイアウトプログラムにおいて，
複数のセルとその接続データを有するネットリストとセルのタイミング条件データに基づいてチップ内にセルの自動配置を行う自動セル配置プログラムと，
前記セル間を接続する配線を，配線間の短絡条件を緩和して生成するグローバル配線処理プログラムと，
前記自動配置されたセル間を接続する配線の信号伝播時間に応じて最適化するタイミング最適化処理プログラムと，
前記配線の混雑度を求め，当該混雑度が基準レベルより高い領域を検出する混雑度解析処理プログラムと，
前記チップを複数に分割した小領域であって，当該混雑度が基準レベルより高い小領域内で，前記セルの再配置処理を行うセル再配置処理プログラムと，
前記セル再配置処理の後で，セル間を接続する配線を，配線間の短絡を禁止して生成する詳細配線処理プログラムとを有することを特徴とするＬＳＩのレイアウトプログラム。
【００８９】
【発明の効果】
以上，本発明によれば，タイミングを優先してセルの自動配置を行い，そのタイミングの最適化処理を行ってから，配線の混雑度の高い領域にセルの再配置処理を行うので，その後の詳細配線処理において，配線不能になる可能性を低く抑えることができる。従って，改めてセルの自動配置処理と詳細配線処理というコンピュータ処理時間が長い処理を繰り返す必要が少なくなる。
【図面の簡単な説明】
【図１】本発明にかかる実施の形態のレイアウト方法を概略的に説明する図である。
【図２】本発明にかかる実施の形態のレイアウト方法を概略的に説明する図である。
【図３】本発明にかかる実施の形態のレイアウト方法を概略的に説明する図である。
【図４】本実施の形態例におけるレイアウト装置の構成図である。
【図５】本実施の形態例におけるレイアウト方法のフローチャート図である。
【図６】詳細配線プログラムのフローチャート図である。
【図７】グローバル配線プログラムのフローチャート図である。
【図８】クロックツリー生成例を示す回路図である。
【図９】インプレースオプティマイズ処理の例を示す図である。
【図１０】配線混雑度を説明する図である。
【図１１】セルの再配置において，セル列内における隣接セル間の間隔を拡げる方法を説明する図である。
【図１２】セルの再配置において，セル列内における隣接セル間の間隔を拡げる方法を説明する図である。
【図１３】セルの再配置において，セル列の間隔を生成する方法を説明する図である。
【図１４】セルの再配置において，隣接するセルの位置を上下或いは左右に入れ替える方法を説明する図である。
【図１５】セルの再配置において，セルの方向を反転する方法を説明する図である。
【図１６】セルの再配置において，同じ論理回路及び電気特性を有し端子位置が異なるセルに置き換える方法を説明する図である。
【符号の説明】
１ チップ
２ セルアレイ，セル列
３ チャネル領域
CEL セル
DSR 小領域
【発明の属する技術分野】
本発明は，集積回路（以下ＬＳＩ）のレイアウト方法及びその装置に関し，特に，タイミングを優先してセル配置を行いセル間配線を生成するＬＳＩのレイアウト方法及びそのレイアウト装置に関する。
【０００２】
【従来の技術】
ＬＳＩの設計は，一般にコンピュータを利用して行われる。特に，セミカスタムＬＳＩであるＡＳＩＣ（Application Specific Integrated Circuit)は，目的とする機能を発揮するＬＳＩの論理設計を行い，その論理設計データを基にＬＳＩのレイアウトを行う。論理設計では，あらかじめ登録されているセルライブラリから必要な基本セルを選択し，目的とする機能を実現するための論理回路が設計される。その結果，複数のセルとその入出力端子間の接続を有するネットリストと呼ばれる論理データが生成される。このネットリストに従って，チップ上のセルの配置とセル間の接続配線を生成するレイアウト工程が行われる。
【０００３】
レイアウト工程が終了すると，セルの駆動能力と接続配線の抵抗，容量，インダクタンスなどから信号伝播遅延時間が計算され，ネットリストと遅延時間とを参照して，論理シミュレーションが行われる。論理シミュレーションをパスすると，実際のレイアウトデータの生成，パターンデータの生成に移り，ＬＳＩの前工程に必要なデータが生成される。
【０００４】
近年のＬＳＩの高速化に伴い，信号やクロックのタイミングを考慮したセル配置処理や，信号やクロックのタイミングを最適化する最適化処理が実施されている。特にネットリストをもとにしたセルの自動配置処理では，複数のセルに対して，入力信号やクロックのタイミングがより厳しいセルの順に優先順位を決めて，その優先順位に従ってセルを自動配置することが行われる。
【０００５】
【発明が解決しようとする課題】
しかしながら，信号やクロックのタイミングを重視してセルを配置するあまり，チップ内に局所的なセルの密集領域が形成されることがある。即ち，入力信号端子やクロック入力端子に近い領域に，多くのセルが配置されることがある。その結果，自動セル配置工程の後の自動配線工程において，密集領域で配線が混雑して配線を生成することができなくなることがたびたび起こるようになった。自動配線工程で配線不能になると，タイミング条件や他の条件を変更したうえで，再度，自動セル配置処理と自動配線処理をやり直す必要がある。
【０００６】
近年のＡＳＩＣのゲート数は膨大な数に上り，高速コンピュータを利用しても，自動セル配置処理に数日間，自動配線処理にも数日間が必要になっており，上記の自動セル配置処理と自動配線処理のやり直しは，ＡＳＩＣの設計工程を長期化させ，コストアップにつながるばかりでなく，ＡＳＩＣの短納期という特徴を失わせることにつながる。
【０００７】
そこで，本発明の目的は，タイミングを優先したセル配置後の自動配線を，できるだけ可能にするレイアウト方法及びその装置を提供することにある。
【０００８】
【課題を解決するための手段】
上記の目的を達成するために，本発明の一つの側面によれば，複数のセルを有するＬＳＩのレイアウト方法において，セルとその接続データを有するネットリストとタイミング条件に基づいてセルの自動配置を行い，更に，前記タイミングの最適化処理を行って，チップ内に複数のセルを配置した後に，グローバル配線処理を実施し配線の混雑度を解析する。そして，配線の混雑度が高くて詳細配線処理が困難である判断された小領域内において，セルの再配置処理を実施する。そして，その再配置されたセルに対して詳細配線処理を行う。
【０００９】
上記の発明によれば，セルの再配置を混雑度が高い小領域内に限定して行うことで，タイミングが最適化された全体のセル配置を大幅に変更することなく，詳細配線処理で配線不能になる可能性を減らすことができる。その結果，従来のように，長時間のマシンタイムを要する自動セル配置処理と詳細配線処理が無駄に行われることが抑制または防止される。
【００１０】
上記の発明において，より好ましい実施例では，セルの再配置を行っても配線の混雑度が基準レベルより低くならない場合は，最初の小領域を拡大した新たな小領域内でセルの再配置処理を実施する。その結果，配線の混雑度が基準レベルより低ければ，詳細配線処理を行う。この方法によれば，小領域を拡大してセルの再配置処理を行うので，より高い柔軟性をもってセルの再配置処理を行うことができる。
【００１１】
上記の発明において，より好ましい実施例では，セルの再配置処理は，（１）セルの配置間隔を拡げる，（２）セル列の間隔を拡げる，（３）隣接するセルを上下，左右，斜め，回転方向に入れ替える，（４）セルの向きを変更，反転する，（５）論理特性が同一であって端子位置が異なるセルに置き換えるのいずれかを含む処理であることを特徴とする。かかるセルの再配置であれば，セルの相対的な位置関係が変動せずに，最適化されたタイミング状態を崩すことがなく，配線の混雑度を緩和することができる。
【００１２】
上記の発明において，より好ましい実施例では，配線の混雑度は，小領域内のセルの総面積，セルの接続ピン総数，接続配線総数，通過配線総数の少なくとも一つに応じて決定する。或いは，別の好ましい実施例では，配線の混雑度は，小領域内の接続配線総数をピン総数で除した値に応じて決定する。
【００１３】
【発明の実施の形態】
以下，図面を参照して本発明の実施の形態例を説明する。しかしながら，本発明の保護範囲は，以下の実施の形態例に限定されるものではなく，特許請求の範囲に記載された発明とその均等物にまで及ぶものである。
【００１４】
図１，２，３は，本発明にかかる実施の形態のレイアウト方法を概略的に説明する図であり，以下これらの図にしたがって，そのレイアウト方法を説明する。図１は，ある論理設計されたネットリストにタイミング条件を与えて，自動セル配置処理をした結果のセル配置例を示す。図１のＬＳＩは，一般的なスタンダードセルによるＡＳＩＣを示すものであり，チップ１内に複数のセルアレイ２とその間のチャネル領域３とが交互に配置されている。セルアレイ２内には，例えば縦方向のサイズは共通で，横方向のサイズがセルによって異なる複数のセルが，適宜配置される。
【００１５】
今仮に，ＬＳＩが，クロック入力端子４から入力されるクロックの入力タイミングが厳しいセルCEL1，CEL2，CEL3と，タイミング条件がない他のセルCELnとが混在しているとする。そして，クロックの入力タイミング条件は，セルCEL1，CEL2，CEL3の順番に厳しい（より速く供給されるべき）とする。
【００１６】
上記のタイミング条件を優先してチップ内に複数のセルを自動配置処理すると，図１に示される通り，クロック入力端子４に最も近い位置に，第１のセルCEL1が配置され，その外側に第２のセルCEL2が配置され，更にその外側に第３のセルCEL3が配置される。しかも，これらのセルは，間隔を開けることなく隣接して配置される。また，タイミング条件がない若しくはタイミング条件が緩やかな他のセルCELnは，残ったセルアレイ内に一定の間隔を確保しながら配置される。その結果，クロック入力端子４から一定の距離内の領域５においては，セルの混雑度が高くなり，それに伴い配線の混雑度も高くなる。
【００１７】
図１のようにセルが配置されたチップに対して，詳細配線処理を行うと，混雑度が高い領域５において，詳細配線を形成することができずに，配線不能結果におちいることが予想される。
【００１８】
図２は，チップ内を仮想的に分割した小領域DSR1〜6を示す。図２では，図面の関係上チップ１が６つの小領域に分割されているが，実際にはより多くの小領域に分割されることが好ましい。本実施の形態のレイアウト方法によれば，この分割された小領域DSR毎に配線の混雑度を解析する。自動配置されたセル間の配線を概略的に形成するグローバル配線処理により，接続配線を形成し，そのグローバル配線に従って，小領域毎の配線の混雑度を求める。この混雑度の求め方については，後に詳述する。
【００１９】
そして，小領域での配線混雑度が基準レベルを超える場合は，その小領域内でセルの再配置処理を行う。セルの再配置処理には，種々の手法が考えられるが，より好ましい処理としては，（１）セルの間隔を拡げる，（２）セル列の間隔を拡げる，（３）隣接するセルを上下，左右，斜め，回転方向に入れ替える，（４）セルの向きを変更，反転する，（５）論理特性が同一であって端子位置が異なるセルに置き換えるなどが含まれる。これらのセル再配置処理では，セル間の相対的な位置関係（トポロジー関係）が維持されたまま配置が変更されるので，タイミング条件を優先したセル配置状態が維持される。或いは，セルの位置が僅かに変更されるのみであり，タイミングが最適化された状態が維持される。これらのセル再配置処理についても，後に詳述する。
【００２０】
図１に示した領域５に対応する小領域DSR3において，配線の混雑度が基準レベルより高いことが検出されると，図３に示すように，小領域DSR3内において，セルの再配置処理が行われる。図３の例では，一番下のセルアレイと２番目のセルアレイ内において，隣接していた第１のセルCEL1と第２のセルCEL2との間に間隔１０を新たに設ける再配置処理が行われている。この再配置処理により，小領域DSR3内における配線の混雑度が緩和されることになり，その後の詳細配線処理において，配線不能になる可能性が低くなる。
【００２１】
図４は，本実施の形態例におけるレイアウト装置の構成図である。また，図５は，そのレイアウト方法のフローチャート図である。図４に示したレイアウト装置は，エンジニアリングワークステーションである演算装置２０とその入出力用端末装置２２と，演算装置２０にネットワーク２１を介して接続されるファイルサーバ２３とを有し，ファイルサーバ２３には，複数のデータファイルDF1〜7とプログラムP1〜7が格納される。
【００２２】
データファイルは，あらかじめ複数のセルを登録したセルライブラリDF1と，論理設計により生成された複数のセルとその接続データを有するネットリストデータファイルDF2と，ネットリスト内の特定のセルに対するタイミング条件を有するタイミング条件データファイルDF4と，セル配置プログラムP1により配置されたセルの配置（位置）データを有するセル配置データファイルDF3とを有する。更に，データファイルは，配置されたセルに対してグローバル配線プログラムP2により形成された概略的な配線データを含むグローバル配線データファイルDF5と，クロックツリー生成プログラムP3により生成されたクロックツリーデータファイルDF6と，オプティマイズプログラムP4により生成されたオプティマイズデータファイルDF7とを有する。
【００２３】
上記のデータファイルのうち，データファイルDF1，DF2，DF4は，レイアウト工程の前に生成され，それ以外のデータファイルは本レイアウト装置により生成される。
【００２４】
レイアウト装置のプログラムは，上述のプログラム以外に，チップ内の配線の混雑度を求めて基準値レベルを超えているか否かを解析する混雑度解析プログラムP5と，混雑度が基準値レベルを超えている小領域内においてセルの再配置を行うセル再配置プログラムP6とを有する。この２つのプログラムにより，詳細配線処理において配線不能結果になる可能性を少なくすることができる。そして，レイアウト装置のプログラムには，自動配置されタイミングを最適化された複数のセルに対して，接続配線を自動生成する詳細配線プログラムP7が含まれる。グローバル配線プログラムと詳細配線プログラムの違いについては，後に詳述する。
【００２５】
図５のレイアウト方法のフローチャートにしたがって説明する。チップ内にセルを配置してその間の接続配線を生成するレイアウト工程は，ＬＳＩの目的とする機能を実現するための論理回路デザインの後で行われる。論理デザインが終了した段階で，セルとその接続データを含むネットリストDF2が生成される。
【００２６】
レイアウト工程では，最初にネットリストにしたがって，チップ内にセルの初期配置が行われる（Ｓ１０）。このセル配置処理は，ＬＳＩの高速性を考慮して，入力信号やクロックのタイミング条件を優先してセルを自動配置する。タイミング条件を優先してセル配置することで，その後の論理シミュレーションでフェイル結果に至る可能性を低くすることができる。そのために，オペレータは，入力信号やクロックのタイミング制約が厳しいセルに対して，どの信号またはクロックについて，どのようなタイミングの制約があるかを示すタイミング条件データファイルDF4を生成する。従って，セル配置処理Ｓ１０は，ネットリストDF2とタイミング条件DF4とにしたがって行われ，その結果セルの配置データ（位置データ）を有するセル配置データファイルDF3が生成される。この自動セル配置により，図１に示したような一部でセルが密集した状態のセル配置が生成される。
【００２７】
次に，レイアウト装置は，ネットリストDF2とセル配置データファイルDF3とを参照して，グローバル配線処理を行う（Ｓ１２）。グローバル配線処理Ｓ１２は，チップの入出力端子や複数のセル間の接続配線を，一部短絡を許容しながら生成する処理である。接続配線の条件が緩和されているので，比較的短いコンピュータ演算時間で処理することができる。それに対して，後に行われる詳細配線処理Ｓ３０は，チップ入出力端子や複数のセル間の接続配線を，いっさいの短絡を許容せずに生成する処理である。従って，詳細配線処理は，前述のとおり比較的長いコンピュータ演算時間を要する処理である。
【００２８】
図６は，詳細配線プログラムのフローチャート図である。詳細配線処理では，入出力端子やセルの接続すべき２つのピン（接続端子）の間において，配線の形成が許可されるグリッド上の最短配線ルートを検出する（Ｓ４０）。そして，その検出した配線が，グリッド上にすでに生成されている既配線と重なるか否かがチェックされる（Ｓ４２）。検出した配線が既配線と重なる場合は，配線短絡を招くので，異なる配線ルートが検出される（Ｓ４４）。そして，その新たに検出された配線が既配線と重なるか否かがチェックされる（Ｓ４２）。このように，検出した配線が既配線と重ならないことが確認されるまで，処理Ｓ４２とＳ４４が繰り返される。上記の処理が全ての接続すべき配線ルートに対して終了すると（Ｓ４６），詳細配線処理は完了する。
【００２９】
従って，詳細配線処理では，その配線ルート検出アルゴリズムに従って，短絡のない全ての配線を生成する必要があり，比較的長いコンピュータ演算時間を要する。
【００３０】
それに対して，グローバル配線処理（概略配線処理）では，既配線との短絡禁止条件が詳細配線処理に比較すると緩やかになっており，比較的短いコンピュータ演算時間で行うことができる。
【００３１】
図７は，グローバル配線プログラムのフローチャート図である。図７には２種類のフローチャートＡ，Ｂが示される。ここに示したフローチャートは，図６の詳細配線プログラムのフローチャートとは工程番号S42G，S44Gが異なるのみである。即ち，フローチャートＡでは，工程S42Gにて検出した配線が既配線と１回まで重なることを許可する。従って，グリッド上に形成される配線は，２重に重なることは許容されるが，３重に重なることは禁止される。このように，配線短絡の条件が緩和されているので，チップ内の配線の生成に必要なコンピュータ演算時間は，詳細配線プログラムよりも短くなる。
【００３２】
フローチャートＢでは，最初に２つのピン間のグリッド上の最短配線ルートが既配線と重なっている場合に，異なる配線ルートを検出したら（Ｓ４４），再度既配線との重なりをチェックすることなく，無条件でその異なる配線ルートを採用する（図中Ｓ44G）。従って，この場合も，グリッド上で複数の配線が重なることが許容されるので，配線生成に必要なコンピュータ演算時間は，詳細配線プログラムよりも短くなる。
【００３３】
上記のフローチャートは，配線ルート探索アルゴリズムを概略的に説明したものである。より詳細に説明すれば，例えば，配線ルートは，水平方向の配線と垂直方向の配線とそれらを接続するビアホールとにより構成されるのが一般的であり，一方の接続端子から出発して，最初に垂直方向の配線を検出し，ビアホールを介して次の水平方向の配線を検出し，既存の配線と短絡する場合はそれを避けるようにして別の方向の配線を検出するなどして，他方の接続端子に達する，というアルゴリズムが考えられる。その場合でも，上記のように既存配線との重なりをある程度許容することにより，グローバル配線処理は，短時間で完了することができる。配線ルート探索アルゴリズムは，例えばケイデンス社製の「Silicon Ensemble」に含まれている配線ルート探索ツールにより当業者に知られているので，詳細な説明は省略する。
【００３４】
図５に戻り，グローバル配線処理によりチップ内に配置されたセル間の概略的な配線が生成される。その結果は，グローバル配線データファイルDF5として記録される。このグローバル配線は，一部に配線短絡を含むが，その後のタイミングの最適化処理や配線の混雑度解析には十分利用できる。
【００３５】
次に，クロックツリーの生成処理が行われる（Ｓ１４）。クロックツリーとは，あるクロックが複数のセルに並列に供給される場合，複数のセルに対して同じタイミングで供給できるようにしたクロック供給配線である。この場合のクロック供給配線は一般的にツリー形状であり，供給タイミングをそろえるために，クロック供給配線内にバッファなどを挿入してその伝播遅延時間を同程度にする処理が行われる。
【００３６】
図８は，クロックツリー生成例を示す回路図である。図８（Ａ）に示された回路図は，２入力IN0,IN1のANDゲート３０と，その出力OUTがそれぞれデータ入力として供給される２つのフリップフロップFF1,FF2とからなり，２つのフリップフロップのクロック端子には，共通のクロックCLKがクロック供給端子L0,L1を介してそれぞれ供給される。クロック供給配線は，クロック入力端子から分岐点n1を介して，２つの配線L0,L1に分かれて，それぞれのフリップフロップのクロック端子に接続される。つまり，ツリー形状である。
【００３７】
このような回路の場合，ANDゲートの出力OUTはほぼ同じタイミングで２つのフリップフロップのデータ端子Ｄに供給されるので，それらのクロック端子CKへのクロックCLKの入力タイミングをほぼ同じタイミングにそろえる必要がある。ところが，配線L0は配線L1に比較して分岐ノードn1からの距離が長いので，クロック信号伝播時間が長くなり，２つのフリップフロップFF0,FF1間で，クロックのスキューが発生し，誤動作を招くおそれがある。
【００３８】
そこで，クロックツリー生成処理では，図８（Ｂ）に示されるように，第２のクロック供給配線Ｌ１にバッファ３２を挿入し，２つのフリップフロップFF1,FF2へのクロック入力タイミングをそろえることが行われる。即ち，クロックツリー生成処理では，セル配置処理Ｓ１０によりタイミングを優先したセルの配置が行われた後に，その配置に対してクロックのタイミングの最適化を行うものである。クロックツリー生成処理の結果，クロックツリーデータファイルDF6が生成される。
【００３９】
次に，図５に示されるとおり，インプレースオプティマイズ処理が行われる（Ｓ１６）。この最適化処理は，タイミング優先で配置された複数のセルに対して，セル間の信号のタイミングを最適化するために，配線を駆動するセルを異なる駆動能力のセルに置き換えたり，セルの遅延時間が異なるセルに置き換えたり，セルの入力容量が異なるセルに置き換えたり，配線内にバッファを挿入したり削除したりして信号伝播時間の最適化を図る処理である。
【００４０】
図９は，インプレースオプティマイズ処理の例を示す図である。図９（Ａ）の回路例では，２入力のANDゲート３０の出力OUTが２つのフリップフロップFF1,FF2とそれ以外の図示しない回路にも供給されている。そして，セル配置の結果，ANDゲート３０とフリップフロップFF1との間の配線L10に比較して，フリップフロップFF2への配線L11がかなり長くなっており，更に図示しない回路への配線L12,L13,L14も長くなっている。
【００４１】
その結果，第１に，ANDゲート３０の駆動能力に対して，配線L10〜L14の駆動負荷が大きくなり，ANDゲート３０の駆動能力不足が判明し，更に，配線L10の信号伝播時間が他の配線L11〜L14に比較して短すぎることが判明する。
【００４２】
そこで，図９（Ｂ）に示されるように，セルを配置した状態（インプレース）での最適化処理により，第１に，ANDゲートをより駆動能力の大きいANDゲート30Xに置き換えて駆動能力不足を解消し，第２に，短い配線L10内にバッファ３４を挿入して伝播時間を長くし，複数の配線L10〜L14の信号伝播時間をそろえることが行われる。つまり，論理回路設計の段階では判明しなかったセル配置に伴う修正が，この最適化処理により行われる。インプレースオプティマイズ処理の結果，オプティマイズデータファイルDF7が生成される。
【００４３】
上記のクロックツリー生成処理Ｓ１４やインプレースオプティマイズ処理Ｓ１６の結果，新たなバッファが生成され，セルの置き換えが行われる。従って，それらの処理の後はそれぞれグローバル配線生成処理が行われる。
【００４４】
次に，配線混雑度解析処理が行われる（Ｓ１８）。この配線混雑度解析処理は従来のレイアウトツールにない新たな処理である。本実施の形態では，セル配置とその最適化処理の後，詳細配線処理をする前に，詳細配線処理で配線不能になる可能性を予測するために，配線の混雑度を解析する。
【００４５】
配線の混雑度解析では，チップ内を複数の小領域に分割し，その小領域内での混雑度を求める。複数の小領域への分割は，図２にて示した通りである。配線混雑度は，種々の考え方があるが，例えば，（１）小領域内のセル面積を小領域面積で除したセル面積密度，（２）小領域内のセルの接続ピン数を小領域面積で除した接続ピン密度，（３）小領域内の配線総数（水平方向と垂直方向）をグリッド数で除した配線占有率，（４）小領域内を通過する配線数，（５）小領域内の配線総数を接続ピン総数で除した値などが考えられる。
【００４６】
上記（１）のセル面積密度と（２）の接続ピン密度は，間接的に配線の混雑度を示すものであり，簡単な演算により求めることができる。また，（３）の配線占有率は，より直接的な配線混雑度に関するものであるが，グローバル配線により生成された配線に基づくものであり必ずしも混雑度を直接示すものでもない。（４）の通過配線数は，通過配線数が多くなると，小領域内のセルの配線が困難になり配線混雑度の目安になる。そして，（５）の値は接続ピンあたりの配線数であり，例えば出力ピンに対するファンアウト数が多かったり，通過配線数が多かったりすると配線が困難になり配線混雑度の目安になる。
【００４７】
図１０は，配線混雑度を説明する図である。比較のために，図１０（Ａ）に配線混雑度が低いセルレイアウト例を，図１０（Ｂ）に配線混雑度が高いセルレイアウト例をそれぞれ示す。図１０（Ａ）のセルレイアウト例では，２つの小領域DSR10,11内に，それぞれセルCEL10〜12とCEL13〜16とが配置される。一方，図１０（Ｂ）のセルレイアウト例では，２つの小領域DSR12,13内に，それぞれセルCEL20〜23とCEL24〜27とが配置される。
【００４８】
小領域DSR10とDSR12とを比較すると，小領域DSR10内には３つのセルしか配置されず，それぞれのセルは左辺に２つずつの入力端子と右辺に１つずつの出力端子を有するのみである。それに対して，小領域DSR12内には，４つのセルが配置されていて，それぞれのセルは左辺に３つずつの入力端子と右辺に１つずつの出力端子を有する。従って，上記の配線混雑度のうち，（１）セル面積密度と（２）接続ピン密度とに関する混雑度については，小領域DSR12のほうがDSR10よりも高くなる。
【００４９】
次に，小領域DSR11とDSR13とを比較すると，小領域DSR11内のセルCEL13〜16は全て出力端子のファンアウト数は「１」であり，小領域内を通過する配線はない。それに対して，小領域DSR13内のセルCEL24〜27は出力のファンアウト数が全て「２」であり，小領域内を通過する配線PL1,PL2が存在する。
【００５０】
従って，両小領域DSR11,13について，上記（１）セル面積密度と（２）接続ピン密度については同じであるが，上記（４）通過配線数と（５）接続ピン当たりの配線数については，小領域DSR13のほうが高いレベルになる。このように，小領域内に同じセル数，接続ピン数が含まれても，出力ピンのファンアウト数が多かったり，外部からの通過配線が多かったりすると，配線の混雑度が高くなり，詳細配線処理では配線不能の可能性がある。
【００５１】
上記以外にも配線混雑度に関連する値があるが，適宜採用することができる。配線混雑度解析処理Ｓ１８では，ネットリストDF2と，セル配置データDF3と，クロックツリーデータDF6と，オプティマイズデータDF7と，グローバル配線DF5に従って，上記の混雑度に関連する値を小領域毎に求め，基準レベルに応じて，混雑度マップが表示出力される。例えば，図２に示したように，小領域DSR3が混雑度大と表示され，セルの再配置対象の小領域に指定される。
【００５２】
配線可能な混雑度でない場合は（Ｓ２０），混雑度が高い小領域内でのセルの再配置処理が行われる（Ｓ２６）。このセルの再配置処理では，第１に，小領域内に限定して行われるので，チップ全体のセル再配置処理に比較して，チップ全体のセルのタイミング最適化状態をよりそのままに維持することができる。第２に，小領域内でのセル再配置では，セル間の位置関係を維持しながら行うという制約を課すことにより，小領域内のセルのタイミング最適化状態も，よりそのままに維持することができる。セルの再配置処理については，後に詳述する。
【００５３】
混雑度が高い小領域内に限定してセルの再配置を行った後，再度クロックツリー生成処理が行われる（Ｓ２８）。セルの位置が変更されることにより，タイミング最適化に大切なクロックツリーが再度最適化される。そして，再度配線可能な混雑度か否かが判断され（Ｓ２０），配線可能と判断されれば，詳細配線処理Ｓ３０に移行する。
【００５４】
別の好ましい実施の形態では，図５中に破線で示されるとおり，再度配線可能な混雑度か否か判断することなく，セルの再配置後に詳細配線処理Ｓ３０を行っても良い。その場合，少なくとも配線不能になりそうな小領域内においてセルの再配置を行っているので，従来の方法よりも詳細配線処理で配線不能になる可能性は低くなる。従って，従来例のようにセルの初期配置処理と詳細配線処理をやり直すという可能性は低くなる。
【００５５】
別の好ましい実施の形態では，一旦セルの再配置をおこなった後に，再度配線可能な混雑度になっていないと判断された場合は，再配置対象の小領域を拡大して，再度セルの再配置処理を行う（Ｓ２２，Ｓ２４）。再配置処理の対象領域を大きくすることで，より自由度の高い再配置処理が行えるので，小領域内の配線混雑度を緩和することができる。
【００５６】
次に，セルの再配置処理について説明する。図１１，１２は，セルの再配置において，セル列内における隣接セル間の間隔を拡げる方法を説明する図である。図１１（Ａ）は，セル列2A内に３つのセルCEL30〜32が配置され，別のセル列2Bにもそれらに近接してセルCEL33が配置されている。この場合，図１１（Ｂ）に示すとおり，セル列2A内の隣接する３つのセルCEL30〜32の間隔４０，４１を設けて，そこを通過する配線４５，４６が形成できるようにする。このようなセルの再配置処理では，セルCEL30〜32の相対的な位置関係は維持されながら，わずかな間隔４０，４１を設けるという処理を行うのみである。このような再配置であれば，セルのタイミングが最適化された状態を維持することができる。
【００５７】
図１２には，より具体的に示される。この例では，図１２（Ａ）に示されるように，セルCEL30内に３つの端子が存在し，その一つの端子４２がセルCEL33の端子４４と接続する必要があるとすると，図中破線で示す方向に配線を形成する必要がある。配線は，水平方向の１層目の配線層ＬＩと垂直方向の２層目の配線層ＬＩＩとで構成されるが，セルCE30では垂直方向の２層目の配線層ＬＩＩ内にセルCEL33方向の配線可能なグリッドがないので，端子４２，４４間を接続することができない。
【００５８】
そこで，図１２（Ｂ）のようにセル間隔４０を形成することで，新たに配線が通過できるグリッドが増加し，図１２（Ｃ）に示されるように，端子４２，４４間を接続する２層目の配線４５を形成することができるようになる。このように，セル間隔を設けることで配線不能状態が配線可能状態に変わる。しかも，セル間隔を設けることで，セルのタイミング最適化状態に支障がでる可能性は少なくなる。
【００５９】
図１３は，セルの再配置において，セル列の間隔を生成する方法を説明する図である。図１３（Ａ）では，セル列2A，2Bの間にチャネル領域がなく，セル列2Bと2Cとの間にチャネル領域3Aが存在する例である。そして，セル列2A,2Bの左端には，４個ずつのセルが密集して配置されている。このようなセル配置に対して，セルの再配置処理では，図１３（Ｂ）に示すとおり，セル列2Aと2Bとの間に新たな間隔3Bを設けるようにする。その結果，間隔3Bに新たに配線を形成できるグリッドが発生し，配線を形成することが可能になる。つまり，新たな配線領域を確保して，詳細配線での配線不能の可能性を低くしている。
【００６０】
図１４は，セルの再配置において，隣接するセルの位置を上下或いは左右，斜め方向，回転方向に入れ替える方法を説明する図である。図１４（Ａ）に示されるとおり，隣接するセル列2A,2B内にセルCEL40,41及びCEL42,43が配置されている。そして，これらの４個のセルの塊の両側に，配線領域５０，５１が確保されている。しかしながら，セルCEL40,43は，それぞれ２端子ずつしか有していないが，セルCEL41,42は，それぞれ４端子ずつ有している。従って，配線領域５０には合計で８端子に接続される配線を設ける必要があり，場合によっては配線不能状態になる。
【００６１】
そこで，図１４（Ｂ）に示す通り，４つのセルCEL40〜43を反時計回りに移動して，配線領域５１には，２端子のセルCLE40と４端子のセルCLE41とが並び，配線領域５０にも，２端子のセルCEL43と４端子のセルCEL42とが並ぶように再配置する。このようにセルを再配置することで，配線領域５０に必要な配線数が６本と緩和され，配線不能状態を回避することができる。しかも，隣接するセルの位置を入れ替えるだけであるので，タイミングを優先して配置したセルの相対的な位置関係を維持することができる。つまり，セルCEL40〜43は，再配置後も全て同等の位置を維持することができるので，セルのタイミング最適化された状態を維持することができる。
【００６２】
上記の再配置例において，４つのセルを時計回りに移動しても良いし，セルCEL40とCEL41とを入れ替えることでも，同様に配線の混雑を緩和することができる。
【００６３】
図１５は，セルの再配置において，セルの方向を反転する方法を説明する図である。図１５（Ａ）の例では，セル列内にセルCEL50〜53が配置されている。そして，セルCEL50〜52はそれぞれ４つの端子を有し，セルCEL53のみが２つの端子しか有しない。セル51,52,53の原点OR1,2,3は全て左側に位置している。その結果，セルCEL51，CEL52において接続ピンが密集して配線不能になる可能性がある。
【００６４】
そこで，セルの再配置において，図１５（Ｂ）に示されるように，セルCEL52の方向を反転して，その原点OR2が右側になるように再配置する。その結果，セルCEL52の端子位置（接続ピン位置）が右側になり，セルCEL51での端子密度が緩和されて，配線不能の可能性を少なくすることができる。そして，単にセルCEL52の方向が変わっただけであるので，セルの相対位置に変更はなく，セルのタイミング最適化状態が維持される。
【００６５】
図１６は，セルの再配置において，同じ論理回路及び電気特性を有し端子位置が異なるセルに置き換える方法を説明する図である。図１６（Ａ）の例では，セルCEL60,61が隣接して配置され，更にセルCEL60は２つの接続端子が右辺中央に位置し，セルCEL61は２つの接続端子が左辺中央に位置している。つまり，接続端子が接続領域６２，６３を隔てた位置に集中している。かかる状況では，接続配線が不可能になる可能性がある。
【００６６】
そこで，セルの再配置処理では，図１６（Ｂ）に示されるように，セルCEL60，CEL61と同じ論理回路を有し，出力駆動能力や入出力レベルなどの電気的特性が同等であって，接続端子位置が異なるセルCEL60A，CEL61Aに置き換える。これらのセルCEL60A，CEL61Aは，セルライブラリ内に登録された元のセルCEL60，CEL61に代替え可能なセルである。その結果，両セルCEL60A，CEL61Aの接続端子は，接続領域６２，６３側に位置することになり，また，集中度も緩和されて，配線不可能になる可能性を低くすることができる。しかも，セルの位置に変更はないので，セルのタイミング最適状態を維持することもできる。
【００６７】
以上，６種類のセル再配置方法の例を説明した。これらの再配置は，配線の混雑度が高いことが予想される小領域内に限定して行われる。しかも，セル間の相対的位置関係が維持され，或いはセルの位置の微少変更に止められ，タイミングを優先してセル配置し（S10），クロックツリー生成（S14）とインプレースオプティマイズ処理（S16）した結果生成されたセルのタイミング最適化状態を維持することができる。従って，上記のセルの再配置処理により，最初のセル配置とその後の最適化処理を無駄にすることなく，その後の詳細配線処理での配線不可能の可能性を低くすることができる。しかも，セルの再配置処理は，混雑度の高い小領域内に限られているので，全体のセルの配置状態が維持されると共に，再配置処理の対象セル数が少なくコンピュータの処理時間は短い。
【００６８】
また，上記以外にも，セルのタイミング状態を維持したままセルの再配置を行う方法があるが，いずれの方法でも，セル間の相対的位置を維持し，或いはセルの位置の微少変更のみにすることで，セルの最適化されたタイミング状態を維持することができる。
【００６９】
以上説明したＬＳＩのレイアウト方法は，図４に示すレイアウトプログラムツールを有するコンピュータ装置により行うことができる。尚，各レイアウトプログラムツールは，記録媒体に記憶されている。
【００７０】
以上，実施の形態例をまとめると以下の付記の通りである。
【００７１】
（付記１）複数のセルを有するＬＳＩのレイアウト方法において，
複数のセルとその接続データを有するネットリストとセルのタイミング条件データに基づいてチップ内にセルの自動配置を行うセル配置処理工程と，
前記セル間を接続する配線を，配線間の短絡条件を緩和して生成するグローバル配線処理工程と，
前記自動配置されたセル間を接続する配線の信号伝播時間に応じて最適化するタイミング最適化処理工程と，
前記配線の混雑度を求め，当該混雑度が基準レベルより高い領域を検出する混雑度解析処理工程と，
前記チップを複数に分割した小領域であって，当該混雑度が基準レベルより高い小領域内で，前記セルの再配置処理を行うセル再配置処理工程と，
前記セル再配置処理の後で，セル間を接続する配線を，配線間の短絡を禁止して生成する詳細配線処理工程とを有することを特徴とするＬＳＩのレイアウト方法。
【００７２】
（付記２）付記１において，
前記セルの配置処理後であって，前記セルの再配置処理の前に，配置されたセルに対してクロックツリーを生成するクロックツリー生成工程を有することを特徴とするＬＳＩのレイアウト方法。
【００７３】
（付記３）付記２において，
前記セルの再配置処理の後で，再度クロックツリー生成工程を実行することを特徴とするＬＳＩのレイアウト方法。
【００７４】
（付記４）付記１において，
前記セルの再配置処理工程は，隣接する複数のセル間またはセル列間の間隔を拡げる処理であることを特徴とするＬＳＩのレイアウト方法。
【００７５】
（付記５）付記１において，
前記セルの再配置処理工程は，隣接する複数のセルの左右，上下，斜め，回転方向のいずれかに入れ替える処理であることを特徴とするＬＳＩのレイアウト方法。
【００７６】
（付記６）付記１において，
前記セルの再配置処理工程は，セルの方向を反転する処理であることを特徴とするＬＳＩのレイアウト方法。
【００７７】
（付記７）付記１において，
前記セルの再配置処理工程は，セルを論理特性が同じであって接続ピンの位置が異なる別のセルに置き換える処理であることを特徴とするＬＳＩのレイアウト方法。
【００７８】
（付記８）付記１において，
前記セルの再配置処理は，セルのタイミング関係を維持しながら行われることを特徴とするＬＳＩのレイアウト方法。
【００７９】
（付記９）付記１において，
前記配線の混雑度解析工程は，前記小領域内のセルの総面積，セルの接続ピン総数，接続配線総数，通過配線総数の少なくとも一つに応じて前記混雑度を決定することを特徴とするＬＳＩのレイアウト方法。
【００８０】
（付記１０）付記１において，
前記配線の混雑度解析工程は，前記小領域内の接続配線総数をピン総数で除した値に応じて前記混雑度を決定することを特徴とするＬＳＩのレイアウト方法。
【００８１】
（付記１１）付記１において，
前記タイミング最適化処理は，セルの出力駆動能力，セルの遅延時間，セルの入力負荷容量の少なくとも１つが異なるセルに置き換え，またはセル間を接続する配線内にバッファを追加し，又はセル間を接続する配線内のバッファを削除する処理の少なくとも一つを行うことを特徴とするＬＳＩのレイアウト方法。
【００８２】
（付記１２）付記１において，
前記セルの再配置処理後に，再度配線の混雑度解析を行い，基準レベルを超えていない場合に，前記詳細配線処理を行うことを特徴とするＬＳＩのレイアウト方法。
【００８３】
（付記１３）付記１２において，
前記セルの再配置処理後の混雑度解析の結果，基準レベルを超えている領域が存在する場合は，前記小領域のサイズを大きくして再度セルの再配置処理を行うことを特徴とするＬＳＩのレイアウト方法。
【００８４】
（付記１４）複数のセルを有するＬＳＩのレイアウトを行うレイアウト装置において，
複数のセルとその接続データを有するネットリストとセルのタイミング条件データに基づいてチップ内にセルの自動配置を行う自動配置手段と，
前記セル間を接続する配線を，配線間の短絡条件を緩和して生成するグローバル配線処理手段と，
前記自動配置されたセル間を接続する配線の信号伝播時間に応じて最適化するタイミング最適化処理手段と，
前記配線の混雑度を求め，当該混雑度が基準レベルより高い領域を検出する混雑度解析処理手段と，
前記チップを複数に分割した小領域であって，当該混雑度が基準レベルより高い小領域内で，前記セルの再配置処理を行うセル再配置処理手段と，
前記セル再配置処理の後で，セル間を接続する配線を，配線間の短絡を禁止して生成する詳細配線処理手段とを有することを特徴とするＬＳＩのレイアウト装置。
【００８５】
（付記１５）付記１４において，
前記セルの配置処理後であって，前記セルの再配置処理の前に，配置されたセルに対してクロックツリーを生成するクロックツリー生成手段を有することを特徴とするＬＳＩのレイアウト装置。
【００８６】
（付記１６）付記１５において，
前記セルの再配置処理の後で，再度クロックツリー生成を行うことを特徴とするＬＳＩのレイアウト装置。
【００８７】
（付記１７）付記１６において，
前記セルの再配置処理手段は，セルのタイミング関係を維持しながら行われることを特徴とするＬＳＩのレイアウト装置。
【００８８】
（付記１８）複数のセルを有するＬＳＩのレイアウトをコンピュータに実行させるレイアウトプログラムにおいて，
複数のセルとその接続データを有するネットリストとセルのタイミング条件データに基づいてチップ内にセルの自動配置を行う自動セル配置プログラムと，
前記セル間を接続する配線を，配線間の短絡条件を緩和して生成するグローバル配線処理プログラムと，
前記自動配置されたセル間を接続する配線の信号伝播時間に応じて最適化するタイミング最適化処理プログラムと，
前記配線の混雑度を求め，当該混雑度が基準レベルより高い領域を検出する混雑度解析処理プログラムと，
前記チップを複数に分割した小領域であって，当該混雑度が基準レベルより高い小領域内で，前記セルの再配置処理を行うセル再配置処理プログラムと，
前記セル再配置処理の後で，セル間を接続する配線を，配線間の短絡を禁止して生成する詳細配線処理プログラムとを有することを特徴とするＬＳＩのレイアウトプログラム。
【００８９】
【発明の効果】
以上，本発明によれば，タイミングを優先してセルの自動配置を行い，そのタイミングの最適化処理を行ってから，配線の混雑度の高い領域にセルの再配置処理を行うので，その後の詳細配線処理において，配線不能になる可能性を低く抑えることができる。従って，改めてセルの自動配置処理と詳細配線処理というコンピュータ処理時間が長い処理を繰り返す必要が少なくなる。
【図面の簡単な説明】
【図１】本発明にかかる実施の形態のレイアウト方法を概略的に説明する図である。
【図２】本発明にかかる実施の形態のレイアウト方法を概略的に説明する図である。
【図３】本発明にかかる実施の形態のレイアウト方法を概略的に説明する図である。
【図４】本実施の形態例におけるレイアウト装置の構成図である。
【図５】本実施の形態例におけるレイアウト方法のフローチャート図である。
【図６】詳細配線プログラムのフローチャート図である。
【図７】グローバル配線プログラムのフローチャート図である。
【図８】クロックツリー生成例を示す回路図である。
【図９】インプレースオプティマイズ処理の例を示す図である。
【図１０】配線混雑度を説明する図である。
【図１１】セルの再配置において，セル列内における隣接セル間の間隔を拡げる方法を説明する図である。
【図１２】セルの再配置において，セル列内における隣接セル間の間隔を拡げる方法を説明する図である。
【図１３】セルの再配置において，セル列の間隔を生成する方法を説明する図である。
【図１４】セルの再配置において，隣接するセルの位置を上下或いは左右に入れ替える方法を説明する図である。
【図１５】セルの再配置において，セルの方向を反転する方法を説明する図である。
【図１６】セルの再配置において，同じ論理回路及び電気特性を有し端子位置が異なるセルに置き換える方法を説明する図である。
【符号の説明】
１ チップ
２ セルアレイ，セル列
３ チャネル領域
CEL セル
DSR 小領域
Claims (9)
- 複数のセルを有するＬＳＩのレイアウト方法において，
演算処理装置が，複数のセルとその接続データを有するネットリストとセルのタイミング条件データに基づいてチップ内にセルの自動配置を行うセル配置処理工程と，
演算処理装置が，前記セル間を接続する配線を，配線間の短絡条件を緩和して生成するグローバル配線処理工程と，
演算処理装置が，前記自動配置されたセル間を接続する配線の信号伝播時間に応じて最適化するタイミング最適化処理工程と，
演算処理装置が，前記配線の混雑度を求め，当該混雑度が基準レベルより高い領域を検出する混雑度解析処理工程と，
演算処理装置が，前記チップを複数に分割した小領域であって，当該混雑度が基準レベルより高い小領域内で，前記セルの再配置処理を行うセル再配置処理工程と，
演算処理装置が，前記セル再配置処理の後で，セル間を接続する配線を，配線間の短絡を禁止して生成する詳細配線処理工程とを有し，
演算処理装置が，前記セルの再配置処理後に再度配線の混雑度解析を行い，基準レベルを超えていない場合に前記詳細配線処理を行い，基準レベルを超えている領域が存在する場合は，前記小領域のサイズを大きくして再度セルの再配置処理を行うことを特徴とするＬＳＩのレイアウト方法。 - 請求項１において，
前記セルの配置処理後であって，前記セルの再配置処理の前に，配置されたセルに対してクロックツリーを生成するクロックツリー生成工程を有することを特徴とするＬＳＩのレイアウト方法。 - 請求項２において，
前記セルの再配置処理の後で，再度クロックツリー生成工程を実行することを特徴とするＬＳＩのレイアウト方法。 - 請求項１において，
前記セルの再配置処理工程は，隣接する複数のセル間またはセル列間の間隔を拡げる処理であることを特徴とするＬＳＩのレイアウト方法。 - 請求項１において，
前記セルの再配置処理工程は，隣接する複数のセルの左右，上下，斜め，回転方向のいずれかに入れ替える処理であることを特徴とするＬＳＩのレイアウト方法。 - 請求項１において，
前記セルの再配置処理工程は，セルの方向を反転する処理であることを特徴とするＬＳＩのレイアウト方法。 - 請求項１において，
前記セルの再配置処理工程は，セルを論理特性が同じであって接続ピンの位置が異なる別のセルに置き換える処理であることを特徴とするＬＳＩのレイアウト方法。 - 請求項１において，
前記タイミング最適化処理は，セルの出力駆動能力，セルの遅延時間，セルの入力負荷容量の少なくとも１つが異なるセルに置き換え，またはセル間を接続する配線内にバッファを追加し，又はセル間を接続する配線内のバッファを削除する処理の少なくとも一つを行うことを特徴とするＬＳＩのレイアウト方法。 - 複数のセルを有するＬＳＩのレイアウトを行うレイアウト装置において，
複数のセルとその接続データを有するネットリストとセルのタイミング条件データに基づいてチップ内にセルの自動配置を行う自動配置手段と，
前記セル間を接続する配線を，配線間の短絡条件を緩和して生成するグローバル配線処理手段と，
前記自動配置されたセル間を接続する配線の信号伝播時間に応じて最適化するタイミング最適化処理手段と，
前記配線の混雑度を求め，当該混雑度が基準レベルより高い領域を検出する混雑度解析処理手段と，
前記チップを複数に分割した小領域であって，当該混雑度が基準レベルより高い小領域内で，前記セルの再配置処理を行うセル再配置処理手段と，
前記セル再配置処理の後で，セル間を接続する配線を，配線間の短絡を禁止して生成する詳細配線処理手段とを有し，
前記混雑度解析処理手段が前記セルの再配置処理後に再度配線の混雑度解析を行い，基準レベルを超えていない場合に，前記詳細配線処理手段が前記詳細配線処理を行い，基準レベルを超えている領域が存在する場合は，前記セル再配置処理手段が前記小領域のサイズを大きくして再度セルの再配置処理を行うことを特徴とするＬＳＩのレイアウト装置。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001228373A JP4953526B2 (ja) | 2001-07-27 | 2001-07-27 | タイミング優先でセル配置するｌｓｉのレイアウト方法及びその装置 |
| US10/079,545 US6857107B2 (en) | 2001-07-27 | 2002-02-22 | LSI layout method and apparatus for cell arrangement in which timing is prioritized |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001228373A JP4953526B2 (ja) | 2001-07-27 | 2001-07-27 | タイミング優先でセル配置するｌｓｉのレイアウト方法及びその装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2003044536A JP2003044536A (ja) | 2003-02-14 |
| JP4953526B2 true JP4953526B2 (ja) | 2012-06-13 |
Family
ID=19060891
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001228373A Expired - Fee Related JP4953526B2 (ja) | 2001-07-27 | 2001-07-27 | タイミング優先でセル配置するｌｓｉのレイアウト方法及びその装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US6857107B2 (ja) |
| JP (1) | JP4953526B2 (ja) |
Families Citing this family (24)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7454735B2 (en) * | 2002-12-17 | 2008-11-18 | International Business Machines Corporation | ASIC clock floor planning method and structure |
| US7107551B1 (en) * | 2003-05-30 | 2006-09-12 | Prolific, Inc. | Optimization of circuit designs using a continuous spectrum of library cells |
| JP4204444B2 (ja) * | 2003-11-04 | 2009-01-07 | パナソニック株式会社 | 半導体集積回路の設計方法 |
| JP4053969B2 (ja) * | 2003-11-28 | 2008-02-27 | 沖電気工業株式会社 | 半導体集積回路の設計装置および半導体集積回路の設計方法 |
| DE102004038063A1 (de) * | 2004-07-30 | 2006-03-23 | Infineon Technologies Ag | Verfahren zur Herstellung einer Standardzellenanordnung und eine Vorrichtung zur Durchführung des Verfahrens |
| US7721232B2 (en) * | 2004-11-29 | 2010-05-18 | Infineon Technologies Ag | Designated MOSFET and driver design to achieve lowest parasitics in discrete circuits |
| JP4587878B2 (ja) * | 2005-06-02 | 2010-11-24 | Ｏｋｉセミコンダクタ株式会社 | 半導体装置の自動設計方法および自動設計装置 |
| JP2007026170A (ja) * | 2005-07-19 | 2007-02-01 | Matsushita Electric Ind Co Ltd | 半導体集積回路の自動レイアウト方法、自動レイアウトプログラム、および自動レイアウト装置 |
| US7657859B2 (en) * | 2005-12-08 | 2010-02-02 | International Business Machines Corporation | Method for IC wiring yield optimization, including wire widening during and after routing |
| JP2008009871A (ja) * | 2006-06-30 | 2008-01-17 | Fujitsu Ltd | セル配置方法 |
| JP2008090456A (ja) * | 2006-09-29 | 2008-04-17 | Ricoh Co Ltd | 自動配置配線装置、自動配置配線方法、自動配置配線プログラム、半導体集積回路 |
| JP2008311454A (ja) * | 2007-06-15 | 2008-12-25 | Fujitsu Microelectronics Ltd | 半導体集積回路のレイアウト設計方法およびレイアウト設計プログラム |
| US8037441B2 (en) * | 2007-09-25 | 2011-10-11 | International Business Machines Corporation | Gridded-router based wiring on a non-gridded library |
| JP5262065B2 (ja) * | 2007-10-31 | 2013-08-14 | 富士通株式会社 | レイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法 |
| US8104014B2 (en) * | 2008-01-30 | 2012-01-24 | International Business Machines Corporation | Regular local clock buffer placement and latch clustering by iterative optimization |
| JP2010033493A (ja) * | 2008-07-31 | 2010-02-12 | Sony Corp | レイアウト配線混雑予測装置およびその方法、並びにプログラム |
| US7971174B1 (en) * | 2008-09-18 | 2011-06-28 | Cadence Design Systems, Inc. | Congestion aware pin optimizer |
| JP2010146047A (ja) * | 2008-12-16 | 2010-07-01 | Renesas Electronics Corp | バッファ回路挿入方法、バッファ回路挿入装置及びバッファ回路挿入プログラム |
| US8225262B1 (en) * | 2009-03-18 | 2012-07-17 | Xilinx, Inc. | Method of and system for placing clock circuits in an integrated circuit |
| JP5299198B2 (ja) * | 2009-09-29 | 2013-09-25 | 富士通セミコンダクター株式会社 | 設計支援プログラム、設計支援装置、および設計支援方法 |
| US8468488B1 (en) * | 2010-05-28 | 2013-06-18 | Golden Gate Technology, Inc. | Methods of automatically placing and routing for timing improvement |
| US9846759B2 (en) * | 2015-07-30 | 2017-12-19 | Taiwan Semiconductor Manufacturing Company, Ltd. | Global connection routing method and system for performing the same |
| US10312192B2 (en) * | 2016-06-02 | 2019-06-04 | Taiwan Semiconductor Manufacturing Co., Ltd. | Integrated circuit having staggered conductive features |
| CN108520128B (zh) * | 2018-03-29 | 2022-04-15 | 北京集创北方科技股份有限公司 | 集成电路设计方法和计算机可读存储介质 |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2848097B2 (ja) * | 1992-04-06 | 1999-01-20 | 日本電気株式会社 | 配置設計方式 |
| JPH07311798A (ja) * | 1994-05-17 | 1995-11-28 | Hitachi Ltd | データの情報表示方法およびデータ分析支援システム |
| JP3299842B2 (ja) * | 1994-05-19 | 2002-07-08 | 富士通株式会社 | 半導体集積回路の配置配線方法および装置 |
| JP3001416B2 (ja) * | 1996-07-30 | 2000-01-24 | 日本電気アイシーマイコンシステム株式会社 | 半導体集積回路のレイアウト方法 |
| JP3017170B2 (ja) * | 1998-08-11 | 2000-03-06 | 日本電気アイシーマイコンシステム株式会社 | 半導体集積回路のレイアウト設計方法 |
| JP2000172738A (ja) * | 1998-12-09 | 2000-06-23 | Nec Corp | Ｌｓｉの自動レイアウト方法 |
| JP2000250964A (ja) * | 1999-03-03 | 2000-09-14 | Hitachi Ltd | 半導体集積回路の論理セル配置方法 |
| JP3804901B2 (ja) * | 1999-07-16 | 2006-08-02 | 富士通株式会社 | 回路素子を配置する配置装置および方法 |
| JP2001125937A (ja) * | 1999-10-25 | 2001-05-11 | Fujitsu Ltd | 半導体集積回路装置のレイアウト設計システム、半導体集積回路装置のレイアウト設計方法、およびそのシステムにおける各手段をもしくはその方法における各工程をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体 |
| US6415426B1 (en) * | 2000-06-02 | 2002-07-02 | Incentia Design Systems, Inc. | Dynamic weighting and/or target zone analysis in timing driven placement of cells of an integrated circuit design |
| US6530073B2 (en) * | 2001-04-30 | 2003-03-04 | Lsi Logic Corporation | RTL annotation tool for layout induced netlist changes |
-
2001
- 2001-07-27 JP JP2001228373A patent/JP4953526B2/ja not_active Expired - Fee Related
-
2002
- 2002-02-22 US US10/079,545 patent/US6857107B2/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JP2003044536A (ja) | 2003-02-14 |
| US20030023938A1 (en) | 2003-01-30 |
| US6857107B2 (en) | 2005-02-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4953526B2 (ja) | タイミング優先でセル配置するｌｓｉのレイアウト方法及びその装置 | |
| KR102373540B1 (ko) | 표준 셀들을 포함하는 집적 회로, 이를 제조하기 위한 방법 및 컴퓨팅 시스템 | |
| US10796053B2 (en) | Computer implemented system and method for generating a layout of a cell defining a circuit component | |
| KR102593720B1 (ko) | 집적회로 설계 및/또는 제조 | |
| US10817640B2 (en) | Integrated circuit including different types of cells, and method and system of designing the same | |
| US11031385B2 (en) | Standard cell for removing routing interference between adjacent pins and device including the same | |
| US6209123B1 (en) | Methods of placing transistors in a circuit layout and semiconductor device with automatically placed transistors | |
| CN107066681B (zh) | 集成电路和制造集成电路的计算机实现方法 | |
| US6598215B2 (en) | Datapath design methodology and routing apparatus | |
| US8365120B2 (en) | Resolving global coupling timing and slew violations for buffer-dominated designs | |
| US6958545B2 (en) | Method for reducing wiring congestion in a VLSI chip design | |
| KR102717096B1 (ko) | 집적 회로 및 상기 집적 회로의 제조를 위한 컴퓨터 구현 방법 | |
| US9760669B2 (en) | Congestion mitigation by wire ordering | |
| US8560999B2 (en) | Routing | |
| Ran et al. | Via-configurable routing architectures and fast design mappability estimation for regular fabrics | |
| US8468488B1 (en) | Methods of automatically placing and routing for timing improvement | |
| JP3433025B2 (ja) | モジュール配置方法 | |
| Zha et al. | Defect-tolerant mapping of CMOL circuits with delay optimization | |
| US6477692B1 (en) | Method and apparatus for channel-routing of an electronic device | |
| CN114722763A (zh) | 布局fpga芯片内时钟线网的方法及设备 | |
| US11151298B1 (en) | Metal track routing with buffer bank insertion | |
| US20230267261A1 (en) | Design system, design method and method of manufacture of semiconductor device | |
| Vacca et al. | Automatic Place&Route of nano-magnetic logic circuits | |
| Mohaghegh | Expanding FPGA CAD and Architecture Exploration to New Routing Structures and Stacked Silicon | |
| KR20240107566A (ko) | 단락을 해결하기 위한 라우팅 방법 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20080613 |
|
| A711 | Notification of change in applicant |
Free format text: JAPANESE INTERMEDIATE CODE: A712 Effective date: 20080731 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20100210 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20100216 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20100414 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20100803 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20101001 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20110105 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20120313 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20150323 Year of fee payment: 3 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313111 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| LAPS | Cancellation because of no payment of annual fees |