JPH0748207B2

JPH0748207B2 - 行列演算装置

Info

Publication number: JPH0748207B2
Application number: JP1096079A
Authority: JP
Inventors: 俊夫赤羽; 好司藤本; 尚行福田
Original assignee: Sharp Corp
Current assignee: Sharp Corp
Priority date: 1989-04-14
Filing date: 1989-04-14
Publication date: 1995-05-24
Anticipated expiration: 2010-05-24
Also published as: JPH02273867A

Description

【発明の詳細な説明】〈産業上の利用分野〉この発明は、零成分を多く含む行列（スパース行列）と
ベクトルとの演算に適した行列演算装置に関する。

〈従来の技術〉自然界における現象を計算機を用いてシュミレーション
する場合、２次元配列で表わされる行列を変換行列とし
て、１次元配列で表わされるベクトルの１次変換を計算
することが多い。例えば、次式（１），（２）に示すよ
うな行列演算が挙げられる。

ｙ＝Wx …（１） v^t＝u^tW …（２）ここで、ｘ＝（x₁,x₂,x₃,…,x_M）^tは入力ベクトル、ｙ
＝（y₁,y₂,y₃,…,y_N）^tは出力ベクトル、Ｗ＝｛Wji｝は
一次変換のためのＮ行Ｍ列の変換行列、ｕ＝（u₁,u₂,
u₃,…,u_N）^tは入力ベクトル、ｖ＝（v₁,v₂,v₃,…,v_M）^t
は出力ベクトル、（＊）^tは行と列を入れ換えた転置行
列を示している。

従来のベクトルプロセッサなどの行列演算装置は、上記
変換行列Ｗの各要素Wjiを表わすデータを記憶するメモ
リと、この要素Wjiと入力ベクトルの要素との積和の計
算アルゴリズムを記憶する記憶手段と、この計算アルゴ
リズムに従って計算する演算手段とを備えて、（１）式
の計算のとき出力yj（ｊ＝1,2,…,N）を、次式（３）に
従って計算するようにしている。

また（２）式の計算のとき各列の出力v_i（ｉ＝1,2,…,
M）を、次式（４）に従って計算するようにしている。

なお、これら式（３），（４）の計算を模式的に示すと
それぞれ第16図、第17図のようになる。

〈発明が解決しようとする課題〉ところで、上記行列演算を現実の問題に適用するにあた
って、上記変換行列Ｗの要素Wjiのうち零である要素
（以下、「零要素」と呼ぶ）の占める割合が大きくなる
場合がある。たとえば、神経回路網のシュミレーション
において、一方の神経回路素子群が他方の神経回路素子
群から受け取る伝達信号は、送り手の各素子の出力を入
力ベクトルｘとし、送り手側の各素子から受け手側の各
素子への結合の強さ（結合係数）を変換行列Ｗとした一
次変換ｙ＝Wxと考えることができるが、このとき、すべ
ての神経回路素子間が接続されていることは稀であっ
て、逆に、各素子間の結合係数すなわち変換行列Ｗの要
素のうち大部分が零要素である（スパース行列である）
場合が多い。この傾向は神経回路網が大規模になるほど
強くなる。

このような場合、上記従来の演算処理装置は、零でない
要素（以下、「非零要素」と呼ぶ）が多い行列を取り扱
う場合と同様に、上記Ｎ行Ｍ列の変換行列Ｗの各要素Wj
iをそのままＮ×Ｍ個の実数としてメモリに割り当てて
記憶する必要があり、また、上記行列演算処理１回につ
き乗算と加算とをＮ×Ｍ回ずつ行なっている。このた
め、零要素を記憶・計算する無駄が生じていると考えら
れる。

そこで、スパース行列の非零要素からなるデータ列を格
納した行列メモリと、上記スパース行列内での各非零要
素の位置情報を記憶したインデックスメモリを備えて、
上記インデックスメモリの位置情報を参照しつつ上記ス
パース行列の非零要素のみと入力ベクトルの要素との積
和を演算する線形変換方式が提案されている（特開昭53
-64439号公報）。この線形変換方式によれば、メモリの
記憶量と計算量を低減することができる。

