JPH1097555A - 回路シミュレーションの回路分割方法 - Google Patents

Abstract

(57)【要約】 【課題】 本発明の目的は，回路を分割して１台のマシ
ンで回路解析する回路シミュレータにおける回路分割方
法を提供することにある。 【解決手段】 階層を持つ回路の再帰的縁付きブロック
対角構造回路行列を生成し、下位のブロックのインタフ
ェースノードを上位ブロックに移動して回路全体と最上
位回路のLU分解時の演算数を求める。インタフェースノ
ードの移動方法を変えて上記処理を繰り返し、回路全体
のLU分解時の演算数と最上位回路のLU分解時の演算数が
判定基準を満たしたときの状態で回路行列を生成する。 【効果】 再帰的縁付きブロック対角構造回路行列で回
路解析を行うときのLU分解時の演算数を削減することが
できる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、大規模LSIの回路
設計時に用いる回路シミュレーションの回路分割方法に
関する。

【０００２】

【従来の技術】回路の大規模化に伴い、精度を劣化させ
ることなく高速に回路シミュレーションを行う方法がま
すます重要になってきている。高速化の１つの手法とし
て回路を複数のブロックに分割してブロック単位に回路
解析を行う方法がある。１台の計算機でシミュレーショ
ンする際の回路分割方法としては、電子情報通信学会の
第３回回路とシステム軽井沢ＷＳ論文集２３８頁〜２４
５頁、１９９０年、「直接法を用いた大規模回路シミュ
レーション」によれば、回路が記述されているサブ回路
の単位で全体を階層的に分割するブロック分割方法があ
る。また、Inter-national Conference on Computer-Ai
ded Design Proceedings ４３８頁〜４４１頁、１９８
８年、「A dormant subcircuit model for maximizing
iterationlatency」によれば機能を構成する素子で回路
を１階層のブロックに分割し、同一のインタフェースノ
ードに接続する複数のブロックについては、統合後のブ
ロックがある大きさ以下になる範囲でブロックを統合
し、インタフェースノードをそのブロックの内部ノード
にする方法がある。

【０００３】上記回路分割方法は複数の計算機を用いて
回路シミュレーションを行う並列回路シミュレーション
のための回路分割方法であり、各計算機の計算負荷を均
等にする、あるいは、並列に処理できない部分を減らす
ための回路分割方法である。

【０００４】この時の回路の分割方法として、複数の計
算機を用いた並列回路シミュレーションのための回路分
割方法があった。特開平3-186971は回路中の１素子をク
ラスタとして、クラスタの数が目標ブロック数になる評
価関数に従って算出した評価値に基づいてクラスタペア
を結合して回路を分割する方法である。特開平4-74274
は、１素子を１クラスタとし、特定の評価関数にしたが
って算出した評価値に基づいてクラスタペアを選択して
結合し、目標とするブロック数になるまで続ける。その
後、最も素子数の多いブロックと少ないブロックを選択
し、ブロック間を接続する外部接点数の増加量が特定の
許容量より少なく、ブロック間の素子数の量が逆転しな
い範囲でブロック間でクラスタの交換を行い、回路を分
割する方法である。特開平3-186971は回路中の１素子を
クラスタとして、クラスタの数が目標ブロック数になる
評価関数にしたがって算出した評価値に基づいてクラス
タペアを結合し、その後最も素子の多いブロックと最も
素子の少ないブロックの間でクラスタの交換を行う回路
分割方法である。特開平1-250173は各部分回路の負荷を
接点数とトランジスタ数から算出して、負荷が最大の部
分回路を２分割し部分回路数がプロセッサ数に達する
か、全部分回路と前記の部分回路を連結する連結素子か
らなす親回路と、負荷が最大の部分回路との双方の負荷
を足し合わせた和が最小であると判定されるまでの分割
処理を繰り返す回路分割方法である。特開平2-87279は
回路を子回路とそれを参照する親回路によって構成する
回路分割方法において、最上位レベルの親回路から葉に
至るパスのシミュレーション時間を予測算定し、シミュ
レーション時間が最大であるパスに属する葉を２分し、
葉の数がプロセッサ数に等しいか、処理時間短縮が飽和
状態になるまで繰り返す回路分割方法であるこれらの方
法は複数の計算機を用いて回路シミュレーションを行う
並列回路シミュレーションのための方法であり、計算機
１台だけ用いた回路シミュレーション方法に適した方法
ではない。

【０００５】

