JPH09259151A - 回路シミュレーション方法 - Google Patents
回路シミュレーション方法Info
- Publication number
- JPH09259151A JPH09259151A JP8062276A JP6227696A JPH09259151A JP H09259151 A JPH09259151 A JP H09259151A JP 8062276 A JP8062276 A JP 8062276A JP 6227696 A JP6227696 A JP 6227696A JP H09259151 A JPH09259151 A JP H09259151A
- Authority
- JP
- Japan
- Prior art keywords
- group
- depth
- groups
- fan
- circuit simulation
- 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.)
- Withdrawn
Links
Abstract
(57)【要約】
【課題】回路シミュレーションの対象である全体回路を
部分回路に分割し、ファンイン側の部分回路の回路シミ
ュレーション結果を使用して、ファンイン側の部分回路
から逐次的に回路シミュレーションを行う回路シミュレ
ーション方法に関し、少ないメモリ使用量で高精度の回
路シミュレーションを高速に行うことができるようにす
る。 【解決手段】全体回路を拡大グループＧ１〜Ｇ４に分割
し、ファンイン側のグループ（例えば、グループＡ、
Ｄ）の回路シミュレーション結果をファンアウト側のグ
ループ（例えば、グループＢ、Ｅ）の入力データとして
取り扱い、１個の拡大グループ内のグループごとに、そ
の出力に影響を及ぼすと考えられるファンアウト側のグ
ループを含めて回路シミュレーションを行う。
部分回路に分割し、ファンイン側の部分回路の回路シミ
ュレーション結果を使用して、ファンイン側の部分回路
から逐次的に回路シミュレーションを行う回路シミュレ
ーション方法に関し、少ないメモリ使用量で高精度の回
路シミュレーションを高速に行うことができるようにす
る。 【解決手段】全体回路を拡大グループＧ１〜Ｇ４に分割
し、ファンイン側のグループ（例えば、グループＡ、
Ｄ）の回路シミュレーション結果をファンアウト側のグ
ループ（例えば、グループＢ、Ｅ）の入力データとして
取り扱い、１個の拡大グループ内のグループごとに、そ
の出力に影響を及ぼすと考えられるファンアウト側のグ
ループを含めて回路シミュレーションを行う。
Description
【０００１】
【発明の属する技術分野】本発明は、集積回路の設計を
行う場合に使用される回路シミュレーション方法、より
詳しくは、回路シミュレーションの対象である全体回路
を部分回路に分割し、ファンイン側（信号伝搬の上流
側）の部分回路の回路シミュレーション結果を使用し
て、ファンイン側の部分回路から逐次的に回路シミュレ
ーションを行う回路シミュレーション方法に関する。
行う場合に使用される回路シミュレーション方法、より
詳しくは、回路シミュレーションの対象である全体回路
を部分回路に分割し、ファンイン側（信号伝搬の上流
側）の部分回路の回路シミュレーション結果を使用し
て、ファンイン側の部分回路から逐次的に回路シミュレ
ーションを行う回路シミュレーション方法に関する。
【０００２】
【従来の技術】従来、この種の回路シミュレーション方
法として、回路シミュレーションの対象である全体回路
を部分回路に分割した場合、部分回路の出力端子に接続
されている素子は無視するか、あるいは、部分回路の出
力端子は定電圧源に接続されているものとして取り扱う
回路シミュレーション方法が知られている。
法として、回路シミュレーションの対象である全体回路
を部分回路に分割した場合、部分回路の出力端子に接続
されている素子は無視するか、あるいは、部分回路の出
力端子は定電圧源に接続されているものとして取り扱う
回路シミュレーション方法が知られている。
【０００３】
【発明が解決しようとする課題】このような従来の回路
シミュレーション方法においては、部分回路の出力端子
が接続されているファンアウト側（信号伝搬の下流側）
の部分回路による影響が考慮されていないので、高精度
な回路シミュレーションを行うことができないという問
題点があった。
シミュレーション方法においては、部分回路の出力端子
が接続されているファンアウト側（信号伝搬の下流側）
の部分回路による影響が考慮されていないので、高精度
な回路シミュレーションを行うことができないという問
題点があった。
【０００４】なお、回路シミュレーションの対象である
全体回路を部分回路に分割しないで回路シミュレーショ
ンを行う場合には、高精度な回路シミュレーションを行
うことができるが、このようにする場合には、メモリ使
用量が増大し、メモリを増設しなければならないという
問題点がある。
全体回路を部分回路に分割しないで回路シミュレーショ
ンを行う場合には、高精度な回路シミュレーションを行
うことができるが、このようにする場合には、メモリ使
用量が増大し、メモリを増設しなければならないという
問題点がある。
【０００５】本発明は、かかる点に鑑み、少ないメモリ
使用量で高精度の回路シミュレーションを高速に行うこ
とができるようにした回路シミュレーション方法を提供
することを目的とする。
使用量で高精度の回路シミュレーションを高速に行うこ
とができるようにした回路シミュレーション方法を提供
することを目的とする。
【０００６】
【課題を解決するための手段】本発明中、第１の発明の
回路シミュレーション方法（請求項１記載の回路シミュ
レーション方法）は、回路シミュレーションの対象であ
る全体回路を複数のグループに分割する工程と、ファン
イン側のグループの回路シミュレーション結果をファン
アウト側のグループの入力データとして取り扱い、ファ
ンアウト側に、同一のグループを、出力に影響を与える
と考えられるグループとして有する複数のグループは、
これら複数のグループごとに、その他のグループは、グ
ループごとに、それぞれ、その出力に影響を及ぼすと考
えられるファンアウト側のグループを含めて回路シミュ
レーションを行う工程とを含んでいるというものであ
る。
回路シミュレーション方法（請求項１記載の回路シミュ
レーション方法）は、回路シミュレーションの対象であ
る全体回路を複数のグループに分割する工程と、ファン
イン側のグループの回路シミュレーション結果をファン
アウト側のグループの入力データとして取り扱い、ファ
ンアウト側に、同一のグループを、出力に影響を与える
と考えられるグループとして有する複数のグループは、
これら複数のグループごとに、その他のグループは、グ
ループごとに、それぞれ、その出力に影響を及ぼすと考
えられるファンアウト側のグループを含めて回路シミュ
レーションを行う工程とを含んでいるというものであ
る。
【０００７】第１の発明の回路シミュレーション方法に
よれば、ファンイン側のグループの回路シミュレーショ
ン結果をファンアウト側のグループの入力データとして
取り扱い、ファンアウト側に、同一のグループを、出力
に影響を与えると考えられるグループとして有する複数
のグループは、これら複数のグループごとに、その他の
グループは、グループごとに、それぞれ、その出力に影
響を及ぼすと考えられるファンアウト側のグループを含
めて回路シミュレーションを行うとしているので、少な
いメモリ使用量で高精度の回路シミュレーションを高速
に行うことができる。
よれば、ファンイン側のグループの回路シミュレーショ
ン結果をファンアウト側のグループの入力データとして
取り扱い、ファンアウト側に、同一のグループを、出力
に影響を与えると考えられるグループとして有する複数
のグループは、これら複数のグループごとに、その他の
グループは、グループごとに、それぞれ、その出力に影
響を及ぼすと考えられるファンアウト側のグループを含
めて回路シミュレーションを行うとしているので、少な
いメモリ使用量で高精度の回路シミュレーションを高速
に行うことができる。
【０００８】また、第２の発明の回路シミュレーション
方法（請求項２記載の回路シミュレーション方法）は、
第１の発明の回路シミュレーション方法において、回路
シミュレーションの対象である全体回路を複数のグルー
プに分割する工程は、全体回路を電源端子及び結合の弱
い箇所で切り離して複数のブロックに分割する工程と、
ブロック間の信号の流れを調べ、信号がループしている
複数のブロックが存在する場合には、これら複数のブロ
ックをまとめて１個のグループとし、その他のブロック
をそれぞれ１個のグループとし、信号がループしている
複数のブロックが存在しない場合には、各ブロックをそ
れぞれ１個のグループとする工程とを含んでいるという
ものである。
方法（請求項２記載の回路シミュレーション方法）は、
第１の発明の回路シミュレーション方法において、回路
シミュレーションの対象である全体回路を複数のグルー
プに分割する工程は、全体回路を電源端子及び結合の弱
い箇所で切り離して複数のブロックに分割する工程と、
ブロック間の信号の流れを調べ、信号がループしている
複数のブロックが存在する場合には、これら複数のブロ
ックをまとめて１個のグループとし、その他のブロック
をそれぞれ１個のグループとし、信号がループしている
複数のブロックが存在しない場合には、各ブロックをそ
れぞれ１個のグループとする工程とを含んでいるという
ものである。
【０００９】第２の発明の回路シミュレーション方法に
よれば、好適なグループを効率的に抽出し、少ないメモ
リ使用量で高精度の回路シミュレーションを高速に行う
ことができる。
よれば、好適なグループを効率的に抽出し、少ないメモ
リ使用量で高精度の回路シミュレーションを高速に行う
ことができる。
【００１０】また、第３の発明の回路シミュレーション
方法（請求項３記載の回路シミュレーション方法）は、
第１又は第２の発明の回路シミュレーション方法におい
て、ファンイン側のグループの回路シミュレーション結
果をファンアウト側のグループの入力データとして取り
扱い、ファンアウト側に、同一のグループを、出力に影
響を与えると考えられるグループとして有する複数のグ
ループは、これら複数のグループごとに、その他のグル
ープは、グループごとに、それぞれ、その出力に影響を
及ぼすと考えられるファンアウト側のグループを含めて
回路シミュレーションを行う工程は、各グループごと
に、その出力に影響を及ぼすと考えられるグループを有
効周辺グループとして抽出する工程と、同一のグループ
をファンアウト側の有効周辺グループとする複数のグル
ープが存在する場合には、これら複数のグループをまと
めて１個の拡大グループとし、その他のグループをそれ
ぞれ１個の拡大グループとし、同一のグループをファン
アウト側の有効周辺グループとする複数のグループが存
在しない場合には、各グループをそれぞれ１個の拡大グ
ループとする工程と、１個の拡大グループ内のグループ
ごとに、かつ、ファンイン側のグループから順に、拡大
グループ内のグループのファンアウト側の有効周辺グル
ープを含めて回路シミュレーションを行う工程とを含ん
でいるというものである。
方法（請求項３記載の回路シミュレーション方法）は、
第１又は第２の発明の回路シミュレーション方法におい
て、ファンイン側のグループの回路シミュレーション結
果をファンアウト側のグループの入力データとして取り
扱い、ファンアウト側に、同一のグループを、出力に影
響を与えると考えられるグループとして有する複数のグ
ループは、これら複数のグループごとに、その他のグル
ープは、グループごとに、それぞれ、その出力に影響を
及ぼすと考えられるファンアウト側のグループを含めて
回路シミュレーションを行う工程は、各グループごと
に、その出力に影響を及ぼすと考えられるグループを有
効周辺グループとして抽出する工程と、同一のグループ
をファンアウト側の有効周辺グループとする複数のグル
ープが存在する場合には、これら複数のグループをまと
めて１個の拡大グループとし、その他のグループをそれ
ぞれ１個の拡大グループとし、同一のグループをファン
アウト側の有効周辺グループとする複数のグループが存
在しない場合には、各グループをそれぞれ１個の拡大グ
ループとする工程と、１個の拡大グループ内のグループ
ごとに、かつ、ファンイン側のグループから順に、拡大
グループ内のグループのファンアウト側の有効周辺グル
ープを含めて回路シミュレーションを行う工程とを含ん
でいるというものである。
【００１１】第３の発明の回路シミュレーション方法に
よれば、拡大グループごとの回路シミュレーションを効
率的に行い、少ないメモリ使用量で高精度の回路シミュ
レーションを高速に行うことができる。
よれば、拡大グループごとの回路シミュレーションを効
率的に行い、少ないメモリ使用量で高精度の回路シミュ
レーションを高速に行うことができる。
【００１２】また、第４の発明の回路シミュレーション
方法（請求項４記載の回路シミュレーション方法）は、
第３の発明の回路シミュレーション方法において、各グ
ループごとに、その出力に影響を及ぼすと考えられるグ
ループを有効周辺グループとして抽出する工程は、グル
ープを１個ずつ対象グループとして選択し、対象グルー
プから他のグループまでのグループ間を結ぶパスをたど
り、順方向の信号の流れをもつパスの数を数え、その数
を対象グループに対する他のグループの深度とし、この
深度が予め指定した深度よりも小さいグループを対象グ
ループの有効周辺グループとして抽出する工程を含んで
いるというものである。
方法（請求項４記載の回路シミュレーション方法）は、
第３の発明の回路シミュレーション方法において、各グ
ループごとに、その出力に影響を及ぼすと考えられるグ
ループを有効周辺グループとして抽出する工程は、グル
ープを１個ずつ対象グループとして選択し、対象グルー
プから他のグループまでのグループ間を結ぶパスをたど
り、順方向の信号の流れをもつパスの数を数え、その数
を対象グループに対する他のグループの深度とし、この
深度が予め指定した深度よりも小さいグループを対象グ
ループの有効周辺グループとして抽出する工程を含んで
いるというものである。
【００１３】第４の発明の回路シミュレーション方法に
よれば、好適な有効周辺グループを効率的に抽出し、少
ないメモリ使用量で高精度の回路シミュレーションを高
速に行うことができる。
よれば、好適な有効周辺グループを効率的に抽出し、少
ないメモリ使用量で高精度の回路シミュレーションを高
速に行うことができる。
【００１４】また、第５の発明の回路シミュレーション
方法（請求項５記載の回路シミュレーション方法）は、
回路シミュレーションに必要な全体回路のデータを仮想
メモリ装置に格納し、この仮想メモリ装置から回路シミ
ュレーションに必要なグループのデータを実メモリ装置
に読み込み、この実メモリ装置に読み込まれたグループ
のデータを使用した回路シミュレーションに必要な演算
を演算装置で行うことにより、第１、第２、第３又は第
４の発明の回路シミュレーション方法を行うというもの
である。
方法（請求項５記載の回路シミュレーション方法）は、
回路シミュレーションに必要な全体回路のデータを仮想
メモリ装置に格納し、この仮想メモリ装置から回路シミ
ュレーションに必要なグループのデータを実メモリ装置
に読み込み、この実メモリ装置に読み込まれたグループ
のデータを使用した回路シミュレーションに必要な演算
を演算装置で行うことにより、第１、第２、第３又は第
４の発明の回路シミュレーション方法を行うというもの
である。
【００１５】第５の発明の回路シミュレーション方法に
よれば、特別な回路シミュレーション装置を必要とせ
ず、既存の回路シミュレーション装置を使用して、第
１、第２、第３又は第４の発明の回路シミュレーション
方法を実行することができる。
よれば、特別な回路シミュレーション装置を必要とせ
ず、既存の回路シミュレーション装置を使用して、第
１、第２、第３又は第４の発明の回路シミュレーション
方法を実行することができる。
【００１６】
【発明の実施の形態】図１は、本発明の実施の一形態を
示すフローチャートである。即ち、本発明の実施の一形
態においては、まず、回路シミュレーションの対象とす
る全体回路を電源端子及び結合の弱い箇所で切り離して
ブロックに分割する（処理Ｓ１）。
示すフローチャートである。即ち、本発明の実施の一形
態においては、まず、回路シミュレーションの対象とす
る全体回路を電源端子及び結合の弱い箇所で切り離して
ブロックに分割する（処理Ｓ１）。
【００１７】たとえば、図２において、１は回路シミュ
レーションの対象とする全体回路を示しているが、この
全体回路１を、電源端子及び結合の弱い箇所で切り離し
て、たとえば、ブロックａ〜ｉに分割する。
レーションの対象とする全体回路を示しているが、この
全体回路１を、電源端子及び結合の弱い箇所で切り離し
て、たとえば、ブロックａ〜ｉに分割する。
【００１８】次に、ブロック間の信号の流れを調べ（処
理Ｓ２）、信号がループしている複数のブロックが存在
する場合には、信号がループしている複数のブロックを
まとめて１個のグループとし、その他のブロックをそれ
ぞれ１個のグループとし、信号がループしている複数の
ブロックが存在しない場合には、各ブロックをそれぞれ
１個のグループとする（処理Ｓ３）。
理Ｓ２）、信号がループしている複数のブロックが存在
する場合には、信号がループしている複数のブロックを
まとめて１個のグループとし、その他のブロックをそれ
ぞれ１個のグループとし、信号がループしている複数の
ブロックが存在しない場合には、各ブロックをそれぞれ
１個のグループとする（処理Ｓ３）。
【００１９】たとえば、図２において、４個のブロック
ｅ〜ｈは、信号がループしているブロックであるから、
これら４個のブロックｅ〜ｈをまとめて１つのグループ
Ｅとし、その他のブロックａ、ｂ、ｃ、ｄ、ｉをそれぞ
れ１個のグループＡ、Ｂ、Ｃ、Ｄ、Ｆとする。
ｅ〜ｈは、信号がループしているブロックであるから、
これら４個のブロックｅ〜ｈをまとめて１つのグループ
Ｅとし、その他のブロックａ、ｂ、ｃ、ｄ、ｉをそれぞ
れ１個のグループＡ、Ｂ、Ｃ、Ｄ、Ｆとする。
【００２０】次に、各グループごとに、グループの出力
に影響を及ぼすと考えられるグループを有効周辺グルー
プとして抽出し（処理Ｓ４）、更に、同一のグループを
ファンアウト側の有効周辺グループとする複数のグルー
プが存在する場合には、これら複数のグループをまとめ
て１個の拡大グループとし、その他のグループをそれぞ
れ１個の拡大グループとし、同一のグループをファンア
ウト側の有効周辺グループとする複数のグループが存在
しない場合には、各グループをそれぞれ１個の拡大グル
ープとする（処理Ｓ５）。
に影響を及ぼすと考えられるグループを有効周辺グルー
プとして抽出し（処理Ｓ４）、更に、同一のグループを
ファンアウト側の有効周辺グループとする複数のグルー
プが存在する場合には、これら複数のグループをまとめ
て１個の拡大グループとし、その他のグループをそれぞ
れ１個の拡大グループとし、同一のグループをファンア
ウト側の有効周辺グループとする複数のグループが存在
しない場合には、各グループをそれぞれ１個の拡大グル
ープとする（処理Ｓ５）。
【００２１】ここに、図３は、有効周辺グループおよび
拡大グループの抽出アルゴリズムを示すフローチャート
である。
拡大グループの抽出アルゴリズムを示すフローチャート
である。
【００２２】即ち、有効周辺グループおよび拡大グルー
プを抽出する場合には、グループの中から１つのグルー
プを対象グループとして選択し（処理Ｐ１）、対象グル
ープの隣接グループを検索する（処理Ｐ２）。なお、処
理Ｐ２においては、後述するように、抽出された有効周
辺グループに隣接するグループの検索も行われる。
プを抽出する場合には、グループの中から１つのグルー
プを対象グループとして選択し（処理Ｐ１）、対象グル
ープの隣接グループを検索する（処理Ｐ２）。なお、処
理Ｐ２においては、後述するように、抽出された有効周
辺グループに隣接するグループの検索も行われる。
【００２３】ここに、検索の結果、隣接グループが１個
の場合には、その隣接グループを選択し（処理Ｐ４）、
その選択グループの対象グループに対する深度を求める
（処理Ｐ５）。
の場合には、その隣接グループを選択し（処理Ｐ４）、
その選択グループの対象グループに対する深度を求める
（処理Ｐ５）。
【００２４】これに対して、検索の結果、隣接グループ
が複数個ある場合には、１つの隣接グループを選択し
て、残りの隣接グループをスタックに積み（処理Ｐ
４）、選択した隣接グループの対象グループに対する深
度を求める（処理Ｐ５）。
が複数個ある場合には、１つの隣接グループを選択し
て、残りの隣接グループをスタックに積み（処理Ｐ
４）、選択した隣接グループの対象グループに対する深
度を求める（処理Ｐ５）。
【００２５】また、検索の結果、隣接グループが存在し
ない場合には、スタックから１つのグループを抽出し
（処理Ｐ３）、そのグループの深度を求める（処理Ｐ
５）。なお、スタックにグループが積まれていない場合
には、隣接グループを検索しているグループに対する処
理を終了して後述する処理Ｐ９に移行する。
ない場合には、スタックから１つのグループを抽出し
（処理Ｐ３）、そのグループの深度を求める（処理Ｐ
５）。なお、スタックにグループが積まれていない場合
には、隣接グループを検索しているグループに対する処
理を終了して後述する処理Ｐ９に移行する。
【００２６】選択された隣接グループの深度は、図４に
示すように、ファンアウト深度と、ファンイン深度とで
表わすものとする。
示すように、ファンアウト深度と、ファンイン深度とで
表わすものとする。
【００２７】ここに、対象グループのファンアウト深度
およびファンイン深度は０とし、対象グループまたは有
効周辺グループの隣接グループの深度は、その隣接グル
ープの選択の元となったグループ（以下、親グループと
いう）に対してファンアウトグループであれば、親グル
ープのファンアウト深度に１を足し、ファンイングルー
プであれば、親グループのファンイン深度から１を引く
ことにより求めるものとする。
およびファンイン深度は０とし、対象グループまたは有
効周辺グループの隣接グループの深度は、その隣接グル
ープの選択の元となったグループ（以下、親グループと
いう）に対してファンアウトグループであれば、親グル
ープのファンアウト深度に１を足し、ファンイングルー
プであれば、親グループのファンイン深度から１を引く
ことにより求めるものとする。
【００２８】そして、処理Ｐ５で求めた深度が予め設定
した規準外の場合には、この隣接グループに対する処理
を終了し、新たにスタックから隣接グループを１つ抽出
して（処理Ｐ３）、そのグループの深度を求める（処理
Ｐ５）。
した規準外の場合には、この隣接グループに対する処理
を終了し、新たにスタックから隣接グループを１つ抽出
して（処理Ｐ３）、そのグループの深度を求める（処理
Ｐ５）。
【００２９】これに対して、処理Ｐ５で求めた深度が予
め設定した規準内の深度である場合には、この隣接グル
ープが対象グループに関して過去にパス検索を実行した
か否か、即ち、対象グループに対する深度が既に求めら
れているものであるか否かを判断する（処理Ｐ６）。
め設定した規準内の深度である場合には、この隣接グル
ープが対象グループに関して過去にパス検索を実行した
か否か、即ち、対象グループに対する深度が既に求めら
れているものであるか否かを判断する（処理Ｐ６）。
【００３０】判断の結果、はじめてパス検索を実行した
もの、即ち、深度が未定のものである場合には、処理Ｐ
５で求めた深度をその隣接グループの深度として決定
し、その隣接グループを対象グループの有効周辺グルー
プとし（処理Ｐ８）、処理Ｐ２に戻り、有効周辺グルー
プに対する隣接グループを検索して、これまでの処理を
繰り返す。
もの、即ち、深度が未定のものである場合には、処理Ｐ
５で求めた深度をその隣接グループの深度として決定
し、その隣接グループを対象グループの有効周辺グルー
プとし（処理Ｐ８）、処理Ｐ２に戻り、有効周辺グルー
プに対する隣接グループを検索して、これまでの処理を
繰り返す。
【００３１】他方、処理Ｐ６において、既にパス検索を
実行した隣接グループであることが判明した場合には、
既に求めたファンアウト深度と新たに求めたファンアウ
ト深度との比較を行い、それらが等しいか、新たに求め
たファンアウト深度の方が大きい場合には、その隣接グ
ループに対する処理を終了し（処理Ｐ７）、新たにスタ
ックから隣接グループを１つ抽出し（処理Ｐ３）、この
隣接グループについて、深度を求める（処理Ｐ５）。
実行した隣接グループであることが判明した場合には、
既に求めたファンアウト深度と新たに求めたファンアウ
ト深度との比較を行い、それらが等しいか、新たに求め
たファンアウト深度の方が大きい場合には、その隣接グ
ループに対する処理を終了し（処理Ｐ７）、新たにスタ
ックから隣接グループを１つ抽出し（処理Ｐ３）、この
隣接グループについて、深度を求める（処理Ｐ５）。
【００３２】これに対して、処理Ｐ７において、新しく
求めたファンアウト深度の方が小さいことが判明した場
合には、新しいファンアウト深度を、そのグループのフ
ァンアウト深度とし（処理Ｐ８）、処理Ｐ２に戻り、そ
の隣接グループに対する隣接グループを検索して、これ
までの処理を繰り返す。
求めたファンアウト深度の方が小さいことが判明した場
合には、新しいファンアウト深度を、そのグループのフ
ァンアウト深度とし（処理Ｐ８）、処理Ｐ２に戻り、そ
の隣接グループに対する隣接グループを検索して、これ
までの処理を繰り返す。
【００３３】そして、処理Ｐ３において、スタックにグ
ループが積まれていない場合には、対象グループに対す
る処理を終了し、対象グループおよび対象グループと同
じ深度のグループとをまとめて拡大グループとする（処
理Ｐ９）。
ループが積まれていない場合には、対象グループに対す
る処理を終了し、対象グループおよび対象グループと同
じ深度のグループとをまとめて拡大グループとする（処
理Ｐ９）。
【００３４】ここに、図５〜図１０は、図３に示す有効
周辺グループおよび拡大グループの抽出アルゴリズムを
説明するための図であり、図２に示すグループＡ〜Ｆに
ついて、ファンアウト深度が１以下、ファンアウト深度
とファンイン深度の合計が０以上の場合を有効周辺グル
ープ抽出の規準とし、ファンアウト深度とファンイン深
度の合計が０の場合を拡大グループの規準とした場合を
例にしている。
周辺グループおよび拡大グループの抽出アルゴリズムを
説明するための図であり、図２に示すグループＡ〜Ｆに
ついて、ファンアウト深度が１以下、ファンアウト深度
とファンイン深度の合計が０以上の場合を有効周辺グル
ープ抽出の規準とし、ファンアウト深度とファンイン深
度の合計が０の場合を拡大グループの規準とした場合を
例にしている。
【００３５】即ち、有効周辺グループおよび拡大グルー
プを抽出する場合には、まず、図５に示すように、たと
えば、グループＡを対象グループとして選択し（処理Ｐ
１）、グループＡの深度を（０、０）に設定する。
プを抽出する場合には、まず、図５に示すように、たと
えば、グループＡを対象グループとして選択し（処理Ｐ
１）、グループＡの深度を（０、０）に設定する。
【００３６】次に、グループＡの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＢ、Ｅが存在するので、たとえば、グループＢを選択
し、グループＥをスタックに積み（処理Ｐ４）、グルー
プＢの深度を求める（処理Ｐ５）。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＢ、Ｅが存在するので、たとえば、グループＢを選択
し、グループＥをスタックに積み（処理Ｐ４）、グルー
プＢの深度を求める（処理Ｐ５）。
【００３７】グループＢは、親グループであるグループ
Ａのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プ抽出の規準内の深度であり、かつ、グループＢは対象
グループであるグループＡに関して過去にパス検索を実
行していないので、グループＢをグループＡの有効周辺
グループとする（処理Ｐ８）。
Ａのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プ抽出の規準内の深度であり、かつ、グループＢは対象
グループであるグループＡに関して過去にパス検索を実
行していないので、グループＢをグループＡの有効周辺
グループとする（処理Ｐ８）。
【００３８】次に、グループＢの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＡ、Ｃが存在するので、たとえば、グループＡを選択
し、グループＣをスタックに積み（処理Ｐ４）、グルー
プＡの深度を求める（処理Ｐ５）。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＡ、Ｃが存在するので、たとえば、グループＡを選択
し、グループＣをスタックに積み（処理Ｐ４）、グルー
プＡの深度を求める（処理Ｐ５）。
【００３９】この場合、グループＡは、親グループであ
るグループＢのファンイングループであるから、その深
度は（１、−１）となり、深度（１、−１）は有効周辺
グループ抽出の基準内の深度であるが、ファンアウト深
度は０から１に変化しており、新ファンアウト深度＞旧
ファンアウト深度となるので、グループＡについての処
理を終了してスタックからグループＣを抽出し（処理Ｐ
３）、グループＣの深度を求める（処理Ｐ５）。
るグループＢのファンイングループであるから、その深
度は（１、−１）となり、深度（１、−１）は有効周辺
グループ抽出の基準内の深度であるが、ファンアウト深
度は０から１に変化しており、新ファンアウト深度＞旧
ファンアウト深度となるので、グループＡについての処
理を終了してスタックからグループＣを抽出し（処理Ｐ
３）、グループＣの深度を求める（処理Ｐ５）。
【００４０】グループＣは、親グループであるグループ
Ｂのファンアウトグループであるから、その深度は
（２、０）となるが、深度（２、０）は有効周辺グルー
プ抽出の規準外の深度であるから、グループＣについて
の処理を終了してスタックからグループＥを抽出し（処
理Ｐ３）、グループＥの深度を求める（処理Ｐ５）。
Ｂのファンアウトグループであるから、その深度は
（２、０）となるが、深度（２、０）は有効周辺グルー
プ抽出の規準外の深度であるから、グループＣについて
の処理を終了してスタックからグループＥを抽出し（処
理Ｐ３）、グループＥの深度を求める（処理Ｐ５）。
【００４１】グループＥは、親グループであるグループ
Ａのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プ抽出の規準内の深度であり、かつ、グループＥは対象
グループであるグループＡに関して過去にパス検索を実
行していないので、グループＥをグループＡの有効周辺
グループとする（処理Ｐ８）。
Ａのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プ抽出の規準内の深度であり、かつ、グループＥは対象
グループであるグループＡに関して過去にパス検索を実
行していないので、グループＥをグループＡの有効周辺
グループとする（処理Ｐ８）。
【００４２】次に、グループＥの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＡ、Ｃ、Ｄ、Ｆが存在するので、たとえば、グループ
Ａを隣接グループとして選択し、グループＣ、Ｄ、Ｆを
隣接グループとしてスタックに積み（処理Ｐ４）、グル
ープＡの深度を求める（処理Ｐ５）。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＡ、Ｃ、Ｄ、Ｆが存在するので、たとえば、グループ
Ａを隣接グループとして選択し、グループＣ、Ｄ、Ｆを
隣接グループとしてスタックに積み（処理Ｐ４）、グル
ープＡの深度を求める（処理Ｐ５）。
【００４３】グループＡは、親グループであるグループ
Ｅのファンイングループであるから、その深度は（１、
−１）となり、深度（１、−１）は有効周辺グループ抽
出の規準内の深度であるが、ファンアウト深度は０から
１に変化しており、新ファンアウト深度＞旧ファンアウ
ト深度となるので、グループＡについての処理を終了し
てスタックからグループＣを抽出し（処理Ｐ３）、グル
ープＣの深度を求める（処理Ｐ５）。
Ｅのファンイングループであるから、その深度は（１、
−１）となり、深度（１、−１）は有効周辺グループ抽
出の規準内の深度であるが、ファンアウト深度は０から
１に変化しており、新ファンアウト深度＞旧ファンアウ
ト深度となるので、グループＡについての処理を終了し
てスタックからグループＣを抽出し（処理Ｐ３）、グル
ープＣの深度を求める（処理Ｐ５）。
【００４４】グループＣは、親グループであるグループ
Ｅのファンアウトグループであるから、その深度は
（２、０）となるが、深度（２、０）は有効周辺グルー
プ抽出の規準外の深度であるから、グループＣについて
の処理を終了してスタックからグループＤを抽出し（処
理Ｐ３）、グループＤの深度を求める（処理Ｐ５）。
Ｅのファンアウトグループであるから、その深度は
（２、０）となるが、深度（２、０）は有効周辺グルー
プ抽出の規準外の深度であるから、グループＣについて
の処理を終了してスタックからグループＤを抽出し（処
理Ｐ３）、グループＤの深度を求める（処理Ｐ５）。
【００４５】グループＤは、親グループであるグループ
Ｅのファンイングループであるから、その深度は（１、
−１）となるが、深度（１、−１）は有効周辺グループ
抽出の規準内の深度であり、かつ、グループＤは対象グ
ループであるグループＡに関して過去にパス検索を実行
していないので、グループＤをグループＡの有効周辺グ
ループとする（処理Ｐ８）。
Ｅのファンイングループであるから、その深度は（１、
−１）となるが、深度（１、−１）は有効周辺グループ
抽出の規準内の深度であり、かつ、グループＤは対象グ
ループであるグループＡに関して過去にパス検索を実行
していないので、グループＤをグループＡの有効周辺グ
ループとする（処理Ｐ８）。
【００４６】次に、グループＤの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＥが存在するので、グループＥを選択し（処理Ｐ
４）、グループＥの深度を求める。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＥが存在するので、グループＥを選択し（処理Ｐ
４）、グループＥの深度を求める。
【００４７】グループＥは、親グループであるグループ
Ｄのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の規準外の深度であるから、グループＥにつ
いての処理を終了してスタックからグループＦを抽出し
（処理Ｐ３）、グループＦの深度を求める（処理Ｐ
５）。
Ｄのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の規準外の深度であるから、グループＥにつ
いての処理を終了してスタックからグループＦを抽出し
（処理Ｐ３）、グループＦの深度を求める（処理Ｐ
５）。
【００４８】グループＦは、親グループであるグループ
Ｅのファンアウトグループであるから、その深度は
（２、０）となるが、深度（２、０）は有効周辺グルー
プ抽出の規準外の深度であるから、グループＦについて
の処理を終了し、処理Ｐ３に戻るが、この場合、スタッ
クにはグループが積まれていないので、対象グループで
あるグループＡについての処理を終了する。
Ｅのファンアウトグループであるから、その深度は
（２、０）となるが、深度（２、０）は有効周辺グルー
プ抽出の規準外の深度であるから、グループＦについて
の処理を終了し、処理Ｐ３に戻るが、この場合、スタッ
クにはグループが積まれていないので、対象グループで
あるグループＡについての処理を終了する。
【００４９】ここに、グループＤのファンアウト深度お
よびファンイン深度の合計値は０となるので、グループ
Ａと、グループＡと同一深度のグループＤとをまとめて
拡大グループとする（処理Ｐ９）。
よびファンイン深度の合計値は０となるので、グループ
Ａと、グループＡと同一深度のグループＤとをまとめて
拡大グループとする（処理Ｐ９）。
【００５０】次に、図６に示すように、対象グループと
して、たとえば、グループＢを選択し（処理Ｐ１）、グ
ループＢの深度を（０、０）に設定する。
して、たとえば、グループＢを選択し（処理Ｐ１）、グ
ループＢの深度を（０、０）に設定する。
【００５１】そして、グループＢの隣接グループを検索
する（処理Ｐ２）。この場合、隣接グループとしてグル
ープＡ、Ｃが存在するので、たとえば、グループＡを選
択し、グループＣをスタックに積み（処理Ｐ４）、グル
ープＡの深度を求める（処理Ｐ５）。
する（処理Ｐ２）。この場合、隣接グループとしてグル
ープＡ、Ｃが存在するので、たとえば、グループＡを選
択し、グループＣをスタックに積み（処理Ｐ４）、グル
ープＡの深度を求める（処理Ｐ５）。
【００５２】グループＡは、親グループであるグループ
Ｂのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
抽出の基準外の深度であるから、グループＡについての
処理を終了してスタックからグループＣを抽出し（処理
Ｐ３）、グループＣの深度を求める（処理Ｐ５）。
Ｂのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
抽出の基準外の深度であるから、グループＡについての
処理を終了してスタックからグループＣを抽出し（処理
Ｐ３）、グループＣの深度を求める（処理Ｐ５）。
【００５３】グループＣは、親グループであるグループ
Ｂのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プの規準内の深度であり、かつ、グループＣは、対象グ
ループであるグループＢに関して過去にパス検索を実行
していないので、グループＣをグループＢの有効周辺グ
ループとする（処理Ｐ８）。
Ｂのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プの規準内の深度であり、かつ、グループＣは、対象グ
ループであるグループＢに関して過去にパス検索を実行
していないので、グループＣをグループＢの有効周辺グ
ループとする（処理Ｐ８）。
【００５４】次に、グループＣの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＢ、Ｅが存在するので、たとえば、グループＢを選択
し、グループＥをスタックに積み（処理Ｐ４）、グルー
プＢの深度を求める（処理Ｐ５）。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＢ、Ｅが存在するので、たとえば、グループＢを選択
し、グループＥをスタックに積み（処理Ｐ４）、グルー
プＢの深度を求める（処理Ｐ５）。
【００５５】グループＢは、親グループであるグループ
Ｃのファンアウトグループであるから、その深度は
（１、−１）となり、深度（１、−１）は有効周辺グル
ープ抽出の規準内の深度であるが、ファンアウト深度は
０から１に変化しており、新ファンアウト深度＞旧ファ
ンアウト深度となるので、グループＢについての処理を
終了してスタックからグループＥを抽出し（処理Ｐ
３）、グループＥの深度を求める（処理Ｐ５）。
Ｃのファンアウトグループであるから、その深度は
（１、−１）となり、深度（１、−１）は有効周辺グル
ープ抽出の規準内の深度であるが、ファンアウト深度は
０から１に変化しており、新ファンアウト深度＞旧ファ
ンアウト深度となるので、グループＢについての処理を
終了してスタックからグループＥを抽出し（処理Ｐ
３）、グループＥの深度を求める（処理Ｐ５）。
【００５６】グループＥは、親グループであるグループ
Ｃのファンイングループであるから、その深度は（１、
−１）となるが、深度（１、−１）は有効周辺グループ
抽出の規準内の深度であり、かつ、グループＥは、対象
グループであるグループＢに関して過去にパス検索を実
行していないので、グループＥをグループＢの有効周辺
グループとする（処理Ｐ８）。
Ｃのファンイングループであるから、その深度は（１、
−１）となるが、深度（１、−１）は有効周辺グループ
抽出の規準内の深度であり、かつ、グループＥは、対象
グループであるグループＢに関して過去にパス検索を実
行していないので、グループＥをグループＢの有効周辺
グループとする（処理Ｐ８）。
【００５７】次に、グループＥの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとして、グル
ープＡ、Ｃ、Ｄ、Ｆが存在するので、たとえば、グルー
プＡを選択し、グループＣ、Ｄ、Ｆをスタックに積み
（処理Ｐ４）、グループＡの深度を求める（処理Ｐ
５）。
る（処理Ｐ２）。この場合、隣接グループとして、グル
ープＡ、Ｃ、Ｄ、Ｆが存在するので、たとえば、グルー
プＡを選択し、グループＣ、Ｄ、Ｆをスタックに積み
（処理Ｐ４）、グループＡの深度を求める（処理Ｐ
５）。
【００５８】グループＡは、親グループであるグループ
Ｅのファンイングループであるから、その深度は（１、
−２）となるが、深度（１、−２）は有効周辺グループ
抽出の規準外の深度であるから、グループＡについての
処理を終了してスタックからグループＣを抽出し（処理
Ｐ３）、グループＣの深度を求める（処理Ｐ５）。
Ｅのファンイングループであるから、その深度は（１、
−２）となるが、深度（１、−２）は有効周辺グループ
抽出の規準外の深度であるから、グループＡについての
処理を終了してスタックからグループＣを抽出し（処理
Ｐ３）、グループＣの深度を求める（処理Ｐ５）。
【００５９】グループＣは、親グループであるグループ
Ｅのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の規準外の深度であるから、グループＣにつ
いての処理を終了してスタックからグループＤを抽出し
（処理Ｐ３）、グループＤの深度を求める（処理Ｐ
５）。
Ｅのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の規準外の深度であるから、グループＣにつ
いての処理を終了してスタックからグループＤを抽出し
（処理Ｐ３）、グループＤの深度を求める（処理Ｐ
５）。
【００６０】グループＤは、親グループであるグループ
Ｅのファンイングループであるから、その深度は（１、
−２）となるが、深度（１、−２）は有効周辺グループ
抽出の規準外の深度となるので、グループＤについての
処理を終了してスタックからグループＦを抽出し（処理
Ｐ３）、グループＦの深度を求める（処理Ｐ５）。
Ｅのファンイングループであるから、その深度は（１、
−２）となるが、深度（１、−２）は有効周辺グループ
抽出の規準外の深度となるので、グループＤについての
処理を終了してスタックからグループＦを抽出し（処理
Ｐ３）、グループＦの深度を求める（処理Ｐ５）。
【００６１】グループＦは、親グループであるグループ
Ｅのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の規準外の深度であるので、処理Ｐ３に戻る
が、この場合、スタックにはグループが積まれていない
ので、対象グループであるグループＢに対する処理を終
了する。
Ｅのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の規準外の深度であるので、処理Ｐ３に戻る
が、この場合、スタックにはグループが積まれていない
ので、対象グループであるグループＢに対する処理を終
了する。
【００６２】ここに、グループＥのファンアウト深度お
よびファンイン深度の合計値は０となるので、グループ
Ｂと、グループＢと同一深度のグループＥとをまとめて
拡大グループとする（処理Ｐ９）。
よびファンイン深度の合計値は０となるので、グループ
Ｂと、グループＢと同一深度のグループＥとをまとめて
拡大グループとする（処理Ｐ９）。
【００６３】次に、図７に示すように、対象グループと
して、たとえば、グループＣを選択し（処理Ｐ１）、グ
ループＣの深度を（０、０）に設定する。
して、たとえば、グループＣを選択し（処理Ｐ１）、グ
ループＣの深度を（０、０）に設定する。
【００６４】そして、グループＣの隣接グループを検索
する（処理Ｐ２）。この場合、隣接グループとしてグル
ープＢ、Ｅが存在するので、たとえば、グループＢを選
択し、グループＥをスタックに積み（処理Ｐ４）、グル
ープＢの深度を求める（処理Ｐ５）。
する（処理Ｐ２）。この場合、隣接グループとしてグル
ープＢ、Ｅが存在するので、たとえば、グループＢを選
択し、グループＥをスタックに積み（処理Ｐ４）、グル
ープＢの深度を求める（処理Ｐ５）。
【００６５】グループＢは、親グループであるグループ
Ｃのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
抽出の規準外の深度であるので、グループＢについての
処理を終了してスタックからグループＥを抽出し（処理
Ｐ３）、グループＥの深度を求める（処理Ｐ５）。
Ｃのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
抽出の規準外の深度であるので、グループＢについての
処理を終了してスタックからグループＥを抽出し（処理
Ｐ３）、グループＥの深度を求める（処理Ｐ５）。
【００６６】グループＥは、親グループであるグループ
Ｃのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
の規準外の深度であるので、処理Ｐ３に戻る。
Ｃのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
の規準外の深度であるので、処理Ｐ３に戻る。
【００６７】この場合、スタックにはグループが積まれ
ていないので、対象グループであるグループＣに対する
処理を終了し、グループＣと同じ深度のグループは存在
しないので、次に、図８に示すように、対象グループと
して、たとえば、グループＤを選択し（処理Ｐ１）、グ
ループＤの深度を（０、０）に設定する。
ていないので、対象グループであるグループＣに対する
処理を終了し、グループＣと同じ深度のグループは存在
しないので、次に、図８に示すように、対象グループと
して、たとえば、グループＤを選択し（処理Ｐ１）、グ
ループＤの深度を（０、０）に設定する。
【００６８】そして、グループＤの隣接グループを検索
する（処理Ｐ２）。この場合、隣接グループとしてグル
ープＥが存在するので、グループＥを選択し（処理Ｐ
４）、グループＥの深度を求める（処理Ｐ５）。
する（処理Ｐ２）。この場合、隣接グループとしてグル
ープＥが存在するので、グループＥを選択し（処理Ｐ
４）、グループＥの深度を求める（処理Ｐ５）。
【００６９】グループＥは、親グループであるグループ
Ｄのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プ抽出の規準内の深度であり、かつ、グループＥは、対
象グループであるグループＤに関して過去にパス検索を
実行していないので、グループＥをグループＤの有効周
辺グループとする（処理Ｐ８）。
Ｄのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プ抽出の規準内の深度であり、かつ、グループＥは、対
象グループであるグループＤに関して過去にパス検索を
実行していないので、グループＥをグループＤの有効周
辺グループとする（処理Ｐ８）。
【００７０】次に、グループＥの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＡ、Ｃ、Ｄ、Ｆが存在するので、たとえば、グループ
Ａを選択し、グループＣ、Ｄ、Ｆをスタックに積み（処
理Ｐ４）、グループＡの深度を求める（処理Ｐ５）。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＡ、Ｃ、Ｄ、Ｆが存在するので、たとえば、グループ
Ａを選択し、グループＣ、Ｄ、Ｆをスタックに積み（処
理Ｐ４）、グループＡの深度を求める（処理Ｐ５）。
【００７１】グループＡは、親グループであるグループ
Ｅのファンイングループであるから、その深度は（１、
−１）となるが、深度（１、−１）は有効周辺グループ
抽出の基準内の深度であり、かつ、グループＡは、対象
グループであるグループＤに関して過去にパス検索を実
行していないので、グループＡをグループＤの有効周辺
グループとする（処理Ｐ８）。
Ｅのファンイングループであるから、その深度は（１、
−１）となるが、深度（１、−１）は有効周辺グループ
抽出の基準内の深度であり、かつ、グループＡは、対象
グループであるグループＤに関して過去にパス検索を実
行していないので、グループＡをグループＤの有効周辺
グループとする（処理Ｐ８）。
【００７２】次に、グループＡの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＢ、Ｅが存在するので、たとえば、グループＢを選択
し、グループＥをスタックに積み（処理Ｐ４）、グルー
プＢの深度を求める（処理Ｐ５）。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＢ、Ｅが存在するので、たとえば、グループＢを選択
し、グループＥをスタックに積み（処理Ｐ４）、グルー
プＢの深度を求める（処理Ｐ５）。
【００７３】グループＢは、親グループであるグループ
Ａのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の基準外の深度であるから、グループＢにつ
いての処理を終了してスタックからグループＥを抽出し
（処理Ｐ３）、グループＥの深度を求める（処理Ｐ
５）。
Ａのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の基準外の深度であるから、グループＢにつ
いての処理を終了してスタックからグループＥを抽出し
（処理Ｐ３）、グループＥの深度を求める（処理Ｐ
５）。
【００７４】グループＥは、親グループであるグループ
Ａのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の基準外の深度であるから、グループＥにつ
いての処理を終了してスタックからグループＣを抽出し
（処理Ｐ３）、グループＣの深度を求める（処理Ｐ
５）。
Ａのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の基準外の深度であるから、グループＥにつ
いての処理を終了してスタックからグループＣを抽出し
（処理Ｐ３）、グループＣの深度を求める（処理Ｐ
５）。
【００７５】グループＣは、親グループであるグループ
Ｅのファンアウトグループであるから、その深度は
（２、０）となるが、深度（２、０）は有効周辺グルー
プ抽出の規準外の深度であるので、グループＣについて
の処理を終了し、スタックからグループＤを抽出し（処
理Ｐ３）、グループＤの深度を求める（処理Ｐ５）。
Ｅのファンアウトグループであるから、その深度は
（２、０）となるが、深度（２、０）は有効周辺グルー
プ抽出の規準外の深度であるので、グループＣについて
の処理を終了し、スタックからグループＤを抽出し（処
理Ｐ３）、グループＤの深度を求める（処理Ｐ５）。
【００７６】グループＤは、親グループであるグループ
Ｅのファンイングループであるから、その深度は（１、
−１）となり、深度（１、−１）は有効周辺グループ抽
出の規準外の深度であるが、ファンアウト深度は０から
１に変化しており、新ファンアウト深度＞旧ファンアウ
ト深度となるので、グループＤについての処理を終了
し、スタックからグループＦを抽出し（処理Ｐ３）、グ
ループＦの深度を求める（処理Ｐ５）。
Ｅのファンイングループであるから、その深度は（１、
−１）となり、深度（１、−１）は有効周辺グループ抽
出の規準外の深度であるが、ファンアウト深度は０から
１に変化しており、新ファンアウト深度＞旧ファンアウ
ト深度となるので、グループＤについての処理を終了
し、スタックからグループＦを抽出し（処理Ｐ３）、グ
ループＦの深度を求める（処理Ｐ５）。
【００７７】グループＦは、親グループであるグループ
Ｅのファンアウトグループであるから、その深度は
（２、０）となるが、深度（２、０）は有効周辺グルー
プ抽出の規準外の深度であるので、処理Ｐ３に戻るが、
この場合、スタックにはグループが積まれていないの
で、対象グループであるグループＤに対する処理を終了
する。
Ｅのファンアウトグループであるから、その深度は
（２、０）となるが、深度（２、０）は有効周辺グルー
プ抽出の規準外の深度であるので、処理Ｐ３に戻るが、
この場合、スタックにはグループが積まれていないの
で、対象グループであるグループＤに対する処理を終了
する。
【００７８】ここに、グループＡのファンアウト深度お
よびファンイン深度の合計値は０となるので、グループ
Ｄと、グループＤと同一深度のグループＡとをまとめて
拡大グループとする（処理Ｐ９）。
よびファンイン深度の合計値は０となるので、グループ
Ｄと、グループＤと同一深度のグループＡとをまとめて
拡大グループとする（処理Ｐ９）。
【００７９】次に、図９に示すように、対象グループと
して、たとえば、グループＥを選択し（処理Ｐ１）、グ
ループＥの深度を（０、０）に設定する。
して、たとえば、グループＥを選択し（処理Ｐ１）、グ
ループＥの深度を（０、０）に設定する。
【００８０】次に、グループＥの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＡ、Ｃ、Ｄ、Ｆが存在するので、たとえば、グループ
Ａを選択し、グループＣ、Ｄ、Ｆをスタックに積み（処
理Ｐ４）、グループＡの深度を求める（処理Ｐ５）。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＡ、Ｃ、Ｄ、Ｆが存在するので、たとえば、グループ
Ａを選択し、グループＣ、Ｄ、Ｆをスタックに積み（処
理Ｐ４）、グループＡの深度を求める（処理Ｐ５）。
【００８１】グループＡは、親グループであるグループ
Ｅのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
抽出の規準外の深度であるので、グループＡについての
処理を終了してスタックからグループＣを抽出し（処理
Ｐ３）、グループＣの深度を求める（処理Ｐ５）。
Ｅのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
抽出の規準外の深度であるので、グループＡについての
処理を終了してスタックからグループＣを抽出し（処理
Ｐ３）、グループＣの深度を求める（処理Ｐ５）。
【００８２】グループＣは、親グループであるグループ
Ｅのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プ抽出の規準内の深度であり、かつ、グループＣは、対
象グループであるグループＥに関して過去にパス検索を
実行していないので、グループＣをグループＥの有効周
辺グループとする（処理Ｐ８）。
Ｅのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プ抽出の規準内の深度であり、かつ、グループＣは、対
象グループであるグループＥに関して過去にパス検索を
実行していないので、グループＣをグループＥの有効周
辺グループとする（処理Ｐ８）。
【００８３】次に、グループＣの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＢ、Ｅが存在するので、たとえば、グループＢを選択
し、グループＥをスタックに積み（処理Ｐ４）、グルー
プＢの深度を求める（処理Ｐ５）。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＢ、Ｅが存在するので、たとえば、グループＢを選択
し、グループＥをスタックに積み（処理Ｐ４）、グルー
プＢの深度を求める（処理Ｐ５）。
【００８４】グループＢは、親グループであるグループ
Ｃのファンイングループであるから、その深度は（１、
−１）となるが、深度（１、−１）は有効周辺グループ
抽出の規準内の深度であり、かつ、グループＢは、対象
グループであるグループＥに関して過去にパス検索を実
行していないので、グループＢをグループＥの有効周辺
グループとする（処理Ｐ８）。
Ｃのファンイングループであるから、その深度は（１、
−１）となるが、深度（１、−１）は有効周辺グループ
抽出の規準内の深度であり、かつ、グループＢは、対象
グループであるグループＥに関して過去にパス検索を実
行していないので、グループＢをグループＥの有効周辺
グループとする（処理Ｐ８）。
【００８５】次に、グループＢの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＡ、Ｃが存在するので、たとえば、グループＡを選択
し、グループＣをスタックに積み（処理Ｐ４）、グルー
プＡの深度を求める（処理Ｐ５）。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＡ、Ｃが存在するので、たとえば、グループＡを選択
し、グループＣをスタックに積み（処理Ｐ４）、グルー
プＡの深度を求める（処理Ｐ５）。
【００８６】グループＡは、親グループであるグループ
Ｂのファンイングループであるから、その深度は（１、
−２）となるが、深度（１、−２）は有効周辺グループ
抽出の規準外の深度であるから、グループＡについての
処理を終了してスタックからグループＣを抽出し（処理
Ｐ３）、グループＣの深度を求める（処理Ｐ５）。
Ｂのファンイングループであるから、その深度は（１、
−２）となるが、深度（１、−２）は有効周辺グループ
抽出の規準外の深度であるから、グループＡについての
処理を終了してスタックからグループＣを抽出し（処理
Ｐ３）、グループＣの深度を求める（処理Ｐ５）。
【００８７】グループＣは、親グループであるグループ
Ｂのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の規準外の深度であるから、グループＣにつ
いての処理を終了してスタックからグループＥを抽出し
（処理Ｐ３）、グループＥの深度を求める（処理Ｐ
５）。
Ｂのファンアウトグループであるから、その深度は
（２、−１）となるが、深度（２、−１）は有効周辺グ
ループ抽出の規準外の深度であるから、グループＣにつ
いての処理を終了してスタックからグループＥを抽出し
（処理Ｐ３）、グループＥの深度を求める（処理Ｐ
５）。
【００８８】グループＥは、親グループであるグループ
Ｃのファンイングループであるから、その深度は（１、
−１）となり、深度（１、−１）は有効周辺グループ抽
出の基準内の深度であるが、ファンアウト深度は、０か
ら１に変化しており、新ファンアウト深度＞旧ファンア
ウト深度となるので、グループＥについての処理を終了
してスタックからグループＤを抽出し（処理Ｐ３）、グ
ループＤの深度を求める（処理Ｐ５）。
Ｃのファンイングループであるから、その深度は（１、
−１）となり、深度（１、−１）は有効周辺グループ抽
出の基準内の深度であるが、ファンアウト深度は、０か
ら１に変化しており、新ファンアウト深度＞旧ファンア
ウト深度となるので、グループＥについての処理を終了
してスタックからグループＤを抽出し（処理Ｐ３）、グ
ループＤの深度を求める（処理Ｐ５）。
【００８９】グループＤは、親グループであるグループ
Ｅのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
抽出の規準外の深度であるので、グループＤについての
処理を終了してスタックからグループＦを抽出し（処理
Ｐ３）、グループＦの深度を求める（処理Ｐ５）。
Ｅのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
抽出の規準外の深度であるので、グループＤについての
処理を終了してスタックからグループＦを抽出し（処理
Ｐ３）、グループＦの深度を求める（処理Ｐ５）。
【００９０】グループＦは、親グループであるグループ
Ｅのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プ抽出の規準内の深度であり、かつ、グループＦは、対
象グループであるグループＥに関して過去にパス検索を
実行していないので、グループＦをグループＥの有効周
辺グループとする（処理Ｐ８）。
Ｅのファンアウトグループであるから、その深度は
（１、０）となるが、深度（１、０）は有効周辺グルー
プ抽出の規準内の深度であり、かつ、グループＦは、対
象グループであるグループＥに関して過去にパス検索を
実行していないので、グループＦをグループＥの有効周
辺グループとする（処理Ｐ８）。
【００９１】次に、グループＦの隣接グループを検索す
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＥが存在するので、グループＥを選択し（処理Ｐ
４）、グループＥの深度を求める（処理Ｐ５）。
る（処理Ｐ２）。この場合、隣接グループとしてグルー
プＥが存在するので、グループＥを選択し（処理Ｐ
４）、グループＥの深度を求める（処理Ｐ５）。
【００９２】グループＥは、親グループであるグループ
Ｆのファンイングループであるから、その深度は（１、
−１）となり、深度（１、−１）は有効周辺グループ抽
出の規準内の深度であるが、ファンアウト深度は、０か
ら１に変化しており、新ファンアウト深度＞旧ファンア
ウト深度となるので、グループＥについての処理を終了
し、処理Ｐ３に戻るが、この場合、スタックにはグルー
プが積まれていないので、対象グループであるグループ
Ｅに対する処理を終了する。
Ｆのファンイングループであるから、その深度は（１、
−１）となり、深度（１、−１）は有効周辺グループ抽
出の規準内の深度であるが、ファンアウト深度は、０か
ら１に変化しており、新ファンアウト深度＞旧ファンア
ウト深度となるので、グループＥについての処理を終了
し、処理Ｐ３に戻るが、この場合、スタックにはグルー
プが積まれていないので、対象グループであるグループ
Ｅに対する処理を終了する。
【００９３】ここに、グループＢのファンアウト深度お
よびファンイン深度の合計値は０となるので、グループ
Ｅと、グループＥと同一深度のグループＢとをまとめて
拡大グループとする（処理Ｐ９）。
よびファンイン深度の合計値は０となるので、グループ
Ｅと、グループＥと同一深度のグループＢとをまとめて
拡大グループとする（処理Ｐ９）。
【００９４】次に、図１０に示すように、対象グループ
としてグループＦを選択し（処理Ｐ１）、グループＦの
深度を（０、０）に設定する。
としてグループＦを選択し（処理Ｐ１）、グループＦの
深度を（０、０）に設定する。
【００９５】そして、グループＦの隣接グループを検索
する（処理Ｐ２）。この場合、隣接グループとしてグル
ープＥが存在するので、グループＥを選択し（処理Ｐ
４）、グループＥの深度を求める（処理Ｐ５）。
する（処理Ｐ２）。この場合、隣接グループとしてグル
ープＥが存在するので、グループＥを選択し（処理Ｐ
４）、グループＥの深度を求める（処理Ｐ５）。
【００９６】グループＥは、親グループであるグループ
Ｆのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
の規準外であるので、処理Ｐ３に戻るが、この場合、ス
タックにはグループが積まれていないので、対象グルー
プに対する処理を終了する。なお、この場合、グループ
Ｆとまとめて１個の拡大グループとするグループは存在
しないことになる。
Ｆのファンイングループであるから、その深度は（０、
−１）となるが、深度（０、−１）は有効周辺グループ
の規準外であるので、処理Ｐ３に戻るが、この場合、ス
タックにはグループが積まれていないので、対象グルー
プに対する処理を終了する。なお、この場合、グループ
Ｆとまとめて１個の拡大グループとするグループは存在
しないことになる。
【００９７】ここに、すべてのグループＡ〜Ｆを対象グ
ループとし、もはや、対象グループとすべきグループは
存在しないので、図３に示すように、拡大グループのマ
ージを行う（処理Ｐ１０）。
ループとし、もはや、対象グループとすべきグループは
存在しないので、図３に示すように、拡大グループのマ
ージを行う（処理Ｐ１０）。
【００９８】前述したように、同一のグループを有効周
辺グループとする複数のグループが存在する場合には、
これら複数のグループをまとめて１個の拡大グループと
し、その他のグループをそれぞれ１個の拡大グループと
し、同一のグループを有効周辺グループとする複数のグ
ループが存在しない場合には、各グループをそれぞれ１
個の拡大グループとすべきであるので、この例の場合に
は、図１１に示すように、４個の拡大グループＧ１、Ｇ
２、Ｇ３、Ｇ４が形成される。
辺グループとする複数のグループが存在する場合には、
これら複数のグループをまとめて１個の拡大グループと
し、その他のグループをそれぞれ１個の拡大グループと
し、同一のグループを有効周辺グループとする複数のグ
ループが存在しない場合には、各グループをそれぞれ１
個の拡大グループとすべきであるので、この例の場合に
は、図１１に示すように、４個の拡大グループＧ１、Ｇ
２、Ｇ３、Ｇ４が形成される。
【００９９】このように、拡大グループの最終的な設定
が終了した場合には、即ち、図１に示す処理Ｓ５が終了
した場合には、ファンイン側のグループの番号が若い番
号となるように、かつ、同一の拡大グループ内のグルー
プには同一の番号を付けるように、各グループに番号を
付ける（処理Ｓ６）。
が終了した場合には、即ち、図１に示す処理Ｓ５が終了
した場合には、ファンイン側のグループの番号が若い番
号となるように、かつ、同一の拡大グループ内のグルー
プには同一の番号を付けるように、各グループに番号を
付ける（処理Ｓ６）。
【０１００】たとえば、図１１に示すようなグループ
Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆに対して、図１２に示すよう
に、グループＡ、Ｄには番号１、グループＢ、Ｅには番
号２、グループＣには番号３、グループＦには番号４を
付ける。
Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆに対して、図１２に示すよう
に、グループＡ、Ｄには番号１、グループＢ、Ｅには番
号２、グループＣには番号３、グループＦには番号４を
付ける。
【０１０１】次に、ファンイン側のグループの回路シミ
ュレーション結果をファンアウト側のグループの入力デ
ータとして取り扱い、番号順に、即ち、拡大グループ内
のグループごとに、かつ、ファンイン側のグループから
順に、有効周辺グループを含めて回路シミュレーション
を行う（処理Ｓ７）。
ュレーション結果をファンアウト側のグループの入力デ
ータとして取り扱い、番号順に、即ち、拡大グループ内
のグループごとに、かつ、ファンイン側のグループから
順に、有効周辺グループを含めて回路シミュレーション
を行う（処理Ｓ７）。
【０１０２】たとえば、図１２に示す回路例において
は、まず、グループＡ、Ｄについて、グループＢ、Ｅを
含めて回路シミュレーションを行い、グループＡ、Ｄの
回路シミュレーション結果をグループＡ、Ｄの出力ノー
ドＮ１、Ｎ２、Ｎ３に得るようにする。
は、まず、グループＡ、Ｄについて、グループＢ、Ｅを
含めて回路シミュレーションを行い、グループＡ、Ｄの
回路シミュレーション結果をグループＡ、Ｄの出力ノー
ドＮ１、Ｎ２、Ｎ３に得るようにする。
【０１０３】次に、この回路シミュレーション結果以外
のデータをメモリ上から削除し、グループＢ、Ｅについ
てグループＣ、Ｆを含めて回路シミュレーションを行
い、グループＢ、Ｅの回路シミュレーション結果をグル
ープＢ、Ｅの出力ノードＮ４、Ｎ５、Ｎ６に得るように
するが、この回路例の場合には、最終段のグループＣ、
Ｆの回路シミュレーション結果もグループＣ、Ｆの出力
ノードＮ７、Ｎ８に得られることになる。
のデータをメモリ上から削除し、グループＢ、Ｅについ
てグループＣ、Ｆを含めて回路シミュレーションを行
い、グループＢ、Ｅの回路シミュレーション結果をグル
ープＢ、Ｅの出力ノードＮ４、Ｎ５、Ｎ６に得るように
するが、この回路例の場合には、最終段のグループＣ、
Ｆの回路シミュレーション結果もグループＣ、Ｆの出力
ノードＮ７、Ｎ８に得られることになる。
【０１０４】したがって、この回路例においては、グル
ープＣ、Ｆの出力ノードＮ７、Ｎ８に得られる回路シミ
ュレーション結果を出力して、全体回路１についての回
路シミュレーションを終了する。
ープＣ、Ｆの出力ノードＮ７、Ｎ８に得られる回路シミ
ュレーション結果を出力して、全体回路１についての回
路シミュレーションを終了する。
【０１０５】即ち、グループＣ、Ｆのファンアウト側に
更にグループが存在する場合には、グループＢ、Ｅの出
力ノードＮ４、Ｎ５、Ｎ６に得られるグループＢ、Ｅの
回路シミュレーション結果を残して、他のデータをメモ
リ上から削除し、続いて、グループＢ、Ｅの回路シミュ
レーション結果を使用してグループＣ、Ｆについて、グ
ループＣ、Ｆの有効周辺グループを含めて回路シミュレ
ーションを行うことになるが、この回路例では、グルー
プＣ、Ｆが最終段であり、これらグループＣ、Ｆについ
ての回路シミュレーションは既に実行しているので、こ
こで終了することになる。
更にグループが存在する場合には、グループＢ、Ｅの出
力ノードＮ４、Ｎ５、Ｎ６に得られるグループＢ、Ｅの
回路シミュレーション結果を残して、他のデータをメモ
リ上から削除し、続いて、グループＢ、Ｅの回路シミュ
レーション結果を使用してグループＣ、Ｆについて、グ
ループＣ、Ｆの有効周辺グループを含めて回路シミュレ
ーションを行うことになるが、この回路例では、グルー
プＣ、Ｆが最終段であり、これらグループＣ、Ｆについ
ての回路シミュレーションは既に実行しているので、こ
こで終了することになる。
【０１０６】以上のように、本発明の実施の一形態によ
れば、ファンイン側のグループの回路シミュレーション
結果をファンアウト側のグループの入力データとして取
り扱い、１個の拡大グループ内のグループごとに、か
つ、ファンイン側のグループから順に、出力に影響を与
えると考えられるファンアウト側の有効周辺グループを
含めて回路シミュレーションを行うとしているので、少
ないメモリ使用量で高精度の回路シミュレーションを高
速に行うことができる。
れば、ファンイン側のグループの回路シミュレーション
結果をファンアウト側のグループの入力データとして取
り扱い、１個の拡大グループ内のグループごとに、か
つ、ファンイン側のグループから順に、出力に影響を与
えると考えられるファンアウト側の有効周辺グループを
含めて回路シミュレーションを行うとしているので、少
ないメモリ使用量で高精度の回路シミュレーションを高
速に行うことができる。
【０１０７】また、グループは、全体回路を電源端子及
び結合の弱い箇所で切り離して複数のブロックに分割す
る工程と、ブロック間の信号の流れを調べ、信号がルー
プしている複数のブロックが存在する場合には、これら
複数のブロックをまとめて１個のグループとし、その他
のブロックをそれぞれ１個のグループとし、信号がルー
プしている複数のブロックが存在しない場合には、各ブ
ロックをそれぞれ１個のグループとする工程とを経て設
定するとしているので、好適なグループを効率的に抽出
することができる。
び結合の弱い箇所で切り離して複数のブロックに分割す
る工程と、ブロック間の信号の流れを調べ、信号がルー
プしている複数のブロックが存在する場合には、これら
複数のブロックをまとめて１個のグループとし、その他
のブロックをそれぞれ１個のグループとし、信号がルー
プしている複数のブロックが存在しない場合には、各ブ
ロックをそれぞれ１個のグループとする工程とを経て設
定するとしているので、好適なグループを効率的に抽出
することができる。
【０１０８】また、有効周辺グループは、グループを順
に対象グループとして選択し、対象グループから他のグ
ループまでのグループ間を結ぶパスを数え、その数を対
象グループに対する他のグループの深度とし、この深度
が指定した深度よりも小さいグループを対象グループの
有効周辺グループとして抽出することにより行うとして
いるので、好適な有効周辺グループを効率的に抽出する
ことができる。
に対象グループとして選択し、対象グループから他のグ
ループまでのグループ間を結ぶパスを数え、その数を対
象グループに対する他のグループの深度とし、この深度
が指定した深度よりも小さいグループを対象グループの
有効周辺グループとして抽出することにより行うとして
いるので、好適な有効周辺グループを効率的に抽出する
ことができる。
【０１０９】なお、本発明の実施の一形態は、仮想メモ
リ装置として、たとえば、磁気ディスク装置、実メモリ
装置として、たとえば、半導体記憶装置、演算装置とし
て、いわゆるＣＰＵを備える既存の回路シミュレーショ
ン装置を使用し、回路シミュレーションに必要な全体回
路のデータを磁気ディスク装置に格納し、磁気ディスク
装置から回路シミュレーションに必要なグループのデー
タを半導体記憶装置に読み込み、半導体記憶装置に読み
込まれたグループのデータを使用した回路シミュレーシ
ョンに必要な演算をＣＰＵで行うことにより実行するこ
とができ、特別な回路シミュレーション装置を必要とし
ない。
リ装置として、たとえば、磁気ディスク装置、実メモリ
装置として、たとえば、半導体記憶装置、演算装置とし
て、いわゆるＣＰＵを備える既存の回路シミュレーショ
ン装置を使用し、回路シミュレーションに必要な全体回
路のデータを磁気ディスク装置に格納し、磁気ディスク
装置から回路シミュレーションに必要なグループのデー
タを半導体記憶装置に読み込み、半導体記憶装置に読み
込まれたグループのデータを使用した回路シミュレーシ
ョンに必要な演算をＣＰＵで行うことにより実行するこ
とができ、特別な回路シミュレーション装置を必要とし
ない。
【０１１０】
【発明の効果】本発明中、第１の発明（請求項１記載の
回路シミュレーション方法）によれば、少ないメモリ使
用量で高精度の回路シミュレーションを高速に行うこと
ができる。
回路シミュレーション方法）によれば、少ないメモリ使
用量で高精度の回路シミュレーションを高速に行うこと
ができる。
【０１１１】また、第２の発明（請求項２記載の回路シ
ミュレーション方法）によれば、好適なグループを効率
的に抽出し、少ないメモリ使用量で高精度の回路シミュ
レーションを高速に行うことができる。
ミュレーション方法）によれば、好適なグループを効率
的に抽出し、少ないメモリ使用量で高精度の回路シミュ
レーションを高速に行うことができる。
【０１１２】また、第３の発明（請求項３記載の回路シ
ミュレーション方法）によれば、拡大グループごとの回
路シミュレーションを効率的に行い、少ないメモリ使用
量で高精度の回路シミュレーションを高速に行うことが
できる。
ミュレーション方法）によれば、拡大グループごとの回
路シミュレーションを効率的に行い、少ないメモリ使用
量で高精度の回路シミュレーションを高速に行うことが
できる。
【０１１３】また、第４の発明（請求項４記載の回路シ
ミュレーション方法）によれば、有効周辺グループを効
率的に抽出し、少ないメモリ使用量で高精度の回路シミ
ュレーションを高速に行うことができる。
ミュレーション方法）によれば、有効周辺グループを効
率的に抽出し、少ないメモリ使用量で高精度の回路シミ
ュレーションを高速に行うことができる。
【０１１４】また、第５の発明（請求項５記載の回路シ
ミュレーション方法）によれば、特別な回路シミュレー
ション装置を必要とせず、既存の回路シミュレーション
装置を使用して、第１、第２、第３又は第４の発明の回
路シミュレーション方法を実行することができる。
ミュレーション方法）によれば、特別な回路シミュレー
ション装置を必要とせず、既存の回路シミュレーション
装置を使用して、第１、第２、第３又は第４の発明の回
路シミュレーション方法を実行することができる。
【図１】本発明の実施の一形態を示すフローチャートで
ある。
ある。
【図２】本発明の実施の一形態で行われる全体回路のブ
ロック化、グループ化を説明するための図である。
ロック化、グループ化を説明するための図である。
【図３】本発明の実施の一形態で行われる有効周辺グル
ープおよび拡大グループの抽出アルゴリズムを示すフロ
ーチャートである。
ープおよび拡大グループの抽出アルゴリズムを示すフロ
ーチャートである。
【図４】本発明の実施の一形態におけるグループの深度
の表示方法を示す図である。
の表示方法を示す図である。
【図５】本発明の実施の一形態で行われる有効周辺グル
ープおよび拡大グループの抽出アルゴリズムを説明する
ための図である。
ープおよび拡大グループの抽出アルゴリズムを説明する
ための図である。
【図６】本発明の実施の一形態で行われる有効周辺グル
ープおよび拡大グループの抽出アルゴリズムを説明する
ための図である。
ープおよび拡大グループの抽出アルゴリズムを説明する
ための図である。
【図７】本発明の実施の一形態で行われる有効周辺グル
ープおよび拡大グループの抽出アルゴリズムを説明する
ための図である。
ープおよび拡大グループの抽出アルゴリズムを説明する
ための図である。
【図８】本発明の実施の一形態で行われる有効周辺グル
ープおよび拡大グループの抽出アルゴリズムを説明する
ための図である。
ープおよび拡大グループの抽出アルゴリズムを説明する
ための図である。
【図９】本発明の実施の一形態で行われる有効周辺グル
ープおよび拡大グループの抽出アルゴリズムを説明する
ための図である。
ープおよび拡大グループの抽出アルゴリズムを説明する
ための図である。
【図１０】本発明の実施の一形態で行われる有効周辺グ
ループおよび拡大グループの抽出アルゴリズムを説明す
るための図である。
ループおよび拡大グループの抽出アルゴリズムを説明す
るための図である。
【図１１】本発明の実施の一形態で行われる拡大グルー
プの設定を説明するための図である。
プの設定を説明するための図である。
【図１２】本発明の実施の一形態で行われるグループに
対する番号付けおよび回路シミュレーション方法を説明
するための図である。
対する番号付けおよび回路シミュレーション方法を説明
するための図である。
１ 全体回路 ａ〜ｉ ブロック Ａ〜Ｆ グループ Ｇ１〜Ｇ４ 拡大グループ
Claims (5)
- 【請求項１】回路シミュレーションの対象である全体回
路を複数のグループに分割する工程と、 ファンイン側のグループの回路シミュレーション結果を
ファンアウト側のグループの入力データとして取り扱
い、ファンアウト側に、同一のグループを、出力に影響
を与えると考えられるグループとして有する複数のグル
ープは、これら複数のグループごとに、その他のグルー
プは、グループごとに、それぞれ、その出力に影響を及
ぼすと考えられるファンアウト側のグループを含めて回
路シミュレーションを行う工程とを含んでいることを特
徴とする回路シミュレーション方法。 - 【請求項２】前記回路シミュレーションの対象である全
体回路を複数のグループに分割する工程は、 前記全体回路を電源端子及び結合の弱い箇所で切り離し
て複数のブロックに分割する工程と、 ブロック間の信号の流れを調べ、信号がループしている
複数のブロックが存在する場合には、これら複数のブロ
ックをまとめて１個のグループとし、その他のブロック
をそれぞれ１個のグループとし、信号がループしている
複数のブロックが存在しない場合には、各ブロックをそ
れぞれ１個のグループとする工程とを含んでいることを
特徴とする請求項１記載の回路シミュレーション方法。 - 【請求項３】前記ファンイン側のグループの回路シミュ
レーション結果をファンアウト側のグループの入力デー
タとして取り扱い、ファンアウト側に、同一のグループ
を、出力に影響を与えると考えられるグループとして有
する複数のグループは、これら複数のグループごとに、
その他のグループは、グループごとに、それぞれ、その
出力に影響を及ぼすと考えられるファンアウト側のグル
ープを含めて回路シミュレーションを行う工程は、 各グループごとに、その出力に影響を及ぼすと考えられ
るグループを有効周辺グループとして抽出する工程と、 同一のグループをファンアウト側の有効周辺グループと
する複数のグループが存在する場合には、これら複数の
グループをまとめて１個の拡大グループとし、その他の
グループをそれぞれ１個の拡大グループとし、同一のグ
ループをファンアウト側の有効周辺グループとする複数
のグループが存在しない場合には、各グループをそれぞ
れ１個の拡大グループとする工程と、 １個の拡大グループ内のグループごとに、かつ、ファン
イン側のグループから順に、拡大グループ内のグループ
のファンアウト側の有効周辺グループを含めて回路シミ
ュレーションを行う工程とを含んでいることを特徴とす
る請求項１又は２記載の回路シミュレーション方法。 - 【請求項４】前記各グループごとに、その出力に影響を
及ぼすと考えられるグループを有効周辺グループとして
抽出する工程は、 グループを１個ずつ対象グループとして選択し、前記対
象グループから他のグループまでのグループ間を結ぶパ
スをたどり、順方向の信号の流れをもつパスの数を数
え、その数を前記対象グループに対する前記他のグルー
プの深度とし、この深度が予め指定した深度よりも小さ
いグループを前記対象グループの有効周辺グループとし
て抽出する工程を含んでいることを特徴とする請求項３
記載の回路シミュレーション方法。 - 【請求項５】回路シミュレーションに必要な全体回路の
データを仮想メモリ装置に格納し、この仮想メモリ装置
から回路シミュレーションに必要なグループのデータを
実メモリ装置に読み込み、この実メモリ装置に読み込ま
れたグループのデータを使用した回路シミュレーション
に必要な演算を演算装置で行い、前記全体回路について
回路シミュレーションを行うことを特徴とする請求項
１、２、３又は４記載の回路シミュレーション方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP8062276A JPH09259151A (ja) | 1996-03-19 | 1996-03-19 | 回路シミュレーション方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP8062276A JPH09259151A (ja) | 1996-03-19 | 1996-03-19 | 回路シミュレーション方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH09259151A true JPH09259151A (ja) | 1997-10-03 |
Family
ID=13195466
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP8062276A Withdrawn JPH09259151A (ja) | 1996-03-19 | 1996-03-19 | 回路シミュレーション方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH09259151A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7721234B2 (en) | 2006-02-09 | 2010-05-18 | Renesas Technology Corp. | Simulation method and simulation program |
-
1996
- 1996-03-19 JP JP8062276A patent/JPH09259151A/ja not_active Withdrawn
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7721234B2 (en) | 2006-02-09 | 2010-05-18 | Renesas Technology Corp. | Simulation method and simulation program |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7017132B2 (en) | Methodology to optimize hierarchical clock skew by clock delay compensation | |
| US6654938B2 (en) | Delay characteristic analyzing method and delay characteristic analyzing system for a custom LSI | |
| Pomeranz et al. | An efficient nonenumerative method to estimate the path delay fault coverage in combinational circuits | |
| US6006023A (en) | Method of optimizing a logic circuit | |
| US6292924B1 (en) | Modifying timing graph to avoid given set of paths | |
| US6000038A (en) | Parallel processing of Integrated circuit pin arrival times | |
| JPH09259151A (ja) | 回路シミュレーション方法 | |
| JPH09321145A (ja) | 半導体集積回路のレイアウト方法 | |
| JP3766119B2 (ja) | 回路シミュレーション方法及びその装置 | |
| KR20010024944A (ko) | 전자 소자 및 장치의 설계 및 제조 방법 | |
| CN112084742B (zh) | 集成电路设计方法与其非瞬时计算机可读介质 | |
| CN116776791B (zh) | 消除公共路径悲观度的静态时序分析方法 | |
| US7010765B2 (en) | Method for identifying removable inverters in an IC design | |
| Pomeranz et al. | Procedures for static compaction of test sequences for synchronous sequential circuits | |
| US6463572B1 (en) | IC timing analysis with known false paths | |
| JP3080037B2 (ja) | 論理シミュレーション用モデルの作成方法 | |
| JPH06310601A (ja) | レイアウト設計方法 | |
| Kang et al. | Accurate logic simulation by overcoming the unknown value propagation problem | |
| JPH0195365A (ja) | クリティカルパスの解析処理方式 | |
| JP3012546B2 (ja) | シミュレーション装置及びその方法 | |
| JP2786017B2 (ja) | 半導体集積回路の製造方法 | |
| JPH09259172A (ja) | 論理シミュレーション用モデルの作成方法 | |
| JPH06110963A (ja) | パスの遅延値自動算出方法 | |
| JPH06119411A (ja) | 論理回路の遅延経路探索方法 | |
| JPH10256377A (ja) | フロアプラン方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20030603 |