(57)【要約】【課題】行列ベクトル演算をより高速に行う。【解決手段】実施形態の情報処理装置は、行列と、ベクトルとの演算を行う情報処理装置であって、分割処理部と、サイズ設定部と、格納部と、演算部とを有する。分割処理部は、行列を独立して演算するブロック単位に分割する。サイズ設定部は、分割したブロックごとに、ブロックとの演算にかかるベクトルの要素数に基づいてキャッシュメモリにおいて確保する所定領域のサイズを設定する。格納部は、サイズを設定して確保した所定領域にブロックとの演算にかかるベクトルの要素を格納する。演算部は、所定領域に格納したベクトルの要素を参照し、ブロック単位でブロックとベクトルとの演算を行う。【選択図】図２
2020013412.tif 000002
【特許請求の範囲】
【請求項１】
行列と、ベクトルとの演算を行う情報処理装置において、
前記行列を独立して演算するブロック単位に分割する分割処理部と、
分割したブロックごとに、当該ブロックとの演算にかかるベクトルの要素数に基づいてキャッシュメモリにおいて確保する所定領域のサイズを設定するサイズ設定部と、
サイズを設定して確保した前記所定領域に前記ブロックとの演算にかかるベクトルの要素を格納する格納部と、
前記所定領域に格納した前記ベクトルの要素を参照し、前記ブロック単位で当該ブロックとベクトルとの演算を行う演算部と、
を有することを特徴とする情報処理装置。
【請求項２】
前記分割処理部は、分割したブロックとの演算にかかるベクトルの要素数に基づくサイズが所定値以上である場合、分割するブロックのサイズを小さくして前記ブロック単位の分割をやり直す、
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記格納部は、確保した前記所定領域以外の前記キャッシュメモリの領域に前記ブロックにかかる要素を格納する、
ことを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
コンピュータが、行列と、ベクトルとの演算を行う行列演算方法であって、
前記行列を独立して演算するブロック単位に分割し、
分割したブロックごとに、当該ブロックとの演算にかかるベクトルの要素数に基づいてキャッシュメモリにおいて確保する所定領域のサイズを設定し、
サイズを設定して確保した前記所定領域に前記ブロックとの演算にかかるベクトルの要素を格納し、
前記所定領域に格納した前記ベクトルの要素を参照し、前記ブロック単位で当該ブロックとベクトルとの演算を行う、
処理を実行することを特徴とする行列演算方法。
【請求項５】
コンピュータに、行列と、ベクトルとの演算を実行させる行列演算プログラムであって、
前記行列を独立して演算するブロック単位に分割し、
分割したブロックごとに、当該ブロックとの演算にかかるベクトルの要素数に基づいてキャッシュメモリにおいて確保する所定領域のサイズを設定し、
サイズを設定して確保した前記所定領域に前記ブロックとの演算にかかるベクトルの要素を格納し、
前記所定領域に格納した前記ベクトルの要素を参照し、前記ブロック単位で当該ブロックとベクトルとの演算を行う、
処理を実行させることを特徴とする行列演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、情報処理装置、行列演算方法および行列演算プログラムに関する。
【背景技術】
【０００２】
有限差分法、有限体積法、有限要素法などの手法を用いた科学技術計算では、有限差分法、有限体積法、有限要素法などで離散化された偏微分方程式を一般に疎行列を係数行列とした連立一次方程式として扱う。このため、多くの場合、連立一次方程式を解く問題に帰着する。この連立一次方程式は、ＣＧ（conjugate  gradient）法やＢｉＣＧ（Bi-Conjugate  Gradient）法などの非定常反復法によって解かれることが多い。また、非定常反復法では、収束に要する反復回数を減らすため、不完全ＬＵ分解／不完全コレスキー分解、ガウスサイデル前処理などの前処理を施すことがある。
【０００３】
図１２は、前処理付きＣＧ法の処理例を示すフローチャートである。図１２に示すように、前処理付きＣＧ法では、Ｓ３０１〜Ｓ３１４の各処理が行われて、連立一次方程式を表す係数行列（Ａ）の解ベクトル（ｘ）が求められる。このような前処理付きＣＧ法においては、Ｓ３０２、Ｓ３０３、Ｓ３０６、Ｓ３１１で行列ベクトル演算が行われ、これらの行列ベクトル演算が演算時間の大半を占めている。
【０００４】
行列ベクトル演算では、演算時間を短縮するため、ブロックマルチカラー法により行列ベクトル演算にかかる行列およびベクトルを並び替え、データ依存性を解消して並列に計算することが行われている。そして、行列ベクトル演算では、演算にかかるデータをキャッシュに格納し、キャッシュに格納したデータを各ＰＥ（Processing  Element）が読み出して並列に処理する従来技術が知られている。このように演算にかかるデータをキャッシュに格納し、メインメモリからのデータ読み出しにより演算を中止しなくても済むようにすることで、演算処理のスピードを向上することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特表２００５−５３５０５５号公報
【特許文献２】特開２００８−１８１３８６号公報
【特許文献３】特開２０１６−４２２４１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、キャッシュには演算にかかるデータの全てが収まるものではなく、行列ベクトル演算において再利用性の高いベクトルの要素がキャッシュにない場合はメインメモリ等にデータを探しに行く機会が増え、演算処理に時間を要することがある。
【０００７】
１つの側面では、行列ベクトル演算をより高速に行うことを可能とする情報処理装置、行列演算方法および行列演算プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
第１の案では、行列と、ベクトルとの演算を行う情報処理装置は、分割処理部と、サイズ設定部と、格納部と、演算部とを有する。分割処理部は、行列を独立して演算するブロック単位に分割する。サイズ設定部は、分割したブロックごとに、ブロックとの演算にかかるベクトルの要素数に基づいてキャッシュメモリにおいて確保する所定領域のサイズを設定する。格納部は、サイズを設定して確保した所定領域にブロックとの演算にかかるベクトルの要素を格納する。演算部は、所定領域に格納したベクトルの要素を参照し、ブロック単位でブロックとベクトルとの演算を行う。
【発明の効果】
【０００９】
本発明の１実施態様によれば、行列ベクトル演算をより高速に行うことができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施形態にかかる情報処理装置のハードウエア構成例を示す説明図である。
【図２】図２は、実施形態にかかる情報処理装置の機能構成例を示すブロック図である。
【図３】図３は、ブロックマルチカラー法の適用例を説明する説明図である。
【図４】図４は、キャッシュサイズの設定を説明する説明図である。
【図５−１】図５−１は、ブロックサイズを決定する処理の一例を示すフローチャートである。
【図５−２】図５−２は、ブロックサイズを決定する処理の一例を示すフローチャートである。
【図５−３】図５−２は、「ｃｏｌｏｒ０」での処理例を示す説明図である。
【図６】図６は、行列ベクトル積演算の処理の一例を示すフローチャートである。
【図７−１】図７−１は、セクタサイズを決定する処理の一例を示すフローチャートである。
【図７−２】図７−２は、行例ベクトル積関数と関数エントリポイントの一例を示す説明図である。
【図８−１】図８−１は、行列ベクトル積関数の処理例を示すフローチャートである。
【図８−２】図８−２は、Ｉｎｄｅｘ生成処理の一例を示すフローチャートである。
【図９−１】図９−１は、Ｉｎｄｅｘ生成の一例を示す説明図である。
【図９−２】図９−２は、「ｃｏｌｏｒ０」での処理例を示す説明図である。
【図９−３】図９−３は、「ｃｏｌｏｒ０」での処理例を示す説明図である。
【図１０−１】図１０−１は、「ｃｏｌｏｒ０」での行列ベクトル積演算における第２セクタ内容を示す説明図である。
【図１０−２】図１０−２は、「ｃｏｌｏｒ１」での行列ベクトル積演算における第２セクタ内容を示す説明図である。
【図１０−３】図１０−３は、「ｃｏｌｏｒ２」での行列ベクトル積演算における第２セクタ内容を示す説明図である。
【図１１】図１１は、行列ベクトル積演算の一例を説明する説明図である。
【図１２】図１２は、前処理付きＣＧ法の処理例を示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して、実施形態にかかる情報処理装置、行列演算方法および行列演算プログラムを説明する。実施形態において同一の機能を有する構成には同一の符号を付し、重複する説明は省略する。なお、以下の実施形態で説明する情報処理装置、行列演算方法および行列演算プログラムは、一例を示すに過ぎず、実施形態を限定するものではない。また、以下の各実施形態は、矛盾しない範囲内で適宜組みあわせてもよい。
【００１２】
図１は、実施形態に情報処理装置のハードウエア構成例を示す説明図である。図１に示すように、情報処理装置１は、例えばＰＣ（Personal  Computer）などであり、ユーザによる操作を受け付けて演算結果を表示するためのディプレイ２、キーボード３およびマウス４が接続される。
【００１３】
情報処理装置１は、ＣＰＵ１０（CPU:Central  Processing  Unit）、メインメモリ２０および記憶装置３０を有する。ＣＰＵ１０は、記憶装置３０に記憶されたプログラム３１を読み出して、メインメモリ２０に展開して実行することで、入力部１００、ブロックマルチカラー処理部１１０、ブロックサイズ設定部１２０、読み込み部１３０、行列ベクトル演算部１４０および出力部１５０（図２参照）にかかる各種の処理を行う。
【００１４】
また、ＣＰＵ１０は、並列に演算処理を行う第１ＰＥ１１ａ、第２ＰＥ１１ｂと、各ＰＥでの演算処理にかかるデータを格納するＬ１キャッシュ１２ａ、１２ｂと、第１ＰＥ１１ａ、第２ＰＥ１１ｂが共有するＬ２共有キャッシュ１３とを有する。なお、ＰＥ等については、ＧＰＵ（Graphics  Processing  Unit）を用いてもよい。
【００１５】
Ｌ２共有キャッシュ１３は、第１セクタ１３ａ、第２セクタ１３ｂの複数のセクタと呼ばれる単位に記憶領域を分割してキャッシュデータを管理するセクタキャッシュと呼ばれる機能を有する。セクタキャッシュでは、Ｌ２共有キャッシュ１３に占める第１セクタ１３ａおよび第２セクタ１３ｂの割合が適宜設定される（詳細は後述する）。また、セクタキャッシュでは、Ｌ２共有キャッシュ１３において、第１セクタ１３ａを通常のキャッシュとして使用し、再利用頻度の高いデータを第２セクタ１３ｂに配置することで、再利用頻度の高いデータがＬ２共有キャッシュ１３から追い出されることを防ぐ。
【００１６】
なお、本実施形態では、第１ＰＥ１１ａと、第２ＰＥ１１ｂとが共有するＬ２共有キャッシュ１３へのデータ格納を例示するが、第１ＰＥ１１ａ、第２ＰＥ１１ｂそれぞれのＬ１キャッシュ１２ａ、１２ｂへのデータ格納が同様に行わるものであってもよい。
【００１７】
メインメモリ２０は、ＲＡＭ（Random  Access  Memory）などであり、ＣＰＵ１０がプログラム３１を実行するための作業領域を提供する。記憶装置３０は、ＨＤＤ（Hard  Disk  Drive）などであり、プログラム３１やプログラム３１を実行する際に参照する設定情報等の各種データ３２を格納する。
【００１８】
なお、プログラム３１は、記憶装置３０に記憶されていなくてもよい。例えば、情報処理装置１が読み取り可能な記憶媒体に記憶されたプログラム３１を、情報処理装置１が読み出して実行するようにしてもよい。情報処理装置１が読み取り可能な記憶媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢ（Universal  Serial  Bus）メモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ等に接続された装置にこのプログラム３１を記憶させておき、情報処理装置１がこれらからプログラム３１を読み出して実行するようにしてもよい。
【００１９】
図２は、実施形態にかかる情報処理装置１の機能構成例を示すブロック図である。図２に示すように、情報処理装置１は、入力部１００、ブロックマルチカラー処理部１１０、ブロックサイズ設定部１２０、読み込み部１３０、行列ベクトル演算部１４０および出力部１５０を有する。
【００２０】
入力部１００は、キーボード３やマウス４による操作や、ファイルの読み込みなどにより、演算対象とする係数行列や右辺ベクトルなどの演算にかかるデータの入力を受け付ける。
【００２１】
ブロックマルチカラー処理部１１０は、公知のブロックマルチカラー法により入力された演算対象の行列（係数行列）を第１ＰＥ１１ａおよび第２ＰＥ１１ｂにおいて独立して演算するブロック単位に分割する処理部である。すなわち、ブロックマルチカラー処理部１１０は、分割処理部の一例である。具体的には、ブロックマルチカラー処理部１１０は、ブロック化部１１１、ブロック彩色部１１２、番号並び替え部１１３を有する。
【００２２】
ブロック化部１１１は、係数行列について、所定のブロックサイズでデータ依存性がある要素をまとめ、要素のブロックを作成する。なお、ブロックサイズは、ブロック内の要素数である。例えば、ブロックサイズが２である場合は、２×２の４要素を有するブロックとなる。
【００２３】
ブロック彩色部１１２は、ブロック化部１１１が作成したブロックについて、接続関係のあるブロック同士を異なる色に塗り分ける（色で分類する）彩色処理を行い、色を示す番号を付与する。これにより、同色中（同じ色番号）では、ブロックごとに並列に演算処理が可能となる。なお、ブロック内の演算については逐次処理となる。
【００２４】
番号並び替え部１１３は、色番号、ブロックの順番を示すブロック番号の若い順に、係数行列における要素の要素番号を並び替える。なお、読み込み部１３０は、係数行列における元の要素番号と、並び替え後の要素番号との対応関係をテーブルなどに保持しておく。
【００２５】
図３は、ブロックマルチカラー法の適用例を説明する説明図である。図３に示すブロックマルチカラー法の適用例では、１２×１２の係数行列および１２要素の右辺ベクトルを、ブロックサイズを２としてブロック化している。そして、「ｃｏｌｏｒ  ０」〜「ｃｏｌｏｒ  ２」の３色で彩色し、各色のブロックを２つのプロセッサエレメント（第１ＰＥ１１ａ、第２ＰＥ１１ｂ）で並列に処理可能としている。
【００２６】
例えば、「ｃｏｌｏｒ  ０」のブロック行番号が「０」のブロックＢ００、ブロックＢ０２は、第１ＰＥ１１ａで逐次に演算処理が行われる。また、ブロック行番号が「１」のブロックブロックＢ１１、ブロックＢ１２、ブロックＢ１３は、第２ＰＥ１１ｂで逐次に演算処理が行われる。
【００２７】
また、上記のブロック化およびブロックの彩色処理をした際に、それぞれのブロックで演算対象となるベクトルのブロック（要素）は決まる。例えば、「ｃｏｌｏｒ  ０」のブロック行番号が「０」のブロックＢ００、ブロックＢ０２については、Ｘ０（ｘ０，ｘ１）、Ｘ２（ｘ４，ｘ５）が演算対象となるベクトルの要素である。また、「ｃｏｌｏｒ  ０」のブロック行番号が「１」のブロックＢ１１、ブロックＢ１２、ブロックＢ１３については、Ｘ１（ｘ２，ｘ３）、Ｘ２（ｘ４，ｘ５）、Ｘ３（ｘ６，ｘ７）が演算対象となるベクトルの要素である。
【００２８】
ブロックサイズ設定部１２０は、ブロックマルチカラー法で彩色した色ごとに、ブロックマルチカラー処理部１１０が分割した各ブロックで演算対象となるベクトルの要素がキャッシュアウトしないように、ブロックマルチカラー法での分割にかかるブロックサイズを設定する。
【００２９】
具体的には、ブロックサイズ設定部１２０は、分割したブロックごとに、ブロックとの演算にかかるベクトルの要素数に基づいて再利用性の高いベクトルの要素を格納するための第２セクタ１３ｂのサイズを設定する。そして、ブロックサイズ設定部１２０は、設定した第２セクタ１３ｂのサイズに合わせて、第２セクタ１３ｂに格納するベクトルの要素のサイズに対応したブロックサイズを設定する。すなわち、ブロックサイズ設定部１２０は、サイズ設定部の一例である。
【００３０】
図４は、キャッシュサイズの設定を説明する説明図である。図４に示すように、第１セクタ１３ａおよび第２セクタ１３ｂを合わせたＬ２共有キャッシュ１３全体のキャッシュサイズをＣとする。
【００３１】
行列ベクトル演算において、再利用頻度の高いデータ、すなわちブロックごとに演算対象となるベクトルの要素を第２セクタ１３ｂに格納する。また、第１セクタ１３ａには、行列ベクトル演算における行列の要素など、再利用性が低いデータを格納する。
【００３２】
再利用性が低いとしても、第１セクタ１３ａについてもある程度のサイズは確保する必要があるため、０≦β＜となるβによって第２セクタ１３ｂの最大サイズＣ＊βを設定する。例えば、β＝０．８であれば、Ｌ２共有キャッシュ１３全体のキャッシュサイズＣの８割が第２セクタ１３ｂの最大サイズとなる。そして、各色の行列ベクトル演算で必要なベクトル要素のサイズがＣ＊β以下になるようにブロックサイズを設定する。これにより、ベクトルの要素が第２セクタ１３ｂからキャッシュアウトしないようにすることができる。
【００３３】
読み込み部１３０は、演算対象として入力され、メインメモリ２０などに格納された係数行列や右辺ベクトルなどの演算にかかるデータをＬ２共有キャッシュ１３に読み込む。具体的には、読み込み部１３０は、ブロックマルチカラー法で彩色した色ごとに、ブロックサイズ設定部１２０がサイズを設定して確保した第２セクタ１３ｂに、再利用頻度の高いブロックとの演算にかかるベクトルの要素を格納する。また、読み込み部１３０は、ブロックマルチカラー法で彩色した色ごとに、第１セクタ１３ａに再利用頻度の低い行列要素などのデータを格納する。
【００３４】
行列ベクトル演算部１４０は、読み込み部１３０によりＬ２共有キャッシュ１３に格納された、係数行列や右辺ベクトルなどの演算にかかるデータを参照し、解ベクトルを求めるための行列ベクトル演算の演算処理を行う。具体的には、行列ベクトル演算部１４０は、ブロックマルチカラー法で彩色した色ごとに、各ブロックについて第１セクタ１３ａに格納した行列要素などのデータと、第２セクタ１３ｂに格納したベクトルの要素のデータとを読み出す。次いで、行列ベクトル演算部１４０は、第１ＰＥ１１ａ、第２ＰＥ１１ｂにおいて、ブロックごとの演算処理を実施する。次いで、行列ベクトル演算部１４０は、各色のブロックごとの演算処理で求めた解ベクトルなどの演算結果をメインメモリ２０に格納する。
【００３５】
出力部１５０は、行列ベクトル演算部１４０の演算結果、すなわち行列ベクトル演算による解ベクトルをファイルまたはディプレイ２への表示などにより出力する。
【００３６】
図５−１、図５−２は、ブロックサイズを決定する処理の一例を示すフローチャートである。なお、処理に際して、演算にかかる係数行列（Ａ）、Ｌ２共有キャッシュ１３のキャッシュサイズ（Ｃ）およびブロックサイズの初期値（ｂｓ０）などのデータは、入力部１００からの入力などにより事前に得られているものとする。
【００３７】
図５−１に示すように、ブロックサイズを決定する処理が開始されると、ブロックサイズ設定部１２０は、処理対象とするブロックサイズの値（ｂｓ）をｂｓ＝ｂｓ０として初期値（ｂｓ０）に設定する（Ｓ１）。
【００３８】
次いで、ブロックマルチカラー処理部１１０は、公知のブロックマルチカラー法により、係数行列（Ａ）を第１ＰＥ１１ａおよび第２ＰＥ１１ｂにおいて独立して演算するブロック単位に分割する。具体的には、ブロック化部１１１は、係数行列（Ａ）について、ブロックサイズの値（ｂｓ）でデータ依存性がある要素をまとめてブロック化するブロック化処理を行う（Ｓ２）。次いで、ブロック彩色部１１２は、彩色処理を行い、接続関係のあるブロック同士を異なる色に塗り分けるブロック彩色処理を行う（Ｓ３）。
【００３９】
次いで、ブロックサイズ設定部１２０は、彩色した各色において、それぞれのブロックで処理対象となるブロックを特定する。そして、ブロックサイズ設定部１２０は、特定したブロックとの演算において必要なベクトルの要素数の最大値（Ｖ）を算出する（Ｓ４）。
【００４０】
具体的には、図５−２に示すように、ベクトルの要素数の最大値（Ｖ）を求める処理が開始されると、ブロックサイズ設定部１２０は、最大値（Ｖ）の値をＶ＝０として初期化する（Ｓ４０）。なお、処理対象となる色情報やブロックの情報は処理の開始時に得られているものとする。例えば色情報としては、総色数（ｎｃｏｌｏｒｓ）などがある。また、ブロックの情報としては、各色における開始ブロック行（ｂｓｔａ）、各色における終了ブロック行（ｂｅｎｄ）、ブロック数（ｎｂｌｏｃｋｓ）などがある。
【００４１】
次いで、ブロックサイズ設定部１２０は、色番号（ｉｃ）をｉｃ＝０とし（Ｓ４１）、最初の色番号から処理をスタートする。色番号（ｉｃ）の処理が開始されると、ブロックサイズ設定部１２０は、色番号（ｉｃ）のベクトル要素のデータサイズｖ[ｉｃ]をｖ[ｉｃ]＝０として初期化する（Ｓ４２）。
【００４２】
次いで、ブロックサイズ設定部１２０は、色番号（ｉｃ）のブロック番号（ｉｂ）をｉｂ＝ｂｓｔａ［ｉｃ］より求め（Ｓ４３）、ブロック（ｉｂ）に接続するブロックをカウントしてｂｃに格納する（Ｓ４４）。
【００４３】
次いで、ブロックサイズ設定部１２０は、接続するブロック数（ｂｃ）にブロックサイズ（ｂｓ）をかけ、ｖ[ｉｃ]＝ｖ[ｉｃ]＋ｂｃ＊ｂｓとしてベクトル要素のデータサイズを求める（Ｓ４５）。
【００４４】
次いで、ブロックサイズ設定部１２０は、ｉｂ＜ｂｅｎｄ［ｉｃ］であるか否かを判定し（Ｓ４６）、最終のブロックまで処理が進んだか否かを判定する。最終のブロックまで処理が進んでいなければ（Ｓ４６：ＹＥＳ）、ブロックサイズ設定部１２０は、ｉｂを１つインクリメントして（Ｓ４７）、Ｓ４４へ処理を戻す。
【００４５】
最終のブロックまで処理が進んでいれば（Ｓ４６：ＮＯ）、ブロックサイズ設定部１２０は、ベクトルの要素数の最大値（Ｖ）と、ｖ［ｉｃ］とを比較し、Ｖ＜ｖ［ｉｃ］であるか否かを判定する（Ｓ４８）。
【００４６】
Ｖよりもｖ［ｉｃ］の方が大きい場合（Ｓ４８：ＹＥＳ）、ブロックサイズ設定部１２０は、Ｖ＝ｖ［ｉｃ］としてＶの値を更新する（Ｓ４９）。Ｖよりもｖ［ｉｃ］の方が大きくない場合（Ｓ４８：ＮＯ）、ブロックサイズ設定部１２０は、Ｖの値をそのままとしてＳ５０へ処理を進める。
【００４７】
次いで、ブロックサイズ設定部１２０は、ｉｃ＜ｎｃｏｌｏｒｓであるか否かを判定し、彩色したすべての色について処理が済んだか否かを判定する（Ｓ５０）。処理が済んでいない場合（Ｓ５０：ＹＥＳ）、ブロックサイズ設定部１２０は、ｉｃを１つインクリメントして（Ｓ５１）、Ｓ４２へ処理を戻す。処理が済んだ場合（Ｓ５０：ＮＯ）、ブロックサイズ設定部１２０は処理を終了する。このＳ４０〜Ｓ５１の処理を行うことで、行列ベクトル演算においてブロックとの演算で必要なベクトルの要素数の最大値（Ｖ）と、色ごとにブロックとので必要なベクトルの要素数の最大値ｖ［ｉｃ］とを得ることができる。
【００４８】
図５−３は、「ｃｏｌｏｒ０」での処理例を示す説明図である。図５−３に示すように、ケースＣ１は、「ｃｏｌｏｒ０」におけるブロック行番号「０」の処理例を示している。ｖ［０］はｖ［０］＝０として初期化されている。ケースＣ１において、ブロック行番号「０」と接続するブロックは、ブロック列番号「０」、「２」のブロックＢ００、ブロックＢ０２である。よって、ｂｃ＝２であり、ｖ［０］は、ｖ［０］＋ｂｃ＊ｂｓ＝０＋２＊２＝４となる。
【００４９】
ケースＣ２は、「ｃｏｌｏｒ０」におけるブロック行番号「１」の処理例を示している。ｖ［０］は、ブロック行番号「０」の処理によりｖ［０］＝４となっている。ケースＣ２において、ブロック行番号「１」と接続するブロックは、ブロック列番号「１」、「２」、「３」のブロックＢ１１、ブロックＢ１２、ブロックＢ１３である。よって、ｂｃ＝３であり、ｖ［０］は、ｖ［０］＋ｂｃ＊ｂｓ＝４＋３＊２＝１０となる。このように、ブロックサイズ設定部１２０は、各色についてブロックとの演算に要するベクトルの要素数を求める。
【００５０】
図５−１に戻り、Ｓ４に次いで、ブロックサイズ設定部１２０は、算出したベクトルの要素数の最大値（Ｖ）と、第２セクタ１３ｂの最大サイズＣ＊βとを比較し、Ｖ＞Ｃ＊βであるか否かを判定する（Ｓ５）。
【００５１】
算出したベクトルの要素数の最大値（Ｖ）が第２セクタ１３ｂの最大サイズＣ＊βを超える場合は、行列ベクトル演算の際に、第２セクタ１３ｂにおいてキャッシュアウトが生じる。したがって、ブロックサイズ設定部１２０は、Ｖ＞Ｃ＊βである場合（Ｓ５：ＹＥＳ）、０≦α＜１である所定の縮小率αを用いてブロックサイズ（ｂｓ）をｂｓ＝ｂｓ＊αとして小さくする（Ｓ６）。次いで、ブロックサイズ設定部１２０は、Ｓ２に処理を戻してブロックマルチカラー法によるブロック単位の分割をやり直す。
【００５２】
Ｖ＞Ｃ＊βでない場合（Ｓ５：ＮＯ）、ブロックサイズ設定部１２０は、ベクトルの要素がキャッシュアウトしないように、ブロックサイズ（ｂｓ）を決定したものとして処理を終了する。このように、ブロックサイズ（ｂｓ）を小さくしていくことで、演算に要するベクトルの要素数を減らして第２セクタ１３ｂに収まるようにすることができる。
【００５３】
図６は、行列ベクトル積演算の処理の一例を示すフローチャートである。図６に示すように、行列ベクトル積演算の処理が開始されると、行列ベクトル演算部１４０は、色番号（ｉｃ）をｉｃ＝０とし（Ｓ１０）、最初の色番号から処理をスタートする。
【００５４】
次いで、ブロックサイズ設定部１２０は、色番号（ｉｃ）における色の処理で必要なベクトル要素の数ｖ［ｉｃ］から第２セクタ１３ｂのセクタサイズを決定する（Ｓ１１）。
【００５５】
図７−１は、セクタサイズを決定する処理の一例を示すフローチャートである。図７−１に示すように、処理が開始されると、ブロックサイズ設定部１２０は、ｖ［ｉｃ］個、色番号（ｉｃ）における色の処理で必要なベクトル要素の数を第２セクタ１３ｂのサイズとする（Ｓ１１１）。
【００５６】
次いで、ブロックサイズ設定部１２０は、第２セクタ１３ｂのサイズに対応する行列ベクトル積関数ＭａｔＶｅｃ（）の関数エントリポイント番号を予め設定されたテーブルから取得する（Ｓ１１２）。次いで、ブロックサイズ設定部１２０は、取得した番号に対応する関数エントリポイントを返す（Ｓ１１３）。この関数エントリポイントにより、読み込み部１３０は、第２セクタ１３ｂにおいて関数が使用する配列を確保し、色番号（ｉｃ）における色の処理で必要なベクトル要素を格納する。
【００５７】
図７−２は、行列ベクトル積関数と関数エントリポイントの一例を示す説明図である。図７−２に示すように、行列ベクトル積関数Ｆ１、Ｆ２は、Ｌ２共有キャッシュ１３に占める第１セクタ１３ａおよび第２セクタ１３ｂの比率ごとに、予め用意されている。ブロックサイズ設定部１２０は、第２セクタ１３ｂのサイズに対応する関数のエントリポイントが示されたテーブルＴ１を参照し、行列ベクトル積関数Ｆ１、Ｆ２に対応するエントリポイントを求める。これにより、第２セクタ１３ｂでは、行列ベクトル積関数Ｆ１、Ｆ２に対応するエントリポイントにおいて演算にかかる配列が格納される。
【００５８】
図６に戻り、Ｓ１１に次いで、行列ベクトル演算部１４０は、行列ベクトル積関数ＭａｔＶｅｃ（Ａ，ｘ，ｙ，ｉｃ）の演算を行う（Ｓ１２）。なお、Ａは係数行列、ｘは右辺ベクトル、ｙは求める解ベクトル、ｉｃは色番号を示す。
【００５９】
図８−１は、行列ベクトル積関数に処理例を示すフローチャートである。図８−１に示すように、行列ベクトル積関数ＭａｔＶｅｃ（Ａ，ｘ，ｙ，ｉｃ）の処理が開始されると、読み込み部１３０は、行列ベクトル演算において、右辺ベクトル（ｘ）を格納する配列ｘｔｅｍｐを確保する（Ｓ１２１）。
【００６０】
次いで、読み込み部１３０は、Ｉｎｄｅｘ生成処理により、行列ベクトル演算の各ブロックで演算対象となる右辺ベクトル（ｘ）のベクトル要素を特定し、それらの要素を示す要素番号をＩｎｄｅｘに格納する。次いで、読み込み部１３０は、右辺ベクトル（ｘ）からＩｎｄｅｘに対応する要素を配列ｘｔｅｍｐにコピーする（Ｓ１２２）。
【００６１】
図８−２は、Ｉｎｄｅｘ生成処理の一例を示すフローチャートである。図８−２に示すように、Ｉｎｄｅｘ生成処理が開始されると、読み込み部１３０は、ブロック番号ｉｂの値をｉｂ＝０として初期化する（Ｓ１３０）。次いで、読み込み部１３０は、各ブロックについて処理に用いる変数ｋをｋ＝０として初期化する（Ｓ１３１）。
【００６２】
次いで、読み込み部１３０は、配列Ｉｎｄｅｘ［ｉｂ］［ｋ］にブロック番号がｉｂのブロックと接続するブロック内のベクトル要素の番号を格納する（Ｓ１３２）。なお、ブロック館の接続関係は、ブロック化された行列のブロック列番号で表されている。
【００６３】
次いで、読み込み部１３０は、ブロック番号ｉｂのブロックと接続するブロックをすべてチェックしたか否かを判定する（Ｓ１３３）。すべてチェックしていない場合（Ｓ１３３：ＮＯ）、読み込み部１３０は、変数ｋの値を１つインクリメントして（Ｓ１３４）、Ｓ１３２へ処理を戻す。
【００６４】
すべてチェックした場合（Ｓ１３３：ＹＥＳ）、読み込み部１３０は、ｉｂ＜ｎｂｌｏｃｋｓであるか否かを判定し、最終のブロックまで到達しているか否かを判定する（Ｓ１３５）。ｉｂ＜ｎｂｌｏｃｋｓである場合（Ｓ１３５：ＹＥＳ）、読み込み部１３０は、ブロック番号ｉｂを１つインクリメントしてＳ１３１へ処理を戻す。ｉｂ＜ｎｂｌｏｃｋｓでない場合（Ｓ１３５：ＮＯ）、読み込み部１３０はＩｎｄｅｘ生成処理を終了する。
【００６５】
図９−１は、Ｉｎｄｅｘ生成の一例を示す説明図である。図９−１に示すように、Ｉｎｄｅｘ生成処理を行うことで、係数行列について色「ｃｏｌｏｒ  ０」〜「ｃｏｌｏｒ  ２」ごとにブロックＢ００〜Ｂ５５と演算するベクトルの要素が、ブロックごとに配列Ｉｎｄｅｘに格納される。具体的には、ベクトルの要素（ｘ０〜ｘ１１）の要素番号を示す値（１〜１１）が、「ｃｏｌｏｒ  ０」〜「ｃｏｌｏｒ  ２」におけるブロック「ｂｌｏｃｋ  ０」〜「ｂｌｏｃｋ  ５」ごとに配列Ｉｎｄｅｘに格納される。
【００６６】
図９−２、図９−３は、「ｃｏｌｏｒ  ０」での処理例を示す説明図である。図９−２に示すように、「ｃｏｌｏｒ  ０」にかかる係数行列の行列要素（ａ００〜ａ３６）について、四角で囲んだ部分をブロックＢ００〜Ｂ１３として表記している。ここで、ブロックの列番号が、そのブロックと接続関係にあるブロックを示す。
【００６７】
図９−３に示すように、ケースＣ３は、「ｂｌｏｃｋ  ０」での処理例を示している。ケースＣ３において、「ｂｌｏｃｋ  ０」との接続では、要素番号０、１が該当することから、配列Ｉｎｄｅｘ［０］には要素番号０、１が格納される。また、「ｂｌｏｃｋ  ２」との接続では、要素番号４、５が該当することから、配列Ｉｎｄｅｘ［０］には要素番号４、５が追加して格納される。
【００６８】
また、ケースＣ４は、「ｂｌｏｃｋ  １」での処理例を示している。ケースＣ４において、「ｂｌｏｃｋ  １」との接続では、要素番号２、３のベクトルの要素が該当することから、配列Ｉｎｄｅｘ［１］には要素番号２、３が格納される。また、「ｂｌｏｃｋ  ２」との接続では、要素番号４、５が該当することから、配列Ｉｎｄｅｘ［１］には要素番号４、５が追加して格納される。また、「ｂｌｏｃｋ  ３」との接続では、要素番号６、７が該当することから、配列Ｉｎｄｅｘ［１］には要素番号６、７が追加して格納される。このようにして、行列ベクトル演算の各ブロックで演算対象となる右辺ベクトル（ｘ）のベクトル要素を特定し、それらの要素を示す要素番号が配列Ｉｎｄｅｘに格納される。
【００６９】
図８−１に戻り、Ｓ１２２に次いで、読み込み部１３０は、配列ｘｔｅｍｐを第２セクタ１３ｂに指定し（Ｓ１２３）、配列ｘｔｅｍｐの内容を第２セクタ１３ｂに格納する。
【００７０】
次いで、行列ベクトル演算部１４０は、ブロック行番号ｉをｉ＝ｂｓｔａ［ｉｃ］として開始ブロック行に設定し（Ｓ１２４）、ａｉｊ≠０に対してｙ［ｉ］＝Σａｉｊ＊ｘｔｅｍｐｊとする行列ベクトル積の演算処理を行う（Ｓ１２５）。
【００７１】
次いで、行列ベクトル演算部１４０は、ブロック行番号ｉがｉ＜ｂｅｎｄ［ｉｃ］であるか否かを判定し、終了行番号まで到達しているか否かを判定する（Ｓ１２６）。ｉ＜ｂｅｎｄ［ｉｃ］である場合（Ｓ１２６：ＹＥＳ）、行列ベクトル演算部１４０は、ブロック行番号ｉを１つインクリメントしてＳ１２５へ処理を戻す。ｉ＜ｂｅｎｄ［ｉｃ］でない場合（Ｓ１２６：ＮＯ）、読み込み部１３０は行列ベクトル積関数の演算処理を終了する。
【００７２】
図１０−１は、「ｃｏｌｏｒ０」での行列ベクトル積演算における第２セクタ１３ｂ内容を示す説明図である。図１０−１に示すように、「ｃｏｌｏｒ０」の行列ベクトル積演算では、ｖ［０］＝１０をもとに、「ｃｏｌｏｒ０」の演算にかかるベクトル要素を格納するための第２セクタ１３ｂのセクタサイズを決定する（Ｓ２００）。
【００７３】
次いで、読み込み部１３０は、第１ＰＥ１１ａ、第２ＰＥ１１ｂのそれぞれで独立して行列ベクトル積演算を行うための配列ｘｔｅｍｐを確保する（Ｓ２０１）。次いで、読み込み部１３０は、Ｉｎｄｅｘ生成処理で生成された配列Ｉｎｄｅｘに従い、ベクトル要素を配列ｘｔｅｍｐに格納する（Ｓ２０２）。
【００７４】
次いで、読み込み部１３０は、配列ｘｔｅｍｐを第２セクタ１３ｂに設定して格納する（Ｓ２０３）。これにより、行列ベクトル演算部１４０は、第２セクタ１３ｂを参照して「ｃｏｌｏｒ０」での行列ベクトル積演算を行う。
【００７５】
図１０−２は、「ｃｏｌｏｒ１」での行列ベクトル積演算における第２セクタ１３ｂ内容を示す説明図である。図１０−２に示すように、「ｃｏｌｏｒ１」の行列ベクトル積演算では、ｖ［１］＝１４をもとに、「ｃｏｌｏｒ１」の演算にかかるベクトル要素を格納するための第２セクタ１３ｂのセクタサイズを決定する（Ｓ２１０）。
【００７６】
次いで、読み込み部１３０は、第１ＰＥ１１ａ、第２ＰＥ１１ｂのそれぞれで独立して行列ベクトル積演算を行うための配列ｘｔｅｍｐを確保する（Ｓ２１１）。次いで、読み込み部１３０は、Ｉｎｄｅｘ生成処理で生成された配列Ｉｎｄｅｘに従い、ベクトル要素を配列ｘｔｅｍｐに格納する（Ｓ２１２）。
【００７７】
次いで、読み込み部１３０は、配列ｘｔｅｍｐを第２セクタ１３ｂに設定して格納する（Ｓ２１３）。これにより、行列ベクトル演算部１４０は、第２セクタ１３ｂを参照して「ｃｏｌｏｒ１」での行列ベクトル積演算を行う。
【００７８】
図１０−３は、「ｃｏｌｏｒ２」での行列ベクトル積演算における第２セクタ１３ｂ内容を示す説明図である。図１０−３に示すように、「ｃｏｌｏｒ２」の行列ベクトル積演算では、ｖ［２］＝１０をもとに、「ｃｏｌｏｒ２」の演算にかかるベクトル要素を格納するための第２セクタ１３ｂのセクタサイズを決定する（Ｓ２２０）。
【００７９】
次いで、読み込み部１３０は、第１ＰＥ１１ａ、第２ＰＥ１１ｂのそれぞれで独立して行列ベクトル積演算を行うための配列ｘｔｅｍｐを確保する（Ｓ２２１）。次いで、読み込み部１３０は、Ｉｎｄｅｘ生成処理で生成された配列Ｉｎｄｅｘに従い、ベクトル要素を配列ｘｔｅｍｐに格納する（Ｓ２２２）。
【００８０】
次いで、読み込み部１３０は、配列ｘｔｅｍｐを第２セクタ１３ｂに設定して格納する（Ｓ２２３）。これにより、行列ベクトル演算部１４０は、第２セクタ１３ｂを参照して「ｃｏｌｏｒ２」での行列ベクトル積演算を行う。
【００８１】
図１１は、行列ベクトル積演算の一例を説明する説明図である。より具体的には、図１１は、「ｃｏｌｏｒ０」での行列ベクトル積演算を例示している。図１１に示すように、「ｂｌｏｃｋ  ０」にかかるｘ０、ｘ１、ｘ４と、「ｂｌｏｃｋ  １」にかかるｘ２、ｘ３、ｘ４は、第２セクタ１３ｂに格納されている。
【００８２】
このため、「ｃｏｌｏｒ０」での行列ベクトル積演算において、ベクトル要素のキャッシュミスが生じることがなく、メインメモリ２０への再アクセスが不要となる。したがって、行列ベクトル積演算を高速化することができる。なお、本実施形態では行列ベクトル積演算を例示したが、ＩＬＵ／ＩＣの前進消去・後退代入や、ガウスサイデル法などの行列とベクトルの演算についても同様に実施できることは言うまでもないことである。
【００８３】
以上のように、行列と、ベクトルとの演算を行う情報処理装置１は、ブロックマルチカラー処理部１１０と、ブロックサイズ設定部１２０と、読み込み部１３０と、行列ベクトル演算部１４０とを有する。ブロックマルチカラー処理部１１０は、行列を独立して演算するブロック単位に分割する。ブロックサイズ設定部１２０は、分割したブロックごとに、ブロックとの演算にかかるベクトルの要素数に基づいてキャッシュメモリ（Ｌ２共有キャッシュ１３）において確保する所定領域（第２セクタ１３ｂ）のサイズを設定する。読み込み部１３０は、サイズを設定して確保した所定領域（第２セクタ１３ｂ）にブロックとの演算にかかるベクトルの要素を格納する。行列ベクトル演算部１４０は、所定領域（第２セクタ１３ｂ）に格納したベクトルの要素を参照し、ブロック単位でブロックとベクトルとの演算を行う。
【００８４】
このように、情報処理装置１では、行列と、ベクトルとの演算において再利用頻度の高いベクトルの要素をキャッシュメモリに確保した所定領域に格納することで、キャッシュミスが生じることを低減することができる。したがって、情報処理装置１では、キャッシュミスによりメインメモリ２０等にデータを探しに行くことが減ることから、行列と、ベクトルとの演算処理をより高速に行うことが可能となる。
【００８５】
また、情報処理装置１のブロックマルチカラー処理部１１０は、分割したブロックとの演算にかかるベクトルの要素数に基づくサイズが所定値以上である場合、分割するブロックのサイズを小さくしてブロック単位の分割をやり直す。これにより、情報処理装置１では、ベクトルの要素数に基づくサイズが所定値以上となることを抑止しつつ、行列を独立して演算するブロック単位に分割できる。したがって、情報処理装置１では、ブロックとの演算にかかるベクトルの要素を格納する所定領域（第２セクタ１３ｂ）がキャッシュメモリ（Ｌ２共有キャッシュ１３）の大部分を占めることを抑止でき、例えばベクトルの要素以外のアクセスが遅くなることを防ぐことができる。
【００８６】
また、情報処理装置１の読み込み部１３０は、確保した所定領域（第２セクタ１３ｂ）以外の領域（第１セクタ１３ａ）にブロックにかかる要素を格納する。このように、情報処理装置１では、行列と、ベクトルとの演算において再利用頻度の低いブロックにかかる要素を第１セクタ１３ａに格納することで、再利用頻度の高いベクトルの要素が演算時に書き換わることを抑止できる。
【００８７】
以上の実施形態に関し、さらに以下の付記を開示する。
【００８８】
（付記１）行列と、ベクトルとの演算を行う情報処理装置において、
前記行列を独立して演算するブロック単位に分割する分割処理部と、
分割したブロックごとに、当該ブロックとの演算にかかるベクトルの要素数に基づいてキャッシュメモリにおいて確保する所定領域のサイズを設定するサイズ設定部と、
サイズを設定して確保した前記所定領域に前記ブロックとの演算にかかるベクトルの要素を格納する格納部と、
前記所定領域に格納した前記ベクトルの要素を参照し、前記ブロック単位で当該ブロックとベクトルとの演算を行う演算部と、
を有することを特徴とする情報処理装置。
【００８９】
（付記２）前記分割処理部は、分割したブロックとの演算にかかるベクトルの要素数に基づくサイズが所定値以上である場合、分割するブロックのサイズを小さくして前記ブロック単位の分割をやり直す、
ことを特徴とする付記１に記載の情報処理装置。
【００９０】
（付記３）前記格納部は、確保した前記所定領域以外の前記キャッシュメモリの領域に前記ブロックにかかる要素を格納する、
ことを特徴とする請求項１または２に記載の情報処理装置。
【００９１】
（付記４）コンピュータが、行列と、ベクトルとの演算を行う行列演算方法であって、
前記行列を独立して演算するブロック単位に分割し、
分割したブロックごとに、当該ブロックとの演算にかかるベクトルの要素数に基づいてキャッシュメモリにおいて確保する所定領域のサイズを設定し、
サイズを設定して確保した前記所定領域に前記ブロックとの演算にかかるベクトルの要素を格納し、
前記所定領域に格納した前記ベクトルの要素を参照し、前記ブロック単位で当該ブロックとベクトルとの演算を行う、
処理を実行することを特徴とする行列演算方法。
【００９２】
（付記５）前記分割する処理は、分割したブロックとの演算にかかるベクトルの要素数に基づくサイズが所定値以上である場合、分割するブロックのサイズを小さくして前記ブロック単位の分割をやり直す、
ことを特徴とする付記４に記載の行列演算方法。
【００９３】
（付記６）前記格納する処理は、確保した前記所定領域以外の前記キャッシュメモリの領域に前記ブロックにかかる要素を格納する、
ことを特徴とする付記４または５に記載の行列演算方法。
【００９４】
（付記７）コンピュータに、行列と、ベクトルとの演算を実行させる行列演算プログラムであって、
前記行列を独立して演算するブロック単位に分割し、
分割したブロックごとに、当該ブロックとの演算にかかるベクトルの要素数に基づいてキャッシュメモリにおいて確保する所定領域のサイズを設定し、
サイズを設定して確保した前記所定領域に前記ブロックとの演算にかかるベクトルの要素を格納し、
前記所定領域に格納した前記ベクトルの要素を参照し、前記ブロック単位で当該ブロックとベクトルとの演算を行う、
処理を実行させることを特徴とする行列演算プログラム。
【００９５】
（付記８）前記分割する処理は、分割したブロックとの演算にかかるベクトルの要素数に基づくサイズが所定値以上である場合、分割するブロックのサイズを小さくして前記ブロック単位の分割をやり直す、
ことを特徴とする付記７に記載の行列演算プログラム。
【００９６】
（付記９）前記格納する処理は、確保した前記所定領域以外の前記キャッシュメモリの領域に前記ブロックにかかる要素を格納する、
ことを特徴とする付記７または８に記載の行列演算プログラム。
【符号の説明】
【００９７】
１…情報処理装置
２…ディプレイ
３…キーボード
４…マウス
１０…ＣＰＵ
１１ａ…第１ＰＥ
１１ｂ…第２ＰＥ
１２ａ、１２ｂ…Ｌ１キャッシュ
１３…Ｌ２共有キャッシュ
１３ａ…第１セクタ
１３ｂ…第２セクタ
２０…メインメモリ
３０…記憶装置
３１…プログラム
３２…各種データ
１００…入力部
１１０…ブロックマルチカラー処理部
１１１…ブロック化部
１１２…ブロック彩色部
１１３…番号並び替え部
１２０…ブロックサイズ設定部
１３０…読み込み部
１４０…行列ベクトル演算部
１５０…出力部
Ｃ１〜Ｃ４…ケース
Ｆ１、Ｆ２…行列ベクトル積関数
Ｔ１…テーブル
【図１】
2020013412.tif 000003
【図２】
2020013412.tif 000004
【図３】
2020013412.tif 000005
【図４】
2020013412.tif 000006
【図５−１】
2020013412.tif 000007
【図５−２】
2020013412.tif 000008
【図５−３】
2020013412.tif 000009
【図６】
2020013412.tif 000010
【図７−１】
2020013412.tif 000011
【図７−２】
2020013412.tif 000012
【図８−１】
2020013412.tif 000013
【図８−２】
2020013412.tif 000014
【図９−１】
2020013412.tif 000015
【図９−２】
2020013412.tif 000016
【図９−３】
2020013412.tif 000017
【図１０−１】
2020013412.tif 000018
【図１０−２】
2020013412.tif 000019
【図１０−３】
2020013412.tif 000020
【図１１】
2020013412.tif 000021
【図１２】
2020013412.tif 000022