【発明が解決しようとする課題】電子回路の解析を行う
回路シミュレータでは解析をする処理の一つとして、回
路行列計算があり行列を解く際にLU分解法を用いて解く
方法がある。LU分解の際には行列要素のフィルインが生
じ、その分回路行列時の演算量が増加する。通常の回路
シミュレーションではフィルインにより増加する要素数
を最小限に抑えるために、解析前に回路行列のリオーダ
リング（行や列の入れ換え)を行なう。

【０００６】一方で、回路の高速解析手法の一つとして
回路分割型回路シミュレータがある。これは、回路を複
数の部分回路（ブロック）に分割し、動作していないブ
ロックについては、そのブロックに所属する素子の素子
計算や行列計算を省略するものである。分割の方法とし
ては、設計者が回路図を作成したときのサブ回路の構造
をもとにブロック分割する方法がある。これは、回路図
を作成する際には同じ機能を構成する回路を同一のサブ
回路とすることが多く、同じ機能を構成する回路素子は
同時に動作することが多いため、回路の潜伏性を利用す
るのに都合がいいためである。また、回路を階層構造を
もつブロックに分割して解析することによって、回路の
潜伏性をより効率よく利用できる。

【０００７】ところが、上記の従来法のようにサブ回路
の単位でブロックを構成して、そのまま回路行列を生成
する方法では、ブロック単位になっている回路行列の構
造を保つためにリオーダの際に交換できる行や列に制限
があり、そのためLU分解時のフィルインの増加による演
算量の増加を招く。

【０００８】また、上記従来技術の２つ目の方法では、
１階層に分割しているため下の階層の回路しか動作して
いないときに、動作していない回路部分の計算が必要に
なることがある。また、回路によっては上位ブロックの
インタフェースノードをブロックの内部ノードとするこ
とによって最上位回路に所属するノードのリオーダリン
グの制限が生じ、かえってLU分解時の演算数が増えるこ
ともある。

【０００９】本発明は、回路の階層構造を保ったまま下
位ブロックのノードを上位ブロックに移動することによ
って、潜伏性を効率良く利用して、行列計算にかかる計
算時間を低減するための回路分割方法を提供するもので
ある。

【００１０】

【課題を解決するための手段】本発明は１つの計算機上
で行う回路シミュレーションにおいて、設計者が図面入
力した回路構造を基に、回路を階層構造を持つブロック
に分割する。ここでいうブロックとはサブ回路を単位と
して構成した回路素子とノードの集合であり、解析をす
るときの単位となるものである。ここで生成したブロッ
クをもとに、素子の所属ブロックは移動することなく、
ブロック間のインタフェースノードになっているものに
ついて所属ブロックを変更する。この時の移動の方法は
ある階層のブロック間のインタフェースノードになって
いるものを、上位ブロックの階層に引き上げるものであ
る。インタフェースノードを引き上げた後に回路全体、
及び、最上位ブロックのLU分解時の演算数を求める。そ
して、その時のインタフェースノードの状態とそれぞれ
の演算数を格納しておく。次に引き上げるインタフェー
スノードの階層、あるいは、移動する先の階層を変更
し、再び回路全体、最上位ブロックのLU分解時の演算数
を求め、回路全体の演算数と最上位ブロックの演算数を
求める。これを複数回繰り返した後に回路全体の演算数
と最上位ブロックの演算数が前回に対して増加したら、
その時あるいはその前のインタフェースノードの状態で
回路行列を生成し回路シミュレーションを行う。

【００１１】

