図面 (/)

技術 行列演算装置、行列演算方法および行列演算プログラム

出願人 富士通株式会社
発明者 荒川敬山崎雅文
出願日 2018年2月27日 (2年8ヶ月経過) 出願番号 2018-033029
公開日 2019年9月5日 (1年1ヶ月経過) 公開番号 2019-148969
状態 未査定
技術分野 複合演算
主要キーワード ダミー要素 一部要素 行列ベクトル積 圧縮列 Y座標 D形式 行列演算装置 合算結果
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2019年9月5日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

行列積演算並列処理化を効率的に行えるようにする。

解決手段

行列15に含まれる複数の第1の行それぞれについて値がゼロでない非ゼロ要素の数をカウントし、非ゼロ要素の数の最大値を判定する。各第1の行から非ゼロ要素の値と列識別子とのペアを抽出し、非ゼロ要素の数が最大値より少ない第1の行に対しては値がゼロであるダミーのペアを追加することで、各第1の行に対して共通する個数のペアを含む圧縮格納データ18を生成する。圧縮格納データ18に含まれる各ペアに対して、行列16から列識別子に対応する行識別子をもつ第2の行を抽出し、抽出した第2の行に対して当該ペアの値を乗算することで行ベクトルを生成する。各第1の行に対して共通する個数のスレッド割り当て、各第1の行についてスレッドを用いて行ベクトルを合算することで、行列15と行列16との行列積を示す行列17を生成する。

概要

背景

科学技術計算などのある種の計算分野では、ゼロ要素(値がゼロである要素)が多く非ゼロ要素(値がゼロでない要素)が少ない疎行列を扱うことがある。疎行列の内部表現形式として、全ての要素の値を列挙する通常の格納方法を用いると非効率であることから、圧縮行格納(CSR:Compressed Sparse Row)法や圧縮列格納(CSC:Compressed Sparse Column)法などの圧縮格納法を用いることがある。

SR法では、非ゼロ要素の値と当該非ゼロ要素の列番号との組を列挙した非ゼロ要素リストが生成される。非ゼロ要素リストは、疎行列の非ゼロ要素を行番号の小さい順に列挙したものであって、同じ行の中では列番号の小さい順に列挙したものである。すなわち、非ゼロ要素リストは、疎行列からゼロ要素を除去して非ゼロ要素を左詰めし、1番目の行の非ゼロ要素、2番目の行の非ゼロ要素、…と並べて一次元化したリストである。また、CSR法では、非ゼロ要素リストのみでは行の区切りが不明であるため、各行の最初の非ゼロ要素が非ゼロ要素リストの何番目に出現するかを表す行リストが生成される。この非ゼロ要素リストと行リストによって疎行列が表現される。CSC法はCSR法の行と列を入れ替えたものであり、非ゼロ要素リストと列リストが生成される。

疎行列を扱う計算分野では、疎行列と他の行列(密行列やベクトルなどであってもよい)との行列積をコンピュータに計算させることがある。このとき、コンピュータが保持する疎行列のデータは圧縮格納法によって表現されていることがある。

例えば、疎行列とベクトルの積の演算高速化する行列ベクトル積演算システムが提案されている。提案の行列ベクトル積演算システムは、CSR形式の疎行列が入力されると、疎行列のデータ構造をCSR形式からJAD(Jagged Diagonal)形式に変換し、JAD形式の疎行列とベクトルとの積を複数のプロセッサを用いて並列に計算する。JAD形式は、疎行列に含まれる複数の行を非ゼロ要素の多い順に並べ替え、行毎に非ゼロ要素を抽出して左詰めし、それら非ゼロ要素を列方向に辿って一次元化したデータ形式である。

また、例えば、CSR形式の疎行列とベクトルとの積を、CSR形式のままで複数のプロセッサを用いて並列に計算する行列演算方法が提案されている。また、例えば、疎行列のうち非ゼロ要素の数が閾値以上である列のデータをJAD形式で保持し、非ゼロ要素の数が閾値未満である列のデータをCSR形式で保持し、当該疎行列とベクトルとの積を計算する情報処理装置が提案されている。

概要

行列積演算並列処理化を効率的に行えるようにする。行列15に含まれる複数の第1の行それぞれについて値がゼロでない非ゼロ要素の数をカウントし、非ゼロ要素の数の最大値を判定する。各第1の行から非ゼロ要素の値と列識別子とのペアを抽出し、非ゼロ要素の数が最大値より少ない第1の行に対しては値がゼロであるダミーのペアを追加することで、各第1の行に対して共通する個数のペアを含む圧縮格納データ18を生成する。圧縮格納データ18に含まれる各ペアに対して、行列16から列識別子に対応する行識別子をもつ第2の行を抽出し、抽出した第2の行に対して当該ペアの値を乗算することで行ベクトルを生成する。各第1の行に対して共通する個数のスレッド割り当て、各第1の行についてスレッドを用いて行ベクトルを合算することで、行列15と行列16との行列積を示す行列17を生成する。

目的

本発明は、行列積演算の並列処理化を効率的に行えるようにする行列演算装置、行列演算方法および行列演算プログラムを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

行列演算プログラムを記憶する記憶部と、前記行列演算プログラムに基づいて複数のスレッド並列に実行可能な処理部と、を有し、前記行列演算プログラムを実行する前記処理部は、第1の行列に含まれる複数の第1の行それぞれについて値がゼロでない非ゼロ要素の数をカウントし、前記複数の第1の行の間で前記非ゼロ要素の数の最大値を判定し、前記複数の第1の行それぞれから非ゼロ要素の値と当該非ゼロ要素が位置する列を示す列識別子とのペアを抽出し、前記非ゼロ要素の数が前記最大値より少ない第1の行に対しては値がゼロであるダミーのペアを追加することで、前記複数の第1の行それぞれに対して共通する個数のペアを含む圧縮格納データを生成し、前記圧縮格納データに含まれるペアそれぞれに対して、第2の行列から当該ペアの列識別子に対応する行識別子をもつ第2の行を抽出し、当該抽出した第2の行に対して当該ペアの値を乗算することで、当該ペアに対応する行ベクトルを生成し、前記複数の第1の行それぞれに対して共通する個数のスレッドを割り当て、前記複数の第1の行それぞれについて前記共通する個数のスレッドを用いて行ベクトルを合算することで、前記第1の行列と前記第2の行列との行列積を示す第3の行列を生成する、行列演算装置

請求項2

前記ダミーのペアは、ゼロの値と所定の列識別子とのペアであり、前記行ベクトルの生成は、前記ダミーのペアに対しても実行される、請求項1記載の行列演算装置。

請求項3

前記圧縮格納データに含まれる第1の行毎のペアの個数は、前記最大値である、請求項1記載の行列演算装置。

請求項4

前記複数の第1の行それぞれに割り当てるスレッドの個数は、前記圧縮格納データに含まれる第1の行毎のペアの個数と前記第2の行列の列数とから決定される、請求項1記載の行列演算装置。

請求項5

前記複数の第1の行それぞれに対応して4つ以上の行ベクトルが生成された場合、前記行ベクトルの合算は、2つの行ベクトルの合算を木構造で繰り返すことで行う、請求項1記載の行列演算装置。

請求項6

行列演算プログラムを記憶する記憶部と、前記行列演算プログラムに基づいて複数のスレッドを並列に実行可能な処理部と、を有し、前記行列演算プログラムを実行する前記処理部は、第1の行列に含まれる複数の第1の列それぞれについて値がゼロでない非ゼロ要素の数をカウントし、前記複数の第1の列の間で前記非ゼロ要素の数の最大値を判定し、前記複数の第1の列それぞれから非ゼロ要素の値と当該非ゼロ要素が位置する行を示す行識別子とのペアを抽出し、前記非ゼロ要素の数が前記最大値より少ない第1の列に対しては値がゼロであるダミーのペアを追加することで、前記複数の第1の列それぞれに対して共通する個数のペアを含む圧縮格納データを生成し、前記圧縮格納データに含まれるペアそれぞれに対して、第2の行列から当該ペアの行識別子に対応する列識別子をもつ第2の列を抽出し、当該抽出した第2の列に対して当該ペアの値を乗算することで、当該ペアに対応する列ベクトルを生成し、前記複数の第1の列それぞれに対して共通する個数のスレッドを割り当て、前記複数の第1の列それぞれについて前記共通する個数のスレッドを用いて列ベクトルを合算することで、前記第2の行列と前記第1の行列との行列積を示す第3の行列を生成する、行列演算装置。

請求項7

コンピュータが実行する行列演算方法であって、第1の行列に含まれる複数の第1の行それぞれについて値がゼロでない非ゼロ要素の数をカウントし、前記複数の第1の行の間で前記非ゼロ要素の数の最大値を判定し、前記複数の第1の行それぞれから非ゼロ要素の値と当該非ゼロ要素が位置する列を示す列識別子とのペアを抽出し、前記非ゼロ要素の数が前記最大値より少ない第1の行に対しては値がゼロであるダミーのペアを追加することで、前記複数の第1の行それぞれに対して共通する個数のペアを含む圧縮格納データを生成し、前記圧縮格納データに含まれるペアそれぞれに対して、第2の行列から当該ペアの列識別子に対応する行識別子をもつ第2の行を抽出し、当該抽出した第2の行に対して当該ペアの値を乗算することで、当該ペアに対応する行ベクトルを生成し、前記複数の第1の行それぞれに対して共通する個数のスレッドを割り当て、前記複数の第1の行それぞれについて前記共通する個数のスレッドを用いて行ベクトルを合算することで、前記第1の行列と前記第2の行列との行列積を示す第3の行列を生成する、行列演算方法。

請求項8

コンピュータに、第1の行列に含まれる複数の第1の行それぞれについて値がゼロでない非ゼロ要素の数をカウントし、前記複数の第1の行の間で前記非ゼロ要素の数の最大値を判定し、前記複数の第1の行それぞれから非ゼロ要素の値と当該非ゼロ要素が位置する列を示す列識別子とのペアを抽出し、前記非ゼロ要素の数が前記最大値より少ない第1の行に対しては値がゼロであるダミーのペアを追加することで、前記複数の第1の行それぞれに対して共通する個数のペアを含む圧縮格納データを生成し、前記圧縮格納データに含まれるペアそれぞれに対して、第2の行列から当該ペアの列識別子に対応する行識別子をもつ第2の行を抽出し、当該抽出した第2の行に対して当該ペアの値を乗算することで、当該ペアに対応する行ベクトルを生成し、前記複数の第1の行それぞれに対して共通する個数のスレッドを割り当て、前記複数の第1の行それぞれについて前記共通する個数のスレッドを用いて行ベクトルを合算することで、前記第1の行列と前記第2の行列との行列積を示す第3の行列を生成する、処理を実行させる行列演算プログラム。

技術分野

0001

本発明は行列演算装置行列演算方法および行列演算プログラムに関する。

背景技術

0002

科学技術計算などのある種の計算分野では、ゼロ要素(値がゼロである要素)が多く非ゼロ要素(値がゼロでない要素)が少ない疎行列を扱うことがある。疎行列の内部表現形式として、全ての要素の値を列挙する通常の格納方法を用いると非効率であることから、圧縮行格納(CSR:Compressed Sparse Row)法や圧縮列格納(CSC:Compressed Sparse Column)法などの圧縮格納法を用いることがある。

0003