しかしながら、この線形変換方式では、インデックスメ
モリに位置情報として行番号を表す整数と列番号を表す
整数とを格納しているため、行列メモリの非零要素を読
み出すためには、別途アドレスコントローラによって上
記インデックスメモリの内容に基づいてアドレスを指定
しなければならない。つまり、行列メモリのアドレスを
指定するために複雑な制御を行わなければならないとい
う問題がある。

そこで、この発明の目的は、大規模なスパース行列演算
処理を行なうときにメモリの記憶量と計算量を低減する
ことができる上、簡単に制御できる行列演算装置を提供
することにある。

〈課題を解決するための手段〉上記目的を達成するために、この発明の行列演算装置
は、２次元配列で表わされる行列の各要素について零で
ある要素か零でない要素かを特定するデータを格納する
第１のメモリと、上記行列の零でない要素の内容を表わ
すデータを格納する第２のメモリと、上記第１のメモリ
に格納されたデータを参照して、上記行列の要素が零で
あるか否かを判別する判別手段と、上記判別手段によっ
て零でないと判別された行列の要素について、上記第２
のメモリに格納されたデータと入力ベクトルの要素とを
乗算して、積和を求める演算手段を備えた行列演算装置
において、上記第１のメモリは、上記行列内で、零であ
る要素が連続して並ぶ数を表わす整数と、零でない要素
が連続して並ぶ数を表す整数とを、上記行列内の各連続
する並びの順に格納していることを特徴としている。

〈作用〉上記判別手段によって第１のメモリに格納されたデータ
を参照して、参照した上記行列の要素が零であるとき
は、何ら計算を行なうことなく、次の要素の参照を続け
る。そして、参照した要素が零でないとき、上記演算手
段によって上記第２のメモリに格納されたデータと、入
力ベクトルのこのデータに対応する要素とを乗算する。
１つの行または列について、この積和を計算して、出力
ベクトルの１つの要素とする。そして、各行または各列
について、この計算を行なって、出力ベクトルの全要素
を求める。

このように行列演算処理を行なう場合、例えば上記行列
の全要素（Ｎ×Ｍ個の実数）のうち非零要素の占める割
合がｋ％であるとき、この行列の要素を記憶するための
上記第２のメモリの記憶量は、実数にしてＮ×Ｍ×k/10
0個分となる。また、上記行列演算処理１回につき乗算
と加算を行なう回数は、それぞれＮ×Ｍ×k/100とな
る。したがって、非零要素の占める割合が少ない（ｋが
小さい）ときに、上記行列の要素の記憶量と上記演算処
理の計算量が低減される。

しかも、上記第１のメモリは、上記行列内で、零である
要素が連続して並ぶ数を表わす整数と、零でない要素が
連続して並ぶ数を表す整数とを、上記行列内の各連続す
る並びの順に格納しているので、第２のメモリの内容を
読み出すときにそのアドレス指定が簡単に行われる。す
なわち、第１のメモリを例えばポインタによって順にス
キャンして、非零要素が並ぶ数を表す整数が検出された
とき、この整数分だけ順に第２のメモリに格納された非
零要素の内容を表すデータを読み出せば良い。このよう
に、第１のメモリの内容検出と、第２のメモリの内容読
み出しとを並行して進めることによって、簡単に第２の
メモリのアドレス指定が行われる。この結果、この行列
演算装置の制御は簡単に行われる。

〈実施例〉以下、この発明の行列演算装置を実施例により詳細に説
明する。