【発明の実施の形態】図１と図２を用いて本発明の概要
を説明する。図２に回路シミュレーション全体の処理フ
ローを示し、その中で回路を分割して回路行列を作成す
る処理の詳細を図１に示す。まず、設計者の作成した回
路図面を基に、データを読み込んで回路記述を作成し
（ステップ２１）、回路をブロックに分割してブロック
単位の行列を生成する（ステップ２１）。このとき、ま
ず回路を解析を行う単位となるブロックを生成する（ス
テップ１）。例えば、入力となる回路を図３とする。こ
の回路のサブ回路の階層構造は図４のようになる。この
サブ回路を単位として１つ以上のサブ回路でブロックを
構成する。例えばメイン回路をブロック１、X1というサ
ブ回路をブロック２、X11, X111, X112をブロック３、X
12, X121, X122をブロック４、X2をブロック５、X21を
ブロック６、X211をブロック７、X212をブロック８、X2
2をブロック９、X221をブロック１０、X222をブロック
１１とする。まず、ループカウンタを初期化し（ステッ
プ２）、ループに入ってカウンタをインクリメントする
（ステップ３）。次にこの回路の回路行列を生成する
（ステップ４）。この時の回路行列は従来から知られて
いる再帰的縁付きブロック対角構造回路行列とし、この
とき各ノードには図３に示すノード番号を割り当て図５
に示す回路行列を生成する。そして、この行列のリオー
ダリングをする（ステップ５）。これはLU分解時の演算
数を減らすために行うものであり、再帰的縁付きブロッ
ク対角構造回路行列についてリオーダする場合には、回
路行列のブロック単位での構成を崩さないために、ブロ
ックの範囲内で行あるいは列の入れ替えを行う。 この
ときのリオーダリングは、従来から知られているマルコ
ビッツ法などをブロック内に適用する。そして、LU分解
を行い、回路全体のLU分解時の演算数と最上位ブロック
の演算数を求める（ステップ６）。そして、この時の値
を格納しておく。ここで、処理が１回目かどうかの判定
をして（ステップ７）、１回目（ｎ＝１）の時はインタ
フェースノードの所属ブロックを変える（ステップ１
０）。この時のインタフェースノードの所属ブロックの
変更の方法は、ある階層までのインタフェースノードを
最上位ブロックに上げるものである。例えば、図３の回
路で２階層目のインタフェースノードを最上位に引き上
げるものとする。２階層目とは２階層目のブロック（ブ
ロック２、ブロック５）の内部ノードのことをいい、ノ
ード９、ノード１０、ノード１７、ノード１８のことを
いう。この４つのノードの所属をブロック２、ブロック
５からブロック１に変更する。インタフェースノードの
所属ブロックを変更した後に、再び回路行列を生成する
（ステップ４）。この時の回路行列は図６の様になる。
図中にあるノード番号とはインタフェースノードの所属
ブロックを変更する前の番号であり、変更後のノード番
号は上から下へ、あるいは左から右への連番となる。こ
の状態で再びLU分解を行い、LU分解時の演算量をカウン
トする。そして、回路全体のLU分解時の演算数と最上位
回路の演算数を求め、その時の値とインタフェースノー
ドの情報を格納しておく。処理が２回目以上の時には回
路全体のLU分解時の演算数、あるいは、最上位ブロック
の演算数が前回（ｎー１回目）に対して増加したかどう
かの判定をする（ステップ８）。このとき、増加してい
ないときはインタフェースノードの移動階層がブロック
の最も深い階層より小さいかどうかの判定をし（ステッ
プ９）、小さいときにはインタフェースノードの所属ブ
ロックを再び変えて（ステップ１０）、ステップ３から
の処理を再び繰り返す。回路全体のLU分解時の演算数、
あるいは、最上位ブロックの演算数が前回（ｎー１回
目）に対して増加してる場合には、処理の回数（ｎ）を
判定して（ステップ１１）、次の処理を行う。ｎが３回
目以上の場合には、前回（ｎー１回目）の条件でインタ
フェースノードの所属ブロックを決定し（ステップ１
２）、回路行列を生成する（ステップ１４）。ｎが２回
目の場合には今回の条件でインタフェースノードの所属
ブロックを決定し（ステップ１３）、回路行列を生成す
る（ステップ１４）。そして、ブロック単位で行列のリ
オーダリングを行う（ステップ１５）。

【００１２】上記の回路分割方法を用いて回路をブロッ
クに分割して回路行列を生成した後に次のステップで回
路シミュレーションを行う。まず、ブロック単位で潜伏
判定をする（ステップ２３）。これは、ブロックに所属
する素子が動作したかどうか、あるいは、ブロックに所
属するノードの電圧が変化したかどうかを判定するステ
ップである。潜伏している場合には、次のブロックに対
して同じ判定を行い、潜伏していない場合には、ブロッ
クに所属する素子の素子計算（ステップ２４）とブロッ
クに所属する部分行列のLU分解を行う（ステップ２
５）。これを全ブロックについて行ったかどうか判定し
（ステップ２６）、終了したら回路行列全体の前進、後
退代入を行い（ステップ２７）、反復ループで収束した
かどうかの判定をブロック単位に行う（ステップ２
８）。１つでも収束していないブロックがある場合には
上記処理を繰り返し、全ブロックが収束した場合には解
析時刻が終了時刻に達したかどうか判定し（ステップ２
９）達してしないときは解析時刻を更新して（ステップ
３０）、解析終了時刻まで上記処理を繰り返す。そし
て、ノード電圧等の解析結果を出力して（ステップ３
１）終了する。