SR法では、非ゼロ要素の値と当該非ゼロ要素の列番号との組を列挙した非ゼロ要素リストが生成される。非ゼロ要素リストは、疎行列の非ゼロ要素を行番号の小さい順に列挙したものであって、同じ行の中では列番号の小さい順に列挙したものである。すなわち、非ゼロ要素リストは、疎行列からゼロ要素を除去して非ゼロ要素を左詰めし、1番目の行の非ゼロ要素、2番目の行の非ゼロ要素、…と並べて一次元化したリストである。また、CSR法では、非ゼロ要素リストのみでは行の区切りが不明であるため、各行の最初の非ゼロ要素が非ゼロ要素リストの何番目に出現するかを表す行リストが生成される。この非ゼロ要素リストと行リストによって疎行列が表現される。CSC法はCSR法の行と列を入れ替えたものであり、非ゼロ要素リストと列リストが生成される。

0004

疎行列を扱う計算分野では、疎行列と他の行列(密行列やベクトルなどであってもよい)との行列積をコンピュータに計算させることがある。このとき、コンピュータが保持する疎行列のデータは圧縮格納法によって表現されていることがある。

0005

例えば、疎行列とベクトルの積の演算高速化する行列ベクトル積演算システムが提案されている。提案の行列ベクトル積演算システムは、CSR形式の疎行列が入力されると、疎行列のデータ構造をCSR形式からJAD(Jagged Diagonal)形式に変換し、JAD形式の疎行列とベクトルとの積を複数のプロセッサを用いて並列に計算する。JAD形式は、疎行列に含まれる複数の行を非ゼロ要素の多い順に並べ替え、行毎に非ゼロ要素を抽出して左詰めし、それら非ゼロ要素を列方向に辿って一次元化したデータ形式である。

0006

また、例えば、CSR形式の疎行列とベクトルとの積を、CSR形式のままで複数のプロセッサを用いて並列に計算する行列演算方法が提案されている。また、例えば、疎行列のうち非ゼロ要素の数が閾値以上である列のデータをJAD形式で保持し、非ゼロ要素の数が閾値未満である列のデータをCSR形式で保持し、当該疎行列とベクトルとの積を計算する情報処理装置が提案されている。

先行技術

0007

特開2001−209631号公報
特開2008−181386号公報
国際公開第2017/154946号

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

0008

コンピュータが、従来の圧縮格納法によって表された行列Sと他の行列Dとの行列積を計算して行列Oを生成することを考える。例えば、コンピュータは、従来のCSR法によって表された行列Sを用いてS×D=Oを以下のように計算することが考えられる。

0009

行列Sのi行目には2つの非ゼロ要素があり、i行j1列の要素S[i,j1]とi行j2列の要素S[i,j2]が非ゼロ要素であるとする。コンピュータは、行列Dからj1行目の行ベクトルを抽出し、抽出した行ベクトルの各要素に対して要素S[i,j1]の値を乗算する。また、コンピュータは、行列Dからj2行目の行ベクトルを抽出し、抽出した行ベクトルの各要素に対して要素S[i,j2]の値を乗算する。この2つの行ベクトルを合算したものが行列Oのi行目に相当する。よって、コンピュータは、CSR形式の行列Sに含まれる非ゼロ要素リストのレコード毎に、行列Dから行ベクトルを抽出して当該抽出した行ベクトルの各要素に対して乗算を行い、行列Sの行毎にそれら行ベクトルを合算することで行列Oを生成することができる。

0010

また、例えば、コンピュータは、従来のCSC法によって表された行列Sを用いてD×S=Oを以下のように計算することも考えられる。
行列Sのj列目には2つの非ゼロ要素があり、i1行j列の要素S[i1,j]とi2行j列の要素S[i2,j]が非ゼロ要素であるとする。コンピュータは、行列Dからi1列目の列ベクトルを抽出し、抽出した列ベクトルの各要素に対して要素S[i1,j]の値を乗算する。また、コンピュータは、行列Dからi2列目の列ベクトルを抽出し、抽出した列ベクトルの各要素に対して要素S[i2,j]の値を乗算する。この2つの列ベクトルを合算したものが行列Oのj列目に相当する。よって、コンピュータは、CSC形式の行列Sに含まれる非ゼロ要素リストのレコード毎に、行列Dから列ベクトルを抽出して当該抽出した列ベクトルの各要素に対して乗算を行い、行列Sの列毎にそれら列ベクトルを合算することで行列Oを生成することができる。

0011

コンピュータは、行列Sと行列Dの行列積を、複数のスレッドを用いて並列処理化することも考えられる。しかし、従来の圧縮格納法によって表された行列Sをそのまま使用した場合、複数のベクトルの合算を並列処理化することが非効率になるという問題がある。

0012

例えば、行列Sの行毎の非ゼロ要素数が可変であるため、上記のS×D=Oの計算では合算すべき行ベクトルの数が行列Sの行によって異なり、合算する行ベクトルの範囲とスレッドとを対応付けるスレッド割り当ての制御が複雑になってしまう。また、例えば、行列Sの列毎の非ゼロ要素数が可変であるため、上記のD×S=Oの計算では合算すべき列ベクトルの数が行列Sの列によって異なり、合算する列ベクトルの範囲とスレッドとを対応付けるスレッド割り当ての制御が複雑になってしまう。

0013

1つの側面では、本発明は、行列積演算の並列処理化を効率的に行えるようにする行列演算装置、行列演算方法および行列演算プログラムを提供することを目的とする。

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

0014

1つの態様では、記憶部と処理部とを有する行列演算装置が提供される。記憶部は、行列演算プログラムを記憶する。処理部は、行列演算プログラムに基づいて複数のスレッドを並列に実行可能である。行列演算プログラムを実行する処理部は、第1の行列に含まれる複数の第1の行それぞれについて値がゼロでない非ゼロ要素の数をカウントし、複数の第1の行の間で非ゼロ要素の数の最大値を判定する。処理部は、複数の第1の行それぞれから非ゼロ要素の値と当該非ゼロ要素が位置する列を示す列識別子とのペアを抽出し、非ゼロ要素の数が最大値より少ない第1の行に対しては値がゼロであるダミーのペアを追加することで、複数の第1の行それぞれに対して共通する個数のペアを含む圧縮格納データを生成する。処理部は、圧縮格納データに含まれるペアそれぞれに対して、第2の行列から当該ペアの列識別子に対応する行識別子をもつ第2の行を抽出し、当該抽出した第2の行に対して当該ペアの値を乗算することで、当該ペアに対応する行ベクトルを生成する。処理部は、複数の第1の行それぞれに対して共通する個数のスレッドを割り当て、複数の第1の行それぞれについて共通する個数のスレッドを用いて行ベクトルを合算することで、第1の行列と第2の行列との行列積を示す第3の行列を生成する。

0015

また、1つの態様では、情報処理装置が実行する行列演算方法が提供される。また、1つの態様では、コンピュータに実行させる行列演算プログラムが提供される。

発明の効果

0016

1つの側面では、行列積演算の並列処理化を効率的に行える。

図面の簡単な説明

0017

行列演算装置の例を説明する図である。
情報処理装置のハードウェア例を示すブロック図である。
情報処理装置のソフトウェア構成例を示すブロック図である。
行列積演算の例を示す図である。
第1のCSRデータの例を示す図である。
第1のCSRデータを用いた行列積演算の例を示す図である。
第1の行列積演算における集計処理の例を示す図である。
第1の集計処理におけるスレッド割り当て例を示す図である。
第1のCSRデータ生成の手順例を示すフローチャートである。
第1の行列積演算の手順例を示すフローチャートである。
第1の行列積演算の手順例を示すフローチャート(続き)である。
第2のCSRデータの例を示す図である。
第2のCSRデータを用いた行列積演算の例を示す図である。
第2の行列積演算における集計処理の例を示す図である。
第2の集計処理におけるスレッド割り当て例を示す図である。
第2のCSRデータ生成の手順例を示すフローチャートである。
第2のCSRデータ生成の手順例を示すフローチャート(続き)である。
第2の行列積演算の手順例を示すフローチャートである。
第2の行列積演算の手順例を示すフローチャート(続き)である。

実施例

0018

以下、本実施の形態を図面を参照して説明する。
[第1の実施の形態]
第1の実施の形態を説明する。

0019

図1は、行列演算装置の例を説明する図である。
第1の実施の形態の行列演算装置10は、2つの行列の行列積を計算するコンピュータである。行列演算装置10は、大規模な疎行列を扱う科学技術計算に用いられることがある。行列演算装置10は、クライアントコンピュータでもよいしサーバコンピュータでもよい。行列演算装置10は、記憶部11および処理部12を有する。

0020

記憶部11は、行列演算プログラム13を記憶する。行列演算プログラム13は、後述する行列積演算を処理部12に実行させるプログラムである。行列演算プログラム13は、ユーザが作成したユーザプログラムでもよいし、コンパイラリンカなどの変換ソフトウェアを用いてユーザプログラムから変換されたプログラムでもよいし、ユーザプログラムから呼び出されるライブラリプログラムでもよい。記憶部11は、RAM(Random Access Memory)などの揮発性半導体メモリでもよいし、HDD(Hard Disk Drive)やフラッシュメモリなどの不揮発性ストレージでもよい。

0021

処理部12は、記憶部11に記憶された行列演算プログラム13を実行する。処理部12は、複数のスレッドを並列に実行することができる複数の演算部を有する。複数の演算部は、プロセッサコアでもよいしALU(Arithmetic Logic Unit)などの比較的小さな演算回路でもよい。処理部12は、CPU(Central Processing Unit)でもよいし、GPU(Graphics Processing Unit)、GPGPU(General Purpose Computing on GPU)やDSP(Digital Signal Processor)でもよい。処理部12は、数千個から数万個の多数の演算部を有してもよく、それら多数の演算部を用いて数千個から数万個の多数のスレッドを並列に実行可能であってもよい。処理部12は、行列演算プログラム13に基づいて、後述する行列積演算のためにスレッド14a,14bなどの複数のスレッドを起動して並列に実行する。

0022

行列演算プログラム13を実行する処理部12は、行列15(第1の行列、行列S)と行列16(第2の行列、行列D)から、行列15と行列16の行列積を示す行列17(第3の行列、行列O)を生成する。行列15は、行数列数の大きい大規模行列であって、値がゼロでない要素である非ゼロ要素が比較的少なく値がゼロの要素であるゼロ要素が比較的多い疎行列である。行列15は正方行列であってもよい。後述するように行列演算装置10は、行列15のデータを、圧縮格納法(圧縮行格納法または圧縮列格納法)を拡張した方法を用いて保持する。行列16は、行列15との行列積を計算可能な行列、すなわち、行数と列数の少なくとも一方が行列15と同じ行列である。行列16は、非ゼロ要素が比較的多くゼロ要素が比較的少ない密行列であってもよい。行列演算装置10は、行列16のデータを圧縮格納法を用いずに保持してもよい。

0023

以下では、行列15が圧縮行格納法を拡張した方法で表現され、S×D=Oという行列積演算を行う場合を説明する。よって以下の例では、行列15の列数と行列16の行数は同じである。後述するように、行列15が圧縮列格納法を拡張した方法で表現され、D×S=Oという行列積演算を行う場合には、「行」と「列」を入れ替えて解釈すればよい。また、D×S=(ST×DT)Tであるため、行列15と行列16をそれぞれ転置することで、S×D=Oと同様の方法でD×S=Oを計算することもできる。その場合、行列16の列数と行列15の行数は同じである。

0024

