JPH0748204B2

JPH0748204B2 - 行列演算処理方法

Info

Publication number: JPH0748204B2
Application number: JP63171506A
Authority: JP
Inventors: 正憲杉田
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1988-07-08
Filing date: 1988-07-08
Publication date: 1995-05-24
Anticipated expiration: 2010-05-24
Also published as: JPH0221361A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、ベクトル計算機における行列演算をベクトル
アキュムレータを使用して高速に行う行列演算処理方法
に関する。

〔従来の技術〕

従来より、行列の逆行列の算出や、連立１次方程式の解
法としては例えば、山内二郎他著「電子計算機のための
数値計算法Ｉ」P7〜P22に示されるように掃き出し法
や、ガウスの消去法が、一般的に知られている。

逆行列の算出は、単位行列をＥとすれば、Ａ・Ｘ＝Ｅと
なるＸを求めればよく、それには、連立１次方程式AX_j
＝e_j（X_jはＸの第ｊ列、e_jはＥの第ｊ列）をｊ＝1,2,
…,nについて解けばよい。従って、以下の説明では、Ｐ
・Ｘ＝Ｑを満たす、行列Ｘの算出について述べる。ここ
で、P,Qは、それぞれｍ行ｍ列、ｍ行ｎ−ｍ列の与えら
れた行列であり、Ｘは求めるべき、ｍ行ｎ−ｍ列の行列
である。

掃き出し法では、なる行列Ａについて、１）第ｋ行をa_kkで割る。（a_kkをピボットと呼ぶ）２）ｊ＝1,2,…,mに対し（ただしｊ＝ｋを除く）、第ｊ
行から第ｋ行のa_jk倍を引く。

３）上記１）,2）をｋ＝1,2,…,mについて繰り返す。

という計算を行う。

ガウスの消去法では、１）ｊ＝ｋ＋1,…,mに対し、第ｊ行から第ｋ行のa_jk／a
_kk倍を引く。

（a_kkをピボットと呼ぶ）２）上記１）をｋ＝1,2,…,m−１について繰り返す。

という計算を行う。

掃き出し法においても、ガウスの消去法においても、各
段階のピボット（a_kk）は、“0"であってはならない。
また、“0"でなくても、計算の途中で、ピボットが極め
て小さな値となることがある。このまま計算を続けるこ
とは、計算の精度上、好ましくない。

従って、従来より、ピボットの選択という操作が、必要
であった。

この操作は、例えばｋ回目のピボットを決定する際に、
a_kkを無条件にピボットにするのではなく、ｉ＝k,k＋1,
…,mなるa_ikの中で、絶対値が最も大きなものを選択す
るものである。そして、その要素を含む行をピボット行
とし、第ｋ行とピボット行との間で行の入れ換えを行っ
た後、計算を行う。

このような行列演算を高速に行うための計算機としてベ
クトル計算機がある。第６図は、このような従来の行列
演算処理方法を行うベクトル計算機の一例を、ブロック
図で示したものであり、図において、１は演算対象の行
列を記憶する主メモリ、２は演算処理を行う演算装置
（CPU）、３は複数のベクトルレジスタからなり、主メ
モリ１から演算の対象となる行列を読み出して、保持す
るベクトルアキュムレータ（VACC）である。

また、第７図は、特開昭62-138968号公報に示された、
このような従来の行列演算方法を行うベクトル計算機の
別の一例を示すブロック図であり、図において、５はス
カラ値の保持するスカラアキュムレータ（SACC）、6a,6
bは主メモリ１のデータをベクトルアキュムレータ３に
読み出すためのロードバス、７はベクトルアキュムレー
タ３のデータを主メモリに書き込むためのストアバス、
８は主メモリ１とベクトルアキュムレータ３およびスカ
ラアキュムレータ５との間でロードバス6a,6bやストア
バス７を介してデータのやり取りを行うための転送用ス
イッチング回路、９はベクトルアキュムレータ３および
スカラアキュムレータ５と演算装置２との間で演算デー
タのやり取りを行う演算用スイッチング回路である。な
お、図６と同じ番号は同じものを示す。

ベクトルアキュムレータ３内のベクトルレジスタのデー
タを演算用スイッチング回路９を介して演算装置２で演
算する処理は、パイプラインにより高速で行われるの
で、行列演算処理は、初めに主メモリ１から行列データ
の行データをベクトルデータとしてベクトルアキュムレ
ータ３内のベクトルレジスタに取り込み、ベクトルデー
タの演算を演算装置２で行い、途中の演算結果をベクト
ルアキュムレータ３に書き戻し、最後に最終結果を主メ
モリ１に書き戻すことによって行われる。

次に、第８図〜第10図のフローチャートに基づき、従来
の行列演算処理方法について説明する。なお、ここで
は、掃き出し法により、前述したＰ・Ｘ＝Ｑの方程式を
解く場合を例にとって、説明する。