第１図はこの発明の基礎となる第１の行列演算装置を示
している。この行列演算装置は、CPU（中央演算処理装
置）１と、所定の計算アルゴリズムを記憶するROM2と、
変換行列Ｗについての情報を記憶する第１のメモリ11お
よび第２のメモリ12と、入力ベクトルｘ＝（x₁，…,xj,
…，x_M）^tまたはｕ＝（u₁，…,uj,…u_N）^tの情報を入力
する入力装置21と、出力ベクトルｙ＝（y₁，…,yj,…
y_N）^tまたはｖ＝（v₁，…,vj,…，v_M）^tの情報を出力す
る出力装置22を備えている。

上記CPU1は、上記入力装置21から入力ベクトルｘの各要
素を表わすデータを受けて、上記第１のメモリ11および
第２のメモリ12を参照し、ROM2が記憶する計算アルゴリ
ズムに従って、上記入力ベクトルｘまたはｕの一次変換
を計算して、出力ベクトルｙまたはｖを表わすデータを
上記出力装置22に出力することができる。第７図に示す
ように、上記入力装置21は、入力ベクトルｘの各要素xi
を表わすデータを保持可能な入力バッファ302およびこ
の入力バッファ302の各データXTxp（xp＝1,2,…,M）を
指すポインタ（指示値xp）306と、入力ベクトルｕの各
要素ujを表わすデータを保持可能な入力バッファ304お
よびこの入力バッファ304の各データUTup（up＝1,2,…
Ｎ）を指すポインタ（指示値up）308とからなってい
る。上記出力装置22は、出力ベクトルｙの各要素tjを表
わすデータを保持可能な積和演算バッファ兼用の出力バ
ッフア303およびこの出力バッフア303の各データYTyp
（yp＝1,2,…,N）を指すポインタ（指示値yp）307と、
出力ベクトルｖの各要素viを表わすデータを保持可能な
積和演算バッファ兼用の出力バッフア305およびこの出
力バッフア305の各データVTvp（vp＝1,2,…Ｍ）を指す
ポインタ（指示値vp）309とからなっている。なお、第
７図中の301は、この行列演算装置の機能を説明するた
めに、例として変換行列Ｗの各要素Wjiを２次元配列に
よって表わしたものである。図中、“0"はWji＝０であ
る零要素、“W"はWji≠０である非零要素を表わしてい
る。また、piは零要素が行方向に並ぶ数、qiは非零要素
が行方向に並ぶ数を表わしている。第２図に示すよう
に、上記第１のメモリ11は、上記変換行列Ｗの零要素が
連続して並ぶ数を表わす整数を記憶しているインデック
ステーブル401と、このインデックステーブル401の各デ
ータITip（ip＝1,2,…）を指すポインタ（指示値ip）40
3とからなっている。一方、第３図に示すように、上記
第２のメモリ12は、上記変換行列Ｗの非零要素の内容を
表わすデータを順に格納している係数メモリ402と、こ
の係数メモリ402の各データWTwp（wp＝1,2,…）を指す
ポインタ（指示値wp）404とからなっている。

上記インデックステーブル401、係数メモリ402は、次の
ようにして作成される。第７図に示した上記変換行列W3
01の各行を１行目から順に左から右に調べてゆき、非零
要素のときその内容（実数）を表わすデータを、上記係
数メモリ402に格納する一方、この非零要素の左側に並
ぶ零要素の数piに１を足した整数（pi＋１）をｎビット
のデータで表わして上記インデックステーブル401に格
納する（以下、単に「整数を登録する」という）。な
お、上記非零要素の左隣が非零要素である場合、pi＝０
であるため、登録する整数は１となる。非零要素がqi個
並ぶときは上記インデックステーブル401には整数１を
（qi−１）個続けて登録することになる。各行の行末に
きたときは、行末記号delim（delim＝2ⁿ−１）を登録す
る。行末が零要素である場合、この行末の零要素を含む
零要素の並びの数（零要素が並んでおらず、左隣が非零
要素のときは１）を登録するのでなく、行末記号delim
を登録する。ところで、このようにｎビットのデータ
（１ワード）で整数を表わす場合、表わすことができる
整数は（2ⁿ−１）までであり、さらに整数（2ⁿ−１）を
上に述べたように行末記号delimに使用しているので、
結局、１ワードで表すことができる整数は（2ⁿ−２）ま
でとなっている。そこで、（2ⁿ−２）個以上零要素が並
ぶときは、次のように２ワード以上使ってその数を表わ
して登録する。例えば、零要素が並ぶ数をpiとすると、 pi＋１＝（2ⁿ−２）ａ＋ｂ a,bは整数０≦ａ０≦ｂ＜（2ⁿ−２）と表わせるときは、（ａ＋１）個のワードを使って表わ
す。すなわち、ａ個のワードのデータは（2ⁿ−２）と
し、最後の１ワードのデータはｂとする。