処理部12は、行列15に含まれる複数の行それぞれについて非ゼロ要素の数をカウントし、それら複数の行の間で非ゼロ要素数の最大値を判定する。図1には説明を簡単にするため、4行4列の行列15の例が記載されている。この行列15に含まれる要素のうち、S[0,2],S[1,0],S[1,2],S[2,1],S[2,3],S[3,0]が非ゼロ要素である。よって、行#0の非ゼロ要素数は1、行#1の非ゼロ要素数は2、行#2の非ゼロ要素数は2、行#3の非ゼロ要素数は1であり、行#0〜#3の非ゼロ要素数の最大値は2となる。なお、行番号および列番号はゼロから始まるものとする。

0025

次に、処理部12は、行列15を表す圧縮格納データ18を生成する。処理部12は、圧縮格納法を用いずに表現された二次元構造データから圧縮格納データ18を生成してもよいし、圧縮行格納法など通常の圧縮格納法を用いて表現されたデータを圧縮格納データ18に変換してもよい。前者の場合は処理部12は二次元構造データを受け取り、後者の場合は処理部12は通常の圧縮格納法のデータを受け取る。

0026

このとき、処理部12は、行列15の行それぞれから、非ゼロ要素の値と当該非ゼロ要素が位置する列を示す列識別子(例えば、列番号)とのペアを抽出する。処理部12は、抽出したペアを圧縮格納データ18に登録する。ただし、処理部12は、非ゼロ要素数が最大値より少ない行については値がゼロであるダミーのペアを追加することで、圧縮格納データ18において、行列15の行毎のペア数が共通する個数になるようにする。すなわち、圧縮格納データ18に登録された行毎のペア数を統一する。共通のペア数は、例えば、上記で判定した非ゼロ要素数の最大値とする。ダミーのペアに含まれる列識別子は任意の列識別子でよく、例えば、列#0を示す列識別子とする。なお、非ゼロ要素の値と列識別子とは単一のテーブルで管理されなくても、両者が対応付けられていればよく、非ゼロ要素の値と列識別子とが異なるテーブルまたは異なる配列によって管理されてもよい。

0027

上記で述べた図1の例の場合、(値,列識別子)のペアとして、行#0からは(1,列#2)が抽出される。また、行#0の非ゼロ要素数は最大値未満であるため、ここでは(0,列#0)というダミーのペアが追加されている。行#1からは(2,列#0)と(3,列#2)が抽出される。行#0の非ゼロ要素数は最大値であるため、このではダミーのペアは追加されていない。行#2からは(1,列#1)と(2,列#3)が抽出される。行#2の非ゼロ要素数は最大値であるため、ここではダミーのペアは追加されていない。行#3からは(3,列#0)が抽出される。行#3の非ゼロ要素数は最大値未満であるため、ここでは(0,列#0)というダミーのペアが追加されている。これにより、圧縮格納データ18では行毎のペア数が2個に統一される。

0028

次に、処理部12は、圧縮格納データ18に含まれる各ペアについて、行列16から、当該ペアに含まれる列識別子に対応する行識別子(例えば、列番号と同じ行番号)をもつ行を抽出する。処理部12は、抽出した行の各要素に対して当該ペアに含まれる値を乗算する。これにより、圧縮格納データ18に含まれるペア毎に行ベクトルが生成される。それら行ベクトルを列挙したものがベクトルデータ19である。処理部12は、複数のスレッドを用いてベクトルデータ19の生成を並列処理化してもよい。例えば、異なるペアに対応する行ベクトルの生成を異なるスレッドに実行させる。

0029

上記で述べた図1の例の場合、行列15の行#0について、行列16の行#2を抽出して各要素に1を乗じた行ベクトルと、行列16の行#0を抽出して各要素にゼロを乗じた行ベクトルが生成される。行列15の行#1について、行列16の行#0を抽出して各要素に2を乗じた行ベクトルと、行列16の行#2を抽出して各要素に3を乗じた行ベクトルが生成される。行列15の行#2について、行列16の行#1を抽出して各要素に1を乗じた行ベクトルと、行列16の行#3を抽出して各要素に2を乗じた行ベクトルが生成される。行列15の行#3について、行列16の行#0を抽出して各要素に3を乗じた行ベクトルと、行列16の行#0を抽出して各要素に0を乗じた行ベクトルが生成される。

0030

ダミーのペアに含まれる値はゼロであるため、ダミーのペアに対応する行ベクトルは全ての要素がゼロ要素であるゼロベクトルとなる。並列処理の制御を効率化するため、ダミーのペアに対しても他のペアと同様の手順で行ベクトルを生成することが好ましい。

0031

次に、処理部12は、行列15の各行に対して共通する個数のスレッドを割り当てる。すなわち、行列15の各行に割り当てるスレッドの数を統一する。共通のスレッド数は、例えば、圧縮格納データ18における共通のペア数と行列16の列数(すなわち、行ベクトルの列数)とから決定される。一例として、共通のペア数を2で割って小数点以下を切り捨てた整数に、行列16の列数を乗じた数を、共通のスレッド数とする。上記で述べた図1の例の場合、共通のペア数が2であり行列16の列数が2であるため、共通のスレッド数は2となり、行列15の各行に対して2個のスレッドが割り当てられる。

0032

次に、処理部12は、行列15の各行について、当該行に割り当てられたスレッドを用いて、当該行に対応する行ベクトルを合算することを並列処理化する。行列15の各行について、共通するペア数に相当する数の行ベクトルが生成されているため、これら行ベクトルの間で同じ列の要素の値同士を足し合わせることになる。4つ以上の行ベクトルの合算は、例えば、二分木のように2つの行ベクトルを合算することを階層的に繰り返すことによって実行し得る。ある2つの行ベクトルの合算と別の2つの行ベクトルの合算とは、異なるスレッドを用いて並列に実行し得る。また、ある2つの行ベクトルの中で、ある列の値の加算と別の列の値の加算も異なるスレッドを用いて並列に実行し得る。このとき、並列処理の制御を効率化するため、ダミーのペアから生成されたゼロベクトルについても他の行ベクトルと同様の手順で合算を行うことが好ましい。

0033

そして、処理部12は、行列15の各行に対応する行ベクトルの合算結果を、当該行列15の行に対応する行列17の行として使用する。これにより、行列15と行列16の行列積を示す行列17が生成される。行ベクトルの合算は、ベクトルデータ19の一部の行ベクトルを書き換えていくことで、ベクトルデータ19を記憶した記憶領域の中で行うことも可能であり、2つの行ベクトルを合算する毎に新たな記憶領域を使用しなくてもよい。ベクトルデータ19を記憶した記憶領域の中で合算を行った場合、最終的な合算結果に相当する一部の行ベクトルがベクトルデータ19から抽出されて行列17が生成される。ただし、ベクトルデータ19の記憶領域とは別に行列17の記憶領域を用意する代わりに、ベクトルデータ19の一部の行ベクトルのみが見えビューを定義してもよい。これにより、アプリケーションからはベクトルデータ19のサブセットが行列17に見える。

0034

上記で述べた図1の例の場合、行列15の行#0に対応する2つの行ベクトルが合算されて行列17の行#0が生成される。ただし、この2つの行ベクトルの一方はゼロベクトルである。行列15の行#1に対応する2つの行ベクトルが合算されて行列17の行#1が生成される。行列15の行#2に対応する2つの行ベクトルが合算されて行列17の行#2が生成される。行列15の行#3に対応する2つの行ベクトルが合算されて行列17の行#3が生成される。ただし、この2つの行ベクトルの一方はゼロベクトルである。このように、ベクトルデータ19には2つのゼロベクトルが存在するものの、行ベクトルを合算するスレッド毎の処理は均一にすることが可能である。

0035

上記ではS×D=Oという行列積演算を説明したが、D×S=Oという行列積演算も「行」と「列」を入れ替えることで可能となる。
すなわち、処理部12は、行列15の列毎に非ゼロ要素の数をカウントし、非ゼロ要素数の最大値を判定する。処理部12は、行列15の各列から非ゼロ要素の値と行識別子とのペアを抽出し、非ゼロ要素数が最大値より少ない列に対しては値がゼロのダミーのペアを追加することで、行列15の列の間で共通する個数のペアを含む圧縮格納データ18を生成する。処理部12は、圧縮格納データ18に含まれるペア毎に、当該ペアの行識別子に対応する列識別子をもつ行列16の列を抽出し、抽出した列の各要素に当該ペアの値を乗じることで列ベクトルを生成する。これら列ベクトルを列挙したものがベクトルデータ19となる。処理部12は、行列15の各列について、共通する個数のスレッドを割り当て、割り当てたスレッドを用いて当該列に対応する列ベクトルを合算することで、行列16と行列15の行列積を示す行列17を生成する。

0036

第1の実施の形態の行列演算装置10によれば、圧縮格納データ18に値がゼロのダミーのペアを追加することで、行列15の行毎のペア数(または、行列15の列毎のペア数)が統一される。そのため、行列15の行毎に生成される行ベクトルの数(または、行列15の列毎に生成される列ベクトルの数)が統一される。よって、スレッドと合算すべき行ベクトルの範囲(または、合算すべき列ベクトルの範囲)との対応付けが容易となり、行ベクトルを合算する合算処理(または、列ベクトルを合算する合算処理)の並列処理化の制御が簡潔となる。このため、行列積演算の並列処理化が効率的となる。

0037

[第2の実施の形態]
次に、第2の実施の形態を説明する。
図2は、情報処理装置のハードウェア例を示すブロック図である。

0038

第2の実施の形態の情報処理装置100は、大規模疎行列と密行列の行列積を計算する。情報処理装置100は、CPU101、GPGPU102、RAM103、HDD104、画像信号処理部105、入力信号処理部106、媒体リーダ107および通信インタフェース108を有する。これらのユニットバスに接続されている。なお、RAM103またはHDD104は、第1の実施の形態の記憶部11に対応する。GPGPU102は、第1の実施の形態の処理部12に対応する。

0039

CPU101は、プログラムの命令を実行する演算回路を含むプロセッサである。CPU101は、HDD104に記憶されたプログラムやデータの少なくとも一部をRAM103にロードし、プログラムを実行する。CPU101は、GPGPU102を制御し、行列積演算をGPGPU102に実行させることがある。

0040

GPGPU102は、画像処理に適した演算器をもつGPUを他の用途に転用したプロセッサである。GPGPU102は、並列にスレッドを実行可能な演算器102a,102b,102cを含む多数の演算器を有する。これらの演算器は、プロセッサコアでもよいしALUなどの比較的小さな単位回路でもよい。例えば、GPGPU102は、数千個から数万個の多数の演算器を有し、多数のスレッドを並列に実行することができる。

0041

RAM103は、CPU101やGPGPU102が実行するプログラムや演算に用いるデータを一時的に記憶する揮発性半導体メモリである。なお、情報処理装置100は、RAM以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。

0042

HDD104は、OS(Operating System)やアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性記憶装置である。なお、情報処理装置100は、フラッシュメモリやSSD(Solid State Drive)などの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。

0043

画像信号処理部105は、CPU101からの命令に従って、情報処理装置100に接続されたディスプレイ111に画像を出力する。ディスプレイ111としては、CRT(Cathode Ray Tube)ディスプレイ、液晶ディスプレイ(LCD:Liquid Crystal Display)、プラズマディスプレイ有機EL(OEL:Organic Electro-Luminescence)ディスプレイなど、任意の種類のディスプレイを用いることができる。

0044

入力信号処理部106は、情報処理装置100に接続された入力デバイス112から入力信号を取得し、CPU101に出力する。入力デバイス112としては、マウスタッチパネルタッチパッドトラックボールなどのポインティングデバイスキーボードリモートコントローラ、ボタンスイッチなどを用いることができる。また、情報処理装置100に複数の種類の入力デバイスが接続されていてもよい。