【００１３】これに対して従来から用いられている回路
シミュレーションの方法は図７に示すように、回路のデ
ータを読み込んで（ステップ４１）回路を分割すること
なく回路行列を生成し（ステップ４２）、行列のリオー
ダリングを行い（ステップ４３）回路全体の素子計算
（ステップ４４）、LU分解（ステップ４５）、前進後退
代入（ステップ４６）を行う。そして、回路全体につい
て収束判定をし（ステップ４７）、回路の一部でも収束
判定を満たさなければまた、ステップ４４からの処理を
繰り返す。そして、回路全体が収束した場合には解析時
刻が終了時刻に達したかどうか判定し（ステップ４８）
達してしないときは解析時刻を更新して（ステップ４
９）、解析終了時刻まで上記処理を繰り返す。そして、
ノード電圧等の解析結果を出力して（ステップ５０）終
了する。

【００１４】また、回路を分割してシミュレーションを
する方法として従来から用いられている方法を図８に示
す。この方法は、まずデータを読み込んで（ステップ５
１）、回路をサブ回路単位で階層構造を持つブロックに
分解し（ステップ５２）、回路行列を生成（ステップ５
３）、そして、ブロック単位で回路行列のリオーダリン
グをし（ステップ５４）、その後のインタフェースノー
ドの所属ブロックの変更は行わずに回路シミュレーショ
ンを始めるものである。まず、ブロック単位で潜伏判定
をし（ステップ５５）、潜伏している場合には、次のブ
ロックに対して同じ処理を行い、潜伏していない場合に
は、ブロックに所属する素子の素子計算（ステップ５
６）とブロックに所属する部分行列のLU分解を行う（ス
テップ５７）。これを全ブロックについて行ったかどう
か判定し（ステップ５８）、終了したら回路行列全体の
前進、後退代入を行い（ステップ５９）、反復ループで
収束したかどうかの判定をブロック単位に行う（ステッ
プ６０）。収束していない場合には上記処理を繰り返
し、収束した場合には解析時刻が終了時刻に達したかど
うか判定し（ステップ６１）達してしないときは解析時
刻を更新して（ステップ６２）、解析終了時刻まで上記
処理を繰り返す。そして、ノード電圧等の解析結果を出
力して（ステップ６３）終了する。

【００１５】従来方法はブロックを分割して回路行列を
生成し、そのまま回路シミュレーションを行うのに対し
て、本発明は一旦回路行列を生成した後にインタフェー
スノードの移動を行って回路行列の変更をしてから、素
子計算、行列計算等の処理に入る点が異なる。

【００１６】

【発明の効果】回路行列全体の演算数と最上位ブロック
の演算数を考慮してインターフェースノードの所属階層
を決めることによって、回路を分割して動作しているブ
ロックのみ解析を行う回路分割型回路シミュレーション
において、少ない演算量で行列計算を行うことができ
る。

【図面の簡単な説明】

【図１】本発明による回路分割方法の処理フローであ
る。

【図２】本発明の回路分割方法を用いた回路シミュレー
ション処理フローである。

【図３】分割する回路の回路図である。

【図４】分割する回路の階層構造図である。

【図５】再帰的縁付きブロック対角構造回路行列であ
る。

【図６】インタフェースノードの所属ブロック変更後の
再帰的縁付きブロック対角構造回路行列である。

【図７】従来の回路シミュレーション処理フローであ
る。

【図８】従来の回路分割方法を用いた回路シミュレーシ
ョン処理フローである。

【符号の説明】

１…サブ回路，２…回路素子，３…ノード，４…ブロッ
ク，５…サブ回路，６…再帰的縁付きブロック対角構造
回路行列，７…行列要素。

Claims (1)

【特許請求の範囲】
1. 【請求項１】回路をブロックに分割して回路シミュレー
   ションするときの分割方法であって、 下の階層のイン
   タフェースノードを階層の浅いほうから順番に上位ブロ
   ックに移動して再帰的縁付きブロック対角構造行列を生
   成し、LU分解時の回路全体の演算数と最上位ブロックの
   演算数の数を求め、回路全体の演算数、あるいは、最上
   位ブロックの演算数の数のいずれかが前の数より増加し
   たところで処理を止め、その状態でインタフェースノー
   ドの所属ブロックを決定し、回路を分割することを特徴
   とする回路シミュレーションの回路分割方法。