この行列演算装置は、上記述べたように、変換行列Ｗの
零要素が並ぶ数piと行末記号delimをインデックスとし
て、次のように演算処理を行なう。

入力ベクトルｘの一次変換として式（１）を計算をする
場合、第８図に示す計算アルゴリズムに従って計算す
る。

まず、ステップS₁に示すように、各ポインタ403,404,30
6,307の指示値をそれぞれip,wp,yp＝１、xp＝０とし、
出力バッフア303のデータYTyp（yp＝1,…,M）を０とす
る（初期化）。次に、インデックステーブル401のデー
タITipが行末記号delim（＝2ⁿ−１）であるかどうか判
別（S₂）して、行末であれば改行（S₃）する。行末でな
ければ、行方向向きにITip分だけ移動（S₅）して、ITip
が最大数（2ⁿ−２）であるかどうかを判別（S₆）する。
最大数であれば、インデックステーブル401の次のデー
タを調べにゆく（S₇）。最大数でなければ、積WTwp×XT
xpをYTypに加算（S₈）し、係数メモリ404の次のデータ
を出せるように指示値wpを１つ進めると共に、インデッ
クステーブル401の次のデータを調べにゆく（S₉）。そ
して、ステップS₂に戻って、再びITipが行末記号delim
であるかどうかを判別して、行末であれば改行（S₃）し
て、さらに、Ｎ行まで調べ終わったとき、この演算を終
了する。

入力ベクトルu^tの一次変換式（２）を計算する場合、上
記演算と同様の手順によって、第９図に示す計算アルゴ
リズムに従って計算する。

このように演算処理を行なうことによって、例えばＮ行
Ｍ列の変換行列Ｗの全要素（Ｎ×Ｍ個の実数）のうち非
零要素の占める割合がｋ％であるとき、この行列Ｗの要
素を記憶するための上記係数メモリ402の記憶量は、実
数にしてＮ×Ｍ×k/100個分となり、一方、上記インデ
ックステーブル401の記憶量は、整数にして約Ｎ×Ｍ×k
/100個分となる。したがって、非零要素の占める割合が
少ない（ｋが小さいとき）上記変換行列Ｗの要素の記憶
量を低減することができる。また、上記行列演算処理１
回につき乗算と加算を行なう回数はそれぞれＮ×Ｍ×k/
100回となって、ｋが小さいとき計算量を低減すること
ができる。

次に、この発明の基礎となる第２の行列演算装置を説明
する。

この行列演算装置は、第１の行列演算装置のインデック
ステーブル401に代えて、第４図に示すインデックステ
ーブル411を備えている。他の構成は第１の行列演算装
置と同一である。上記インデックステーブル411は次の
ようにして作成される。インデックステーブル401と同
様に、零要素の並びの数piに１を足した整数（pi＋１）
を登録する。ただし、行末記号delimを使用せず、零要
素が行末から次行の行頭へ続く場合は、行末の零要素の
並び数と次行の行頭の零要素の並び数とを足した数に１
を加えて登録する。例えば、第７図に示す変換行列W301
の１行目の行末と２行目の行頭の場合、整数（p₂＋p₃＋
１）を登録する。