0045

媒体リーダ107は、記録媒体113に記録されたプログラムやデータを読み取る読み取り装置である。記録媒体113として、例えば、磁気ディスク光ディスク光磁気ディスク(MO:Magneto-Optical disk)、半導体メモリなどを使用できる。磁気ディスクには、フレキシブルディスクFD:Flexible Disk)やHDDが含まれる。光ディスクには、CD(Compact Disc)やDVD(Digital Versatile Disc)が含まれる。

0046

媒体リーダ107は、記録媒体113から読み取ったプログラムやデータを、RAM103やHDD104などの他の記録媒体にコピーする。読み取られたプログラムは、CPU101やGPGPU102によって実行され得る。なお、記録媒体113は可搬型記録媒体であってもよく、プログラムやデータの配布に用いられることがある。また、記録媒体113やHDD104を、コンピュータ読み取り可能な記録媒体と言うことがある。

0047

通信インタフェース108は、ネットワーク114に接続され、ネットワーク114を介して他の情報処理装置と通信を行うインタフェースである。通信インタフェース108は、スイッチなどの有線通信装置ケーブルで接続される有線通信インタフェースでもよいし、基地局と無線リンクで接続される無線通信インタフェースでもよい。

0048

図3は、情報処理装置のソフトウェア構成例を示すブロック図である。
情報処理装置100は、ユーザアプリケーション121、行列演算ライブラリ122、オペレーティングシステム127、スレッドプール128およびデータ記憶部129を有する。ユーザアプリケーション121、行列演算ライブラリ122およびオペレーティングシステム127は、プログラムを用いて実装される。スレッドプール128およびデータ記憶部129は、例えば、RAM103の記憶領域を用いて実装される。

0049

ユーザアプリケーション121は、ユーザが作成したユーザプログラムを用いて実装されるアプリケーションソフトウェアである。ユーザアプリケーション121は、疎行列と密行列を指定して行列演算ライブラリ122を呼び出すことで、疎行列と密行列の行列積を行列演算ライブラリ122に計算させて演算結果を取得する。

0050

行列演算ライブラリ122は、行列積を計算するプログラムを用いて実装されるライブラリソフトウェアである。行列演算ライブラリ122は、行列演算ライブラリ122を呼び出すユーザアプリケーション121とリンクされる。行列演算ライブラリ122は、ユーザアプリケーション121の生成時に静的にリンクされる静的リンクライブラリでもよいし、その実行時に動的にリンクされる動的リンクライブラリでもよい。行列演算ライブラリ122は、ユーザアプリケーション121に取り込まれて配布されてもよい。

0051

行列演算ライブラリ122は、GPGPU102に複数のスレッドを並列に実行させて行列積演算を高速化する。行列演算ライブラリ122は、疎行列生成部123、データ構造変換部124、密行列生成部125および行列積演算部126を有する。

0052

疎行列生成部123は、ユーザアプリケーション121からの入力に応じて、ゼロ要素も含めて疎行列の全ての要素を二次元配列として並べた二次元構造データの疎行列を生成する。データ構造変換部124は、疎行列生成部123が生成した二次元構造データを、圧縮行格納法の考え方に基づくCSRデータに変換する。後述するようにCSRデータとしては、通常の圧縮行格納法に従った第1のCSRデータと、圧縮行格納法を拡張した方法に従った第2のCSRデータを生成することが可能である。

0053

密行列生成部125は、ユーザアプリケーション121からの入力に応じて、密行列の全ての要素を二次元配列として並べた二次元構造データの密行列を生成する。行列積演算部126は、データ構造変換部124が生成したCSRデータと密行列生成部125が生成した密行列の二次元構造データを用いて、疎行列と密行列の行列積である出力行列を生成する。この出力行列は、出力行列の全ての要素を二次元配列として並べた二次元構造データである。後述するように、行列積演算の方法はCSRデータの形式によって異なる。行列積演算部126は、出力行列をユーザアプリケーション121に出力する。

0054

オペレーティングシステム127は、入力デバイス112を用いたユーザ入力受け付け、ユーザ入力に応じた制御を行う。情報処理装置100は、ユーザアプリケーション121を生成するために、コンパイラやリンカなどの開発用ソフトウェアを有してもよい。例えば、オペレーティングシステム127が受け付けたユーザ入力に応じて、コンパイラがソースコードコンパイルしてオブジェクトコードを生成し、リンカが当該オブジェクトコードと行列演算ライブラリ122とをリンクする。これにより、行列演算ライブラリ122とリンクされたユーザアプリケーション121が生成される。

0055

ただし、ユーザアプリケーション121に相当する実行可能プログラムは、他の情報処理装置によって生成されて情報処理装置100に入力されてもよい。また、第2の実施の形態では行列積演算のアルゴリズムが行列演算ライブラリ122に記述されているが、ユーザがソースコードの中に当該アルゴリズムを直接記述することも可能である。また、ソースコードに当該アルゴリズムが記述されていない場合であっても、コンパイラが自動的にオブジェクトコードの中に当該アルゴリズムを挿入することも可能である。

0056

スレッドプール128は、GPGPU102が有する複数の演算器を用いて並列に実行可能な複数のスレッドを予め起動しておいたプールである。複数のスレッドを予め起動しておくことで、行列積演算の途中におけるスレッド起動オーバヘッドを削減できる。これら複数のスレッドは行列演算ライブラリ122によって起動される。また、これら複数のスレッドは行列積演算部126によって行列積演算のために使用される。

0057

データ記憶部129は、疎行列生成部123が生成した疎行列の二次元構造データと、データ構造変換部124が生成したCSRデータと、密行列生成部125が生成した密行列の二次元構造データを記憶する。また、データ記憶部129は、行列積演算の途中で行列積演算部126が生成した中間データと、行列積演算部126が生成した出力行列の二次元構造データを記憶する。また、データ記憶部129は、スレッドプール128が保持するスレッドの割り当て状況を示す情報など各種の制御情報を記憶する。

0058

行列演算ライブラリ122は、疎行列のデータ構造として第1のCSRデータを用いる第1の行列積演算と、疎行列のデータ構造として第2のCSRデータを用いる第2の行列積演算のうち、何れか一方または両方を実行できる。行列演算ライブラリ122が両方を実行できる場合、ユーザが行列積演算の方法を選択できるようにしてもよい。以下では、まず第1の行列積演算を説明し、その後に第2の行列積演算を説明する。

0059

図4は、行列積演算の例を示す図である。
第2の実施の形態の行列積演算を説明するにあたり、図4に示す比較的コンパクトな疎行列131(疎行列S2D)および密行列132(密行列D)を使用する。

0060

疎行列131は、ゼロ要素が多い8行8列の行列である。疎行列131の行番号は上側の行から下側の行に向かって#0,#1,…,#7と付与されており、疎行列131の列番号は左側の列から右側の列に向かって#0,#1,…,#7と付与されている。

0061

疎行列131では、[0,5],[0,7],[1,1],[1,3],[3,4],[3,5],[3,6],[3,7],[4,1],[4,2],[4,5],[4,7],[5,4],[5,6],[6,2],[7,2],[7,3]が非ゼロ要素である。それ以外の疎行列131の要素はゼロ要素である。すなわち、疎行列131に含まれる64個の要素のうち17個のみが非ゼロ要素である。

0062

密行列132は、ゼロ要素が少ない8行3列の行列である。密行列132の行番号は上側の行から下側の行に向かって#0,#1,…,#7と付与されており、密行列132の列番号は左側の列から右側の列に向かって#0,#1,#2と付与されている。

0063

なお、第2の実施の形態では、疎行列S2Dを圧縮行格納法またはそれを拡張した方法によって表現してS2D×Dを計算するが、疎行列S2Dを圧縮列格納法またはそれを拡張した方法によって表現してD×S2Dを計算することも可能である。その場合には、以下で説明するアルゴリズムの「行」と「列」を入れ替えればよい。また、D×S2D=(S2DT×DT)Tであるため、疎行列S2Dと密行列Dをそれぞれ転置し、生成された出力行列を転置することによっても、D×S2Dを計算することができる。

0064

図5は、第1のCSRデータの例を示す図である。
第1の行列積演算では、疎行列131から非ゼロ要素テーブル141(非ゼロ要素テーブルSE)および行管理テーブル142(行管理テーブルSR)が生成される。非ゼロ要素テーブル141および行管理テーブル142は、データ記憶部129に記憶される。

0065

非ゼロ要素テーブル141は、組番号、値および列番号の項目を含む。組番号の項目には、ゼロから始まる整数の連番であって、疎行列131に含まれる非ゼロ要素を識別する数字が登録される。値の項目には、非ゼロ要素の値が登録される。列番号の項目には、非ゼロ要素が位置する列を示す列番号が登録される。非ゼロ要素テーブル141における複数の非ゼロ要素は、行番号が小さい順に並べられており、同じ行の中では列番号が小さい順に並べられている。なお、非ゼロ要素を特定できるように格納されていれば、非ゼロ要素テーブル141が明示的に組番号の項目を含んでいなくてもよい。

0066

行管理テーブル142は、非ゼロ要素テーブル141における行の区切りを示す。これは、非ゼロ要素テーブル141には非ゼロ要素が位置する列を特定する情報が含まれているものの行を特定する情報が含まれていないためである。行管理テーブル142は、行番号および組番号の項目を含む。行番号の項目には、疎行列131の行を示す行番号が登録される。組番号の項目には、非ゼロ要素テーブル141において各行の最初の非ゼロ要素を示す組番号が登録される。ただし、非ゼロ要素が1つも存在しない行に対しては、次の非ゼロ要素を示す組番号が対応付けられる。また、行管理テーブル142の末尾を明確にするため、行番号を「sentinel」とし、組番号を最大値より1だけ大きい数字としたレコードが行管理テーブル142に登録される。

0067

例えば、非ゼロ要素テーブル141では、疎行列131に含まれる17個の非ゼロ要素に対して組番号0〜16が付与される。行管理テーブル142では、行#0と当該行の最初の非ゼロ要素を示す組番号0が対応付けられる。以下同様に、行#1と当該行の最初の非ゼロ要素を示す組番号2が対応付けられる。行#2には非ゼロ要素が存在しないため、行#3と当該行の最初の非ゼロ要素を示す組番号4が対応付けられ、行#2と組番号4が対応付けられる。行#4と当該行の最初の非ゼロ要素を示す組番号8が対応付けられる。行#5と当該行の最初の非ゼロ要素を示す組番号12が対応付けられる。行#6と当該行の最初の非ゼロ要素を示す組番号14が対応付けられる。行#7と当該行の最初の非ゼロ要素を示す組番号15が対応付けられる。そして、「sentinel」と組番号17を対応付けたレコードが行管理テーブル142の末尾に登録される。

0068

図6は、第1のCSRデータを用いた行列積演算の例を示す図である。
疎行列131が非ゼロ要素テーブル141および行管理テーブル142として表現されている場合、行列積演算部126は以下のようにして行列積を計算することができる。行列積の計算は以下に説明するように、第1工程としての複製処理と、第2の工程としての乗算処理と、第3工程としての集計処理とを含む。

0069

複製処理では、行列積演算部126は、非ゼロ要素テーブル141から中間行列143を生成する。中間行列143は、データ記憶部129に記憶される。中間行列143は、行数が非ゼロ要素テーブル141のレコード数と同じ、すなわち、疎行列131の非ゼロ要素数と同じであり、列数が密行列132の列数と同じである二次元行列である。

0070

