(57)【要約】【課題】連立一次方程式の解を高速に求めることが可能な連立一次方程式の並列求解装置を得ること。【解決手段】この発明の連立一次方程式の並列求解装置によれば、行単位に並列処理する方法を採用し、ＬＵ分解では、各要素の実行可否を当該要素の処理フラグの設定、確認により制御し、また、前進消去、後退代入の処理では、当該ＣＰＵで計算した解について、後段のＣＰＵで処理する計算項目も当該ＣＰＵで計算して後段のＣＰＵにデータを受渡し、また、各要素の実行可否を当該要素の処理フラグの設定、確認により、制御することにより、各ＣＰＵの演算量を減少させ、各ＣＰＵの演算量のバランスを図ることにより、並列処理の効率性を向上させて、連立一次方程式を高速に求解できるようにした。【選択図】          図４−１
2008176738.tif 000002
【特許請求の範囲】
【請求項１】
複数の演算処理部を備え、係数行列Ａを下三角行列Ｌと上三角行列Ｕとの積に分解するＬＵ分解を利用して、Ａを係数行列とする連立一次方程式Ａｘ＝ｂ（但し、ｘ、ｂは列ベクトル）の解ｘを並列的に求める並列求解装置であって、
行単位の並列処理を行うために、前記各演算処理部が処理するＡの行を前記各演算処理部に割り当てる行割り当て手段と、
この行割り当て手段により割り当てられた行におけるＬ要素および／またはＵ要素の演算処理を行う一の演算処理部に対して、前記割り当てられた行の行番号よりも大きい行番号の行が割り当てられた他の演算処理部において、前記Ｌ要素および／またはＵ要素の演算処理に必要なＵ要素の演算処理が終了しているか否かを判別するためのＵ要素処理フラグを管理するＵ要素処理フラグ管理手段と、
前記Ｌ要素および／またはＵ要素の演算処理に必要なＵ要素の受け渡しを含む前記演算処理部間のデータの受け渡しに利用される共有メモリと、
前記各演算処理部に対して、前記Ｕ要素処理フラグに基づいて前記Ｌ要素および／またはＵ要素の演算処理に必要なＵ要素の演算処理が終了していることを確認した後に、前記共有メモリを介して前記Ｌ要素および／またはＵ要素の演算処理に必要なＵ要素を取得するＵ要素取得手段と、
を備えることを特徴とする連立一次方程式の並列求解装置。
【請求項２】
前記各演算処理部に対して、前記Ｌ要素および／またはＵ要素の演算処理を含む一つの行についての行単位の処理を終了したか否かを判別するための演算処理フラグを管理する演算処理フラグ管理手段を備えることを特徴とする請求項１に記載の連立一次方程式の並列求解装置。
【請求項３】
前記係数行列ＡのＬＵ分解が終了したか否かを判別するためのＬＵ分解処理終了フラグを管理するＬＵ分解処理終了フラグ管理手段を備えることを特徴とする請求項２に記載の連立一次方程式の並列求解装置。
【請求項４】
複数の演算処理部を備え、係数行列Ａを下三角行列Ｌと上三角行列Ｕとの積に分解するＬＵ分解を利用して、Ａを係数行列とする連立一次方程式Ａｘ＝ｂ（但し、ｘ、ｂは列ベクトル）の解ｘを並列的に求め、前記係数行列ＡのＬＵ分解の結果に基づき、Ｌｙ＝ｂの解ｙを並列的に求める前進消去の処理を行う並列求解装置であって、
行単位の並列処理を行うために、前記各演算処理部が処理するｙの行を前記各演算処理部に割り当てる行割り当て手段と、
この行割り当て手段により割り当てられた行におけるｙ要素の演算処理を行う一の演算処理部に対して、前記割り当てられた行の行番号よりも大きい行番号の行が割り当てられた他の演算処理部において、前記ｙ要素の演算処理に必要なＬ要素とｙ要素との積からなるＬＬ行列の要素であるＬＬ要素の演算処理が終了しているか否かを判別するためのＬＬ要素処理フラグを管理するＬＬ要素処理フラグ管理手段と、
前記ｙ要素の演算処理に必要なＬＬ要素の受け渡しを含む前記演算処理部間のデータの受け渡しに利用される共有メモリと、
前記各演算処理部に対して、前記ＬＬ要素処理フラグに基づいて前記ｙ要素の演算処理に必要なＬＬ要素の演算処理が終了していることを確認した後に、前記共有メモリを介して前記ｙ要素の演算処理に必要なＬＬ要素を取得するＬＬ要素取得手段と、
を備えることを特徴とする連立一次方程式の並列求解装置。
【請求項５】
前記各演算処理部に対して、前記ｙ要素およびＬＬ要素の演算処理を含む一つの行についての行単位の処理を終了したか否かを判別するための演算処理フラグを管理する演算処理フラグ管理手段を備えることを特徴とする請求項４に記載の連立一次方程式の並列求解装置。
【請求項６】
前記前進消去の処理が終了したか否かを判別するための前進消去終了フラグを管理する前進消去終了フラグ管理手段を備えることを特徴とする請求項５に記載の連立一次方程式の並列求解装置。
【請求項７】
複数の演算処理部を備え、係数行列Ａを下三角行列Ｌと上三角行列Ｕとの積に分解するＬＵ分解を利用して、Ａを係数行列とする連立一次方程式Ａｘ＝ｂ（但し、ｘ、ｂは列ベクトル）の解ｘを並列的に求め、前記係数行列ＡのＬＵ分解の結果に基づき、Ｕｘ＝ｙの解ｘを並列的に求める後退代入の処理を行う並列求解装置であって、
行単位の並列処理を行うために、前記各演算処理部が処理するｘの行を前記各演算処理部に割り当てる行割り当て手段と、
この行割り当て手段により割り当てられた行におけるｘ要素の演算処理を行う一の演算処理部に対して、前記割り当てられた行の行番号よりも小さい行番号の行が割り当てられた他の演算処理部において、前記ｘ要素の演算処理に必要なＵ要素とｘ要素との積からなるＵＵ行列の要素であるＵＵ要素の演算処理が終了しているか否かを判別するためのＵＵ要素処理フラグを管理するＵＵ要素処理フラグ管理手段と、
前記ｘ要素の演算処理に必要なＵＵ要素の受け渡しを含む前記演算処理部間のデータの受け渡しに利用される共有メモリと、
前記各演算処理部に対して、前記ＵＵ要素処理フラグに基づいて前記ｘ要素の演算処理に必要なＵＵ要素の演算処理が終了していることを確認した後に、前記共有メモリを介して前記ｘ要素の演算処理に必要なＵＵ要素を取得するＵＵ要素取得手段と、
を備えることを特徴とする連立一次方程式の並列求解装置。
【請求項８】
前記各演算処理部に対して、前記ｘ要素およびＵＵ要素の演算処理を含む一つの行についての行単位の処理を終了したか否かを判別するための演算処理フラグを管理する演算処理フラグ管理手段を備えることを特徴とする請求項７に記載の連立一次方程式の並列求解装置。
【請求項９】
前記後退代入の処理が終了したか否かを判別するための後退代入終了フラグを管理する後退代入終了フラグ管理手段を備えることを特徴とする請求項８に記載の連立一次方程式の並列求解装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、連立一次方程式の並列求解装置に関し、特に、給電指令所、制御所等の運転員の平常時、事故時における系統運用に関する技術、技能などの維持・向上を図るための訓練シミュレータの系統シミュレーション手法である周波数・潮流計算（連結）方式の潮流計算における連立一次方程式の求解に関するものである。
【背景技術】
【０００２】
一般に、連立一次方程式を解くためには行列を高速にＬＵ分解する必要がある。これは連立一次方程式の係数行列Ａを、下三角行列Ｌと上三角行列Ｕとの積に分解して解く方法である。ＬＵ分解による解法には様々なものがあり、例えば非特許文献１にＬＵ分解の並列処理に関する従来技術が記載されている。非特許文献１に記載されている方法は、連立一次方程式を列単位で並列処理する方法である。しかし、前記並列処理において、各プロセッサの待ち時間が大きくなるということから、それを改善するために、特許文献１に記載の従来技術が開示されている。以下、特許文献１の内容を示す。
【０００３】
連立一次方程式を、下記（１）式で表す。
Ａ・ｘ＝ｂ                                                    ・・・（１）
【０００４】
ここで、Ａは正方行列、ｘ、ｂはベクトルとする。Ａは連立一次方程式の係数行列である。
【０００５】
図１１は、一般的なＬＵ分解の処理過程を示すフローチャートであり、以下、このフローチャートに基づいて説明する。図１１に示すように、ステップ３９で行列Ａの（ｉ，ｊ）成分を（ｉ，ｉ）成分で割る。次に繰り返し変数をｋとして、ｋ＝ｉ＋１，ｉ＋２，・・，ｎに対して、ステップ４０でＡの（ｋ，ｊ）成分から（ｉ，ｊ）成分と（ｋ，ｉ）成分を乗じたものを減ずる。ステップ３９，４０の処理をＰ（ｊ，ｉ）で表し、この処理を、繰り返し変数をｊとして、ｊ＝ｉ＋１，ｉ＋２，・・，ｎに対して行う。さらに、ステップ４１でｂのｉ成分をＡ（ｉ，ｉ）成分で割る。次に繰り返し変数をｋとして、ｋ＝ｉ＋１，ｉ＋２，・・，ｎに対してステップ４２でｂのｋ成分からｉ成分とＡの（ｋ，ｉ）成分を乗じたものを減ずる。ステップ４１，４２の処理をＰｂ（ｉ）で表し、このＰ（ｊ，ｉ），Ｐｂ（ｉ）の処理をｉ＝１，２，３，・・，ｎに対して実行する。この処理を実行することにより、いわゆる前進代入が行われる。
【０００６】
前進代入後、ステップ４３では、ｂのｊ成分からｂの第ｉ成分とＡの（ｊ，ｉ）成分を乗じたものを減ずる。ステップ４３を、繰り返し変数をｊとして、ｊ＝ｉ−１，ｉ−２，・・，１に対して実行する処理をＰｃ（ｉ）で表し、さらに繰り返し変数をｉとして、ｉ＝ｎ，ｎ−１，・・，２に対して実行すれば、いわゆる後退代入が行われる。
【０００７】
ここまでの処理で変化したＡの対角成分と下三角行列に−１を掛けて合わせたものがＬ行列であり、単位行列とＡの上三角行列を合わせたものがＵ行列となる。また、ベクトルｂは上記（１）式に示す連立一次方程式の解ｘに変化する。
【０００８】
上記のようなＬＵ分解を計算する際、従来、並列処理を行うことにより高速化している。すなわち、並列化とは、処理Ｐ（ｊ，ｉ）を係数行列Ａの列毎、すなわち変数ｊの値により分けて、分けたものを各プロセッサで処理する方法である。ここで、処理する順序には制約があり、例えば疎でない行列を処理するときには図１２に示すような順序で処理を行う必要がある。図１２において、矢印は、始点の処理が終点の処理よりも先に実行される必要があることを表現している。図１２からわかるように、第ｊ列に対する処理単位Ｐ（ｊ，ｉ）（ｉ＝１，２，・・，ｊ−１）は、ｊの小さい順に実行しなければならないが、処理Ｐ（ｉ＋１，ｉ）、（ｉ＋２，ｉ），・・，Ｐ（ｎ，ｉ），Ｐｂ（ｉ）（ｉ＝１，２，・・，ｎ）は並列に処理できる。
【０００９】
図１３は、このＬＵ分解を並列に計算するための求解装置の構成を示すブロック図である。図１３において、４４はマスタプロセッサ、４５は列ベクトル処理用プロセッサ、４６はベクトルｂ処理用プロセッサである。列ベクトル処理用プロセッサ４５は、並列処理のために複数個設けられている。マスタプロセッサ４４は、各列ベクトル処理用プロセッサ４５、ベクトルｂ処理用プロセッサ４６に、列ベクトル、ベクトルｂを割り当て、必要なデータを送信する。図１４は、マスタプロセッサ４４の処理を示すフローチャートである。ステップ４７でベクトルｂをベクトルｂ処理用プロセッサ４６に送信する。また、ステップ４８で行列の各列を列ベクトル処理用プロセッサ４５に割り当てる。
【００１０】
列ベクトル処理用プロセッサ４５は、マスタプロセッサ４４から行列Ａの列ベクトルを受取り、必要な処理を行う。図１５は、列ベクトル処理用プロセッサ４５の処理手順を示すフローチャートである。ステップ４９でマスタプロセッサ４４からの列の割り当てを待つ。列が割り当てられたら、ステップ５０で実行可能な処理Ｐ（ｊ，ｉ）が存在するか否かを判断する。ここで実行可能な処理Ｐ（ｊ、ｉ）が存在しない場合は、ステップ５１で下三角成分Ａ（ｋ，ｋ），Ａ（ｋ＋１，ｋ），・・，Ａ（ｎ，ｋ）の受信待ちをし、ステップ５０に戻る。ここで、ｋは任意の整数である。ステップ５０の判断で、実行可能な処理Ｐ（ｊ，ｉ）が存在する場合、ステップ５２で実行可能な処理Ｐ（ｊ，ｉ）を実行する。ステップ５０における処理Ｐ（ｊ，ｉ）の実行可能判定方法と、ステップ５２における実行可能なＰ（ｊ，ｉ）の実行については、後に詳述する。
【００１１】
次に，ステップ５３で下三角成分Ａ（ｊ，ｊ），Ａ（ｊ＋１，ｊ），・・，Ａ（ｎ，ｊ）は確定したか否かを判別する。この判別方法については、後に詳述する。判別の結果、確定していれば、ステップ５４にて下三角成分Ａ（ｊ，ｊ），Ａ（ｊ＋１，ｊ），・・，Ａ（ｎ，ｊ）を他のプロセッサに送信し、ステップ５５で、列ｊに対する処理Ｐ（ｊ，ｉ）（ｉ＝１，２，・・，ｊ−１）は全て終了したかどうか判別する。終了した場合は、ステップ５６で上三角成分（１，ｊ），Ａ（２，ｊ），・・，Ａ（ｊ−１，ｊ）をベクトルｂ処理用プロセッサ４６に送信する。ステップ５７で割り当てられた全ての列について、全ての処理が終了したかどうか判断し、終了した場合、処理を終了する。ステップ５５，５７で終了でないと判別した場合、ステップ５０に戻り、全ての処理が終了するまで繰返す。このように、１つの列ベクトル処理用プロセッサ４５は実行前に単数または複数の列を割り当てられ、割り当てられた全ての列についての終了したとき、処理終了となる。
【００１２】
次に、図１５のステップ５０における処理Ｐ（ｊ，ｉ）の実行可能判別方法について説明する。図１６は、処理Ｐ（ｊ，ｉ）の実行可能判別方法を示すフローチャートである。Ａ（ｉ，ｉ），Ａ（ｉ＋１，ｉ），・・，Ａ（ｎ，ｉ）が使用できる状態にあるかどうかを判別するステップ５８、および処理Ｐ（ｊ，ｉ−１）が終了しているかどうかを判別するステップ５９で、必要な行要素が使用できる状態にあり、かつ処理Ｐ（ｊ，ｉ−１）が終了している場合には、処理Ｐ（ｊ，ｉ）は実行可能と判別する。（ステップ６０）。Ａ（ｉ，ｉ），Ａ（ｉ＋１，ｉ），・・，Ａ（ｎ，ｉ）が使用できる状態にないか、または処理Ｐ（ｊ，ｉ−１）が終了していない場合には、処理Ｐ（ｊ，ｉ）は実行可能でないと判別する（ステップ６１）。
【００１３】
ここで、図１６におけるステップ５８の、Ａ（ｉ，ｉ），Ａ（ｉ＋１，ｉ），・・，Ａ（ｎ，ｉ）は使用できる状態にあるかどうかの判定方法を、図１７のフローチャートに示す。ステップ６２で、第ｉ列を割振られているかどうかを判別し、割振られている場合はステップ６３にて、Ａ（ｉ，ｉ），Ａ（ｉ＋１，ｉ），・・，Ａ（ｎ，ｉ）は確定したかどうか判別する。確定した場合、Ａ（ｉ，ｉ），Ａ（ｉ＋１，ｉ），・・，Ａ（ｎ，ｉ）は使用できると判定し（ステップ６５）、確定していない場合、使用できないと判定する（ステップ６６）。また、第ｉ列を割振られていない場合、ステップ６４にて、Ａ（ｉ，ｉ），Ａ（ｉ＋１，ｉ），・・，Ａ（ｎ，ｉ）を他のプロセッサから受信したかどうか判別する。受信した場合、Ａ（ｉ，ｉ），Ａ（ｉ＋１，ｉ），・・，Ａ（ｎ，ｉ）は使用できると判定し（ステップ６５）、受信していない場合、使用できないと判定する（ステップ６６）。
【００１４】
次に、図１５のステップ５２における実行可能な処理Ｐ（ｊ，ｉ）の実行について説明する。図１８は、実行可能な処理Ｐ（ｊ，ｉ）の実行を示すフローチャートである。ｉを１に初期設定し（ステップ６７）、処理Ｐ（ｊ，ｉ）は実行可能かどうか判別する（ステップ６８）。実行不可能な場合は、ｉ＝ｉ＋１として（ステップ６９）、ステップ６８に戻り、実行可能な場合、処理Ｐ（ｊ，ｉ）を実行する（ステップ７０）。
【００１５】
次に、図１２のステップ５３における下三角成分Ａ（ｊ，ｊ），Ａ（ｊ＋１，ｊ），・・，Ａ（ｎ，ｊ）の確定の判別方法について説明する。図１９は、この判別方法を示すフローチャートである。ステップ７１で処理Ｐ（ｊ，ｉ）（ｉ＝１，２，・・，ｊ−１）は全て終了したかどうか判定する。全て終了した場合は、Ａ（ｊ，ｊ），Ａ（ｊ＋１、ｊ），・・，Ａ（ｎ，ｊ）は確定したと判定する（ステップ７２）。全て終了していない場合は、Ａ（ｊ，ｊ），Ａ（ｊ＋１，ｊ），・・，Ａ（ｎ，ｊ）は確定していないと判定する（ステップ７３）。
【００１６】
次に、ベクトルｂ処理用プロセッサ４６の処理について説明する。図２０はベクトルｂ処理用プロセッサ４６の処理手順を示すフローチャートである。ベクトルｂをマスタプロセッサ４４から受信する（ステップ７４）。ステップ７５でＰｂ（ｉ）の実行可能なものを実行する。続いて、Ｐｂ（ｉ）の処理がすべて終了したかどうかを判別し（ステップ７６）、終了していない場合、下三角成分、上三角成分を受信して（ステップ７７）、ステップ７５に戻る。Ｐｂ（ｉ）の処理が全て終了した場合、必要があれば上三角成分を受信し（ステップ７８）、ベクトルｂの後退代入を実行する（ステップ７９）。
【００１７】
従来のＬＵ分解の並列処理方法は、上記のように構成されており、処理Ｐ（ｊ，ｉ）と処理Ｐｂ（ｉ）は、列ベクトル処理用プロセッサ４５とベクトルｂ処理用プロセッサ４６を用いることにより、並列に行うことができる。しかしながら、行列Ａの列ベクトルを割り与えられた一つの列ベクトル処理用プロセッサ４５は、Ｐ（ｊ，ｉ）の処理を異なるｉに対して複数回行わなければならず、従来の処理方法では、これをｉの小さい順番に処理していたため、待ち時間が増加しているという問題点があった。
【００１８】
これに対して、特許文献１では、以下の手順により、この問題点が解決できるとしている。すなわち、特許文献１に記載の並列ＬＵ分解の処理方法は、ｎ行ｎ列の正方行列ＡのＬＵ分解の演算処理を処理単位
Ｐ（ｊ，ｉ）：
ａ：行列Ａの（ｉ，ｊ）成分を（ｉ，ｉ）成分で割る。
ｂ：繰り返し変数ｋに対して、ｋ＝ｉ＋１，ｉ＋２，・・，ｎについて、行列Ａの（ｋ，ｊ）成分から（ｋ，ｉ）成分と（ｉ，ｊ）成分を乗じたものを減ずる。
ｊ＝２，３，・・，ｎ
ｉ＝１，２，・・，ｊ−１
に分け、列毎の演算を複数の列ベクトル処理用プロセッサで分担して並列に処理する際、行列Ａの非零要素の位置から処理Ｐ（ｊ，ｉ），Ｐ（ｊ，２），・・，Ｐ（ｊ，ｉ−１）の中で処理Ｐ（ｊ，ｉ）よりも先に実行する必要のものを求め、処理Ｐ（ｊ，ｉ），Ｐ（ｊ，２），・・，Ｐ（ｊ，ｉ−１）の中で処理Ｐ（ｊ，ｉ）よりも先に実行する必要のあるものと処理Ｐ（ｉ，１），Ｐ（ｉ，２），・・，Ｐ（ｉ，ｉ−１）とが終了した時点で、処理（ｊ，ｉ）の実行を可能としたものである。
【００１９】
【特許文献１】特開平７−１２９５４４号公報
【非特許文献１】大山力  著「疎行列処理の並列化による電力系統解析の高速化」電気学会論文誌Ｂ、１１２巻７号、ｐｐ．６０９−６１４、平成４年
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、上記従来の技術によれば以下に示すような問題点があった。すなわち、特許文献１に開示された従来技術においては、連立一次方程式の並列処理の問題点を解決するために、処理方法の改善を行っているが、処理Ｐ（ｊ，ｉ）よりも先に実行する必要のある処理、また、処理Ｐ（ｊ，ｉ）が終了した時点で実行する必要のある処理の判別は、多数の要素について判定を行う必要があり、相当な処理時間がかかるため、処理時間の短縮が困難であるという問題点があった。
【００２１】
さらに、特許文献１においては、行列を列毎に複数のプロセッサで並列処理しており、本発明が開示する行毎に並列処理する方法に比較して、各プロセッサ間の受渡しデータが多くなり、かつ、各ＣＰＵ間の演算量のアンバランスが大きく、並列処理には不向きな処理方法となっており、高速化には解決すべき問題点があった。
【００２２】
このように従来の技術によれば、連立一次方程式の並列求解方法は、連立一次方程式を列単位に、複数のプロセッサで処理しているが、並列処理の待ち時間の短縮を行うための並列処理が可能な要素の判定、また、当該の処理後でないと処理できない要素の判定に、処理時間を必要とし、さらに、各プロセッサ間の受渡しデータが多くなり、かつ、各ＣＰＵ間の演算量のアンバランスが大きく、結果的に並列処理の効率が低下するという問題点があった。
【００２３】
この発明は、上記に鑑みてなされたものであって、連立一次方程式の解を高速に求めることが可能な連立一次方程式の並列求解装置を得ることを目的とする。
【課題を解決するための手段】
【００２４】
上述した課題を解決し、目的を達成するために、本発明にかかる連立一次方程式の並列求解装置は、複数の演算処理部を備え、係数行列Ａを下三角行列Ｌと上三角行列Ｕとの積に分解するＬＵ分解を利用して、Ａを係数行列とする連立一次方程式Ａｘ＝ｂ（但し、ｘ、ｂは列ベクトル）の解ｘを並列的に求める並列求解装置であって、行単位の並列処理を行うために、前記各演算処理部が処理するＡの行を前記各演算処理部に割り当てる行割り当て手段と、この行割り当て手段により割り当てられた行におけるＬ要素および／またはＵ要素の演算処理を行う一の演算処理部に対して、前記割り当てられた行の行番号よりも大きい行番号の行が割り当てられた他の演算処理部において、前記Ｌ要素および／またはＵ要素の演算処理に必要なＵ要素の演算処理が終了しているか否かを判別するためのＵ要素処理フラグを管理するＵ要素処理フラグ管理手段と、前記Ｌ要素および／またはＵ要素の演算処理に必要なＵ要素の受け渡しを含む前記演算処理部間のデータの受け渡しに利用される共有メモリと、前記各演算処理部に対して、前記Ｕ要素処理フラグに基づいて前記Ｌ要素および／またはＵ要素の演算処理に必要なＵ要素の演算処理が終了していることを確認した後に、前記共有メモリを介して前記Ｌ要素および／またはＵ要素の演算処理に必要なＵ要素を取得するＵ要素取得手段と、を備えることを特徴とする。
【発明の効果】
【００２５】
この発明によれば、ＬＵ分解を利用した連立一次方程式の求解において、複数の演算処理部を用いて行単位に並列処理する方法を採用し、各要素の実行可否を当該要素の処理フラグの設定、確認により制御することにより、各演算処理部の演算量を減少させ、各演算処理部の演算量のバランスを図ることにより、並列処理の効率性を向上させて、連立一次方程式を高速に求解できるという効果を奏する。
【発明を実施するための最良の形態】
【００２６】
以下に、本発明にかかる連立一次方程式の並列求解装置の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００２７】
実施の形態
図１は、本実施の形態にかかる連立一次方程式の並列求解装置が適用された訓練シミュレータである訓練装置の構成を示す図である。図１に示すように、本実施の形態における訓練装置は、トレーナ（指導者）が訓練シナリオの設定等のために使用するトレーナ卓４と、訓練シナリオ作成等の支援機能を備え、訓練管理を行う訓練管理サーバ群１と、訓練シナリオに基づいて系統シミュレーションを実行する系統模擬サーバ群２と、系統シミュレーション結果が表示される大画面系統盤６と、トレーニ（被訓練者）が系統シミュレーション結果に応じて指令、操作等を行うために使用するトレーニ卓５と、トレーニが実勤務において使用している給電指令所、制御所等における計算機システムに実装されているソフトウェアの機能を模擬する自動化模擬サーバ群３と、これらの構成要素を接続するシステムＬＡＮ７と、を備えている。なお、本実施の形態にかかる連立一次方程式の並列求解装置は系統模擬サーバ群２により実現される。
【００２８】
図１においては、まず、訓練を実施するための訓練の問題となる系統構成状態、発電機・負荷条件、事故発生条件等からなる訓練シナリオを、トレーナが訓練管理サーバ群１、トレーナ卓４を使用して作成し、登録する。次に、訓練実施時には、トレーナがトレーナ卓４から登録した訓練シナリオを選択して、実時間で実行するが、それに伴い、系統摸擬サーバ群２で系統シミュレーションが実行され、その計算結果がトレーナ卓４、トレーニ卓５、および大画面系統盤６に表示される。トレーニは自動化摸擬サーバ群３、トレーニ卓５、大画面系統盤６を使用して、事故発生状況を確認、把握して、事故復旧操作のための復旧指令、復旧操作等を行い、停電している負荷の復旧等を行う。一方、訓練実施中の系統シミュレーションは、系統摸擬サーバ群２で実行されるが、この系統模擬サーバ群２は本実施の形態にかかる連立一次方程式の求解装置を備え、この求解装置の動作に基づいて系統の静的、動的特性をシミュレーションする。訓練管理サーバ群１、系統摸擬サーバ群２、自動化摸擬サーバ群３間の情報の送受信、また、トレーナ卓４、トレーニ卓５、大画面系統盤６へのデータ送信は、システムＬＡＮ７を介して行う。
【００２９】
図３は、系統摸擬機能サーバ群２に実装し、系統シミュレーションを行う周波数・潮流計算（連結）方式の処理例を示すフローチャートである。周波数・潮流計算（連結）方式は、通常、３秒周期で、系統の周波数、母線電圧、位相角、送電線等の有効電力、無効電力潮流を計算する。なお、系統周波数は、例えば０．１秒刻みで、３秒間の系統周波数の計算を行う。
【００３０】
図３においては、まず、前回の計算周期から今回の計算周期の間に発生している状態変化の取り込み処理を行い（ステップ１３）、その系統状態における潮流計算を実行し（ステップ１４−１）、今回の計算周期における初期系統断面を求める。次に、系統周波数の計算（ステップ１５）を、Δｔ刻みに実施し、計算された系統周波数について、周波数応動モデル処理（ステップ１６）の処理を行い、それをＮｆ回（Ｎｆ＝系統計算周期／Δｔ）繰返し、それを周波数計算終了（１周期）で判定する（ステップ１７）。周波数応動モデルとしては、発電機の制御系であるガバナ・タービン系の処理と系統保護装置である周波数低下リレー（ＵＦ）、周波数上昇リレー（ＯＦ）が対象になる。次に、系統周波数計算終了時点（３秒後）で潮流計算を行い（ステップ１４−２）、前回の最終断面と今回の断面の母線電圧、有効電力を使用して、潮流応動モデル１処理（ステップ１８）、潮流応動モデル処理２処理（ステップ１９）を実施する。潮流応動モデル１では、電圧・無効電力制御装置（ＶＱＣ）の模擬を行い、潮流応動モデル２処理では、過負荷リレー（ＯＬＲ）、系統安定化装置等の模擬を行う。次に、これらの各モデルが動作した系統断面の潮流計算を実行する（ステップ１４−３）。この潮流計算結果は、トレーニ（被訓練者）側に送信され、大画面系統盤、ＣＲＴ画面等に表示される。最後に、系統計算周期である３秒に対して、リアルタイム同期（３秒）を取り（ステップ２０）、１回の系統計算を終了する。本実施の形態では、この処理フローにおける潮流計算の並列求解を行うアルゴリズムとそのアルゴリズムが実装された並列求解装置を提供する。
【００３１】
図２は、本実施の形態にかかる連立一次方程式の並列求解装置を実現する計算機構成の一例を示す図である。図２に示すように、本実施の形態における計算機は、例えば、対称型マルチＣＰＵ構成の計算機であり、複数のＣＰＵであるＣＰＵ１（８）、ＣＰＵ２（９）、ＣＰＵ３（１０）、・・・、ＣＰＵｎ（１１）と、各ＣＰＵが共通にアクセス可能な共有メモリ１２と、を含んで構成される。ここで、ｎは２以上の任意の整数である。なお、各ＣＰＵは、キャッシュメモリ、ローカルメモリ、および外部記憶装置を実装しており、システムＬＡＮ７と接続している。
【００３２】
次に、本実施の形態による連立一次方程式の並列求解方法について、具体的に説明する。正則な正方行列Ａは、次のように、二つの行列の積に分解して表現することができる。
【００３３】
Ａ＝Ｌ・Ｕ                                                        ・・・（２）
【００３４】
ここで、Ｌ：下三角行列、対角要素を含まない右上三角部分の要素が全て零の行列であり、Ｕ：上三角行列、対角要素が全て１、かつ左下三角部分の要素が全て零の行列である。このような表現を、行列Ａの三角化分解またはＬＵ分解という。
【００３５】
例えば、Ａが（４×４）の行列の場合に、行列の要素で三角化分解を表すと下記（３）式のようになる。
【００３６】
【数１】
2008176738.tif 000003
【００３７】
すなわち、左辺が行列Ａを表し、右辺が行列Ｌと行列Ｕとの積を表している。ここで分解された行列の各要素は、以下に示す手順で次々に決めて行くことができる。
【００３８】
ａ１１＝Ｌ１１                ∴Ｌ１１＝ａ１１                      ・・・（４）
ａ１２＝Ｌ１１Ｕ１２          ∴Ｕ１２＝ａ１２／Ｌ１１              ・・・（５）
ａ１３＝Ｌ１１Ｕ１３          ∴Ｕ１３＝ａ１３／Ｌ１１              ・・・（６）
ａ１４＝Ｌ１１Ｕ１４          ∴Ｕ１４＝ａ１４／Ｌ１１              ・・・（７）
ａ２１＝Ｌ２１                ∴Ｌ２１＝ａ２１                      ・・・（８）
ａ２２＝Ｌ２１Ｕ１２＋Ｌ２２  ∴Ｌ２２＝ａ２２−Ｌ２１Ｕ１２                                                                                        ・・・（９）
ａ２３＝Ｌ２１Ｕ１３＋Ｌ２２Ｕ２３  ∴Ｕ２３＝（ａ２３−Ｌ２１Ｕ１３）／Ｌ２２                                                                    ・・・（１０）
ａ２４＝Ｌ２１Ｕ１４＋Ｌ２２Ｕ２４  ∴Ｕ２４＝（ａ２４−Ｌ２１Ｕ１４）／Ｌ２２                                                                    ・・・（１１）
ａ３１＝Ｌ３１                ∴Ｌ３１＝ａ３１                    ・・・（１２）
ａ３２＝Ｌ３１Ｕ１２＋Ｌ３２  ∴Ｌ３２＝ａ３２−Ｌ３１Ｕ１２                                                                                      ・・・（１３）
ａ３３＝Ｌ３１Ｕ１３＋Ｌ３２Ｕ２３＋Ｌ３３
∴Ｌ３３＝ａ３３−Ｌ３１Ｕ１３−Ｌ３２Ｕ２３            ・・・（１４）
ａ３４＝Ｌ３１Ｕ１４＋Ｌ３２Ｕ２４＋Ｌ３３Ｕ３４
∴Ｕ３４＝（ａ３４−Ｌ３１Ｕ１４−Ｌ３２Ｕ２４）／Ｌ３３・・・（１５）
ａ４１＝Ｌ４１                ∴Ｌ４１＝ａ４１                    ・・・（１６）
ａ４２＝Ｌ４１Ｕ１２＋Ｌ４２  ∴Ｌ４２＝ａ４２−Ｌ４１Ｕ１２                                                                                      ・・・（１７）
ａ４３＝Ｌ４１Ｕ１３＋Ｌ４２Ｕ２３＋Ｌ４３
∴Ｌ４３＝ａ４３−Ｌ４１Ｕ１３−Ｌ４２Ｕ２３            ・・・（１８）
ａ４４＝Ｌ４１Ｕ１４＋Ｌ４２Ｕ２４＋Ｌ４３Ｕ３４＋Ｌ４４
∴Ｌ４４＝ａ４４−Ｌ４１Ｕ１４−Ｌ４２Ｕ２４−Ｌ４３Ｕ３４・・・（１９）
【００３９】
一般に、元の行列Ａが（ｎ×ｎ）の場合、分解された二つの三角行列Ｌ、Ｕの要素を求めるには、ｉ＝１，２，・・・，ｎ、ｊ＝１，２，・・・，ｎの順序で、ｉを主、ｊを従にして変えながら順次、次の計算を行えばよい。
【００４０】
ｉ≧ｊ：Ｌｉｊ＝ａｉｊ−ΣＬｉｋＵｋｊ，
ｉ＜ｊ：Ｕｉｊ＝（ａｉｊ−ΣＬｉｋＵｋｊ）／Ｌｉｊ                ・・・（２０）
【００４１】
ここで、Ｌｉｊに対しては、Σはｋ＜ｊを満たすｋについての和であり、Ｕｉｊに対しては、Σはｋ＜ｉを満たすｋについての和を表すものとする。その他の要素については、下記（２１）式を満たす。
【００４２】
ｉ＜ｊ：Lij＝０；ｉ＝ｊ：Ｕｉｊ＝１；ｉ＞ｊ：Ｕｉｊ＝０          ・・・（２１）
【００４３】
ＬＵ分解の処理を行単位、または列単位で並列処理する場合、以下のようになる。なお、上述のように、適用計算機は対称型マルチプロセッサ（ＳＭＰ型）、ＣＰＵ台数は例えば４台とし、各ＣＰＵは共有メモリで結合されているとする。すなわち、図２において、ｎ＝４の計算機構成を例に並列処理の説明を行う。
【００４４】
図５−１は、本実施の形態が採用する行単位の並列処理を示す図、図５−２は、従来の列単位の並列処理を示す図、図５−３は、図５−１の処理をさらに改善したものであり、本実施の形態で採用する行単位の並列処理を示す図である。
【００４５】
図５−１においては、４台のＣＰＵにより上記（４）〜（１９）式に示す処理が行単位で並列処理される。すなわち、ＣＰＵ１では、係数行列Ａの１行目の成分についての処理が行われ、Ｌ１１，Ｕ１２，Ｕ１３，Ｕ１４の順に演算が行われる。また、ＣＰＵ２，ＣＰＵ３，ＣＰＵ４では、それぞれ、係数行列のＡの２行目、３行目、４行目についての処理が行われ、各ＣＰＵにおいては、それぞれ１〜４の番号の付された４つの処理を番号順に実行する。ＣＰＵ１では、Ｌ１１はａ１１で与えられ、Ｕ１２，Ｕ１３，Ｕ１４はＬ１１の値をもとに計算される。ＣＰＵ２では、Ｌ２１はａ２１で与えられ、Ｌ２２はＬ２１とＣＰＵ１における計算結果であるＵ１２をもとに計算される。また、Ｕ２３はＬ２２とＣＰＵ１における計算結果であるＵ１３をもとに計算され、Ｕ２４はＬ２２とＣＰＵ１における計算結果であるＵ１４をもとに計算される。ＣＰＵ３では、ＣＰＵ１における計算結果であるＵ１２、ＣＰＵ２における計算結果であるＵ２３、およびＬ３１をもとに各処理が行われる。ＣＰＵ４では、ＣＰＵ１における計算結果であるＵ１２、ＣＰＵ２における計算結果であるＵ２３、ＣＰＵ３における計算結果であるＵ３４、およびＬ４１をもとに各処理が行われる。また、図５−２においては、４台のＣＰＵに、全体として図５−１に示す処理と同様の処理が、列単位で割り当てている。なお、図５−１、図５−２、図５−３、における下線が付された変数は、前段のＣＰＵ（ＣＰＵ番号が相対的に小さい方）が処理した結果を後段のＣＰＵ（ＣＰＵ番号が相対的に大きい方）に、共有メモリ上で受け渡すことを示す（以下、図６−１、図６−２、図７−１、図７−２でも同様）。
【００４６】
次に、図５−１に示す行単位の並列処理と、図５−２に示す列単位の並列処理とを、ＣＰＵ間のデータ受渡し回数、各ＣＰＵの演算量のバランスから比較する。データ受渡し回数は、図５−１に示す行単位の処理が１４回、図５−２に示す列単位の処理が２０回になる。また、加減乗除の回数は、図５−１に示す行単位の処理では、最小が３回、最大が１２回であるのに対して、図５−２に示す列単位の処理では、最小が０回、最大が１５回である。したがって、ＣＰＵ間のデータ受渡し回数が少なく、かつ、各ＣＰＵの加減乗除の演算量のバランスが取れている行単位の並列処理が、より効率的な処理であることがわかる。本実施の形態では、従来利用されていた列単位の並列処理の替わりに、行単位の並列処理を利用してＬＵ分解を行う。
【００４７】
なお、行単位の並列処理においては、Ｌ行列の対角要素で割り算を行う回数が多いため、まず、１度割り算を実行して逆数を求め、その結果をＬＬ行列の対角成分として保存し、以降の計算では、乗算のみを行うことにより、高速化を図ることが可能である。それを、図５−３に示す。すなわち、図５−３においては、ＬＬ１１＝１／Ｌ１１，ＬＬ２２＝１／Ｌ２２，ＬＬ３３＝１／Ｌ３３を計算して保存し、計算に用いている。
【００４８】
以下、図５−３に基づく、ＬＵ分解の並列処理の手順について述べる。複数のＣＰＵで並列処理を行う場合、各ＣＰＵの処理する行ｉの決定、各ＣＰＵの処理が終了したことの検出方法、また、全行の処理が終了したことの検出方法を決める必要がある。さらに、ＬＵ分解の並列処理には、並列処理の順序を守るために、Ｕ要素処理フラグが必要となる。以下では、これらについて詳述する。
【００４９】
（ａ）各ＣＰＵが処理する行ｉの決定
（１）係数行列Ａの大きさを、行ｎmax、列ｎmaxとする。
（２）まず、各ＣＰＵが処理する行ｉを、例えば、下記（２２）式により算出する。
ｉ＝（ｋ−１）＊ＣＰＵmax＋ＣＰＵｉ                              ・・・（２２）
ただし、
ｉ：処理対象の行番号
ｋ：各ＣＰＵの行処理回数（ＣＰＵ１が初期化する。初期値＝１）
ＣＰＵmax：並列処理を行うＣＰＵ台数
ＣＰＵｉ：ＣＰＵ番号（ＣＰＵ１＝１，ＣＰＵ２＝２，・・・，ＣＰＵ４＝４など）
【００５０】
図８は、４台のＣＰＵに対して、各ＣＰＵが処理する行ｉが割り当てられている様子を示す図である。例えば、ＣＰＵ１では、行処理回数が１回目に１行目を処理し、行処理回数が２回目に５行目を処理し、行処理回数がｎ回目にｎ１行目を処理する。各行の処理は、図５−３に示すように、さらに複数の処理からなる行単位の処理である。なお、ＣＰＵ１は、各ＣＰＵの行処理回数ｋの更新を行う。また、各ＣＰＵが処理する行ｉの算出は、例えば、ＣＰＵ１が一括して行ってもよいし、各ＣＰＵは自身が処理する行ｉの算出を個別に行ってもよい。
【００５１】
（ｂ）ＣＰＵ処理フラグの管理
ＣＰＵ１が各ＣＰＵの行処理回数ｋの更新を行うためには、各ＣＰＵの行処理が終了したことを確認する必要がある。これを、ＣＰＵ処理フラグを設定することにより行う。図８では、各ＣＰＵに対してＣＰＵ処理フラグが設定されている。
（１）初期化
ＣＰＵ１が、全ＣＰＵのＣＰＵ処理フラグを、０で初期化する。
（２）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の行処理が終了した時点で、ＣＰＵ処理フラグに自身のＣＰＵ番号を書き込む。
（３）行処理回数ｋのカウントアップ
ＣＰＵ１は、全ＣＰＵのＣＰＵ処理フラグが正になった時点で、ｋを１だけ加算し、全ＣＰＵのＣＰＵ処理フラグを０にリセットする。
【００５２】
（ｃ）ＬＵ分解終了フラグの管理
ＬＵ分解の処理終了を確認するために、ＬＵ分解終了フラグを設定する。ＬＵ分解の処理終了は、各ＣＰＵがＬＵ分解終了フラグを参照して行う。
（１）初期化
ＣＰＵ１が、ＬＵ分解終了フラグを、０で初期化する。
（２）最終行の検出
各ＣＰＵが処理する行番号ｉが、行サイズｎmaxと一致した場合、最終行の処理をしたと判断し、検出したＣＰＵは、ＬＵ分解終了フラグに自身のＣＰＵ番号をセットする。
（３）ＬＵ分解の終了
各ＣＰＵは、ＬＵ分解終了フラグが正の場合、ＬＵ分解の処理が終了したと判断し、次の前進消去の処理に入る。
【００５３】
（ｄ）Ｕ要素処理フラグの管理
（１）直列処理の実施
ＬＵ分解では、直列に処理をする形式になっており、行番号が大きい行列要素について処理を行うＣＰＵは、行番号の小さい行列要素について処理を行うＣＰＵの処理が終了した後に、処理を行う必要がある。例えば、図５−３に示すように、前段のＣＰＵ（ＣＰＵ番号が相対的に小さい方）が処理したＵ要素の計算結果は、共有メモリを介して後段のＣＰＵ（ＣＰＵ番号が相対的に大きい方）に受け渡され、この前段のＣＰＵから受け渡されたＵ要素をもとに、後段のＣＰＵは処理を行う。このため、Ｕ要素処理フラグを設け、当該要素の処理を実施したＣＰＵが、自身のＣＰＵ番号をＵ要素処理フラグにセットする。
（２）各ＣＰＵは、自身の処理に必要なＵ要素が計算済みかどうかを、Ｕ要素処理フラグをチェックして判断し、フラグの値が正の場合に計算に必要な要素を取得して処理を行う。正でない場合は、継続してチェックを行う。ただし、ＣＰＵ１において、ｉ＝１の処理では、このチェックを不要とする。
（３）Ｕ要素処理フラグは、以下の各Ｕ要素に対して設定されるものとする。
ＵＵ１１，ＵＵ１２，・・・ＵＵ１ｎ，ＵＵ２２，ＵＵ２３，・・・ＵＵ２ｎ，・・・ＵＵｎ−１ｎ，ＵＵｎｎ
【００５４】
本実施の形態におけるＬＵ分解の並列処理手順をまとめると、以下の通りである。
（処理１）各ＣＰＵが処理する処理対象行ｉを決定する。
（処理２）各ＣＰＵが、計算に必要な関連するＵ要素処理フラグをチェックし、計算に必要な要素を取得した後にＬ行列要素、Ｕ行列要素の計算を行い、Ｕ要素処理フラグ、ＣＰＵ処理フラグをセットする。なお、Ｕ要素と掛け算となるＬ要素がゼロの場合は、その処理をスキップして、演算量を低減させる。
（処理３）ＣＰＵ１が、全ＣＰＵ処理フラグが正であることを確認し、ｋを１加算し、全ＣＰＵのＣＰＵ処理フラグを０にリセットし、（処理１）に戻る。
（処理４）各ＣＰＵは、自身が最終行を処理した場合、ＬＵ分解終了フラグに自身のＣＰＵ番号をセットする。
（処理５）各ＣＰＵは、ＬＵ分解終了フラグが正の場合、ＬＵ分解を終了し、次の前進消去の処理に進む。なお、上記各種フラグは、例えば、共有メモリにて管理される。
【００５５】
次に、前進消去の並列処理について説明する。ＬＵ分解を行った行列に対して、前進消去、および後退代入の処理を行うと、連立一次方程式の解を求めることができる。連立一次方程式Ａ・ｘ＝ｂに対して、係数行列ＡにＬＵ分解の結果を代入すると、下記（２３）式のように表される。
【００５６】
Ｌ・Ｕ・ｘ＝ｂ                                                  ・・・（２３）
【００５７】
ここで、ｙ＝Ｕ・ｘを求めるのが前進消去である。すなわち、Ｌｙ＝ｂを満たすｙを求める処理であり、ベクトルｙのｉ行目の要素は下記（２４）式により求められる。
【００５８】
ｙｉ＝（ｂｉ−ΣＬｉｎＹｎ）／Ｌｉｉ                            ・・・（２４）
【００５９】
ここで、Σはｎ≠ｉを満たすｎについて、１からｉまでの和を表すものとする。
【００６０】
また、係数行列Ａが（４×４）の場合に、上記（２３）式およびｙ＝Ｕ・ｘから、それらを要素表示した下記（２５）式および（２６）式が得られる。
【００６１】
【数２】
2008176738.tif 000004
【００６２】
【数３】
2008176738.tif 000005
【００６３】
上記（２６）式より、Ｌ要素および係数ベクトルｂの成分を用いて、ｙｉは以下のように順次求められる。
【００６４】
Ｌ１１ｙ１＝ｂ１
∴ｙ１＝ｂ１／Ｌ１１                              ・・・（２７）
Ｌ２１ｙ１＋Ｌ２２ｙ２＝ｂ２
∴ｙ２＝（ｂ２−Ｌ２１ｙ１）／Ｌ２２              ・・・（２８）
Ｌ３１ｙ１＋Ｌ３２ｙ２＋Ｌ３３ｙ３＝ｂ３
∴ｙ３＝（ｂ３−Ｌ３１ｙ１−Ｌ３２ｙ２）／Ｌ３３  ・・・（２９）
Ｌ４１ｙ１＋Ｌ４２ｙ２＋Ｌ４３ｙ３＋Ｌ４４ｙ４＝ｂ４
∴ｙ４＝（ｂ４−Ｌ４１ｙ１−Ｌ４２ｙ２−Ｌ４３ｙ３）／Ｌ４４
・・・（３０）
【００６５】
これを例えば４つのＣＰＵに分散して行単位で並列処理すると、図６−１のようになる。図６−１に示すように、ＣＰＵ１における演算の回数は１回であるのに対して、ＣＰＵ４における演算の回数は７回となっている。これでは、各ＣＰＵの処理量のバランスが悪い。そこで、ＣＰＵ１でｙ１の計算時に、ＣＰＵ２，３，４で処理することになっているｙ１に関係する処理（すなわち、ｙ１とＬ要素との積であるＬ２１ｙ１，Ｌ３１ｙ１，Ｌ４１ｙ１）も行うように処理の変形を行うと、図６−２のようになる。図６−２に示すように、例えば、ＣＰＵ１では、ＬＵ分解の計算時に得られたＬＬ１１を用いて、ｙ１を計算しており、また、ＣＰＵ２，３，４で処理することになっている演算Ｌ２１ｙ１，Ｌ３１ｙ１，Ｌ４１ｙ１を行い、その演算結果を、それぞれ、ＬＬ２１，ＬＬ３１，ＬＬ４１として保存している。他のＣＰＵにおいても、同様に、後段のＣＰＵの処理に利用されるＬＬ要素を計算して保存している。
【００６６】
図６−２では、ＣＰＵ間のデータ受渡し回数は図６−１と同じであるが、各ＣＰＵの加減乗除の回数が一定の４回であり（最小、最大共に４回）、図６−１の最小で１回、最大で７回と比較して、非常にバランスが取れており、並列処理に適したアルゴリズムになっている。なお、ＣＰＵ間のデータ受け渡しは、共有メモリ１２を介して行われる。
【００６７】
以下、図６−２に基づく、前進消去の並列処理の手順について述べる。複数のＣＰＵで並列処理を行う場合、各ＣＰＵの処理するｙｉの決定、各ＣＰＵの処理が終了したことの検出方法、また、全行の処理が終了したことの検出方法を決める必要がある。さらに、前進消去の並列処理には、並列処理の順序を守るために、ＬＬ要素処理フラグが必要となる。以下では、これらについて詳述する。
【００６８】
（ａ）処理対象ｙiの決定
各ＣＰＵが処理するｙｉの行番号を、例えば、下記（２２−２）式により算出する。
ｉ＝（ｋ−１）＊ＣＰＵｍａｘ＋ＣＰＵｉ                        ・・・（２２−２）
ただし、
ｉ：処理対象の行番号
ｋ：各ＣＰＵの行処理回数（ＣＰＵ１が初期化する。初期値＝１）
ＣＰＵｍａｘ：並列処理するＣＰＵ台数
ＣＰＵｉ：ＣＰＵ番号（ＣＰＵ１＝１，ＣＰＵ２＝２,・・・,ＣＰＵ４＝４など）
【００６９】
図９は、前進消去の処理において、４台のＣＰＵに対して、各ＣＰＵが処理する行ｉが割り当てられている様子を示す図である。例えば、ＣＰＵ１では、行処理回数が１回目に１行目を処理し、行処理回数が２回目に５行目を処理し、行処理回数がｎ回目にｎ１行目を処理する。なお、ＣＰＵ１は、各ＣＰＵの行処理回数ｋの更新を行う。また、各ＣＰＵが処理する行ｉの算出は、例えば、ＣＰＵ１が一括して行ってもよいし、各ＣＰＵが、自身が処理する行ｉの算出を個別に行ってもよい。
【００７０】
（ｂ）ＣＰＵ処理フラグの管理
ＣＰＵ１が各ＣＰＵの行処理回数ｋの更新を行うためには、各ＣＰＵの処理が終了したことを確認する必要がある。これを、ＣＰＵ処理フラグを設定することにより行う。
（１）初期化
ＣＰＵ１が、全ＣＰＵのＣＰＵ処理フラグを、０で初期化する。
（２）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の行処理が終了した時点で、ＣＰＵ処理フラグに自身のＣＰＵ番号を書き込む。
（３）行処理回数ｋのカウントアップ
ＣＰＵ１は、全ＣＰＵのＣＰＵ処理フラグが正になった時点で、ｋを１だけ加算し、全ＣＰＵのＣＰＵ処理フラグを０にリセットする。
【００７１】
（ｃ）前進消去終了フラグの管理
前進消去の処理終了を確認するために、前進消去終了フラグを設定する。前進消去の処理終了は、各ＣＰＵが前進消去終了フラグを参照して行う。
（１）初期化
ＣＰＵ１が、前進消去終了フラグを、０で初期化する。
（２）最終行の検出
各ＣＰＵが処理するｙｉの行番号ｉが、行サイズｎmaxと一致した場合、最終行の処理をしたと判断し、検出したＣＰＵは、前進消去終了フラグに自身のＣＰＵ番号をセットする。
（３）前進消去の終了
各ＣＰＵは、前進消去終了フラグが正の場合、前進消去の処理が終了したと判断し、次の後退代入の処理に入る。
【００７２】
（ｄ）ＬＬ要素処理フラグ
（１）直列処理の実施
前進消去では、直列に処理をする形式になっており、行番号の大きい行列要素についての処理を行うＣＰＵは、行番号の小さい行列要素についての処理を行うＣＰＵの処理が終了した後に、処理を行う必要がある。このため、前段のＣＰＵ（ＣＰＵ番号が相対的に小さい方）が解を得た時点で、この解に関して後段のＣＰＵ（ＣＰＵ番号が相対的に大きい方）で処理する演算も前段のＣＰＵで処理を行うが、この処理結果であるＬＬ要素について、処理フラグを設け、当該要素の処理を実施したＣＰＵは自身のＣＰＵ番号を、ＬＬ要素処理フラグにセットする。例えば、図６−２においては、ＣＰＵ１は１行目についての前進消去の処理後に、ＬＬ２１，ＬＬ３１，ＬＬ４１の各要素に対応する処理フラグに、自身のＣＰＵ番号ＣＰＵ１＝１をセットする。
（２）各ＣＰＵは、自身の処理に必要なＬＬ要素が計算済みかどうかを、ＬＬ要素処理フラグをチェックして判断し、フラグの値が正の場合に処理に必要なＬＬ要素を取得して処理を行う。正でない場合は、継続してチェックを行う。ただし、ＣＰＵ１において、ｉ＝１の処理では、このチェックを不要とする。
（３）ＬＬ要素処理フラグは、以下の各ＬＬ要素に対して設定されるものとする。
ＬＬ１１，ＬＬ１２，・・・ＬＬ１ｎ，ＬＬ２２，ＬＬ２３，・・・ＬＬ２ｎ，・・・ＬＬｎ−１ｎ，ＬＬｎｎ
【００７３】
本実施の形態における前進消去の並列処理手順をまとめると、以下の通りである。
（処理１）各ＣＰＵが処理するｙｉの処理対象行ｉを決定する。
（処理２）各ＣＰＵが、計算に必要な関連するＬＬ要素処理フラグをチェックし、計算に必要な要素を取得してｙｉ、ＬＬ行列要素の計算を行い、ＬＬ要素処理フラグ、ＣＰＵ処理フラグをセットする。なお、ｙｉ要素と掛け算となるＬ要素がゼロの場合は、その処理をスキップして、演算量を低減させる。
（処理３）ＣＰＵ１が、全ＣＰＵ処理フラグが正であることを確認し、ｋを１加算し、全ＣＰＵのＣＰＵ処理フラグを０にリセットし、（処理１）に戻る。
（処理４）各ＣＰＵは、自身が最終行を処理した場合、前進消去終了フラグを自身のＣＰＵ番号にセットする。
（処理５）各ＣＰＵは、前進消去終了フラグが正の場合、前進消去を終了し、次の後退代入の処理に進む。なお、上記各種フラグは、例えば、共有メモリにて管理される。
【００７４】
次に、後退代入の並列処理について説明する。後退代入の処理は、下記（３１）式を解くことにより、連立一次方程式の解ｘを求める処理である。
【００７５】
Ｕ・ｘ＝ｙ                                                      ・・・（３１）
【００７６】
また、上記（３１）式を行列形式で表現すると、下記（３２）式になる。
【数４】
2008176738.tif 000006
【００７７】
そこで、下記のように、上記（３２）式を順次解いていけば、解ｘが得られる。
ｘ４＝ｙ４
∴ｘ４＝ｙ４                                      ・・・（３３）
ｘ３＋Ｕ３４ｘ４＝ｙ３
∴ｘ３＝ｙ３−Ｕ３４ｘ４                          ・・・（３４）
ｘ２＋Ｕ２３ｘ３＋Ｕ２４ｘ４＝ｙ２
∴ｘ２＝ｙ２−Ｕ２３ｘ３−Ｕ２４ｘ４              ・・・（３５）
ｘ１＋Ｕ１２ｘ２＋Ｕ１３ｘ３＋Ｕ１４ｘ４＝ｙ１
∴ｘ１＝ｙ１−Ｕ１２ｘ２−Ｕ１３ｘ３−Ｕ１４ｘ４
・・・（３６）
【００７８】
これを例えば４つのＣＰＵに分散して行単位で並列処理すると、図７−１のようになる。図７−１に示すように、ＣＰＵ１における演算の回数は０回であるのに、ＣＰＵ４における演算の回数は６回となっている。これでは、各ＣＰＵの処理量のバランスが悪い。そこで、ＣＰＵ１でｘ４の計算時に、ＣＰＵ２，３，４で処理することになっているｘ４に関係する処理（すなわち、Ｕ３４ｘ４，Ｕ２４ｘ４、Ｕ１４ｘ４）も行うように処理の変形を行うと、図７−２のようになる。図７−２に示すように、例えば、ＣＰＵ１では、ＣＰＵ２，３，４で処理することになっている演算Ｕ３４ｘ４，Ｕ２４ｘ４、Ｕ１４ｘ４を行い、その演算結果を、それぞれＵＵ３４，ＵＵ２４，ＵＵ１４として保存している。他のＣＰＵにおいても、同様に、後段のＣＰＵ（ＣＰＵ番号が相対的に小さい方）の処理に利用されるＵＵ要素を計算して保存している。
【００７９】
図７−２では、ＣＰＵ間のデータ受渡し回数は図７−１と同じであるが、各ＣＰＵの加減乗除の回数が、最小で３回、最大で３回であり、図７−１の最小で０回、最大で６回と比較して、非常にバランスが取れており、並列処理に適したアルゴリズムになっている。なお、ＣＰＵ間のデータの受け渡しは、共有メモリ１２を介して行われる。
【００８０】
以下、図７−２に基づく、後退代入の並列処理の手順について述べる。複数のＣＰＵで並列処理を行う場合、各ＣＰＵの処理するｘｉの決定、各ＣＰＵの処理が終了したことの検出方法、また、全行の処理が終了したことの検出方法を決める必要がある。さらに、後退代入の並列処理には、並列処理の順序を守るために、ＵＵ要素処理フラグが必要となる。以下では、これらについて詳述する。
【００８１】
（ａ）処理対象ｘiの決定
各ＣＰＵが処理するｙｉの行番号を、例えば、下記（２２−３）式により算出する。
ｉ＝ｎｍａｘ−（ｋ−１）・ＣＰＵmax−ＣＰＵｉ＋１            ・・・（２２−３）
ただし、
ｎｍａｘ：ｘｉの最大要素数、すなわちベクトルｘの次元
ｋ：各ＣＰＵの行処理回数（ＣＰＵ１が初期化する。初期値＝１）
ＣＰＵｍａｘ：並列処理するＣＰＵ台数
ＣＰＵｉ：ＣＰＵ番号（ＣＰＵ１＝１、・・・、ＣＰＵ４＝４など）
【００８２】
図１０は、４台のＣＰＵに対して、各ＣＰＵが処理する行ｉが割り当てられている様子を示す図である。例えば、ＣＰＵ１では、行処理回数が１回目にｎｍａｘ行目を処理し、行処理回数が２回目に（ｎｍａｘ−３）行目を処理し、行処理回数がｎ回目に３行目を処理する。なお、ＣＰＵ１は、各ＣＰＵの行処理回数ｋの更新を行う。また、各ＣＰＵが処理する行ｉの算出は、例えば、ＣＰＵ１が一括して行ってもよいし、各ＣＰＵが、自身が処理する行ｉの算出を個別に行ってもよい。
【００８３】
（ｂ）ＣＰＵ処理フラグの管理
ＣＰＵ１が各ＣＰＵの行処理回数ｋの更新を行うためには、各ＣＰＵの処理が終了したことを確認する必要がある。これを、ＣＰＵ処理フラグを設定することにより行う。
（１）初期化
ＣＰＵＩが、全ＣＰＵのＣＰＵ処理フラグを、０で初期化する。
（２）ＣＰＵ処理フラグの設定
各ＣＰＵが、担当の行処理が終了した時点で、ＣＰＵ処理フラグに自身のＣＰＵ番号を書き込む。
（３）計算回数ｋのカウントアップ
ＣＰＵ１は、全ＣＰＵのＣＰＵ処理フラグが正になった時点で、ｋを１だけ加算し、全ＣＰＵのＣＰＵ処理フラグを０にリセットする。
【００８４】
（ｃ）後退代入終了フラグの管理
後退代入の処理終了を確認するために、後退代入終了フラグを設定する。後退代入の処理終了は、各ＣＰＵが後退代入終了フラグを参照して行う。
（１）初期化
ＣＰＵＩが、前進消去終了フラグを、０で初期化する。
（２）最終行の検出
各ＣＰＵが処理するｘｉの行番号ｉが、行サイズｎmaxと一致した場合、最終行の処理をしたと判断し、検出したＣＰＵは、前進消去終了フラグに自身のＣＰＵ番号をセットする。
（３）後退代入の終了
各ＣＰＵは、後退代入終了フラグが正の場合、後退代入の処理が終了したと判断し、全処理の終了とする。
【００８５】
（ｄ）ＵＵ要素処理フラグ
（１）直列処理の実施
後退代入では、直列に処理をする形式になっており、行番号が小さい行列要素についての処理を行うＣＰＵは、行番号の大きい行列要素についての処理を行うＣＰＵの処理が終了した後に、処理を行う必要がある。このため、前段のＣＰＵ（ＣＰＵ番号が相対的に小さい方）が解を得た時点で、この解に関して後段のＣＰＵ（ＣＰＵ番号が相対的に大きい方）で処理する演算も前段のＣＰＵで処理を行うが、この結果であるＵＵ要素について、処理フラグを設け、当該要素の処理を実施したＣＰＵは自身のＣＰＵ番号を、ＵＵ要素処理フラグにセットする。例えば、図７−２においては、ＣＰＵ１は１行目についての後退代入の処理後に、ＵＵ３４，ＵＵ２４，ＵＵ１４の各要素に対応する処理フラグに、ＣＰＵ＝１をセットする。
（２）各ＣＰＵは、自分の処理に必要なＵＵ要素が計算済みかどうかを、ＵＵ要素処理フラグをチェックして判断し、フラグの値が正の場合に計算に必要な要素を取得して処理を行う。正でない場合は、継続してチェックを行う。ただし、ＣＰＵ１において、ｉ＝１の処理では、このチェックを不要とする。
（３）ＵＵ要素処理フラグは、以下の各ＵＵ要素に対して設定されるものとする。
ＵＵ１１，ＵＵ１２，・・・ＵＵ１ｎ，ＵＵ２２，ＵＵ２３，・・・ＵＵ２ｎ，・・・ＵＵｎ−１ｎ，ＵＵｎｎ
【００８６】
本実施の形態における後退代入の並列処理手順をまとめると、以下の通りである。
（処理１）各ＣＰＵが処理するｘｉの処理対象行ｉを決定する。
（処理２）各ＣＰＵが、計算に必要な関連するＵＵ要素処理フラグをチェックし、計算に必要な要素を取得した後にｘｉ、ＵＵ行列要素の計算を行い、ＵＵ要素処理フラグ、ＣＰＵ処理フラグをセットする。なお、ｘｉ要素と掛け算となるＵ要素がゼロの場合は、その処理をスキップして、演算量を低減する。
（処理３）ＣＰＵ１が、全ＣＰＵ処理フラグが正であることを確認し、ｋを１加算し、全ＣＰＵのＣＰＵ処理フラグを０にリセットし、（処理１）に戻る。
（処理４）各ＣＰＵは、自身が最終行を処理した場合、後退代入終了フラグを自身のＣＰＵ番号にセットする。
（処理５）各ＣＰＵは、後退代入終了フラグが正の場合、後退代入を終了し、全ての終了となる。なお、上記各種フラグは、例えば、共有メモリにて管理される。
【００８７】
以上説明した本実施の形態におけるＬＵ分解、前進消去、および後退代入の処理の手順を繋げて、並列求解の処理手順として図４−１および図４−２を参照してまとめる。図４−１、および図４−２は、本実施の形態による並列求解の処理の手順を示すフローチャートである。なお、図４−２は、図４−１に続く処理を示している。本実施の形態を実現する計算機構成に含まれる各ＣＰＵには同じプログラムが実装されるが、上述のように、各ＣＰＵには、事前に独立したＣＰＵ番号が割り付けられている（図２参照）。また、全体の制御を行うＣＰＵは、例えばＣＰＵ１が担当し、ＣＰＵ２〜ＣＰＵｎは、与えられた処理を並列処理するということで、機能分担を行う。ただし、ＣＰＵ１は、ＣＰＵ２〜ＣＰＵｎが担当する処理も、同様に分担する。
【００８８】
図４−１に示すように、まず、当該ＣＰＵがＣＰＵ１であるかどうかの判定（ステップ２１−１）を行い、ＣＰＵ１であれば、フラグ類の初期化処理１（ステップ２２）とＣＰＵ２〜ＣＰＵｎの起動（ステップ２３）を行う。次に、全ＣＰＵが分担して、ＬＵ分解の処理を並列に実行する。なお、ＣＰＵ１の最初の処理のみは、無条件で処理可能とする。
【００８９】
次に、各ＣＰＵに対して処理対象の行ｉを選定し（ステップ２４）、その行において処理対象であるＬ行列要素の計算が可能かどうかを、その処理に必要な関連するＵ行列要素が計算済みかどうかの判定で行い（ステップ２５−１）、Ｙｅｓであれば、その行についてＬ行列要素の計算を行う（ステップ２６）。Ｎｏの場合は、関連するＵ行列要素が計算済みかどうかの判定（ステップ２５−１）を繰返してチェックし、Ｙｅｓの状態になるまで待つ。次に、その行において処理対象であるＵ行列要素の計算が可能かどうかを、その処理に必要な関連するＵ行列要素が計算済みかどうかの判定で行い（ステップ２５−２）、Ｙｅｓの場合は、Ｕ行列要素の計算を行う（ステップ２７）。Ｎｏの場合は、関連するＵ行列要素が計算済みかどうかの判定（ステップ２５−２）を繰返してチェックし、Ｙｅｓの状態になるまで待つ。最後に、ＬＵ分解の処理が全て終了しているかをチェックし（ステップ２８）、終了していない場合は、ステップ２４に戻る。終了していればＬＵ分解の処理を終了として、前進消去の処理に移る。なお、フラグ類の設定については前述の通りである。
【００９０】
次に、図４−２に示すように、前進消去処理を行うが、まず、当該ＣＰＵがＣＰＵ１であるかどうかの判定を行い（ステップ２１−２）、ＣＰＵ１であれば、フラグ類の初期化処理２を行う（ステップ２９）。次に、処理対象であるベクトルｙの行列要素ｙｉの選定を行い（ステップ３０）、ｙｉ、ＬＬ行列要素の計算に必要な、関連するＬＬ行列要素が計算済みかどうかを判定し（ステップ３１）、Ｙｅｓの場合は、ｙｉ、ＬＬ行列要素の計算を行う（ステップ３２）。Ｎｏの場合は、関連するＬＬ行列要素が計算済みかどうかの判定（ステップ３１）を繰返してチェックし、Ｙｅｓの状態になるまで待つ。最後に、前進消去の処理が全て終了したかを判定し（ステップ３３）、Ｎｏの場合は、ステップ３０に分岐し、ＹＥＳの場合は、前進消去の処理を終了し、最後の後退代入の処理に移る。なお、フラグ類の設定については前述の通りである。
【００９１】
次に、後退代入処理を行うが、まず、当該ＣＰＵがＣＰＵ１であるかどうかの判定を行い（ステップ２１−３）、ＣＰＵ１であれば、フラグ類の初期化処理３を行う（ステップ３４）。次に、処理対象であるベクトルｘの行列要素ｘｉの選定を行い（ステップ３５）、ｘｉ、ＵＵ行列要素の計算に必要な、関連するＵＵ行列要素が計算済みかどうかを判定し（ステップ３６）、Ｙｅｓの場合は、ｘｉ、ＵＵ行列要素の計算３７を行う。Ｎｏの場合は、関連するＵＵ行列要素が計算済みかどうかの判定（ステップ３６）を繰返してチェックし、Ｙｅｓの状態になるまで待つ。最後に、後退代入の処理が全て終了したかを判定し（ステップ３８）、Ｎｏの場合は、ステップ３５に分岐し、ＹＥＳの場合は、全ての処理を終了する。なお、フラグ類の設定については前述の通りである。
【００９２】
このように、本実施の形態によれば、行単位に並列処理する方式を採用し、ＬＵ分解では、各要素の実行可否を当該要素の処理フラグの設定、確認により、制御し、また、前進消去、後退代入の処理では、当該ＣＰＵで計算した解について、後段のＣＰＵで処理する計算項目も当該ＣＰＵで計算して後段のＣＰＵにデータを受渡し、また、各要素の実行可否を当該要素の処理フラグの設定、確認により、制御することにより、各ＣＰＵの演算量を減少させ、各ＣＰＵの演算量のバランスを図ることにより、並列処理の効率性を向上させて、連立一次方程式を高速に求解できるという効果がある。
【産業上の利用可能性】
【００９３】
以上のように、本発明にかかる連立一次方程式の並列求解装置は、連立一次方程式の高速な求解に有用であり、給電指令所、制御所等の運転員の平常時、事故時における系統運用に関する技術、技能などの維持・向上を図るための訓練シミュレータの系統シミュレーション手法である周波数・潮流計算（連結）方式の潮流計算にも好適に利用することができる。
【図面の簡単な説明】
【００９４】
【図１】本発明の実施の形態が適用された訓練シミュレータである訓練装置の構成を示す図である。
【図２】本発明の実施の形態にかかる連立一次方程式の並列求解装置を実現する計算機構成の一例を示す図である。
【図３】本発明の実施の形態における系統摸擬機能サーバ群に実装し、系統シミュレーションを行う周波数・潮流計算（連結）方式の処理例を示すフローチャートである。
【図４−１】本発明の実施の形態による並列処理の手順を示すフローチャートである。
【図４−２】図４−１に続くフローチャートである。
【図５−１】実施の形態が採用する行単位の並列処理を示す図である。
【図５−２】従来の列単位の並列処理を示す図である。
【図５−３】図５−１の処理をさらに改善したものであり、実施の形態で採用する行単位の並列処理を示す図である。
【図６−１】前進消去の処理における行単位の並列処理を示す図である。
【図６−２】ＣＰＵ間の演算量のバランスを改善した前進消去の処理における行単位の並列処理を示す図である。
【図７−１】後退代入の処理における行単位の並列処理を示す図である。
【図７−２】ＣＰＵ間の演算量のバランスを改善した後退代入の処理における行単位の並列処理を示す図である。
【図８】ＬＵ分解において、４台のＣＰＵに対して、各ＣＰＵが処理する行ｉが割り当てられている様子を示す図である。
【図９】前進消去の処理において、４台のＣＰＵに対して、各ＣＰＵが処理する行ｉが割り当てられている様子を示す図である。
【図１０】後退代入の処理において、４台のＣＰＵに対して、各ＣＰＵが処理する行ｉが割り当てられている様子を示す図である。
【図１１】従来の一般的なＬＵ分解の処理過程を示すフローチャートである。
【図１２】従来の処理Ｐの処理順序を示す説明図である。
【図１３】並列ＬＵ分解を計算する従来の求解装置の構成を示すブロック図である。
【図１４】従来のマスタプロセッサの処理手順を示すフローチャートである。
【図１５】従来の列ベクトル処理用プロセッサの処理手順を示すフローチャートである。
【図１６】従来の処理Ｐ（ｊ，ｉ）の実行可能判別方法を示すフローチャートである。
【図１７】従来のＡ（ｉ，ｉ），Ａ（ｉ＋１，ｉ）・・・，Ａ（ｎ，ｉ）は使用できる状態にあるかどうかの判定方法を示すフローチャートである。
【図１８】従来の実行可能なＰ（ｊ，ｉ）の実行を示すフローチャートである。
【図１９】従来の下三角成分Ａ（ｊ，ｊ），Ａ（ｊ＋１，ｊ）・・・，Ａ（ｎ，ｊ）の確定の判別方法を示すフローチャートである。
【図２０】従来のベクトルｂ処理用プロセッサの処理手順を示すフローチャートである。
【符号の説明】
【００９５】
１  訓練管理サーバ群
２  系統摸擬サーバ群
３  自動化模擬サーバ群
４  トレーナ卓
５  トレーニ卓
６  大画面系統盤
７  システムＬＡＮ
８  ＣＰＵ１
９  ＣＰＵ２
１０  ＣＰＵ３
１１  ＣＰＵｎ
１２  共有メモリ
１３  状態変化取込み処理部
１４  潮流計算処理部
１５  周波数計算処理部
１６  周波数応動モデル処理部
１７  周波数計算終了判定部
１８  潮流応動モデル１処理部
１９  潮流応動モデル２処理部
２０  周波数／潮流計算終了判定部
２１  ＣＰＵ１の判定部
２２  ＬＵ分解の初期化処理部
２３  ＣＰＵ１〜ＣＰＵｎの起動部
２４  処理対象行ｉの選定部
２５  関連のＵ要素計算済みの判定部
２６  Ｌ行列要素の計算部
２７  Ｕ行列要素の計算部
２８  ＬＵ分解終了の判定部
２９  前進消去の初期化処理部
３０  処理対象ｙｉの選定部
３１  関連のＬＬ要素計算済みの判定部
３２  ｙｉ、ＬＬ要素の計算部
３３  前進消去終了の判定部
３４  後退代入の初期化処理部
３５  処理対象ｘｉの選定部
３６  関連のＵＵ要素計算済みの判定部
３７  ｘi、ＵＵ要素の計算部
３８  後退代入終了の判定部
３９  Ａ（ｉ，ｊ）の計算部
４０  Ａ（ｋ，ｊ）の計算部
４１  Ａ（ｋ，ｊ）の計算部
４２  ｂ（ｉ）の計算部
４３  ｂ（ｉ）の計算部
４４  マスタプロセッサ
４５  列ベクトル処理用プロセッサ
４６  ベクトルｂ処理用プロセッサ
４７  ベクトルｂの送信処理部
４８  列ベクトルの割り当て処理部
４９  列割り当ての待ち処理部
５０  処理Ｐ（ｊ，ｉ）の判定部
５１  下三角成分Ａの受信待ち処理部
５２  処理Ｐ（ｊ，ｉ）の実行部
５３  下三角成分の確定判定部
５４  下三角成分Ａの送信部
５５  処理Ｐ（ｊ，ｉ）の判定部
５６  上三角成分Ａの送信部
５７  列処理の判定部
５８  Ａ（ｉ，ｉ）の判定部
５９  Ｐ(ｊ，ｉ−１)の判定部
６０  実行可能の判断部
６１  実行不可の判断部
６２  第ｉ列割振りの判定部
６３  Ａ（ｉ，ｉ）の確定判定部
６４  Ａ（ｉ，ｉ）の受信判定部
６５  Ａ（ｉ，ｉ）使用可能の判定部
６６  Ａ（ｉ，ｉ）使用不可の判定部
６７  ｉの初期化処理部
６８  Ｐ（ｊ，ｉ）の判定部
６９  ｉの加算処理部
７０  Ｐ（ｊ，ｉ）の実行部
７１  Ｐ（１，ｉ）の判定部
７２  Ａ（ｎ，ｊ）の確定判定部
７３  Ａ（ｎ，ｊ）の未確定判定部
７４  ｂベクトルの受信部
７５  Ｐｂ（ｉ）の実行部
７６  Ｐｂ（ｉ）の判定部
７７  下，上三角成分の受信部
７８  上三角成分の受信部
７９  ベクトルｂの実行部
【図１】
2008176738.tif 000007
【図２】
2008176738.tif 000008
【図３】
2008176738.tif 000009
【図４−１】
2008176738.tif 000010
【図４−２】
2008176738.tif 000011
【図５−１】
2008176738.tif 000012
【図５−２】
2008176738.tif 000013
【図５−３】
2008176738.tif 000014
【図６−１】
2008176738.tif 000015
【図６−２】
2008176738.tif 000016
【図７−１】
2008176738.tif 000017
【図７−２】
2008176738.tif 000018
【図８】
2008176738.tif 000019
【図９】
2008176738.tif 000020
【図１０】
2008176738.tif 000021
【図１１】
2008176738.tif 000022
【図１２】
2008176738.tif 000023
【図１３】
2008176738.tif 000024
【図１４】
2008176738.tif 000025
【図１５】
2008176738.tif 000026
【図１６】
2008176738.tif 000027
【図１７】
2008176738.tif 000028
【図１８】
2008176738.tif 000029
【図１９】
2008176738.tif 000030
【図２０】
2008176738.tif 000031