JPH0916640A - 回路シミュレータ及びブロック緩和反復シミュレーション方法 - Google Patents
回路シミュレータ及びブロック緩和反復シミュレーション方法Info
- Publication number
- JPH0916640A JPH0916640A JP7168250A JP16825095A JPH0916640A JP H0916640 A JPH0916640 A JP H0916640A JP 7168250 A JP7168250 A JP 7168250A JP 16825095 A JP16825095 A JP 16825095A JP H0916640 A JPH0916640 A JP H0916640A
- Authority
- JP
- Japan
- Prior art keywords
- circuit
- external
- partial
- external node
- nodes
- 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
【０００１】
【産業上の利用分野】本発明は、回路シミュレータ及び
シミュレーション方法に関し、特に、大規模集積回路の
ように非線形な大規模回路やシステムの数値シミュレー
ションを、計算機を用いて行う場合に適用して好適なも
のである。
シミュレーション方法に関し、特に、大規模集積回路の
ように非線形な大規模回路やシステムの数値シミュレー
ションを、計算機を用いて行う場合に適用して好適なも
のである。
【０００２】
【従来の技術】集積回路などを製造する場合、その電気
特性を十分に検証しておくことが必要であり、計算機に
よる回路動作の数値シミュレーションが不可欠となって
いる。しかしながら、集積回路の高密度化や大規模化に
伴い、１つの回路のシミュレーションにかかる時間は非
常に長大化し、特に複雑な非線形特性のため、ニュート
ン法による線形化方程式をＬＵ分解法などの直接法行列
求解に基づいて解く場合に時間がかかるようになってき
た。
特性を十分に検証しておくことが必要であり、計算機に
よる回路動作の数値シミュレーションが不可欠となって
いる。しかしながら、集積回路の高密度化や大規模化に
伴い、１つの回路のシミュレーションにかかる時間は非
常に長大化し、特に複雑な非線形特性のため、ニュート
ン法による線形化方程式をＬＵ分解法などの直接法行列
求解に基づいて解く場合に時間がかかるようになってき
た。
【０００３】このため、従来の回路シミュレータは、非
線形な大規模回路を正確で高速にシュミレートするた
め、複数のプロセッサを相互に接続した並列計算機シス
テムを用いて並列処理を行っていた。例えば、図１４に
示すように、対象となる回路を部分回路ｉ、ｊ、ｋに分
割し、境界となる外部節点Ｐi 、Ｐj 、Ｐk に外部節点
電圧ｖi 、ｖj 、ｖk を与えて、各部分回路ｉ、ｊ、ｋ
の解析するブロック緩和反復シミュレーション法が用い
られていた。
線形な大規模回路を正確で高速にシュミレートするた
め、複数のプロセッサを相互に接続した並列計算機シス
テムを用いて並列処理を行っていた。例えば、図１４に
示すように、対象となる回路を部分回路ｉ、ｊ、ｋに分
割し、境界となる外部節点Ｐi 、Ｐj 、Ｐk に外部節点
電圧ｖi 、ｖj 、ｖk を与えて、各部分回路ｉ、ｊ、ｋ
の解析するブロック緩和反復シミュレーション法が用い
られていた。
【０００４】すなわち、このブロック緩和反復シミュレ
ーション法は、図１５のステップＳ１に示すように、対
象となる回路を部分回路ｉ、ｊ、ｋに分割し、ステップ
Ｓ２で部分回路ｉ、ｊ、ｋのロードを行い、ステップＳ
３で外部節点電圧ｖi 、ｖj、ｖk の設定を行う。
ーション法は、図１５のステップＳ１に示すように、対
象となる回路を部分回路ｉ、ｊ、ｋに分割し、ステップ
Ｓ２で部分回路ｉ、ｊ、ｋのロードを行い、ステップＳ
３で外部節点電圧ｖi 、ｖj、ｖk の設定を行う。
【０００５】次に、ステップＳ４に示すように、部分回
路ｉ、ｊ、ｋの解析を各部分回路ｉ、ｊ、ｋに対応して
設けられたプロセッサＰＥi 、ＰＥj 、ＰＥk で並列に
行う。
路ｉ、ｊ、ｋの解析を各部分回路ｉ、ｊ、ｋに対応して
設けられたプロセッサＰＥi 、ＰＥj 、ＰＥk で並列に
行う。
【０００６】次に、ステップＳ５に示すように、ステッ
プＳ４の部分回路ｉ、ｊ、ｋの解析で求めた外部節点電
圧ｖi ´、ｖj ´、ｖk ´が、ステップＳ３で設定した
外部節点電圧ｖi 、ｖj 、ｖk に収束するかどうかの判
断を行い、収束しない場合はステップＳ３に戻り、収束
するまでステップＳ３〜Ｓ５の動作を繰り返す。
プＳ４の部分回路ｉ、ｊ、ｋの解析で求めた外部節点電
圧ｖi ´、ｖj ´、ｖk ´が、ステップＳ３で設定した
外部節点電圧ｖi 、ｖj 、ｖk に収束するかどうかの判
断を行い、収束しない場合はステップＳ３に戻り、収束
するまでステップＳ３〜Ｓ５の動作を繰り返す。
【０００７】次に、ステップＳ３〜Ｓ５の動作を図１６
を参照しながらより詳しく説明する。図１４のような回
路に対して、（１）式に示すような線形連立方程式が成
立する。
を参照しながらより詳しく説明する。図１４のような回
路に対して、（１）式に示すような線形連立方程式が成
立する。
【０００８】
【数１】
【０００９】ここで、 Ａi ：部分回路ｉの内部節点間のアドミタンス回路行列 Ｂi ：部分回路ｉの内部節点と外部節点との間のアドミ
タンス回路行列 Ｃi ：部分回路ｉの外部節点と内部節点との間のアドミ
タンス回路行列 Ｄ ：外部回路の外部節点間のアドミタンス回路行列 ｘi ：部分回路ｉの内部（節点電圧）変数ベクトル ｖ ：外部（節点電圧）変数ベクトル ｂi ：部分回路ｉの内部（電流源）電源ベクトル ｄ ：外部（電流源）電源ベクトルである。
タンス回路行列 Ｃi ：部分回路ｉの外部節点と内部節点との間のアドミ
タンス回路行列 Ｄ ：外部回路の外部節点間のアドミタンス回路行列 ｘi ：部分回路ｉの内部（節点電圧）変数ベクトル ｖ ：外部（節点電圧）変数ベクトル ｂi ：部分回路ｉの内部（電流源）電源ベクトル ｄ ：外部（電流源）電源ベクトルである。
【００１０】この（１）式は、以下の（２）〜（６）式
に展開される。 Ａ1 ｘ1 ＋Ｂ1 ｖ＝ｂ1 ・・・（２）式 Ａ2 ｘ2 ＋Ｂ2 ｖ＝ｂ2 ・・・（３）式 ： Ａi ｘi ＋Ｂi ｖ＝ｂi ・・・（４）式 ： Ａn ｘn ＋Ｂn ｖ＝ｂn ・・・（５）式 Ｄｖ＝ｄ−（Ｃ1 ｘ1 ＋Ｃ2 ｘ2 ＋・・・＋Ｃn Ｘn ）・・・（６）式 まず、図１６のステップＳ１００で外部変数ベクトルｖ
に初期値ｖ0 を設定する。
に展開される。 Ａ1 ｘ1 ＋Ｂ1 ｖ＝ｂ1 ・・・（２）式 Ａ2 ｘ2 ＋Ｂ2 ｖ＝ｂ2 ・・・（３）式 ： Ａi ｘi ＋Ｂi ｖ＝ｂi ・・・（４）式 ： Ａn ｘn ＋Ｂn ｖ＝ｂn ・・・（５）式 Ｄｖ＝ｄ−（Ｃ1 ｘ1 ＋Ｃ2 ｘ2 ＋・・・＋Ｃn Ｘn ）・・・（６）式 まず、図１６のステップＳ１００で外部変数ベクトルｖ
に初期値ｖ0 を設定する。
【００１１】次に、ステップＳ１０１〜Ｓ１０ｎに示す
ように、ステップＳ１００で与えられた外部変数ベクト
ルｖに対して、各プロセッサＰＥ1 〜ＰＥn で（２）式
〜（５）式を解析することにより、各部分回路１〜ｎの
内部変数ベクトルｘ1 〜ｘnを求める。そして、内部変
数ベクトルｘ1 〜ｘn が所定の値に収束している場合、
ホスト計算機に内部変数ベクトルｘ1 〜ｘn を送信す
る。
ように、ステップＳ１００で与えられた外部変数ベクト
ルｖに対して、各プロセッサＰＥ1 〜ＰＥn で（２）式
〜（５）式を解析することにより、各部分回路１〜ｎの
内部変数ベクトルｘ1 〜ｘnを求める。そして、内部変
数ベクトルｘ1 〜ｘn が所定の値に収束している場合、
ホスト計算機に内部変数ベクトルｘ1 〜ｘn を送信す
る。
【００１２】次に、ステップＳ２００、Ｓ２１０に示す
ように、ホスト計算機では、各プロセッサＰＥ1 〜ＰＥ
n から送信された内部変数ベクトルｘ1 〜ｘn に基づい
て、（６）式の解析により外部変数ベクトルｖを求め
る。そして、ステップＳ２２０に示すように、外部変数
ベクトルｖが収束したかどうかを判定する。
ように、ホスト計算機では、各プロセッサＰＥ1 〜ＰＥ
n から送信された内部変数ベクトルｘ1 〜ｘn に基づい
て、（６）式の解析により外部変数ベクトルｖを求め
る。そして、ステップＳ２２０に示すように、外部変数
ベクトルｖが収束したかどうかを判定する。
【００１３】次に、ステップＳ２３０に示すように、求
めた外部変数ベクトルｖが初期値ｖ0 に十分近くない場
合、ステップＳ１００に戻り、この求めた外部変数ベク
トルｖを初期値ｖ0 として以上の処理を繰り返す。
めた外部変数ベクトルｖが初期値ｖ0 に十分近くない場
合、ステップＳ１００に戻り、この求めた外部変数ベク
トルｖを初期値ｖ0 として以上の処理を繰り返す。
【００１４】
【発明が解決しようとする課題】従来のブロック緩和反
復シミュレーション法は、シミュレーションを行う対象
回路が同一の場合においても、回路の分割方法や緩和反
復する変数の選択法により、反復の収束速度が大きく異
なっていた。そのため、ブロック緩和反復シミュレーシ
ョンを並列処理で効率よく行うためには、ブロックの大
きさの均等化やブロック間の通信量の最小化が必要とさ
れていた。
復シミュレーション法は、シミュレーションを行う対象
回路が同一の場合においても、回路の分割方法や緩和反
復する変数の選択法により、反復の収束速度が大きく異
なっていた。そのため、ブロック緩和反復シミュレーシ
ョンを並列処理で効率よく行うためには、ブロックの大
きさの均等化やブロック間の通信量の最小化が必要とさ
れていた。
【００１５】例えば、解くべき行列Ａを、 Ａ＝Ｂ−Ｃ ・・・（７）式 の形式に分ける。ここで、行列Ｂは、 Ｂｘ＝ｄ ・・・（８）式 を容易に解くことができる行列、例えば、対角行列や下
三角行列である。
三角行列である。
【００１６】なお、 Ａ＝Ｌ＋Ｄ＋Ｕ ・・・（９）式 とすると、ガウス−ヤコビ法では、Ｂ＝Ｄ、Ｃ＝−（Ｌ
＋Ｕ）となり、ガウス−ザイデル法では、Ｂ＝（Ｌ＋
Ｄ）、Ｃ＝−Ｕとなる。また、Ｌは下三角行列、Ｄは対
角行列、Ｕは上三角行列を表している。
＋Ｕ）となり、ガウス−ザイデル法では、Ｂ＝（Ｌ＋
Ｄ）、Ｃ＝−Ｕとなる。また、Ｌは下三角行列、Ｄは対
角行列、Ｕは上三角行列を表している。
【００１７】ここで、 ｘk+1 ＝−Ｂ-1ｃｘk ＋ｃ-1ｂ ・・・（１０）式 の緩和反復が収束するための条件は、 スペクトル半径ρ（Ｂ-1Ｃ）＜１ ・・・（１１）式 である。
【００１８】次に、２次元の行列で変数の接続度を考え
る。
る。
【００１９】
【数２】
【００２０】（１２）式において、ガウス−ザイデル法
では、スペクトル半径ρ（Ｂ-1Ｃ）は（１３）式のよう
になる。
では、スペクトル半径ρ（Ｂ-1Ｃ）は（１３）式のよう
になる。
【００２１】
【数３】
【００２２】（１３）式において、ａ12とａ21が、ａ11
とａ22に比べて大きい時、密結合である。また、ａ12と
ａ21が、ａ11とａ22に比べて小さい時、疎結合である。
特に、ａ12＝０の時、ρ（Ｂ-1Ｃ）＝０となり１回で収
束する。
とａ22に比べて大きい時、密結合である。また、ａ12と
ａ21が、ａ11とａ22に比べて小さい時、疎結合である。
特に、ａ12＝０の時、ρ（Ｂ-1Ｃ）＝０となり１回で収
束する。
【００２３】次に、上述の概念をブロックに拡張し、ブ
ロックｘ1 、ｘ2 、ｘ3 が図１７に示すように結合した
状態を考える。
ロックｘ1 、ｘ2 、ｘ3 が図１７に示すように結合した
状態を考える。
【００２４】
【数４】
【００２５】（１４）式において、ｘ2 とｘ3 は密結合
しているので、ｘ2 とｘ3 をブロック化し、ガウス−ザ
イデル法を用いるために変数の順序を（１５）式によう
に並べ換える。
しているので、ｘ2 とｘ3 をブロック化し、ガウス−ザ
イデル法を用いるために変数の順序を（１５）式によう
に並べ換える。
【００２６】
【数５】
【００２７】（１５）式において、ｘ2 とｘ3 のブロッ
ク、
ク、
【００２８】
【数６】
【００２９】すなわち、（１６）式を直接法行列求解で
解けば、元の行列は１回の緩和反復で解くことができ
る。このように、変数の分割方法は、緩和反復の収束速
度に大きく影響する。
解けば、元の行列は１回の緩和反復で解くことができ
る。このように、変数の分割方法は、緩和反復の収束速
度に大きく影響する。
【００３０】しかしながら、従来のシミュレーション方
法では、対象回路を部分的に最適化する方法は考えられ
ていたが、回路の分割方法、緩和反復する変数の選択
法、或いは並列処理の効率化を回路全体から見て体系的
に行うようにしたシミュレーション方法は考えられてい
なかった。
法では、対象回路を部分的に最適化する方法は考えられ
ていたが、回路の分割方法、緩和反復する変数の選択
法、或いは並列処理の効率化を回路全体から見て体系的
に行うようにしたシミュレーション方法は考えられてい
なかった。
【００３１】そこで、本発明の目的は、対象回路全体か
ら見た回路の分割や緩和変数の選択を最適化することに
より、ブロック緩和反復シミュレーション法の収束効率
を向上させることができる回路シミュレータ及びシミュ
レーション方法を提供することである。
ら見た回路の分割や緩和変数の選択を最適化することに
より、ブロック緩和反復シミュレーション法の収束効率
を向上させることができる回路シミュレータ及びシミュ
レーション方法を提供することである。
【００３２】
【課題を解決するための手段】上述した課題を解決する
ために、対象回路を複数の部分回路に分割し、分割した
各部分回路を接続する外部節点の選択を対象回路内に信
号が伝わる順序で求め、外部節点の電位及び前記各部分
回路の内部節点の電圧を並列的に求める。
ために、対象回路を複数の部分回路に分割し、分割した
各部分回路を接続する外部節点の選択を対象回路内に信
号が伝わる順序で求め、外部節点の電位及び前記各部分
回路の内部節点の電圧を並列的に求める。
【００３３】部分回路を複数のプロセッサに割り当てて
並列に処理する。点・ブロック緩和法では、反復の各ス
テップで内部節点及び外部節点の電位をＬＵ分解法によ
り求める。
並列に処理する。点・ブロック緩和法では、反復の各ス
テップで内部節点及び外部節点の電位をＬＵ分解法によ
り求める。
【００３４】外部節点方程式を解く緩和法では、プロセ
ッサ内の処理をガウス−ザイデル法で行い、プロセッサ
間の処理をガウス−ヤコビ法で行う。一方、ブロック緩
和法では、複数のプロセッサを相互に接続した並列計算
機を用いて、対象回路網を外部節点で接続される部分回
路に分割して解析する機構を有するシステムにおいて、
信号入力端子を始点、信号出力端子を終点とする回路グ
ループ間の信号伝播フローグラフを抽出し、信号伝播フ
ローグラフを深さ方向優先に辿って外部節点を抽出し
て、外部節点に初期電位を与えて、前記初期電位を用い
て求まる各部分回路への入力電流を用いて各部分回路を
各プロセッサで並列に直接法を用いて解析して、新たに
外部節点の電位を求める手続きを前記外部節点の電位の
変化が許容以下になるまで繰り返す。
ッサ内の処理をガウス−ザイデル法で行い、プロセッサ
間の処理をガウス−ヤコビ法で行う。一方、ブロック緩
和法では、複数のプロセッサを相互に接続した並列計算
機を用いて、対象回路網を外部節点で接続される部分回
路に分割して解析する機構を有するシステムにおいて、
信号入力端子を始点、信号出力端子を終点とする回路グ
ループ間の信号伝播フローグラフを抽出し、信号伝播フ
ローグラフを深さ方向優先に辿って外部節点を抽出し
て、外部節点に初期電位を与えて、前記初期電位を用い
て求まる各部分回路への入力電流を用いて各部分回路を
各プロセッサで並列に直接法を用いて解析して、新たに
外部節点の電位を求める手続きを前記外部節点の電位の
変化が許容以下になるまで繰り返す。
【００３５】信号入力端子を始点、信号出力端子を終点
とする回路グループ間の信号伝播フローグラフを抽出
し、この信号伝播フローグラフから外部節点のみを残し
た非連結の外部節点グラフを抽出し、所定よりも多い外
部節点の部分グラフは所定以下になるまで細分化し、各
部分グラフに対して、その部分グラフを構成する外部節
点と同じ外部節点を一番多く持つ部分回路に組み込んで
反復求解する。
とする回路グループ間の信号伝播フローグラフを抽出
し、この信号伝播フローグラフから外部節点のみを残し
た非連結の外部節点グラフを抽出し、所定よりも多い外
部節点の部分グラフは所定以下になるまで細分化し、各
部分グラフに対して、その部分グラフを構成する外部節
点と同じ外部節点を一番多く持つ部分回路に組み込んで
反復求解する。
【００３６】対象回路を複数の部分回路に分割し、接続
度の一番大きな部分回路に外部節点を組み込む。接続度
は、部分回路の外部節点数とその部分回路に合致する外
部節点数との割合である。
度の一番大きな部分回路に外部節点を組み込む。接続度
は、部分回路の外部節点数とその部分回路に合致する外
部節点数との割合である。
【００３７】対象回路を複数の部分回路に分割し、部分
回路が最も多く接続している外部節点を、その外部節点
が接続している全ての部分回路に組み込む。トランジス
タグループの接続関係に基づいて、入力端子から出力端
子までの信号の流れる方向を認識する信号伝播フローグ
ラフ抽出手段と、信号伝播フローグラフ抽出手段の出力
に基づいて、部分回路の解析を行う解析手段とを備え
る。
回路が最も多く接続している外部節点を、その外部節点
が接続している全ての部分回路に組み込む。トランジス
タグループの接続関係に基づいて、入力端子から出力端
子までの信号の流れる方向を認識する信号伝播フローグ
ラフ抽出手段と、信号伝播フローグラフ抽出手段の出力
に基づいて、部分回路の解析を行う解析手段とを備え
る。
【００３８】解析手段は、部分回路と同数のプロセッサ
により並列に解析を行う。部分回路を接続する外部節点
を、接続度の一番大きな部分回路に組み込む組み込み手
段と、組み込み手段により外部節点を組み込んだ部分回
路の解析を行う解析手段とを備える。
により並列に解析を行う。部分回路を接続する外部節点
を、接続度の一番大きな部分回路に組み込む組み込み手
段と、組み込み手段により外部節点を組み込んだ部分回
路の解析を行う解析手段とを備える。
【００３９】
【作用】各部分回路の抽出と、分割した各部分回路を接
続する外部節点の選択を、対象回路内に信号が伝わる順
序で求めることにより、各部分回路を解析する際の収束
効率が向上し、シミュレーションを行う時間を短くする
ことができる。
続する外部節点の選択を、対象回路内に信号が伝わる順
序で求めることにより、各部分回路を解析する際の収束
効率が向上し、シミュレーションを行う時間を短くする
ことができる。
【００４０】部分回路を複数のプロセッサに割り当てて
並列に直接法又は緩和法で処理することにより、シミュ
レーションを行う時間をより一層短くすることができ
る。点・ブロック緩和法における外部節点方程式を解く
緩和法では、プロセッサ内の処理をガウス−ザイデル法
で行い、プロセッサ間の処理をガウス−ヤコビ法で行う
ことにより、収束効率の向上と並列処理の最適化を同時
に達成することができる。
並列に直接法又は緩和法で処理することにより、シミュ
レーションを行う時間をより一層短くすることができ
る。点・ブロック緩和法における外部節点方程式を解く
緩和法では、プロセッサ内の処理をガウス−ザイデル法
で行い、プロセッサ間の処理をガウス−ヤコビ法で行う
ことにより、収束効率の向上と並列処理の最適化を同時
に達成することができる。
【００４１】緩和ブロック法においては、複数のプロセ
ッサを相互に接続した並列計算機を用いて、対象回路網
を外部節点で接続される部分回路に分割して解析する機
構を有するシステムにおいて、信号入力端子を始点、信
号出力端子を終点とする回路グループ間の信号伝播フロ
ーグラフを抽出し、信号伝播フローグラフを深さ方向優
先に辿って外部節点を抽出して、外部節点に初期電位を
与えて、前記初期電位を用いて求まる各部分回路への入
力電流を用いて各部分回路を各プロセッサで並列に直接
法を用いて解析して、新たに外部節点の電位を求める手
続きを前記外部節点の電位の変化が許容以下になるまで
繰り返す。
ッサを相互に接続した並列計算機を用いて、対象回路網
を外部節点で接続される部分回路に分割して解析する機
構を有するシステムにおいて、信号入力端子を始点、信
号出力端子を終点とする回路グループ間の信号伝播フロ
ーグラフを抽出し、信号伝播フローグラフを深さ方向優
先に辿って外部節点を抽出して、外部節点に初期電位を
与えて、前記初期電位を用いて求まる各部分回路への入
力電流を用いて各部分回路を各プロセッサで並列に直接
法を用いて解析して、新たに外部節点の電位を求める手
続きを前記外部節点の電位の変化が許容以下になるまで
繰り返す。
【００４２】信号入力端子を始点、信号出力端子を終点
とする回路グループ間の信号伝播フローグラフを抽出
し、この信号伝播フローグラフから外部節点のみを残し
た非連結の外部節点グラフを抽出し、所定よりも多い外
部節点の部分グラフは所定以下になるまで細分化し、各
部分グラフに対して、その部分グラフを構成する外部節
点と同じ外部節点を一番多く持つ部分回路に組み込んで
反復求解する。
とする回路グループ間の信号伝播フローグラフを抽出
し、この信号伝播フローグラフから外部節点のみを残し
た非連結の外部節点グラフを抽出し、所定よりも多い外
部節点の部分グラフは所定以下になるまで細分化し、各
部分グラフに対して、その部分グラフを構成する外部節
点と同じ外部節点を一番多く持つ部分回路に組み込んで
反復求解する。
【００４３】対象回路を複数の部分回路に分割し、接続
度の一番大きな部分回路に外部節点を組み込むことによ
り、各部分回路内の変数間の相互関係が強くなり、各部
分回路を解析する際の収束効率を向上させることができ
る。
度の一番大きな部分回路に外部節点を組み込むことによ
り、各部分回路内の変数間の相互関係が強くなり、各部
分回路を解析する際の収束効率を向上させることができ
る。
【００４４】接続度を部分回路の外部節点数とその部分
回路に合致する外部節点数との割合とすることにより、
接続度を容易に求めることができ、外部節点を部分回路
に組み込む際の処理を簡単に行うことができる。
回路に合致する外部節点数との割合とすることにより、
接続度を容易に求めることができ、外部節点を部分回路
に組み込む際の処理を簡単に行うことができる。
【００４５】外部節点の電位をＬＵ分解法により求める
ことにより、高速処理が可能となる。対象回路を複数の
部分回路に分割し、部分回路が最も多く接続している外
部節点を、その外部節点が接続している全ての部分回路
に組み込むことにより、各部分回路内の変数間の相互関
係をより一層強固にすることができ、各部分回路を解析
する際の収束効率を向上させることができる。
ことにより、高速処理が可能となる。対象回路を複数の
部分回路に分割し、部分回路が最も多く接続している外
部節点を、その外部節点が接続している全ての部分回路
に組み込むことにより、各部分回路内の変数間の相互関
係をより一層強固にすることができ、各部分回路を解析
する際の収束効率を向上させることができる。
【００４６】入力端子から出力端子までの信号の流れる
方向に基づいて、抽出した部分回路の解析を行うことに
より、各部分回路を解析する際の収束効率が向上し、シ
ミュレーションを行う時間を短くすることができる。
方向に基づいて、抽出した部分回路の解析を行うことに
より、各部分回路を解析する際の収束効率が向上し、シ
ミュレーションを行う時間を短くすることができる。
【００４７】部分回路と同数のプロセッサにより並列に
解析を行うことにより、シミュレーションを行う時間を
より一層短くすることができる。部分回路を接続する外
部節点を、接続度の 一番大きな部分回路に組み込んで
部分回路の解析を行うことにより、各部分回路内の変数
間の相互関係が強くなり、各部分回路を解析する際の収
束効率を向上させることができる。
解析を行うことにより、シミュレーションを行う時間を
より一層短くすることができる。部分回路を接続する外
部節点を、接続度の 一番大きな部分回路に組み込んで
部分回路の解析を行うことにより、各部分回路内の変数
間の相互関係が強くなり、各部分回路を解析する際の収
束効率を向上させることができる。
【００４８】部分回路が最も多く接続している外部節点
を、その外部節点が接続している全ての部分回路に組み
込んで部分回路の解析を行うことにより、各部分回路内
の変数間の相互関係をより一層強固にすることができ、
各部分回路を解析する際の収束効率を向上させることが
できる。
を、その外部節点が接続している全ての部分回路に組み
込んで部分回路の解析を行うことにより、各部分回路内
の変数間の相互関係をより一層強固にすることができ、
各部分回路を解析する際の収束効率を向上させることが
できる。
【００４９】
【実施例】以下、本発明の一実施例による回路シミュレ
ータを図面を参照しながら説明する。図１は、本発明の
一実施例による回路シミュレータの概略構成を示すブロ
ック図である。
ータを図面を参照しながら説明する。図１は、本発明の
一実施例による回路シミュレータの概略構成を示すブロ
ック図である。
【００５０】図１において、並列計算機３は、２次元格
子状に接続された複数のプロセッサＰＥ1 〜ＰＥn を備
えている。各プロセッサＰＥ1 〜ＰＥn は、ネットワー
クを介して任意のプロセッサＰＥ1 〜ＰＥn と通信でき
る。また、各プロセッサＰＥ1 〜ＰＥn は、バス２を介
してホスト計算機１に現在の動作状況を送信することが
できる。
子状に接続された複数のプロセッサＰＥ1 〜ＰＥn を備
えている。各プロセッサＰＥ1 〜ＰＥn は、ネットワー
クを介して任意のプロセッサＰＥ1 〜ＰＥn と通信でき
る。また、各プロセッサＰＥ1 〜ＰＥn は、バス２を介
してホスト計算機１に現在の動作状況を送信することが
できる。
【００５１】また、図２において、４は対象回路の素子
の接続関係を示すネットリストを読み込むネットリスト
読み込み手段、５は最小単位の機能を有するトランジス
タグループを抽出するトランジスタグループ抽出手段、
６はトランジスタグループを単位として、図１の並列計
算機３のプロセッサＰＥ1 〜ＰＥn の数の部分回路に対
象回路を分割する回路分割手段、７はトランジスタグル
ープの接続関係に基づいて、入力端子から出力端子まで
の信号の流れる方向を認識する信号伝播フローグラフ抽
出手段、８は部分回路を並列に解析し収束の判定を行う
解析手段である。
の接続関係を示すネットリストを読み込むネットリスト
読み込み手段、５は最小単位の機能を有するトランジス
タグループを抽出するトランジスタグループ抽出手段、
６はトランジスタグループを単位として、図１の並列計
算機３のプロセッサＰＥ1 〜ＰＥn の数の部分回路に対
象回路を分割する回路分割手段、７はトランジスタグル
ープの接続関係に基づいて、入力端子から出力端子まで
の信号の流れる方向を認識する信号伝播フローグラフ抽
出手段、８は部分回路を並列に解析し収束の判定を行う
解析手段である。
【００５２】次に、本発明の一実施例による回路シミュ
レータの動作について説明する。図３において、シミュ
レーションを行う対象回路は、例えば、ＭＯＳトランジ
スタＭ1 〜Ｍ9 、抵抗Ｒ1 、キャパシタＣ1 、Ｃ2 など
から構成され、図２のネットリスト読み込み手段４によ
り、対象回路の素子の接続関係を示すネットリストを読
み込む。
レータの動作について説明する。図３において、シミュ
レーションを行う対象回路は、例えば、ＭＯＳトランジ
スタＭ1 〜Ｍ9 、抵抗Ｒ1 、キャパシタＣ1 、Ｃ2 など
から構成され、図２のネットリスト読み込み手段４によ
り、対象回路の素子の接続関係を示すネットリストを読
み込む。
【００５３】次に、対象回路から機能を持ったまとまり
を認識し、トランジスタグループ抽出手段５により、ト
ランジスタグループＴＧ1 〜ＴＧ3 を作成する。この場
合、一般的には、ＭＯＳトランジスタＭ1 〜Ｍ9 のゲー
ト入力の部分で分割してトランジスタグループＴＧ1 〜
ＴＧ3 の作成が行われる。例えば、トランジスタグルー
プＴＧ1 は、ＭＯＳトランジスタＭ1 、Ｍ2 、抵抗
Ｒ1 、キャパシタＣ1 から構成され、トランジスタグル
ープＴＧ2 は、ＭＯＳトランジスタＭ3 、Ｍ4 、Ｍ7 、
キャパシタＣ2 から構成され、トランジスタグループＴ
Ｇ3 は、ＭＯＳトランジスタＭ5 、Ｍ6 から構成されて
いる。このトランジスタグループＴＧ1 〜ＴＧ3 は、論
理ゲートなどの最小単位の機能を有している。
を認識し、トランジスタグループ抽出手段５により、ト
ランジスタグループＴＧ1 〜ＴＧ3 を作成する。この場
合、一般的には、ＭＯＳトランジスタＭ1 〜Ｍ9 のゲー
ト入力の部分で分割してトランジスタグループＴＧ1 〜
ＴＧ3 の作成が行われる。例えば、トランジスタグルー
プＴＧ1 は、ＭＯＳトランジスタＭ1 、Ｍ2 、抵抗
Ｒ1 、キャパシタＣ1 から構成され、トランジスタグル
ープＴＧ2 は、ＭＯＳトランジスタＭ3 、Ｍ4 、Ｍ7 、
キャパシタＣ2 から構成され、トランジスタグループＴ
Ｇ3 は、ＭＯＳトランジスタＭ5 、Ｍ6 から構成されて
いる。このトランジスタグループＴＧ1 〜ＴＧ3 は、論
理ゲートなどの最小単位の機能を有している。
【００５４】次に、図４において、トランジスタグルー
プＴＧ1 〜ＴＧ10を単位として、図２の回路分割手段６
により、図１の並列計算機３のプロセッサＰＥ1 〜ＰＥ
n の数の部分回路ＣＢ1 〜ＣＢ4 に対象回路を分割す
る。この時、各部分回路ＣＢ1〜ＣＢ4 は、大きさがほ
ぼ均等で、且つ部分回路ＣＢ1 〜ＣＢ4 を接続する外部
節点Ｐ1 〜Ｐ5 の数が最小となるように対象回路を分割
する。例えば、部分回路ＣＢ1 はトランジスタグループ
ＴＧ1 〜ＴＧ3 から構成され、部分回路ＣＢ2 はトラン
ジスタグループＴＧ4 〜ＴＧ6 から構成され、部分回路
ＣＢ3 はトランジスタグループＴＧ7 、ＴＧ8 から構成
され、部分回路ＣＢ4 はトランジスタグループＴＧ9 、
ＴＧ10から構成されている。そして、外部節点Ｐ1 は部
分回路ＣＢ1 と部分回路ＣＢ3 とを接続し、外部節点Ｐ
2 は部分回路ＣＢ1 と部分回路ＣＢ2 とを接続し、外部
節点Ｐ3 は部分回路ＣＢ2 と部分回路ＣＢ3 とを接続
し、外部節点Ｐ4 は部分回路ＣＢ2 と部分回路ＣＢ4 と
を接続し、外部節点Ｐ5 は部分回路ＣＢ3 と部分回路Ｃ
Ｂ4 とを接続している。
プＴＧ1 〜ＴＧ10を単位として、図２の回路分割手段６
により、図１の並列計算機３のプロセッサＰＥ1 〜ＰＥ
n の数の部分回路ＣＢ1 〜ＣＢ4 に対象回路を分割す
る。この時、各部分回路ＣＢ1〜ＣＢ4 は、大きさがほ
ぼ均等で、且つ部分回路ＣＢ1 〜ＣＢ4 を接続する外部
節点Ｐ1 〜Ｐ5 の数が最小となるように対象回路を分割
する。例えば、部分回路ＣＢ1 はトランジスタグループ
ＴＧ1 〜ＴＧ3 から構成され、部分回路ＣＢ2 はトラン
ジスタグループＴＧ4 〜ＴＧ6 から構成され、部分回路
ＣＢ3 はトランジスタグループＴＧ7 、ＴＧ8 から構成
され、部分回路ＣＢ4 はトランジスタグループＴＧ9 、
ＴＧ10から構成されている。そして、外部節点Ｐ1 は部
分回路ＣＢ1 と部分回路ＣＢ3 とを接続し、外部節点Ｐ
2 は部分回路ＣＢ1 と部分回路ＣＢ2 とを接続し、外部
節点Ｐ3 は部分回路ＣＢ2 と部分回路ＣＢ3 とを接続
し、外部節点Ｐ4 は部分回路ＣＢ2 と部分回路ＣＢ4 と
を接続し、外部節点Ｐ5 は部分回路ＣＢ3 と部分回路Ｃ
Ｂ4 とを接続している。
【００５５】次に、各トランジスタグループＴＧ1 〜Ｔ
Ｇ10について、図３のＭＯＳトランジスタＭ1 〜Ｍ9 の
ゲート端子をグループ入力、他のトランジスタグループ
ＴＧ1 〜ＴＧ10のゲート端子が接続する節点をグループ
出力とし、信号入力端子９、１０を始点、信号出力端子
１１、１２を終点とする各トランジスタグループＴＧ1
〜ＴＧ10の間のグループ信号伝播フローグラフを作成す
る。
Ｇ10について、図３のＭＯＳトランジスタＭ1 〜Ｍ9 の
ゲート端子をグループ入力、他のトランジスタグループ
ＴＧ1 〜ＴＧ10のゲート端子が接続する節点をグループ
出力とし、信号入力端子９、１０を始点、信号出力端子
１１、１２を終点とする各トランジスタグループＴＧ1
〜ＴＧ10の間のグループ信号伝播フローグラフを作成す
る。
【００５６】次に、グループ信号伝播フローグラフおい
て、回路分割を行った際の外部節点に対して外部節点フ
ラグを立てる。そして、図２の信号伝播フロー抽出手段
７で外部節点フラグを辿ることにより、外部節点の接続
や分離の状況、信号伝播順序などの必要な情報を得る。
て、回路分割を行った際の外部節点に対して外部節点フ
ラグを立てる。そして、図２の信号伝播フロー抽出手段
７で外部節点フラグを辿ることにより、外部節点の接続
や分離の状況、信号伝播順序などの必要な情報を得る。
【００５７】例えば、図５に示す信号伝播フローグラフ
おいて、ブロックＢ0 〜Ｂ7 が外部節点ｘ1 〜ｘ8 によ
り接続されている場合、信号伝播フローグラフを深さ方
向優先で辿り、出会った順序で外部節点ｘ1 〜ｘ8 を並
べる。すなわち、図６に示すように、外部節点ｘ1 〜ｘ
8 の順序を深さ方向優先で並び換える。
おいて、ブロックＢ0 〜Ｂ7 が外部節点ｘ1 〜ｘ8 によ
り接続されている場合、信号伝播フローグラフを深さ方
向優先で辿り、出会った順序で外部節点ｘ1 〜ｘ8 を並
べる。すなわち、図６に示すように、外部節点ｘ1 〜ｘ
8 の順序を深さ方向優先で並び換える。
【００５８】図７は、外部節点ｘ1 〜ｘ8 の順序を深さ
方向優先で並び換える処理を示すフローチャートであ
る。まず、ステップＳ１０で並べ換えテーブルの初期化
を行い、ステップＳ１１で木の根の部分に相当するブロ
ックＢ0 の外部節点をスタックレジスタにスタックす
る。
方向優先で並び換える処理を示すフローチャートであ
る。まず、ステップＳ１０で並べ換えテーブルの初期化
を行い、ステップＳ１１で木の根の部分に相当するブロ
ックＢ0 の外部節点をスタックレジスタにスタックす
る。
【００５９】次に、ステップＳ１２に示すように、スタ
ックレジスタにスタックがある場合、ステップＳ１３に
進んで、スタックレジスタから外部節点ｘ1 〜ｘ8 を先
入れ先出し方式で取り出し、取り出した外部節点ｘ1 〜
ｘ8 を並べ換えテーブルに登録する。
ックレジスタにスタックがある場合、ステップＳ１３に
進んで、スタックレジスタから外部節点ｘ1 〜ｘ8 を先
入れ先出し方式で取り出し、取り出した外部節点ｘ1 〜
ｘ8 を並べ換えテーブルに登録する。
【００６０】次に、ステップＳ１４に示すように、並べ
換えテーブルに登録した外部節点ｘ1 〜ｘ8 に接続する
ブロックＢ0 〜Ｂ7 に外部節点ｘ1 〜ｘ8 がある場合、
ステップＳ１５に進んで、そのブロックＢ0 〜Ｂ7 の外
部節点ｘ1 〜ｘ8 のうち１つを並べ換えテーブルに登録
し、残りの外部節点ｘ1 〜ｘ8 をスタックレジスタにス
タックする。そして、ステップＳ１４に戻って、並べ換
えテーブルに登録した外部節点ｘ1 〜ｘ8 に接続するブ
ロックＢ0 〜Ｂ7 に外部節点ｘ1 〜ｘ8 がなくなるま
で、ステップＳ１５の動作を繰り返す。
換えテーブルに登録した外部節点ｘ1 〜ｘ8 に接続する
ブロックＢ0 〜Ｂ7 に外部節点ｘ1 〜ｘ8 がある場合、
ステップＳ１５に進んで、そのブロックＢ0 〜Ｂ7 の外
部節点ｘ1 〜ｘ8 のうち１つを並べ換えテーブルに登録
し、残りの外部節点ｘ1 〜ｘ8 をスタックレジスタにス
タックする。そして、ステップＳ１４に戻って、並べ換
えテーブルに登録した外部節点ｘ1 〜ｘ8 に接続するブ
ロックＢ0 〜Ｂ7 に外部節点ｘ1 〜ｘ8 がなくなるま
で、ステップＳ１５の動作を繰り返す。
【００６１】一方、ステップＳ１４において、並べ換え
テーブルに登録した外部節点ｘ1 〜ｘ8 に接続するブロ
ックＢ0 〜Ｂ7 に外部節点ｘ1 〜ｘ8 がない場合、ステ
ップＳ１２に戻る。そして、スタックレジスタにスタッ
クがなくなるまで以上の動作を繰り返す。
テーブルに登録した外部節点ｘ1 〜ｘ8 に接続するブロ
ックＢ0 〜Ｂ7 に外部節点ｘ1 〜ｘ8 がない場合、ステ
ップＳ１２に戻る。そして、スタックレジスタにスタッ
クがなくなるまで以上の動作を繰り返す。
【００６２】以上のような動作が行われた後、グループ
信号伝播フローグラフの外部節点フラグからの情報に基
づいて、ブロック緩和反復アルゴリズムに応じた部分回
路ＣＢ1 〜ＣＢ4 毎の方程式を作成する。そして、図２
の解析手段８における図１の並列計算機３の各プロセッ
サＰＥ1 〜ＰＥn にロードして反復求解を行う。
信号伝播フローグラフの外部節点フラグからの情報に基
づいて、ブロック緩和反復アルゴリズムに応じた部分回
路ＣＢ1 〜ＣＢ4 毎の方程式を作成する。そして、図２
の解析手段８における図１の並列計算機３の各プロセッ
サＰＥ1 〜ＰＥn にロードして反復求解を行う。
【００６３】次に、本発明の第１実施例によるシミュレ
ーション方法について説明する。この第１実施例は、点
・ブロック緩和シミュレーションと呼ばれるもので、外
部節点電圧ベクトルｖ0 の外部節点変数の順序を深さ方
向優先で並べることにより、収束効率を向上させたもの
である。
ーション方法について説明する。この第１実施例は、点
・ブロック緩和シミュレーションと呼ばれるもので、外
部節点電圧ベクトルｖ0 の外部節点変数の順序を深さ方
向優先で並べることにより、収束効率を向上させたもの
である。
【００６４】点・ブロック緩和シミュレーションを行う
場合、回路を分割し、分割した節点、すなわち外部節点
変数を集めると、図８に示すように、縁付きブロック対
角（ＢＢＤ）行列となる。この縁付きブロック対角（Ｂ
ＢＤ）行列により、各部分回路ＣＢ1 〜ＣＢ4 毎の方程
式が得られる。なお、ここでは、回路を４つに分割し、
４台のプロセッサＰＥ1 〜ＰＥ4 で並列に処理を行う場
合について示した。
場合、回路を分割し、分割した節点、すなわち外部節点
変数を集めると、図８に示すように、縁付きブロック対
角（ＢＢＤ）行列となる。この縁付きブロック対角（Ｂ
ＢＤ）行列により、各部分回路ＣＢ1 〜ＣＢ4 毎の方程
式が得られる。なお、ここでは、回路を４つに分割し、
４台のプロセッサＰＥ1 〜ＰＥ4 で並列に処理を行う場
合について示した。
【００６５】図９において、まず、ステップＳ２０に示
すように、外部節点電圧ベクトルｖ0 の外部節点変数の
順序を、信号伝播フローグラフにおける深さ方向優先で
並べる。
すように、外部節点電圧ベクトルｖ0 の外部節点変数の
順序を、信号伝播フローグラフにおける深さ方向優先で
並べる。
【００６６】次に、ステップＳ２１に示すように、外部
節点電圧ベクトルｖ0 に予測値を与える。次に、ステッ
プＳ２２に示すように、図８の行列式から求めた（１
９）式を、プロセッサＰＥi （ｉ＝１、２、３、４）を
用いて部分回路ＣＢ1 〜ＣＢ4 毎にＬＵ分解法で解く。
節点電圧ベクトルｖ0 に予測値を与える。次に、ステッ
プＳ２２に示すように、図８の行列式から求めた（１
９）式を、プロセッサＰＥi （ｉ＝１、２、３、４）を
用いて部分回路ＣＢ1 〜ＣＢ4 毎にＬＵ分解法で解く。
【００６７】 Ａi ｖi ＝ｊi −Ｂi ｖ0 （ｉ＝１、２、３、４） ・・・（１９）式 次に、ステップＳ２３に示すように、（２０）式の計算
し、求めた値をｊ00とする。
し、求めた値をｊ00とする。
【００６８】 Ｊ0 −Ｃ1 ｖ1 −Ｃ2 ｖ2 −Ｃ3 ｖ3 −Ｃ4 ｖ4 ・・・（２０）式 次に、ステップＳ２４において、図８に示すようにプロ
セッサＰＥi （ｉ＝１、２、３、４）に（２１）式を割
り付ける。
セッサＰＥi （ｉ＝１、２、３、４）に（２１）式を割
り付ける。
【００６９】 Ｄ0 ｖ0 ＝ｊ00 ・・・（２１）式 次に、ステップＳ２５に示すように、各プロセッサＰＥ
i （ｉ＝１、２、３、４）内では、収束速度の速いガウ
ス−ザイデル法により、各プロセッサＰＥi （ｉ＝１、
２、３、４）間では、並列性の高いガウス−ヤコビ法に
より、（２２）式を解く。
i （ｉ＝１、２、３、４）内では、収束速度の速いガウ
ス−ザイデル法により、各プロセッサＰＥi （ｉ＝１、
２、３、４）間では、並列性の高いガウス−ヤコビ法に
より、（２２）式を解く。
【００７０】 Ｄ0iｖ0i＝ｊ0i（ｉ＝１、２、３、４） ・・・（２２）式 次に、ステップＳ２６に示すように、求めた外部節点電
圧ベクトルｖ0 ´が、予測値として与えた外部節点電圧
ベクトルｖ0 に十分近くなるまで、以上の処理を繰り返
す。
圧ベクトルｖ0 ´が、予測値として与えた外部節点電圧
ベクトルｖ0 に十分近くなるまで、以上の処理を繰り返
す。
【００７１】以上説明したように、本発明の第１実施例
によれば、外部節点行列Ｄ0 を解く際に、外部節点変数
を信号の伝わる順序に並べてガウス−ザイデル法で解
き、その外側をガウス−ヤコビ法で解くことにより、収
束の速さと並列処理による効果の両方を期待できる。
によれば、外部節点行列Ｄ0 を解く際に、外部節点変数
を信号の伝わる順序に並べてガウス−ザイデル法で解
き、その外側をガウス−ヤコビ法で解くことにより、収
束の速さと並列処理による効果の両方を期待できる。
【００７２】次に、本発明の第２実施例によるシミュレ
ーション方法について説明する。この第２実施例は、ブ
ロック緩和シミュレーションと呼ばれるもので、図１２
に示すように外部節点電圧ベクトルｖ0 の外部節点変数
ｖ01〜ｖ04を、接続度の高い部分回路に組み込んで、部
分回路の解析を行うようにしたものである。
ーション方法について説明する。この第２実施例は、ブ
ロック緩和シミュレーションと呼ばれるもので、図１２
に示すように外部節点電圧ベクトルｖ0 の外部節点変数
ｖ01〜ｖ04を、接続度の高い部分回路に組み込んで、部
分回路の解析を行うようにしたものである。
【００７３】以下、外部節点変数の部分回路への組み込
み手順について説明する。図１１のステップＳ３０にお
いて、図１０の非連結外部節点部分グラフＥＢj〜ＥＢ
j+3 を任意に１つ取り出す。ここで、非連結外部節点部
分グラフＥＢj 〜ＥＢj+3 とは、共通の部分回路ＣＢ
i+1 〜ＣＢi+4 を接続する外部節点ｖp 〜ｖp+5 の集合
である。
み手順について説明する。図１１のステップＳ３０にお
いて、図１０の非連結外部節点部分グラフＥＢj〜ＥＢ
j+3 を任意に１つ取り出す。ここで、非連結外部節点部
分グラフＥＢj 〜ＥＢj+3 とは、共通の部分回路ＣＢ
i+1 〜ＣＢi+4 を接続する外部節点ｖp 〜ｖp+5 の集合
である。
【００７４】次に、ステップＳ３１で非連結外部節点部
分グラフＥＢj 〜ＥＢj+3 がある場合、ステップＳ３１
に進み、取り出した非連結外部節点部分グラフＥＢj 〜
ＥＢj+3 に接続する全ての部分回路ＣＢi+1 〜ＣＢi+4
について、接続度の計算を行う。ここで、接続度は、部
分回路ＣＢi+1 〜ＣＢi+4 の外部節点ｖp 〜ｖp+5 の数
と合致する外部節点ｖp 〜ｖp+5 の数との割合である。
分グラフＥＢj 〜ＥＢj+3 がある場合、ステップＳ３１
に進み、取り出した非連結外部節点部分グラフＥＢj 〜
ＥＢj+3 に接続する全ての部分回路ＣＢi+1 〜ＣＢi+4
について、接続度の計算を行う。ここで、接続度は、部
分回路ＣＢi+1 〜ＣＢi+4 の外部節点ｖp 〜ｖp+5 の数
と合致する外部節点ｖp 〜ｖp+5 の数との割合である。
【００７５】次に、外部節点を部分回路に組み込んだ後
の、部分回路の解析手順について説明する。 図１３に
おいて、ステップＳ４０〜Ｓ４３の手順により、外部節
点の部分回路への組み込みが行われ、図１２に示すよう
に、外部節点電圧ベクトルｖ0 の外部節点変数ｖ01〜ｖ
04が、部分回路ＣＢ1 〜ＣＢ4 の内部節点電圧変数ベク
トルｖ1 〜ｖ4 に組み込まれる。また、部分回路ＣＢ1
〜ＣＢ4 の内部節点と外部節点との間のアドミタンス回
路行列Ｂ1 〜Ｂ4 、部分回路ＣＢ1 〜ＣＢ4 の外部節点
と内部節点との間のアドミタンス回路行列Ｃ1 〜Ｃ4 、
外部節点行列Ｄ0 は、部分回路ＣＢ1 〜ＣＢ4 の内部節
点間のアドミタンス回路行列Ａ1 〜Ａ4に組み込まれ
る。
の、部分回路の解析手順について説明する。 図１３に
おいて、ステップＳ４０〜Ｓ４３の手順により、外部節
点の部分回路への組み込みが行われ、図１２に示すよう
に、外部節点電圧ベクトルｖ0 の外部節点変数ｖ01〜ｖ
04が、部分回路ＣＢ1 〜ＣＢ4 の内部節点電圧変数ベク
トルｖ1 〜ｖ4 に組み込まれる。また、部分回路ＣＢ1
〜ＣＢ4 の内部節点と外部節点との間のアドミタンス回
路行列Ｂ1 〜Ｂ4 、部分回路ＣＢ1 〜ＣＢ4 の外部節点
と内部節点との間のアドミタンス回路行列Ｃ1 〜Ｃ4 、
外部節点行列Ｄ0 は、部分回路ＣＢ1 〜ＣＢ4 の内部節
点間のアドミタンス回路行列Ａ1 〜Ａ4に組み込まれ
る。
【００７６】次に、ステップＳ４４に示すように、外部
節点電圧ベクトルｖ0 に予測値を与える。次に、ステッ
プＳ４５に示すように、図１２の行列式から求めた（２
３）式を、プロセッサＰＥk を用いて部分回路ＣＢ1 〜
ＣＢ4 毎に計算する。
節点電圧ベクトルｖ0 に予測値を与える。次に、ステッ
プＳ４５に示すように、図１２の行列式から求めた（２
３）式を、プロセッサＰＥk を用いて部分回路ＣＢ1 〜
ＣＢ4 毎に計算する。
【００７７】
【数７】
【００７８】次に、ステップＳ４６に示すように、（２
４）式を、プロセッサＰＥk を用いて部分回路ＣＢ1 〜
ＣＢ4 毎にＬＵ分解法で解く。 Ａkkｖk ＝ｊk ´ ・・・（２４）式 次に、ステップＳ４７に示すように、求めた外部節点電
圧ベクトルｖk が、予測値として与えた外部節点電圧ベ
クトルｖ0 に十分近くなるまで、以上の処理を繰り返
す。
４）式を、プロセッサＰＥk を用いて部分回路ＣＢ1 〜
ＣＢ4 毎にＬＵ分解法で解く。 Ａkkｖk ＝ｊk ´ ・・・（２４）式 次に、ステップＳ４７に示すように、求めた外部節点電
圧ベクトルｖk が、予測値として与えた外部節点電圧ベ
クトルｖ0 に十分近くなるまで、以上の処理を繰り返
す。
【００７９】以上説明したように、本発明の第２実施例
によれば、非連結外部節点部分グラフを最も関係の深い
部分回路に組み込むことにより、ブロック内の変数間の
相互関係が強くなり、ブロック緩和反復法の収束能力を
高めることができる。
によれば、非連結外部節点部分グラフを最も関係の深い
部分回路に組み込むことにより、ブロック内の変数間の
相互関係が強くなり、ブロック緩和反復法の収束能力を
高めることができる。
【００８０】次に、本発明の第３実施例によるシミュレ
ーション方法について説明する。この第３実施例は、オ
ーバーラップ・ブロック緩和シミュレーションと呼ばれ
るもので、非連結の外部節点の部分グラフを適切な部分
回路に組み込むとともに、その非連結外部節点部分グラ
フにおいて、他の部分回路が一番多く接続している外部
節点変数を、接続している全ての部分回路にもオーバー
ラップさせて組み込むようにしたものである。なお、外
部節点変数を組み込んだ後の部分回路の解析は、上述し
たブロック緩和シミュレーションと同様に行われる。
ーション方法について説明する。この第３実施例は、オ
ーバーラップ・ブロック緩和シミュレーションと呼ばれ
るもので、非連結の外部節点の部分グラフを適切な部分
回路に組み込むとともに、その非連結外部節点部分グラ
フにおいて、他の部分回路が一番多く接続している外部
節点変数を、接続している全ての部分回路にもオーバー
ラップさせて組み込むようにしたものである。なお、外
部節点変数を組み込んだ後の部分回路の解析は、上述し
たブロック緩和シミュレーションと同様に行われる。
【００８１】以上説明したように、本発明の第３実施例
によれば、各部分回路のサイズは増加するが、最も適切
な外部節点変数を部分回路にオーバーラップさせること
により、尾非連結外部節点部分グラフを最も関係の深い
部分回路に組み込むことにより、ブロック内の変数間の
相互関係がより一層強くなり、ブロック緩和反復法の収
束能力をさらに高めることができる。
によれば、各部分回路のサイズは増加するが、最も適切
な外部節点変数を部分回路にオーバーラップさせること
により、尾非連結外部節点部分グラフを最も関係の深い
部分回路に組み込むことにより、ブロック内の変数間の
相互関係がより一層強くなり、ブロック緩和反復法の収
束能力をさらに高めることができる。
【００８２】
【発明の効果】以上説明したように、本発明によれば、
大規模な回路を高速にシミュレーションするために、並
列処理によるブロック緩和反復法が有効である。ブロッ
ク緩和反復は、対象回路が同じでも、回路の分割の方
法、変数の分離の方法により、収束速度が大きく異な
る。
大規模な回路を高速にシミュレーションするために、並
列処理によるブロック緩和反復法が有効である。ブロッ
ク緩和反復は、対象回路が同じでも、回路の分割の方
法、変数の分離の方法により、収束速度が大きく異な
る。
【００８３】本発明では、回路の信号伝播フローグラフ
を抽出し、分割する外部節点グラフを状況を認識するこ
とにより、回路分割や変数の分離を大局的見地から最適
に行い、ブロック緩和反復法の収束速度を高めることが
できる。
を抽出し、分割する外部節点グラフを状況を認識するこ
とにより、回路分割や変数の分離を大局的見地から最適
に行い、ブロック緩和反復法の収束速度を高めることが
できる。
【図１】本発明の一実施例による回路シミュレータの概
略構成を示すブロック図である。
略構成を示すブロック図である。
【図２】本発明の第１実施例による回路シミュレータの
機能を示すブロック図である。
機能を示すブロック図である。
【図３】本発明の一実施例によるトランジスタグループ
の構成を示す回路図である。
の構成を示す回路図である。
【図４】本発明の一実施例による部分回路の構成を示す
ブロック図である。
ブロック図である。
【図５】本発明の一実施例による信号伝播フローグラフ
を示す図である。
を示す図である。
【図６】本発明の一実施例によるスタックレジスタの内
容を示す図である。
容を示す図である。
【図７】本発明の一実施例による信号伝播フローグラフ
に基づいて変数を並べる処理を示すフローチャートであ
る。
に基づいて変数を並べる処理を示すフローチャートであ
る。
【図８】本発明の第１実施例によるブロック対角行列を
示す図である。
示す図である。
【図９】本発明の第１実施例によるシミュレーション方
法を示すフローチャートである。
法を示すフローチャートである。
【図１０】本発明の一実施例による非連結外部節点を有
する部分回路の構成を示すブロック図である。
する部分回路の構成を示すブロック図である。
【図１１】本発明の第１実施例による非連結外部節点部
分グラフの組み込み手順をを示すフローチャートであ
る。
分グラフの組み込み手順をを示すフローチャートであ
る。
【図１２】本発明の第２実施例によるブロック対角行列
を示す図である。
を示す図である。
【図１３】本発明の第２実施例によるシミュレーション
方法を示すフローチャートである。
方法を示すフローチャートである。
【図１４】従来の部分回路の構成を示すブロック図であ
る。
る。
【図１５】従来のシミュレーション方法を示すフローチ
ャートである。
ャートである。
【図１６】従来のシミュレーション方法の並列処理を示
すフローチャートである。
すフローチャートである。
【図１７】ブロックの結合状態を示す図である。
１ ホスト計算機 ２ バス ３ 並列計算機 ４ ネットリスト読み込み手段 ５ トランジスタグループ抽出手段 ６ 回路分割手段 ７ 信号伝播フロー抽出手段 ８ 収束判定手段
Claims (9)
- 【請求項１】 複数のプロセッサを相互に接続した並列
計算機を用いて、対象回路網を外部節点で接続される部
分回路に分割して解析する機構を有するシステムにおい
て、 外部節点に初期電位を与えて、各プロセッサが各部分回
路を直接法を用いて並列に解き、この結果を使って外部
節点電位方程式を前記各プロセッサに割り当てて緩和法
を用いて並列に解析して前記外部節点の電位を更新し、
この電位の変化が許容以下になるまで繰り返す点・ブロ
ック緩和シミュレーション方法。 - 【請求項２】 信号入力端子を始点、信号出力端子を終
点とする回路グループ間の信号伝播フローグラフを抽出
し、信号伝播フローグラフを深さ方向優先に辿って外部
節点電位方程式の外部節点変数を並べ、上から均等に各
プロセッサに割り付けて反復求解することを特徴とする
請求項１記載の点・ブロック緩和シミュレーション方
法。 - 【請求項３】 前記緩和法の実行において、 前記プロセッサ内の処理をガウス−ザイデル法で行い、
前記プロセッサ間の処理をガウス−ヤコビ法で行うこと
を特徴とする請求項２に記載の点・ブロック緩和シミュ
レーション方法。 - 【請求項４】 複数のプロセッサを相互に接続した並列
計算機を用いて、対象回路網を外部節点で接続される部
分回路に分割して解析する機構を有するシステムにおい
て、 信号入力端子を始点、信号出力端子を終点とする回路グ
ループ間の信号伝播フローグラフを抽出し、信号伝播フ
ローグラフを深さ方向優先に辿って外部節点を抽出し
て、 外部節点に初期電位を与えて、前記初期電位を用いて求
まる各部分回路への入力電流を用いて各部分回路を各プ
ロセッサで並列に直接法を用いて解析して、新たに外部
節点の電位を求める手続きを前記外部節点の電位の変化
が許容以下になるまで繰り返すことを特徴とするブロッ
ク緩和シミュレーション方法。 - 【請求項５】 信号入力端子を始点、信号出力端子を終
点とする回路グループ間の信号伝播フローグラフを抽出
し、この信号伝播フローグラフから外部節点のみを残し
た非連結の外部節点グラフを抽出し、所定よりも多い外
部節点の部分グラフは所定以下になるまで細分化し、各
部分グラフに対して、その部分グラフを構成する外部節
点と同じ外部節点を一番多く持つ部分回路に組み込んで
反復求解する請求項４記載のブロック緩和シミュレーシ
ョン方法。 - 【請求項６】 接続度の一番大きな部分回路に前記外部
節点を組み込んで前記外部節点の電位及び前記各部分回
路の内部節点の電圧を求め、前記接続度は、部分回路の
外部節点数とその部分回路に合致する外部節点数との割
合であることを特徴とする請求項５記載のブロック緩和
シミュレーション方法。 - 【請求項７】 請求項５記載の反復求解方式において、 収束速度を高めるために各部分回路で変数を重複させて
反復求解を行うオーバーラップ・ブロック緩和シミュレ
ーション法を行うために、外部節点の各部分グラフにお
いて、その部分グラフを構成する外部節点のうち、部分
回路が一番多く接続する外部節点を、その外部節点に接
続するすべての部分回路にも組み込んで反復求解する方
式。 - 【請求項８】 請求項２において、対象回路の素子の接
続関係を示すネットリストを読み込むネットリスト読み
込み手段と、 最小単位の機能を有する回路グループを抽出する回路グ
ループ抽出手段と、 前記回路グループを単位として、前記対象回路を複数の
部分回路に分割する回路分割手段と、 前記回路グループの接続関係に基づいて、入力端子から
出力端子までの信号の流れる方向を認識する信号伝播フ
ローグラフ抽出手段と、 前記信号伝播フローグラフ抽出手段の出力に基づいて、
前記部分回路の解析を該部分回路と同数のプロセッサに
より並列に行う解析手段とを備えることを特徴とする回
路シミュレータ。 - 【請求項９】 請求項５において、対象回路の素子の接
続関係を示すネットリストを読み込むネットリスト読み
込み手段と、 最小単位の機能を有する回路グループを抽出する回路グ
ループ抽出手段と、 前記回路グループを単位として、前記対象回路を複数の
部分回路に分割する回路分割手段と、 各部分回路に接続する外部節点を、接続度の一番大きな
部分回路に組み込む組み込み手段と、 前記組み込み手段により外部節点を組み込んだ部分回路
の解析を行う解析手段とを備えることを特徴とする回路
シミュレータ。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7168250A JPH0916640A (ja) | 1995-06-10 | 1995-06-10 | 回路シミュレータ及びブロック緩和反復シミュレーション方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7168250A JPH0916640A (ja) | 1995-06-10 | 1995-06-10 | 回路シミュレータ及びブロック緩和反復シミュレーション方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0916640A true JPH0916640A (ja) | 1997-01-17 |
Family
ID=15864537
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7168250A Withdrawn JPH0916640A (ja) | 1995-06-10 | 1995-06-10 | 回路シミュレータ及びブロック緩和反復シミュレーション方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0916640A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2013101608A (ja) * | 2011-10-17 | 2013-05-23 | Mizuho Information & Research Institute Inc | 非線形構造解析計算装置、非線形構造解析計算方法及び非線形構造解析計算プログラム |
| JP2016009320A (ja) * | 2014-06-24 | 2016-01-18 | 富士電機株式会社 | 電気回路のシミュレーション装置、電気回路のシミュレーション方法、プログラム |
| US9690750B2 (en) | 2014-01-17 | 2017-06-27 | Fujitsu Limited | Arithmetic device, arithmetic method, and wireless communication device |
| JP2019008794A (ja) * | 2017-06-20 | 2019-01-17 | ディスペース デジタル シグナル プロセッシング アンド コントロール エンジニアリング ゲゼルシャフト ミット ベシュレンクテル ハフツングｄｓｐａｃｅ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ａｎｄ ｃｏｎｔｒｏｌ ｅｎｇｉｎｅｅｒｉｎｇ ＧｍｂＨ | 電気全体回路のシミュレーションのためのコンピュータ実装方法 |
-
1995
- 1995-06-10 JP JP7168250A patent/JPH0916640A/ja not_active Withdrawn
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2013101608A (ja) * | 2011-10-17 | 2013-05-23 | Mizuho Information & Research Institute Inc | 非線形構造解析計算装置、非線形構造解析計算方法及び非線形構造解析計算プログラム |
| US9690750B2 (en) | 2014-01-17 | 2017-06-27 | Fujitsu Limited | Arithmetic device, arithmetic method, and wireless communication device |
| JP2016009320A (ja) * | 2014-06-24 | 2016-01-18 | 富士電機株式会社 | 電気回路のシミュレーション装置、電気回路のシミュレーション方法、プログラム |
| JP2019008794A (ja) * | 2017-06-20 | 2019-01-17 | ディスペース デジタル シグナル プロセッシング アンド コントロール エンジニアリング ゲゼルシャフト ミット ベシュレンクテル ハフツングｄｓｐａｃｅ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ａｎｄ ｃｏｎｔｒｏｌ ｅｎｇｉｎｅｅｒｉｎｇ ＧｍｂＨ | 電気全体回路のシミュレーションのためのコンピュータ実装方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5930499A (en) | Method for mixed placement of structured and non-structured circuit elements | |
| US9111058B1 (en) | Solving a hierarchical circuit network using a barycenter compact model | |
| US11663383B2 (en) | Method and system for hierarchical circuit simulation using parallel processing | |
| US6810506B1 (en) | Methodology for stitching reduced-order models of interconnects together | |
| Gu et al. | Model reduction via projection onto nonlinear manifolds, with applications to analog circuits and biochemical systems | |
| CN114707445B (zh) | 集成电路的综合方法、装置、计算机设备及存储介质 | |
| CN114330173B (zh) | 边界节点连接关系获取方法、装置、设备和存储介质 | |
| US20060112356A1 (en) | System and method for converting a flat netlist into a hierarchical netlist | |
| WO2005050494A1 (ja) | グラフ幅削減装置及びグラフ幅削減方法、並びに論理回路合成装置及び論理回路合成方法 | |
| CN102893282A (zh) | 用于在综合期间执行异步和同步复位去除的方法以及设备 | |
| JPH0916640A (ja) | 回路シミュレータ及びブロック緩和反復シミュレーション方法 | |
| Mak et al. | Board-level multiterminal net routing for FPGA-based logic emulation | |
| Chen et al. | Tsa-ticer: A two-stage ticer acceleration framework for model order reduction | |
| US8020122B2 (en) | Circuit splitting in analysis of circuits at transistor level | |
| CN117787202B (zh) | 跨工艺角的签核级时序预测方法及系统 | |
| KR100576987B1 (ko) | 전자 소자 및 전자 장치의 설계 및 제조 방법 | |
| US7979817B2 (en) | Net list producing device producing a net list with an interconnection parasitic element by hierarchical processing | |
| US20060020441A1 (en) | Method and system for creating timing constraint library | |
| US11210440B1 (en) | Systems and methods for RLGC extraction based on parallelized left-looking incomplete inverse fast multipole operations | |
| CN112861455B (zh) | Fpga建模验证系统及方法 | |
| Houngninou et al. | Implementation of switching circuit models as transfer functions | |
| JPH07287051A (ja) | 論理シミュレータ用入力データ作成装置 | |
| JP3766119B2 (ja) | 回路シミュレーション方法及びその装置 | |
| US20240070361A1 (en) | Circuit analysis method, circuit analysis device, and circuit analysis system | |
| Schmiedle et al. | Dynamic re-encoding during MDD minimization |
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: 20020903 |