行列積演算部126は、非ゼロ要素テーブル141から列番号を抽出し、その列番号と同じ行番号をもつ行を密行列132から抽出して中間行列143に格納する。このとき、非ゼロ要素テーブル141の列番号の順序と中間行列143の行の順序とが対応しているようにする。例えば、行列積演算部126は、組番号0に対応する列#5について、密行列132から行#5を抽出して中間行列143の行#0に複製する。また、行列積演算部126は、組番号1に対応する列#7について、密行列132から行#7を抽出して中間行列143の行#1に複製する。このようにして、行列積演算部126は、組番号0〜16の列番号に基づいて17個の行が密行列132から抽出される。

0071

乗算処理では、行列積演算部126は、中間行列143から中間行列144を生成する。中間行列144は、中間行列143を更新した行列であり、中間行列143の記憶領域を上書きすれば中間行列143と異なる記憶領域を使用しなくてもよい。

0072

行列積演算部126は、非ゼロ要素テーブル141から値を抽出し、その値を中間行列143の対応する行の各要素に乗じる。例えば、行列積演算部126は、組番号0に対応する値「1」を、中間行列143の行#0の各要素に乗じる(各要素の値を1倍する)。また、行列積演算部126は、組番号1に対応する値「2」を、中間行列143の行#1の各要素に乗じる(各要素の値を2倍する)。このようにして、行列積演算部126は、組番号0〜16の値と中間行列143の行#0〜#16の値の間でそれぞれ乗算を行う。

0073

集計処理では、行列積演算部126は、疎行列131の行毎に中間行列の行をグルーピングし、グルーピングした行を合算することで出力行列145を生成する。出力行列145は、データ記憶部129に記憶される。出力行列145は、行数が疎行列131の行数と同じであり、列数が密行列132の列数と同じ二次元行列である。

0074

行列積演算部126は、疎行列131の行毎に、その疎行列131の行に存在する非ゼロ要素から生成された中間行列144の行範囲を特定し、特定した行範囲の値を列毎に合計する。合計値が、その疎行列131の行に対応する出力行列の行の値となる。例えば、行列積演算部126は、疎行列131の行#0に対応する中間行列144の行#0,#1を特定し、2つの行を合算して出力行列145の行#0を求める。また、行列積演算部126は、疎行列131の行#1に対応する中間行列144の行#2,#3を特定し、2つの行を合算して出力行列145の行#1を求める。疎行列131の行#2に対応する中間行列144の行は存在しないため、出力行列145の行#2の全ての要素はゼロとなる。

0075

また、行列積演算部126は、疎行列131の行#3に対応する中間行列144の行#4〜#7を特定し、4つの行を合算して出力行列145の行#3を求める。また、行列積演算部126は、疎行列131の行#4に対応する中間行列144の行#8〜#11を特定し、4つの行を合算して出力行列145の行#4を求める。また、行列積演算部126は、疎行列131の行#5に対応する中間行列144の行#12,#13を特定し、2つの行を合算して出力行列145の行#5を求める。疎行列131の行#6に対応する中間行列144の行は行#14のみであるため、これが出力行列145の行#6となる。また、行列積演算部126は、疎行列131の行#7に対応する中間行列144の行#15,#16を特定し、2つの行を合算して出力行列145の行#7を求める。

0076

ここで、中間行列143の生成は複数のスレッドを用いて容易に並列処理化できる。例えば、非ゼロ要素テーブル141の異なる非ゼロ要素に対して異なるスレッドを割り当てることで、中間行列143の異なる行の生成を並列に実行できる。非ゼロ要素それぞれに対して密行列132の列数に相当する数のスレッドを割り当て、中間行列143の1つの要素を1つのスレッドによって生成することも可能である。

0077

また、中間行列144の生成も複数のスレッドを用いて容易に並列処理化できる。例えば、非ゼロ要素テーブル141の異なる非ゼロ要素に対して異なるスレッドを割り当てることで、中間行列144の異なる行の乗算を並列に実行できる。非ゼロ要素それぞれに対して密行列132の列数に相当する数のスレッドを割り当て、中間行列144の1つの要素を1つのスレッドによって計算することも可能である。

0078

これに対し、中間行列144を集計して出力行列145を生成することについては幾つかの並列処理化の方法が考えられる。第1の方法は、中間行列144の1つの要素に対して1つのスレッドを割り当てる方法である。各スレッドは出力行列145の何れか1つの要素に対して加算を実行する。ただし、第1の方法では出力行列145の同じ要素に対して複数のスレッドがアクセスする可能性があり、排他制御のオーバヘッドが生じる。

0079

第2の方法は、出力行列145の1つの要素に対して1つのスレッドを割り当てる方法である。各スレッドは出力行列145の何れか1つの要素を独占的に計算するため、排他制御は不要である。ただし、第2の方法では疎行列131の中の非ゼロ要素が多い行については、並列度不足によって計算効率が低くなることがある。疎行列131の特定の行にA個(Aは4以上の整数)の非ゼロ要素があり、中間行列144のA個の行を合算することを考える。A個の行の合算は理論上、二分木に従って2つの行の合算を階層的に繰り返すことで、A/2個のスレッドを用いてlog2Aステップで実行することができる。これに対して第2の方法では、スレッド数の不足によりA−1ステップを要する。

0080

第3の方法は、出力行列145の1つの要素に対して可変個のスレッドを割り当てる方法である。例えば、出力行列145の1つの要素に対して、A/2個のスレッドなど、中間行列144の中の合算すべき行数に応じた数のスレッドを割り当てる。ただし、第3の方法では、疎行列131の行毎の非ゼロ要素数が可変であるため、行管理テーブル142の先頭から順に走査して非ゼロ要素数を確認し、中間行列144の担当行範囲とスレッドとの対応付けを決定することになる。よって、スレッド割り当て処理が複雑となり、スレッド割り当て自体のオーバヘッドが大きくなる。

0081

以下では、第3の方法を用いて集計処理を行うとする。
図7は、第1の行列積演算における集計処理の例を示す図である。
行列積演算部126は、中間行列144の一部要素を順次上書きすることで集計処理を進める。行列積演算部126は、中間行列144を更新して中間行列144aを生成し、中間行列144aを更に更新して中間行列144bを生成する。中間行列144a,144bの記憶領域としては、中間行列144の記憶領域をそのまま使用すればよい。

0082

行列積演算部126は、行管理テーブル142を参照し、疎行列131の各行から生成された中間行列144の行を特定する。例えば、疎行列131の行#0には中間行列144の行#0,#1が対応する。疎行列131の行#1には中間行列144の行#2,#3が対応する。疎行列131の行#2に対応する中間行列144の行は存在しない。疎行列131の行#3には中間行列144の行#4〜#7が対応する。疎行列131の行#4には中間行列144の行#8〜#11が対応する。疎行列131の行#5には中間行列144の行#12,#13が対応する。疎行列131の行#6には中間行列144の行#14が対応する。疎行列131の行#7には中間行列144の行#15,#16が対応する。

0083

行列積演算部126は、上記のように区分した行範囲それぞれの中で、2つの行を合算する処理を二分木形式で階層的に繰り返す。2つの行の合算は、列毎に、行番号の大きい方の行の値を行番号の小さい方の行に加算することで行う。最初は隣接する行同士が合算され、集計処理のステップが進むにつれて離れた行同士が合算される。集計処理の第Iステップ(Iは0以上の整数)では、2Iだけ離れた行同士が合算される。1行当たり非ゼロ要素数の最大値をMとすると、集計処理の終了までのステップ数はlog2Mである。

0084

例えば、中間行列144を中間行列144aに更新する第0ステップでは、中間行列144の行#1の値が行#0に加算される。行#3の値が行#2に加算される。行#5の値が行#4に加算され、行#7の値が行#6に加算される。行#9の値が行#8に加算され、行#11の値が行#10に加算される。行#13の値が行#12に加算される。行#14は加算相手がないためそのまま維持する。行#16の値が行#15に加算される。

0085

次に、中間行列144aを中間行列144bに更新する第1ステップでは、中間行列144aの行#0は加算相手がないためそのまま維持する。行#2は加算相手がないためそのまま維持する。行#6の値が行#4に加算される。行#10の値が行#8に加算される。行#12は加算相手がないためそのまま維持する。行#14は加算相手がないためそのまま維持する。行#15は加算相手がないためそのまま維持する。中間行列144aの上記以外の行は、第0ステップで合算済みであるため無視してよい。

0086

この例では1行当たり非ゼロ要素数の最大値は4であるため、第0ステップと第1ステップで集計処理は終了する。疎行列131の各行に対応する中間行列144bの行は高々1個に集約されている。中間行列144bにおける集約結果の行は、行管理テーブル142の組番号に相当する行である。疎行列131の行#0には中間行列144bの行#0が対応する。疎行列131の行#1には中間行列144bの行#2が対応する。疎行列131の行#2に対応する中間行列144bの行は存在しない。これは、疎行列131の行#2には要素が全てゼロである行ベクトルが対応することを意味する。疎行列131の行#3には中間行列144bの行#4が対応する。疎行列131の行#4には中間行列144bの行#8が対応する。疎行列131の行#5には中間行列144bの行#12が対応する。疎行列131の行#6には中間行列144bの行#14が対応する。疎行列131の行#7には中間行列144bの行#15が対応する。中間行列144bの上記以外の行は、第0ステップおよび第1ステップで合算済みであるため無視してよい。

0087

行列積演算部126は、中間行列144bの一部の行を抽出して出力行列145を生成する。中間行列144bの一部の行を複製して出力行列145を生成してもよいし、行の複製を行わずに中間行列144bの一部の行のみが見えるビューを生成してもよい。

0088

例えば、出力行列145の行#0は中間行列144bの行#0である。出力行列145の行#1は中間行列144bの行#2である。出力行列145の行#2は要素が全てゼロの行ベクトルである。出力行列145の行#3は中間行列144bの行#4である。出力行列145の行#4は中間行列144bの行#8である。出力行列145の行#5は中間行列144bの行#12である。出力行列145の行#6は中間行列144bの行#14である。出力行列145の行#7は中間行列144bの行#15である。

0089

行列積演算部126は、2つの値を加算する加算演算毎に1つのスレッドを割り当てる。上記の第0ステップでは中間行列144を中間行列144aに更新するにあたり、8行×3列=24個の加算演算が行われており、24個のスレッドが並列に実行される。また、上記の第1ステップでは中間行列144aを中間行列144bに更新するにあたり、2行×3列=6個の加算演算が行われており、6個のスレッドが並列に実行される。ただし、集約処理のステップが進むにつれて加算演算の数は減少するため、前のステップで使用されたスレッドのサブセットを次のステップで使用すればよい。上記の第1ステップでは、中間行列144aの行#4を計算したスレッドが中間行列144bの行#4を計算すればよく、中間行列144aの行#8を計算したスレッドが中間行列144bの行#8を計算すればよい。よって、スレッド割り当ては集約処理の開始時に決定される。

0090

図8は、第1の集計処理におけるスレッド割り当て例を示す図である。
スレッドテーブル146は、中間行列144から決定されるスレッド割り当てを示す。スレッドテーブル146は、データ記憶部129に記憶される。

0091

スレッドテーブル146は、行番号およびスレッド番号の項目を有する。行番号の項目には、非ゼロ要素が存在する疎行列131の行の行番号が登録される。スレッド番号の項目には、疎行列131の行に対して割り当てられたスレッドを識別するスレッド番号が二次元配列として列挙される。この二次元配列の行数は、非ゼロ要素数をAとするとA/2(小数点以下切り捨て)である。この二次元配列の列数は、密行列132の列数である。

0092