上記入力ベクトルx,入力ベクトルu^tの一次変換式
（１），式（２）を計算する場合、それぞれ第10図、第
11図に示す計算アルゴリズムに従って行なう。なお、簡
単のため、各データ、指示値は第１の行列演算装置と同
一記号を使用している（後に述べる第３、第４の行列演
算装置において同様）。第１の行列演算装置に対して略
同一手順であるが、式（１）の計算の場合、行末を検出
するためにxpとＭとを比較して、xp＞Ｍならば行が変わ
ったと判断（S₂₅）して、ypをint（xp/M）だけ進める
（S₂₆）点が異なっている。式（２）の計算の場合、vp
を使ってこれを行なう。なお、int（＊）は括弧内の式
の値の整数部を示している。

次に、この発明を具現化した第３の行列演算装置を説明
する。

この行列演算装置は、第１の行列演算装置のインデック
ステーブル401に代えて、第５図に示すインデックステ
ーブル421を備えている。他の構成は第１の行列演算装
置と同一である。上記インデックステーブル421は、零
要素の並びの数piと別に非零要素の並びの数qiを登録す
る。すなわち、非零要素が並んでいる場合、第１の行列
演算装置，第２の行列演算装置と異なり、（qi−１）個
の整数１をそれぞれ別個に登録するのでなく、１つのデ
ータとして整数qiを登録する。そして、１ワード当たり
ｎビットのうち最上位ビットを、零要素の並びの数piで
あるか非零要素の並びの数qiであるかの区別に使用す
る。零要素または非零要素が行末から次行の行頭へ続く
ときは、それらの並びの数を足した整数（pi＋pi₊₁），
（qi＋qi₊₁）を登録する。このようにした場合、第１の
行列演算装置，第２の行列演算装置に比して、インデッ
クステーブルのデータ量を少なくすることができる。

上記入力ベクトルｘ、入力ベクトルu^tの一次変換として
式（１），（２）を計算する場合、それぞれ第12図，第
13図に示す計算アルゴリズムに従って演算処理を行な
う。第１の行列演算装置および第２の行列演算装置に対
して略同一手順であるが、ITipが零要素または非零要素
のいずれを示しているかを判断（S₅₃,S₇₄）して、零要
素を示しているときは、その数だけxpまたはvpをスキッ
プする点が異なっている（S₅₄,S₇₅）。非零要素を示し
ているときは、その数だけ入力XTxpと係数WTwpとの積和
を計算する（S₅₇乃至S₆₁,S₇₈乃至S₈₂）。ただし、第２
の行列演算装置と同様に、その途中で行末になったかど
うかを、xpまたはvpの値をＭの値と比較して判断する
（S₆₀,S₈₀）。

このように、インデックステーブル421の内容検出と、
第２のメモリ12の内容読み出しとを並行して進めること
によって、簡単に第２のメモリのアドレス指定を行うこ
とができる。この結果、この行列演算装置の制御を簡単
に行うことができる。

次に、この発明を具現化した第４の行列演算装置を説明
する。

この行列演算装置は、第１の行列演算装置のインデック
ステーブルに代えて、第６図に示すインデックステーブ
ル431を備えている。他の構成は第１の行列演算装置と
同一である。上記インデックステーブル431は、第３の
行列演算装置と同様に、零要素の並びの数piと別に非零
要素の並びの数qiを登録する。ただし、行末では零要素
または非零要素の並びの数のいずれかの最大値を行末記
号delimとして登録する。なお、行末が零要素または零
要素の並びで終わるときは、１または並びの数を登録せ
ず、上記行末記号delimを登録する。このようにした場
合、第１の行列演算装置，第２の行列演算装置に比し
て、インデックステーブルのデータ量を少なくすること
ができる。

