(57)【要約】【課題】大規模な回路の回路シミュレーション時間を短縮する。【解決手段】ステップ１３〜２１で、分割終了フラグが立っていない且つ予測値が最大値の部分回路を分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和を求め、分割後予測値の和が最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて、最大値の部分回路の分割不可または分割可を判定し、分割不可の場合、分割前の状態に復帰して、最大値の部分回路に分割終了フラグを立て、分割可の場合、全ての回路を複数のプロセッサに割り当てて、回路全体の並列回路シミュレーション時間の予測値を求め、現在までの最小値である場合、現在の分割状態を一時保存し、ステップ２２〜２３で、全ての部分回路に分割終了フラグが立つまで繰り返す。【選択図】　　　図１
2004013465.tif 000002
【特許請求の範囲】
【請求項１】
トランジスタ，抵抗を含む物理的素子からなる回路を複数プロセッサにより並列回路シミュレーションするため、前記回路を入力し回路全体を最上位の１つの部分回路と見做して階層的に分割し出力する回路分割方法において、
分割終了フラグが立っていない部分回路から、部分回路の回路シミュレーション時間の予測値が最大値の部分回路を検索し、２つの下位の部分回路と、これら２つの下位の部分回路を接続する節点からなり部分回路間を結合する結合回路とに分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求める処理と、
前記分割後予測値の和が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定し、分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立て、分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を前記最小値として一時保存し且つ現在の分割状態を一時保存する処理とを、
全ての部分回路に分割終了フラグが立つまで繰り返すことを特徴とする回路分割方法。
【請求項２】
前記回路を入力し回路全体を最上位の１つの部分回路と見做して、前記予測値を求め、同時に、前記最小値として一時保存する入力ステップと、
分割終了フラグが立っていない部分回路から、前記予測値が最大値の部分回路を検索する検索ステップと、
前記最大値の部分回路を２つの下位の部分回路と前記結合回路とに分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求める分割ステップと、
前記分割後予測値の和が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定する分割判定ステップと、
この分割判定ステップで前記最大値の部分回路が分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立てる復帰ステップと、
前記分割判定ステップで前記最大値の部分回路が分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を前記最小値として一時保存し且つ現在の分割状態を一時保存する一時保存ステップと、
全ての部分回路に分割終了フラグが立っていない場合、前記検索ステップに戻る終了判定ステップと、
一時保存された最小値の分割状態を出力する出力ステップとを含む、請求項１記載の回路分割方法。
【請求項３】
前記部分回路または前記結合回路を記述する線形連立方程式の係数行列である回路行列を作成し、１ニュートン反復当たりのモデル計算時間および行列演算時間を測定し、測定結果に基づき前記回路行列のモデル計算時間および行列演算時間の和を求めて前記部分回路または前記結合回路の回路シミュレーション時間の予測値とする、請求項１または２記載の回路分割方法。
【請求項４】
前記部分回路または前記結合回路の素子数に基づきモデル計算の演算回数を見積り、前記部分回路または前記結合回路を記述する線形連立方程式の係数行列である回路行列の行列計算の演算回数を見積って、モデル計算時間および行列計算時間をそれぞれ見積り、これらの和を求めて前記部分回路または前記結合回路の回路シミュレーション時間の予測値とする、請求項１または２記載の回路分割方法。
【請求項５】
トランジスタ，抵抗を含む物理的素子からなる回路を複数プロセッサにより並列回路シミュレーションするため、前記回路を入力し回路全体を最上位の１つの部分回路と見做して階層的に分割し出力する回路分割方法において、
分割終了フラグが立っていない部分回路から、部分回路の回路シミュレーション処理経路のクリティカルパス長が最大値の部分回路を検索し、２つの下位の部分回路と、これら２つの下位の部分回路を接続する節点からなり部分回路間を結合する結合回路とに分割し、新たに分割された回路の回路シミュレーション処理経路のクリティカルパス長をそれぞれ予測し分割後最大値を求める処理と、
前記分割後最大値が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定し、分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立て、分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を求め前記最小値として一時保存し且つ現在の分割状態を一時保存する処理とを、
全ての部分回路に分割終了フラグが立つまで繰り返すことを特徴とする回路分割方法。
【請求項６】
前記部分回路または前記結合回路を記述する線形連立方程式の解法の１つであるガウス消去法の処理経路を各変数の消去処理時間により重み付け、前記処理経路の重みの総和が最大のものを前記部分回路または前記結合回路の回路シミュレーション処理経路のクリティカルパス長とする、請求項５記載の回路分割方法。
【請求項７】
トランジスタ，抵抗を含む物理的素子からなる回路を複数プロセッサにより並列回路シミュレーションするため、前記回路を入力し回路全体を最上位の１つの部分回路と見做して階層的に分割し出力する回路分割処理をコンピュータに実行させる回路分割プログラムにおいて、
前記回路分割処理が、分割終了フラグが立っていない部分回路から、部分回路の回路シミュレーション時間の予測値が最大値の部分回路を検索し、２つの下位の部分回路と、これら２つの下位の部分回路を接続する節点からなり部分回路間を結合する結合回路とに分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求める処理と、
前記分割後予測値の和が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定し、分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立て、分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を前記最小値として一時保存し且つ現在の分割状態を一時保存する処理とを、
全ての部分回路に分割終了フラグが立つまで繰り返すことを特徴とする回路分割プログラム。
【請求項８】
前記回路分割処理が、前記回路を入力し回路全体を最上位の１つの部分回路と見做して、前記予測値を求め、同時に、前記最小値として一時保存する入力ステップと、
分割終了フラグが立っていない部分回路から、前記予測値が最大値の部分回路を検索する検索ステップと、
前記最大値の部分回路を２つの下位の部分回路と前記結合回路とに分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求める分割ステップと、
前記分割後予測値の和が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定する分割判定ステップと、
この分割判定ステップで前記最大値の部分回路が分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立てる復帰ステップと、
前記分割判定ステップで前記最大値の部分回路が分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を前記最小値として一時保存し且つ現在の分割状態を一時保存する一時保存ステップと、
全ての部分回路に分割終了フラグが立っていない場合、前記検索ステップに戻る終了判定ステップと、
一時保存された最小値の分割状態を出力する出力ステップとを含む、請求項７記載の回路分割プログラム。
【請求項９】
前記部分回路または前記結合回路を記述する線形連立方程式の係数行列である回路行列を作成し、１ニュートン反復当たりのモデル計算時間および行列演算時間を測定し、測定結果に基づき前記回路行列のモデル計算時間および行列演算時間の和を求めて前記部分回路または前記結合回路の回路シミュレーション時間の予測値とする、請求項７または８記載の回路分割プログラム。
【請求項１０】
前記部分回路または前記結合回路の素子数に基づきモデル計算の演算回数を見積り、前記部分回路または前記結合回路を記述する線形連立方程式の係数行列である回路行列の行列計算の演算回数を見積って、モデル計算時間および行列計算時間をそれぞれ見積り、これらの和を求めて前記部分回路または前記結合回路の回路シミュレーション時間の予測値とする、請求項７または８記載の回路分割プログラム。
【請求項１１】
トランジスタ，抵抗を含む物理的素子からなる回路を複数プロセッサにより並列回路シミュレーションするため、前記回路を入力し回路全体を最上位の１つの部分回路と見做して階層的に分割し出力する回路分割処理をコンピュータに実行させる回路分割プログラムにおいて、
前記回路分割処理が、分割終了フラグが立っていない部分回路から、部分回路の回路シミュレーション処理経路のクリティカルパス長が最大値の部分回路を検索し、２つの下位の部分回路と、これら２つの下位の部分回路を接続する節点からなり部分回路間を結合する結合回路とに分割し、新たに分割された回路の回路シミュレーション処理経路のクリティカルパス長をそれぞれ予測し分割後最大値を求める処理と、
前記分割後最大値が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定し、分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立て、分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を求め前記最小値として一時保存し且つ現在の分割状態を一時保存する処理とを、
全ての部分回路に分割終了フラグが立つまで繰り返すことを特徴とする回路分割プログラム。
【請求項１２】
前記部分回路または前記結合回路を記述する線形連立方程式の解法の１つであるガウス消去法の処理経路を各変数の消去処理時間により重み付け、前記処理経路の重みの総和が最大のものを前記部分回路または前記結合回路の回路シミュレーション処理経路のクリティカルパス長とする、請求項１１記載の回路分割プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、回路分割方法に関し、特に、複数プロセッサにより並列回路シミュレーションするための回路分割方法に関する。
【０００２】
【従来の技術】
従来、この種の回路分割方法は、入出力装置，記憶装置および処理装置を備え一般的に構成されたコンピュータに、回路分割プログラムをインストールして各コマンド入力に応じて実行させることにより実施され、たとえば、トランジスタ，抵抗を含む物理的素子からなる回路を複数プロセッサにより並列回路シミュレーションするため、回路を入力し回路全体を最上位の１つの部分回路と見做して階層的に分割し出力する。なお、この回路分割方法の処理対象は、「素子モデルを用いて回路を記述した情報、すなわち、線形連立方程式、または、その係数行列である回路行列」であるが、大部分は、回路の素子以上のレベルで説明できるので、用語の定義時を除き、単に「回路」または「素子」と云う。
【０００３】
この従来の回路分割方法では、部分回路の分割繰り返し過程で、分割された部分回路数がプロセッサ数に達するか、または、並列回路シミュレーション時間の短縮が飽和するまで、部分回路の分割が繰り返される。たとえば、この従来の回路分割方法の１つとして、特開平４−２１０７１号公報に開示されている並列回路シミュレーション装置で実施されている回路分割方法がある。
【０００４】
簡単に説明すると、この回路分割方法では、部分回路の分割繰り返し過程で、分割された部分回路数がプロセッサ数に達したかを判定し、また、並列回路シミュレーション時間の短縮が飽和したかを判定する。このとき、並列回路シミュレーション時間の短縮の飽和または不飽和は、並列回路シミュレーション予測時間が長い未分割の部分回路を順に２つの部分回路に分割する時点から、既に分割された部分回路の最大並列回路シミュレーション予測時間が未分割の部分回路の最大並列回路シミュレーション予測時間より長くなる時点までの区間を１世代として定義し、世代ごとに、部分回路全ての並列回路シミュレーション予測時間を求め、前の世代の並列回路シミュレーション予測時間より長いか否かに応じて判定される。これらの判定結果に応じて、部分回路の分割繰り返しが停止され、最小の並列回路シミュレーション処理間を持つ回路分割が行われる。
【０００５】
また、図４は、他の従来の回路分割方法の概略処理例を示す流れ図であり、特開平９−３１９７８４号公報に開示され、説明の便宜上、符号変更した回路分割方法を示す。
【０００６】
この従来の回路分割方法では、まず、ステップ４１で、シミュレーション対象の回路を入力し、ステップ４２〜４７で、初期クラスタリング処理が行われ、ステップ４８〜５３で、ミニカット処理が行われる。初期クラスタリング処理では、各素子を一つのクラスタとして、クラスタ対を選択してマージを繰り返し、目標値とほぼ同じ大きさを持つ、素子の集まりであるクラスタに分割する。また、ミニカット処理では、初期クラスタリング処理で分割されたクラスタを選択および移動して、大きさの均衡が保たれた部分回路に分割し出力する。
【０００７】
これら初期クラスタリング処理，ミニカット処理において、クラスタ，部分回路の素子数に基づきモデル計算の演算回数を見積り、クラスタ，部分回路を記述する線形連立方程式の係数行列である回路行列の行列計算の演算回数をそれぞれ見積って、モデル計算時間および行列計算時間をそれぞれ見積り、これらの和を求めて、クラスタ，部分回路の回路シミュレーション時間の予測値であるクラスタ，部分回路の大きさとし、クラスタ，部分回路の分割制御のため用いている。ここで、回路行列の行列計算の演算回数は、線形連立方程式の解を得るため回路行列を三角行列の積に分解するＬＵ（Ｌｏｗｅｒ／Ｕｐｐｅｒ）分解において変数を消去するときの更新演算回数であり、行列計算を用いずに、シミュレーション前に求められる。
【０００８】
このため、この従来の回路分割方法は、回路分割時に行われるクラスタ，部分回路に対する回路シミュレーション時間の予測値の精度が向上し、均等になり、結果として並列回路シミュレーションに要する時間が短縮される。
【０００９】
【発明が解決しようとする課題】
しかし、上述した従来の回路分割方法では、いずれも、分割された部分回路数がプロセッサ数以下であることを前提とし、分割された部分回路数がプロセッサ数に達するまでしか、回路分割を行わない。このため、シミュレーション対象の回路が大規模になると、回路規模が大規模な部分回路が生成される。しかし、部分回路の回路シミュレーション時間は、部分回路の回路行列サイズのα（１＜α＜３）乗に比例して増大するため、回路規模が増大するに従って回路の回路シミュレーション時間が急激に増大してしまうという問題がある。
【００１０】
したがって、本発明の目的は、大規模な回路の回路シミュレーション時間を短縮することにある。
【００１１】
【課題を解決するための手段】
そのため、本発明は、トランジスタ，抵抗を含む物理的素子からなる回路を複数プロセッサにより並列回路シミュレーションするため、前記回路を入力し回路全体を最上位の１つの部分回路と見做して階層的に分割し出力する回路分割方法において、
分割終了フラグが立っていない部分回路から、部分回路の回路シミュレーション時間の予測値が最大値の部分回路を検索し、２つの下位の部分回路と、これら２つの下位の部分回路を接続する節点からなり部分回路間を結合する結合回路とに分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求める処理と、
前記分割後予測値の和が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定し、分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立て、分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を前記最小値として一時保存し且つ現在の分割状態を一時保存する処理とを、
全ての部分回路に分割終了フラグが立つまで繰り返している。
【００１２】
また、前記回路を入力し回路全体を最上位の１つの部分回路と見做して、前記予測値を求め、同時に、前記最小値として一時保存する入力ステップと、
分割終了フラグが立っていない部分回路から、前記予測値が最大値の部分回路を検索する検索ステップと、
前記最大値の部分回路を２つの下位の部分回路と前記結合回路とに分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求める分割ステップと、
前記分割後予測値の和が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定する分割判定ステップと、
この分割判定ステップで前記最大値の部分回路が分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立てる復帰ステップと、
前記分割判定ステップで前記最大値の部分回路が分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を前記最小値として一時保存し且つ現在の分割状態を一時保存する一時保存ステップと、
全ての部分回路に分割終了フラグが立っていない場合、前記検索ステップに戻る終了判定ステップと、
一時保存された最小値の分割状態を出力する出力ステップとを含んでいる。
【００１３】
また、前記部分回路または前記結合回路を記述する線形連立方程式の係数行列である回路行列を作成し、１ニュートン反復当たりのモデル計算時間および行列演算時間を測定し、測定結果に基づき前記回路行列のモデル計算時間および行列演算時間の和を求めて前記部分回路または前記結合回路の回路シミュレーション時間の予測値としている。
【００１４】
また、前記部分回路または前記結合回路の素子数に基づきモデル計算の演算回数を見積り、前記部分回路または前記結合回路を記述する線形連立方程式の係数行列である回路行列の行列計算の演算回数を見積って、モデル計算時間および行列計算時間をそれぞれ見積り、これらの和を求めて前記部分回路または前記結合回路の回路シミュレーション時間の予測値としている。
【００１５】
また、トランジスタ，抵抗を含む物理的素子からなる回路を複数プロセッサにより並列回路シミュレーションするため、前記回路を入力し回路全体を最上位の１つの部分回路と見做して階層的に分割し出力する回路分割方法において、
分割終了フラグが立っていない部分回路から、部分回路の回路シミュレーション処理経路のクリティカルパス長が最大値の部分回路を検索し、２つの下位の部分回路と、これら２つの下位の部分回路を接続する節点からなり部分回路間を結合する結合回路とに分割し、新たに分割された回路の回路シミュレーション処理経路のクリティカルパス長をそれぞれ予測し分割後最大値を求める処理と、
前記分割後最大値が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定し、分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立て、分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を求め前記最小値として一時保存し且つ現在の分割状態を一時保存する処理とを、
全ての部分回路に分割終了フラグが立つまで繰り返している。
【００１６】
また、前記部分回路または前記結合回路を記述する線形連立方程式の解法の１つであるガウス消去法の処理経路を各変数の消去処理時間により重み付け、前記処理経路の重みの総和が最大のものを前記部分回路または前記結合回路の回路シミュレーション処理経路のクリティカルパス長とする、請求項５記載の回路分割方法。
【００１７】
また、本発明は、トランジスタ，抵抗を含む物理的素子からなる回路を複数プロセッサにより並列回路シミュレーションするため、前記回路を入力し回路全体を最上位の１つの部分回路と見做して階層的に分割し出力する回路分割処理をコンピュータに実行させる回路分割プログラムにおいて、
前記回路分割処理が、分割終了フラグが立っていない部分回路から、部分回路の回路シミュレーション時間の予測値が最大値の部分回路を検索し、２つの下位の部分回路と、これら２つの下位の部分回路を接続する節点からなり部分回路間を結合する結合回路とに分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求める処理と、
前記分割後予測値の和が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定し、分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立て、分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を前記最小値として一時保存し且つ現在の分割状態を一時保存する処理とを、
全ての部分回路に分割終了フラグが立つまで繰り返している。
【００１８】
また、前記回路分割処理が、前記回路を入力し回路全体を最上位の１つの部分回路と見做して、前記予測値を求め、同時に、前記最小値として一時保存する入力ステップと、
分割終了フラグが立っていない部分回路から、前記予測値が最大値の部分回路を検索する検索ステップと、
前記最大値の部分回路を２つの下位の部分回路と前記結合回路とに分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求める分割ステップと、
前記分割後予測値の和が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定する分割判定ステップと、
この分割判定ステップで前記最大値の部分回路が分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立てる復帰ステップと、
前記分割判定ステップで前記最大値の部分回路が分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を前記最小値として一時保存し且つ現在の分割状態を一時保存する一時保存ステップと、
全ての部分回路に分割終了フラグが立っていない場合、前記検索ステップに戻る終了判定ステップと、
一時保存された最小値の分割状態を出力する出力ステップとを含んでいる。
【００１９】
また、前記部分回路または前記結合回路を記述する線形連立方程式の係数行列である回路行列を作成し、１ニュートン反復当たりのモデル計算時間および行列演算時間を測定し、測定結果に基づき前記回路行列のモデル計算時間および行列演算時間の和を求めて前記部分回路または前記結合回路の回路シミュレーション時間の予測値としている。
【００２０】
また、前記部分回路または前記結合回路の素子数に基づきモデル計算の演算回数を見積り、前記部分回路または前記結合回路を記述する線形連立方程式の係数行列である回路行列の行列計算の演算回数を見積って、モデル計算時間および行列計算時間をそれぞれ見積り、これらの和を求めて前記部分回路または前記結合回路の回路シミュレーション時間の予測値としている。
【００２１】
また、トランジスタ，抵抗を含む物理的素子からなる回路を複数プロセッサにより並列回路シミュレーションするため、前記回路を入力し回路全体を最上位の１つの部分回路と見做して階層的に分割し出力する回路分割処理をコンピュータに実行させる回路分割プログラムにおいて、
前記回路分割処理が、分割終了フラグが立っていない部分回路から、部分回路の回路シミュレーション処理経路のクリティカルパス長が最大値の部分回路を検索し、２つの下位の部分回路と、これら２つの下位の部分回路を接続する節点からなり部分回路間を結合する結合回路とに分割し、新たに分割された回路の回路シミュレーション処理経路のクリティカルパス長をそれぞれ予測し分割後最大値を求める処理と、
前記分割後最大値が前記最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて前記最大値の部分回路の分割不可または分割可を判定し、分割不可の場合、分割前の状態に復帰して前記最大値の部分回路に分割終了フラグを立て、分割可の場合、全ての部分回路および結合回路を前記複数のプロセッサに割り当てて回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さい場合、求めた予測値を求め前記最小値として一時保存し且つ現在の分割状態を一時保存する処理とを、
全ての部分回路に分割終了フラグが立つまで繰り返している。
【００２２】
また、前記部分回路または前記結合回路を記述する線形連立方程式の解法の１つであるガウス消去法の処理経路を各変数の消去処理時間により重み付け、前記処理経路の重みの総和が最大のものを前記部分回路または前記結合回路の回路シミュレーション処理経路のクリティカルパス長としている。
【００２３】
【発明の実施の形態】
本発明による回路分割方法は、従来と同じく、入出力装置，記憶装置および処理装置を備え一般的に構成されたコンピュータに、回路分割プログラムをインストールして各コマンド入力に応じて実行させることにより実施され、たとえば、トランジスタ，抵抗を含む物理的素子からなる回路を複数プロセッサにより並列回路シミュレーションするため、回路を入力し回路全体を最上位の１つの部分回路と見做して階層的に分割し出力する。
【００２４】
次に、本発明について、図面を参照して説明する。図１は、本発明の回路分割方法の実施形態を示す流れ図である。ここで、本実施形態の回路分割方法では、分割された回路を記述する線形連立方程式の係数行列である回路行列を作成し、１ニュートン反復当たりのモデル計算時間および行列演算時間を測定し、測定結果に基づき、回路行列のモデル計算時間および行列演算時間の和を求めて、分割された回路の回路シミュレーション時間の予測値とする。
【００２５】
まず、ステップ１１，１２で、回路を入力し、回路全体を最上位の１つの部分回路と見做して、部分回路の回路シミュレーション時間の予測値を求め、同時に、回路全体に対する並列回路シミュレーション時間の予測値の最小値として一時保存する。
【００２６】
ステップ１３で、分割終了フラグが立っていない部分回路から、予測値が最大値の部分回路を検索し、ステップ１４，１５で、２つの下位の部分回路と、これら２つの下位の部分回路を接続する節点からなり部分回路間を結合する結合回路とに分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和を求める。
【００２７】
ステップ１６で、分割後予測値の和が最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて、最大値の部分回路の分割不可または分割可を判定し、分割不可または分割可に応じてステップ１７またはステップ１８に進む。ステップ１７で、分割前の状態に復帰して、最大値の部分回路に分割終了フラグを立て、ステップ２２に進む。また、ステップ１８〜２１で、複数のプロセッサごとの予測値が均等になるように、たとえば、クリティカルパス法（参考文献：「並列処理技術」、笠原博徳著、コロナ者）を用いて、全ての部分回路および結合回路を複数のプロセッサに割り当てて、回路全体の並列回路シミュレーション時間の予測値を求め、一時保存中の最小値より小さいか判定し、小さい場合、求めた予測値を最小値として一時保存し且つ現在の分割状態を一時保存する。
【００２８】
ステップ２２で、全ての部分回路に分割終了フラグが立っているか判定し、全ての部分回路に分割終了フラグが立っていない場合、ステップ１３に戻り、全ての部分回路に分割終了フラグが立っている場合、ステップ２３に進み、一時保存された最小値の分割状態を出力する。
【００２９】
次に、この実施形態の回路分割方法について実際の適用例に基づき具体的に説明する。図２，図３は、この実施形態の回路分割方法をＲＤＲＡＭ回路に適用した例の前半，後半をそれぞれ示す説明図であり、分図（１）〜（１１）は、この実施形態の回路分割方法により進行するＲＤＲＡＭ回路の分割状態を時系列にそれぞれ示す。ここで、分割された部分回路，結合回路を○印および符号Ｓ０〜Ｓ２２，Ｃ１〜Ｃ１１でそれぞれ表し、部分回路Ｓ０〜Ｓ２２または結合回路Ｃ１〜Ｃ１１の回路シミュレーション時間の予測値を括弧内の数値でそれぞれ示し、回路全体に対する並列回路シミュレーション時間の予測値Ｔの最小値Ｔｍｉｎを括弧内に示す。
【００３０】
図１の流れ図に基づき時系列に説明する。まず、ステップ１１，１２で、ＲＤＲＡＭメモリ回路を入力し、回路全体を最上位の１つの部分回路Ｓ０と見做して、部分回路Ｓ０の回路シミュレーション時間の予測値（１０２２０００）を求め、同時に、回路全体に対する並列回路シミュレーション時間の予測値Ｔの最小値Ｔｍｉｎとして一時保存する。
【００３１】
ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ０から最大値Ｗｉ＝１０２２０００の部分回路Ｓ０を検索し、分図（１）に示すように、２つの部分回路Ｓ１，Ｓ２と結合回路Ｃ１とに分割し、新たに分割された回路Ｓ１，Ｓ２，Ｃ１の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝１２６４４５７を求める。
【００３２】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上であるが、部分回路数がプロセッサ数を超えていないので、最大値の部分回路Ｓ０が分割可と判定し、全ての部分回路Ｓ１，Ｓ２および結合回路Ｃ１を２つのプロセッサ１，２に割り当てて、回路全体の並列回路シミュレーション時間の予測値Ｔ＝８５０１５４を求め、一時保存中の最小値Ｔｍｉｎより小さいので、求めた予測値Ｔ＝８５０１５４を最小値Ｔｍｉｎとして一時保存し且つ現在の分割状態を一時保存する。
【００３３】
ステップ２２で、部分回路Ｓ１，Ｓ２に分割終了フラグが立っていないので、ステップ１３に戻る。
【００３４】
次に、ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ１，Ｓ２から最大値Ｗｉ＝７１６４９１の部分回路Ｓ２を検索し、分図（２）に示すように、２つの部分回路Ｓ３，Ｓ４と結合回路Ｃ２とに分割し、新たに分割された回路Ｓ３，Ｓ４，Ｃ２の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝６３１７５３を求める。
【００３５】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上でないので、最大値の部分回路Ｓ２が分割可と判定し、全ての部分回路Ｓ１，Ｓ３，Ｓ４および結合回路Ｃ１，Ｃ２を２つのプロセッサ１，２に割り当てて、回路全体の並列回路シミュレーション時間の予測値Ｔ＝７６５４１６を求め、一時保存中の最小値Ｔｍｉｎより小さいので、求めた予測値Ｔ＝７６５４１６を最小値Ｔｍｉｎとして一時保存し且つ現在の分割状態を一時保存する。
【００３６】
ステップ２２で、部分回路Ｓ１，Ｓ３，Ｓ４に分割終了フラグが立っていないので、ステップ１３に戻る。
【００３７】
次に、ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ１，Ｓ３，Ｓ４から最大値Ｗｉ＝４１４３０３の部分回路Ｓ１を検索し、分図（３）に示すように、２つの部分回路Ｓ５，Ｓ６と結合回路Ｃ３とに分割し、新たに分割された回路Ｓ５，Ｓ６，Ｃ３の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝５７６６６２を求める。
【００３８】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上であり且つ部分回路数がプロセッサ数を超えているので、最大値の部分回路Ｓ１が分割不可と判定し、分図（２）に示す分割前の状態に復帰して、最大値の部分回路Ｓ１に分割終了フラグを立てる。
【００３９】
ステップ２２で、部分回路Ｓ３，Ｓ４に分割終了フラグが立っていないので、ステップ１３に戻る。
【００４０】
次に、ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ３，Ｓ４から最大値Ｗｉ＝２６４１８８の部分回路Ｓ４を検索し、分図（４）に示すように、２つの部分回路Ｓ７，Ｓ８と結合回路Ｃ４とに分割し、新たに分割された回路Ｓ７，Ｓ８，Ｃ４の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝３７８９８３を求める。
【００４１】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上であり且つ部分回路数がプロセッサ数を超えているので、最大値の部分回路Ｓ４が分割不可と判定し、分図（２）に示す分割前の状態に復帰して、最大値の部分回路Ｓ４に分割終了フラグを立てる。
【００４２】
ステップ２２で、部分回路Ｓ３に分割終了フラグが立っていないので、ステップ１３に戻る。
【００４３】
次に、ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ３から最大値Ｗｉ＝２５４７３０の部分回路Ｓ３を検索し、分図（５）に示すように、２つの部分回路Ｓ９，Ｓ１０と結合回路Ｃ５とに分割し、新たに分割された回路Ｓ９，Ｓ１０，Ｃ５の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝２２８５５５を求める。
【００４４】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上でないので、最大値の部分回路Ｓ３が分割可と判定し、全ての部分回路Ｓ１，Ｓ４，Ｓ９，Ｓ１０および結合回路Ｃ１，Ｃ２，Ｃ５を２つのプロセッサ１，２に割り当てて、回路全体の並列回路シミュレーション時間の予測値Ｔ＝７３９２４１を求め、一時保存中の最小値Ｔｍｉｎより小さいので、求めた予測値Ｔ＝７３９２４１を最小値Ｔｍｉｎとして一時保存し且つ現在の分割状態を一時保存する。
【００４５】
ステップ２２で、部分回路Ｓ９，Ｓ１０に分割終了フラグが立っていないので、ステップ１３に戻る。
【００４６】
次に、ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ９，Ｓ１０から最大値Ｗｉ＝１０７７４２の部分回路Ｓ９を検索し、分図（６）に示すように、２つの部分回路Ｓ１１，Ｓ１２と結合回路Ｃ６とに分割し、新たに分割された回路Ｓ１１，Ｓ１２，Ｃ６の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝７４９９９を求める。
【００４７】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上でないので、最大値の部分回路Ｓ９が分割可と判定し、全ての部分回路Ｓ１，Ｓ４，Ｓ１０，Ｓ１１，Ｓ１２および結合回路Ｃ１，Ｃ２，Ｃ５，Ｃ６を２つのプロセッサ１，２に割り当てて、回路全体の並列回路シミュレーション時間の予測値Ｔ＝７０６４９８を求め、一時保存中の最小値Ｔｍｉｎより小さいので、求めた予測値Ｔ＝７０６４９８を最小値Ｔｍｉｎとして一時保存し且つ現在の分割状態を一時保存する。
【００４８】
ステップ２２で、部分回路Ｓ１０，Ｓ１１，Ｓ１２に分割終了フラグが立っていないので、ステップ１３に戻る。
【００４９】
次に、ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ１０，Ｓ１１，Ｓ１２から最大値Ｗｉ＝７２６５４の部分回路Ｓ１０を検索し、分図（７）に示すように、２つの部分回路Ｓ１３，Ｓ１４と結合回路Ｃ７とに分割し、新たに分割された回路Ｓ１３，Ｓ１４，Ｃ７の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝１１８６４８を求める。
【００５０】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上であり且つ部分回路数がプロセッサ数を超えているので、最大値の部分回路Ｓ１０が分割不可と判定し、分図（６）に示す分割前の状態に復帰して、最大値の部分回路Ｓ１０に分割終了フラグを立てる。
【００５１】
ステップ２２で、部分回路Ｓ１１，Ｓ１２に分割終了フラグが立っていないので、ステップ１３に戻る。
【００５２】
次に、ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ１１，Ｓ１２から最大値Ｗｉ＝２２７５７の部分回路Ｓ１２を検索し、分図（８）に示すように、２つの部分回路Ｓ１５，Ｓ１６と結合回路Ｃ８とに分割し、新たに分割された回路Ｓ１５，Ｓ１６，Ｃ８の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝１８６７０を求める。
【００５３】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上でないので、最大値の部分回路Ｓ１２が分割可と判定し、全ての部分回路Ｓ１，Ｓ４，Ｓ１０，Ｓ１１，Ｓ１５，Ｓ１６および結合回路Ｃ１，Ｃ２，Ｃ５，Ｃ６，Ｃ８を２つのプロセッサ１，２に割り当てて、回路全体の並列回路シミュレーション時間の予測値Ｔ＝７０２４１１を求め、一時保存中の最小値Ｔｍｉｎより小さいので、求めた予測値Ｔ＝７０２４１１を最小値Ｔｍｉｎとして一時保存し且つ現在の分割状態を一時保存する。
【００５４】
ステップ２２で、部分回路Ｓ１１，Ｓ１５，Ｓ１６に分割終了フラグが立っていないので、ステップ１３に戻る。
【００５５】
次に、ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ１１，Ｓ１５，Ｓ１６から最大値Ｗｉ＝２２５２６の部分回路Ｓ１１を検索し、分図（９）に示すように、２つの部分回路Ｓ１７，Ｓ１８と結合回路Ｃ９とに分割し、新たに分割された回路Ｓ１７，Ｓ１８，Ｃ９の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝２３６９７を求める。
【００５６】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上であり且つ部分回路数がプロセッサ数を超えているので、最大値の部分回路Ｓ１１が分割不可と判定し、分図（８）に示す分割前の状態に復帰して、最大値の部分回路Ｓ１１に分割終了フラグを立てる。
【００５７】
ステップ２２で、部分回路Ｓ１５，Ｓ１６に分割終了フラグが立っていないので、ステップ１３に戻る。
【００５８】
次に、ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ１５，Ｓ１６から最大値Ｗｉ＝７５５９の部分回路Ｓ１６を検索し、分図（１０）に示すように、２つの部分回路Ｓ１９，Ｓ２０と結合回路Ｃ１０とに分割し、新たに分割された回路Ｓ１９，Ｓ２０，Ｃ１０の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝８９７２を求める。
【００５９】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上であり且つ部分回路数がプロセッサ数を超えているので、最大値の部分回路Ｓ１６が分割不可と判定し、分図（８）に示す分割前の状態に復帰して、最大値の部分回路Ｓ１６に分割終了フラグを立てる。
【００６０】
ステップ２２で、部分回路Ｓ１５に分割終了フラグが立っていないので、ステップ１３に戻る。
【００６１】
次に、ステップ１３〜１５で、分割終了フラグが立っていない部分回路Ｓ１５から最大値Ｗｉ＝３９４８の部分回路Ｓ１５を検索し、分図（１１）に示すように、２つの部分回路Ｓ２１，Ｓ２２と結合回路Ｃ１１とに分割し、新たに分割された回路Ｓ２１，Ｓ２２，Ｃ１１の回路シミュレーション時間をそれぞれ予測し、分割後予測値の和Ｗｊ＝５８６６を求める。
【００６２】
ステップ１６〜２１で、分割後予測値の和Ｗｊが最大値Ｗｉ以上であり且つ部分回路数がプロセッサ数を超えているので、最大値の部分回路Ｓ１５が分割不可と判定し、分図（８）に示す分割前の状態に復帰して、最大値の部分回路Ｓ１５に分割終了フラグを立てる。
【００６３】
ステップ２２で、全ての部分回路Ｓ１，Ｓ４，Ｓ１０，Ｓ１１，Ｓ１５，Ｓ１６に分割終了フラグが立っているので、ステップ１３に進み、一時保存された最小値Ｔｍｉｎ＝７０２４１１の、分図（８）に示す分割状態を出力する。
【００６４】
上述のように、本実施形態の回路分割方法は、分割終了フラグが立っていない且つ回路シミュレーション時間の予測値が最大値の部分回路を分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求め、分割後予測値の和が最大値以上であり且つ部分回路数がプロセッサ数を超えた場合のみ最大値の部分回路が分割不可と判定し、分割前の状態に復帰して最大値の部分回路に分割終了フラグを立てる。このため、分割後予測値の和が最大値を超えない場合は、部分回路数がプロセッサ数を超えた場合も、回路分割を繰り返し、回路全体に対する並列回路シミュレーション時間の予測値Ｔの最小値Ｔｍｉｎに対応した分割状態を出力できる。
【００６５】
なお、本実施形態の回路分割方法では、部分回路または結合回路に対応した回路行列を作成し、１ニュートン反復当たりのモデル計算時間および行列演算時間を測定し、測定結果に基づき、回路行列のモデル計算時間および行列演算時間の和を求めて、部分回路または結合回路の回路シミュレーション時間の予測値とするとして説明した。しかし、説明した回路分割方法に限定されず、本実施形態の回路分割方法の変形例として、たとえば、従来の回路分割方法と同様に、「部分回路または結合回路の素子数に基づきモデル計算の演算回数を見積り、部分回路または結合回路に対応した回路行列の行列計算の演算回数を見積って、モデル計算時間および行列計算時間をそれぞれ見積り、これらの和を求めて、部分回路または結合回路の回路シミュレーション時間の予測値とする」変形例も可能である。
【００６６】
また、本実施形態の回路分割方法では、「分割終了フラグが立っていない且つ回路シミュレーション時間の予測値が最大値の部分回路を分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求め、分割後予測値の和が最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて最大値の部分回路の分割不可または分割可を判定する」として説明した。しかし、説明した回路分割方法に限定されず、本実施形態の回路分割方法の変形例として、たとえば、特開２０００−２９０７９６号公報に開示されているように、部分回路または結合回路を記述する線形連立方程式の解法の１つであるガウス消去法の処理経路を各変数の消去処理時間により重み付け、処理経路の重みの総和が最大のものを部分回路または結合回路の回路シミュレーション処理経路のクリティカルパス長とし、「分割終了フラグが立っていない且つ部分回路の回路シミュレーション処理経路のクリティカルパス長が最大値の部分回路を分割し、新たに分割された回路の回路シミュレーション処理経路のクリティカルパス長をそれぞれ予測し分割後最大値を求め、分割後最大値が最大値以上であり且つ部分回路数がプロセッサ数を超えたか否かに応じて最大値の部分回路の分割不可または分割可を判定する」変形例も可能である。
【００６７】
【発明の効果】
以上説明したように、本発明による回路分割方法は、分割終了フラグが立っていない且つ回路シミュレーション時間の予測値が最大値の部分回路を分割し、新たに分割された回路の回路シミュレーション時間をそれぞれ予測し分割後予測値の和を求め、分割後予測値の和が最大値以上であり且つ部分回路数がプロセッサ数を超えた場合のみ最大値の部分回路が分割不可と判定し、分割前の状態に復帰して最大値の部分回路に分割終了フラグを立てる。このため、分割後予測値の和が最大値を超えない場合は、部分回路数がプロセッサ数を超えた場合も、部分回路の分割を繰り返し、回路全体に対する並列回路シミュレーション時間の予測値の最小値に対応した分割状態を出力できる。
【００６８】
このため、シミュレーション対象の回路が大規模になっても、プロセッサ数を超えて部分回路の分割を繰り返し、部分回路が大規模にならず、大規模な回路の回路シミュレーション時間を短縮できるなどの効果が奏せられる。
【図面の簡単な説明】
【図１】本発明の回路分割方法の実施形態を示す流れ図である。
【図２】図１の回路分割方法をＲＤＲＡＭ回路に適用した例の前半を示す説明図である。
【図３】図１の回路分割方法をＲＤＲＡＭ回路に適用した例の後半を示す説明図である。
【図４】他の従来の回路分割方法の概略処理例を示す流れ図である。
【符号の説明】
１，２　　プロセッサ
１１〜２２，４１〜５３　　ステップ
Ｃ１〜Ｃ１１　　結合回路
Ｓ１〜Ｓ２２　　部分回路
Ｔ　　並列回路シミュレーション時間の予測値
Ｔｍｉｎ　　最小値
Ｗｉ　　最大値
Ｗｊ　　分割後予測値の和
【図１】
2004013465.tif 000003
【図２】
2004013465.tif 000004
【図３】
2004013465.tif 000005
【図４】
2004013465.tif 000006