上記のように、中間行列144に対する集計処理の第0ステップでは24個の加算演算が行われるため、24個のスレッドが割り当てられる。具体的には、行#0に対してスレッド#0〜#2、行#1に対してスレッド#3〜#5、行#3に対してスレッド#6〜#11、行#4に対してスレッド#12〜#17、行#5に対してスレッド#18〜#20、行#7に対してスレッド#21〜#23が割り当てられる。

0093

例えば、スレッド#0は中間行列144の[0,0]に[1,0]の値を加算するものである。スレッド#1は[0,1]に[1,1]の値を加算するものである。スレッド#2は[0,2]に[1,2]の値を加算するものである。また、スレッド#6は[4,0]に[5,0]の値を加算するものである。スレッド#7は[4,1]に[5,1]の値を加算するものである。スレッド#8は[4,2]に[5,2]の値を加算するものである。また、スレッド#9は[6,0]に[7,0]の値を加算するものである。スレッド#10は[6,1]に[7,1]の値を加算するものである。スレッド#11は[6,2]に[7,2]の値を加算するものである。

0094

集計処理の第0ステップでは、これらのスレッドが全て並列に実行される。それより後のステップでは、これらのスレッドの一部が並列に実行される。上記のように、中間行列144に対する集計処理の第1ステップでは6個の加算演算が行われるため、スレッド#0〜#23のうちの6個のスレッドが並列に実行される。具体的には、スレッド#6〜#8,#12〜#14が実行され、それ以外のスレッドは実行されない。

0095

例えば、スレッド#6は中間行列144aの[4,0]に[6,0]の値を加算する。スレッド#7は[4,1]に[6,1]の値を加算する。スレッド#8は[4,2]に[6,2]の値を加算する。また、スレッド#12は[8,0]に[10,0]の値を加算する。スレッド#13は[8,1]に[10,1]の値を加算する。スレッド#14は[8,2]に[10,2]の値を加算する。これにより集計処理が終了する。

0096

次に、第1のCSRデータに関する処理手順を説明する。
図9は、第1のCSRデータ生成の手順例を示すフローチャートである。
第1のCSRデータ生成は、ユーザアプリケーション121からの入力に応じて疎行列生成部123が二次元構造データの疎行列131を生成した後に行われる。

0097

(S10)データ構造変換部124は、組番号N=0に初期化する。
(S11)データ構造変換部124は、疎行列131(疎行列S2D)の行番号を小さい方から1つ選択する(行番号row)。

0098

(S12)データ構造変換部124は、行管理テーブル142(行管理テーブルSR)の末尾に、行番号rowと組番号Nを含むレコード{row,N}を追加する。
(S13)データ構造変換部124は、行番号rowについて、疎行列131の列番号を小さい方から1つ選択する(列番号col)。

0099

(S14)データ構造変換部124は、疎行列131からrow行col列の値S2D[row][col](値val)を抽出し、val=0であるか判断する。val=0である場合、すなわち、S2D[row][col]がゼロ要素である場合、ステップS17に処理が進む。val=0でない場合、すなわち、S2D[row][col]が非ゼロ要素である場合、ステップS15に処理が進む。

0100

(S15)データ構造変換部124は、非ゼロ要素テーブル141(非ゼロ要素テーブルSE)の末尾に、組番号Nと値valと列番号colを含むレコード{N,val,col}を追加する。

0101

(S16)データ構造変換部124は、組番号Nを1だけ大きくする。
(S17)データ構造変換部124は、ステップS13で、行番号rowについて全ての列番号colを選択したか判断する。全ての列番号colを選択した場合はステップS18に処理が進み、未選択の列番号colがある場合はステップS13に処理が進む。

0102

(S18)データ構造変換部124は、ステップS11で、全ての行番号rowを選択したか判断する。全ての行番号rowを選択した場合はステップS19に処理が進み、未選択の行番号rowがある場合はステップS11に処理が進む。

0103

(S19)データ構造変換部124は、行管理テーブル142の末尾に、「sentinel」と組番号Nを含むレコード{sentinel,N}を追加する。
図10は、第1の行列積演算の手順例を示すフローチャートである。

0104

第1の行列積演算は、データ構造変換部124が第1のCSRデータを生成し、密行列生成部125が二次元構造データの密行列132を生成した後に行われる。
(S20)行列積演算部126は、非ゼロ要素テーブル141から組番号を1つ選択し(組番号N)、組番号Nに対応付けられた列番号SE[N].colを選択する。

0105

(S21)行列積演算部126は、密行列132(密行列D)のcol行目をコピーし、中間行列143(中間行列T)のN行目に格納する。
(S22)行列積演算部126は、ステップS20で、非ゼロ要素テーブル141の全ての組番号Nを選択したか判断する。全ての組番号Nを選択した場合はステップS23に処理が進み、未選択の組番号Nがある場合はステップS20に処理が進む。なお、ステップS20,S21の処理は複数のスレッドを用いて並列処理化することができる。

0106

(S23)行列積演算部126は、中間行列143から行番号と列番号を1つずつ選択し(行番号Nと列番号col)、N行col列の要素T[N][col]を選択する。
(S24)行列積演算部126は、非ゼロ要素テーブル141から組番号Nに対応付けられた値SE[N].valを選択する。行列積演算部126は、ステップS23で選択したT[N][col]にSE[N].valを乗じる。

0107

(S25)行列積演算部126は、ステップS23で、中間行列143の全ての要素を選択したか判断する。全ての要素を選択した場合はステップS26に処理が進み、未選択の要素がある場合はステップS23に処理が進む。なお、ステップS23,S24の処理は複数のスレッドを用いて並列処理化することができる。

0108

(S26)行列積演算部126は、最大値M=0に初期化する。
(S27)行列積演算部126は、行管理テーブル142の行番号を小さい方から1つ選択する(行番号row)。

0109

(S28)行列積演算部126は、行管理テーブル142から行番号rowに対応する組番号SR[row]と行番号row+1に対応する組番号SR[row+1]を検索する。行列積演算部126は、組数range=SR[row+1]−SR[row]を算出する。また、行列積演算部126は、現在の最大値Mと組数rangeの何れか大きい方を最大値Mとする(M=max(M,range))。

0110

(S29)行列積演算部126は、スレッドプール128からfloor(range/2)×cols個のスレッドを取得する。floorは床関数であり、正数に対しては小数点以下切り捨てを表す。colsは、中間行列143を更新することで得られた中間行列144(中間行列T)の列数を表す。行列積演算部126は、スレッドテーブル146(スレッドテーブルH)の行番号rowに対応する二次元配列H[row][:][:]に、取得したスレッドのスレッド番号を埋めていく。二次元配列H[row][:][:]の行数はfloor(range/2)であり、列数はcolsである。

0111

(S30)行列積演算部126は、ステップS27で、行管理テーブル142の全ての行番号rowを選択したか判断する。全ての行番号rowを選択した場合はステップS31に処理が進み、未選択の行番号rowがある場合はステップS27に処理が進む。

0112

図11は、第1の行列積演算の手順例を示すフローチャート(続き)である。
(S31)行列積演算部126は、イテレーション数I=0に初期化する。
(S32)行列積演算部126は、スレッドテーブル146からスレッド番号を1つ選択する(H[row][m][col])。スレッド番号の位置は、行番号rowと二次元配列内の行インデックスmと二次元配列内の列番号colによって特定される。選択されたスレッド番号が示すスレッドによってステップS33〜S35が実行される。

0113

(S33)行列積演算部126は、行管理テーブル142から行番号rowに対応する組番号SR[row]と行番号row+1に対応する組番号SR[row+1]を検索する。行列積演算部126は、SR[row+1]−SR[row]>2Iであるか、すなわち、行番号rowに対応する組数が2Iを超えるか判断する。上記条件を満たす場合はステップS34に処理が進み、上記条件を満たさない場合はステップS36に処理が進む。

0114

(S34)行列積演算部126は、行インデックスmを2Iで割った余り剰余)がゼロであるか、すなわち、m%2I=0であるか判断する。上記条件を満たす場合はステップS35に処理が進み、上記条件を満たさない場合はステップS36に処理が進む。

0115

(S35)行列積演算部126は、中間行列144から要素T[SR[row]+2I×2m][col]と要素T[SR[row]+2I×(2m+1)][col]を選択し、後者の値を前者に加算することで中間行列144を更新する。

0116

(S36)行列積演算部126は、ステップS32で、スレッドテーブル146の全てのスレッド番号を選択したか判断する。全てのスレッド番号を選択した場合はステップS37に処理が進み、未選択のスレッド番号がある場合はステップS32に処理が進む。なお、ステップS33〜S35の処理は並列処理化することができる。

0117

(S37)行列積演算部126は、イテレーション数Iを1だけ大きくする。
(S38)行列積演算部126は、I<ceil(log2M)を満たすか判断する。ceilは天井関数であり、正数に対しては小数点以下切り上げを表す。MはステップS28によって算出された非ゼロ要素数の最大値である。上記条件を満たす場合はステップS32に処理が進み、上記条件を満たさない場合はステップS39に処理が進む。

0118

(S39)行列積演算部126は、出力行列145(出力行列O)から行番号と列番号を選択する(行番号rowと列番号col)。行列積演算部126は、行管理テーブル142から行番号rowに対応する組番号SR[row]を検索し、中間行列144からT[SR[row]][col]を抽出する。行列積演算部126は、T[SR[row]][col]の値をO[row][col]の値として用いる。行列積演算部126は、各行と各列についてこれを繰り返すことで出力行列145を生成する。

0119

以上、第1の行列積演算について説明した。第1の行列積演算では、中間行列144に対する集計処理の並列処理化が複雑になり、多数のスレッドを並列に実行可能なGPGPU102の演算能力が十分に活用されないおそれがある。これに対し、行列演算ライブラリ122は、圧縮行格納法を拡張した方法に基づく第2の行列積演算を実行することもできる。次に、第2の行列積演算について説明する。

0120

図12は、第2のCSRデータの例を示す図である。
第2の行列積演算では、第1のCSRデータに代えて、疎行列131から値配列151(値配列SV)および列番号配列152(列番号配列SC)が生成される。値配列151および列番号配列152は、データ記憶部129に記憶される。

0121

値配列151は、疎行列131の非ゼロ要素の値を含む二次元配列である。列番号配列152は、疎行列131の非ゼロ要素が位置する列の列番号を含む二次元配列である。値配列151の行数と列番号配列152の行数は同じであり、値配列151の列数と列番号配列152の列数は同じである。同じ位置にある値配列151の要素と列番号配列152の要素とは対応関係にある。値配列151および列番号配列152の行数は、疎行列131の行数である。値配列151および列番号配列152の列数は、疎行列131の各行の非ゼロ要素数のうちの最大値(前述の最大値M)である。

0122

値配列151では、疎行列131の各行の非ゼロ要素の値が左詰めで格納される。非ゼロ要素数が最大値未満の行については値がゼロであるダミー要素を挿入することで、値配列151の1行当り要素数固定値に統一している。図4の疎行列131の場合、非ゼロ要素数の最大値は4であるため、値配列151は8行4列の二次元配列になる。

0123