上記入力ベクトルx,入力ベクトルu^tの一次変換式
（１），式（２）を計算する場合、それぞれ第14図，第
15図に示す計算アルゴリズムに従って演算処理を行な
う。第３の行列演算装置に対して、行末であるかどうか
行末記号delimを使用して判断（S₉₃,S₁₀₄）する点のみ
が異なっている。

このように、インデックステーブル431の内容検出と、
第２のメモリ12の内容読み出しとを並行して進めること
によって、簡単に第２のメモリのアドレス指定を行うこ
とができる。この結果、この行列演算装置の制御を簡単
に行うことができる。

なお、第１乃至第４の行列演算装置において、変換行列
Ｗの各行を左から右へスキャンしたが、当然ながら、列
方向にスキャンしても良い。

＜発明の効果＞以上より明らかなように、この発明の行列演算装置は、
２次元配列で表わされる行列の各要素について零要素か
非零要素かを特定するデータを格納する第１のメモリ
と、上記行列の非零要素の内容を表わすデータを格納す
る第２のメモリと、上記第１のメモリに格納されたデー
タを参照して、上記行列の要素が零であるか否かを判別
する判別手段と、上記判別手段によって零でないと判別
された行列の要素について、上記第２のメモリに格納さ
れたデータと入力ベクトルの要素とを乗算して、積和を
求める演算手段を備えているので、大規模なスパース行
列の演算処理を行なう場合、変換行列において非零要素
の占める割合がｋ％であるとき、メモリの記憶量と計算
量をｋ％に低減することができる。

しかも、上記第１のメモリは、上記行列内で、零である
要素が連続して並ぶ数を表わす整数と、零でない要素が
連続して並ぶ数を表す整数とを、上記行列内の各連続す
る並びの順に格納しているので、第２のメモリの内容を
読み出すときにそのアドレス指定を簡単に行うことがで
きる。すなわち、第１のメモリを例えばポインタによっ
て順にスキャンして、非零要素が並ぶ数を表す整数が検
出されたとき、この整数分だけ順に第２のメモリに格納
された非零要素の内容を表すデータを読み出す。このよ
うに、第１のメモリの内容検出と、第２のメモリの内容
読み出しとを並行して進めることによって、簡単に第２
のメモリのアドレス指定を行うことができる。この結
果、この行列演算装置の制御を簡単に行うことができ
る。

【図面の簡単な説明】

第１図はこの発明の行列演算装置の構成を示すブロック
図、第２図，第４図，第５図および第６図は上記行列演
算装置のインデックステーブルを示す図、第３図は上記
行列演算装置の係数メモリを示す図、第７図は上記行列
演算装置の入出力バッファ，ポインタと変換行列Ｗの要
素を示す図、第８図乃至第15図は上記行列演算装置の計
算アルゴリズムを示すフローチャート、第16図および第
17図は従来の行列演算装置による演算を模式的に示す図
である。１……CPU、２……ROM、11……第１のメモリ、12……第
２のメモリ、21……入力装置、22……出力装置、301…
…変換行列Ｗ、302,308……入力バッファ、303,305……
出力バッフア、401,411,421,431……インデックステー
ブル、402……係数メモリ、306,307,308,309,403,404…
…ポインタ。

Claims

【特許請求の範囲】

【請求項１】２次元配列で表わされる行列の各要素につ
いて零である要素か零でない要素かを特定するデータを
格納する第１のメモリと、上記行列の零でない要素の内容を表わすデータを格納す
る第２のメモリと、上記第１のメモリに格納されたデータを参照して、上記
行列の要素が零であるか否かを判別する判別手段と、上記判別手段によって零でないと判別された行列の要素
について、上記第２のメモリに格納されたデータと入力
ベクトルの要素とを乗算して、積和を求める演算手段を
備えた行列演算装置において、上記第１のメモリは、上記行列内で、零である要素が連
続して並ぶ数を表わす整数と、零でない要素が連続して
並ぶ数を表す整数とを、上記行列内の各連続する並びの
順に格納していることを特徴とする行列演算装置。