特許ウォッチ

公開番号2024065355
公報種別公開特許公報(A)
公開日2024-05-15
出願番号2022174178
出願日2022-10-31
発明の名称疎行列ベクトル積演算装置、疎行列ベクトル積演算方法および疎行列ベクトル積演算プログラム
出願人日本電気株式会社
代理人個人,個人
主分類G06F 17/16 20060101AFI20240508BHJP(計算;計数)
要約【課題】疎行列ベクトル積を求める演算の性能を向上させることができる疎行列ベクトル積演算装置を提供する。
【解決手段】疎行列ベクトル積演算装置20は、所定の形式の第1の疎行列を構成する複数の列のうち非零の成分を所定数以上有する複数の列を非零の成分の数が多い順に並べることによって、所定の形式の第2の疎行列を生成する生成部21を備える。また、疎行列ベクトル積演算装置20は、第1の疎行列を構成する複数の列のうち非零の成分を所定数未満有する複数の列で構成される作業行列を構成する行に対してその行が有する非零の成分を行方向に探索し、非零の成分が探索されたら非零の成分を有する作業行列を構成する列を作業行列から抽出し、k(kは正の整数)番目に抽出された列を第k列として所定の形式の第3の疎行列に追加する追加処理を、作業行列を構成する各行に対して上から順に繰り返し実行する追加部を備える。
【選択図】図14
特許請求の範囲【請求項１】
所定の形式の第１の疎行列を構成する複数の列のうち非零の成分を所定数以上有する複数の列を前記非零の成分の数が多い順に並べることによって、前記所定の形式の第２の疎行列を生成する生成部を備える
ことを特徴とする疎行列ベクトル積演算装置。
続きを表示（約 1,600 文字）【請求項２】
第１の疎行列を構成する複数の列のうち非零の成分を所定数未満有する複数の列で構成される作業行列を構成する行に対して当該行が有する前記非零の成分を行方向に探索し、前記非零の成分が探索されたら前記非零の成分を有する前記作業行列を構成する列を前記作業行列から抽出し、ｋ（ｋは正の整数）番目に抽出された列を第ｋ列として所定の形式の第３の疎行列に追加する追加処理を、前記作業行列を構成する各行に対して上から順に繰り返し実行する追加部を備える
請求項１記載の疎行列ベクトル積演算装置。
【請求項３】
第２の疎行列と全ての追加処理が実行された第３の疎行列を、前記第２の疎行列、前記第３の疎行列の順で横方向に結合することによって所定の形式の第４の疎行列を生成する結合部を備える
請求項２記載の疎行列ベクトル積演算装置。
【請求項４】
第１の疎行列との乗算の対象であるベクトルの各成分を、前記第１の疎行列を構成する各列が第４の疎行列において並べられた順番に応じて入れ替える入替部を備える
請求項３記載の疎行列ベクトル積演算装置。
【請求項５】
第４の疎行列と各成分が入れ替えられたベクトルとの乗算を演算する演算部を備える
請求項４記載の疎行列ベクトル積演算装置。
【請求項６】
所定の形式の第１の疎行列を構成する複数の列のうち非零の成分を所定数未満有する複数の列で構成される作業行列を構成する行に対して当該行が有する前記非零の成分を行方向に探索し、前記非零の成分が探索されたら前記非零の成分を有する前記作業行列を構成する列を前記作業行列から抽出し、ｋ番目に抽出された列を第ｋ列として前記所定の形式の第２の疎行列に追加する追加処理を、前記作業行列を構成する各行に対して上から順に繰り返し実行する追加部を備える
ことを特徴とする疎行列ベクトル積演算装置。
【請求項７】
所定の形式の第１の疎行列を構成する複数の列のうち非零の成分を所定数以上有する複数の列を前記非零の成分の数が多い順に並べることによって、前記所定の形式の第２の疎行列を生成する
ことを特徴とする疎行列ベクトル積演算方法。
【請求項８】
所定の形式の第１の疎行列を構成する複数の列のうち非零の成分を所定数未満有する複数の列で構成される作業行列を構成する行に対して当該行が有する前記非零の成分を行方向に探索し、前記非零の成分が探索されたら前記非零の成分を有する前記作業行列を構成する列を前記作業行列から抽出し、ｋ番目に抽出された列を第ｋ列として前記所定の形式の第２の疎行列に追加する追加処理を、前記作業行列を構成する各行に対して上から順に繰り返し実行する
ことを特徴とする疎行列ベクトル積演算方法。
【請求項９】
コンピュータに、
所定の形式の第１の疎行列を構成する複数の列のうち非零の成分を所定数以上有する複数の列を前記非零の成分の数が多い順に並べることによって、前記所定の形式の第２の疎行列を生成する生成処理
を実行させるための疎行列ベクトル積演算プログラム。
【請求項１０】
コンピュータに、
所定の形式の第１の疎行列を構成する複数の列のうち非零の成分を所定数未満有する複数の列で構成される作業行列を構成する行に対して当該行が有する前記非零の成分を行方向に探索し、前記非零の成分が探索されたら前記非零の成分を有する前記作業行列を構成する列を前記作業行列から抽出し、ｋ番目に抽出された列を第ｋ列として前記所定の形式の第２の疎行列に追加する追加処理を、前記作業行列を構成する各行に対して上から順に繰り返し実行させる
ための疎行列ベクトル積演算プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、疎行列ベクトル積演算装置、疎行列ベクトル積演算方法および疎行列ベクトル積演算プログラムに関する。
続きを表示（約 1,300 文字）【背景技術】
【０００２】
機械学習やHPC(High-Performance Computing)の分野では、行列演算が多く行われる。行列演算では、一部の成分のみが非零の値を有し（以下、非零の成分と呼ぶ。）、他の成分が全て０（以下、零の成分と呼ぶ。）である行列である「疎行列」が用いられることも多い。疎行列の性質を利用して非零の成分だけが保存されると、記憶領域の省力化および計算時間の短縮化が行われる。
【０００３】
図１６は、疎行列の例を示す説明図である。図１６に示す疎行列における白色の矩形が、零の成分を表す。また、図１６に示す疎行列における斜線模様の矩形が、非零の成分を表す（他の図においても同様）。
【０００４】
図１６の左部に示すように、疎行列は、一部の成分のみが非零の値を有する行列である。また、図１６の右部に示すように、非零の成分だけを詰めて保存することによって、効率的に疎行列が保存される。
【０００５】
疎行列を対象とする演算は、疎行列とベクトルとの積（以下、疎行列ベクトル積と呼ぶ。）を求める演算であることが多い。図１７は、疎行列を対象とする演算の例を示す説明図である。
【０００６】
図１７に示すように、疎行列と列ベクトルとの乗算が行われることによって、疎行列ベクトル積が求められる。なお、疎行列を対象とする演算は、例えば非零の成分が詰められた形式の疎行列を対象に実行される。
【０００７】
非零の成分が詰められた疎行列の形式として、例えばJagged Diagonal Storage(JDS)が挙げられる。JDSは、ベクトル型コンピュータで多く使用される形式である。ベクトル型コンピュータは、「ベクトル」という単位ごとに処理を行うことによって高速に演算を実行するコンピュータである。
【０００８】
ベクトル型コンピュータによる処理を高速にするためには、ベクトル型コンピュータが一度に処理可能な量を示すベクトル長をより長くすることが求められる。JDSは疎行列ベクトル積を求める演算においてベクトル長をより長くできる形式であるため、ベクトル型コンピュータでJDSが多く使用される。
【０００９】
図１８は、JDSの疎行列の例を示す説明図である。図１８の上部に示すように、最初に疎行列の非零の成分が全て左に詰められ、図１８の中部に示す行列に疎行列が変換される。次いで、変換された行列の各行が非零の成分の数が多い順にソートされ、図１８の下部に示す行列に変換される。次いで、変換された行列の列方向（縦方向）に、非零の成分の値が保存される。
【００１０】
図１９は、JDSの内部表現の例を示す説明図である。図１９に示すJDSの内部表現は、図１８に示すJDSの疎行列に対応する。JDSの疎行列を保存するメモリは、図１９に示す「値(value)」、「列の位置(index)」、「新しい列が始まる位置(offset)」をそれぞれ保存している。
（【００１１】以降は省略されています）

関連特許