疎行列131の行#0は非ゼロ要素数が2であるため、値配列151の列#0,#1に非ゼロ要素の値が登録され、列#2,#3にゼロが登録される。行#1は非ゼロ要素数が2であるため、列#0,#1に非ゼロ要素の値が登録され、列#2,#3にゼロが登録される。行#2は非ゼロ要素数が0であるため、列#0〜#3にゼロが登録される。行#3は非ゼロ要素数が4であるため、列#0〜#3に非ゼロ要素の値が登録される。行#4は非ゼロ要素数が4であるため、列#0〜#3に非ゼロ要素の値が登録される。行#5は非ゼロ要素数が2であるため、列#0,#1に非ゼロ要素の値が登録され、列#2,#3にゼロが登録される。行#6は非ゼロ要素数が1であるため、列#0に非ゼロ要素の値が登録され、列#1〜#3にゼロが登録される。行#7は非ゼロ要素数が2であるため、列#0,#1に非ゼロ要素の値が登録され、列#2,#3にゼロが登録される。

0124

列番号配列152では、値配列151に非ゼロ要素の値が登録されている位置には、当該非ゼロ要素が存在する列の列番号が登録される。一方、値配列151にゼロが登録されている位置には、値配列151と同様にダミー要素が登録される。これにより、列番号配列152の1行当り要素数を固定値に統一している。列番号配列152のダミー要素は、ゼロなどの所定の列番号をもつ。ただし、ダミー要素の列番号は疎行列131に実在する列の列番号であればよく、任意の列番号でもよい。以下の説明では、ダミーの列番号の例としてゼロを用いている。図4の疎行列131の場合、値配列151と同様に列番号配列152は8行4列の二次元配列になる。

0125

なお、第2の実施の形態では値配列151を二次元配列としたが、行番号の小さい順に非ゼロ要素およびダミー要素を並べた一次元配列とすることも可能である。同様に、列番号配列152を一次元配列とすることも可能である。また、第2の実施の形態では値配列151と列番号配列152を分離しているが、両者を単一のテーブルに統合してもよい。

0126

図13は、第2のCSRデータを用いた行列積演算の例を示す図である。
疎行列131が値配列151および列番号配列152として表現されている場合、行列積演算部126は以下のようにして行列積を計算することができる。行列積の計算は第1のCSRデータを用いた第1の行列積演算と同様に、第1工程としての複製処理と、第2の工程としての乗算処理と、第3工程としての集計処理とを含む。

0127

複製処理では、行列積演算部126は、列番号配列152から中間テンソル153を生成する。中間テンソル153は、第1次元座標X座標)と第2次元座標(Y座標)と第3次元座標(Z座標)により要素が特定される三次元配列である。中間テンソル153はデータ記憶部129に記憶される。X座標数は列番号配列152の行数と同じ、すなわち、疎行列131の行数と同じである。Y座標数は列番号配列152の列数と同じ、すなわち、非ゼロ要素数の最大値と同じである。Z座標数は密行列132の列数と同じである。

0128

行列積演算部126は、列番号配列152から列番号を抽出し、その列番号と同じ行番号をもつ行を密行列132から抽出して中間テンソル153に格納する。このとき、列番号配列152の行と中間テンソル153のX座標が対応し、列番号配列152の列と中間テンソル153のY座標が対応するようにする。また、列番号配列152に含まれるダミーの列番号に対しても、他の列番号と同様の処理が行われる。

0129

例えば、中間テンソル153にはX座標とY座標の組が8×4=32通り存在する。このうち17通りについては、列番号配列152に含まれるダミーでない列番号に従って密行列132の何れかの行の複製が格納される。一方、残りの15通りについては、列番号配列152に含まれるダミーの列番号に従って密行列132の特定の行の複製が格納される。第2の実施の形態ではダミーの列番号はゼロであるため、非ゼロ要素が存在しない位置には密行列132の行#0が格納されることになる。

0130

乗算処理では、行列積演算部126は、中間テンソル153から中間テンソル154を生成する。中間テンソル154は、中間テンソル153を更新したものであり、中間テンソル153の記憶領域を上書きすることで別個の記憶領域を使用しなくてもよい。

0131

行列積演算部126は、値配列151から値を抽出し、その値を中間テンソル153の対応する要素に乗じる。値配列151に含まれるダミー要素に対しても、非ゼロ要素と同様の処理が行われる。例えば、行列積演算部126は、値配列151の0行0列に対応する値「1」を、中間テンソル153のX=0,Y=0,Z=0〜2の各要素に乗じる(各要素の値を1倍する)。また、行列積演算部126は、値配列151の0行1列に対応する値「2」を、中間テンソル153のX=0,Y=1,Z=0〜2の各要素に乗じる(各要素の値を2倍する)。中間テンソル153に存在する32通りのX座標とY座標の組のうち17通りについては、非ゼロ要素の値を乗じることになる。一方、残りの15通りについては、ダミー要素の値であるゼロを乗じることになる。

0132

集計処理では、行列積演算部126は、中間テンソル154の要素をX座標とZ座標の組毎に合計することで出力行列155を生成する。これは、中間テンソル154のX座標毎に固定数の行ベクトルを合算することを意味する。出力行列155は、第1の行列積演算で生成される出力行列155と同じであり、データ記憶部129に記憶される。出力行列155は、行数が疎行列131の行数と同じであり、列数が密行列132の列数と同じ二次元行列である。出力行列155の行は中間テンソル154のX座標に対応し、出力行列155の列は中間テンソル154のZ座標に対応する。値配列151のダミー要素から生成された中間テンソル154の要素に対しても、他の要素と同様の処理が行われる。

0133

例えば、中間テンソル154のX=0,Y=0〜3の4つの行ベクトルを合算して出力行列155の行#0になる。中間テンソル154のX=1,Y=0〜3の4つの行ベクトルを合算して出力行列155の行#1になる。中間テンソル154のX=2,Y=0〜3の4つの行ベクトルを合算して出力行列155の行#2になる。中間テンソル154のX=3,Y=0〜3の4つの行ベクトルを合算して出力行列155の行#3になる。

0134

また、中間テンソル154のX=4,Y=0〜3の4つの行ベクトルを合算して出力行列155の行#4になる。中間テンソル154のX=5,Y=0〜3の4つの行ベクトルを合算して出力行列155の行#5になる。中間テンソル154のX=6,Y=0〜3の4つの行ベクトルを合算して出力行列155の行#6になる。中間テンソル154のX=7,Y=0〜3の4つの行ベクトルを合算して出力行列155の行#7になる。このように、第1の行列積演算と異なり第2の行列積演算では、出力行列155の1行当りに合算する中間テンソル154の行ベクトルの数が固定になる。

0135

ここで、中間テンソル153の生成は複数のスレッドを用いて容易に並列処理化できる。例えば、列番号配列152の異なる要素に対して異なるスレッドを割り当てることで、中間テンソル153の異なるX座標とY座標の組に対する複製処理を並列に実行できる。また、中間テンソル154の生成も複数のスレッドを用いて容易に並列処理化できる。例えば、値配列151の異なる要素に対して異なるスレッドを割り当てることで、中間テンソル154の異なるX座標とY座標の組に対する乗算処理を並列に実行できる。また、出力行列155の生成も複数のスレッドを用いて並列処理化できる。

0136

図14は、第2の行列積演算における集計処理の例を示す図である。
行列積演算部126は、中間テンソル154の一部要素を順次上書きすることで集計処理を進める。行列積演算部126は、中間テンソル154を更新して中間テンソル154aを生成し、中間テンソル154aを更に更新して中間テンソル154bを生成する。中間テンソル154a,154bのために別途記憶領域を用意しなくてもよい。

0137

行列積演算部126は、中間テンソル154の各X座標の中で、Y座標が異なる2つの行ベクトルの合算を二分木形式で階層的に繰り返す。2つの行ベクトルの合算は、Z座標毎に、Y座標が大きい方の要素の値をY座標が小さい方の要素に加算することで行う。最初はY座標が1だけ離れた行ベクトル同士が合算され、集計処理のステップが進むにつれてY座標が離れた行ベクトル同士が合算される。集計処理の第Iステップ(Iは0以上の整数)では、Y座標が2Iだけ離れた行ベクトル同士が合算される。中間テンソル154のY座標数をMとすると、集計処理の終了までのステップ数はlog2Mである。

0138

例えば、中間テンソル154を中間テンソル154aに更新する第0ステップでは、各X座標について、Y=1,Z=0の値がY=0,Z=0に加算され、Y=1,Z=1の値がY=0,Z=1に加算され、Y=1,Z=2の値がY=0,Z=2に加算される。また、各X座標について、Y=3,Z=0の値がY=2,Z=0に加算され、Y=3,Z=1の値がY=2,Z=1に加算され、Y=3,Z=2の値がY=2,Z=2に加算される。

0139

次に、中間テンソル154aを中間テンソル154bに更新する第1ステップでは、各X座標について、Y=2,Z=0の値がY=0,Z=0に加算され、Y=2,Z=1の値がY=0,Z=1に加算され、Y=2,Z=2の値がY=0,Z=2に加算される。上記以外の要素は、第0ステップで合算済みであるため無視してよい。

0140

この例では中間テンソル154のY座標数が4であるため、第0ステップと第1ステップで集計処理は終了する。集約処理の結果は、中間テンソル154bのY=0に位置する行ベクトルである。行列積演算部126は、中間テンソル154bからY=0の行ベクトルを抽出して出力行列155を生成する。中間テンソル154bの一部の行ベクトルを複製して出力行列155を生成してもよいし、行ベクトルの複製を行わずに中間テンソル154bの一部の行ベクトルのみが見えるビューを生成してもよい。

0141

例えば、出力行列155の行#0は中間テンソル154bのX=0,Y=0である。出力行列155の行#1は中間テンソル154bのX=1,Y=0である。出力行列155の行#2は中間テンソル154bのX=2,Y=0である。出力行列155の行#3は中間テンソル154bのX=3,Y=0である。出力行列155の行#4は中間テンソル154bのX=4,Y=0である。出力行列155の行#5は中間テンソル154bのX=5,Y=0である。出力行列155の行#6は中間テンソル154bのX=6,Y=0である。出力行列155の行#7は中間テンソル154bのX=7,Y=0である。

0142

行列積演算部126は、2つの値を加算する加算演算毎に1つのスレッドを割り当てる。上記の第0ステップでは8×2×3=48個の加算演算が行われており、48個のスレッドが並列に実行される。また、上記の第1ステップでは8×1×3=24個の加算演算が行われており、24個のスレッドが並列に実行される。ただし、集約処理が進むにつれて加算演算の数は減少するため、前のステップで使用されたスレッドのサブセットを次のステップで使用すればよい。上記の第1ステップでは、中間テンソル154aのX=0,Y=0,Z=0を計算したスレッドが中間テンソル154bのX=0,Y=0,Z=0を計算すればよい。よって、スレッド割り当ては集約処理の開始時に決定される。

0143

図15は、第2の集計処理におけるスレッド割り当て例を示す図である。
スレッド配列156は、中間テンソル154から決定されるスレッド割り当てを示す。スレッド配列156は、データ記憶部129に記憶される。スレッド配列156は、第1次元座標(X座標)と第2次元座標(Y座標)と第3次元座標(Z座標)により要素が特定される三次元配列である。スレッド配列156のX座標数は、中間テンソル154のX座標数と同じである。スレッド配列156のY座標数は、中間テンソル154のY座標数をMとするとM/2(小数点以下切り捨て)である。スレッド配列156のZ座標数は、中間テンソル154のZ座標数と同じである。

0144

スレッド配列156には、スレッドを識別するスレッド番号が登録される。中間テンソル154の各X座標に対して固定数のスレッドが割り当てられる。上記のように、中間テンソル154に対する集計処理の第0ステップでは48個の加算演算が行われるため、48個のスレッドが割り当てられる。例えば、X=0に対してスレッド#0〜#5、X=1に対してスレッド#6〜#11、X=2に対してスレッド#12〜#17、X=3に対してスレッド#18〜#23が割り当てられる。また、X=4に対してスレッド#24〜#29、X=5に対してスレッド#30〜#35、X=6に対してスレッド#36〜#41、X=7に対してスレッド#42〜#47が割り当てられる。

