(57)【特許請求の範囲】
【請求項１】
線形連立方程式の解を求める計算装置であって、
線形連立方程式の係数に対応する構造を有する係数行列に対して、当該係数行列の各ピボットの非ゼロ要素の数に基づく次数が所定の値以下である場合に、前記係数行列の各ピボットのガウス消去法における累積的な処理時間に対応する値が少ない順序となるように前記係数行列の各ピボットを入れ替えるピボット入れ替え手段と、
前記各ピボットが入れ替えられた係数行列に対して、ガウス消去法による係数消去を係数単位で並列実行するガウス消去法並列実行手段と、
を備えることを特徴とする計算装置。
【請求項２】
前記ピボット入れ替え手段は、前記係数行列の各ピボットの次数から最小の次数の値を求め、当該最小値から所定の範囲内の次数の値を持ち、かつ、ガウス消去法における累積的な処理時間に対応する値が最小であるピボットｉ（ｉは、１≦ｉ≦前記係数行列のサイズ）を求める第１のピボット決定手段と、
前記最小の次数の値から所定の範囲内の次数の値を持ち、かつ、ガウス消去法における累積的な処理時間に対応する値が最小であるピボットｐ（ｐは、ｉ≦ｐ≦前記係数行列のサイズ）を求める第２のピボット決定手段と、
前記係数行列に対して、前記第１のピボット決定手段で求まったピボットｉと前記第２のピボット決定手段で求まったピボットｐとを入れ替える入れ替え手段と、
を有することを特徴とする請求項１に記載の計算装置。
【請求項３】
線形連立方程式の解を求める計算装置であって、
線形連立方程式の係数に対応する構造を有する係数行列に対して、当該係数行列の各ピボットの非ゼロ要素の数に基づく次数が所定の値以下である場合に、前記係数行列の各ピボットのガウス消去法におけるクリティカルパスの長さが短い順序となるように前記係数行列の各ピボットを入れ替えるピボット入れ替え手段と、
前記各ピボットが入れ替えられた係数行列に対して、ガウス消去法による係数消去を係数単位で並列実行するガウス消去法並列実行手段と、
を備えることを特徴とする計算装置。
【請求項４】
入れ替える行列の対称性に基づいて行列順序を入れ替える対称性に基づく入れ替え手段と、
所定の条件で、前記ピボット入れ替え手段による行列順序の入れ替えと、前記対称性に基づく入れ替え手段による行列順序の入れ替えとを選択する選択手段と、
をさらに備えることを特徴とする請求項１〜３のいずれか１項に記載の計算装置。
【請求項５】
前記係数行列が非対称な構造を有する場合に、前記対称性に基づく入れ替え手段に対して、行列の構造を対称にする変換を行った後、入れ替えるべき行列を供給する行列供給手段をさらに備えることを特徴とする請求項４に記載の計算装置。
【請求項６】
電子回路に基づいて作成された線形連立方程式を解く手段を有して電子回路のシミュレーションを行う電子回路シミュレーション装置において、
前記線形連立方程式を解く手段は、請求項１〜５のいずれか１項に記載の計算装置であることを特徴とする電子回路シミュレーション装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、線形連立方程式の係数行列の行列順序を決定する際に用いて好適な行列リオーダリング方法及び装置、並びにそれを用いた電子回路シミュレーション方法及び装置に関する。
【０００２】
【従来の技術】
コンピュータを利用したシステムのシミュレーション方法には、システムを構成する複数の要素を線形連立方程式として記述し、これを繰り返し解くことで、システムの動作を解析するものがある。このようなシミュレーション方法において、線形連立方程式の解を求める方法の１つとしてよく利用されるものにガウス消去法がある。ガウス消去法では、ｎ元１次連立方程式の各係数で構成される係数行列と定数項とを横に並べた形のｎ行ｎ＋１列の行列を、上三角行列に変換する前進消去処理と、変換した行列の最下行から順次解を求める後退代入処理とによって、解が求められるようになっている。ここで、連立方程式の各係数で構成される係数行列内の各要素すなわち各元（特に非ゼロの元）を、所定の方法であらかじめ整理すること（行列リオーダリングあるいは行列オーダリングすること）で、解を求める際に必要となる乗算や除算の回数を減らすことができることが知られている。
【０００３】
図１４は、電子回路シミュレーションシステム等において用いられる従来の行列リオーダリング部の処理の流れを示す流れ図である。一般に、従来の行列リオーダリングにおいては、「最小次数法」と呼ばれている方法が採用されている（小国力編著、「行列計算ソフトウェア」、丸善株式会社等参照）。図１４において、Ｎ行×Ｎ列の係数行列のリオーダリングを行う場合、変数ｉに１を代入した後（Ｓ１０１）、次に、与えられた係数行列のうちまだ順番が決定されていないピボットの中から最小次数のピボットを一つ選択し、その番号を変数ｐに代入する（Ｓ１０２）。ここで、第ｋ番目のピボットとは、第ｋ行の各元と第ｋ列の各元をまとめて指すものであり（ｋは１〜Ｎの整数）、次数とはピボット内の対角線上の要素を除き、対角線よりも列方向で下側または行方向で右側にある非ゼロ要素の個数を示し、そして、最小次数のピボットとは、ｉ番目以降のピボットの次数で最小のものを有するピボットを指している。次に、選択した第ｐ番目のピボットと第ｉ番目のピボットとを交換することによって、第ｉ番目のピボットを決定し（Ｓ１０３）、第ｉピボットに対するガウス消去処理を行った時に発生する非ゼロ要素を係数行列に追加する（Ｓ１０４）。ここで、第ｐ番目のピボットと第ｉ番目のピボットの交換とは、第ｐ行の各元と第ｉ行の各元をすべて交換するとともに、第ｐ列の各元と第ｉ列の各元をすべて交換すること、つまり行と列を同時に入替えることを意味する。これら一連の処理を、すべてのピボットの順序が決定するまで繰り返す（Ｓ１０５，Ｓ１０６）。「最小次数法」によれば、係数行列内で非ゼロ要素がより少ないピボットがより上側へと整理されるので、ガウス消去における乗算や除算の演算の総数を減少させることが可能となる。
【０００４】
【発明が解決しようとする課題】
ところで、上述したような従来の行列リオーダリング方法によって整理した係数行列を用いて、複数のプロセッサを用いてガウス消去処理を並列実行する場合、単独のプロセッサで逐次実行した場合と比べて十分に高速化されないことがある。ガウス消去処理では、ある行の演算を行う場合に、他の行の演算結果を使用（参照）することになる。したがって、ガウス消去処理を並列実行する場合に、演算処理を行単位で複数のプロセッサに分けて並列処理するときには、演算の総数を減少させることと共に、各行の演算数と、各行で参照する他の行およびさらにその行で参照される他の行での演算数とを加えたものを減少させることを考慮することが、高速化を図る上での重要な課題となる。しかしながら従来の行列リオーダリング方法では、ガウス消去処理における総演算数の低減のみを行っていたため、ガウス消去処理を並列実行した場合に、必ずしも並列実行による高速化の効果を得ることはできなかった。
【０００５】
本発明は、上記の事情を考慮し、ガウス消去処理を複数のプロセッサを用いて並列実行する場合に、従来に比べてガウス消去処理の高速化を図ることができる係数行列を生成する行列リオーダリング方法及び装置並びに電子回路シミュレーション方法及び装置を提供することを目的とする。
【０００６】
【課題を解決するための手段】
上記課題を解決するため、請求項１に記載の発明は、線形連立方程式の解を求める計算装置であって、線形連立方程式の係数に対応する構造を有する係数行列に対して、当該係数行列の各ピボットの非ゼロ要素の数に基づく次数が所定の値以下である場合に、前記係数行列の各ピボットのガウス消去法における累積的な処理時間に対応する値が少ない順序となるように前記係数行列の各ピボットを入れ替えるピボット入れ替え手段と、前記各ピボットが入れ替えられた係数行列に対して、ガウス消去法による係数消去を係数単位で並列実行するガウス消去法並列実行手段と、を備えることを特徴とする。請求項２に記載の発明は、前記ピボット入れ替え手段は、前記係数行列の各ピボットの次数から最小の次数の値を求め、当該最小値から所定の範囲内の次数の値を持ち、かつ、ガウス消去法における累積的な処理時間に対応する値が最小であるピボットｉ（ｉは、１≦ｉ≦前記係数行列のサイズ）を求める第１のピボット決定手段と、前記最小の次数の値から所定の範囲内の次数の値を持ち、かつ、ガウス消去法における累積的な処理時間に対応する値が最小であるピボットｐ（ｐは、ｉ≦ｐ≦前記係数行列のサイズ）を求める第２のピボット決定手段と、前記係数行列に対して、前記第１のピボット決定手段で求まったピボットｉと前記第２のピボット決定手段で求まったピボットｐとを入れ替える入れ替え手段と、を有することを特徴とする。請求項３に記載の発明は、線形連立方程式の解を求める計算装置であって、線形連立方程式の係数に対応する構造を有する係数行列に対して、当該係数行列の各ピボットの非ゼロ要素の数に基づく次数が所定の値以下である場合に、前記係数行列の各ピボットのガウス消去法におけるクリティカルパスの長さが短い順序となるように前記係数行列の各ピボットを入れ替えるピボット入れ替え手段と、前記各ピボットが入れ替えられた係数行列に対して、ガウス消去法による係数消去を係数単位で並列実行するガウス消去法並列実行手段と、を備えることを特徴とする。請求項４に記載の発明は、入れ替える行列の対称性に基づいて行列順序を入れ替える対称性に基づく入れ替え手段と、所定の条件で、前記ピボット入れ替え手段による行列順序の入れ替えと、前記対称性に基づく入れ替え手段による行列順序の入れ替えとを選択する選択手段と、をさらに備えることを特徴とする。請求項５に記載の発明は、前記係数行列が非対称な構造を有する場合に、前記対称性に基づく入れ替え手段に対して、行列の構造を対称にする変換を行った後、入れ替えるべき行列を供給する行列供給手段をさらに備えることを特徴とする。
【０００７】
請求項６に記載の発明は、電子回路に基づいて作成された線形連立方程式を解く手段を有して電子回路のシミュレーションを行う電子回路シミュレーション装置において、前記線形連立方程式を解く手段は、請求項１〜５のいずれか１項に記載の計算装置であることを特徴とする。
【０００８】
【発明の実施の形態】
以下、図面を参照して本発明による行列リオーダリング方法およびそれを用いるシミュレーション方法の実施形態の一例について説明する。図１は、本発明を電子回路のシミュレーションシステムに適用する場合の電子回路シミュレーション方法の全体の処理の流れを示す流れ図である。本実施の形態における電子回路のシミュレーションシステムは、線形連立方程式を解く過程を複数のプロセッサを並列稼働することによって行う電子計算機と、その電子計算機によって実行されるソフトウェアプログラムとによって実現されているものとする。また、そのプログラムはコンピュータ読みとり可能な記録媒体あるいはネットワークを介して頒布することが可能である。
【０００９】
まず、シミュレーション対象の電子回路を示す回路記述を、所定の入力装置から入力する（Ｓ２０１）。次に、入力された回路記述に基づいて、回路を構成する各電子素子を示す線形方程式（１次方程式）を、全素子に対応する連立方程式として構成する。そして、連立方程式の各変数の係数のうち、非ゼロである要素の位置を、行列Ａに登録する（Ｓ２０２）。ここで、行列Ａは、電子回路に対応する連立方程式がＮ元線形連立方程式である場合に、Ｎ行×Ｎ列型の行列となる。ステップＳ２０２では、この行列Ａの各元（各要素）に、連立方程式の対応する係数が設定される。次に、行列リオーダリング処理ステップ（Ｓ２０３）では、行列Ａ内の各要素の値を示す行列構造情報を用いて、行列Ａの行の順序と列の順序を入替えることによって、ステップＳ２０６の線形連立方程式の求解処理の処理時間が最小となるように行列順序を決定する。一般には、行列の第ｉ行と第ｉ列をまとめて第ｉピボットと呼ぶが、ここでは、このピボットを交換する処理を行う。つまり行と列を同時に入替えることによって行列順序を変更する。
【００１０】
次に、電子回路シミュレーションにおける最適な時間刻み幅Δｔを求め、次のタイムポイントｔn+1を、現在の時刻ｔnからΔｔだけ進めた（ｔn+1＝ｔn＋Δｔ）として決定する（Ｓ２０４）。そして、ステップＳ２０３で並べ替えが終了した行列Ａの行列構造情報（行と列の順序）に基づき、その時刻における各素子の非線形特性を線形化してニュートン方程式（線形連立方程式）を作成する（Ｓ２０５）。
【００１１】
次に、ステップＳ２０５で作成したニュートン方程式をガウス消去法を適用して解く処理を行う（Ｓ２０６）。本実施形態では、このニュートン方程式をガウス消去法を適用して解く処理を、複数のプロセッサを並列動作させることによって行う。次に、解が収束したかどうかを判定し（Ｓ２０７）、収束しなかった場合には、ステップＳ２０５へ戻って再度ニュートン方程式を作成し直してステップＳ２０６の求解処理を行う。一方、ステップＳ２０７で解が収束した場合には、時刻ｔnが最終時刻に達したかどうかを判定し（Ｓ２０８）、達したとき（ｔn≧最終時刻の場合）には計算結果を出力して処理を終了し、まだ達していないときには現在の時刻ｔnをtn+1に更新した後、ステップＳ２０４へ戻って、上述したステップＳ２０４〜Ｓ２０７の処理を繰り返し実行する。
【００１２】
なお、上記のような電子回路のシミュレーション方法については、例えば、特開平１０−１１４７５号公報「回路シミュレーション方法」、特開平７−１２９６３７号公報「回路シミュレーション方法」等に記載されている。
【００１３】
図１に示すガウス消去処理（Ｓ２０６）は、連立方程式の変数を一つずつ消去していく過程とみなすことができる。変数１つを消去する処理を１つのタスクとして定義すると、各タスクの間には実行順序の制約がある。この制約は、例えば図１１に示すような「タスクグラフ」と呼ばれる有向グラフによって示すことができる。図１１に示す「タスクグラフ」では、「タスクｉはタスクｊの終了後に実行しなければならない」という制約を、「頂点ｊから頂点ｉに向かう辺がある」ことで表現している。図１１において、頂点とは、番号（数字）を丸で囲ったものであり、辺は矢印で示している。また、タスクｉの「処理に要する時間」を頂点ｉの「重み」として与えている。頂点の横の数字が頂点の「重み」を表している。
【００１４】
ガウス消去処理（Ｓ２０６）の並列実行時間は、このタスクグラフ内の任意の頂点から任意の頂点への経路のうち最も長い経路（クリティカルパス）の長さで決まる。ここでいう「長さ」とは、「経路に含まれるすべての頂点の重みの総和」である。したがって、本実施の形態が特徴とする行列リオーダリング処理（Ｓ２０３）では、このクリティカルパスをできるだけ短くするように行列のリオーダリングを行う。
【００１５】
ここで、図１に示される行列リオーダリング処理を説明するのに必要な「行列グラフ」、「ピボットの次数」、および「ピボットのクリティカルパス」について説明する。「行列グラフ」とは、行列Ａの第ｉ行、第ｊ列の要素ａ（ｉ，ｊ）がゼロでない時、およびその時に限って、頂点ｉと頂点ｊの間に辺があるような無向グラフである。例えば、図６の行列の行列グラフは図７のようになる。グラフの頂点に繋がる辺の数は、一般に「次数」と呼ばれるが、行列グラフの頂点は行列のピボットに対応することから、頂点の次数を「ピボットの次数」とも呼ぶ。なお、図６において、×印と○印は非ゼロ要素を示し、対角線上に配置された○印で示す非ゼロ要素内の番号はリオーダリング前のピボットの番号を示している。また、空白はゼロ要素を示し、記号「Ｆ」はガウス消去処理（Ｓ２０６）において各ピボットの消去処理を行う際に追加される非ゼロ要素を示している。
【００１６】
Ｎ×Ｎの正方行列に対する行列リオーダリング処理の途中で、１番目からｉ番目までのピボットのみの順序が決定され、ｉ＋１番目からＮ番目までのピボットの順序は決定されていない時、ガウス消去処理では１番目からｉ番日の変数の消去処理は可能であり、したがってタスク１からタスクｉのｉ個のタスクからなるタスクグラフを作成することができる。このタスクグラフ内のタスクｋに至る任意の経路のうちで最長のものを「タスクｋのクリティカルパス」と呼び、これを「第ｋ番目のピボットのクリティカルパス」とも呼ぶことにする。また、タスクｋのクリティカルパスに含まれるすべての頂点の重みの総和をタスクｋあるいはピボットｋの「クリティカルパス長」と呼ぶことにする。
【００１７】
図２は、図１に示す電子回路シミュレーションの流れ図における処理（Ｓ２０３）である行列リオーダリング処理の一例を示す流れ図である。まず、変数ｉに１を代入するとともに、変数Ｎに行列Ａの行列サイズを代入する（Ｓ３００）。次に、全ての変数ｋ（１≦ｋ≦Ｎ）について、配列変数ｌｅｎ（ｋ）をｌｅｎ（ｋ）：＝０と初期化する（Ｓ３０２）。ここで、配列変数ｌｅｎ（ｋ）は、各時点で変化するピボットｋのクリティカルパス長を記憶する変数である。次に、第ｉ番目から第Ｎ番目のピボットの次数のうち、最小の次数ｍｉｎｄｅｇを求める（Ｓ３０４）。次に、第ｉ番目から第Ｎ番目のピボットのうち、次数がｍｉｎｄｅｇ＋α以下でかつクリティカルパス長が最小のピボットｐを求める（Ｓ３０６）。ここで、αは０以上の所定の定数値であり、例えばαの推奨値は１から３の値となる。すなわち、ステップＳ３０６では、次数が最小値ｍｉｎｄｅｇから所定の範囲内にある近最小次数を有する１または複数のピボットのうちで、最もクリティカルパス長の小さい１つの第ｐ番目のピボットを求めることになる。そして、第ｐピボットと第ｉピボットを入れ替える処理が行われる（Ｓ３０８）。
【００１８】
次に、入れ替え後の第ｉピボットの消去処理で値が更新される全ての要素ｅについて、要素ｅが属するピボットｊのクリティカルパス長ｌｅｎ（ｊ）を、ｌｅｎ（ｊ）：＝ｍａｘ｛ｌｅｎ（ｉ）＋ｗ（ｉ），ｌｅｎ（ｊ）｝となるように更新する（Ｓ３１０）。すなわち、ステップＳ３１０では、ステップＳ３０８で第ｐピボットと第ｉピボットを入れ替えたことに影響される他のピボットのクリティカルパス長が最新の値に更新される。ここで、ｍａｘ（ｘ，ｙ）は変数ｘ、ｙのうちで大きい方の値を示す関数であり、ｗ（ｉ）はピボットｉの「重み」を与える関数である。そして、第ｉピボットの消去処理で発生する非ゼロ要素を係数行列Ａに追加する（Ｓ３１２）。次に、変数ｉに１を加えることで更新し（Ｓ３１４）、変数ｉが変数Ｎを越えているかどうかを判定して（Ｓ３１６）、Ｎを越えるまでステップＳ３０４〜Ｓ３１２の処理を繰り返し行う。以上の処理で、Ｎ×Ｎの行列Ａすべてのピボットに対するリオーダリングの処理が終了する。
【００１９】
なお、上記では、関数ｗ（ｉ）がピボットｉの「重み」（処理に要する時間）を与える関数であると説明したが、関数ｗ（ｉ）は、図１におけるガウス消去法（Ｓ２０６）において、そのピボットｉを消去する際に行われる例えば乗算および除算の数を加えたものに対応する値を得るものとして定義することができる。例えば、ガウス消去処理を図５に示すようなプログラムで行う場合、ｋ番目の変数を消去する処理では、重みｗ（ｋ）が、（ｄｅｇ（ｋ）＋１）・ｄｅｇ（ｋ）、すなわち第ｋピボットの次数（＝ｄｅｇ（ｋ））に１を加えたものに次数（ｄｅｇ（ｋ））を掛けたものに対応する値（ｗ（ｉ）＝（ｄｅｇ（ｉ）＋１）・ｄｅｇ（ｉ））として求めることができる。なお、ガウス消去処理を行うためのプログラムの記述方法には、上記のもののほかにも種々のものがあり、異なるものを用いる場合には、上記の重みを求める関数ｗ（ｉ）も異なる記述による処理時間を反映するように適宜変更する。
【００２０】
次に、図３を参照して、図２におけるステップＳ３０４とステップＳ３０６の処理についてより詳細に説明する。図３は、図２におけるステップＳ３０４とステップＳ３０６の処理の流れを示す流れ図であり、ステップＳ４０２〜Ｓ４１２がステップＳ３０４内の処理に対応し、ステップＳ４１４〜Ｓ４２６がステップＳ３０６内の処理に対応している。図３では、まず、最小次数を記憶する変数ｍｉｎｄｅｇを初期化し（Ｓ４０２）、次に、変数ｊに変数ｉの値を設定する（Ｓ４０４）。そして、ステップＳ４０６〜Ｓ４１２の処理を、変数ｊが変数Ｎに達するまで繰り返し行う。ステップＳ４０６では、第ｊ番目のピボットの次数ｄｅｇ（ｊ）が変数ｍｉｎｄｅｇより小さいか否かを判定し、小さい場合には変数ｍｉｎｄｅｇを次数ｄｅｇ（ｊ）で更新した後（Ｓ４０８）、ステップＳ４１０で変数ｊをｊ：＝ｊ＋１によって１だけ増加させる。そして、ステップＳ４１２で変数ｊが変数Ｎより大きいか否かを判定し、大きくない場合には再びステップ４０６以降の処理を実行する。以上の処理によって変数ｍｉｎｄｅｇに最小の次数の値が格納される。
【００２１】
次に、図２のステップＳ３０６に対応する処理では、まず、最短クリティカルパス長を記憶する変数ｍｉｎｌｅｎを初期化し（Ｓ４１４）、次に、変数ｊに変数ｉの値を設定する（Ｓ４１６）。そして、ステップＳ４１８〜Ｓ４２６の処理を、変数ｊが変数Ｎに達するまで繰り返し行う。ステップＳ４１８では、第ｊ番目のピボットの次数ｄｅｇ（ｊ）が（変数ｍｉｎｄｅｇ＋α）より小さいか否かを判定し、小さい場合にはさらに第ｊ番目のピボットのクリティカルパス長ｌｅｎ（ｊ）が変数ｍｉｎｌｅｎより小さいか否かを判定し（Ｓ４２０）、小さいときには変数ｍｉｎｌｅｎをクリティカルパス長ｌｅｎ（ｊ）で更新するとともに、変数ｐに変数ｊを代入する（Ｓ４２２）。そして、ステップＳ４１８〜Ｓ４２２のいずれかの処理が終了した後、ステップＳ４２４で変数ｊをｊ：＝ｊ＋１によって１だけ増加させる。そして、ステップＳ４２６で変数ｊが変数Ｎより大きいか否かを判定し、大きくない場合には再びステップ４１８以降の処理を実行する。以上の処理によって、変数ｐに第ｉ番目から第Ｎ番目のピボットのうち、次数がｍｉｎｄｅｇ＋α以下でかつクリティカルパス長が最小のピボット番号が格納されるとともに、変数ｍｉｎｌｅｎに最小のクリティカルパス長が格納される。
【００２２】
次に、本発明の行列リオーダリング（図１のステップＳ２０３）内の処理を図２に示す処理の流れに従って行う場合の具体的な動作について、図８〜図１１を参照して説明する。なお、図８はシミュレーションしようとする電子回路の例、図９は図８の電子回路に対応する連立方程式の係数行列の例、図１０は図９の行列のリオーダリング後の行列の例、図１１は図１０に対応するタスクグラフをそれぞれ示している。
【００２３】
例えば図８に示すような９個の素子Ｄ１〜Ｄ９からなる電子回路を考える場合、電子回路内の各ノードＮ１〜Ｎ７の電圧等の値を変数とする線形連立方程式の係数行列は、図９のように構成することができる。この場合、図９の係数行列は、第ｉ番目のピボットがｉ番目のノード番号に対応するように構成されている。図９では非ゼロ要素を×、ゼロ要素を空白で表現し、各要素の数値は省略してある。数字を囲んだ丸も非ゼロ要素を表しており、丸の中の番号は、リオーダリング前のピボット番号を表す。第ｉ変数のガウス消去処理（タスクｉ）の重み（ｗ（ｉ））は、（第ｉ番目のピボットの次数＋１）に（第ｉ番目のピボットの次数）を掛けたものとする（ｗ（ｉ）＝（ｄｅｇ（ｉ）＋１）・ｄｅｇ（ｉ））。以降では、α＝０としたときの動作を説明する。
【００２４】
図２の流れ図において、まずｉ＝１とし、次数が最小（α＝０なので最小となる）のピボットで、かつそのピボットを第ｉ番目のピボットと決定した時にそのピボットのクリティカルパス長が最小となるピボットを探す。図９において、第１ピボットと第７ピボットの次数は１で最小であり、かつこれらのクリティカルパス長はいずれも２で最小である。これらのうち番号の小さい第１ピボットを選択し、ｐ＝１とする（Ｓ３０６）。ｉ＝ｐであるので、ステップＳ３０８でのピボット入れ替えは実際には行われない。また、第１ピボットについてガウス消去処理を行っても新たな非ゼロ要素は発生しない（Ｓ３１２）。
【００２５】
続いてｉ＝２として、まだ順序の決定されていない行列部分に対して上記処理を繰り返す。最小次数かつ最短クリティカルパスのピボットは第７ピボットでありｐ＝７となる。第２ピボットと第７ピボットが交換される（Ｓ３０８）。新たな非ゼロ要素は発生しない（Ｓ３１２）。
【００２６】
ｉ＝３に対しては、最小次数・最短クリティカルパスのピボットとしてｐ＝３が選択される（次数は２、クリティカルパス長は６）。第３ピボットを消去すると新たな非ゼロ要素ａ（４，７），ａ（７，４）が追加される（Ｓ３１２）。
【００２７】
ｉ＝４に対しては、最小次数・最短クリティカルパスのピボットとしてｐ＝５が選択される（次数は２、クリティカルパス長は６）。第５ピボットを消去すると新たな非ゼロ要素ａ（４，６），ａ（６，４）が追加される（Ｓ３１２）。
【００２８】
ｉ＝５に対しては、最小次数・最短クリティカルパスのピボットとしてｐ＝４が選択される（次数は２、クリティカルパス長は６＋６＝１２）。第４ピボットを消去するときに新たな非ゼロ要素は発生しない（Ｓ３１２）。
【００２９】
ｉ＝６に対しては、最小次数・最短クリティカルパスのピボットとしてｐ＝６が選択される（次数は１、クリティカルパス長は６＋６＋２＝１４）。第６ピボットを消去するときに新たな非ゼロ要素は発生しない（Ｓ３１２）。
【００３０】
以上の処理によって、図９に示す係数行列が、図１０に示すようにリオーダリングされる。また、タスクグラフは図１１に示すようになる。このとき、実行順序が最も遅いタスク２の次数は０であり、クリティカルパス長は１４であり、すべての重みの合計は２４である。
【００３１】
一方、従来の行列リオーダリング（図１４）を図９の行列に適用すると、図１５のような順序に並び替えられ、対応するタスクグラフは図１６のようになる。この場合の実行順序が最も遅いタスク２のクリティカルパス長は２０であり、すべての重みの合計は２４である。
【００３２】
以上のように、図１の行列リオーダリング（Ｓ２０３）において、図２および図３を参照して説明したような、ピボットの近最小次数（近最小次数＝最小次数＋α）と、クリティカルパス長とを考慮した行列のリオーダリングを行うことによって、本実施形態では、従来に比べて各タスクを複数のプロセッサによって並列実行した場合の処理時間をより短縮することが可能となる。
【００３３】
次に、図１の行列リオーダリング処理（Ｓ２０３）の他の実施形態、すなわち図２に示す構成の変形例について、図４を参照して説明する。図４は電子回路シミュレーションの流れ図（図１）の処理ステップ（Ｓ２０３）である行列リオーダリング処理の流れ図である。おおまかには、図２ものと同様の近最小次数・最短クリティカルパス法（Ｓ８）および従来の行列リオーダリング方法の１つであるネステッド・デイセクション（nested dissection）法（Ｓ１０）の２つのリオーダリング方法を選択可能な形で組み合わせたものとなっている。
【００３４】
「近最小次数・最短クリティカルパス法」による行列リオーダリング部（Ｓ８）は、変数ｉを１に初期化した後（Ｓ１）、与えられた係数行列Ａのうちまだ順番が決定されていないピボットの中から近最小次数（次数が最小次数＋α以下、αの推奨値は１から３）かつ最短クリティカルパスを持つピボット（番号ｐ）を一つ選択し（Ｓ２）、選択した第ｐ番目のピボットと第ｉ番目のピボットとを交換することによって第ｉ番目のピボットを決定し（Ｓ３）、第ｉピボットに対するガウス消去処理を行った時に発生する非ゼロ要素を係数行列Ａに追加する（Ｓ４）。これら一連の処理を、第ｉピボットの次数が定数βを超えるか（Ｓ５）、全てのピボットの順序が決定する（Ｓ７）まで繰り返す。
【００３５】
上記の近最小次数・最短クリティカルパス法（Ｓ８）は、与えられた行列の平均次数が約３以下の時には、ネステッド・ディセクション法よりもクリティカルパス長を短くすることができるが、平均次数がそれより大きくなると、得られるクリティカルパス長はネステッド・ディセクション法によるものより長くなってしまう傾向がある。したがって、近最小次数・最短クリティカルパス法実行中に、選択されたピボットの次数が定数β（βは自然数）より大きくなった場合には、ネステッド・ディセクション法へと切り替える。βの値は３から１０の範囲が適当である。
【００３６】
近最小次数・最短クリティカルパス法（Ｓ８）による行列リオーダリング部の処理が終了してもまだ全てのピボットの順序が決定されていない場合には、係数行列Ａ内のまだ消去されていない部分行列Ｒの行列グラフを作成し（Ｓ９）、この行列グラフを用いてネステッド・ディセクション法により部分行列Ｒのみのリオーダリングを行う（Ｓ１０）。「ネステッド・ディセクション法」は、行列グラフの２分割を再帰的に繰り返し、分割境界上の頂点に対応するピボットが最後にくるように順序付けを行う。すべてのピボットが順序付けられるまで、２分割を再帰的に繰り返す処理が行われる。そして、部分行列Ｒに対するガウス消去処理で発生する非ゼロ要素を係数行列Ａに追加する処理を実行して（Ｓ１１）、係数行列Ａの利オーダリングの処理が終了する。
【００３７】
次に、本発明の行列リオーダリング（図１のステップＳ２０３）内の処理を図４に示す処理の流れによって行う場合の具体的な動作について、図６〜図９および図１２、図１３を参照して説明する。この場合も、上記と同様に、図８に示すような９個の素子Ｄ１〜Ｄ９からなる電子回路と、リオーダリングの対象として図９に示すその線形連立方程式の係数行列を用いることとする。第ｉ変数のガウス消去処理（タスクｉ）の重み（ｗ（ｉ））は、上記と同様に、（第ｉ番目のピボットの次数＋１）に（第ｉ番目のピボットの次数）を掛けたものとする。以降では、α＝０、β＝１としたときの動作を説明する。
【００３８】
図４の近最小次数・最短クリティカルパス法（Ｓ８）において、まずｉ＝１とし、次数が最小（α＝０なので最小となる）のピボットで、かつそのピボットを第ｉ番目のピボットと決定した時にそのピボットのクリティカルパス長が最小となるピボットを探す。図９において、第１ピボットと第７ピボットの次数は１で最小であり、かつこれらのクリティカルパス長はいずれも２で最小である。これらのうち番号の小さい第１ピボットを選択し、ｐ＝１とする（Ｓ２）。ｉ＝ｐであるので、ステップＳ３でのピボット入れ替えは実際には行われない。また、第１ピボットについてガウス消去処理を行っても新たな非ゼロ要素は発生しない（Ｓ４）。
【００３９】
続いてｉ＝２として、まだ順序の決定されていない行列部分に対して上記処理を繰り返す。最小次数かつ最短クリティカルパスのピボットは第７ピボットでありｐ＝７となる。第２ピボットと第７ピボットが交換される（Ｓ３）。新たな非ゼロ要素は発生しない（Ｓ４）。
【００４０】
ｉ＝３に対しては、最小次数・最短クリティカルパスのピボットとしてｐ＝３が選択される（次数は２、クリティカルパス長は６）。第３ピボットを消去すると新たな非ゼロ要素ａ（４，７），ａ（７，４）が追加される。第３ピボットの次数は２でありβ＝１より大きいため、近最小次数・最短クリティカルパス法によるリオーダリングは終了される（Ｓ５）。
【００４１】
このとき、まだピボットの順番が決定されていない部分の行列Ｒは図６のようになっており、この行列グラフは図７のように生成される（Ｓ９）。ネステッド・ディセクション法では、このグラフの２分割を行い、分割境界上のノードに対応するピボットが最後にくるように順序付けられる。すべてのピボットが順序付けられるまで２分割が再帰的に繰り返されるが、この例の場合は１度の２分割で十分であり、例えば頂点４と６が分割境界Ｐ１上の頂点となり、５，２，４，６の順番で順序付けられる。最終的に得られる行列は図１２となり、この行列に対するガウス消去処理のタスクグラフは図１３のようになる。このタスクグラフの頂点の番号は図１２のピボット番号に対応している。このタスクグラフのクリティカルパス長は１４である。図４に示す行列リオーダリングの方法によっても、従来の行列リオーダリング（図１４）に比べてクリティカルパス長が減少していることがわかる。
【００４２】
なお、図２および図４を参照して説明した行列リオーダリング（図１のステップＳ２０３）の処理方法については、対称行列を対象とするものとして説明を行ったが、非対称行列に適用する場合には、次のような変更を行うようにすればよい。第１番目の変更点は、図２および図４の処理に共通するものであり、クリティカルパス長の最小のピボットを選択する際の必要条件である「次数ｄｅｇ（ｉ）が所定の値（α）以下」という条件を、次数ｄｅｇ（ｉ）の代わりに、√｛ＮＺＬＣ（ｉ）・ＮＺＵＲ（ｉ）｝をパラメータとして用いて、「√｛ＮＺＬＣ（ｉ）・ＮＺＵＲ（ｉ）｝が所定の値（α）以下」とする点である。ここで、ＮＺＬＣ（ｉ）は、図１７に示すような対角線上の要素を含まない下三角行列Ｌの第ｉ列中の非ゼロ要素の数であり、ＮＺＵＲ（ｉ）は、同じく対角線上の要素を含まない上三角行列Ｕの第ｉ行中の非ゼロ要素の数である。
【００４３】
第２の変更点と第３の変更点は、図４に示す本発明による近最小次数・最小クリティカルパス法と、ネステッドディセクション法を組み合わせて所定の条件に基づいて選択する場合の処理においてのみ適用される変更点である。図２に示す近最小次数・最小クリティカルパス法のみを用いる場合には、上記第１の変更点のみで非対称行列に対応可能である。第２の変更点は、図４に示す近最小次数・最小クリティカルパス法（Ｓ８）と、ネステッドディセクション法（Ｓ１０）との切り替えを行う条件を、次数ｄｅｇ（ｉ）＞β（Ｓ５）に代えて、第１の変更点と同様に、√｛ＮＺＬＣ（ｉ）・ＮＺＵＲ（ｉ）｝＞βと変更することである。そして、第３の変更点は、ネステッドディセクション法（Ｓ１０）を、非対称の行列Ｒの行列グラフにではなく、行列（Ｒ＋ＲT）のように対称行列に変換し後の行列（Ｒ＋ＲT）の行列グラフに適用することである。ここで、ＲTは、行列Ｒ行と列を入れ替えた転置行列である。これらの第２および第３の変更点を導入することで、図４に示す処理を非対称行列に適用することができる。
【００４４】
また、上記の変形例として、図４に示す処理において、非対称行列のリオーダリングを行う場合には、あらかじめ、リオーダリングの対象となる非対称係数行列Ａとその転置行列ＡTとから対称行列（Ａ＋ＡT）を作成して、これに対して、近最小次数・最小クリティカルパス法（Ｓ８）と、ネステッドディセクション法（Ｓ１０）とによる並べ替え行うようにすることもできる。
【００４５】
なお、本発明の行列リオーダリング方法の適用は、電子回路のシミュレーション方法に限定されるものではなく、１次連立方程式をガウス消去法によって並列実行して解く過程を含むデータ処理方法であれば、それに適用することができる。
【００４６】
【発明の効果】
以上説明したように、本発明によれば、従来に比べて、ガウス消去処理のタスクグラフのクリティカルパス長を低減しているため、ガウス消去処理を並列実行した際の実行時間を短縮することができる。
【図面の簡単な説明】
【図１】本発明による電子回路シミュレーション方法の一実施形態を示す流れ図。
【図２】図１に示す電子回路シミュレーション方法における行列リオーダリング処理（Ｓ２０３）の流れの一実施形態を示す流れ図。
【図３】図２のステップＳ３０４，Ｓ３０６の処理の流れを示す流れ図。
【図４】図１に示す電子回路シミュレーション方法における行列リオーダリング処理（Ｓ２０３）の流れの他の実施形態を示す流れ図。
【図５】図１のガウス消去法（Ｓ２０６）の計算方法を記述したプログラムの一例を示す説明図。
【図６】まだ順序づけされていない部分行列Ｒを示す図。
【図７】図６の行列に対するガウス消去処理のタスクグラフ。
【図８】入力される回路例を示す回路図。
【図９】図８の回路図に対応するリオーダリング前の行列を示す図。
【図１０】図９の行列を、図２に示す行列リオーダリング処理（近最小次数・最小（最短）クリティカルパス法）によってリオーダリングした後の行列を示す図。
【図１１】図１０の行列リオーダリング後の行列についてのタスクグラフ。
【図１２】図９の行列を、図４に示す行列リオーダリング処理によってリオーダリングした後の行列を示す図。
【図１３】図１２の行列リオーダリング後の行列についてのタスクグラフ。
【図１４】従来の行列リオーダリング処理（最小次数法）によるリオーダリング処理の流れを示す流れ図。
【図１５】図９の行列を、図１４に示す従来の行列リオーダリング処理によってリオーダリングした後の行列を示す図。
【図１６】図１５の行列リオーダリング後の行列についてのタスクグラフ。
【図１７】上下三角行列を説明するための図。
【符号の説明】
Ｓ２０３  行列リオーダリング処理
Ｓ２０６  ガウス消去法を適用する線形連立方程式の求解処理
【図１】
0003768375.tif 000002
【図２】
0003768375.tif 000003
【図３】
0003768375.tif 000004
【図４】
0003768375.tif 000005
【図５】
0003768375.tif 000006
【図６】
0003768375.tif 000007
【図７】
0003768375.tif 000008
【図８】
0003768375.tif 000009
【図９】
0003768375.tif 000010
【図１０】
0003768375.tif 000011
【図１１】
0003768375.tif 000012
【図１２】
0003768375.tif 000013
【図１３】
0003768375.tif 000014
【図１４】
0003768375.tif 000015
【図１５】
0003768375.tif 000016
【図１６】
0003768375.tif 000017
【図１７】
0003768375.tif 000018