連立一次方程式の並列求解方法およびノード順序付け方法
【課題】大規模系統の回路網計算である連立一次方程式の求解を実時間性能で実行できる連立一次方程式の並列計算用のノード順序付け方法および連立一次方程式の並列求解方法を得ること。
【解決手段】放射状系統部分については、最初に順序付けするノードは接続されているブランチ数が最小のノードの中から任意に選択し、以降はノードに接続されているブランチ数が少ないノードから順に選択すると共に、ノード順序付け候補のノードとその相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードの場合に優先してノード順序付けを行う。ループ状系統部分については、ノードの縮約時に発生する新規非零要素発生数のシミュレーションを並列計算し、新規非零要素発生数の少ないノードから選択すると共に、ノード順序付け候補のノードとその相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードの場合に優先してノード順序付けを行う。
【解決手段】放射状系統部分については、最初に順序付けするノードは接続されているブランチ数が最小のノードの中から任意に選択し、以降はノードに接続されているブランチ数が少ないノードから順に選択すると共に、ノード順序付け候補のノードとその相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードの場合に優先してノード順序付けを行う。ループ状系統部分については、ノードの縮約時に発生する新規非零要素発生数のシミュレーションを並列計算し、新規非零要素発生数の少ないノードから選択すると共に、ノード順序付け候補のノードとその相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードの場合に優先してノード順序付けを行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電力系統の計算に現れる連立一次方程式の並列計算に関し、特に、並列計算を高速に処理できるノードの順序付け方法と、前進消去・後退代入処理の並列計算に関する。
【背景技術】
【０００２】
従来、連立一次方程式の解法として、三角分解による直接解法が知られており、この手法を用いた場合に、連立一次方程式の求解は、（１）ノードの順序付け、（２）係数行列の三角分解（ＬＤＵ分解）、（３）前進／後退代入計算による解の算出、の３つの処理を行うことになる。また、連立一次方程式の高速な求解のために並列計算が利用されている。並列計算では、複数のＣＰＵに処理を分散して計算を行い、また、ＣＰＵ間のデータの授受は通信処理を経て行っている。
【０００３】
従来の連立一次方程式の並列計算は、前進／後退代入処理のツリー作成に基づいており、その際、ノードの順序付け方法が重要になる。従来の方法では、Ｔｉｎｎｅｙ２法に基づき、ノードの消去により発生するｆｉｌｌ−ｉｎ（非零要素）の数が少ないものから選択し、あるステージ（並列処理での各ステップをステージという）で接続ブランチ数が２本以下のノードが消去される場合には、当該ステージでは接続ブランチ数が３本以上のノードは消去せず、かつ、あるノードから２ブランチまでの範囲に、同じステージで消去されるノードがある場合、当該ノードは消去しないとしている（非特許文献１を参照）。
【０００４】
【非特許文献１】永田真幸、内田直之著 「過度安定度計算高速化のための系統計算の並列処理アルゴリズムの開発」 電気学会論文誌Ｂ、１２０巻２号、平成１２年
【非特許文献２】田岡久雄、阿部茂著「パイプライン処理に適した連立一次方程式の高速求解法とその電力系統解析への応用」電気学会論文誌Ｂ、１０５巻５号、昭和６０年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来の連立一次方程式の並列計算のためのノード順序付け方法は、ノード消去により発生するｆｉｌｌ−ｉｎの数が少ないものから選択し、あるステージで接続ブランチ数が２本以下のノードを消去する場合には、当該ステージでは接続ブランチ数が３本以上のノードは消去せず、かつ、あるノードから２ブランチまでの範囲に、同じステージで消去されるノードがある場合、当該ノードは消去しないとしており、また、ノード順序付けの結果として得られた処理を各ＣＰＵに割当てるために、通信回数の削減とＣＰＵ間での計算処理の均等化のバランスをとるようにしている。
【０００６】
従来の方法は、上記の通りノードの順序付けにＴｉｎｎｅｙ２法を適用しており、放射状系統に対しては最適な順序付けになるが、ループ状系統に対しては最適な順序付けにはならず、ｆｉｌｌ−ｉｎが多くなり処理性能が悪化すること、また、並列計算を各ＣＰＵへ割当てるための処理に時間が掛り、並列処理のオーバヘッドが大きくなること、また、並列処理の効果をＣＰＵ間通信量と各ＣＰＵの処理量のバランスを考慮して決定するため、ＣＰＵ資源の無駄が発生する等の問題点があった。このような問題点と、さらに、オフラインで実施される系統解析業務以外の訓練シミュレータ、オンラインの給電自動化システム等への適用にはリアルタイム性能が要求されることから、従来の方法はこの分野には適用が困難であるという問題点があった。
【０００７】
本発明は、上記に鑑みてなされたものであって、大規模系統の回路網計算である連立一次方程式の求解を実時間性能で実行できる連立一次方程式の並列計算用のノード順序付け方法および連立一次方程式の並列求解方法を得ることを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するために、本発明にかかるノード順序付け方法は、複数個のＣＰＵと、前記各ＣＰＵが共通にアクセス可能な共有メモリと、を有する対称型マルチＣＰＵ構成の並列計算装置を用い、係数行列の三角分解、前進消去処理、および後退代入処理に基づいて電力系統の解析における連立一次方程式の解を並列計算する際に使用され、前記係数行列の構造ならびに前記前進消去処理および前記後退代入処理の手順を、ノードおよびノード間を接続するブランチからなるツリーで表現するときのノード順序付け方法であって、前記ツリーにおけるループを含まない系統部分である放射状系統部分に属するノードについてのノード順序付けを行う第１のステップと、前記ツリーにおける放射状系統部分以外の系統部分であるループ状系統部分に属するノードについてのノード順序付けを行う第２のステップと、を含み、前記第１のステップにおいては、最初に順序付けするノードはそのノードに接続されているブランチ数が最小のノードの中から任意に選択し、以降はノード順序付け候補のノードのうち各ノードに接続されているブランチ数が少ないノードから順に選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行い、前記第２のステップにおいては、前記複数個のＣＰＵを用いて前記前進消去処理におけるノードの縮約時に発生する新規非零要素発生数のシミュレーションを並列処理して実施し、前記シミュレーションにより得られた前記新規非零要素発生数の少ないノードから選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行うことを特徴とする。
【発明の効果】
【０００９】
この発明にかかるノード順序付け方法によれば、前進消去・後退代入処理における並列処理の実行効率を向上させて、処理性能を高速化できるという効果があり、大規模系統の回路網方程式（連立一次方程式）を実時間性能で実行することが可能になるという効果がある。
【発明を実施するための最良の形態】
【００１０】
以下に、本発明にかかる連立一次方程式の並列求解方法およびノード順序付け方法の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００１１】
実施の形態１．
図１は、本実施の形態が適用される訓練シミュレータの構成を示す構成図である。図１では、まず、訓練を実施するための訓練の問題となる系統構成状態、発電機・負荷条件、および事故発生条件等からなる訓練シナリオを、トレーナが訓練管理サーバ群１、トレーナ卓４を使用して作成し、登録する。次に、訓練実施時には、トレーナがトレーナ卓４から登録した訓練シナリオを選択して、実時間で実行するが、それに伴い、系統摸擬サーバ群２で系統シミュレーションが実行されて、その計算結果がトレーナ卓４、トレーニ卓５、および大画面系統盤６に表示される。トレーニ（被訓練者）は自動化摸擬サーバ群３、トレーニ卓５、大画面系統盤６を使用して、事故発生状況を確認、把握して、事故復旧操作のための復旧指令、復旧操作等を行い、停電している負荷の復旧等を行う。一方、訓練実施中の系統シミュレーションは、系統摸擬サーバ群２で実行されるが、本実施の形態を適用した系統の静的、動的特性をシミュレーションするソフトウェアは、この系統摸擬サーバ群２に実装され、動作する。訓練管理サーバ群１、系統摸擬サーバ群２、自動化摸擬サーバ群３間の情報の送受信、また、トレーナ卓４、トレーニ卓５、大画面系統盤６へのデータ送信は、システムＬＡＮ７を介して行う。
【００１２】
図２は、本実施の形態にかかる連立一次方程式の並列求解に利用される計算機構成の一例を示す図である。図２に示すように、本実施の形態における計算機は、例えば、対称型マルチＣＰＵ構成の計算機であり、複数のＣＰＵであるＣＰＵ１（８）、ＣＰＵ２（９）、ＣＰＵ３（１０）、・・・、ＣＰＵｎ（１１）と、各ＣＰＵが共通にアクセス可能な共有メモリ１２と、を備えて構成される。ここで、ｎは２以上の任意の整数である。なお、各ＣＰＵは、キャッシュメモリ、ローカルメモリ、および外部記憶装置を実装しており、システムＬＡＮ７と接続している。
【００１３】
図３は、系統摸擬サーバ群２に実装し、系統シミュレーションを行う動態安定度計算の処理例を示すフロー図である。動態安定度計算は、積分刻み毎（通常１０ｍｓｅｃ）に回路網方程式の求解と発電機の微分方程式の求解を交互に行い、電力系統の母線電圧、位相角、周波数、有効電力、無効電力、および発電機の内部位相角等を計算する。
【００１４】
図３においては、まず、初期処理として、計算時刻の初期化（ステップＳ１３）とＹ行列の作成、三角分解（ステップＳ１４）の処理を順次行う。ここで、Ｙ行列は回路網方程式の係数行列である。次に、回路網方程式の求解を行うが、まず、系統構成変化の有無を判定し（ステップＳ１５）、変化がない場合にはステップＳ１７に分岐する。変化がある場合は、Ｙ行列の修正、三角分解（ステップＳ１６）を行い、続いて、回路網方程式の電流項である発電機の等価電流源の計算（ステップＳ１７）と非線形負荷の等価電流源の計算（ステップＳ１８）とを行い、ステップＳ１６、Ｓ１７、Ｓ１８の結果を用いて回路網方程式の求解（ステップＳ１９）を行い、母線電圧を得る。そして、計算結果である回路網の母線電圧（Ｖ）収束の判定（ステップＳ２０）を行い、未収束の場合は、ステップＳ１８に分岐し、計算結果の母線電圧を使用して非線形負荷の等価電流源の計算（ステップ１８）を行い、回路網方程式の求解（ステップＳ１９）を繰返す。回路網方程式の求解が収束すれば、次に、発電機の微分方程式の求解を行う。
【００１５】
まず、発電機の動揺方程式の求解（ステップＳ２１）を行い、発電機内部位相角を算出し、次に発電機のＡＶＲ（自動電圧調整装置）、ガバナ等の制御系と発電機の電機子回路等について、発電機微分方程式の求解（ステップＳ２２）を行い、発電機内部電圧等を算出し、その発電機の内部電圧（Ｖ）収束（ステップＳ２３）の判定を行う。未収束の場合は、ステップＳ１７に分岐し、回路網方程式の求解と発電機微分方程式の求解を繰返す。回路網の電圧と発電機の内部電圧が収束した場合は、動態安定度計算の計算時刻更新（ステップＳ２４）を行い、さらに、計算終了（ステップＳ２５）の判定を行い、計算終了時間に至っていない場合は、ステップＳ１５に分岐し、回路網方程式の求解と発電機微分方程式の求解を繰返す。計算終了時間に至っている場合は、処理を終了する。本実施の形態の連立一次方程式の並列計算方法は、回路網方程式の求解（ステップＳ１９）を高速に処理するために適用されるものである。
【００１６】
次に、本実施の形態と従来の技術との相違を明確にするために、非特許文献１に記載の従来の系統計算の並列処理アルゴリズムの説明を行う。
【００１７】
従来の方法においても、計算機として、並列計算機（マルチＣＰＵ）を想定しており、ＣＰＵ間のデータ授受は通信処理により行うことを想定している。また、連立一次方程式の解法として、三角分解による直接解法を用いている。本手法を用いた場合、
ｙ＝Ａ・ｘ ・・・（１）
という連立一次方程式の求解を以下の３つの処理で行うことになる。
（１）ノードの順序付け
（２）係数行列Ａの三角分解（ＬＤＵ分解）
（３）前進／後退代入計算によるｘの算出
【００１８】
安定度計算は、系統計算（回路網計算）と発電機微分方程式求解から構成され、系統計算が全体の約４割を占め、その内、前進／後退代入計算が約６割を占め、かつ、多数回の計算が行われる。また、三角分解と前進／後退代入の処理は、ノードの順序付けが決まれば自動的に決定されるので、ノードの順序付けをどのように行うかが逐次処理での直接法高速化の鍵となる。連立一次方程式の直接解法における前進代入処理は、
ｘｊ＝ｘｊ＋ｘｉ・Ｄｉｊ ・・・（２）
という計算の繰返し処理であり、（２）式は、ノードｉとノードｊとを結ぶブランチＤｉｊを消去して、ノードｊの値を変更するという処理である（（２）式のＤｉｊは、三角分解（ＬＤＵ分解）における対角要素である。）。あるノードｉについてブランチＤｉｊを全てのｊについて消去すれば、ノードｉの値ｘｉは以後の処理には必要でなくなる。これはノードｉの消去に対応する。後退代入計算も同様であり、例えば、図２１−１の単純なネットワークの場合には、（２）式の処理を前進／後退代入それぞれについて、６回繰返すことになる。なお、図中の点線のブランチは三角分解の結果生じるｆｉｌｌ−ｉｎ（三角分解により新たに発生する非零要素）に対応する。
【００１９】
前進／後退代入計算の処理は、図２１−２のようにツリー構造の処理過程として表すことができる。図２１−２の横向きの矢印は前進代入でのノードの消去を表している。また、図２１−２での矢印の向き（上から下）は前進代入での処理の流れであり、後退代入の場合はツリーの根から葉の方へ（下から上へ）、ツリーをたどる処理となる。
【００２０】
図中、四角で囲っている箇所は、ノードが複数データを持つことを意味している。例えば、ノード１を消去した場合、ノード３とノード５の両方の値が変わることになるが、ノード１から見てノード番号が近い方のノード３に渡す。そのためノード３は自分自身のデータとノード５の値を更新するためのデータを持つことになる。この表現法により、ノード間をどのようなデータが移動していくかを容易に把握できる。
【００２１】
ここで注意すべきは、ノード１の消去とノード２の消去の処理は順番を入れ替えても、あるいは同時に並列に処理しても計算結果に影響を与えないことである。なぜならば、これらの計算は互いに無関係に行うことができる（依存関係がない）からである。つまり、ツリーにおいて並んでいる横向きの矢印（ノードの消去）同士は並列に実行できることになる。したがって、ノードの消去を一つの処理単位として考えると、図２１−２の例の前進代入計算は、逐次処理では４ステップの処理であるのに対し、並列処理では３ステップの処理で済むことになる。以下、並列処理での各ステップ（複数のノード同時消去）をステージと呼ぶ。
【００２２】
図２１−２のようなツリーを用いた前進／後退代入処理の表現は、これまでも提案されているが、図２１−２のツリー表現は、これまでのものよりも前進代入計算処理で並列に実行可能な処理の抽出を容易なものとするために考案されたものであり、以下の特徴をもっている。
（１）ツリーの各ステージの処理は、前進代入においては必ず左から右に（後退代入では右から左に）ツリーをたどる向きとなり、逆向きの処理は発生しない。
（２）同一ステージ内のノードの処理（横向きの矢印）は全て並列に行うことができ
る。
（３）並列処理の場合、例えば前進代入で、ノードの消去処理時に消去されるノードと値の変わるノードが異なるＣＰＵに割当てられている場合には、通信処理が発生する。これはツリーでＣＰＵ間をまたがる横向きの矢印となるため、並列処理時に必要となる通信回数が容易に把握できる。
（４）ノード間でどのようなデータが渡されるかがツリー上に明示されている。このため、並列処理時に通信で授受されるデータが容易に把握できる。
【００２３】
非特許文献１では、Ｔｉｎｎｅｙ２法をベースにして並列処理向けの新しいノードの順序付け手法を考案している。前進／後退代入計算の並列処理を効率良く行うには、並列に実行できる計算ができるだけ多くなるように順序付けをすることが必要となる。そのためには、ステージ数がなるべく小さくなるようにノードの順序付けを行えば良い。そこでノードの順序付けを、各ステージでのノードの消去処理が通信処理の妨げにならない範囲でできるだけ多くなるように、かつＬＤＵ分解でのｆｉｌｌ−ｉｎの発生ができるだけ少なくなるように行うようにしている。
【００２４】
具体的には、各ステージで消去されるノードに関して、以下の２つの選択基準を設けている。
【００２５】
（１）ノードの消去により発生するｆｉｌｌ−ｉｎが少ないものから選択していく。ただし、あるステージで接続ブランチが２本以下のノードが消去される場合には、接続ブランチ数が３本以上のノードはこのステージでは消去せず、次のステージ以降で消去する。
（２）あるノードから２ブランチまでの範囲に、同じステージで消去されるノードがある場合、当該ノードは消去しない。
【００２６】
ノードの消去によって発生するｆｉｌｌ−ｉｎの数は、そのノードに接続しているブランチ数によって決まるので、接続するブランチ数が少ないノードから選択することで、（１）の条件を満たすことができる。また、接続ブランチ数の多いノードが早い段階で消去されると、ｆｉｌｌ−ｉｎの数の増大を招くので、接続ブランチ数が２本以下のノードが消去されるステージでは、接続ブランチ数が３本以上のノードは消去しない。
【００２７】
（２）の条件に関しては以下の理由による。あるノードが消去されるとそのノードに隣接するノードの値が書き換えられる。消去されたノードから２ブランチの範囲までに、同じステージで消去されるノードがあると、再度の値の書き換えが行われる可能性がある。２度の書き換えの両方が通信処理を伴う場合、２つの通信処理の前後関係を判断するのは不可能である。２つの通信処理のスケジューリング上の前後関係が実際の前後関係と異なる場合には、通信時間を余計に長くしてしまうことになり、また、使用計算機のＣＰＵ間の通信方式が共通のバスを用いる場合には、バスの混雑が発生し、通信処理に大きなペナルティが発生する可能性がある。このような通信処理の非効率化を避けるために、（２）の条件を設けている。
【００２８】
以上に述べた、ノードの順序付けのアルゴリズムを図２２に示す（非特許文献１を参照）。ここでは、接続ブランチ数が２以下のノードがない場合にのみ、接続ブランチ数が３以上のノードが選択できるようにしている。
【００２９】
以上、ノードの順序付けについて述べたが、これは前進／後退代入の計算過程から、「並列処理が行える処理を抽出する処理」であり、順序付けの結果として得られた処理を各ＣＰＵに割当てていく必要がある。系統解析計算の多くが基本的にノード単位の処理であるため、非特許文献１では、ノード単位にＣＰＵに割当てることとしている。
【００３０】
効率の良い並列処理を実現するためには、以下の２点を考慮する必要がある。
・通信回数の低減
・ＣＰＵ間での計算処理の均等化
【００３１】
この２つの目的はトレードオフの関係にある。そこで、一つのパラメータ（以下、グループ化係数と呼ぶ）を用いて、ノードにＣＰＵを割当てる際にノードのグループの大きさを調整するようにし、両者のバランスが取れるようにしている。
【００３２】
通信の処理は計算の処理に比べて時間を要するため、通信回数をなるべく少なくすることが並列処理による高速化の観点から不可欠となる。処理ツリー上では通信処理はＣＰＵ間にまたがる横向きの矢印であるので、横向きの矢印の少ない、番号の大きなステージで通信を行うようにする。
【００３３】
各ＣＰＵに処理を割当てるアルゴリズムは以下のようになる。
（１）前進／後退代入の処理ツリーを番号の大きなステージで切る。ただし、切り離された枝葉の部分のノード数が、（全ノード数）／（グループ化係数）を上回らないようにする。切り離された枝葉の部分の各々を一つのグループとする。
（２）（１）の結果得られるグループの境界線から、（ＣＰＵ数−１）本の境界線を選択して、ＣＰＵへの割り当ての境界線とする。その際、
Σｉ｜ｎｉ−ｎＴｏｔａｌ／ｎＣＰＵ｜ ・・・（３）
を最小化する境界線の組合せを選択する。ただし、ｎｉはＣＰＵｉに割当てられるノードの数、ｎＴｏｔａｌは全ノード数、ｎＣＰＵはＣＰＵ数を表す。
【００３４】
上述のような非特許文献１に記載の方法は、ノードの順序付けにＴｉｎｎｅｙ２法を適用しており、放射状系統に対しては最適になるが、ループ状系統に対しては最適にはならず、ｆｉｌｌ−ｉｎが多くなり処理性能が悪化すること、また、並列計算を各ＣＰＵへ割当てるための処理に時間が掛り、並列処理のオーバヘッドが大きくなること、また、並列処理の効果をＣＰＵ間通信量と各ＣＰＵの処理量のバランスを考慮して決定するため、ＣＰＵ資源の無駄が発生する等の問題点があった。ここで、放射状系統とは、内部にループ構造を含まない系統であり、ループ状系統とはループ構造を含む系統である。なお、実際の系統では、発電所等が系統の末端にあり、そのため、ツリーの中に放射状系統部分は必ず存在している。このような問題点と、さらに、オフラインで実施される系統解析業務以外の訓練シミュレータ、オンラインの給電自動化システム等への適用にはリアルタイム性能が要求されることから、非特許文献１に記載の方法はこの分野には適用が困難であるという問題点があった。
【００３５】
そこで、本実施の形態では、リアルタイム性能を実現させるために、非特許文献２に記載された連立一次方程式の求解方法に基づき、前進消去・後退代入処理の並列処理化を向上させるノード順序付け方法を以下に開示する。
【００３６】
図１１−１および図１１−２は、本実施形態のノード順序付け方法を示すフロー図であり、図１１−２は、図１１−１に続く処理を示す。なお、図１１−１と図１１−２とは、‘１’で示す箇所で接続される。図１１−１において、まず初期化処理（１）（ステップＳ４０）により、フラグ類の初期設定を行い、次に各ノードに接続する相手端ノード番号、相手端ノード数等のノードテーブル作成（ステップＳ４１）を行い、相手端ノード数の少ない順番にノードテーブル並替え（ステップＳ４２）を行う。相手端ノード数が同一の場合は、先に処理したノード順に並替えを行う。なお、各ノードに接続する相手端ノードとは、各ノードに（１本の）ブランチを介して接続されている隣接ノードをいう。例えば、図１３−３においては、ノード１の相手端ノードは、ノード５である。
【００３７】
次に、まず、放射状系統部分のノード順序付けを行う。放射状系統部分においては、例えば図１３−３の放射状系統におけるノード１、ノード２、ノード３、ノード４、およびノード６のように、あるノードに接続するブランチ数が１つという部分を含み、従って、このようなノードに対しては、相手端ノード数も１つということになる。また、例えばノード１を任意に選択して順序付けた場合、ノード１が消去されノード１とノード５との間のブランチも消去されると、ノード５の接続ブランチ数が１つとなって、同様の構造が生じる。そして、順次、放射状系統部分のノード順序付けを行えば、最適なノード順序付けを行えることが分かっている（Ｔｉｎｎｅｙ２法の考え方）。以下、この特徴に基づき、ノード順序付けを行う。
【００３８】
前進消去、後退代入処理を並列処理する場合、通常は各ＣＰＵが１ノードの処理を行うため、並列処理に利用されるＣＰＵ数（以下、並列ＣＰＵ数という。）の要素を一度に扱うことになり、それらの要素処理単位でノード順序付けを行う必要がある。このため、まずステップＳ４３で同時に順序付けを行うノード数が並列ＣＰＵ数以下か否かの判定を行い、Ｎｏの場合は初期化処理（２）（ステップＳ４４）により、要素数カウントの初期化を行う。Ｙｅｓの場合は、何も処理せず、ステップＳ４５に分岐する。
【００３９】
ステップＳ４５では、順序付け対象のノードｉが放射状系統か否かの判定を行い、Ｙｅｓであれば、ステップＳ４６で、ノードｉは並列処理可能か否かの判定を行う。なお、並列処理可能か否かの判定については後述する。ステップＳ４６での判定の結果がＹｅｓの場合、ノードｉを順序付け（ステップＳ４７）、各種配列のカウントアップ（１）（ステップＳ４８）を行い、ステップＳ４３に分岐する。ステップＳ４６での判定の結果がＮｏの場合は、この処理では当該ノードｉを順序付け除外対象（ステップＳ４９）とし、各種配列のカウントアップ（２）（ステップＳ５０）を行い、ステップＳ４３に分岐する。
【００４０】
ステップＳ４５でＮｏの場合は、除外対象ノードとした放射状系統部分が残っているかどうかを確認するために、順序付けが未実施のノードについて、相手端ノード数が少ない順番にノードテーブル並替え（ステップＳ５１）を行い、初期化処理（３）（ステップＳ５２）を行う。次に、ノードテーブル並替え後のノードについて、ノードｉが放射状系統部分か否かの判定（ステップＳ５３）を行い、Ｙｅｓの場合は、さらに放射状系統部分が全て除外対象であるか否かの判定（ステップＳ５４）を行い、ステップＳ５４での判定結果がＮｏの場合、ステップＳ４６に分岐する。ステップＳ５４での判定結果がＹｅｓの場合は、全除外対象ノードを順番に順序付け（ステップＳ５５）を行い、図１１−２の‘１’に示すステップに進む。ステップＳ５３でＮｏの場合は、図１１−２の‘１’に示すステップに進む。
【００４１】
上記までの処理で、放射状系統部分のノード順序付けが終了したので、以降はループ系統部分のノード順序付けを行う。ループ系統部分については、最適なノード順序付け方法が無く、従って、各ノードの新規非零要素発生のシミュレーションを行い、その新規非零要素発生数の一番少ないノードについて、順序付けを行い、それを繰返して実施して行くことが準最適化になることになっている（Ｔｉｎｎｅｙ３法の考え方）。ここでは、その考え方に基づき、以下の手順でノード順序付けを行う。
【００４２】
図１１−２に示すように、まず、ステップＳ５６で、各種フラグ等の初期化処理（４）を行い、次に残りノード全てについて、新規非零要素発生のシミュレーション（ステップＳ５７）を行い、新規非零要素発生数の少ない順番にノード並替え（ステップＳ５８）を行う。次に、順序付けノード数が並列ＣＰＵ数以上か否かの判定（ステップＳ５９）を行い、Ｙｅｓの場合は、順序付け配列数等の初期化処理（２）（ステップＳ６０）を行い、ステップＳ６１に分岐する。Ｎｏの場合は、何も処理せずにステップＳ６１に分岐する。ステップＳ６１では、ノードｉが並列処理可能か否かの判定を行い、Ｙｅｓの場合、ノードｉを順序付け（ステップＳ６２）をし、各種配列のカウントアップ（３）（ステップＳ６３）を行い、次に、ステップＳ６４で、全ノードの順序付けが終了したか否かの判定を行い、Ｎｏの場合は、各種配列のカウントアップ（４）（ステップＳ６５）を行い、ステップＳ５７に分岐する。ステップＳ６４での判定結果がＹｅｓの場合は、処理を終了する。ステップＳ６１でＮｏの場合は、この処理ではノードｉを除外対象（ステップＳ６６）とし、各種配列のカウントアップ（５）（ステップＳ６７）を行い、続いて、残りのノードが全て除外対象か否かの判定（ステップＳ６８）を行い、Ｎｏの場合は、各種配列のカウントアップ（６）（ステップＳ６９）を行い、ステップＳ５９に分岐する。ステップＳ６８でＹｅｓの場合は、残りのノードについて、新規非零要素発生のシミュレーション（ステップＳ７０）を行い、新規非零要素発生数の少ない順番にノード並替え（ステップＳ７１）を行い、そして、それが最小のノードｉの順序付け（ステップＳ７２）を行い、全て終了すれば処理を終了する。
【００４３】
図１２は、図１１−２における新規非零要素発生のシミュレーションの並列処理を示すフロー図である。ループ系統部分においては、ノード順序付けの最適化のために、残りの全ノードについて、そのノードを順序付けした場合の新規非零要素発生数がいくつになるかのシミュレーションを行い、その新規非零要素発生数が最小のノードを次の順序付けノード候補とし、当該ノードを並列処理が可能か否かの判定を行い、並列処理が可能な場合は、そのノードの順序付けを行い、以降、上記の処理を最後まで繰返し、実施している。従って、ループ系統部分のノード順序付けは、処理時間が掛かることになる。そのため、新規非零要素発生のシミュレーションについては、並列処理を行い、処理の高速化を実現する。
【００４４】
図１２において、ループ系統部分の全ノードを、並列処理を行う複数のＣＰＵに平均的に按分して、処理を分担することを考える。まず、各ＣＰＵで処理する場合の平均処理量の計算（ステップＳ７３）を行い、また、平均処理量の計算における余りの計算（ステップＳ７４）を行う。余りの処理量については、ＣＰＵ１で担当させる（すなわち、ＣＰＵ１は、平均処理量＋余り分の処理を担当する。）。次に、処理するＣＰＵがＣＰＵ１か否かの判定（ステップＳ７５）を行い、Ｙｅｓの場合は、処理対象（ｋ１、ｋ２）の計算（ステップＳ７６）を行い、以降の処理におけるフラグ類の初期化処理（ステップＳ７７）を行い、ステップＳ７９に分岐する。ＣＰＵ１以外の場合は、処理対象（ｋ１、ｋ２）の計算（ステップＳ７８）を行い、ステップＳ７９に分岐する。ステップＳ７９では、各ＣＰＵが処理を実行できる状態か否かを、自身に対するＣＰＵ処理フラグである自ＣＰＵ処理フラグがゼロか否かで判定し、Ｎｏの場合は継続してチェックを行う。ステップＳ７９でＹｅｓの場合は、各ＣＰＵが担当する処理量について、新規非零要素発生のシミュレーション（ステップＳ８０）を行い、その結果を共有メモリに保存する。その後、各ＣＰＵは処理が終了したことをＣＰＵ１に示すために、自ＣＰＵ処理フラグに、自ＣＰＵ番号を書き込む（ステップＳ８１）。
【００４５】
次に、再び、ＣＰＵ１か否かの判定（ステップＳ８２）を行い、ＣＰＵ１の場合は、全ＣＰＵの処理フラグが正か否かの判定（ステップＳ８３）を行い、ステップＳ８３での判定結果がＮｏの場合は継続してチェックを行う。ステップＳ８３での判定結果がＹｅｓの場合は、各ＣＰＵが計算した新規非零要素発生数が少ない順番に並び替えを行い、それが最小である最初のノードを選定し（ステップＳ８４）、その後、処理終了フラグにＣＰＵ１の番号をセットし（ステップＳ８５）、処理を終了する。ステップＳ８２でＣＰＵ１でない場合、処理終了フラグが正か否かの判定（ステップＳ８６）を行い、Ｎｏの場合は継続してチェックを行い、Ｙｅｓの場合は処理を終了する。
【００４６】
次に、本実施の形態の動作について説明する。本実施の形態は、非特許文献２に記載の連立一次方程式求解の実時間処理を実現するために、連立一次方程式の前進消去・後退代入の処理について、並列処理を可能とすると共に、並列処理の実行効率を向上させて処理性能の大幅な向上を実現するものである。なお、図２に示すように、連立一次方程式の並列計算を行う計算機構成は、共有メモリ結合された対称型マルチＣＰＵを想定しており、この計算機であれば、各ＣＰＵで共通に読み書きするデータを共有メモリに配置することにより、計算機間の通信手段を不要とし、高速にデータのアクセスができることになり、各ＣＰＵの性能を十分に活用することが可能になる。
【００４７】
非特許文献２では、ノードの順序付け方法としてＴｉｎｎｅｙ２法に基づいている。図４は、非特許文献２に記載の系統例を示す図であり、円内の数字は、ノード番号を示す。また、図５は、図４の系統例の回路網方程式（連立一次方程式）を示す図である。また、非特許文献２では、係数行列の三角分解については、図６の処理フローにより実施し、その結果を図７に示すテーブル形式で保存している。図６では、処理はｉ、ｊ、ｋの３重のループで構成されており、ループｉではステップＳ２６、Ｓ２７の処理を、ループｊではステップＳ２８、Ｓ２９の処理を、また、ループｋではステップＳ３０の処理を行う。図６におけるＮＮｍａｘはノード総数を示す。図７では、’のついている要素は、三角分解の過程で変更を受けた要素であり、Ｐ（ｋ）、Ｑ（ｋ）はノードの縮約順序を示すベクトルである。また、Ｎｍａｘは、係数行列の三角分解後の非対角非零要素数を示す。ノード順序付けは、Ｑ（ｋ）で示すノードを消去し、Ｐ（ｋ）で示すノードに縮約したことを示している。一方、係数行列の三角分解後に行う前進消去・後退代入の処理は、図８に示す処理フローに従って実行するが、後退代入の処理は、２段階に分かれている。この前進消去の処理において、並列処理の阻害要因があり、それを図９により説明する。
【００４８】
図９においては、例えばＣＰＵ４台で並列処理する場合を示しており、１回目の並列処理では、ｋ＝１，２，３，４をそれぞれＣＰＵ１、ＣＰＵ２、ＣＰＵ３、ＣＰＵ４が担当するが、ＣＰＵ２については、Ｑ（２）＝２が先行して処理するＣＰＵ１のＰ（１）＝２と一致するため、並列処理ができず、直列に処理を行う必要がある。そのため、ＣＰＵ１の処理が終了した後に、ＣＰＵ２の処理を実行する必要がある。また、ＣＰＵ４については、Ｐ（４）＝４が、ＣＰＵ３のＰ（３）＝４と一致するため、並列処理ができず、直列に処理を行う必要があり、ＣＰＵ３の処理が終了した後に、ＣＰＵ４の処理を実行する必要がある。同様に、２回目の並列処理においては、ＣＰＵ２の処理は並列処理ができず、また、３回目の並列処理においては、ＣＰＵ２の処理は並列処理ができないことが分かる。
【００４９】
一方、後退代入の処理における並列処理の阻害要因については、図１０を参照して説明する。後退代入処理については、要素番号の大きいものから要素番号が小さい方向に、処理を行う。まず、１回目の並列処理においては、ｋ＝１０，９，８，７を、それぞれＣＰＵ１、ＣＰＵ２、ＣＰＵ３、ＣＰＵ４が担当するが、ＣＰＵ２については、Ｐ（９）＝１０が、ＣＰＵ１のＱ（１０）＝１０と一致するため、並列処理ができず、直列に処理を行う必要がある。そのため、ＣＰＵ１の処理が終了した後に、ＣＰＵ２の処理を実行する必要がある。また、２回目の並列処理においては、ＣＰＵ２については、Ｐ（５）＝３が、ＣＰＵ１のＱ（６）＝３と一致するため、並列処理ができず、直列に処理を行う必要があり、ＣＰＵ１の処理が終了した後に、ＣＰＵ２の処理を実行する必要がある。さらに、ＣＰＵ４については、Ｐ（３）＝４が、ＣＰＵ３のＰ（４）＝４と一致するため、並列処理ができず、直列に処理を行う必要があり、ＣＰＵ３の処理が終了した後に、ＣＰＵ４の処理を実行する必要がある。３回目の並列処理でも、ＣＰＵについては、Ｐ（１）＝２が、ＣＰＵ１のＱ（２）＝２と一致するため、並列処理ができず、直列に処理を行う必要があり、ＣＰＵ１の処理が終了した後に、ＣＰＵ２の処理を実行する必要がある。前述の通り、後退代入処理における並列処理の阻害要因も、前進消去処理と同じであることが分かる。
【００５０】
係数行列のノード順序付けを行うと、三角分解、前進消去、後退代入の処理も全て、同じ影響を受けることになる。従って、係数行列の三角分解の処理に悪影響を与えず、前進消去と後退代入処理の並列処理の実行効率を向上させるノード順序付け方法を考案することが求められる。
【００５１】
従って、本実施の形態では、以下の基本的考え方に基づき、ノード順序付けを行う。
【００５２】
（１）ｆｉｌｌ−ｉｎの最小なノードからノード順序付けを行う。この条件を維持すれば、係数行列の三角分解の処理は、従来の方法と同じ考え方であり、処理性能が悪くなることは無い。
（２）（１）に基づき、前進消去処理における並列処理が可能なノードを優先して、ノ
ード順序付けを行う。これにより、前進消去処理の並列処理の実行効率を向上できると共に、後退代入処理の並列処理の実行効率も向上できる。
【００５３】
前進消去処理の並列処理の実行効率を向上させるためのノード順序付け方法を以下に説明する。前進消去処理における並列処理の阻害要因については、図９に基づき説明した。従って、この阻害要因を解消し、以下の考え方でノード順序付けを行う。
（１）ｆｉｌｌ−ｉｎが最小なノードからノード順序付けを行う。
（２）最初のノードは、（１）で得られたｆｉｌｌ−ｉｎが最小なノードの中から任意に選択するが、以降の並列処理対象のノードについては、当該ノード順序付け候補のノードとその相手端ノードが、順序付け済みのノードの相手端ノードと一致しないノードである場合、優先してノード順序付けを行う。ノード順序付け候補のノードとその相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードであるか否かは、前述の、並列処理が可能か否かの判定である。
（３）優先して順序付けるノードが全て無くなれば、残りのノードをｆｉｌｌ−ｉｎが最小なノードから順にノード順序付けを行う。
【００５４】
上記の考え方を処理フローで表現したのが、図１１−１および図１１−２である。図１１−１では、まず、ｆｉｌｌ−ｉｎが最小となる放射状系統部分のノード順序付けを行い、その後、図１１−２で、ループ状系統部分のノード順序付けを行う方法である。なお、ノード順序付け方法については、放射状系統部分にはＴｉｎｎｅｙ２法を、ループ状系統部分についてはＴｉｎｎｅｙ３法を適用しており、ｆｉｌｌ−ｉｎが最小となる方法である。
【００５５】
なお、Ｔｉｎｎｅｙ３法を適用した計算では、新規非零要素発生のシミュレーションを全ノードについて実施し、ｆｉｌｌ−ｉｎが最小なノードを選択することになるため、これを並列処理して、高速化を実現している。その処理フローを図１２に示す。図１２では、まず、各ＣＰＵが自分の処理対象要素を計算するために、各ＣＰＵの平均処理量と余りを計算し、ＣＰＵ１が先頭から、（平均処理量＋余り）の要素を分担し、ＣＰＵ２以降はそれに続く、平均処理量の要素を分担するようにしている。その後、各ＣＰＵが分担する全要素について、新規非零要素発生数のシミュレーションを行い、処理が終了すれば、共有メモリにそのシミュレーション結果と自分のＣＰＵ処理フラグに自分のＣＰＵ番号をセットする。全体の管理を行うＣＰＵ１は、自分の処理が終了し、全ＣＰＵのＣＰＵ処理フラグがセットされていれば、全処理が終了したことになるので、各ＣＰＵの計算した新規非零要素発生数のシミュレーション結果を共有メモリから取り出し、それを新規非零要素発生数の少ない順番に並び替えを行い、最初のノードをノード順序付け候補として選択する。そして、処理終了フラグをセットし、処理を終了する。一方、ＣＰＵ１以外のＣＰＵは、処理終了フラグをチェックし、処理終了フラグがセットされていれば、処理を終了する。以上の方法で、新規非零要素発生数のシミュレーションを並列処理することができる。
【００５６】
次に、このノード順序付け方法の効果を、図１３−１〜図１３−４を参照して説明する。図１３−１は、系統例における従来のノード順序付けされたノード番号を示し、図１３−２は、そのノード順序付けに従い、三角分解をした結果を示す。図１３−３は、本実施形態のノード順序付けに基づくノード順序付けの結果を示し、図１３−４は、そのノード順序付けに基づき、三角分解をした結果を示す。図１３−１および図１３−３は、図５に示す連立一次方程式の係数行列の構造をツリーで表現し、このツリーはノードとノード間を接続するブランチとから構成されている。図１３−１、１３−２では、矢印で示すように、並列処理が不可能な処理が４回発生している。一方、図１３−３、１３−４は、実施の形態１のノード順序付け方法の結果を示しており、並列処理が不可能な処理が２回となっており、効果があることを示している。特に、本実施の形態におけるノード順序付けの基準の一つである、ノード順序付け候補のノードとその相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に優先してノード順序付けにより、図１３−２に示すような並列処理の阻害要因を解消する効果があることがわかる。
【００５７】
このように、本実施の形態における連立一次方程式の並列計算方式のノード順序付け方法は、ｆｉｌｌ−ｉｎが最小なノードからノード順序付けを行うが、最初のノードは、ｆｉｌｌ−ｉｎが最小なノードの中から任意に選択し、以降の並列処理対象のノードについては、当該ノードとその相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に優先してノード順序付けを行う。そして、優先して順序付けるノードが無くなれば、残るノードをｆｉｌｌ−ｉｎが最小なノードからノード順序付けを行うようにしたものである。本実施の形態によれば、前進消去・後退代入処理における並列処理の実行効率を向上させて、処理性能を高速化できるという効果があり、大規模系統の回路網方程式（連立一次方程式）を実時間性能で実行することが可能となる。
【００５８】
実施の形態２．
図１１−１は、実施の形態２のノード順序付け方法を示すフロー図であり、図１１−２は、図１１−１に続くフロー図である。すなわち、本実施の形態でも実施の形態１と同様のノード順序付け方法に従う。しかしながら、実施の形態１では、ループ状系統部分のノード順序付けにおける新規非零要素発生のシミュレーションを並列処理しているが、実施の形態２では、この新規非零要素発生のシミュレーションを並列処理せず、１台のＣＰＵで処理するようにしたものである。このようにすれば、処理性能は高速化できないが、ノード順序付けの最適化は実現可能であり、ＣＰＵ台数を少なくして訓練シミュレータを安価に構成できるという効果がある。
【００５９】
実施の形態３．
図１４−１および図１４−２は、実施の形態３のノード順序付け方法を示すフロー図である。なお、図１４−２は、図１４−１に続く処理を示しており、‘２’で示す箇所において処理が接続される。図１４−１において、まず初期化処理（１）（ステップＳ９０）により、フラグ類の初期設定を行い、次に各ノードに接続する相手端ノード番号、相手端ノード数等のノードテーブル作成（ステップＳ９１）を行い、相手端ノード数の少ない順番にノードテーブル並替え（ステップＳ９２）を行う。相手端ノード数が同一の場合は、先に処理したノード順に並び替えを行う。
【００６０】
次に、まず、放射状系統部分のノード順序付けを行う。放射状系統部分においては、例えば図１３−３の放射状系統におけるノード１、ノード２、ノード３、ノード４、およびノード６のように、あるノードに接続するブランチ数が１つという部分を含み、従って、このようなノードに対しては、相手端ノード数も１つということになる。また、例えばノード１を任意に選択して順序付けた場合、ノード１が消去されノード１とノード５との間のブランチも消去されると、ノード５の接続ブランチ数が１つとなって、同様の構造が生じる。そして、順次、放射状系統部分のノード順序付けを行えば、最適なノード順序付けを行えることが分かっている（Ｔｉｎｎｅｙ２法の考え方）。以下、この特徴に基づき、ノード順序付けを行う。
【００６１】
前進消去、後退代入処理を並列処理する場合、各ＣＰＵが１ノードの処理を行うため、並列処理を行うＣＰＵ数の要素を一度に扱うことになり、それらの要素処理単位でノード順序付けを行う必要がある。このため、まずステップＳ９３で、同時に順序付けを行うノード数が並列ＣＰＵ数以下か否かの判定を行い、Ｎｏの場合は初期化処理（２）（ステップＳ９４）により、要素数カウントの初期化を行う。ステップＳ９３での判定結果がＹｅｓの場合は、何も処理せず、ステップＳ９５に分岐する。
【００６２】
ステップＳ９５では、順序付け対象のノードｉが放射状系統か否かの判定を行い、Ｙｅｓであれば、ステップＳ９６で、ノードｉは並列処理可能か否かの判定を行う。ステップＳ９６での判定結果がＹｅｓの場合、ノードｉを順序付け（ステップＳ９７）を行い、各種配列のカウントアップ（１）（ステップＳ９８）を行い、ステップＳ９３に分岐する。
ステップＳ９６での判定結果がＮｏの場合は、この処理では当該ノードｉを順序付け除外対象（ステップＳ９９）とし、各種配列のカウントアップ（２）（ステップＳ１００）を行い、ステップＳ９３に分岐する。
【００６３】
ステップＳ９５でＮｏの場合は、除外対象ノードとした放射状系統部分が残っているかどうかを確認するために、順序付けが未実施のノードについて、相手端ノード数が少ない順番にノードテーブル並替え（ステップＳ１０１）を行い、初期化処理（３）（ステップＳ１０２）を行う。次に、ノードテーブル並替え後のノードについて、ノードｉが放射状系統部分か否かの判定（ステップＳ１０３）を行い、Ｙｅｓの場合は、さらに放射状系統部分が全て除外対象であるか否かの判定（ステップＳ１０４）を行い、Ｎｏの場合、ステップＳ９６に分岐する。ステップＳ１０４でＹｅｓの場合は、全除外対象ノードを順番に順序付け（ステップＳ１０５）を行い、図１４−２に示す処理に進む。また、ステップＳ１０３でＮｏの場合は、図１４−２示す処理に進む。
【００６４】
上記までの処理で、放射状系統部分のノード順序付けが終了したので、以降はループ状系統部分のノード順序付けを行う。ループ状系統部分についても、放射状系統部分と同様の考え方でノード順序付けを行う。
【００６５】
図１４−２に示すように、まず、ステップＳ１０６で、各種フラグ等の初期化処理（４）を行い、次に、残りノード全てについて、ノード接続数の少ない順番にノードテーブルの並び替え（ステップＳ１０７）を行い、ノード接続数が少ない順番にノードを並替える。次に、順序付けノード数が並列ＣＰＵ数以上か否かの判定（ステップＳ１０８）を行い、Ｙｅｓの場合は、順序付け配列数等の初期化処理（２）（ステップＳ１０９）を行い、ステップＳ１１０に分岐する。ステップ１０８でＮｏの場合は、何も処理せずにステップＳ１１０に分岐する。ステップＳ１１０では、ノードｉが並列処理可能か否かの判定を行い、Ｙｅｓの場合、ノードｉを順序付け（ステップＳ１１１）をし、各種配列のカウントアップ（３）（ステップＳ１１２）を行い、次に、ステップＳ１１３で全ノードの順序付けが終了したかの判定を行う。ステップＳ１１３でＮｏの場合は、各種配列のカウントアップ（４）（ステップＳ１１４）を行い、ステップＳ１０７に分岐する。ステップＳ１１３でＹｅｓの場合は、処理を終了する。
【００６６】
ステップＳ１１０でＮｏの場合は、この処理ではノードｉを除外対象（ステップＳ１１５）とし、各種配列のカウントアップ（５）（ステップＳ１１６）を行い、続いて、残りのノードが全て除外対象か否かの判定（ステップＳ１１７）を行い、Ｎｏの場合は、各種配列のカウントアップ（６）（ステップＳ１１８）を行い、ステップＳ１０８に分岐する。ステップＳ１１７でＹｅｓの場合は、残りのノードについて、ノード接続数が少ない順番にノードテーブルの並替え（ステップＳ１１９）を行い、そして、それが最小のノードｉの順序付け（ステップＳ１２０）を行い、全て終了すれば処理を終了する。
【００６７】
実施の形態１では、ループ状系統部分のノード順序付けにおいて、新規非零要素発生数のシミュレーションを並列処理するようにしたが、この実施の形態３では、ループ状系統部分のノード順序付けにおいて、新規非零要素発生のシミュレーションの替わりに、放射状系統部分と同様に、あるノードに接続する相手端ノード数が少ない順番にノード順序付け候補とするようにしたものである。このようにすれば、ノード順序付けの最適化の度合いは実施の形態１よりは低下するが、ノード順序付けの処理を１台のＣＰＵでも高速に処理できるため、訓練シミュレータにおける訓練実行段階でも系統構成状態の変化が発生した場合に、再度、ノード順序付けを高速に実行できるため、訓練実行段階における回路網計算を準最適化できる。そのため、連立一次方程式の求解を高速に処理することが可能になると共に、安価に訓練シミュレータを構成できるという効果がある。また、給電自動化システム等のオンライン用途のシステムにも適用可能になるという効果がある。
【００６８】
実施の形態４．
本実施の形態にかかる連立一次方程式の並列求解方法について説明する。なお、ノード順序付けは、実施の形態１〜３のいずれか１つのノード順序付け方法を利用して行い、また、係数行列の三角分解は非特許文献２の方法により実施するものとし、その三角分解結果を用いて、前進消去処理および後退代入処理を行うものとする。図１５−１および図１５−２は、本実施の形態にかかる連立一次方程式の並列求解方法を示すフロー図であり、実施の形態１、２、または３のノード順序付け方法を適用した前進消去、後退代入過程の複数ＣＰＵによる並列処理を示すフロー図である。なお、図１５−２は、図１５−１に続く処理の流れを示し、‘３’で示す箇所で接続されている。
【００６９】
図１５−１において、まず、前進消去過程の並列処理を行うが、最初に、ＣＰＵ１か否かの判定（ステップＳ１２１）を行い、Ｙｅｓの場合は、フラグ類の初期化処理（ステップＳ１２２）を行い、次に、各ＣＰＵが並列処理できるか否かを示す並列処理フラグの作成（ステップＳ１２３）を行い、ステップＳ１２４に進む。ステップＳ１２１での判定結果がＮｏの場合は、ステップＳ１２４に分岐する。ステップＳ１２４では、複数個のＣＰＵが並列処理を行う処理回数Ｌ、処理順序ｋの設定を行い、続いて、処理対象ｂｊ要素の選定（ステップＳ１２５）を行う。ここで、ｂｊは、係数ベクトルｂのｊ番目の成分を表す。次に、ｂｊ要素が並列処理可能か否かの判定（ステップＳ１２６）を行い、Ｙｅｓの場合は、ステップＳ１２８に分岐する。ステップＳ１２６での判定結果がＮｏの場合は、ｂｊ要素の処理に必要な、関連する要素である関連ｂｉ要素が処理済みか否かの判定（ステップＳ１２７）を行い、ステップＳ１２７での判定結果がＮｏの場合は継続してチェックを行い、ステップＳ１２７での判定結果がＹｅｓの場合はステップＳ１２８に進む。ステップＳ１２８では、前進消去過程の計算を行い、続いて、ＣＰＵ処理フラグの設定（ステップＳ１２９）をし、前進消去過程終了の判定（ステップＳ１３０）を行う。ステップＳ１３０での判定結果がＮｏの場合はＣＰＵ処理フラグをゼロに設定（ステップＳ１３１）し、ステップＳ１２４に分岐する。ステップＳ１３０での判定結果がＹｅｓの場合は、前進消去過程の処理を終了し、後退代入過程１の処理に移る。
【００７０】
図１５−２に示すように、後退代入過程１では、まず、ＣＰＵ１か否かの判定（ステップＳ１３２）を行い、Ｙｅｓの場合は、フラグ類の初期化処理（ステップＳ１３３）を行い、Ｎｏの場合はスキップする。次に、処理対象ｘｉ群の設定（ステップＳ１３４）を行い、後退代入過程１の計算（ステップＳ１３５）を実行し、計算終了後に、ＣＰＵ処理フラグの設定（ステップＳ１３６）を行い、続いて、後退代入過程１終了の判定（ステップＳ１３７）を行う。ここで、ｘｉは解ｘのｉ番目の成分を表し、また、ステップＳ１３５において、ａｉｉは係数行列のｉ番目の対角成分、ｂｉは係数ベクトルのｉ番目の成分、
Ｃ（ｉ）＝１／ａｉｉである（図６を参照）。ステップＳ１３７での判定結果がＮｏの場合は継続してチェックを行うが、Ｙｅｓの場合は後退代入過程１を終了し、後退代入過程２に移る。
【００７１】
後退代入過程２では、まず、ＣＰＵ１か否かの判定（ステップＳ１３８）を行い、Ｙｅｓの場合にはフラグ類の初期化処理（ステップＳ１３９）を行い、次に、各ＣＰＵが並列処理できるか否かを示す並列処理フラグの作成（ステップＳ１４０）を行うが、Ｎｏの場合、ステップＳ１４１に分岐する。ステップＳ１４１では、処理回数Ｌ、処理順序ｋの設定を行い、処理対象ｘｉ要素の選定（ステップＳ１４２）をし、次に、ｘｉ要素が並列処理可能か否かの判定（ステップＳ１４３）を行う。ステップＳ１４３での判定結果がＮｏの場合は、ｘｉ要素の処理に必要な、関連する要素である関連ｘｊ要素が処理済みか否かの判定（ステップＳ１４４）を行い、ステップＳ１４４での判定結果がＮｏの場合は継続してチェックを行い、ステップＳ１４４での判定結果がＹｅｓの場合はステップＳ１４５に進む。ステップＳ１４３での判定結果がＹｅｓの場合は、ステップＳ１４５に分岐する。
【００７２】
ステップＳ１４５では、後退代入過程２の計算を行い、次に、ＣＰＵ処理フラグの設定（ステップＳ１４６）をし、最後に、後退代入過程２終了の判定（ステップＳ１４７）を行い、Ｎｏの場合はＣＰＵ処理フラグにゼロを設定（ステップＳ１４８）し、ステップＳ１４１に分岐する。ステップＳ１４７での判定結果がＹｅｓの場合は、後退代入過程２の処理を終了する。
【００７３】
図１６−１および図１６−２は、本実施の形態の前進消去過程における並列処理フラグ作成の処理を示すフロー図である。なお、図１６−２は、図１６−１に続くフロー図であり、‘４’で示す箇所で接続されている。図１６−１では、まず、並列処理フラグ作成対象の設定（ステップＳ１５０）を行い、続いて、ＣＰＵ１か否かの判定（ステップＳ１５１）を行い、Ｙｅｓの場合はＣＰＵ実行フラグ、ＣＰＵ参照フラグ、ＣＰＵ処理フラグ、並列処理フラグ作成の終了フラグ等、フラグ類の初期化処理（ステップＳ１５２）を行い、Ｎｏの場合はステップＳ１５３に分岐する。次に、処理要素の配列ｉと処理ＣＰＵ番号ｋｍ、ｋｎの初期値設定（ステップＳ１５３）を行う。次に、図１６−２では、前進消去の並列処理対象要素の計算（ステップＳ１５４）を行い、以降、各要素について並列処理が可能か否かの判定を行い、可能な場合はＣＰＵ実行フラグにＣＰＵ番号を設定し、不可能な場合は、処理終了を参照すべきＣＰＵ番号をＣＰＵ参照フラグに設定して、並列処理フラグの作成を行う。
【００７４】
まず、選定した要素の配列Ｑが既に選定した要素の配列Ｐと一致するか否かのチェックを行う。一致する場合は、並列処理が不可能であり、一致しない場合は、並列処理が可能と判定する。この処理は、ｍとｎのループから構成するが、ｍのループでは、並列処理対象要素を全て含み、ステップＳ１５５で、ｍのループにおける処理ＣＰＵ番号をカウントアップする。ｎのループは最初の要素は必ず含むが、それ以降の要素は、ｍ−１の要素までとする。これは、例えば、２番目の要素は１番目の要素と、３番目の要素は１番目、２番目の要素と、４番目の要素は１番目、２番目、３番目の要素と比較するためである。
【００７５】
まず、ステップＳ１５６で、ｎのループにおける処理ＣＰＵ番号をカウントアップする。ｋｎは先行して選定された要素を処理するＣＰＵ番号であり、ｋｍは先行して選定された要素に対し並列処理を行うＣＰＵ番号である。
【００７６】
次に、ｋｍが１か否かの判定（ステップＳ１５７）を行い、Ｙｅｓの場合は、並列処理対象の先頭要素であるため、無条件で並列処理可能として、ＣＰＵ実行フラグを設定し、ＣＰＵ参照フラグをクリア（ステップＳ１６２）し、ステップＳ１６１の次に分岐する（ｍのループの更新を行う。）。ステップＳ１５７でＮｏの場合は、Ｑ（ｍ）とＰ（ｎ）が一致するか否かの判定（ステップＳ１５９）を行い、Ｙｅｓの場合は並列処理が不可能であるため、ＣＰＵ参照フラグを設定し、ＣＰＵ実行フラグをクリア（ステップＳ１５９）するが、Ｎｏの場合は何も処理しない。そして、ｎのループが終了した後で、Ｑ（ｍ）と全Ｐ（ｎ）とが不一致か否かの判定（ステップＳ１６０）を行い、Ｙｅｓの場合は並列処理が可能であるため、ＣＰＵ実行フラグを設定し、ＣＰＵ参照フラグをクリア（ステップＳ１６１）する。ステップＳ１６０でＮｏの場合は何も処理しない。
【００７７】
次に、さらに並列処理が可能か否かの判定として、先行して選定した要素の配列Ｐとそれ以降に選定した要素の配列Ｐとが一致するか否かのチェックを行う。一致しない場合は、並列処理が可能であるが、一致する場合は並列処理が不可能であるため、それぞれに対応して、ＣＰＵ実行フラグ、ＣＰＵ参照フラグの設定を行う。
【００７８】
まず、ｎのループにおける処理ＣＰＵ番号を初期値設定（ステップＳ１６３）する。これらの処理は、ｍとｎのループで構成し、ｍのループについては、先頭の要素は無条件で並列処理可能であるため、２番目の要素から選定する、また、ｎのループについては、先頭の要素からｍ−１の要素までを選定する。これは、２番目の場合は１番目の要素と、３番目の要素の場合は１番目、２番目の要素と、４番目の場合は１番目、２番目、３番目の要素と比較するためである。
【００７９】
まず、ステップＳ１６４で処理ＣＰＵ番号ｋｎをカウントアップし、Ｐ（ｍ）とＰ（ｎ）とが一致するか否かの判定（ステップＳ１６５）を行い、一致する場合は並列処理が不可能なためＣＰＵ参照フラグを設定し、ＣＰＵ実行フラグをクリア（ステップＳ１６６）し、Ｎｏの場合は何も処理しない。ｍとｎのループの処理が終了すれば、全要素の処理が終了したか否かの判定（ステップＳ１６７）を行い、Ｎｏの場合は、配列ｉを並列処理するＣＰＵ台数分（ＣＰＵｍａｘ）だけ増加（ステップＳ１６８）させ、また、処理ＣＰＵ番号ｋｍ、ｋｎをクリア（ステップＳ１６９）して、ステップＳ１５４に分岐する。Ｙｅｓの場合は自ＣＰＵ処理フラグに、処理を実施したＣＰＵ番号を設定し（ステップＳ１７０）、ＣＰＵ１の判定（ステップＳ１７１）を行い、Ｙｅｓの場合は全ＣＰＵ処理フラグが正か否かの判定（ステップＳ１７２）を行う。ステップＳ１７２で、Ｎｏの場合は継続してチェックを行い、Ｙｅｓの場合は並列処理フラグ作成の終了フラグを設定（ステップＳ１７３）し、ＣＰＵ１の処理を終了する。ステップＳ１７１でＣＰＵ１以外の場合は、並列処理フラグ作成の終了フラグの判定（ステップＳ１７４）を行い、判定結果が、Ｎｏの場合は継続してチェックを行い、Ｙｅｓの場合は処理を終了する。
【００８０】
図１７−１および図１７−２は、本実施の形態の後退代入過程における並列処理フラグ作成の処理を示すフロー図である。なお、図１７−２は、図１７−１に続くフロー図であり、‘５’で示す箇所で接続されている。前進消去処理では、要素１から最大要素の方向に処理が進むが、後退代入処理の場合は、逆に、最大の要素から要素１の方向に処理が進む。これが両者の最大の差異である。
【００８１】
図１７−１では、まず、並列処理フラグ作成対象の設定（ステップＳ１５０）を行い、続いて、ＣＰＵ１か否かの判定（ステップＳ１５０）を行い、Ｙｅｓの場合はＣＰＵ実行フラグ、ＣＰＵ参照フラグ、ＣＰＵ処理フラグ、並列処理フラグ作成の終了フラグ等、フラグ類の初期化処理（ステップＳ１５２）を行い、Ｎｏの場合はステップ１５３に分岐する。次に、処理要素の配列ｉとＣＰＵ処理番号ｋｍ、ｋｎの初期値設定（ステップＳ１５２）を行う。次に、図１７−２では、後退代入の並列処理対象要素の計算（ステップＳ１５４）を行い、以降、各要素について並列処理が可能か否かの判定を行い、可能な場合はＣＰＵ実行フラグにＣＰＵ番号を設定し、不可能な場合は、処理終了を参照するべきＣＰＵ番号をＣＰＵ参照フラグに設定して、並列処理フラグの作成を行う。
【００８２】
まず、選定した要素の配列Ｑが既に選定した要素の配列Ｐと一致するか否かのチェックを行う。一致する場合は、並列処理が不可能であり、一致しない場合は、並列処理が可能と判定する。この処理は、ｍとｎのループから構成するが、ｍのループでは、並列処理対象要素を全て含み、ステップＳ１５５でｍのループにおける処理ＣＰＵ番号をカウントアップする。ｎのループは最初の要素は必ず含むが、それ以降の要素は、ｍ−１の要素までとする。これは、２番目の要素は１番目の要素と、３番目の要素は１番目、２番目の要素と、４番目の要素は１番目、２番目、３番目の要素と比較するためである。
【００８３】
まず、ステップＳ１５６で、ｎのループにおける処理ＣＰＵ番号をカウントアップする。ｋｎは先行して選定された要素を処理するＣＰＵ番号であり、ｋｍは先行して選定された要素に対し並列処理を行うＣＰＵ番号である。
【００８４】
次に、ｋｍが１か否かの判定（ステップＳ１５７）を行い、Ｙｅｓの場合は、並列処理対象の先頭要素であるため、無条件で並列処理可能として、ＣＰＵ実行フラグを設定し、ＣＰＵ参照フラグをクリア（ステップＳ１６２）し、ステップＳ１６２の次に分岐する（ｍのループの更新を行う。）。Ｎｏの場合は、ステップＳ１５７でＮｏの場合は、Ｐ（ｍ）とＱ（ｎ）とが一致する否かの判定（ステップＳ１５９）を行い、Ｙｅｓの場合は並列処理が不可能であるため、ＣＰＵ参照フラグを設定し、ＣＰＵ実行フラグをクリア（ステップ１００）するが、Ｎｏの場合は何も処理しない。そして、ｎのループが終了した後で、Ｐ（ｍ）と全Ｑ（ｎ）とが不一致か否かの判定（ステップＳ１６０）を行い、Ｙｅｓの場合は並列処理が可能であるため、ＣＰＵ実行フラグを設定し、ＣＰＵ参照フラグをクリア（ステップＳ１６１）する。ステップＳ１６０でＮｏの場合は何も処理しない。
【００８５】
次に、さらに並列処理が可能か否かの判定として、先行して選定した要素の配列Ｐとそれ以降に選定した要素の配列Ｐが一致するかのチェックを行う。一致しない場合は、並列処理が可能であるが、一致する場合は並列処理が不可能であるため、それぞれに対応して、ＣＰＵ実行フラグ、ＣＰＵ参照フラグの設定を行う。
【００８６】
まず、ｎのループにおける処理ＣＰＵ番号を初期値設定（ステップＳ１６３）する。これらの処理は、ｍとｎのループで構成し、ｍのループについては、先頭の要素は無条件で並列処理可能であるため、２番目の要素から選定する、また、ｎのループについては、先頭の要素からｍ−１の要素までを選定する。これは、２番目の場合は１番目の要素と、３番目の要素の場合は１番目、２番目の要素と、４番目の場合は１番目、２番目、３番目の要素と比較するためである。
【００８７】
まず、ステップＳ１６４で処理ＣＰＵ番号ｋｎをカウントアップし、Ｐ（ｍ）とＰ（ｎ）が一致するかの判定（ステップＳ１６５）を行い、一致する場合は並列処理が不可能なためＣＰＵ参照フラグを設定し、ＣＰＵ実行フラグをクリア（ステップＳ１６６）し、Ｎｏの場合は何も処理しない。ｍとｎのループの処理が終了すれば、全要素の処理が終了したか否かの判定（ステップＳ１６７）を行い、Ｎｏの場合は、配列ｉを並列処理するＣＰＵ台数分（ＣＰＵｍａｘ）だけ減少（ステップＳ１６８）させ、また、処理ＣＰＵ番号ｋｍ、ｋｎをクリア（ステップＳ１６９）して、ステップＳ１５４に分岐する。Ｙｅｓの場合は自ＣＰＵ処理フラグに自ＣＰＵ番号を設定（ステップＳ１７０）し、ＣＰＵ１か否かの判定（ステップＳ１７１）を行い、Ｙｅｓの場合は全ＣＰＵ処理フラグが正か否かの判定（ステップＳ１７２）を行う。ステップＳ７１２で、Ｎｏの場合は継続してチェックし、Ｙｅｓの場合は並列処理フラグ作成の終了フラグを設定（ステップＳ１７３）し、ＣＰＵ１の処理を終了する。ステップＳ１７１でＮｏの場合は、並列処理フラグ作成の終了フラグが正か否かの判定（ステップＳ１７４）を行い、判定結果が、Ｎｏの場合は継続してチェックを行い、Ｙｅｓの場合は処理を終了する。
【００８８】
実施の形態１では、前進消去、後退代入処理の並列処理の実行効率を上げるためのノード順序付け方法を説明したが、この実施の形態４では、そのノード順序付けを適用した場合の前進消去、後退代入処理の並列処理の実現方法を説明した。このように、実施の形態１と実施の形態４とを組合せることにより、連立一次方程式求解の並列処理を実現できると共に、高速処理が可能になるという効果がある。
【００８９】
次に、動作について説明する。まず、前進消去過程の並列処理について、説明する。複数のＣＰＵで並列処理を行う場合、処理前に、ｂｉ要素の並列処理が可能であるか否かのチェックを行い、並列処理フラグ（ＣＰＵ実行フラグ、ＣＰＵ参照フラグ）を複数ＣＰＵで並列に作成し、各ＣＰＵの処理するｂｉ、ｂｊ要素の決定、１回毎の並列計算ステップにおける各ＣＰＵの処理が終了したことの検出方法、また、全行の処理が終了したことの検出方法を定める必要がある。
（ａ）並列処理フラグ（ＣＰＵ実行フラグ、ＣＰＵ参照フラグ）の作成
（１）各ＣＰＵは、各ＣＰＵが担当する自分の並列処理フラグ作成対象の設定を行う。
（２）ＣＰＵ１は、まず、全ＣＰＵのＣＰＵ実行フラグ、ＣＰＵ参照フラグを「０」で初期化する。
（３）次に、各ＣＰＵは、当該並列処理における並列処理対象要素について、後段のＱ（ｍ）と前段の全Ｐ（ｎ）の値とが一致するか否かチェックする。一致する場合は、並列処理が不可になるのでＣＰＵ参照フラグを設定し、全て一致しない場合は並列処理が可能になるので、ＣＰＵ実行フラグを設定する。
・並列処理対象の最初の要素は、無条件で並列処理可能とし、当該ＣＰＵのＣＰＵ実行フラグに当該ＣＰＵ番号を設定する。
・後段の要素と先行する全要素のチェックの結果、一致する場合は、当該ＣＰＵのＣＰＵ参照フラグに、参照すべき一致した要素のＰ（ｎ）を担当するＣＰＵ番号を設定する。
・後段の要素と先行する全要素のチェックの結果、全て一致しない場合は、当該要素Ｑ（ｍ）を担当するＣＰＵのＣＰＵ実行フラグに当該ＣＰＵ番号を設定する。
（４）次に、各ＣＰＵは、当該並列処理における並列処理対象要素について、後段のＰ（ｍ）と前段の全Ｐ（ｎ）の値とが一致するか否かチェックする。一致する場合は、並列処理が不可になるのでＣＰＵ参照フラグを設定する。全て一致しない場合は何も処理しない。
・一致する場合は、当該ＣＰＵのＣＰＵ参照フラグに、参照すべき一致した要素のＰ（ｎ）を担当するＣＰＵ番号を設定する。
・一致しない場合は、何もしない。
（５）各ＣＰＵは、自分の処理が終了すれば、自ＣＰＵ処理フラグに自分のＣＰＵ番号を設定する。
（６）ＣＰＵ１は、全てのＣＰＵの処理が終了したか否かをＣＰＵ終了フラグでチェックし、終了していれば、並列処理フラグ作成の終了フラグを設定し、処理を終了する。
（７）ＣＰＵ１以外のＣＰＵも、並列処理フラグ作成の終了フラグが設定されている場合は、処理を終了する。
（ｂ）処理対象ｂｉ、ｂｊ要素の決定
（１）各ＣＰＵが処理するｂｉ、ｂｊ要素を下記の（４）式により算出する。また、図１８は、前進消去過程の並列処理において、４台のＣＰＵに処理を割り振り各種フラグで管理する様子を示す図である。
ｋ＝（Ｌ−１）＊ＣＰＵｍａｘ＋ＣＰＵｉ ・・・（４）
ｊ＝Ｐ（ｋ）
ｉ＝Ｑ（ｋ）
ただし、
Ｌ：各ＣＰＵの計算回数（ＣＰＵ１が初期化。初期値は１）
ＣＰＵｍａｘ：並列処理するＣＰＵ台数
ＣＰＵｉ：ＣＰＵ番号（ＣＰＵ１＝１、・・・、ＣＰＵｎ＝ＣＰＵｍａｘ）
（ｃ）ＣＰＵ処理フラグの管理
ＣＰＵ１が各ＣＰＵの計算回数Ｌの更新を行うためには、各ＣＰＵの処理が終了したことを確認する必要がある。これをＣＰＵ処理フラグと定義する。
（１）初期化
ＣＰＵ１が、全ＣＰＵのＣＰＵ処理フラグを、０で初期化する。
（２）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の処理が終了した時点で、ＣＰＵ処理フラグに自ＣＰＵ番号を書き込む。
（３）計算回数Ｌのカウントアップ
ＣＰＵ１は、全ＣＰＵのＣＰＵ処理フラグが正になった時点で、Ｌを１だけ、カウントアップし、全ＣＰＵのＣＰＵ処理フラグをリセットする。
（ｄ）前進消去過程終了フラグの管理
前進消去過程の処理終了は、各ＣＰＵが行う。
（１）初期化
ＣＰＵ１が、前進消去過程終了フラグを、０で初期化する。
（２）最終行の検出
各ＣＰＵが処理するｂｊ要素の行番号が、行サイズｎｍａｘと一致した場合、最
終行の処理をしたと判断し、検出したＣＰＵは、前進消去過程終了フラグに自ＣＰＵ番号をセットする。
（３）前進消去過程の終了
各ＣＰＵは、前進消去過程終了フラグが正の場合、前進消去過程の処理が終了したと判断し、次の後退代入過程１の処理に入る。
（ｅ）前進消去過程の並列処理手順
（１）各ＣＰＵが担当する並列処理フラグ作成対象を設定する。
（２）ＣＰＵ１が、各ＣＰＵのＣＰＵ実行フラグ、ＣＰＵ参照フラグ、ＣＰＵ処理フラグ、前進消去過程終了フラグを初期化する。
（３）各ＣＰＵが、全てのＣＰＵ実行フラグ、ＣＰＵ参照フラグを並列に作成する。
（４）各ＣＰＵが、処理対象ｂｉ、ｂｊ要素を決定する。
（５）各ＣＰＵが、ＣＰＵ実行フラグをチェックする。
・自分のＣＰＵ番号と一致する場合は、ｂｊ要素の計算を行い、ＣＰＵ処理フラグをセットする。なお、ｂｉ要素と掛け算となるＤ要素がゼロの場合は、その処理をスキップする。
・自分のＣＰＵ番号と一致しない場合は、ＣＰＵ参照フラグが示すＣＰＵ番号について、そのＣＰＵ処理フラグをチェックする。
（ｉ）ＣＰＵ処理フラグが正の場合は、ｂｊ要素の処理を行い、ＣＰＵ処理フラグをセットする。
（ｉｉ）ＣＰＵ処理フラグが正でない場合は、継続チェックを行う（先行ＣＰＵの計算終了待ち）。
（６）ＣＰＵ１が、全ＣＰＵ処理フラグが正であることを確認し、Ｌを１アップし、
全ＣＰＵのＣＰＵ処理フラグをリセットし、（４）に戻る。
（７）各ＣＰＵは、自分が最終行を処理した場合、前進消去過程終了フラグをセット
する。
（８）各ＣＰＵは、前進消去過程終了フラグが正の場合、前進消去を終了し、次の後
退代入過程１に進む。
【００９０】
次に、後退代入過程１の並列処理について、説明する。後退代入過程１の処理は、各ＣＰＵが全処理を分担して、並列処理することができる。複数のＣＰＵで並列処理を行う場合、各ＣＰＵの処理するｘｊ要素の決定、各ＣＰＵの処理が終了したことの検出方法、また、全行の処理が終了したことの検出方法を決める必要がある。
（ａ）処理対象ｘｉの決定
（１）各ＣＰＵが処理するｘｉ要素を下記の式により算出する。
・各ＣＰＵの平均処理量
ｋ０＝（ｎｍａｘ／ＣＰＵｍａｘ）の整数値
・余り
ｋ１＝ｎｍａｘ−ｋ０・ＣＰＵｍａｘ
・ＣＰＵ１の処理量
ｉ＝１〜ｋ０＋ｋ１
・ＣＰＵ２〜ＣＰＵｍａｘの処理量
ｉ＝（ｋ０＋ｋ１）＋（ＣＰＵｉ−２）＊ｋ０＋１
〜（ｋ０＋ｋ１）＋（ＣＰＵｉ−１）＊ｋ０
（ｂ）ＣＰＵ処理フラグ、後退代入過程１終了フラグの管理
後退代入過程１の処理が終了したことをチェックするためには、各ＣＰＵの処理が終了したことを確認する必要がある。また、図１９は、後退代入過程１の並列処理において、４台のＣＰＵに処理を割り振りＣＰＵ処理フラグで管理する様子を示す図である。
（１）初期化
ＣＰＵ１が、全ＣＰＵのＣＰＵ処理フラグ、後退代入過程１終了フラグを、０で初期化する。
（２）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の処理が終了した時点で、ＣＰＵ処理フラグに自ＣＰＵ番号を書き込む。
（３）後退代入過程１終了フラグの設定
ＣＰＵ１は、自分の処理が終了した時点に、他ＣＰＵのＣＰＵ処理フラグが正になったことを検出し、後退代入過程１終了フラグをセットする。
（ｃ）後退代入過程１の並列処理手順
（１）初期化
ＣＰＵ１が、全ＣＰＵのＣＰＵ処理フラグ、後退代入過程１終了フラグを、０で初期化する。
（２）処理対象ｘｉの決定
各ＣＰＵが、自分が担当する処理対象ｘｉを計算する。
（３）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の処理が終了した時点で、ＣＰＵ処理フラグに自ＣＰＵ番号を書き込む。
（４）後退代入過程１終了フラグの設定
ＣＰＵ１は、自分の処理が終了した時点で、他ＣＰＵのＣＰＵ処理フラグが正になっていることを検出し、後退代入過程１終了フラグをセットする。
（５）各ＣＰＵは、後退代入過程１終了フラグが正の場合、後退代入過程１の処理が終了したことを認識し、次の後退代入過程２の処理に進む。
【００９１】
最後に、後退代入過程２の並列処理について、説明する。複数のＣＰＵで並列処理を行う場合、処理前に、ｘｉ、ｘｊ要素の並列処理が可能であるか否かのチェックを行い、並列処理フラグ（ＣＰＵ実行フラグ、ＣＰＵ参照フラグ）を複数ＣＰＵで並列に作成し、各ＣＰＵの処理するｘｉ、ｘｊ要素の決定、１回毎の並列計算ステップにおける各ＣＰＵの処理が終了したことの検出方法、また、全行の処理が終了したことの検出方法を定める必要がある。
（ａ）並列処理フラグ（ＣＰＵ実行フラグ、ＣＰＵ参照フラグ）の作成
（１）各ＣＰＵが自分の担当する並列処理フラグ作成の対象要素を設定する。
（２）ＣＰＵ１は、まず、全ＣＰＵのＣＰＵ実行フラグ、ＣＰＵ参照フラグを「０」で初期化する。
（３）次に、各ＣＰＵは、今回の並列処理対象要素について、後段のＰ（ｍ）と前段の全Ｑ（ｎ）の値とが一致するか否かチェックする。一致する場合は、並列処理が不可になるのでＣＰＵ参照フラグを設定し、全て一致しない場合は並列処理が可能になるので、ＣＰＵ実行フラグを設定する。
・並列処理対象の最初の要素は、無条件で並列処理可能とし、当該ＣＰＵのＣＰＵ実行フラグに当該ＣＰＵ番号を設定する。
・後段の要素と先行する全要素のチェックの結果、一致する場合は、当該ＣＰＵのＣＰＵ参照フラグに、参照すべき一致した要素のＱ（ｎ）を担当するＣＰＵ番号を設定する。
・後段の要素と先行する全要素のチェックの結果、全て一致しない場合は、当該要素Ｐ（ｍ）を担当するＣＰＵのＣＰＵ実行フラグに当該ＣＰＵ番号を設定する。
（４）次に、各ＣＰＵは、今回の並列処理対象要素について、後段のＰ（ｍ）と前段の全Ｐ（ｎ）の値とが一致するかチェックする。一致する場合は、並列処理が不可になるのでＣＰＵ参照フラグを設定する。全て一致しない場合は何も処理しない。
・一致する場合は、当該ＣＰＵのＣＰＵ参照フラグに、参照すべき一致した要素のＰ（ｎ）を担当するＣＰＵ番号を設定する。
・一致しない場合は、何もしない。
（５）各ＣＰＵは、自分の担当する処理が終了すれば、自ＣＰＵ処理フラグに自分のＣＰＵ番号を設定する。
（６）ＣＰＵ１は、全てのＣＰＵの処理が終了したか否かを、ＣＰＵ処理フラグから判定し、終了している場合は、並列処理フラグ作成の終了フラグを設定し、処理を終了する。
（７）ＣＰＵ１以外のＣＰＵは、並列処理フラグ作成の終了フラグをチェックし、設定済みの場合は処理を終了する。
（ｂ）処理対象ｘｉ、ｘｊ要素の決定
（１）各ＣＰＵが処理するｘｉを下記の（５）式により算出する。また、図２０は、後退代入過程２の並列処理において、４台のＣＰＵに処理を割り振り各種フラグで管理する様子を示す図である。
ｋ＝ｎｍａｘ−（Ｌ−１）・ＣＰＵmax−ＣＰＵｉ＋１ ・・・（５）
ｉ＝Ｑ（ｋ）
ｊ＝Ｐ（ｋ）
ただし、
ｎｍａｘ：ｘｉの最大要素数
Ｌ：各ＣＰＵの計算回数（ＣＰＵ１が初期化。初期値は１）
ＣＰＵｍａｘ：並列処理するＣＰＵ台数
ＣＰＵｉ：ＣＰＵ番号（ＣＰＵ１＝１、・・・、ＣＰＵｎ＝ＣＰＵｍａｘ）
（ｃ）ＣＰＵ処理フラグの管理
ＣＰＵ１が各ＣＰＵの計算回数Ｌの更新を行うためには、各ＣＰＵの処理が終了したことを確認する必要がある。これをＣＰＵ処理フラグと定義する。
（１）初期化
ＣＰＵ１が、全ＣＰＵのＣＰＵ処理フラグを、０で初期化する。
（２）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の処理が終了した時点で、ＣＰＵ処理フラグに自ＣＰＵ番号を書き込む。
（３）計算回数Ｌのカウントアップ
ＣＰＵ１は、全ＣＰＵのＣＰＵ処理フラグが正になった時点で、Ｌを１だけ、
カウントアップし、全ＣＰＵのＣＰＵ処理フラグをリセットする。
（ｄ）後退代入過程２終了フラグの管理
後退代入過程２の処理終了は、各ＣＰＵが行う。
（１）初期化
ＣＰＵ１が、後退代入過程２終了フラグを、０で初期化する。
（２）最終行の検出
各ＣＰＵが処理するｘｉの行番号が、「１」と一致した場合、最終行の処理をしたと判断し、検出したＣＰＵは、後退代入過程２終了フラグに自ＣＰＵ番号をセットする。
（３）後退代入過程２の終了
各ＣＰＵは、後退代入過程２終了フラグが正の場合、後退代入の処理が終了したと判断し、全処理の終了とする。
（ｅ）後退代入過程２の並列処理手順
（１）各ＣＰＵは、自分の担当する並列処理フラグ作成の対象要素を設定する。
（２）ＣＰＵ１が、各ＣＰＵのＣＰＵ実行フラグ、ＣＰＵ参照フラグ、ＣＰＵ処理フラグ、後退代入過程２終了フラグを初期化する。
（３）各ＣＰＵが、全てのＣＰＵ実行フラグ、ＣＰＵ参照フラグを並列に作成する。
（４）各ＣＰＵが、処理対象ｘｉ、ｘｊ要素を決定する。
（５）各ＣＰＵが、ＣＰＵ実行フラグをチェックする。
・自分のＣＰＵ番号と一致する場合は、ｘｉ要素の計算を行い、ＣＰＵ処理フラグをセットする。なお、ｘｊ要素と掛け算となるＤ要素がゼロの場合は、その処理をスキップする。
・自分のＣＰＵ番号と一致しない場合は、ＣＰＵ参照フラグが示すＣＰＵ番号について、そのＣＰＵ処理フラグをチェックする。
（ｉ）ＣＰＵ処理フラグが正の場合は、ｘｉ要素の処理を行い、ＣＰＵ処理フラ
グをセットする。
（ｉｉ）ＣＰＵ処理フラグが正でない場合は、継続チェックを行う（先行ＣＰＵの処理終了待ち）。
（６）ＣＰＵ１が、全ＣＰＵ処理フラグが正であることを確認し、Ｌを１カウントアップし、全ＣＰＵのＣＰＵ処理フラグをリセットし、（４）に戻る。
（７）各ＣＰＵは、自分が１行目を処理した場合、後退代入過程２終了フラグをセッ
トする。
（８）各ＣＰＵは、後退代入過程２終了フラグが正の場合、後退代入過程２を終了す
る。
【００９２】
本実施の形態によれば、実施の形態１〜３のいずれかのノード順序付けの結果に基づき、処理の実施前に、前進消去・後退代入処理の並列処理可能の可否を判定し、可能な場合はＣＰＵ実行フラグをセットし、不可能な場合はＣＰＵ参照フラグに参照すべきＣＰＵ番号をセットし、前進消去・後退代入処理においては、ＣＰＵ実行フラグがセットされている場合は並列処理を行い、セットされていない場合は、ＣＰＵ参照フラグより、参照すべきＣＰＵ番号を抽出し、そのＣＰＵの処理が終了したことを確認して、その後に当該ＣＰＵの処理を行うようにしたので、従来はすべて直列に処理していた前進消去・後退代入処理の並列処理を実現すると共に、並列処理の実行効率を向上させることができるという効果がある。また、図２に示すような対称型マルチＣＰＵ構成の計算機に基づき、本実施の形態にかかる連立一次方程式の並列求解方法を用いることにより、連立一次方程式の解を並列求解するための並列求解装置を構成することができる。
【図面の簡単な説明】
【００９３】
【図１】実施の形態１が適用される訓練シミュレータの構成を示す構成図である。
【図２】実施の形態１にかかる連立一次方程式の並列求解に利用される計算機構成の一例を示す図である。
【図３】実施の形態１において、系統摸擬サーバ群に実装し、系統シミュレーションを行う動態安定度計算の処理例を示すフロー図である。
【図４】非特許文献２に記載の系統例を示す図である。
【図５】図４の系統例の回路網方程式（連立一次方程式）を示す図である。
【図６】三角分解の基本的な処理を示すフロー図である。
【図７】三角分解結果の各種データを保存するテーブルの構造を示す図である。
【図８】前進消去・後退代入処理を示す処理フロー図である。
【図９】前進消去処理における並列処理の問題点を示す図である。
【図１０】後退代入処理における並列処理の問題点を示す図である。
【図１１−１】実施の形態１のノード順序付け方法を示すフロー図である。
【図１１−２】図１１−１に続くフロー図である。
【図１２】図１１−２における新規非零要素発生のシミュレーションの並列処理を示すフロー図である。
【図１３−１】実施の形態１のノード順序付けの効果を説明するための図である。
【図１３−２】実施の形態１のノード順序付けの効果を説明するための図である。
【図１３−３】実施の形態１のノード順序付けの効果を説明するための図である。
【図１３−４】実施の形態１のノード順序付けの効果を説明するための図である。
【図１４−１】実施の形態３のノード順序付け方法を示すフロー図である。
【図１４−２】図１４−１に続くフロー図である。
【図１５−１】実施の形態４における連立一次方程式の並列求解方法を示すフロー図である。
【図１５−２】図１５−１に続くフロー図である。
【図１６−１】実施の形態４の後退代入過程における並列処理フラグ作成の処理を示すフロー図である。
【図１６−２】図１６−１に続くフロー図である。
【図１７−１】実施の形態４の後退代入過程における並列処理フラグ作成の処理を示すフロー図である。
【図１７−２】図１７−１に続くフロー図である。
【図１８】前進消去過程の並列処理において、４台のＣＰＵに処理を割り振り各種フラグで管理する様子を示す図である。
【図１９】後退代入過程１の並列処理において、４台のＣＰＵに処理を割り振りＣＰＵ処理フラグで管理する様子を示す図である。
【図２０】後退代入過程２の並列処理において、４台のＣＰＵに処理を割り振り各種フラグで管理する様子を示す図である。
【図２１−１】非特許文献１に記載の単純なネットワークを示す図である。
【図２１−２】非特許文献１に記載のツリー構造の処理過程を示す図である。
【図２２】非特許文献１に記載のノード順序付けアルゴリズムを示すフロー図である。
【符号の説明】
【００９４】
１ 訓練管理サーバ群
２ 系統摸擬サーバ群
３ 自動化模擬サーバ群
４ トレーナ卓
５ トレーニ卓
６ 大画面系統盤
７ システムＬＡＮ
８ ＣＰＵ１
９ ＣＰＵ２
１０ ＣＰＵ３
１１ ＣＰＵｎ
１２ 共有メモリ
【技術分野】
【０００１】
本発明は、電力系統の計算に現れる連立一次方程式の並列計算に関し、特に、並列計算を高速に処理できるノードの順序付け方法と、前進消去・後退代入処理の並列計算に関する。
【背景技術】
【０００２】
従来、連立一次方程式の解法として、三角分解による直接解法が知られており、この手法を用いた場合に、連立一次方程式の求解は、（１）ノードの順序付け、（２）係数行列の三角分解（ＬＤＵ分解）、（３）前進／後退代入計算による解の算出、の３つの処理を行うことになる。また、連立一次方程式の高速な求解のために並列計算が利用されている。並列計算では、複数のＣＰＵに処理を分散して計算を行い、また、ＣＰＵ間のデータの授受は通信処理を経て行っている。
【０００３】
従来の連立一次方程式の並列計算は、前進／後退代入処理のツリー作成に基づいており、その際、ノードの順序付け方法が重要になる。従来の方法では、Ｔｉｎｎｅｙ２法に基づき、ノードの消去により発生するｆｉｌｌ−ｉｎ（非零要素）の数が少ないものから選択し、あるステージ（並列処理での各ステップをステージという）で接続ブランチ数が２本以下のノードが消去される場合には、当該ステージでは接続ブランチ数が３本以上のノードは消去せず、かつ、あるノードから２ブランチまでの範囲に、同じステージで消去されるノードがある場合、当該ノードは消去しないとしている（非特許文献１を参照）。
【０００４】
【非特許文献１】永田真幸、内田直之著 「過度安定度計算高速化のための系統計算の並列処理アルゴリズムの開発」 電気学会論文誌Ｂ、１２０巻２号、平成１２年
【非特許文献２】田岡久雄、阿部茂著「パイプライン処理に適した連立一次方程式の高速求解法とその電力系統解析への応用」電気学会論文誌Ｂ、１０５巻５号、昭和６０年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来の連立一次方程式の並列計算のためのノード順序付け方法は、ノード消去により発生するｆｉｌｌ−ｉｎの数が少ないものから選択し、あるステージで接続ブランチ数が２本以下のノードを消去する場合には、当該ステージでは接続ブランチ数が３本以上のノードは消去せず、かつ、あるノードから２ブランチまでの範囲に、同じステージで消去されるノードがある場合、当該ノードは消去しないとしており、また、ノード順序付けの結果として得られた処理を各ＣＰＵに割当てるために、通信回数の削減とＣＰＵ間での計算処理の均等化のバランスをとるようにしている。
【０００６】
従来の方法は、上記の通りノードの順序付けにＴｉｎｎｅｙ２法を適用しており、放射状系統に対しては最適な順序付けになるが、ループ状系統に対しては最適な順序付けにはならず、ｆｉｌｌ−ｉｎが多くなり処理性能が悪化すること、また、並列計算を各ＣＰＵへ割当てるための処理に時間が掛り、並列処理のオーバヘッドが大きくなること、また、並列処理の効果をＣＰＵ間通信量と各ＣＰＵの処理量のバランスを考慮して決定するため、ＣＰＵ資源の無駄が発生する等の問題点があった。このような問題点と、さらに、オフラインで実施される系統解析業務以外の訓練シミュレータ、オンラインの給電自動化システム等への適用にはリアルタイム性能が要求されることから、従来の方法はこの分野には適用が困難であるという問題点があった。
【０００７】
本発明は、上記に鑑みてなされたものであって、大規模系統の回路網計算である連立一次方程式の求解を実時間性能で実行できる連立一次方程式の並列計算用のノード順序付け方法および連立一次方程式の並列求解方法を得ることを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するために、本発明にかかるノード順序付け方法は、複数個のＣＰＵと、前記各ＣＰＵが共通にアクセス可能な共有メモリと、を有する対称型マルチＣＰＵ構成の並列計算装置を用い、係数行列の三角分解、前進消去処理、および後退代入処理に基づいて電力系統の解析における連立一次方程式の解を並列計算する際に使用され、前記係数行列の構造ならびに前記前進消去処理および前記後退代入処理の手順を、ノードおよびノード間を接続するブランチからなるツリーで表現するときのノード順序付け方法であって、前記ツリーにおけるループを含まない系統部分である放射状系統部分に属するノードについてのノード順序付けを行う第１のステップと、前記ツリーにおける放射状系統部分以外の系統部分であるループ状系統部分に属するノードについてのノード順序付けを行う第２のステップと、を含み、前記第１のステップにおいては、最初に順序付けするノードはそのノードに接続されているブランチ数が最小のノードの中から任意に選択し、以降はノード順序付け候補のノードのうち各ノードに接続されているブランチ数が少ないノードから順に選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行い、前記第２のステップにおいては、前記複数個のＣＰＵを用いて前記前進消去処理におけるノードの縮約時に発生する新規非零要素発生数のシミュレーションを並列処理して実施し、前記シミュレーションにより得られた前記新規非零要素発生数の少ないノードから選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行うことを特徴とする。
【発明の効果】
【０００９】
この発明にかかるノード順序付け方法によれば、前進消去・後退代入処理における並列処理の実行効率を向上させて、処理性能を高速化できるという効果があり、大規模系統の回路網方程式（連立一次方程式）を実時間性能で実行することが可能になるという効果がある。
【発明を実施するための最良の形態】
【００１０】
以下に、本発明にかかる連立一次方程式の並列求解方法およびノード順序付け方法の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００１１】
実施の形態１．
図１は、本実施の形態が適用される訓練シミュレータの構成を示す構成図である。図１では、まず、訓練を実施するための訓練の問題となる系統構成状態、発電機・負荷条件、および事故発生条件等からなる訓練シナリオを、トレーナが訓練管理サーバ群１、トレーナ卓４を使用して作成し、登録する。次に、訓練実施時には、トレーナがトレーナ卓４から登録した訓練シナリオを選択して、実時間で実行するが、それに伴い、系統摸擬サーバ群２で系統シミュレーションが実行されて、その計算結果がトレーナ卓４、トレーニ卓５、および大画面系統盤６に表示される。トレーニ（被訓練者）は自動化摸擬サーバ群３、トレーニ卓５、大画面系統盤６を使用して、事故発生状況を確認、把握して、事故復旧操作のための復旧指令、復旧操作等を行い、停電している負荷の復旧等を行う。一方、訓練実施中の系統シミュレーションは、系統摸擬サーバ群２で実行されるが、本実施の形態を適用した系統の静的、動的特性をシミュレーションするソフトウェアは、この系統摸擬サーバ群２に実装され、動作する。訓練管理サーバ群１、系統摸擬サーバ群２、自動化摸擬サーバ群３間の情報の送受信、また、トレーナ卓４、トレーニ卓５、大画面系統盤６へのデータ送信は、システムＬＡＮ７を介して行う。
【００１２】
図２は、本実施の形態にかかる連立一次方程式の並列求解に利用される計算機構成の一例を示す図である。図２に示すように、本実施の形態における計算機は、例えば、対称型マルチＣＰＵ構成の計算機であり、複数のＣＰＵであるＣＰＵ１（８）、ＣＰＵ２（９）、ＣＰＵ３（１０）、・・・、ＣＰＵｎ（１１）と、各ＣＰＵが共通にアクセス可能な共有メモリ１２と、を備えて構成される。ここで、ｎは２以上の任意の整数である。なお、各ＣＰＵは、キャッシュメモリ、ローカルメモリ、および外部記憶装置を実装しており、システムＬＡＮ７と接続している。
【００１３】
図３は、系統摸擬サーバ群２に実装し、系統シミュレーションを行う動態安定度計算の処理例を示すフロー図である。動態安定度計算は、積分刻み毎（通常１０ｍｓｅｃ）に回路網方程式の求解と発電機の微分方程式の求解を交互に行い、電力系統の母線電圧、位相角、周波数、有効電力、無効電力、および発電機の内部位相角等を計算する。
【００１４】
図３においては、まず、初期処理として、計算時刻の初期化（ステップＳ１３）とＹ行列の作成、三角分解（ステップＳ１４）の処理を順次行う。ここで、Ｙ行列は回路網方程式の係数行列である。次に、回路網方程式の求解を行うが、まず、系統構成変化の有無を判定し（ステップＳ１５）、変化がない場合にはステップＳ１７に分岐する。変化がある場合は、Ｙ行列の修正、三角分解（ステップＳ１６）を行い、続いて、回路網方程式の電流項である発電機の等価電流源の計算（ステップＳ１７）と非線形負荷の等価電流源の計算（ステップＳ１８）とを行い、ステップＳ１６、Ｓ１７、Ｓ１８の結果を用いて回路網方程式の求解（ステップＳ１９）を行い、母線電圧を得る。そして、計算結果である回路網の母線電圧（Ｖ）収束の判定（ステップＳ２０）を行い、未収束の場合は、ステップＳ１８に分岐し、計算結果の母線電圧を使用して非線形負荷の等価電流源の計算（ステップ１８）を行い、回路網方程式の求解（ステップＳ１９）を繰返す。回路網方程式の求解が収束すれば、次に、発電機の微分方程式の求解を行う。
【００１５】
まず、発電機の動揺方程式の求解（ステップＳ２１）を行い、発電機内部位相角を算出し、次に発電機のＡＶＲ（自動電圧調整装置）、ガバナ等の制御系と発電機の電機子回路等について、発電機微分方程式の求解（ステップＳ２２）を行い、発電機内部電圧等を算出し、その発電機の内部電圧（Ｖ）収束（ステップＳ２３）の判定を行う。未収束の場合は、ステップＳ１７に分岐し、回路網方程式の求解と発電機微分方程式の求解を繰返す。回路網の電圧と発電機の内部電圧が収束した場合は、動態安定度計算の計算時刻更新（ステップＳ２４）を行い、さらに、計算終了（ステップＳ２５）の判定を行い、計算終了時間に至っていない場合は、ステップＳ１５に分岐し、回路網方程式の求解と発電機微分方程式の求解を繰返す。計算終了時間に至っている場合は、処理を終了する。本実施の形態の連立一次方程式の並列計算方法は、回路網方程式の求解（ステップＳ１９）を高速に処理するために適用されるものである。
【００１６】
次に、本実施の形態と従来の技術との相違を明確にするために、非特許文献１に記載の従来の系統計算の並列処理アルゴリズムの説明を行う。
【００１７】
従来の方法においても、計算機として、並列計算機（マルチＣＰＵ）を想定しており、ＣＰＵ間のデータ授受は通信処理により行うことを想定している。また、連立一次方程式の解法として、三角分解による直接解法を用いている。本手法を用いた場合、
ｙ＝Ａ・ｘ ・・・（１）
という連立一次方程式の求解を以下の３つの処理で行うことになる。
（１）ノードの順序付け
（２）係数行列Ａの三角分解（ＬＤＵ分解）
（３）前進／後退代入計算によるｘの算出
【００１８】
安定度計算は、系統計算（回路網計算）と発電機微分方程式求解から構成され、系統計算が全体の約４割を占め、その内、前進／後退代入計算が約６割を占め、かつ、多数回の計算が行われる。また、三角分解と前進／後退代入の処理は、ノードの順序付けが決まれば自動的に決定されるので、ノードの順序付けをどのように行うかが逐次処理での直接法高速化の鍵となる。連立一次方程式の直接解法における前進代入処理は、
ｘｊ＝ｘｊ＋ｘｉ・Ｄｉｊ ・・・（２）
という計算の繰返し処理であり、（２）式は、ノードｉとノードｊとを結ぶブランチＤｉｊを消去して、ノードｊの値を変更するという処理である（（２）式のＤｉｊは、三角分解（ＬＤＵ分解）における対角要素である。）。あるノードｉについてブランチＤｉｊを全てのｊについて消去すれば、ノードｉの値ｘｉは以後の処理には必要でなくなる。これはノードｉの消去に対応する。後退代入計算も同様であり、例えば、図２１−１の単純なネットワークの場合には、（２）式の処理を前進／後退代入それぞれについて、６回繰返すことになる。なお、図中の点線のブランチは三角分解の結果生じるｆｉｌｌ−ｉｎ（三角分解により新たに発生する非零要素）に対応する。
【００１９】
前進／後退代入計算の処理は、図２１−２のようにツリー構造の処理過程として表すことができる。図２１−２の横向きの矢印は前進代入でのノードの消去を表している。また、図２１−２での矢印の向き（上から下）は前進代入での処理の流れであり、後退代入の場合はツリーの根から葉の方へ（下から上へ）、ツリーをたどる処理となる。
【００２０】
図中、四角で囲っている箇所は、ノードが複数データを持つことを意味している。例えば、ノード１を消去した場合、ノード３とノード５の両方の値が変わることになるが、ノード１から見てノード番号が近い方のノード３に渡す。そのためノード３は自分自身のデータとノード５の値を更新するためのデータを持つことになる。この表現法により、ノード間をどのようなデータが移動していくかを容易に把握できる。
【００２１】
ここで注意すべきは、ノード１の消去とノード２の消去の処理は順番を入れ替えても、あるいは同時に並列に処理しても計算結果に影響を与えないことである。なぜならば、これらの計算は互いに無関係に行うことができる（依存関係がない）からである。つまり、ツリーにおいて並んでいる横向きの矢印（ノードの消去）同士は並列に実行できることになる。したがって、ノードの消去を一つの処理単位として考えると、図２１−２の例の前進代入計算は、逐次処理では４ステップの処理であるのに対し、並列処理では３ステップの処理で済むことになる。以下、並列処理での各ステップ（複数のノード同時消去）をステージと呼ぶ。
【００２２】
図２１−２のようなツリーを用いた前進／後退代入処理の表現は、これまでも提案されているが、図２１−２のツリー表現は、これまでのものよりも前進代入計算処理で並列に実行可能な処理の抽出を容易なものとするために考案されたものであり、以下の特徴をもっている。
（１）ツリーの各ステージの処理は、前進代入においては必ず左から右に（後退代入では右から左に）ツリーをたどる向きとなり、逆向きの処理は発生しない。
（２）同一ステージ内のノードの処理（横向きの矢印）は全て並列に行うことができ
る。
（３）並列処理の場合、例えば前進代入で、ノードの消去処理時に消去されるノードと値の変わるノードが異なるＣＰＵに割当てられている場合には、通信処理が発生する。これはツリーでＣＰＵ間をまたがる横向きの矢印となるため、並列処理時に必要となる通信回数が容易に把握できる。
（４）ノード間でどのようなデータが渡されるかがツリー上に明示されている。このため、並列処理時に通信で授受されるデータが容易に把握できる。
【００２３】
非特許文献１では、Ｔｉｎｎｅｙ２法をベースにして並列処理向けの新しいノードの順序付け手法を考案している。前進／後退代入計算の並列処理を効率良く行うには、並列に実行できる計算ができるだけ多くなるように順序付けをすることが必要となる。そのためには、ステージ数がなるべく小さくなるようにノードの順序付けを行えば良い。そこでノードの順序付けを、各ステージでのノードの消去処理が通信処理の妨げにならない範囲でできるだけ多くなるように、かつＬＤＵ分解でのｆｉｌｌ−ｉｎの発生ができるだけ少なくなるように行うようにしている。
【００２４】
具体的には、各ステージで消去されるノードに関して、以下の２つの選択基準を設けている。
【００２５】
（１）ノードの消去により発生するｆｉｌｌ−ｉｎが少ないものから選択していく。ただし、あるステージで接続ブランチが２本以下のノードが消去される場合には、接続ブランチ数が３本以上のノードはこのステージでは消去せず、次のステージ以降で消去する。
（２）あるノードから２ブランチまでの範囲に、同じステージで消去されるノードがある場合、当該ノードは消去しない。
【００２６】
ノードの消去によって発生するｆｉｌｌ−ｉｎの数は、そのノードに接続しているブランチ数によって決まるので、接続するブランチ数が少ないノードから選択することで、（１）の条件を満たすことができる。また、接続ブランチ数の多いノードが早い段階で消去されると、ｆｉｌｌ−ｉｎの数の増大を招くので、接続ブランチ数が２本以下のノードが消去されるステージでは、接続ブランチ数が３本以上のノードは消去しない。
【００２７】
（２）の条件に関しては以下の理由による。あるノードが消去されるとそのノードに隣接するノードの値が書き換えられる。消去されたノードから２ブランチの範囲までに、同じステージで消去されるノードがあると、再度の値の書き換えが行われる可能性がある。２度の書き換えの両方が通信処理を伴う場合、２つの通信処理の前後関係を判断するのは不可能である。２つの通信処理のスケジューリング上の前後関係が実際の前後関係と異なる場合には、通信時間を余計に長くしてしまうことになり、また、使用計算機のＣＰＵ間の通信方式が共通のバスを用いる場合には、バスの混雑が発生し、通信処理に大きなペナルティが発生する可能性がある。このような通信処理の非効率化を避けるために、（２）の条件を設けている。
【００２８】
以上に述べた、ノードの順序付けのアルゴリズムを図２２に示す（非特許文献１を参照）。ここでは、接続ブランチ数が２以下のノードがない場合にのみ、接続ブランチ数が３以上のノードが選択できるようにしている。
【００２９】
以上、ノードの順序付けについて述べたが、これは前進／後退代入の計算過程から、「並列処理が行える処理を抽出する処理」であり、順序付けの結果として得られた処理を各ＣＰＵに割当てていく必要がある。系統解析計算の多くが基本的にノード単位の処理であるため、非特許文献１では、ノード単位にＣＰＵに割当てることとしている。
【００３０】
効率の良い並列処理を実現するためには、以下の２点を考慮する必要がある。
・通信回数の低減
・ＣＰＵ間での計算処理の均等化
【００３１】
この２つの目的はトレードオフの関係にある。そこで、一つのパラメータ（以下、グループ化係数と呼ぶ）を用いて、ノードにＣＰＵを割当てる際にノードのグループの大きさを調整するようにし、両者のバランスが取れるようにしている。
【００３２】
通信の処理は計算の処理に比べて時間を要するため、通信回数をなるべく少なくすることが並列処理による高速化の観点から不可欠となる。処理ツリー上では通信処理はＣＰＵ間にまたがる横向きの矢印であるので、横向きの矢印の少ない、番号の大きなステージで通信を行うようにする。
【００３３】
各ＣＰＵに処理を割当てるアルゴリズムは以下のようになる。
（１）前進／後退代入の処理ツリーを番号の大きなステージで切る。ただし、切り離された枝葉の部分のノード数が、（全ノード数）／（グループ化係数）を上回らないようにする。切り離された枝葉の部分の各々を一つのグループとする。
（２）（１）の結果得られるグループの境界線から、（ＣＰＵ数−１）本の境界線を選択して、ＣＰＵへの割り当ての境界線とする。その際、
Σｉ｜ｎｉ−ｎＴｏｔａｌ／ｎＣＰＵ｜ ・・・（３）
を最小化する境界線の組合せを選択する。ただし、ｎｉはＣＰＵｉに割当てられるノードの数、ｎＴｏｔａｌは全ノード数、ｎＣＰＵはＣＰＵ数を表す。
【００３４】
上述のような非特許文献１に記載の方法は、ノードの順序付けにＴｉｎｎｅｙ２法を適用しており、放射状系統に対しては最適になるが、ループ状系統に対しては最適にはならず、ｆｉｌｌ−ｉｎが多くなり処理性能が悪化すること、また、並列計算を各ＣＰＵへ割当てるための処理に時間が掛り、並列処理のオーバヘッドが大きくなること、また、並列処理の効果をＣＰＵ間通信量と各ＣＰＵの処理量のバランスを考慮して決定するため、ＣＰＵ資源の無駄が発生する等の問題点があった。ここで、放射状系統とは、内部にループ構造を含まない系統であり、ループ状系統とはループ構造を含む系統である。なお、実際の系統では、発電所等が系統の末端にあり、そのため、ツリーの中に放射状系統部分は必ず存在している。このような問題点と、さらに、オフラインで実施される系統解析業務以外の訓練シミュレータ、オンラインの給電自動化システム等への適用にはリアルタイム性能が要求されることから、非特許文献１に記載の方法はこの分野には適用が困難であるという問題点があった。
【００３５】
そこで、本実施の形態では、リアルタイム性能を実現させるために、非特許文献２に記載された連立一次方程式の求解方法に基づき、前進消去・後退代入処理の並列処理化を向上させるノード順序付け方法を以下に開示する。
【００３６】
図１１−１および図１１−２は、本実施形態のノード順序付け方法を示すフロー図であり、図１１−２は、図１１−１に続く処理を示す。なお、図１１−１と図１１−２とは、‘１’で示す箇所で接続される。図１１−１において、まず初期化処理（１）（ステップＳ４０）により、フラグ類の初期設定を行い、次に各ノードに接続する相手端ノード番号、相手端ノード数等のノードテーブル作成（ステップＳ４１）を行い、相手端ノード数の少ない順番にノードテーブル並替え（ステップＳ４２）を行う。相手端ノード数が同一の場合は、先に処理したノード順に並替えを行う。なお、各ノードに接続する相手端ノードとは、各ノードに（１本の）ブランチを介して接続されている隣接ノードをいう。例えば、図１３−３においては、ノード１の相手端ノードは、ノード５である。
【００３７】
次に、まず、放射状系統部分のノード順序付けを行う。放射状系統部分においては、例えば図１３−３の放射状系統におけるノード１、ノード２、ノード３、ノード４、およびノード６のように、あるノードに接続するブランチ数が１つという部分を含み、従って、このようなノードに対しては、相手端ノード数も１つということになる。また、例えばノード１を任意に選択して順序付けた場合、ノード１が消去されノード１とノード５との間のブランチも消去されると、ノード５の接続ブランチ数が１つとなって、同様の構造が生じる。そして、順次、放射状系統部分のノード順序付けを行えば、最適なノード順序付けを行えることが分かっている（Ｔｉｎｎｅｙ２法の考え方）。以下、この特徴に基づき、ノード順序付けを行う。
【００３８】
前進消去、後退代入処理を並列処理する場合、通常は各ＣＰＵが１ノードの処理を行うため、並列処理に利用されるＣＰＵ数（以下、並列ＣＰＵ数という。）の要素を一度に扱うことになり、それらの要素処理単位でノード順序付けを行う必要がある。このため、まずステップＳ４３で同時に順序付けを行うノード数が並列ＣＰＵ数以下か否かの判定を行い、Ｎｏの場合は初期化処理（２）（ステップＳ４４）により、要素数カウントの初期化を行う。Ｙｅｓの場合は、何も処理せず、ステップＳ４５に分岐する。
【００３９】
ステップＳ４５では、順序付け対象のノードｉが放射状系統か否かの判定を行い、Ｙｅｓであれば、ステップＳ４６で、ノードｉは並列処理可能か否かの判定を行う。なお、並列処理可能か否かの判定については後述する。ステップＳ４６での判定の結果がＹｅｓの場合、ノードｉを順序付け（ステップＳ４７）、各種配列のカウントアップ（１）（ステップＳ４８）を行い、ステップＳ４３に分岐する。ステップＳ４６での判定の結果がＮｏの場合は、この処理では当該ノードｉを順序付け除外対象（ステップＳ４９）とし、各種配列のカウントアップ（２）（ステップＳ５０）を行い、ステップＳ４３に分岐する。
【００４０】
ステップＳ４５でＮｏの場合は、除外対象ノードとした放射状系統部分が残っているかどうかを確認するために、順序付けが未実施のノードについて、相手端ノード数が少ない順番にノードテーブル並替え（ステップＳ５１）を行い、初期化処理（３）（ステップＳ５２）を行う。次に、ノードテーブル並替え後のノードについて、ノードｉが放射状系統部分か否かの判定（ステップＳ５３）を行い、Ｙｅｓの場合は、さらに放射状系統部分が全て除外対象であるか否かの判定（ステップＳ５４）を行い、ステップＳ５４での判定結果がＮｏの場合、ステップＳ４６に分岐する。ステップＳ５４での判定結果がＹｅｓの場合は、全除外対象ノードを順番に順序付け（ステップＳ５５）を行い、図１１−２の‘１’に示すステップに進む。ステップＳ５３でＮｏの場合は、図１１−２の‘１’に示すステップに進む。
【００４１】
上記までの処理で、放射状系統部分のノード順序付けが終了したので、以降はループ系統部分のノード順序付けを行う。ループ系統部分については、最適なノード順序付け方法が無く、従って、各ノードの新規非零要素発生のシミュレーションを行い、その新規非零要素発生数の一番少ないノードについて、順序付けを行い、それを繰返して実施して行くことが準最適化になることになっている（Ｔｉｎｎｅｙ３法の考え方）。ここでは、その考え方に基づき、以下の手順でノード順序付けを行う。
【００４２】
図１１−２に示すように、まず、ステップＳ５６で、各種フラグ等の初期化処理（４）を行い、次に残りノード全てについて、新規非零要素発生のシミュレーション（ステップＳ５７）を行い、新規非零要素発生数の少ない順番にノード並替え（ステップＳ５８）を行う。次に、順序付けノード数が並列ＣＰＵ数以上か否かの判定（ステップＳ５９）を行い、Ｙｅｓの場合は、順序付け配列数等の初期化処理（２）（ステップＳ６０）を行い、ステップＳ６１に分岐する。Ｎｏの場合は、何も処理せずにステップＳ６１に分岐する。ステップＳ６１では、ノードｉが並列処理可能か否かの判定を行い、Ｙｅｓの場合、ノードｉを順序付け（ステップＳ６２）をし、各種配列のカウントアップ（３）（ステップＳ６３）を行い、次に、ステップＳ６４で、全ノードの順序付けが終了したか否かの判定を行い、Ｎｏの場合は、各種配列のカウントアップ（４）（ステップＳ６５）を行い、ステップＳ５７に分岐する。ステップＳ６４での判定結果がＹｅｓの場合は、処理を終了する。ステップＳ６１でＮｏの場合は、この処理ではノードｉを除外対象（ステップＳ６６）とし、各種配列のカウントアップ（５）（ステップＳ６７）を行い、続いて、残りのノードが全て除外対象か否かの判定（ステップＳ６８）を行い、Ｎｏの場合は、各種配列のカウントアップ（６）（ステップＳ６９）を行い、ステップＳ５９に分岐する。ステップＳ６８でＹｅｓの場合は、残りのノードについて、新規非零要素発生のシミュレーション（ステップＳ７０）を行い、新規非零要素発生数の少ない順番にノード並替え（ステップＳ７１）を行い、そして、それが最小のノードｉの順序付け（ステップＳ７２）を行い、全て終了すれば処理を終了する。
【００４３】
図１２は、図１１−２における新規非零要素発生のシミュレーションの並列処理を示すフロー図である。ループ系統部分においては、ノード順序付けの最適化のために、残りの全ノードについて、そのノードを順序付けした場合の新規非零要素発生数がいくつになるかのシミュレーションを行い、その新規非零要素発生数が最小のノードを次の順序付けノード候補とし、当該ノードを並列処理が可能か否かの判定を行い、並列処理が可能な場合は、そのノードの順序付けを行い、以降、上記の処理を最後まで繰返し、実施している。従って、ループ系統部分のノード順序付けは、処理時間が掛かることになる。そのため、新規非零要素発生のシミュレーションについては、並列処理を行い、処理の高速化を実現する。
【００４４】
図１２において、ループ系統部分の全ノードを、並列処理を行う複数のＣＰＵに平均的に按分して、処理を分担することを考える。まず、各ＣＰＵで処理する場合の平均処理量の計算（ステップＳ７３）を行い、また、平均処理量の計算における余りの計算（ステップＳ７４）を行う。余りの処理量については、ＣＰＵ１で担当させる（すなわち、ＣＰＵ１は、平均処理量＋余り分の処理を担当する。）。次に、処理するＣＰＵがＣＰＵ１か否かの判定（ステップＳ７５）を行い、Ｙｅｓの場合は、処理対象（ｋ１、ｋ２）の計算（ステップＳ７６）を行い、以降の処理におけるフラグ類の初期化処理（ステップＳ７７）を行い、ステップＳ７９に分岐する。ＣＰＵ１以外の場合は、処理対象（ｋ１、ｋ２）の計算（ステップＳ７８）を行い、ステップＳ７９に分岐する。ステップＳ７９では、各ＣＰＵが処理を実行できる状態か否かを、自身に対するＣＰＵ処理フラグである自ＣＰＵ処理フラグがゼロか否かで判定し、Ｎｏの場合は継続してチェックを行う。ステップＳ７９でＹｅｓの場合は、各ＣＰＵが担当する処理量について、新規非零要素発生のシミュレーション（ステップＳ８０）を行い、その結果を共有メモリに保存する。その後、各ＣＰＵは処理が終了したことをＣＰＵ１に示すために、自ＣＰＵ処理フラグに、自ＣＰＵ番号を書き込む（ステップＳ８１）。
【００４５】
次に、再び、ＣＰＵ１か否かの判定（ステップＳ８２）を行い、ＣＰＵ１の場合は、全ＣＰＵの処理フラグが正か否かの判定（ステップＳ８３）を行い、ステップＳ８３での判定結果がＮｏの場合は継続してチェックを行う。ステップＳ８３での判定結果がＹｅｓの場合は、各ＣＰＵが計算した新規非零要素発生数が少ない順番に並び替えを行い、それが最小である最初のノードを選定し（ステップＳ８４）、その後、処理終了フラグにＣＰＵ１の番号をセットし（ステップＳ８５）、処理を終了する。ステップＳ８２でＣＰＵ１でない場合、処理終了フラグが正か否かの判定（ステップＳ８６）を行い、Ｎｏの場合は継続してチェックを行い、Ｙｅｓの場合は処理を終了する。
【００４６】
次に、本実施の形態の動作について説明する。本実施の形態は、非特許文献２に記載の連立一次方程式求解の実時間処理を実現するために、連立一次方程式の前進消去・後退代入の処理について、並列処理を可能とすると共に、並列処理の実行効率を向上させて処理性能の大幅な向上を実現するものである。なお、図２に示すように、連立一次方程式の並列計算を行う計算機構成は、共有メモリ結合された対称型マルチＣＰＵを想定しており、この計算機であれば、各ＣＰＵで共通に読み書きするデータを共有メモリに配置することにより、計算機間の通信手段を不要とし、高速にデータのアクセスができることになり、各ＣＰＵの性能を十分に活用することが可能になる。
【００４７】
非特許文献２では、ノードの順序付け方法としてＴｉｎｎｅｙ２法に基づいている。図４は、非特許文献２に記載の系統例を示す図であり、円内の数字は、ノード番号を示す。また、図５は、図４の系統例の回路網方程式（連立一次方程式）を示す図である。また、非特許文献２では、係数行列の三角分解については、図６の処理フローにより実施し、その結果を図７に示すテーブル形式で保存している。図６では、処理はｉ、ｊ、ｋの３重のループで構成されており、ループｉではステップＳ２６、Ｓ２７の処理を、ループｊではステップＳ２８、Ｓ２９の処理を、また、ループｋではステップＳ３０の処理を行う。図６におけるＮＮｍａｘはノード総数を示す。図７では、’のついている要素は、三角分解の過程で変更を受けた要素であり、Ｐ（ｋ）、Ｑ（ｋ）はノードの縮約順序を示すベクトルである。また、Ｎｍａｘは、係数行列の三角分解後の非対角非零要素数を示す。ノード順序付けは、Ｑ（ｋ）で示すノードを消去し、Ｐ（ｋ）で示すノードに縮約したことを示している。一方、係数行列の三角分解後に行う前進消去・後退代入の処理は、図８に示す処理フローに従って実行するが、後退代入の処理は、２段階に分かれている。この前進消去の処理において、並列処理の阻害要因があり、それを図９により説明する。
【００４８】
図９においては、例えばＣＰＵ４台で並列処理する場合を示しており、１回目の並列処理では、ｋ＝１，２，３，４をそれぞれＣＰＵ１、ＣＰＵ２、ＣＰＵ３、ＣＰＵ４が担当するが、ＣＰＵ２については、Ｑ（２）＝２が先行して処理するＣＰＵ１のＰ（１）＝２と一致するため、並列処理ができず、直列に処理を行う必要がある。そのため、ＣＰＵ１の処理が終了した後に、ＣＰＵ２の処理を実行する必要がある。また、ＣＰＵ４については、Ｐ（４）＝４が、ＣＰＵ３のＰ（３）＝４と一致するため、並列処理ができず、直列に処理を行う必要があり、ＣＰＵ３の処理が終了した後に、ＣＰＵ４の処理を実行する必要がある。同様に、２回目の並列処理においては、ＣＰＵ２の処理は並列処理ができず、また、３回目の並列処理においては、ＣＰＵ２の処理は並列処理ができないことが分かる。
【００４９】
一方、後退代入の処理における並列処理の阻害要因については、図１０を参照して説明する。後退代入処理については、要素番号の大きいものから要素番号が小さい方向に、処理を行う。まず、１回目の並列処理においては、ｋ＝１０，９，８，７を、それぞれＣＰＵ１、ＣＰＵ２、ＣＰＵ３、ＣＰＵ４が担当するが、ＣＰＵ２については、Ｐ（９）＝１０が、ＣＰＵ１のＱ（１０）＝１０と一致するため、並列処理ができず、直列に処理を行う必要がある。そのため、ＣＰＵ１の処理が終了した後に、ＣＰＵ２の処理を実行する必要がある。また、２回目の並列処理においては、ＣＰＵ２については、Ｐ（５）＝３が、ＣＰＵ１のＱ（６）＝３と一致するため、並列処理ができず、直列に処理を行う必要があり、ＣＰＵ１の処理が終了した後に、ＣＰＵ２の処理を実行する必要がある。さらに、ＣＰＵ４については、Ｐ（３）＝４が、ＣＰＵ３のＰ（４）＝４と一致するため、並列処理ができず、直列に処理を行う必要があり、ＣＰＵ３の処理が終了した後に、ＣＰＵ４の処理を実行する必要がある。３回目の並列処理でも、ＣＰＵについては、Ｐ（１）＝２が、ＣＰＵ１のＱ（２）＝２と一致するため、並列処理ができず、直列に処理を行う必要があり、ＣＰＵ１の処理が終了した後に、ＣＰＵ２の処理を実行する必要がある。前述の通り、後退代入処理における並列処理の阻害要因も、前進消去処理と同じであることが分かる。
【００５０】
係数行列のノード順序付けを行うと、三角分解、前進消去、後退代入の処理も全て、同じ影響を受けることになる。従って、係数行列の三角分解の処理に悪影響を与えず、前進消去と後退代入処理の並列処理の実行効率を向上させるノード順序付け方法を考案することが求められる。
【００５１】
従って、本実施の形態では、以下の基本的考え方に基づき、ノード順序付けを行う。
【００５２】
（１）ｆｉｌｌ−ｉｎの最小なノードからノード順序付けを行う。この条件を維持すれば、係数行列の三角分解の処理は、従来の方法と同じ考え方であり、処理性能が悪くなることは無い。
（２）（１）に基づき、前進消去処理における並列処理が可能なノードを優先して、ノ
ード順序付けを行う。これにより、前進消去処理の並列処理の実行効率を向上できると共に、後退代入処理の並列処理の実行効率も向上できる。
【００５３】
前進消去処理の並列処理の実行効率を向上させるためのノード順序付け方法を以下に説明する。前進消去処理における並列処理の阻害要因については、図９に基づき説明した。従って、この阻害要因を解消し、以下の考え方でノード順序付けを行う。
（１）ｆｉｌｌ−ｉｎが最小なノードからノード順序付けを行う。
（２）最初のノードは、（１）で得られたｆｉｌｌ−ｉｎが最小なノードの中から任意に選択するが、以降の並列処理対象のノードについては、当該ノード順序付け候補のノードとその相手端ノードが、順序付け済みのノードの相手端ノードと一致しないノードである場合、優先してノード順序付けを行う。ノード順序付け候補のノードとその相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードであるか否かは、前述の、並列処理が可能か否かの判定である。
（３）優先して順序付けるノードが全て無くなれば、残りのノードをｆｉｌｌ−ｉｎが最小なノードから順にノード順序付けを行う。
【００５４】
上記の考え方を処理フローで表現したのが、図１１−１および図１１−２である。図１１−１では、まず、ｆｉｌｌ−ｉｎが最小となる放射状系統部分のノード順序付けを行い、その後、図１１−２で、ループ状系統部分のノード順序付けを行う方法である。なお、ノード順序付け方法については、放射状系統部分にはＴｉｎｎｅｙ２法を、ループ状系統部分についてはＴｉｎｎｅｙ３法を適用しており、ｆｉｌｌ−ｉｎが最小となる方法である。
【００５５】
なお、Ｔｉｎｎｅｙ３法を適用した計算では、新規非零要素発生のシミュレーションを全ノードについて実施し、ｆｉｌｌ−ｉｎが最小なノードを選択することになるため、これを並列処理して、高速化を実現している。その処理フローを図１２に示す。図１２では、まず、各ＣＰＵが自分の処理対象要素を計算するために、各ＣＰＵの平均処理量と余りを計算し、ＣＰＵ１が先頭から、（平均処理量＋余り）の要素を分担し、ＣＰＵ２以降はそれに続く、平均処理量の要素を分担するようにしている。その後、各ＣＰＵが分担する全要素について、新規非零要素発生数のシミュレーションを行い、処理が終了すれば、共有メモリにそのシミュレーション結果と自分のＣＰＵ処理フラグに自分のＣＰＵ番号をセットする。全体の管理を行うＣＰＵ１は、自分の処理が終了し、全ＣＰＵのＣＰＵ処理フラグがセットされていれば、全処理が終了したことになるので、各ＣＰＵの計算した新規非零要素発生数のシミュレーション結果を共有メモリから取り出し、それを新規非零要素発生数の少ない順番に並び替えを行い、最初のノードをノード順序付け候補として選択する。そして、処理終了フラグをセットし、処理を終了する。一方、ＣＰＵ１以外のＣＰＵは、処理終了フラグをチェックし、処理終了フラグがセットされていれば、処理を終了する。以上の方法で、新規非零要素発生数のシミュレーションを並列処理することができる。
【００５６】
次に、このノード順序付け方法の効果を、図１３−１〜図１３−４を参照して説明する。図１３−１は、系統例における従来のノード順序付けされたノード番号を示し、図１３−２は、そのノード順序付けに従い、三角分解をした結果を示す。図１３−３は、本実施形態のノード順序付けに基づくノード順序付けの結果を示し、図１３−４は、そのノード順序付けに基づき、三角分解をした結果を示す。図１３−１および図１３−３は、図５に示す連立一次方程式の係数行列の構造をツリーで表現し、このツリーはノードとノード間を接続するブランチとから構成されている。図１３−１、１３−２では、矢印で示すように、並列処理が不可能な処理が４回発生している。一方、図１３−３、１３−４は、実施の形態１のノード順序付け方法の結果を示しており、並列処理が不可能な処理が２回となっており、効果があることを示している。特に、本実施の形態におけるノード順序付けの基準の一つである、ノード順序付け候補のノードとその相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に優先してノード順序付けにより、図１３−２に示すような並列処理の阻害要因を解消する効果があることがわかる。
【００５７】
このように、本実施の形態における連立一次方程式の並列計算方式のノード順序付け方法は、ｆｉｌｌ−ｉｎが最小なノードからノード順序付けを行うが、最初のノードは、ｆｉｌｌ−ｉｎが最小なノードの中から任意に選択し、以降の並列処理対象のノードについては、当該ノードとその相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に優先してノード順序付けを行う。そして、優先して順序付けるノードが無くなれば、残るノードをｆｉｌｌ−ｉｎが最小なノードからノード順序付けを行うようにしたものである。本実施の形態によれば、前進消去・後退代入処理における並列処理の実行効率を向上させて、処理性能を高速化できるという効果があり、大規模系統の回路網方程式（連立一次方程式）を実時間性能で実行することが可能となる。
【００５８】
実施の形態２．
図１１−１は、実施の形態２のノード順序付け方法を示すフロー図であり、図１１−２は、図１１−１に続くフロー図である。すなわち、本実施の形態でも実施の形態１と同様のノード順序付け方法に従う。しかしながら、実施の形態１では、ループ状系統部分のノード順序付けにおける新規非零要素発生のシミュレーションを並列処理しているが、実施の形態２では、この新規非零要素発生のシミュレーションを並列処理せず、１台のＣＰＵで処理するようにしたものである。このようにすれば、処理性能は高速化できないが、ノード順序付けの最適化は実現可能であり、ＣＰＵ台数を少なくして訓練シミュレータを安価に構成できるという効果がある。
【００５９】
実施の形態３．
図１４−１および図１４−２は、実施の形態３のノード順序付け方法を示すフロー図である。なお、図１４−２は、図１４−１に続く処理を示しており、‘２’で示す箇所において処理が接続される。図１４−１において、まず初期化処理（１）（ステップＳ９０）により、フラグ類の初期設定を行い、次に各ノードに接続する相手端ノード番号、相手端ノード数等のノードテーブル作成（ステップＳ９１）を行い、相手端ノード数の少ない順番にノードテーブル並替え（ステップＳ９２）を行う。相手端ノード数が同一の場合は、先に処理したノード順に並び替えを行う。
【００６０】
次に、まず、放射状系統部分のノード順序付けを行う。放射状系統部分においては、例えば図１３−３の放射状系統におけるノード１、ノード２、ノード３、ノード４、およびノード６のように、あるノードに接続するブランチ数が１つという部分を含み、従って、このようなノードに対しては、相手端ノード数も１つということになる。また、例えばノード１を任意に選択して順序付けた場合、ノード１が消去されノード１とノード５との間のブランチも消去されると、ノード５の接続ブランチ数が１つとなって、同様の構造が生じる。そして、順次、放射状系統部分のノード順序付けを行えば、最適なノード順序付けを行えることが分かっている（Ｔｉｎｎｅｙ２法の考え方）。以下、この特徴に基づき、ノード順序付けを行う。
【００６１】
前進消去、後退代入処理を並列処理する場合、各ＣＰＵが１ノードの処理を行うため、並列処理を行うＣＰＵ数の要素を一度に扱うことになり、それらの要素処理単位でノード順序付けを行う必要がある。このため、まずステップＳ９３で、同時に順序付けを行うノード数が並列ＣＰＵ数以下か否かの判定を行い、Ｎｏの場合は初期化処理（２）（ステップＳ９４）により、要素数カウントの初期化を行う。ステップＳ９３での判定結果がＹｅｓの場合は、何も処理せず、ステップＳ９５に分岐する。
【００６２】
ステップＳ９５では、順序付け対象のノードｉが放射状系統か否かの判定を行い、Ｙｅｓであれば、ステップＳ９６で、ノードｉは並列処理可能か否かの判定を行う。ステップＳ９６での判定結果がＹｅｓの場合、ノードｉを順序付け（ステップＳ９７）を行い、各種配列のカウントアップ（１）（ステップＳ９８）を行い、ステップＳ９３に分岐する。
ステップＳ９６での判定結果がＮｏの場合は、この処理では当該ノードｉを順序付け除外対象（ステップＳ９９）とし、各種配列のカウントアップ（２）（ステップＳ１００）を行い、ステップＳ９３に分岐する。
【００６３】
ステップＳ９５でＮｏの場合は、除外対象ノードとした放射状系統部分が残っているかどうかを確認するために、順序付けが未実施のノードについて、相手端ノード数が少ない順番にノードテーブル並替え（ステップＳ１０１）を行い、初期化処理（３）（ステップＳ１０２）を行う。次に、ノードテーブル並替え後のノードについて、ノードｉが放射状系統部分か否かの判定（ステップＳ１０３）を行い、Ｙｅｓの場合は、さらに放射状系統部分が全て除外対象であるか否かの判定（ステップＳ１０４）を行い、Ｎｏの場合、ステップＳ９６に分岐する。ステップＳ１０４でＹｅｓの場合は、全除外対象ノードを順番に順序付け（ステップＳ１０５）を行い、図１４−２に示す処理に進む。また、ステップＳ１０３でＮｏの場合は、図１４−２示す処理に進む。
【００６４】
上記までの処理で、放射状系統部分のノード順序付けが終了したので、以降はループ状系統部分のノード順序付けを行う。ループ状系統部分についても、放射状系統部分と同様の考え方でノード順序付けを行う。
【００６５】
図１４−２に示すように、まず、ステップＳ１０６で、各種フラグ等の初期化処理（４）を行い、次に、残りノード全てについて、ノード接続数の少ない順番にノードテーブルの並び替え（ステップＳ１０７）を行い、ノード接続数が少ない順番にノードを並替える。次に、順序付けノード数が並列ＣＰＵ数以上か否かの判定（ステップＳ１０８）を行い、Ｙｅｓの場合は、順序付け配列数等の初期化処理（２）（ステップＳ１０９）を行い、ステップＳ１１０に分岐する。ステップ１０８でＮｏの場合は、何も処理せずにステップＳ１１０に分岐する。ステップＳ１１０では、ノードｉが並列処理可能か否かの判定を行い、Ｙｅｓの場合、ノードｉを順序付け（ステップＳ１１１）をし、各種配列のカウントアップ（３）（ステップＳ１１２）を行い、次に、ステップＳ１１３で全ノードの順序付けが終了したかの判定を行う。ステップＳ１１３でＮｏの場合は、各種配列のカウントアップ（４）（ステップＳ１１４）を行い、ステップＳ１０７に分岐する。ステップＳ１１３でＹｅｓの場合は、処理を終了する。
【００６６】
ステップＳ１１０でＮｏの場合は、この処理ではノードｉを除外対象（ステップＳ１１５）とし、各種配列のカウントアップ（５）（ステップＳ１１６）を行い、続いて、残りのノードが全て除外対象か否かの判定（ステップＳ１１７）を行い、Ｎｏの場合は、各種配列のカウントアップ（６）（ステップＳ１１８）を行い、ステップＳ１０８に分岐する。ステップＳ１１７でＹｅｓの場合は、残りのノードについて、ノード接続数が少ない順番にノードテーブルの並替え（ステップＳ１１９）を行い、そして、それが最小のノードｉの順序付け（ステップＳ１２０）を行い、全て終了すれば処理を終了する。
【００６７】
実施の形態１では、ループ状系統部分のノード順序付けにおいて、新規非零要素発生数のシミュレーションを並列処理するようにしたが、この実施の形態３では、ループ状系統部分のノード順序付けにおいて、新規非零要素発生のシミュレーションの替わりに、放射状系統部分と同様に、あるノードに接続する相手端ノード数が少ない順番にノード順序付け候補とするようにしたものである。このようにすれば、ノード順序付けの最適化の度合いは実施の形態１よりは低下するが、ノード順序付けの処理を１台のＣＰＵでも高速に処理できるため、訓練シミュレータにおける訓練実行段階でも系統構成状態の変化が発生した場合に、再度、ノード順序付けを高速に実行できるため、訓練実行段階における回路網計算を準最適化できる。そのため、連立一次方程式の求解を高速に処理することが可能になると共に、安価に訓練シミュレータを構成できるという効果がある。また、給電自動化システム等のオンライン用途のシステムにも適用可能になるという効果がある。
【００６８】
実施の形態４．
本実施の形態にかかる連立一次方程式の並列求解方法について説明する。なお、ノード順序付けは、実施の形態１〜３のいずれか１つのノード順序付け方法を利用して行い、また、係数行列の三角分解は非特許文献２の方法により実施するものとし、その三角分解結果を用いて、前進消去処理および後退代入処理を行うものとする。図１５−１および図１５−２は、本実施の形態にかかる連立一次方程式の並列求解方法を示すフロー図であり、実施の形態１、２、または３のノード順序付け方法を適用した前進消去、後退代入過程の複数ＣＰＵによる並列処理を示すフロー図である。なお、図１５−２は、図１５−１に続く処理の流れを示し、‘３’で示す箇所で接続されている。
【００６９】
図１５−１において、まず、前進消去過程の並列処理を行うが、最初に、ＣＰＵ１か否かの判定（ステップＳ１２１）を行い、Ｙｅｓの場合は、フラグ類の初期化処理（ステップＳ１２２）を行い、次に、各ＣＰＵが並列処理できるか否かを示す並列処理フラグの作成（ステップＳ１２３）を行い、ステップＳ１２４に進む。ステップＳ１２１での判定結果がＮｏの場合は、ステップＳ１２４に分岐する。ステップＳ１２４では、複数個のＣＰＵが並列処理を行う処理回数Ｌ、処理順序ｋの設定を行い、続いて、処理対象ｂｊ要素の選定（ステップＳ１２５）を行う。ここで、ｂｊは、係数ベクトルｂのｊ番目の成分を表す。次に、ｂｊ要素が並列処理可能か否かの判定（ステップＳ１２６）を行い、Ｙｅｓの場合は、ステップＳ１２８に分岐する。ステップＳ１２６での判定結果がＮｏの場合は、ｂｊ要素の処理に必要な、関連する要素である関連ｂｉ要素が処理済みか否かの判定（ステップＳ１２７）を行い、ステップＳ１２７での判定結果がＮｏの場合は継続してチェックを行い、ステップＳ１２７での判定結果がＹｅｓの場合はステップＳ１２８に進む。ステップＳ１２８では、前進消去過程の計算を行い、続いて、ＣＰＵ処理フラグの設定（ステップＳ１２９）をし、前進消去過程終了の判定（ステップＳ１３０）を行う。ステップＳ１３０での判定結果がＮｏの場合はＣＰＵ処理フラグをゼロに設定（ステップＳ１３１）し、ステップＳ１２４に分岐する。ステップＳ１３０での判定結果がＹｅｓの場合は、前進消去過程の処理を終了し、後退代入過程１の処理に移る。
【００７０】
図１５−２に示すように、後退代入過程１では、まず、ＣＰＵ１か否かの判定（ステップＳ１３２）を行い、Ｙｅｓの場合は、フラグ類の初期化処理（ステップＳ１３３）を行い、Ｎｏの場合はスキップする。次に、処理対象ｘｉ群の設定（ステップＳ１３４）を行い、後退代入過程１の計算（ステップＳ１３５）を実行し、計算終了後に、ＣＰＵ処理フラグの設定（ステップＳ１３６）を行い、続いて、後退代入過程１終了の判定（ステップＳ１３７）を行う。ここで、ｘｉは解ｘのｉ番目の成分を表し、また、ステップＳ１３５において、ａｉｉは係数行列のｉ番目の対角成分、ｂｉは係数ベクトルのｉ番目の成分、
Ｃ（ｉ）＝１／ａｉｉである（図６を参照）。ステップＳ１３７での判定結果がＮｏの場合は継続してチェックを行うが、Ｙｅｓの場合は後退代入過程１を終了し、後退代入過程２に移る。
【００７１】
後退代入過程２では、まず、ＣＰＵ１か否かの判定（ステップＳ１３８）を行い、Ｙｅｓの場合にはフラグ類の初期化処理（ステップＳ１３９）を行い、次に、各ＣＰＵが並列処理できるか否かを示す並列処理フラグの作成（ステップＳ１４０）を行うが、Ｎｏの場合、ステップＳ１４１に分岐する。ステップＳ１４１では、処理回数Ｌ、処理順序ｋの設定を行い、処理対象ｘｉ要素の選定（ステップＳ１４２）をし、次に、ｘｉ要素が並列処理可能か否かの判定（ステップＳ１４３）を行う。ステップＳ１４３での判定結果がＮｏの場合は、ｘｉ要素の処理に必要な、関連する要素である関連ｘｊ要素が処理済みか否かの判定（ステップＳ１４４）を行い、ステップＳ１４４での判定結果がＮｏの場合は継続してチェックを行い、ステップＳ１４４での判定結果がＹｅｓの場合はステップＳ１４５に進む。ステップＳ１４３での判定結果がＹｅｓの場合は、ステップＳ１４５に分岐する。
【００７２】
ステップＳ１４５では、後退代入過程２の計算を行い、次に、ＣＰＵ処理フラグの設定（ステップＳ１４６）をし、最後に、後退代入過程２終了の判定（ステップＳ１４７）を行い、Ｎｏの場合はＣＰＵ処理フラグにゼロを設定（ステップＳ１４８）し、ステップＳ１４１に分岐する。ステップＳ１４７での判定結果がＹｅｓの場合は、後退代入過程２の処理を終了する。
【００７３】
図１６−１および図１６−２は、本実施の形態の前進消去過程における並列処理フラグ作成の処理を示すフロー図である。なお、図１６−２は、図１６−１に続くフロー図であり、‘４’で示す箇所で接続されている。図１６−１では、まず、並列処理フラグ作成対象の設定（ステップＳ１５０）を行い、続いて、ＣＰＵ１か否かの判定（ステップＳ１５１）を行い、Ｙｅｓの場合はＣＰＵ実行フラグ、ＣＰＵ参照フラグ、ＣＰＵ処理フラグ、並列処理フラグ作成の終了フラグ等、フラグ類の初期化処理（ステップＳ１５２）を行い、Ｎｏの場合はステップＳ１５３に分岐する。次に、処理要素の配列ｉと処理ＣＰＵ番号ｋｍ、ｋｎの初期値設定（ステップＳ１５３）を行う。次に、図１６−２では、前進消去の並列処理対象要素の計算（ステップＳ１５４）を行い、以降、各要素について並列処理が可能か否かの判定を行い、可能な場合はＣＰＵ実行フラグにＣＰＵ番号を設定し、不可能な場合は、処理終了を参照すべきＣＰＵ番号をＣＰＵ参照フラグに設定して、並列処理フラグの作成を行う。
【００７４】
まず、選定した要素の配列Ｑが既に選定した要素の配列Ｐと一致するか否かのチェックを行う。一致する場合は、並列処理が不可能であり、一致しない場合は、並列処理が可能と判定する。この処理は、ｍとｎのループから構成するが、ｍのループでは、並列処理対象要素を全て含み、ステップＳ１５５で、ｍのループにおける処理ＣＰＵ番号をカウントアップする。ｎのループは最初の要素は必ず含むが、それ以降の要素は、ｍ−１の要素までとする。これは、例えば、２番目の要素は１番目の要素と、３番目の要素は１番目、２番目の要素と、４番目の要素は１番目、２番目、３番目の要素と比較するためである。
【００７５】
まず、ステップＳ１５６で、ｎのループにおける処理ＣＰＵ番号をカウントアップする。ｋｎは先行して選定された要素を処理するＣＰＵ番号であり、ｋｍは先行して選定された要素に対し並列処理を行うＣＰＵ番号である。
【００７６】
次に、ｋｍが１か否かの判定（ステップＳ１５７）を行い、Ｙｅｓの場合は、並列処理対象の先頭要素であるため、無条件で並列処理可能として、ＣＰＵ実行フラグを設定し、ＣＰＵ参照フラグをクリア（ステップＳ１６２）し、ステップＳ１６１の次に分岐する（ｍのループの更新を行う。）。ステップＳ１５７でＮｏの場合は、Ｑ（ｍ）とＰ（ｎ）が一致するか否かの判定（ステップＳ１５９）を行い、Ｙｅｓの場合は並列処理が不可能であるため、ＣＰＵ参照フラグを設定し、ＣＰＵ実行フラグをクリア（ステップＳ１５９）するが、Ｎｏの場合は何も処理しない。そして、ｎのループが終了した後で、Ｑ（ｍ）と全Ｐ（ｎ）とが不一致か否かの判定（ステップＳ１６０）を行い、Ｙｅｓの場合は並列処理が可能であるため、ＣＰＵ実行フラグを設定し、ＣＰＵ参照フラグをクリア（ステップＳ１６１）する。ステップＳ１６０でＮｏの場合は何も処理しない。
【００７７】
次に、さらに並列処理が可能か否かの判定として、先行して選定した要素の配列Ｐとそれ以降に選定した要素の配列Ｐとが一致するか否かのチェックを行う。一致しない場合は、並列処理が可能であるが、一致する場合は並列処理が不可能であるため、それぞれに対応して、ＣＰＵ実行フラグ、ＣＰＵ参照フラグの設定を行う。
【００７８】
まず、ｎのループにおける処理ＣＰＵ番号を初期値設定（ステップＳ１６３）する。これらの処理は、ｍとｎのループで構成し、ｍのループについては、先頭の要素は無条件で並列処理可能であるため、２番目の要素から選定する、また、ｎのループについては、先頭の要素からｍ−１の要素までを選定する。これは、２番目の場合は１番目の要素と、３番目の要素の場合は１番目、２番目の要素と、４番目の場合は１番目、２番目、３番目の要素と比較するためである。
【００７９】
まず、ステップＳ１６４で処理ＣＰＵ番号ｋｎをカウントアップし、Ｐ（ｍ）とＰ（ｎ）とが一致するか否かの判定（ステップＳ１６５）を行い、一致する場合は並列処理が不可能なためＣＰＵ参照フラグを設定し、ＣＰＵ実行フラグをクリア（ステップＳ１６６）し、Ｎｏの場合は何も処理しない。ｍとｎのループの処理が終了すれば、全要素の処理が終了したか否かの判定（ステップＳ１６７）を行い、Ｎｏの場合は、配列ｉを並列処理するＣＰＵ台数分（ＣＰＵｍａｘ）だけ増加（ステップＳ１６８）させ、また、処理ＣＰＵ番号ｋｍ、ｋｎをクリア（ステップＳ１６９）して、ステップＳ１５４に分岐する。Ｙｅｓの場合は自ＣＰＵ処理フラグに、処理を実施したＣＰＵ番号を設定し（ステップＳ１７０）、ＣＰＵ１の判定（ステップＳ１７１）を行い、Ｙｅｓの場合は全ＣＰＵ処理フラグが正か否かの判定（ステップＳ１７２）を行う。ステップＳ１７２で、Ｎｏの場合は継続してチェックを行い、Ｙｅｓの場合は並列処理フラグ作成の終了フラグを設定（ステップＳ１７３）し、ＣＰＵ１の処理を終了する。ステップＳ１７１でＣＰＵ１以外の場合は、並列処理フラグ作成の終了フラグの判定（ステップＳ１７４）を行い、判定結果が、Ｎｏの場合は継続してチェックを行い、Ｙｅｓの場合は処理を終了する。
【００８０】
図１７−１および図１７−２は、本実施の形態の後退代入過程における並列処理フラグ作成の処理を示すフロー図である。なお、図１７−２は、図１７−１に続くフロー図であり、‘５’で示す箇所で接続されている。前進消去処理では、要素１から最大要素の方向に処理が進むが、後退代入処理の場合は、逆に、最大の要素から要素１の方向に処理が進む。これが両者の最大の差異である。
【００８１】
図１７−１では、まず、並列処理フラグ作成対象の設定（ステップＳ１５０）を行い、続いて、ＣＰＵ１か否かの判定（ステップＳ１５０）を行い、Ｙｅｓの場合はＣＰＵ実行フラグ、ＣＰＵ参照フラグ、ＣＰＵ処理フラグ、並列処理フラグ作成の終了フラグ等、フラグ類の初期化処理（ステップＳ１５２）を行い、Ｎｏの場合はステップ１５３に分岐する。次に、処理要素の配列ｉとＣＰＵ処理番号ｋｍ、ｋｎの初期値設定（ステップＳ１５２）を行う。次に、図１７−２では、後退代入の並列処理対象要素の計算（ステップＳ１５４）を行い、以降、各要素について並列処理が可能か否かの判定を行い、可能な場合はＣＰＵ実行フラグにＣＰＵ番号を設定し、不可能な場合は、処理終了を参照するべきＣＰＵ番号をＣＰＵ参照フラグに設定して、並列処理フラグの作成を行う。
【００８２】
まず、選定した要素の配列Ｑが既に選定した要素の配列Ｐと一致するか否かのチェックを行う。一致する場合は、並列処理が不可能であり、一致しない場合は、並列処理が可能と判定する。この処理は、ｍとｎのループから構成するが、ｍのループでは、並列処理対象要素を全て含み、ステップＳ１５５でｍのループにおける処理ＣＰＵ番号をカウントアップする。ｎのループは最初の要素は必ず含むが、それ以降の要素は、ｍ−１の要素までとする。これは、２番目の要素は１番目の要素と、３番目の要素は１番目、２番目の要素と、４番目の要素は１番目、２番目、３番目の要素と比較するためである。
【００８３】
まず、ステップＳ１５６で、ｎのループにおける処理ＣＰＵ番号をカウントアップする。ｋｎは先行して選定された要素を処理するＣＰＵ番号であり、ｋｍは先行して選定された要素に対し並列処理を行うＣＰＵ番号である。
【００８４】
次に、ｋｍが１か否かの判定（ステップＳ１５７）を行い、Ｙｅｓの場合は、並列処理対象の先頭要素であるため、無条件で並列処理可能として、ＣＰＵ実行フラグを設定し、ＣＰＵ参照フラグをクリア（ステップＳ１６２）し、ステップＳ１６２の次に分岐する（ｍのループの更新を行う。）。Ｎｏの場合は、ステップＳ１５７でＮｏの場合は、Ｐ（ｍ）とＱ（ｎ）とが一致する否かの判定（ステップＳ１５９）を行い、Ｙｅｓの場合は並列処理が不可能であるため、ＣＰＵ参照フラグを設定し、ＣＰＵ実行フラグをクリア（ステップ１００）するが、Ｎｏの場合は何も処理しない。そして、ｎのループが終了した後で、Ｐ（ｍ）と全Ｑ（ｎ）とが不一致か否かの判定（ステップＳ１６０）を行い、Ｙｅｓの場合は並列処理が可能であるため、ＣＰＵ実行フラグを設定し、ＣＰＵ参照フラグをクリア（ステップＳ１６１）する。ステップＳ１６０でＮｏの場合は何も処理しない。
【００８５】
次に、さらに並列処理が可能か否かの判定として、先行して選定した要素の配列Ｐとそれ以降に選定した要素の配列Ｐが一致するかのチェックを行う。一致しない場合は、並列処理が可能であるが、一致する場合は並列処理が不可能であるため、それぞれに対応して、ＣＰＵ実行フラグ、ＣＰＵ参照フラグの設定を行う。
【００８６】
まず、ｎのループにおける処理ＣＰＵ番号を初期値設定（ステップＳ１６３）する。これらの処理は、ｍとｎのループで構成し、ｍのループについては、先頭の要素は無条件で並列処理可能であるため、２番目の要素から選定する、また、ｎのループについては、先頭の要素からｍ−１の要素までを選定する。これは、２番目の場合は１番目の要素と、３番目の要素の場合は１番目、２番目の要素と、４番目の場合は１番目、２番目、３番目の要素と比較するためである。
【００８７】
まず、ステップＳ１６４で処理ＣＰＵ番号ｋｎをカウントアップし、Ｐ（ｍ）とＰ（ｎ）が一致するかの判定（ステップＳ１６５）を行い、一致する場合は並列処理が不可能なためＣＰＵ参照フラグを設定し、ＣＰＵ実行フラグをクリア（ステップＳ１６６）し、Ｎｏの場合は何も処理しない。ｍとｎのループの処理が終了すれば、全要素の処理が終了したか否かの判定（ステップＳ１６７）を行い、Ｎｏの場合は、配列ｉを並列処理するＣＰＵ台数分（ＣＰＵｍａｘ）だけ減少（ステップＳ１６８）させ、また、処理ＣＰＵ番号ｋｍ、ｋｎをクリア（ステップＳ１６９）して、ステップＳ１５４に分岐する。Ｙｅｓの場合は自ＣＰＵ処理フラグに自ＣＰＵ番号を設定（ステップＳ１７０）し、ＣＰＵ１か否かの判定（ステップＳ１７１）を行い、Ｙｅｓの場合は全ＣＰＵ処理フラグが正か否かの判定（ステップＳ１７２）を行う。ステップＳ７１２で、Ｎｏの場合は継続してチェックし、Ｙｅｓの場合は並列処理フラグ作成の終了フラグを設定（ステップＳ１７３）し、ＣＰＵ１の処理を終了する。ステップＳ１７１でＮｏの場合は、並列処理フラグ作成の終了フラグが正か否かの判定（ステップＳ１７４）を行い、判定結果が、Ｎｏの場合は継続してチェックを行い、Ｙｅｓの場合は処理を終了する。
【００８８】
実施の形態１では、前進消去、後退代入処理の並列処理の実行効率を上げるためのノード順序付け方法を説明したが、この実施の形態４では、そのノード順序付けを適用した場合の前進消去、後退代入処理の並列処理の実現方法を説明した。このように、実施の形態１と実施の形態４とを組合せることにより、連立一次方程式求解の並列処理を実現できると共に、高速処理が可能になるという効果がある。
【００８９】
次に、動作について説明する。まず、前進消去過程の並列処理について、説明する。複数のＣＰＵで並列処理を行う場合、処理前に、ｂｉ要素の並列処理が可能であるか否かのチェックを行い、並列処理フラグ（ＣＰＵ実行フラグ、ＣＰＵ参照フラグ）を複数ＣＰＵで並列に作成し、各ＣＰＵの処理するｂｉ、ｂｊ要素の決定、１回毎の並列計算ステップにおける各ＣＰＵの処理が終了したことの検出方法、また、全行の処理が終了したことの検出方法を定める必要がある。
（ａ）並列処理フラグ（ＣＰＵ実行フラグ、ＣＰＵ参照フラグ）の作成
（１）各ＣＰＵは、各ＣＰＵが担当する自分の並列処理フラグ作成対象の設定を行う。
（２）ＣＰＵ１は、まず、全ＣＰＵのＣＰＵ実行フラグ、ＣＰＵ参照フラグを「０」で初期化する。
（３）次に、各ＣＰＵは、当該並列処理における並列処理対象要素について、後段のＱ（ｍ）と前段の全Ｐ（ｎ）の値とが一致するか否かチェックする。一致する場合は、並列処理が不可になるのでＣＰＵ参照フラグを設定し、全て一致しない場合は並列処理が可能になるので、ＣＰＵ実行フラグを設定する。
・並列処理対象の最初の要素は、無条件で並列処理可能とし、当該ＣＰＵのＣＰＵ実行フラグに当該ＣＰＵ番号を設定する。
・後段の要素と先行する全要素のチェックの結果、一致する場合は、当該ＣＰＵのＣＰＵ参照フラグに、参照すべき一致した要素のＰ（ｎ）を担当するＣＰＵ番号を設定する。
・後段の要素と先行する全要素のチェックの結果、全て一致しない場合は、当該要素Ｑ（ｍ）を担当するＣＰＵのＣＰＵ実行フラグに当該ＣＰＵ番号を設定する。
（４）次に、各ＣＰＵは、当該並列処理における並列処理対象要素について、後段のＰ（ｍ）と前段の全Ｐ（ｎ）の値とが一致するか否かチェックする。一致する場合は、並列処理が不可になるのでＣＰＵ参照フラグを設定する。全て一致しない場合は何も処理しない。
・一致する場合は、当該ＣＰＵのＣＰＵ参照フラグに、参照すべき一致した要素のＰ（ｎ）を担当するＣＰＵ番号を設定する。
・一致しない場合は、何もしない。
（５）各ＣＰＵは、自分の処理が終了すれば、自ＣＰＵ処理フラグに自分のＣＰＵ番号を設定する。
（６）ＣＰＵ１は、全てのＣＰＵの処理が終了したか否かをＣＰＵ終了フラグでチェックし、終了していれば、並列処理フラグ作成の終了フラグを設定し、処理を終了する。
（７）ＣＰＵ１以外のＣＰＵも、並列処理フラグ作成の終了フラグが設定されている場合は、処理を終了する。
（ｂ）処理対象ｂｉ、ｂｊ要素の決定
（１）各ＣＰＵが処理するｂｉ、ｂｊ要素を下記の（４）式により算出する。また、図１８は、前進消去過程の並列処理において、４台のＣＰＵに処理を割り振り各種フラグで管理する様子を示す図である。
ｋ＝（Ｌ−１）＊ＣＰＵｍａｘ＋ＣＰＵｉ ・・・（４）
ｊ＝Ｐ（ｋ）
ｉ＝Ｑ（ｋ）
ただし、
Ｌ：各ＣＰＵの計算回数（ＣＰＵ１が初期化。初期値は１）
ＣＰＵｍａｘ：並列処理するＣＰＵ台数
ＣＰＵｉ：ＣＰＵ番号（ＣＰＵ１＝１、・・・、ＣＰＵｎ＝ＣＰＵｍａｘ）
（ｃ）ＣＰＵ処理フラグの管理
ＣＰＵ１が各ＣＰＵの計算回数Ｌの更新を行うためには、各ＣＰＵの処理が終了したことを確認する必要がある。これをＣＰＵ処理フラグと定義する。
（１）初期化
ＣＰＵ１が、全ＣＰＵのＣＰＵ処理フラグを、０で初期化する。
（２）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の処理が終了した時点で、ＣＰＵ処理フラグに自ＣＰＵ番号を書き込む。
（３）計算回数Ｌのカウントアップ
ＣＰＵ１は、全ＣＰＵのＣＰＵ処理フラグが正になった時点で、Ｌを１だけ、カウントアップし、全ＣＰＵのＣＰＵ処理フラグをリセットする。
（ｄ）前進消去過程終了フラグの管理
前進消去過程の処理終了は、各ＣＰＵが行う。
（１）初期化
ＣＰＵ１が、前進消去過程終了フラグを、０で初期化する。
（２）最終行の検出
各ＣＰＵが処理するｂｊ要素の行番号が、行サイズｎｍａｘと一致した場合、最
終行の処理をしたと判断し、検出したＣＰＵは、前進消去過程終了フラグに自ＣＰＵ番号をセットする。
（３）前進消去過程の終了
各ＣＰＵは、前進消去過程終了フラグが正の場合、前進消去過程の処理が終了したと判断し、次の後退代入過程１の処理に入る。
（ｅ）前進消去過程の並列処理手順
（１）各ＣＰＵが担当する並列処理フラグ作成対象を設定する。
（２）ＣＰＵ１が、各ＣＰＵのＣＰＵ実行フラグ、ＣＰＵ参照フラグ、ＣＰＵ処理フラグ、前進消去過程終了フラグを初期化する。
（３）各ＣＰＵが、全てのＣＰＵ実行フラグ、ＣＰＵ参照フラグを並列に作成する。
（４）各ＣＰＵが、処理対象ｂｉ、ｂｊ要素を決定する。
（５）各ＣＰＵが、ＣＰＵ実行フラグをチェックする。
・自分のＣＰＵ番号と一致する場合は、ｂｊ要素の計算を行い、ＣＰＵ処理フラグをセットする。なお、ｂｉ要素と掛け算となるＤ要素がゼロの場合は、その処理をスキップする。
・自分のＣＰＵ番号と一致しない場合は、ＣＰＵ参照フラグが示すＣＰＵ番号について、そのＣＰＵ処理フラグをチェックする。
（ｉ）ＣＰＵ処理フラグが正の場合は、ｂｊ要素の処理を行い、ＣＰＵ処理フラグをセットする。
（ｉｉ）ＣＰＵ処理フラグが正でない場合は、継続チェックを行う（先行ＣＰＵの計算終了待ち）。
（６）ＣＰＵ１が、全ＣＰＵ処理フラグが正であることを確認し、Ｌを１アップし、
全ＣＰＵのＣＰＵ処理フラグをリセットし、（４）に戻る。
（７）各ＣＰＵは、自分が最終行を処理した場合、前進消去過程終了フラグをセット
する。
（８）各ＣＰＵは、前進消去過程終了フラグが正の場合、前進消去を終了し、次の後
退代入過程１に進む。
【００９０】
次に、後退代入過程１の並列処理について、説明する。後退代入過程１の処理は、各ＣＰＵが全処理を分担して、並列処理することができる。複数のＣＰＵで並列処理を行う場合、各ＣＰＵの処理するｘｊ要素の決定、各ＣＰＵの処理が終了したことの検出方法、また、全行の処理が終了したことの検出方法を決める必要がある。
（ａ）処理対象ｘｉの決定
（１）各ＣＰＵが処理するｘｉ要素を下記の式により算出する。
・各ＣＰＵの平均処理量
ｋ０＝（ｎｍａｘ／ＣＰＵｍａｘ）の整数値
・余り
ｋ１＝ｎｍａｘ−ｋ０・ＣＰＵｍａｘ
・ＣＰＵ１の処理量
ｉ＝１〜ｋ０＋ｋ１
・ＣＰＵ２〜ＣＰＵｍａｘの処理量
ｉ＝（ｋ０＋ｋ１）＋（ＣＰＵｉ−２）＊ｋ０＋１
〜（ｋ０＋ｋ１）＋（ＣＰＵｉ−１）＊ｋ０
（ｂ）ＣＰＵ処理フラグ、後退代入過程１終了フラグの管理
後退代入過程１の処理が終了したことをチェックするためには、各ＣＰＵの処理が終了したことを確認する必要がある。また、図１９は、後退代入過程１の並列処理において、４台のＣＰＵに処理を割り振りＣＰＵ処理フラグで管理する様子を示す図である。
（１）初期化
ＣＰＵ１が、全ＣＰＵのＣＰＵ処理フラグ、後退代入過程１終了フラグを、０で初期化する。
（２）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の処理が終了した時点で、ＣＰＵ処理フラグに自ＣＰＵ番号を書き込む。
（３）後退代入過程１終了フラグの設定
ＣＰＵ１は、自分の処理が終了した時点に、他ＣＰＵのＣＰＵ処理フラグが正になったことを検出し、後退代入過程１終了フラグをセットする。
（ｃ）後退代入過程１の並列処理手順
（１）初期化
ＣＰＵ１が、全ＣＰＵのＣＰＵ処理フラグ、後退代入過程１終了フラグを、０で初期化する。
（２）処理対象ｘｉの決定
各ＣＰＵが、自分が担当する処理対象ｘｉを計算する。
（３）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の処理が終了した時点で、ＣＰＵ処理フラグに自ＣＰＵ番号を書き込む。
（４）後退代入過程１終了フラグの設定
ＣＰＵ１は、自分の処理が終了した時点で、他ＣＰＵのＣＰＵ処理フラグが正になっていることを検出し、後退代入過程１終了フラグをセットする。
（５）各ＣＰＵは、後退代入過程１終了フラグが正の場合、後退代入過程１の処理が終了したことを認識し、次の後退代入過程２の処理に進む。
【００９１】
最後に、後退代入過程２の並列処理について、説明する。複数のＣＰＵで並列処理を行う場合、処理前に、ｘｉ、ｘｊ要素の並列処理が可能であるか否かのチェックを行い、並列処理フラグ（ＣＰＵ実行フラグ、ＣＰＵ参照フラグ）を複数ＣＰＵで並列に作成し、各ＣＰＵの処理するｘｉ、ｘｊ要素の決定、１回毎の並列計算ステップにおける各ＣＰＵの処理が終了したことの検出方法、また、全行の処理が終了したことの検出方法を定める必要がある。
（ａ）並列処理フラグ（ＣＰＵ実行フラグ、ＣＰＵ参照フラグ）の作成
（１）各ＣＰＵが自分の担当する並列処理フラグ作成の対象要素を設定する。
（２）ＣＰＵ１は、まず、全ＣＰＵのＣＰＵ実行フラグ、ＣＰＵ参照フラグを「０」で初期化する。
（３）次に、各ＣＰＵは、今回の並列処理対象要素について、後段のＰ（ｍ）と前段の全Ｑ（ｎ）の値とが一致するか否かチェックする。一致する場合は、並列処理が不可になるのでＣＰＵ参照フラグを設定し、全て一致しない場合は並列処理が可能になるので、ＣＰＵ実行フラグを設定する。
・並列処理対象の最初の要素は、無条件で並列処理可能とし、当該ＣＰＵのＣＰＵ実行フラグに当該ＣＰＵ番号を設定する。
・後段の要素と先行する全要素のチェックの結果、一致する場合は、当該ＣＰＵのＣＰＵ参照フラグに、参照すべき一致した要素のＱ（ｎ）を担当するＣＰＵ番号を設定する。
・後段の要素と先行する全要素のチェックの結果、全て一致しない場合は、当該要素Ｐ（ｍ）を担当するＣＰＵのＣＰＵ実行フラグに当該ＣＰＵ番号を設定する。
（４）次に、各ＣＰＵは、今回の並列処理対象要素について、後段のＰ（ｍ）と前段の全Ｐ（ｎ）の値とが一致するかチェックする。一致する場合は、並列処理が不可になるのでＣＰＵ参照フラグを設定する。全て一致しない場合は何も処理しない。
・一致する場合は、当該ＣＰＵのＣＰＵ参照フラグに、参照すべき一致した要素のＰ（ｎ）を担当するＣＰＵ番号を設定する。
・一致しない場合は、何もしない。
（５）各ＣＰＵは、自分の担当する処理が終了すれば、自ＣＰＵ処理フラグに自分のＣＰＵ番号を設定する。
（６）ＣＰＵ１は、全てのＣＰＵの処理が終了したか否かを、ＣＰＵ処理フラグから判定し、終了している場合は、並列処理フラグ作成の終了フラグを設定し、処理を終了する。
（７）ＣＰＵ１以外のＣＰＵは、並列処理フラグ作成の終了フラグをチェックし、設定済みの場合は処理を終了する。
（ｂ）処理対象ｘｉ、ｘｊ要素の決定
（１）各ＣＰＵが処理するｘｉを下記の（５）式により算出する。また、図２０は、後退代入過程２の並列処理において、４台のＣＰＵに処理を割り振り各種フラグで管理する様子を示す図である。
ｋ＝ｎｍａｘ−（Ｌ−１）・ＣＰＵmax−ＣＰＵｉ＋１ ・・・（５）
ｉ＝Ｑ（ｋ）
ｊ＝Ｐ（ｋ）
ただし、
ｎｍａｘ：ｘｉの最大要素数
Ｌ：各ＣＰＵの計算回数（ＣＰＵ１が初期化。初期値は１）
ＣＰＵｍａｘ：並列処理するＣＰＵ台数
ＣＰＵｉ：ＣＰＵ番号（ＣＰＵ１＝１、・・・、ＣＰＵｎ＝ＣＰＵｍａｘ）
（ｃ）ＣＰＵ処理フラグの管理
ＣＰＵ１が各ＣＰＵの計算回数Ｌの更新を行うためには、各ＣＰＵの処理が終了したことを確認する必要がある。これをＣＰＵ処理フラグと定義する。
（１）初期化
ＣＰＵ１が、全ＣＰＵのＣＰＵ処理フラグを、０で初期化する。
（２）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の処理が終了した時点で、ＣＰＵ処理フラグに自ＣＰＵ番号を書き込む。
（３）計算回数Ｌのカウントアップ
ＣＰＵ１は、全ＣＰＵのＣＰＵ処理フラグが正になった時点で、Ｌを１だけ、
カウントアップし、全ＣＰＵのＣＰＵ処理フラグをリセットする。
（ｄ）後退代入過程２終了フラグの管理
後退代入過程２の処理終了は、各ＣＰＵが行う。
（１）初期化
ＣＰＵ１が、後退代入過程２終了フラグを、０で初期化する。
（２）最終行の検出
各ＣＰＵが処理するｘｉの行番号が、「１」と一致した場合、最終行の処理をしたと判断し、検出したＣＰＵは、後退代入過程２終了フラグに自ＣＰＵ番号をセットする。
（３）後退代入過程２の終了
各ＣＰＵは、後退代入過程２終了フラグが正の場合、後退代入の処理が終了したと判断し、全処理の終了とする。
（ｅ）後退代入過程２の並列処理手順
（１）各ＣＰＵは、自分の担当する並列処理フラグ作成の対象要素を設定する。
（２）ＣＰＵ１が、各ＣＰＵのＣＰＵ実行フラグ、ＣＰＵ参照フラグ、ＣＰＵ処理フラグ、後退代入過程２終了フラグを初期化する。
（３）各ＣＰＵが、全てのＣＰＵ実行フラグ、ＣＰＵ参照フラグを並列に作成する。
（４）各ＣＰＵが、処理対象ｘｉ、ｘｊ要素を決定する。
（５）各ＣＰＵが、ＣＰＵ実行フラグをチェックする。
・自分のＣＰＵ番号と一致する場合は、ｘｉ要素の計算を行い、ＣＰＵ処理フラグをセットする。なお、ｘｊ要素と掛け算となるＤ要素がゼロの場合は、その処理をスキップする。
・自分のＣＰＵ番号と一致しない場合は、ＣＰＵ参照フラグが示すＣＰＵ番号について、そのＣＰＵ処理フラグをチェックする。
（ｉ）ＣＰＵ処理フラグが正の場合は、ｘｉ要素の処理を行い、ＣＰＵ処理フラ
グをセットする。
（ｉｉ）ＣＰＵ処理フラグが正でない場合は、継続チェックを行う（先行ＣＰＵの処理終了待ち）。
（６）ＣＰＵ１が、全ＣＰＵ処理フラグが正であることを確認し、Ｌを１カウントアップし、全ＣＰＵのＣＰＵ処理フラグをリセットし、（４）に戻る。
（７）各ＣＰＵは、自分が１行目を処理した場合、後退代入過程２終了フラグをセッ
トする。
（８）各ＣＰＵは、後退代入過程２終了フラグが正の場合、後退代入過程２を終了す
る。
【００９２】
本実施の形態によれば、実施の形態１〜３のいずれかのノード順序付けの結果に基づき、処理の実施前に、前進消去・後退代入処理の並列処理可能の可否を判定し、可能な場合はＣＰＵ実行フラグをセットし、不可能な場合はＣＰＵ参照フラグに参照すべきＣＰＵ番号をセットし、前進消去・後退代入処理においては、ＣＰＵ実行フラグがセットされている場合は並列処理を行い、セットされていない場合は、ＣＰＵ参照フラグより、参照すべきＣＰＵ番号を抽出し、そのＣＰＵの処理が終了したことを確認して、その後に当該ＣＰＵの処理を行うようにしたので、従来はすべて直列に処理していた前進消去・後退代入処理の並列処理を実現すると共に、並列処理の実行効率を向上させることができるという効果がある。また、図２に示すような対称型マルチＣＰＵ構成の計算機に基づき、本実施の形態にかかる連立一次方程式の並列求解方法を用いることにより、連立一次方程式の解を並列求解するための並列求解装置を構成することができる。
【図面の簡単な説明】
【００９３】
【図１】実施の形態１が適用される訓練シミュレータの構成を示す構成図である。
【図２】実施の形態１にかかる連立一次方程式の並列求解に利用される計算機構成の一例を示す図である。
【図３】実施の形態１において、系統摸擬サーバ群に実装し、系統シミュレーションを行う動態安定度計算の処理例を示すフロー図である。
【図４】非特許文献２に記載の系統例を示す図である。
【図５】図４の系統例の回路網方程式（連立一次方程式）を示す図である。
【図６】三角分解の基本的な処理を示すフロー図である。
【図７】三角分解結果の各種データを保存するテーブルの構造を示す図である。
【図８】前進消去・後退代入処理を示す処理フロー図である。
【図９】前進消去処理における並列処理の問題点を示す図である。
【図１０】後退代入処理における並列処理の問題点を示す図である。
【図１１−１】実施の形態１のノード順序付け方法を示すフロー図である。
【図１１−２】図１１−１に続くフロー図である。
【図１２】図１１−２における新規非零要素発生のシミュレーションの並列処理を示すフロー図である。
【図１３−１】実施の形態１のノード順序付けの効果を説明するための図である。
【図１３−２】実施の形態１のノード順序付けの効果を説明するための図である。
【図１３−３】実施の形態１のノード順序付けの効果を説明するための図である。
【図１３−４】実施の形態１のノード順序付けの効果を説明するための図である。
【図１４−１】実施の形態３のノード順序付け方法を示すフロー図である。
【図１４−２】図１４−１に続くフロー図である。
【図１５−１】実施の形態４における連立一次方程式の並列求解方法を示すフロー図である。
【図１５−２】図１５−１に続くフロー図である。
【図１６−１】実施の形態４の後退代入過程における並列処理フラグ作成の処理を示すフロー図である。
【図１６−２】図１６−１に続くフロー図である。
【図１７−１】実施の形態４の後退代入過程における並列処理フラグ作成の処理を示すフロー図である。
【図１７−２】図１７−１に続くフロー図である。
【図１８】前進消去過程の並列処理において、４台のＣＰＵに処理を割り振り各種フラグで管理する様子を示す図である。
【図１９】後退代入過程１の並列処理において、４台のＣＰＵに処理を割り振りＣＰＵ処理フラグで管理する様子を示す図である。
【図２０】後退代入過程２の並列処理において、４台のＣＰＵに処理を割り振り各種フラグで管理する様子を示す図である。
【図２１−１】非特許文献１に記載の単純なネットワークを示す図である。
【図２１−２】非特許文献１に記載のツリー構造の処理過程を示す図である。
【図２２】非特許文献１に記載のノード順序付けアルゴリズムを示すフロー図である。
【符号の説明】
【００９４】
１ 訓練管理サーバ群
２ 系統摸擬サーバ群
３ 自動化模擬サーバ群
４ トレーナ卓
５ トレーニ卓
６ 大画面系統盤
７ システムＬＡＮ
８ ＣＰＵ１
９ ＣＰＵ２
１０ ＣＰＵ３
１１ ＣＰＵｎ
１２ 共有メモリ
【特許請求の範囲】
【請求項１】
複数個のＣＰＵと、前記各ＣＰＵが共通にアクセス可能な共有メモリと、を有する対称型マルチＣＰＵ構成の並列計算装置を用い、係数行列の三角分解、前進消去処理、および後退代入処理に基づいて電力系統の解析における連立一次方程式の解を並列計算する際に使用され、前記係数行列の構造ならびに前記前進消去処理および前記後退代入処理の手順を、ノードおよびノード間を接続するブランチからなるツリーで表現するときのノード順序付け方法であって、
前記ツリーにおけるループを含まない系統部分である放射状系統部分に属するノードについてのノード順序付けを行う第１のステップと、
前記ツリーにおける放射状系統部分以外の系統部分であるループ状系統部分に属するノードについてのノード順序付けを行う第２のステップと、
を含み、
前記第１のステップにおいては、最初に順序付けするノードはそのノードに接続されているブランチ数が最小のノードの中から任意に選択し、以降はノード順序付け候補のノードのうち各ノードに接続されているブランチ数が少ないノードから順に選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行い、
前記第２のステップにおいては、前記複数個のＣＰＵを用いて前記前進消去処理におけるノードの縮約時に発生する新規非零要素発生数のシミュレーションを並列処理して実施し、前記シミュレーションにより得られた前記新規非零要素発生数の少ないノードから選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行うことを特徴とするノード順序付け方法。
【請求項２】
複数個のＣＰＵと、前記各ＣＰＵが共通にアクセス可能な共有メモリと、を有する対称型マルチＣＰＵ構成の並列計算装置を用い、係数行列の三角分解、前進消去処理、および後退代入処理に基づいて電力系統の解析における連立一次方程式の解を並列計算する際に使用され、前記係数行列の構造ならびに前記前進消去処理および前記後退代入処理の手順を、ノードおよびノード間を接続するブランチからなるツリーで表現するときのノード順序付け方法であって、
前記ツリーにおけるループを含まない系統部分である放射状系統部分に属するノードについてのノード順序付けを行う第１のステップと、
前記ツリーにおける放射状系統部分以外の系統部分であるループ状系統部分に属するノードについてのノード順序付けを行う第２のステップと、
を含み、
前記第１のステップにおいては、最初に順序付けするノードはそのノードに接続されているブランチ数が最小のノードの中から任意に選択し、以降はノード順序付け候補のノードのうち各ノードに接続されるブランチ数が少ないノードから順に選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行い、
前記第２のステップにおいては、前記複数個のＣＰＵのうちの単一のＣＰＵを用いて前記前進消去処理におけるノードの縮約時に発生する新規非零要素発生数のシミュレーションを実施し、前記シミュレーションにより得られた前記新規非零要素発生数が少ないノードから選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行うことを特徴とするノード順序付け方法。
【請求項３】
複数個のＣＰＵと、前記各ＣＰＵが共通にアクセス可能な共有メモリと、を有する対称型マルチＣＰＵ構成の並列計算装置を用い、係数行列の三角分解、前進消去処理、および後退代入処理に基づいて電力系統の解析における連立一次方程式の解を並列計算する際に使用され、前記係数行列の構造ならびに前記前進消去処理および前記後退代入処理の手順を、ノードおよびノード間を接続するブランチからなるツリーで表現するときのノード順序付け方法であって、
前記ツリーにおけるループを含まない系統部分である放射状系統部分に属するノードについてのノード順序付けを行う第１のステップと、
前記ツリーにおける放射状系統部分以外の系統部分であるループ状系統部分に属するノードについてのノード順序付けを行う第２のステップと、
を含み、
前記第１のステップにおいては、最初に順序付けするノードはそのノードに接続されているブランチ数が最小のノードの中から任意に選択し、以降はノード順序付け候補のノードのうち各ノードに接続されるブランチ数が少ないノードから順に選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行い、
前記第２のステップにおいては、前記複数個のＣＰＵのうちの単一のＣＰＵを用いて処理することによりノード順序付け候補のノードのうち各ノードに接続されるブランチ数が少ないノードから順に選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行うことを特徴とするノード順序付け方法。
【請求項４】
複数個のＣＰＵと、前記各ＣＰＵが共通にアクセス可能な共有メモリと、を有する対称型マルチＣＰＵ構成の並列計算装置を用い、請求項１〜３のいずれか１つに記載のノード順序付け方法を適用したノード順序付けステップと、係数行列の三角分解を行う三角分解ステップと、前進消去処理ステップと、後退代入処理ステップと、を含む処理手順に基づいて電力系統の解析における連立一次方程式の解を並列計算する並列求解方法であって、
前記前進消去処理ステップにおいては、並列処理が可能か否かを判別するための並列処理フラグを前記複数個のＣＰＵにより並列に作成し、前記並列処理フラグを参照して、並列処理が可能な要素については並列処理を実行し、並列処理が不可能な要素については当該要素の処理に必要な関連する要素の処理の終了を確認して処理を行うことにより、前進消去の並列処理を実行し、
前記後退代入処理ステップは、前記連立一次方程式の係数ベクトルの成分とこの成分に対応する前記係数行列の対角成分の逆数との積を処理対象である解ベクトルの成分に代入する処理を含む後退代入第１ステップと、この後退代入第１ステップ以降の処理である後退代入第２ステップと、を含み、
前記後退代入第１ステップにおいては、処理対象を前記複数個のＣＰＵに按分して並列処理を行い、
前記後退代入第２ステップにおいては、並列処理が可能か否かを判別するための並列処理フラグを前記複数個のＣＰＵにより並列に作成し、前記並列処理フラグを参照して、並列処理が可能な要素については並列処理を実行し、並列処理が不可能な要素については当該要素の処理に必要な関連する要素の処理の終了を確認して処理を行うことにより、後退代入の並列処理を実行することを特徴とする連立一次方程式の並列求解方法。
【請求項１】
複数個のＣＰＵと、前記各ＣＰＵが共通にアクセス可能な共有メモリと、を有する対称型マルチＣＰＵ構成の並列計算装置を用い、係数行列の三角分解、前進消去処理、および後退代入処理に基づいて電力系統の解析における連立一次方程式の解を並列計算する際に使用され、前記係数行列の構造ならびに前記前進消去処理および前記後退代入処理の手順を、ノードおよびノード間を接続するブランチからなるツリーで表現するときのノード順序付け方法であって、
前記ツリーにおけるループを含まない系統部分である放射状系統部分に属するノードについてのノード順序付けを行う第１のステップと、
前記ツリーにおける放射状系統部分以外の系統部分であるループ状系統部分に属するノードについてのノード順序付けを行う第２のステップと、
を含み、
前記第１のステップにおいては、最初に順序付けするノードはそのノードに接続されているブランチ数が最小のノードの中から任意に選択し、以降はノード順序付け候補のノードのうち各ノードに接続されているブランチ数が少ないノードから順に選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行い、
前記第２のステップにおいては、前記複数個のＣＰＵを用いて前記前進消去処理におけるノードの縮約時に発生する新規非零要素発生数のシミュレーションを並列処理して実施し、前記シミュレーションにより得られた前記新規非零要素発生数の少ないノードから選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行うことを特徴とするノード順序付け方法。
【請求項２】
複数個のＣＰＵと、前記各ＣＰＵが共通にアクセス可能な共有メモリと、を有する対称型マルチＣＰＵ構成の並列計算装置を用い、係数行列の三角分解、前進消去処理、および後退代入処理に基づいて電力系統の解析における連立一次方程式の解を並列計算する際に使用され、前記係数行列の構造ならびに前記前進消去処理および前記後退代入処理の手順を、ノードおよびノード間を接続するブランチからなるツリーで表現するときのノード順序付け方法であって、
前記ツリーにおけるループを含まない系統部分である放射状系統部分に属するノードについてのノード順序付けを行う第１のステップと、
前記ツリーにおける放射状系統部分以外の系統部分であるループ状系統部分に属するノードについてのノード順序付けを行う第２のステップと、
を含み、
前記第１のステップにおいては、最初に順序付けするノードはそのノードに接続されているブランチ数が最小のノードの中から任意に選択し、以降はノード順序付け候補のノードのうち各ノードに接続されるブランチ数が少ないノードから順に選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行い、
前記第２のステップにおいては、前記複数個のＣＰＵのうちの単一のＣＰＵを用いて前記前進消去処理におけるノードの縮約時に発生する新規非零要素発生数のシミュレーションを実施し、前記シミュレーションにより得られた前記新規非零要素発生数が少ないノードから選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行うことを特徴とするノード順序付け方法。
【請求項３】
複数個のＣＰＵと、前記各ＣＰＵが共通にアクセス可能な共有メモリと、を有する対称型マルチＣＰＵ構成の並列計算装置を用い、係数行列の三角分解、前進消去処理、および後退代入処理に基づいて電力系統の解析における連立一次方程式の解を並列計算する際に使用され、前記係数行列の構造ならびに前記前進消去処理および前記後退代入処理の手順を、ノードおよびノード間を接続するブランチからなるツリーで表現するときのノード順序付け方法であって、
前記ツリーにおけるループを含まない系統部分である放射状系統部分に属するノードについてのノード順序付けを行う第１のステップと、
前記ツリーにおける放射状系統部分以外の系統部分であるループ状系統部分に属するノードについてのノード順序付けを行う第２のステップと、
を含み、
前記第１のステップにおいては、最初に順序付けするノードはそのノードに接続されているブランチ数が最小のノードの中から任意に選択し、以降はノード順序付け候補のノードのうち各ノードに接続されるブランチ数が少ないノードから順に選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行い、
前記第２のステップにおいては、前記複数個のＣＰＵのうちの単一のＣＰＵを用いて処理することによりノード順序付け候補のノードのうち各ノードに接続されるブランチ数が少ないノードから順に選択するとともに、ノード順序付け候補のノードとそれにブランチを介して接続された隣接ノードである相手端ノードが順序付け済みのノードの相手端ノードと一致しないノードである場合に当該ノード順序付け候補のノードを優先して選択する、という選択基準に基づいて前記複数個のＣＰＵ単位にノード順序付けを行うことを特徴とするノード順序付け方法。
【請求項４】
複数個のＣＰＵと、前記各ＣＰＵが共通にアクセス可能な共有メモリと、を有する対称型マルチＣＰＵ構成の並列計算装置を用い、請求項１〜３のいずれか１つに記載のノード順序付け方法を適用したノード順序付けステップと、係数行列の三角分解を行う三角分解ステップと、前進消去処理ステップと、後退代入処理ステップと、を含む処理手順に基づいて電力系統の解析における連立一次方程式の解を並列計算する並列求解方法であって、
前記前進消去処理ステップにおいては、並列処理が可能か否かを判別するための並列処理フラグを前記複数個のＣＰＵにより並列に作成し、前記並列処理フラグを参照して、並列処理が可能な要素については並列処理を実行し、並列処理が不可能な要素については当該要素の処理に必要な関連する要素の処理の終了を確認して処理を行うことにより、前進消去の並列処理を実行し、
前記後退代入処理ステップは、前記連立一次方程式の係数ベクトルの成分とこの成分に対応する前記係数行列の対角成分の逆数との積を処理対象である解ベクトルの成分に代入する処理を含む後退代入第１ステップと、この後退代入第１ステップ以降の処理である後退代入第２ステップと、を含み、
前記後退代入第１ステップにおいては、処理対象を前記複数個のＣＰＵに按分して並列処理を行い、
前記後退代入第２ステップにおいては、並列処理が可能か否かを判別するための並列処理フラグを前記複数個のＣＰＵにより並列に作成し、前記並列処理フラグを参照して、並列処理が可能な要素については並列処理を実行し、並列処理が不可能な要素については当該要素の処理に必要な関連する要素の処理の終了を確認して処理を行うことにより、後退代入の並列処理を実行することを特徴とする連立一次方程式の並列求解方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１−１】
【図１１−２】
【図１２】
【図１３−１】
【図１３−２】
【図１３−３】
【図１３−４】
【図１４−１】
【図１４−２】
【図１５−１】
【図１５−２】
【図１６−１】
【図１６−２】
【図１７−１】
【図１７−２】
【図１８】
【図１９】
【図２０】
【図２１−１】
【図２１−２】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１−１】
【図１１−２】
【図１２】
【図１３−１】
【図１３−２】
【図１３−３】
【図１３−４】
【図１４−１】
【図１４−２】
【図１５−１】
【図１５−２】
【図１６−１】
【図１６−２】
【図１７−１】
【図１７−２】
【図１８】
【図１９】
【図２０】
【図２１−１】
【図２１−２】
【図２２】
【公開番号】特開２００８−２９９６４１（Ｐ２００８−２９９６４１Ａ）
【公開日】平成２０年１２月１１日（２００８．１２．１１）
【国際特許分類】
【出願番号】特願２００７−１４５６３９（Ｐ２００７−１４５６３９）
【出願日】平成１９年５月３１日（２００７．５．３１）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２０年１２月１１日（２００８．１２．１１）
【国際特許分類】
【出願日】平成１９年５月３１日（２００７．５．３１）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]