0145

スレッド#0は、中間テンソル154の[X,Y,Z]=[0,0,0]に[0,1,0]の値を加算するものである。スレッド#1は、[0,0,1]に[0,1,1]の値を加算するものである。スレッド#2は、[0,0,2]に[0,1,2]の値を加算するものである。スレッド#3は、[0,2,0]に[0,3,0]の値を加算するものである。スレッド#4は、[0,2,1]に[0,3,1]の値を加算するものである。スレッド#5は、[0,2,2]に[0,3,2]の値を加算するものである。

0146

集計処理の第0ステップでは、これらのスレッドが全て並列に実行される。それより後のステップでは、これらのスレッドの一部が並列に実行される。上記のように、中間テンソル154に対する集計処理の第1ステップでは24個の加算演算が行われるため、スレッド#0〜#47のうちの24個のスレッドが並列に実行される。例えば、スレッド#0〜#2,#6〜#8,#12〜#14,#18〜#20,#24〜#26,#30〜#32,#36〜#38,#42〜#44が実行され、それ以外のスレッドは実行されない。

0147

スレッド#0は、中間テンソル154aの[X,Y,Z]=[0,0,0]に[0,2,0]の値を加算する。スレッド#1は、[0,0,1]に[0,2,1]の値を加算する。スレッド#2は、[0,0,2]に[0,2,2]の値を加算する。

0148

第1の行列積演算では集計処理に24個のスレッドが使用されるのに対し、第2の行列積演算では48個のスレッドが使用されておりスレッド数が増加している。また、第2の行列積演算ではゼロの乗算やゼロの加算など、ダミー要素に基づく余分な演算が追加されている。一方で、第2の行列積演算では中間テンソル154のデータ範囲とスレッドとの対応付けが容易であり、並列処理の制御が簡潔になる。よって、GPGPS102が多数のスレッドを並列実行可能であれば、並列処理が効率化されて実行時間が短縮する。

0149

次に、第2のCSRデータに関する処理手順を説明する。
図16は、第2のCSRデータ生成の手順例を示すフローチャートである。
第2のCSRデータ生成は、ユーザアプリケーション121からの入力に応じて疎行列生成部123が二次元構造データの疎行列131を生成した後に行われる。

0150

(S40)データ構造変換部124は、最大値M=0に初期化する。
(S41)データ構造変換部124は、疎行列131(疎行列S2D)から行番号を1つ選択する(行番号row)。

0151

(S42)データ構造変換部124は、非ゼロ要素数m=0に初期化する。
(S43)データ構造変換部124は、上記の行番号rowについて、疎行列131から列番号を1つ選択する(列番号col)。

0152

(S44)データ構造変換部124は、疎行列131からrow行col列の値S2D[row][col](値val)を抽出し、val=0であるか判断する。val=0である場合、すなわち、S2D[row][col]がゼロ要素である場合、ステップS46に処理が進む。val=0でない場合、すなわち、S2D[row][col]が非ゼロ要素である場合、ステップS45に処理が進む。

0153

(S45)データ構造変換部124は、非ゼロ要素数mを1だけ大きくする。
(S46)データ構造変換部124は、ステップS43で、行番号rowについて全ての列番号colを選択したか判断する。全ての列番号colを選択した場合はステップS47に処理が進み、未選択の列番号colがある場合はステップS43に処理が進む。

0154

(S47)データ構造変換部124は、行番号rowの非ゼロ要素数mと最大値Mとを比較し、mがMより大きいか判断する。mがMより大きい場合はステップS48に処理が進み、mがM以下である場合はステップS49に処理が進む。

0155

(S48)データ構造変換部124は、最大値Mに非ゼロ要素数mを代入する。
(S49)データ構造変換部124は、ステップS41で、全ての行番号rowを選択したか判断する。全ての行番号rowを選択した場合はステップS50に処理が進み、未選択の行番号rowがある場合はステップS41に処理が進む。

0156

(S50)データ構造変換部124は、行数が疎行列131と同じであり列数がMの値配列151(値配列SV)を生成する。また、データ構造変換部124は、行数が疎行列131と同じであり列数がMの列番号配列152(列番号配列SC)を生成する。データ構造変換部124は、値配列151と列番号配列152の各要素をゼロに初期化する。

0157

図17は、第2のCSRデータ生成の手順例を示すフローチャート(続き)である。
(S51)データ構造変換部124は、疎行列131から行番号を1つ選択する(行番号row)。

0158

(S52)データ構造変換部124は、非ゼロ要素数m=0に初期化する。
(S53)データ構造変換部124は、上記の行番号rowについて、疎行列131から列番号を1つ選択する(列番号col)。

0159

(S54)データ構造変換部124は、疎行列131からrow行col列の値S2D[row][col](値val)を抽出し、val=0であるか判断する。val=0である場合、すなわち、S2D[row][col]がゼロ要素である場合、ステップS57に処理が進む。val=0でない場合、すなわち、S2D[row][col]が非ゼロ要素である場合、ステップS55に処理が進む。

0160

(S55)データ構造変換部124は、値配列151のrow行m列に値valを代入する(SV[row][m]=val)。また、データ構造変換部124は、列番号配列152のrow行m列に列番号colを代入する(SC[row][m]=col)。

0161

(S56)データ構造変換部124は、非ゼロ要素数mを1だけ大きくする。
(S57)データ構造変換部124は、ステップS53で、行番号rowについて全ての列番号colを選択したか判断する。全ての列番号colを選択した場合はステップS58に処理が進み、未選択の列番号colがある場合はステップS53に処理が進む。

0162

(S58)データ構造変換部124は、ステップS51で、全ての行番号rowを選択したか判断する。全ての行番号rowを選択した場合はCSRデータ生成が終了し、未選択の行番号rowがある場合はステップS51に処理が進む。

0163

図18は、第2の行列積演算の手順例を示すフローチャートである。
第2の行列積演算は、データ構造変換部124が第2のCSRデータを生成し、密行列生成部125が二次元構造データの密行列132を生成した後に行われる。

0164

(S60)行列積演算部126は、値配列151の行数rows、値配列151の列数Mおよび密行列132の列数colsを確認する。行列積演算部126は、大きさがrows×M×colsの中間テンソル153(中間テンソルT)を生成する。

0165

(S61)行列積演算部126は、列番号配列152の行番号と列番号を1つずつ選択し(行番号rowと列番号m)、列番号配列152からrow行m列の要素SC[row][m](列番号col)を選択する。

0166

(S62)行列積演算部126は、密行列132(密行列D)のcol行目をコピーし、中間テンソル153のX=row,Y=mに格納する(T[row][m][:])。なお、列番号colがダミーであっても通常通りコピーが行われる。

0167

(S63)行列積演算部126は、ステップS61で、列番号配列152の全ての要素を選択したか判断する。全ての要素を選択した場合はステップS64に処理が進み、未選択の要素がある場合はステップS61に処理が進む。なお、ステップS61,S62の処理は複数のスレッドを用いて並列処理化することができる。

0168

(S64)行列積演算部126は、値配列151の行番号と列番号を1つずつ選択し(行番号rowと列番号m)、値配列151からrow行m列の要素SV[row][m](値val)を選択する。

0169

(S65)行列積演算部126は、中間テンソル153のX=row,Y=mの各要素(T[row][m][:])に対して値valを乗じる。なお、値valがダミーでありval=0であっても通常通り乗算が行われる。

0170

(S66)行列積演算部126は、行列積演算部126は、ステップS64で、値配列151の全ての要素を選択したか判断する。全ての要素を選択した場合はステップS67に処理が進み、未選択の要素がある場合はステップS64に処理が進む。なお、ステップS64,S65の処理は複数のスレッドを用いて並列処理化することができる。

0171

(S67)行列積演算部126は、スレッドプール128からrows×floor(M/2)×cols個のスレッドを取得する。rowsは、中間テンソル153を更新することで得られた中間テンソル154(中間テンソルT)のX座標数に相当する。Mは、中間テンソル154のY座標数に相当する。colsは、中間テンソル154のZ座標数に相当する。行列積演算部126は、スレッド配列156(スレッド配列H)に、取得したスレッドのスレッド番号を登録する(H[:][:][:])。スレッド配列156のX座標数はrow、Y座標数はfloor(M/2)、Z座標数はcolsである。

0172

図19は、第2の行列積演算の手順例を示すフローチャート(続き)である。
(S68)行列積演算部126は、イテレーション数I=0に初期化する。
(S69)行列積演算部126は、スレッド配列156からスレッド番号を1つ選択する(H[row][m][col])。選択されたスレッド番号の位置は、X座標rowとY座標mとZ座標colによって特定される。選択されたスレッド番号が示すスレッドによって、以下のステップS70,S71が実行される。

0173

(S70)行列積演算部126は、mを2Iで割った余り(剰余)がゼロであるか、すなわち、m%2I=0であるか判断する。上記条件を満たす場合はステップS71に処理が進み、上記条件を満たさない場合はステップS72に処理が進む。

0174

(S71)行列積演算部126は、中間テンソル154から要素T[row][2I×2m][col]と要素T[row][2I×(2m+1)][col]を選択し、後者の値を前者に加算することで中間テンソル154を更新する。なお、前者および後者の少なくとも一方がダミーであり値がゼロであっても通常通り加算が行われる。

0175

(S72)行列積演算部126は、ステップS69で、スレッド配列156の全てのスレッド番号を選択したか判断する。全てのスレッド番号を選択した場合はステップS73に処理が進み、未選択のスレッド番号がある場合はステップS69に処理が進む。なお、ステップS70,S71の処理は並列処理化することができる。

0176

(S73)行列積演算部126は、イテレーション数Iを1だけ大きくする。
(S74)行列積演算部126は、I<ceil(log2M)を満たすか判断する。Mは中間テンソル154のY座標数である。上記条件を満たす場合はステップS69に処理が進み、上記条件を満たさない場合はステップS75に処理が進む。

0177

(S75)行列積演算部126は、中間テンソル154からY=0のデータ範囲を抽出して出力行列155(出力行列O)を生成する。すなわち、行列積演算部126は、中間テンソル154の全てのX座標rowとZ座標colについて、O[row][col]=T[row][0][col]とする。

0178

第2の実施の形態の情報処理装置100によれば、大規模疎行列が圧縮格納データによって表現され、大規模疎行列と密行列との行列積が圧縮格納データのまま実行される。よって、メモリ使用量が削減されると共に行列積の計算量が削減される。また、行列積演算がデータロードや乗算や加算などの単位演算細分化されて多数のスレッドに割り振られ、多数の演算器を有するプロセッサを用いてそれら多数のスレッドが並列に実行される。よって、行列積演算を高速に実行することができる。

0179

また、第2の行列積演算の方法を採用した場合、大規模疎行列の1行当たり非ゼロ要素数が可変であっても、ダミー要素の挿入によって圧縮格納データに含まれる1行当たり要素数が固定化される。よって、細分化した単位演算を複数のスレッドに割り振る制御が簡潔になり並列処理が効率化される。このため、プロセッサが有する多数の演算器を有効に活用することができ、行列積演算の実行時間を短縮することができる。

0180

10行列演算装置
11 記憶部
12 処理部
13行列演算プログラム
14a,14bスレッド
15,16,17行列
18圧縮格納データ
19ベクトルデータ

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

該当するデータがありません

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

該当するデータがありません

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