第８図において、まず、演算の対象となる行列Ｐ・Ｑを
主メモリ１からベクトルアキュムレータ３にロードする
（ステップ81）。このとき、行列の行データをベクトル
データとして、ベクトルアキュムレータ３のベクトルレ
ジスタごとに対応させて、読み込む。次に、ｋ＝１と
し、（ステップ82）第９図に示すフローチャートに従っ
て、ピボット選択を行う（ステップ83）。第９図におい
て、ピボット選択は、まず、a_ik（ｉ＝k,k＋1,…,m）の
中で絶対値が最大のものを選択し、ピボット値とする
（ステップ91）。このピボット値が“0"であれば、エラ
ーとなる（ステップ92）。次に、ピボット行の番号r_kと
ｋとを比較し（ステップ93）、r_k＝ｋであれば第８図の
フローへ戻り、r_k≠ｋであれば、（ステップ94）第10図
に示すフローチャートに従って、行列のｋ行目とr_k行目
を入れ換え、第８図のフローへ戻る。

第10図において、ベクトルアキュムレータ３に空きのベ
クトルレジスタの有無（ステップ101）によって、処理
方法が変わる。空きのレジスタがあれば、ｋ行目の行デ
ータに対応するベクトルレジスタの内容を、空きレジス
タに転送し（ステップ102）、r_k行目の行データに対応
するベクトルレジスタの内容をｋ行目の行データに対応
するベクトルレジスタに転送する（ステップ103）。次
に、空きレジスタに転送した元のｋ行目の行データを、
r_k行目の行データに対応するベクトルレジスタに転送す
る（ステップ104）ことによって、ｋ行目とr_k行目の行
データの入れ換えが、ベクトルアキュムレータ３内のレ
ジスタ間の転送で行われる。

空きのレジスタがなければ、ステップ105〜107に示すよ
うに、主メモリ１内の空きエリアを使用して、行の入れ
換えを行う。この場合、主メモリへのアクセスを伴うの
で、ベクトル計算機の処理速度が落ちる。

次に第８図に戻り、上記ステップ83のピボット選択が行
われると、ピボット行をピボット値で割る（ステップ8
4）。そして、ピボット行を除いた全ての行に対して掃
き出しを行う（ステップ85〜87）。上記掃き出し操作が
全て完了すれば、ベクトルアキュムレータ３の上の結果
を主メモリ１にストアして演算を終了する。

〔発明が解決しようとする課題〕

従来の方法によれば、ピボット選択の際に、各行毎に、
行の入れ換え操作が必要となる可能性がある。この操作
では、ベクトルアキュムレータ内の行データの交換を必
要とし、その行データ交換のたびにその処理時間が必要
となるという課題があった。

また、ベクトルアキュムレータは、一般に、数個（ｓ
個）のベクトルレジスタから構成されており、行列の行
データをベクトルデータとして、ベクトルレジスタごと
に対応させて、パイプラインにより行列の高速演算を行
う場合、従来の方法のように行の入れ換え操作が必要に
なると、行列の行数がｓ−１行までであれば主メモリに
対するアクセスなしに行の入れ換えできるが、行列の行
数がｓ行であれば、行データ交換のたびに主メモリへの
アクセスが必要となり、処理性能が低下するという課題
があった。

本発明は、上記のような課題を解消するためになされた
もので、ベクトル計算機の演算処理能力を生かして、逆
行列演算もしくは、係数が等しい複数の連立１次方程式
を高速に処理できる行列演算処理方法を得ることを目的
とする。

〔課題を解決するための手段〕

本発明に係る行列演算処理方法は、ピボット選択の際
に、各行の行交換状態を記録しておくためのロウ・イン
デックステーブル（以下RIテーブルと呼ぶ）を作成する
ものである。

〔作用〕

ピボット選択により、行の入れ換えの可能性が生じた場
合には、行の各要素を入れ換える代わりに、本発明にお
けるRIテーブルの入れ換え行に対応する行番号を入れ換
えておき、演算の最終段階で、RIテーブルを参照しなが
ら、ベクトルアキュムレータ内の結果を主メモリに格納
する。

〔発明の実施例〕

以下、この発明の一実施例を図について説明する。第１
図において、１は主メモリ、２は演算処理を行う演算装
置（CPU）、３は演算対象となる行列を保持するベクト
ルアキュムレータ、４は演算の対象となる行列と同じ行
数（ｍ）からなり、ピボット選択により行の入れ換えの
必要性が生じた場合に実際の行を入れ換える代わりに、
対応する行の番号を入れ換えるためのRIテーブルであ
る。

