(57)【特許請求の範囲】
【請求項１】
連立一次方程式の係数行列と定数ベクトルからなる対象行列の行列要素をブロック単位に分割して、連立一次方程式を複数のプロセッサにより解く並列処理システムにおいて、
前記複数のプロセッサと情報の送受信を行うコントロールプロセッサと、
少なくともそれぞれに処理手段と、転送手段とを有する複数のプロセッサと、
各プロセッサごとに接続された記憶手段とからなり、
前記コントロールプロセッサは、枢軸を示す情報と、各プロセッサが担当する行ブロックを示す情報と、前記行ブロックに属する行列要素と、処理の開始を示す情報とを該各プロセッサに送信し、前記行ブロック中の１の列ブロックの処理の完了を示す情報を該プロセッサより受信し、
前記記憶手段は、前記コントロールプロセッサより受信した前記枢軸を示す情報と、前記行ブロックを示す情報と、前記行ブロックに属する行列要素とを記憶し、
前記処理手段は、自配下に接続される前記記憶手段と前記転送手段とから得られる情報に基づいて、前記枢軸の属する行の行列要素を用いて、該枢軸の属する列の枢軸以外の全要素を零とする消去処理を当該各要素の属する行の各要素に対し所定の列ごとに行い、
前記転送手段は、他のプロセッサが処理に用いるための前記枢軸の属する行に含まれる所定の行列要素を該他のプロセッサに転送する
ことを特徴とする並列処理システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、自動車、建設、電機等の分野において、構造解析を行う際に生ずる大規模な連立一次方程式を、並列処理システムを用いて、高速にかつ簡単な構成で解く並列処理システムに関する。
【０００２】
【従来の技術】
従来、有限要素法や差分法等により生ずる連立一次方程式の係数行列の規模が計算機のメモリに入りきらない程大きい場合、係数行列のデータの分割による制御の複雑さを回避するため、係数行列の全データを、単一の外部記憶装置に格納し、処理していた。この場合、処理時間短縮のため、複数のＣＰＵにより並列に処理し、当該処理に必要なデータを、当該外部記憶装置からメモリに読出し、適当なブロックごとに処理していた。
【０００３】
また、通常、このような連立一次方程式を解く場合、解法アルゴリズムとして、ガウスの消去法等が用いられる。これは、ガウスの消去法が、直接法であり、必ず解を得ることができるためである。ここでは、後の説明の便宜を考慮し、ガウスの消去法について説明する。解くべきＮ元の連立一次方程式を、Ａｘ＝ｂとする。ここで、Ａは係数行列、ｘは未知数ベクトル、ｂは定数ベクトルである。成分別に書くと、
0003694946.tif 000002
である。まず、一番目の式の（−Ａ（ｉ，１）／Ａ（１，１））倍をｉ番目の式に加える（ｉ＝２〜Ｎ）。すると、ｉ番目の式のｘ（１）の係数を０にすることができ、ｉ番目の式のＡ（ｉ，ｊ）、ｂ（ｉ）は、
Ａ（ｉ，ｊ）＝Ａ（ｉ，ｊ）−Ａ（ｉ，１）・Ａ（１，ｊ）／Ａ（１，１）、ｂ（ｉ）＝ｂ（ｉ）−Ａ（ｉ，１）ｂ（１）／Ａ（１，１）
と更新される（ｊ＝１〜Ｎ）。ここで、Ａ（ｉ，１）＝０、（ｉ＝２〜Ｎ）となり、方程式（１）の二番目の式以降は、ｘ（２）、・・・、ｘ（Ｎ）に関する（Ｎ−１）元の連立一次方程式となり、問題のサイズを一つ小さくすることができる。次に、同様にして、二番目の式の（−Ａ（ｉ、２）／Ａ（２、２））倍をｉ番目の式に加えると、Ａ（ｉ、２）＝０（ｉ＝３〜Ｎ）となり、ｘ（２）を消去することができ、問題を、ｘ（３）、・・・、ｘ（Ｎ）に関する（Ｎ−２）元の連立一次方程式に縮減することができる。以降についても同様で、一般にｘ（ｋ−１）が消去された段階においては、処理Ｐ
『ｉ＝ｋ＋１からＮまでに対し、
ｂ（ｉ）＝ｂ（ｉ）─Ａ（ｉ，ｋ）・ｂ（ｋ）／Ａ（ｋ，ｋ）、および
ｊ＝１からＮまでに対し、
Ａ（ｉ，ｊ）＝Ａ（ｉ，ｊ）−Ａ（ｉ，ｋ）・Ａ（ｋ，ｊ）／Ａ（ｋ，ｋ）』
を行うことにより、ｘ（ｋ）が消去でき、問題は（Ｎ−ｋ）元の連立一次方程式に帰着する。このｋ行目の消去に用いる非零の対角要素Ａ（ｋ，ｋ）を枢軸という。処理Ｐを、ｋ＝１からｋ＝Ｎ−１まで行うと、問題は、Ａ（Ｎ，Ｎ）・ｘ（Ｎ）＝ｂ（Ｎ）という簡単な式に縮減される。ここまでの処理を前進消去という。前進消去が終了すると、次は、後退代入という処理に入る。前進消去が終了した時点での（１）の方程式は、下三角部分の行列要素は０、上三角部分の行列要素のみが非零に変形されており、Ｎ番目の式は、簡単に解けて、ｘ（Ｎ）＝ｂ（Ｎ）／Ａ（Ｎ，Ｎ）となる。ただし、ｂ（Ｎ）、Ａ（Ｎ、Ｎ）は、処理Ｐによる更新後の値である。得られたｘ（Ｎ）を（Ｎ−１）番目の式に代入すると、ｘ（Ｎ−１）が求まる。求まったｘ（Ｎ）およびｘ（Ｎ−１）を（Ｎ−２）番目の式に代入すると、ｘ（Ｎ−２）が求まる。このようにして、降順に、解ｘ（ｉ）（ｉ＝１〜Ｎ）を得ることができる。
【０００４】
【発明が解決しようとする課題】
上述のように、係数行列を分割せず、単一の外部記憶装置に格納したとすると、上述した並列処理によりＣＰＵの処理時間は短縮できても、データの入出力時間は短縮されず、結果として、解を得るまでの時間が短縮されないという第一の問題があった。
【０００５】
また、ガウスの消去法は、解を得るために、前進消去と後退代入の２つの処理を行わなければならないため、対象行列の行列要素を複数の外部記憶装置に分割して処理する場合、プログラム、つまり制御が複雑になるという第二の問題があった。
【０００６】
【課題を解決するための手段】
本発明では、第二の問題を解決すべく、解法アルゴリズムとして、制御を簡単にするガウス─ヨルダン法を採用し、また、第一の問題を解決すべく、係数行列を適当なブロックで分割し、他のプロセッサとデータの通信を行うことにより、全体の処理時間の短縮を図る。具体的には、請求項１に係る発明の場合、枢軸を示す情報、当該ブロックを示す情報、当該ブロックに属する所定の行数の行列要素と当該要素を示す情報を記憶する記憶手段と、当該記憶手段と後述の転送手段から得られる情報に基づいて、枢軸の属する行の行列要素を用いて、枢軸の属する列の枢軸以外の全要素を零とする消去処理を当該各要素の属する行の各要素に対し所定の列ごとに行う処理手段と、枢軸と当該処理に用いる行列要素と共にそれらの要素を示す情報を他のプロセッサに転送する転送手段とから構成する。第１図は、本発明の構成の原理図を表す。同図中、１は方程式の行列要素と当該要素を特定する情報等を記憶した記憶手段を、２は記憶手段１と転送手段３から得られる情報に基づいて、枢軸の属する行の行列要素を用いて、枢軸の属する列の枢軸以外の全要素を零とする更新処理を当該各要素の属する行の各要素に対し所定の列ごとに行う処理手段を表す。
【０００７】
本発明で用いるガウス─ヨルダン法について、説明する。上述したガウスの消去法においては、処理Ｐから明らかなように、方程式を一回り小さく変形して解くべく、枢軸Ａ（ｋ，ｋ）を用いて、第ｋ列の第ｋ行より下の部分だけを消去の対象としていた。これを変形して全非対角要素を消去するアルゴリズムが、ガウス─ヨルダン法である。つまり、ガウス消去法の処理Ｐの全体に『ｉ＝１からｋ−１』の処理を加えると、ガウス─ヨルダン法のアルゴリズムが得られる。具体的に書き下すと、
『ｉ＝１からｋ−１およびｋ＋１からＮまでに対し、
ｂ（ｉ）＝ｂ（ｉ）─Ａ（ｉ，ｋ）・ｂ（ｋ）／Ａ（ｋ，ｋ）、および
ｊ＝１からＮまでに対し、
Ａ（ｉ，ｊ）＝Ａ（ｉ，ｊ）−Ａ（ｉ，ｋ）・Ａ（ｋ，ｊ）／Ａ（ｋ，ｋ）』
となる。ｋ＝１からＮまでについて、この処理が終了すると、全非対角要素は０となり、対角要素のみが残り、簡単に解ｘ（ｉ）を得ることができる（ｉ＝１，・・・，Ｎ）。したがって、ガウス─ヨルダン法では、後退代入の必要がないため、プログラム、つまり制御が簡単になる。
【０００８】
【実施の形態】
本発明の実施の形態を、第２図から第８図に基づき説明する。なお、以下の説明は、請求項３に係る発明についてのものであるが、他の請求項についても基本的には同様である。第２図は、本発明の実施例を示す構成図である。同図中、１ａはＭ個からなるＤＡＳＤを、１ｂはＭ個からなるキャッシュメモリを、２はＭ個からなるプロセッサを、４はコントロール・プロセッサ（以下、「ＣＰ」という）を表す。ここで、ＤＡＳＤ１ａおよびキャッシュメモリ１ｂは第１図の記憶手段１に、プロセッサ２は第１図の処理手段２および転送手段３に、それぞれ対応するものである。解くべき方程式としては、Ｎ元の連立一次方程式、Ａｘ＝ｂを考える。なお、Ａ、ｘ、ｂは、前出式（１）と同一対象を表す。まず、本発明の全体の処理フローを、第３図に基づき説明し、その後に各処理ステップの詳細を説明する。
【０００９】
ＣＰ４は、係数行列Ａ、定数ベクトルｂからなる対象行列を、第４図に示すように、行ブロックごとに、各ＤＡＳＤ１ａに分割する。ＣＰ４は，各プロセッサ２に、担当するブロックを示す情報と枢軸の初期値Ａ（１，１）を示す情報とを送る。各プロセッサ２は、自配下のＤＡＳＤ１ａに格納された行ブロックを特定するための第５図に示すような情報を、主記憶に格納する。ＣＰ４からキャッシュメモリへの読出開始信号を受けた各プロセッサ２は、自配下のＤＡＳＤ１ａから処理単位である第６図に示す列ブロックに属する行列要素を、キャッシュメモリ１ｂに読出す（Ｓ１）。キャッシュメモリ１ｂには、例えば、第６図に示すように、行列要素が格納される。また、上述したように、各プロセッサ２は、その主記憶に、第５図に示すように、担当ブロックと枢軸を示す情報を格納しており、当該情報に基づき、処理における枢軸が自配下のＤＡＳＤ１ａにあるか否かを判定する（Ｓ２）。
【００１０】
自配下に枢軸があるプロセッサは、他のプロセッサに対し、自配下のキャッシュメモリにある枢軸を転送する。また、後で第９図を用いて説明するが、第ｊ列を処理する場合、第ｋプロセッサ（ｋ＝１〜ｊ−１）は、他のプロセッサに対し、第ｊ列の属するブロック内で、枢軸の属する第ｋ行の行列要素を送信する（Ｓ３）。枢軸の属するプロセッサは、キャッシュメモリ内の行列要素を用いて、枢軸の属さないプロセッサは、当該転送されてきた行列要素と自配下のキャッシュメモリ内の行列要素を用いて、枢軸の属する列の枢軸以外の全行列要素を零とするガウス−ヨルダン法による消去処理を行う。各プロセッサ２は、各列の消去処理を終えると、当該処理の完了通知をＣＰ４に送信し、ＣＰ４は、各プロセッサに次列の処理開始信号を送る。これを受けた各プロセッサ２は、主記憶内の枢軸指示情報を更新する。この処理を繰り返し、一の列ブロックに属する全枢軸について、前記消去処理を終了すると、各プロセッサ２は、ＣＰ４に対し、当該列ブロックの処理の完了を通知し（Ｓ４）、ＤＡＳＤに更新内容を書込む。ＣＰ４は、全プロセッサから当該通知を受信すると、各プロセッサ２に対し、次の列ブロックの行列要素をキャッシュメモリに読み出すトリガとなる読出開始信号を送信する。
【００１１】
また、各プロセッサ２は、主記憶内の枢軸指示情報に基づき、処理対象の列ブロックが最終ブロックであるか否かを判定する（Ｓ５）。最終ブロックでないと判定された場合は、次の列ブロックに属する行列要素をキャッシュメモリに読み込む。最終ブロックであると判定された場合は、既に非対角要素は、零と変形されているため、解ｘ（ｉ）を、ｘ（ｉ）＝ｂ（ｉ）／Ａ（ｉ，ｉ）として求める（Ｓ６）。ここで、ｂ（ｉ）およびＡ（ｉ）は、消去処理Ｓ４により更新された値である。以上が、本発明の処理の全体的なフローの概略である。
【００１２】
次に、各フローの詳細について、説明する。以下では、説明の簡単化のため、Ｎ＝２Ｍ、処理単位の列ブロックを２列として説明する。まず、対象行列の分割の態様を、第４図に基づき説明する。第４図において、第３図と同一符号を付したものは、第３図のものと同一の対象を示す。第４図において、５は、係数行列Ａと定数ベクトルｂからなる対象行列を表す。ＣＰ４は、対象行列の行列要素を、各ＤＡＳＤに均等となるよう割り当てる。この対象行列の各ＤＡＳＤへの分割については、今は、Ｎ＝２Ｍの場合を考えているから、第４図に示すように、行ブロックには、対象行列の各２行が割り当てられる。ＣＰ４は、各ＤＡＳＤに対し、分割された対象行列の行列要素を送信し、各プロセッサ２に対し、自配下にあるＤＡＳＤに格納されている行ブロックを特定する情報を送信する。各プロセッサ２は、受信したこの情報を、第５図に示すように、その主記憶に格納する。ＤＡＳＤに格納している行ブロックを特定する情報としては、行単位で分割しているため、第５図に示すように、行のみを特定し、各プロセッサは、担当ブロックに、フラグをたて、担当でないブロックと区別している。また、各プロセッサは、処理を行うにあたって、現在どの段階まで消去処理をしたか、つまり枢軸の情報を知る必要があるため、主記憶は、第５図に示すように、枢軸を示す情報を格納している。各プロセッサは、ＣＰ４からの上述の処理開始信号または読出開始信号を受けて、主記憶内の枢軸指示情報を逐次更新する。第５図では、１行目に枢軸があること、つまり、枢軸はＡ（１，１）であることを示している。
【００１３】
次に、処理単位である列ブロックを、第６図に基づき説明する。第６図は、対象行列において、処理単位である列ブロックを示した図である。ここでは、列ブロックの単位として２列を考えているため、第６図に示すように、一の列ブロックは２列の行列要素から構成されている。各プロセッサ２は、この列ブロック単位に、キャッシュメモリ１ｂにその行列要素を読出し、消去処理Ｓ４を行う。
【００１４】
次に、ＣＰ４からの上述の読出開始信号の受信により、キャッシュメモリに読出されるデータ構造について、第７図に基づいて説明する。第７図は、行ブロック１担当のキャッシュメモリに格納される列ブロック１の行列要素を示す。各プロセッサ２は、自配下のＤＡＳＤに格納された行列要素を列ブロックごとに読出すので、列ブロック１処理時の行ブロック１担当のキャッシュメモリに、第７図に示すように、Ａ（１，１）、Ａ（１，２）、Ａ（２，１）およびＡ（２，２）の値を格納する。他のキャシュメモリについても、同様である。
【００１５】
次に、枢軸以外のプロセッサ間のデータ通信を、第９図に基づいて説明する。第９図は、係数行列Ａと定数ベクトルｂからなる対象行列を、行ブロックおよび列ブロックに分割した図である。ブロックを（行ブロック、列ブロック）として特定すると、第９図に示すように、ブロック（ｋ，ｋ）は、枢軸の含まれるブロックを示す（ｋ＝１〜Ｍ）。ここでは、行ブロックに分割し、列ブロック毎に処理を進める場合を考えているため、列ブロックｋの消去処理を行う場合、枢軸の属する第ｊプロセッサは、他のプロセッサに対し、ブロック（ｊ，ｋ）内の枢軸の属する行の行列要素を送信する。例えば、列ブロック２の消去処理を行う場合、第１プロセッサは、他のプロセッサに対し、ブロック（１，２）内の枢軸Ａ（１，１）の属する行列要素、Ａ（１，３）、Ａ（１，４）を送信する。各プロセッサは、転送されてきた行列要素を記憶しておき、各列ブロックの消去処理前に更新処理を行う。
【００１６】
各記憶手段が持つべきデータ等についての説明は終了したので、列ブロック１の行列要素がＤＡＳＤからキャッシュメモリに読出された後の消去処理Ｓ４について、第１０図に基づき説明し、そのあと、具体的な処理を説明する。列ブロックＬ（Ｌ＝１〜Ｍ）の消去処理Ｓ４は、第１０図に示すように、４つのステップからなる。まず、第一に、列ブロックＪ（Ｊ＝１〜Ｌ−１）の消去処理による列ブロックＬの行列要素の更新を、Ｊ＝１，２，・・・，Ｌ−１の順に行う（Ｓ４１）。したがって、列ブロック１の消去処理においては、このステップはない。この更新処理を終えると、各プロセッサは、自メモリ内にある枢軸指示情報から特定される枢軸を用いて、ガウス−ヨルダンのアルゴリズムによる消去処理を行う（Ｓ４２）。消去処理を終えると、各プロセッサは、列ブロック（Ｌ＋１）〜Ｍで使用する行列要素の更新処理を行う（Ｓ４３）。各プロセッサは、ＣＰ４に対し、列ブロックＬの処理が終了した旨の通知を送信し（Ｓ４４）、列ブロックＬの消去処理を終わると共に、処理後の内容を、各ＤＡＳＤに書込む。
【００１７】
次に、第１０図に示す消去処理にしたがって、消去処理を具体的に説明する。まず、各プロセッサ２は、主記憶内の枢軸情報を参照し、自キャッシュメモリに枢軸があるか否かを判定する。現在、第５図に示すように、枢軸情報は「１」を示している。したがって、第１行担当のプロセッサ１は、自キャッシュメモリ内の行列要素Ａ（１，２）およびＡ（１，１）を、他のプロセッサに転送する。その後、各プロセッサは、以下の消去処理を行う。
第１プロセッサ：
Ａ（２，１）＝Ａ（２，１）／Ａ（１，１）
Ａ（２，２）＝Ａ（２，２）−Ａ（２，１）・Ａ（１，２）。
第２プロセッサ：
Ａ（３，１）＝Ａ（３，１）／Ａ（１，１）
Ａ（４，１）＝Ａ（４，１）／Ａ（１，１）
Ａ（３，２）＝Ａ（３，２）−Ａ（３，１）・Ａ（１，２）
Ａ（４，２）＝Ａ（４，２）−Ａ（４，１）・Ａ（１，２）。
第３プロセッサ：
・・・
第Ｍプロセッサ：
Ａ（Ｎ─１，１）＝Ａ（Ｎ−１，１）／Ａ（１，１）
Ａ（Ｎ，１）    ＝Ａ（Ｎ，１）／Ａ（１，１）
Ａ（Ｎ−１，２）＝Ａ（Ｎ−１，２）─Ａ（Ｎ−１，１）・Ａ（１，２）
Ａ（Ｎ，２）    ＝Ａ（Ｎ，２）─Ａ（Ｎ，１）・Ａ（１，２）。
ここで、第ｉプロセッサとは、行ブロックｉ担当のプロセッサをいう（ｉ＝１〜Ｍ）。各プロセッサは、列ブロック１の第１列の消去処理を終わったことを、ＣＰ４に対し通知する。ＣＰ４は、全プロセッサからその通知を受けると、各プロセッサに対し、第２列の消去処理を開始する信号を送信する。その信号を受けた各プロセッサ２は、枢軸指示情報をＡ（２，２）を示すように更新し、枢軸Ａ（２，２）を、他のプロセッサに転送する。各プロセッサ２は、既に枢軸Ａ（２，２）の値は変形済であるため、次の列ブロックで使用する行列要素の更新処理、第１プロセッサ：
Ａ（１，２）＝Ａ（１，２）／Ａ（２，２）
第２プロセッサ：
Ａ（３，２）＝Ａ（３，２）／Ａ（２，２）
Ａ（４，２）＝Ａ（４，２）／Ａ（２，２）
第３プロセッサ：
・・・
第Ｍプロセッサ：
Ａ（Ｎ−１，２）＝Ａ（Ｎ−１，２）／Ａ（２，２）
Ａ（Ｎ，２）＝Ａ（Ｎ，２）／Ａ（２，２）
を行う。この処理が終了すると、各プロセッサ２は、列ブロック１の処理が終了したことを、ＣＰ４に対し通知し、ＣＰ４は、各プロセッサ２に対し、処理の終了した列ブロック１の行列要素をＤＡＳＤに書き込み、次の列ブロックをキャッシュメモリに読み込むよう読出開始信号を送信する。その信号を受信した各プロセッサ２は、ＤＡＳＤへの書込処理、キャッシュメモリへの読込処理を行う。また、前記読出開始信号を受信した各プロセッサ２は、自メモリ内の枢軸指示情報を、Ａ（３，３）を示すように更新する。各プロセッサ２は、その枢軸指示情報を参照し、転送する行列要素を決定する。具体的には、自配下のキャッシュメモリに枢軸の属する第２プロセッサは、その属する枢軸Ａ（３，３）を転送し、枢軸指示情報よりその番号の小さい第１プロセッサは、列ブロック２に属する自配下のキャッシュメモリにあるＡ（１，３）、Ａ（１，４）、Ａ（２，３）およびＡ（２，４）を特定する情報とその値を、他のプロセッサに転送する（第９図参照）。受信した各プロセッサは、それ以降の列ブロック処理で生じる更新処理に用いるため、これらの転送された行列要素をそのキャッシュメモリに記憶しておく。
【００１８】
各プロセッサ２は、列ブロック２についての消去処理を行う前に、列ブロック１の消去処理による更新処理を行う。具体的には、各プロセッサは、対象行列の列ブロック１の第１列の消去処理による更新処理：
第１プロセッサ：
Ａ（２，３）＝Ａ（２，３）−Ａ（２，１）・Ａ（１，３）
Ａ（２，４）＝Ａ（２，４）−Ａ（２，１）・Ａ（１，４）
第２プロセッサ：
Ａ（３，３）＝Ａ（３，３）−Ａ（３，１）・Ａ（１，３）
Ａ（４，３）＝Ａ（４，３）−Ａ（４，１）・Ａ（１，３）
Ａ（３，４）＝Ａ（３，４）−Ａ（３，１）・Ａ（１，４）
Ａ（４，４）＝Ａ（４，４）−Ａ（４，１）・Ａ（１，４）
第３プロセッサ：
・・・
第Ｍプロセッサ：
Ａ（Ｎ−１，３）＝Ａ（Ｎ−１，３）─Ａ（Ｎ−１，１）・Ａ（１，３）
Ａ（Ｎ，３）＝Ａ（Ｎ，３）−Ａ（Ｎ，１）・Ａ（１，３）
Ａ（Ｎ−１，４）＝Ａ（Ｎ−１，４）−Ａ（Ｎ−１，１）・Ａ（１，４）
Ａ（Ｎ，４）＝Ａ（Ｎ，４）−Ａ（Ｎ，１）・Ａ（１，４）
を行う。また、各プロセッサは、対象行列の列ブロック１の第２列の消去処理に伴う更新処理：
第１プロセッサ：
Ａ（１，３）＝Ａ（１，３）−Ａ（１，２）・Ａ（２，３）
Ａ（１，４）＝Ａ（１，４）−Ａ（１，２）・Ａ（２，４）
第２プロセッサ：
Ａ（３，３）＝Ａ（３，３）−Ａ（３，２）・Ａ（２，３）
Ａ（４，３）＝Ａ（４，３）−Ａ（４，２）・Ａ（２，３）
Ａ（３，４）＝Ａ（３，４）−Ａ（３，２）・Ａ（２，４）
Ａ（４，４）＝Ａ（４，４）−Ａ（４，２）・Ａ（２，４）
第３プロセッサ：
・・・
第Ｍプロセッサ：
Ａ（Ｎ−１，３）＝Ａ（Ｎ−１，３）─Ａ（Ｎ−１，２）・Ａ（２，３）
Ａ（Ｎ，３）＝Ａ（Ｎ，３）−Ａ（Ｎ，２）・Ａ（２，３）
Ａ（Ｎ−１，４）＝Ａ（Ｎ−１，４）−Ａ（Ｎ−１，２）・Ａ（２，４）
Ａ（Ｎ，４）＝Ａ（Ｎ，４）−Ａ（Ｎ，２）・Ａ（２，４）
を行う。これで、列ブロック１の消去処理による列ブロック２の行列要素の更新処理を終わり、列ブロック２の非対角要素の消去処理を行う。各プロセッサは、以上のようにして、ＣＰ４の制御の下、キャッシュメモリに列ブロックごとに行列要素を読み込み、ガウス−ヨルダン法による消去処理を進めていく。
【００１９】
【発明の効果】
本発明によると、係数行列を複数の記憶手段に分割し、並列に処理するため、従来、計算時間の大部分を占めていた入出力時間を、大幅に短縮（理論的には、記憶手段の数をＭとすると、処理時間は１／Ｍに短縮）することができる。これは、解法アルゴリズムとして、ガウス−ヨルダン法を用いることにより、プログラムを簡素化し、分割されたデータの扱いを簡易なものとすることができたことに起因する。本発明においては、行列要素を分割して持つことができるため、従来より、大きな規模の連立一次方程式を解くことが可能となる。また、本発明では、行ブロックまたは列ブロックごとにまとめて処理を行うため、列または行ごとに行う処理より、高速に処理できるという効果もある。
【図面の簡単な説明】
【図１】    本発明の構成を示す原理図
【図２】    本発明の実施例を示す構成図
【図３】    本発明の処理フローを示す図
【図４】    対象行列の分割の態様を示す図
【図５】    枢軸と担当ブロックを示すデータ構造図
【図６】    処理単位である列ブロックを示す図
【図７】    キャッシュメモリ上の行列要素のデータ図
【図８】    行列要素Ａ（ｉ，ｊ）の更新処理に必要な行列要素を示す図
【図９】    転送する行列要素を示す図
【図１０】  消去処理Ｓ４を示す図
【図１】
0003694946.tif 000003
【図２】
0003694946.tif 000004
【図３】
0003694946.tif 000005
【図４】
0003694946.tif 000006
【図５】
0003694946.tif 000007
【図６】
0003694946.tif 000008
【図７】
0003694946.tif 000009
【図８】
0003694946.tif 000010
【図９】
0003694946.tif 000011
【図１０】
0003694946.tif 000012