また、第２図は、RIテーブル４の行番号の入れ換えを示
す説明図、第３図〜第５図は、掃き出し法により、Ｐ・
Ｘ＝Ｑを満たす行列Ｘを求める場合の、本発明のフロー
チャートである。

演算の対象となる行列、P,Qはそれぞれ主メモリ１から
ベクトルアキュムレータ３にロード（ステップ30）され
た後、第１回目のピボット選択を行う（ステップ31〜33
および第４図）。第１回目のピボット選択では、a₁₁,a
₂₁,…,a_m1の中で絶対値が最も大きな要素を選び出し、
その要素をピボットとし、その要素を含む行がピボット
行となる（ステップ41）。今、仮にa_r1がピボットに選
ばれとすれば、１行目とｒ行目の交換を行う必要がある
が、本発明では、実際の行の交換を行う代わりにRIテー
ブル４の１行目とｒ行目を交換する（ステップ44）。RI
テーブル４は、演算がはじまる前に、１行目から順に1,
2,…,r,…,mの値が初期設定されているから、１回目の
ピボット選択により、RIテーブル４の内容は、１行目か
ら順にr,2,…,1,…,mとなる。

２回目以降ｍ−１回目までのピボット選択についても同
様で、第２図に示すようにｋ回目のピボット選択で、第
１行がピボット行となった場合には、RIテーブル４の第
１行目の内容R₁と第ｋ行目の内容R_kを入れ換える。

このRIテーブル４を使用することにより、１回の行交換
で、ｎ個の要素を交換しなければならなかったものが、
１要素の交換だけで済ませることができる。もしも、ｍ
−１回のピボット選択で毎回行交換が必要となる場合に
は（ｍ−１）・ｎ回分の要素交換をしなくても済む。ま
た、RIテーブルをベクトルアキュムレータ３以外のエリ
アに設けているので、行交換のための空きベクトルレジ
スタをベクトルアキュムレータ３内に持つ必要がなく、
ベクトルアキュムレータ３内の全てのベクトルレジスタ
を行データの格納場所として使用できる。

ピボット選択と、ピボット行以外の全ての行に対する掃
き出しが、１〜ｍ行について行われた後、ベクトルアキ
ュムレータ３には、行交換されないまま結果が残ってい
るため、RIテーブル４を参照しながら、正しい行順で主
メモリ１に処理結果をストアする（ステップ38）。即
ち、第５図に示すように、RIテーブル４のｋ行目にR_kが
入っていたとすれば、ベクトルアキュムレータ３内の行
列の第R_k行の要素群を主メモリ１内の行列の第ｋ行目に
ストアする。

また、上記実施例では、掃き出し法を用いて、PX＝Ｑを
満たすＸを求める場合について説明したが、ガウスの消
去法や、その他、行列の行や列の入れ換え操作を要する
演算にも適用できる。

〔発明の効果〕

以上のように、この発明によれば、行の入れ換え状態を
示すRIテーブルを設置したために、行の入れ換え操作を
要する行列演算において、入れ換え行を構成する全要素
群を入れ換えなくて済み、RIテーブル内の１要素間を交
換するだけでよいため、演算時間が短縮され、高速な行
列演算が可能となる。また、RIテーブルをベクトルアキ
ュムレータ以外のエリアに設けているので、行列の行デ
ータをベクトルデータとして、ベクトルレジスタごとに
対応させて、パイプラインにより行列の高速演算を行う
場合、行交換のための空きベクトルレジスタをベクトル
アキュムレータ内に持つ必要がなく、ベクトルアキュム
レータ内の全てのベクトルレジスタを行データの格納場
所として使用できる。

【図面の簡単な説明】

第１図は本発明の一実施例による行列演算処理方法を示
すブロック図、第２図は本発明による、行交換状態を記
録するテーブルの説明図、第３図〜第５図は、本発明に
よる掃き出し法のフローチャート、第６図および第７図
は、従来の行列演算処理方法を行うベクトル計算機の構
成を示すブロック図、第８図〜第10図は、従来の方法に
よる掃き出し法のフローチャートである。図中、１は主メモリ、２は演算装置、３はベクトルアキ
ュムレータ、４はRIテーブルを示す。なお、図中、同一符号は、同一又は相当部分を示す。

Claims

【特許請求の範囲】

【請求項１】主メモリと、主メモリから読み出した行列
の要素データを保持するベクトルアキュムレータと、行
列の演算を行う演算装置とを備えたベクトル計算機によ
る行列演算処理方法において、行または列の交換状態を
記録するテーブルを設け、行または列の交換を行う場合
は、上記ベクトルアキュムレータの要素データを交換す
る代わりに、交換する行または列に対応する数値を上記
テーブルに記録し、演算後のベクトルアキュムレータの
要素データを、上記テーブルの記録に従って読み換え、
本来の行または列の順に主メモリに書き出すことを特徴
とする行列演算処理方法。