(57)【要約】【課題】疎行列ベクトル積を含む疎行列計算を高速化する。【解決手段】ＳｐＭＶ（疎行列計算）の並列処理をプロセッサの複数のスレッドを用いて実施する場合に、疎行列並替モジュールは、データをアクセスすべきメモリチャンクの位置を計算し、算出したメモリチャンクの位置から、各メモリチャンクに当該データが格納されている度合を表すスコアを計算し、計算されたスコアに基づいて疎行列の行を並替えて、各スレッドに処理を割当てることで、複数スレッドのメモリアクセスを局所的なメモリ領域に収め、ＳｐＭＶの並列処理を高速化する。【選択図】図５
2020080048.tif 000002
【特許請求の範囲】
【請求項１】
疎行列ベクトル積の計算を含む処理を実行する並列処理装置であって、
複数のスレッドを並列に実行可能なプロセッサと、
前記疎行列ベクトル積のための疎行列の非零要素と、入力ベクトルの要素および出力ベクトルの要素を格納するメモリと、を備え、
前記プロセッサは、
前記複数のスレッドが並列に実行されるとき、前記メモリが備える連続した領域を予め定められたサイズを有する部分領域の単位でアクセスし、
前記疎行列の非零要素と前記入力ベクトルの対応する要素との積和演算を含む出力ベクトルの各要素の計算を、処理単位として、前記複数のスレッドそれぞれに割当てる手段と、
前記メモリに格納される前記疎行列の非零要素を、前記部分領域を単位として、各前記複数のスレッドが前記入力ベクトルの対応する要素を参照する順序に従い並替える手段と、を含む、並列処理装置。
【請求項２】
前記並替える手段は、
前記疎行列の非零要素に対応する前記入力ベクトルの要素が前記部分領域に格納されている度合いを示す指標であって、当該部分領域の前記メモリにおける位置で重み付けした指標を生成する手段を、有し、
前記メモリに格納される前記疎行列の非零要素を、前記プロセッサのメモリアクセスのデータ幅に相当するサイズを有する部分領域を単位として、前記指標に従い、各前記複数のスレッドが前記入力ベクトルの対応する要素を参照する順序に従い並替える、請求項１に記載の並列処理装置。
【請求項３】
前記指標を生成する手段は、
前記疎行列の非零要素に対応する前記入力ベクトルの要素であって、前記部分領域に格納される要素のヒストグラムから前記度合いを生成し、当該部分領域の当該入力ベクトルの先頭からの位置に基づき前記重みを生成する、請求項２に記載の並列処理装置。
【請求項４】
前記指標を生成する手段は、
前記疎行列の非零要素に対応する入力ベクトルの要素であって、前記部分領域に格納される当該要素の前記入力ベクトルの先頭からの位置に基づき前記度合いを生成し、当該部分領域が参照される順序に基づき前記重みを生成する、請求項２に記載の並列処理装置。
【請求項５】
前記並列処理装置は、スパース化されたニューラルネットワークの推論処理を実行するよう構成されて、
前記入力ベクトルは、ニューラルネットワークの各層に入力されるデータに対応し、
前記疎行列は、ニューラルネットワークの各層における、入力データとニューロン間の接続の強弱を表すパラメータに対応する、請求項１から４のいずれか１項に記載の並列処理装置。
【請求項６】
疎行列ベクトル積の計算を含む処理を実行する並列処理方法をプロセッサに実行させるためのプログラムであって、
前記プロセッサは、
複数のスレッドを並列に実行可能であり、
前記複数のスレッドが並列に実行されるとき、前記疎行列ベクトル積のための疎行列の非零要素と、入力ベクトルの要素および出力ベクトルの要素を格納するメモリが備える連続した領域を、予め定められたサイズを有する部分領域の単位でアクセスし、
前記並列処理方法は、
前記疎行列の非零要素と前記入力ベクトルの対応する要素との積和演算を含む出力ベクトルの各要素の計算を、処理単位として、前記複数のスレッドそれぞれに割当てるステップと、
前記メモリに格納される前記疎行列の非零要素を、前記部分領域を単位として、各前記複数のスレッドが前記入力ベクトルの対応する要素を参照する順序に従い並替えるステップと、を含む、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、並列処理装置およびプログラムに関し、例えば、疎行列計算を実施する並列処理装置およびプログラムに関する。
【背景技術】
【０００２】
疎行列は、科学技術計算をはじめとする様々な分野で使用される。例えば、画像処理、音声処理、自然言語処理などで利用されるニューラルネットワークでは、スパース化により効率化されたニューラルネットワークの計算に、疎行列が使用される。
【０００３】
このような疎行列計算では、疎行列ベクトル積（ＳｐＭＶ:Sparse  Matrix-Vector  multiplication）が基本的な計算式として使用される。したがって、疎行列計算の速度は、ＳｐＭＶの速度により制限される。
【０００４】
ＳｐＭＶを含む疎行列計算は、複数のデータを同時並列に計算するＳＩＭＤ（Single  Instruction  Multiple  Data）方式のプロセッサを含む並列処理装置を用いることで、速度を向上させる試みが行われている。例えば、並列処理装置には、ＳＩＭＤ拡張命令を備えたＣＰＵ(Central  Processing  Unit)、またはＳＩＭＤ演算ユニットを多数備えたＧＰＵ（Graphics  Processing  Unit）などが用いられる。
【０００５】
このような並列処理装置を用いたＳｐＭＶの並列処理では、疎行列とベクトルのデータは複数の部分データに分割されて、複数の部分データは、並列処理装置が備える複数の実行ユニット（ＳＩＭＤの各実行レーン）に分配される。これにより、各実行ユニットは、当該実行ユニットに分配された疎行列とベクトルの部分データの積を計算する。このように、当該積の計算が複数の実行ユニットにより並列に実施される。
【０００６】
疎行列は、要素の多くが零である。また、疎行列は、非零の要素を不連続かつ非局所的に含む。このため、従来の並列処理装置を用いたＳｐＭＶの並列処理では、例えばＥＬＬＰＡＣＫ−Ｒの形式を用いて、疎行列から、その非零要素を含む密行列を生成してメモリ領域に格納する。これにより、疎行列の非零要素は、連続かつ局所的なメモリ領域に再配置され、メモリアクセスを高速化することができる。このような、ＥＬＬＰＡＣＫ−Ｒの形式に従う疎行列の格納方法が、例えば非特許文献１に開示されている。
2020080048.tif 000003
【発明の概要】
【発明が解決しようとする課題】
【０００７】
疎行列にＥＬＬＰＡＣＫ−Ｒの形式を適用して密行列を生成しメモリ領域に格納することで、ＳｐＭＶ（疎行列ベクトル積）の並列処理における疎行列の要素への参照（読出）は、メモリ領域を連続かつ局所的にアクセスすることが可能となる。一方、当該並列処理におけるベクトルを格納したメモリ領域へのアクセスは、疎行列における非零要素の位置に依存するため不連続かつ非局所的なままである。
【０００８】
一般に、ＳＩＭＤ方式のプロセッサは、データが連続しているデータ列の並列処理に向けられているため、不連続なアドレスからデータを読出して、読出されたデータを連続したデータ列とする、いわゆるギャザーと、データが連続したデータ列からのデータを不連続なアドレスに格納する、いわゆるスキャッターとの機能を備える。ギャザーおよびスキャッターは、それぞれ、一時に１つのメモリ領域（このメモリ領域のサイズは、例えばメモリアクセスのデータバス幅に相当する）をメモリアクセスの単位として実施される。したがって、ギャザーまたはスキャッターが、複数のメモリ領域にまたがって実施される場合は、複数のメモリ領域の数だけメモリアクセスの数が増える。
【０００９】
このようなプロセッサを含む並列処理装置を用いたＳｐＭＶの並列処理では、ベクトルの要素はギャザーおよびスキャッターに従ってアクセスされるため、アクセス対象のベクトルの要素が不連続なメモリ領域に格納される場合、上記に述べたようにメモリアクセス回数が増加して、ギャザーおよびスキャッターにかかるオーバヘッドが大きくなり、高速に並列処理を実行することができないとの課題がある。
【００１０】
この開示は、上述の課題を解決するためになされたものであり、その目的は、疎行列ベクトル積を含む疎行列計算を高速化することを目的とする。
【課題を解決するための手段】
【００１１】
この開示のある局面に係る並列処理装置は、疎行列と入力ベクトルを入力として、疎行列ベクトル積を計算し、結果を出力ベクトルに出力する処理を実行する装置であって、互いに並列処理可能な複数のスレッドを実行するプロセッサと、疎行列、入力ベクトルおよび出力ベクトルを格納するメモリと、を備える。プロセッサは、複数のスレッドが並列に実行されるとき、メモリが備える連続した領域を予め定められたサイズを有する部分領域の単位でアクセスする。また、出力ベクトルの１つの要素の計算（疎行列の非零要素と入力ベクトルの対応する要素との積和演算）を処理単位として、各スレッドに割当てる。プロセッサは、メモリに格納される疎行列の非零要素を、上記の部分領域（例えば、プロセッサが１回のメモリアクセスでデータ転送するサイズ（メモリアクセスのデータバス幅に相当するサイズ）を有した部分領域）を単位として、且つスレッドが入力ベクトルの対応する要素をスレッドが参照する順序に従い並替える。
【発明の効果】
【００１２】
この開示のある局面に係る並列処理装置は、疎行列ベクトル積を計算する場合に、並列処理装置が備えるプロセッサは、出力ベクトルの１つの要素の計算を処理単位として、スレッドに割当てる。また、プロセッサは、メモリに格納される疎行列の非零要素を、プロセッサの上記の部分領域（例えば、メモリアクセスのデータ幅に相当するサイズでアラインされたメモリアドレスから始まる連続した領域である部分領域）を単位として、且つスレッドが入力ベクトルの対応する要素を参照する順序に従って並替える。各スレッドは、並替え後の疎行列を用いて処理を実行し、結果を出力ベクトルの対応する要素に格納する。したがって、疎行列ベクトル積の計算では、各スレッドがメモリに格納された疎行列の非零要素と入力ベクトルの対応する要素をアクセスする場合、アクセスする領域を局所領域に収めることが可能となる。これにより、疎行列ベクトル積の計算ではメモリアクセス回数の増加は抑制されて、当該計算を高速に実施することができる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態に係る並列処理装置１の構成の一例を示すブロック図である。
【図２】実施の形態に係る記憶装置１１４の内容の一例を模式的に示す図である。
【図３】実施の形態に係る並列処理装置１が有するモジュールの構成の一例を模式的に示す図である。
【図４】実施の形態に係る並列処理装置１が実施する処理を概略的に示すフローチャートである。
【図５】実施の形態に係る疎行列並替モジュール３０の処理を概略的に示すフローチャートである。
【図６】実施の形態に係る疎行列の一例を模式的に示す図である。
【図７】図６の疎行列ＡのＥＬＬＰＡＣＫ−Ｒ形式の情報の一例を説明するための図である。
【図８】実施の形態に係る疎行列並替モジュール３０の処理に用いるデータの一例を模式的に示す図である。
【図９】実施の形態に係る疎行列Ａをスコアに従い並替える手順の一例を説明するための図である。
【図１０】実施の形態に係るＳｐＭＶを並列処理するために必要なデータの格納形式の一例を説明するための図である。
【図１１】実施の形態に係る疎行列並替モジュール３０の処理の変形例を示すフローチャートである。
【図１２】実施の形態に係るスコアの他の例を説明するための図である。
【図１３】実施の形態に係る疎行列Ａをスコアに従い並替える手順の他の例を説明するための図である。
【図１４】実施の形態に係るＳｐＭＶを並列処理するために必要なデータのメモリ配置の方式の他の例を説明するための図である。
【図１５】実施の形態に係るＳｐＭＶプログラムの記述の一例を概略的に示す図である。
【図１６】実施の形態に係るＳｐＭＶプログラムの実行ユニット１１１への割当ての一例を模式的に示す図である。
【図１７】実施の形態に係るＳｐＭＶプログラムによる処理の一例を示すフローチャートである。
【図１８】疎行列Ａのアクセスを模式的に示す図である。
【図１９】記憶装置１１４に格納されたベクトルｘのアクセスとベクトルｙのアクセスを模式的に示す図である。
【発明を実施するための形態】
【００１４】
以下、実施の形態について図面を参照して説明する。なお、図面において、同一の参照符号は、同一部分または相当部分を表す。
【００１５】
本開示では、並列処理装置は、ＳｐＭＶ（疎行列ベクトル積）の並列処理において、ベクトルへの高速なアクセス（参照または読出）が可能なように、ベクトルの要素のアクセス先が局所領域に収まるように、疎行列の要素の並替えがなされる。
【００１６】
（疎行列ベクトル積の計算）
実施の形態の背景として、ＳｐＭＶの計算式について説明する。例えば、ＳｐＭＶの計算式は一般に（１）式で表される。
【００１７】
【数１】
2020080048.tif 000004
【００１８】
すなわち、出力であるベクトルｙは、疎行列Ａに、入力のベクトルｘを乗算することによって得られる。ここで、疎行列Ａは、値が零である要素を比較的多く含んでいる点に特徴がある。
【００１９】
（１）式では、ベクトルｙの要素をｙ1，…，ｙnとする。第ｉ番目の出力ベクトルｙの要素をｙiまたはｙ（ｉ）と記載する。入力ベクトルｘの要素をｘ1，…，ｘmとする。第ｊ番目の入力ベクトルｘの要素をｘjまたはｘ（ｊ）と記載する。また、疎行列Ａは、第１から第ｎまでのｎ行と第１から第ｍまでのｍ列で構成される。第ｉ行第ｊ列の疎行列Ａの要素をＡijまたはＡ（ｉ，ｊ）と記載する。数値例を挙げると、（１）式は、例えば（２）式のようなＳｐＭＶとして示すことができる。
【００２０】
【数２】
2020080048.tif 000005
【００２１】
仮に、（２）式の行列計算の各行を、並列処理装置の対応する実行ユニットで個別に実行したとすれば、以下の（３）式に示す４つの計算式が、４個の実行ユニットにそれぞれ割当てられる。
【００２２】
【数３】
2020080048.tif 000006
【００２３】
実施の形態では、実行ユニットは、ＳｐＭＶの疎行列に含まれる各行の非零要素と入力ベクトルの対応する要素との積和計算を実行するモジュールまたはプロセッサを備える。このようなモジュールは、ソフトウェアのプログラムで提供され得る、または例えばＦＰＧＡ（Field  Programmable  Gate  Array）を含む回路で提供され得る。
【００２４】
（２）式に示すように、疎行列Ａの各行において非零要素は不連続かつ非局所的であるから、ＳｐＭＶの実行時に、ベクトルｘを格納したメモリ領域へのアクセス（参照）は、疎行列における非零要素の位置に依存して、不連続かつ非局所的となる。したがって、ベクトルｘを格納したメモリ領域へのアクセス速度が、処理速度を制限する。実施の形態では、ＳｐＭＶの並列処理において、ベクトルｘのメモリ領域へのアクセスが連続かつ局所的となるように疎行列Ａの要素を並替えることで、当該アクセスの回数を削減して、並列処理の高速化を実現する。
【００２５】
（並列処理装置の構成）
図１は、実施の形態に係る並列処理装置１の構成の一例を示すブロック図である。図１（Ａ）を参照して、並列処理装置１は、コンピュータに相当する。並列処理装置１は、複数のプロセッサ１１０、入出力装置１１３、記憶装置１１４、外部のネットワークを介して通信するための通信Ｉ／Ｆ（インターフェースの略）１１５および周辺機器Ｉ／Ｆ（インターフェースの略）１１６を備える。
【００２６】
各プロセッサ１１０は同様の構成を有する。図１（Ｂ）を参照して、プロセッサ１１０は、複数の実行ユニット１１１、アドレスコアレスユニット１１２１およびメモリインターフェースユニット１１２２を備える。各実行ユニット１１１は、演算ユニット１１１１と、レジスタ１１１２およびロード/ストアユニット１１１３を備える。メモリインターフェースユニット１１２２は、記憶装置１１４をアクセス（データ転送）する。
【００２７】
入出力装置１１３は、並列処理装置１に指示を入力するためにユーザーが操作するキーボードなどの入力装置と、並列処理装置１からの情報を出力するためのディスプレイなどの出力装置とを含む。通信Ｉ／Ｆ１１５が、図示しない有線または無線のネットワークを介した並列処理装置１の通信を制御する。周辺機器Ｉ／Ｆ１１６は、外部から脱着自在に装着される記録媒体１１７などの周辺機器を接続するデバイスであり、例えば、ＵＳＢ(Universal  Serial  Bus)、ＳＡＴＡ(Serial  AT  Attachment)、ＰＣＩ−Ｅｘｐｒｅｓｓなどを含む。
【００２８】
記憶装置１１４は、ＳＲＡＭ（Static  Random  Access  Memory）またはＤＲＡＭ（Dynamic  Random  Access  Memory）などの揮発性記憶装置、または、フラッシュメモリまたはＨＤＤ（Hard  Disk  Drive）などの不揮発性記憶装置を含む。
【００２９】
記録媒体１１７は、限定されないが、例えば、磁気ディスク、光ディスク、または半導体メモリなどを含み得る。
【００３０】
上記の構成において、各プロセッサ１１０のＮ（Ｎ≧２）個の実行ユニット１１１は互いに並列的にスレッドを実行することが可能である。このスレッドは、ＳｐＭＶの計算を含み得る。このようなスレッドはプログラムを実行することにより実現される。このようなプログラムはネットワークおよび通信Ｉ／Ｆ１１５を介して並列処理装置１にダウンロード（またはアップロード）されることにより、記憶装置１１４に格納され得る。また、プログラムは、記録媒体１１７に格納されて、周辺機器Ｉ／Ｆ１１６が、装着された記録媒体１１７からプログラムを読出し、読出されたプログラムが記憶装置１１４に格納されてもよい。
【００３１】
プロセッサ１１０は、例えばＣＰＵ、ＧＰＵなどを含み得る。各実行ユニット１１１は、例えばＣＰＵが備えるＳＩＭＤ拡張命令の各実行レーン、およびＧＰＵが備えるＳＩＭＤ演算ユニットの各実行レーンなどを含み得るが、これらに限定されない。プロセッサ１１０は、記憶装置１１４から読出すプログラムを各実行ユニット１１１にロードし、各実行ユニット１１１にプログラムを実行させる。実行ユニット１１１が互いに並列にプログラムを実行することにより、プロセッサ１１０が並列的に実行するスレッド、いわゆるマルチスレッドが実現され得る。
【００３２】
なお、実施の形態では、実行ユニット１１１をプロセッサ１１０が備えるプロセッサコアとして実現したが、実現態様は、これに限定されない。
【００３３】
（記憶内容の一例）
図２は、実施の形態に係る記憶装置１１４の内容の一例を模式的に示す図である。図２を参照して、記憶装置１１４は、各種のデータを格納するための領域Ｅ１、プロセッサ１１０が実行するプログラムを含む各種のプログラムを格納するための領域Ｅ２および作業領域などを含む。
【００３４】
領域Ｅ１は、並替え前の疎行列の情報１１８、並替え後の疎行列の情報１１９、アーキテクチャ情報１２０、ベクトルｘおよびベクトルｙが格納される。アーキテクチャ情報１２０は、ＳｐＭＶのプログラムを実行するために用いられる並列処理装置１のハードウェアアーキテクチャを示す情報であって、例えばプロセッサ１１０が備える実行ユニット１１１の並列度、ギャザーおよびスキャッターが一時にメモリアクセス可能なサイズなどを含み得る。実施の形態では、疎行列やベクトルのデータには、サイズ情報が付随している。記憶装置１１４の領域は、各スレッドが同じメモリ空間でデータ（入力ベクトルｘおよび出力ベクトルｙなど）を共有するように構成されている。
【００３５】
（ギャザーとスキャッター）
各実行ユニット１１１は、実行ユニット１１１ごとに異なるデータに対して、並行してメモリアクセスを実行する。アドレスコアレスユニット１１２１は、実行ユニット１１１からのメモリアクセスのアドレスを統合し、ハードウェアアーキテクチャにより決まるメモリアクセスのサイズ境界で分割する。メモリインターフェースユニット１１２２は、メモリアクセスのサイズ単位で、分割されたメモリアクセスを実行する。
【００３６】
実施の形態では、メモリインターフェースユニット１１２２は、領域Ｅ１のベクトルｘ、ベクトルｙなどのデータを、メモリアクセスのデータバス幅に対応するサイズでアクセス（読み書き）する。具体的には、メモリインターフェースユニット１１２２は、メモリアクセスのサイズ境界にアラインされたメモリアドレスから始まる連続した領域であるメモリチャンクを単位としてアクセスし、また各データは、メモリチャンクの先頭から格納される。メモリチャンクは、「部分領域」の一実施列である。
【００３７】
（機能構成）
図３は、実施の形態に係る並列処理装置１が有するモジュールの構成の一例を模式的に示す図である。図３を参照して、並列処理装置１は、「割当てる手段」の一実施例である割当てモジュール２９、疎行列を「並替える手段」の一実施例に相当する疎行列並替モジュール３０と、ＳｐＭＶモジュール３１とを備える。疎行列並替モジュール３０は、後述する指標を生成する指標生成モジュール３２を含む。実施の形態では、割当てモジュール２９、疎行列並替モジュール３０およびＳｐＭＶモジュール３１は、記憶装置１１４の領域Ｅ２に格納されるプログラムとして実現され得る。プロセッサ１１０は、領域Ｅ２からプログラムを読出し、読出されたプログラムを実行することにより、後述する疎行列Ａの並替えを実施し、また、それぞれがＳｐＭＶを並列に実行するように複数の実行ユニット１１１を制御する。
【００３８】
なお、変形例として、割当てモジュール２９、疎行列並替モジュール３０およびＳｐＭＶモジュール３１は、プログラムで実現される形態に限定されず、例えばＦＰＧＡなどの回路を含んでもよい。また、プログラムと回路の組合せで実現されてもよい。
【００３９】
（処理の概要）
図４は、実施の形態に係る並列処理装置１が実施する処理を概略的に示すフローチャートである。図４を参照して、並列処理装置１が実施する処理は、疎行列並替モジュール３０が、ＳｐＭＶにおいて、ベクトルｘへのアクセスが局所的および連続的となるように疎行列Ａを並替える処理（ステップＳ１）と、ＳｐＭＶモジュール３１が、並替え後の疎行列Ａを用いたＳｐＭＶを実施する処理（ステップＳ２）とを含む。
【００４０】
実施の形態では、並列処理装置１は、例えば画像処理における画像データまたは中間データの要素を示すベクトルｘを入力する。このような画像データなどの大規模データに対して疎行列Ａを繰り返し用いることで、ＳｐＭＶを基本とした行列積の計算を実施する。並列処理装置１は、例えばＳｐＭＶを、スパース化されたニューラルネットワークの推論処理として実行し得る。入力ベクトルは、ニューラルネットワークの各層に入力されるデータに対応し、疎行列Ａは、ニューラルネットワークの各層における、入力データとニューロン間の接続の強弱を表すパラメータに対応する。
【００４１】
実施の形態のプロセッサ１１０では、疎行列並替モジュール３０が疎行列Ａを並替え、ＳｐＭＶモジュール３１は並替え後の疎行列Ａを用いてＳｐＭＶのプログラムを実行する。
【００４２】
具体的には、図４を参照して、ステップＳ１では、プロセッサ１１０は疎行列並替モジュール３０を起動し、疎行列並替モジュール３０は、全ての疎行列Ａについて並替え処理を実施する（ステップＳ１０、Ｓ１１およびＳ１２）。また、ステップＳ２では、プロセッサ１１０はＳｐＭＶプログラムを実行する中でＳｐＭＶモジュール３１を起動する。ＳｐＭＶモジュール３１は、並替え後の疎行列Ａを用いた全てのＳｐＭＶの計算を行う（ステップＳ２０、Ｓ２１、Ｓ２２）。また、実施の形態では、説明を簡単にするために、ＳｐＭＶモジュール３１は並替え後の１つの疎行列ＡについてＳｐＭＶプログラムを実行する。
【００４３】
図５は、実施の形態に係る疎行列並替モジュール３０の処理を概略的に示すフローチャートである。図５を参照して、疎行列並替モジュール３０の指標生成モジュール３２は、データをアクセスすべきメモリチャンクの位置を計算し（ステップＳ１３）、メモリチャンクの位置から後述するヒストグラムを計算する（ステップＳ１４）。指標生成モジュール３２は、計算されたヒストグラムから後述するスコアを計算する（ステップＳ１５）。計算されたスコアの並替えが実施されて（ステップＳ１６）、疎行列並替モジュール３０は、並替えられたスコアに基づき疎行列Ａの要素を並替える（ステップＳ１７）。図５のフローチャートの各ステップの詳細は後述する。
【００４４】
（疎行列とＥＬＬＰＡＣＫ−Ｒ形式の情報）
実施の形態では、ＳｐＭＶの計算において、１回のメモリアクセスで複数のスレッドが同時に同一のメモリチャンク（メモリアクセスのサイズ境界にアラインされたメモリ領域）をアクセスするのを可能とするように、疎行列並替モジュール３０は疎行列Ａの要素の並替えを実施する。並替えのために、実施の形態では、疎行列ＡのＥＬＬＰＡＣＫ−Ｒ形式の情報である並替え前の疎行列の情報１１８は、記憶装置１１４に予め格納されている。
【００４５】
図６は、実施の形態に係る疎行列の一例を模式的に示す図である。図７は、図６の疎行列ＡのＥＬＬＰＡＣＫ−Ｒ形式の情報の一例を説明するための図である。図７のＥＬＬＰＡＣＫ−Ｒ形式の情報により、並替え前の疎行列の情報１１８が示される。図８は、実施の形態に係る疎行列並替モジュール３０の処理に用いるデータの一例を模式的に示す図である。図８のデータは、処理中に記憶装置１１４に一時的に格納されるデータである。図６を参照して疎行列Ａを説明する。疎行列Ａは、太枠で示す非零要素と、他の零要素とを含むｎ行×ｍ列（実施の形態では、ｎ＝ｍ＝８）のサイズを有する。疎行列Ａの各行の要素はメモリチャンク（実施の形態では、データ数は４）の先頭から格納される。図６の疎行列Ａの行の要素数はｎ個であるから、各行の要素は異なる２つのメモリチャンクにまたがって格納されることになる。
【００４６】
次に、図７を参照して、図６の疎行列ＡのＥＬＬＰＡＣＫ−Ｒ形式の情報を説明する。
ＥＬＬＰＡＣＫ−Ｒ形式の情報は、図７（Ａ）の非零要素のリストvalue［］（以下、非零要素リストvalue［］という）、図７（Ｂ）の非零要素の列位置のリストcolind［］（以下、非零要素列位置リストcolind［］という）および図７（Ｃ）の非零要素の数のリストrowlen［］（以下、非零要素数リストrowlen［］という）を含む。非零要素リストvalue［］は、疎行列Ａのｎ×ｋの密行列の要素（非零要素またはパディング）のリストである。ここで、ｎは疎行列Ａの一行のサイズを示し、ｋは疎行列Ａの一行あたりの非零要素の最大個数を表し、１行あたりの非零要素数がｋに満たない場合は、例えば「０」がパディングされる。
【００４７】
図７（Ｂ）を参照して、非零要素列位置リストcolind［］は、非零要素リストvalue［］と同じｎ×ｋのサイズを有する。非零要素列位置リストcolind［］の各要素は、非零要素リストvalue［］の各要素に１対１で対応する。非零要素列位置リストcolind［］の各要素の値は、非零要素リストvalue［］における対応の要素の疎行列Ａにおける列の番号（「０」〜「７」のいずれかの値）を示す。
【００４８】
図７（Ｃ）を参照して、非零要素数リストrowlen［］は、ｎ行のサイズを有する。非零要素数リストrowlen［］の各行の要素の値は、疎行列Ａの対応した行における非零要素の個数を示す。
【００４９】
次に、図５の各ステップの詳細な処理を、図８を参照して説明する。
（Ｓ１３−メモリチャンクの位置の算出）
疎行列Ａの並替えのための指標を生成するために、指標生成モジュール３２は、ＥＬＬＰＡＣＫ−Ｒ形式の情報から、メモリチャンクの位置を計算する（ステップＳ１３）。ステップＳ１３では、指標生成モジュール３２は、図７（Ａ）の非零要素リストvalue［］を走査して、非零要素リストvalue［］と同じｎ×ｋのサイズを有した図７（Ｅ）のメモリチャンクの位置リストを作成する。
【００５０】
具体的には、指標生成モジュール３２は、アーキテクチャ情報１２０と非零要素列位置リストcolind［］からベクトルｘのギャザーにおけるメモリチャンクの位置リスト（オフセット位置）（図８（Ａ）参照）を作成する。すなわち、指標生成モジュール３２は、非零要素列位置リストcolind［］の各要素を、掛け合わされるベクトルｘの要素のギャザーにおけるメモリチャンクの位置（オフセット位置）に変換し、メモリチャンクの位置リストに対応する要素として図８（Ａ）のリストに格納する。
【００５１】
例えば、ベクトルｘの要素が格納され得るメモリチャンクの最大数がＭのとき、非零要素列位置リストcolind［］の各要素の値は、メモリチャンクの位置（オフセット位置）として０からＭ−１のいずれかの値に換算される。また、メモリチャンクの位置リストの要素には、パディングがあてられる。このパディングは、後述するヒストグラムを作成する際にカウントされないので任意の値であってよい。
【００５２】
実施の形態では、指標生成モジュール３２は、アーキテクチャ情報１２０からメモリチャンクに含まれるデータ数（＝４）および疎行列Ａの列数（すなわち、ベクトルｘの要素数＝８）を抽出し、抽出したこれら情報を用いて、Ｍ＝２を得ることができる。したがって、メモリチャンクの位置リスト（図８（Ａ）参照）の各要素は、「０」または「１」を示す。図８（Ａ）では、パディングは「０」である。
【００５３】
（Ｓ１４−疎行列の行毎にヒストグラムの算出）
次に、指標生成モジュール３２は、メモリチャンクの位置リストから、疎行列Ａの行毎にヒストグラムを計算する（ステップＳ１４）。具体的には、指標生成モジュール３２は、図８（Ａ）のメモリチャンクの位置リストを各行において非零要素の個数分走査することにより図８（Ｂ）のヒストグラムを算出する。図８（Ｂ）のヒストグラムは、図８（Ａ）のメモリチャンクの位置リストの各行について、当該行における位置「０」を示す要素の個数（０〜３のいずれかの値）と、位置「１」を示す要素の個数（０〜３のいずれかの値）との組を有する。言い換えると、当該組の値は、対応する行における要素の位置「０」と位置「１」における度数分布を表す。
【００５４】
（Ｓ１５−疎行列Ａの行のスコアの算出）
次に、指標生成モジュール３２は、上記のヒストグラムから、疎行列Ａの行毎のスコアを計算する（ステップＳ１５）。
【００５５】
具体的には、疎行列並替モジュール３０は、図８（Ｂ）のスコアのリストを走査することにより図８（Ｃ）のスコアのリストを算出する。図８（Ｃ）のスコアのリストは、各行に、図８（Ｂ）のリストの対応の行に格納された組のスコア値を並べた４進数値が格納される。疎行列並替モジュール３０は、図８（Ｃ）のスコアのリストを走査することにより図８（Ｄ）のスコアのリストを算出する。図８（Ｄ）のスコアのリストは、各行に、図８（Ｃ）のリストの対応の行に格納された４進数値から算出された１０進数値が格納される。このような手順に従い、並替えのためのスコア（図８（Ｄ）参照）が算出される。なお、ここでは、疎行列Ａの各行の非零要素の最大個数Ｍは、Ｍ＝４であるためにスコアとしては４進数が算出されるが、４進数に限定されない。このように、Ｍ進数の各桁はスコア計算の重みを示す。
【００５６】
図８（Ｃ）または図８（Ｄ）のスコアの数値は、疎行列Ａ（より特定的にはＥＬＬＰＡＣＫ−Ｒ形式の密行列）の各行に対応して示される。疎行列Ａの各行に対応のスコアは、当該行の非零要素に掛け合わせるべき要素（すなわち、ベクトルｘの対応する要素）が、ある同一のメモリチャンクに格納されている個数（ヒストグラム）を、当該メモリチャンクの位置により重み付けをし、掛け合わせた値を示す。言い換えると、スコアは、対応する行の非零要素に掛け合わせるべき要素が、あるメモリチャンクに格納されている度合いを、メモリチャンクの位置で重み付けをし、数値化した指標を表す。具体的には、同一のスコアを示す行の場合、これら行の非零要素に掛け合わせるべき入力ベクトルｘの要素は同一のメモリチャンクに格納されている可能性が高い。また、異なるスコアを示す行の場合、これら行の非零要素に掛け合わせるべき入力ベクトルｘの要素は同一のメモリチャンクに格納されている可能性は低く、スコアの差が大きいほど、異なるメモリチャンクに格納されている可能性が高くなる。
【００５７】
（Ｓ１６−疎行列の行のスコアの並替え）
次に、疎行列並替モジュール３０は、疎行列Ａの各行のスコアを並替える。このとき、メモリチャンクに含まれるデータ数により並替えの範囲を制限する（ステップＳ１６）。具体的には、疎行列並替モジュール３０は、図８（Ｃ）または図８（Ｄ）のスコアを用いて行を並べ替えることで、図９（Ｄ）の非零要素行位置リストrowind［］を生成する。図９（Ｄ）の非零要素行位置リストrowind［］は、疎行列Ａの行の番号（０〜７）をスコアの値に従い並替えたリストを示す。
【００５８】
疎行列並替モジュール３０は、アーキテクチャ情報１２０から並列度を抽出する。実施の形態では、同じＳｐＭＶの計算を同時に実行する複数の実行ユニット１１１による、ベクトルｘへのアクセスが連続かつ局所的となるように、メモリチャンクに含まれるデータ数は並列度の倍数とする。実施の形態では、並列度は、例えばメモリチャンクに含まれるデータ数と等倍の「４」を示す。
【００５９】
疎行列並替モジュール３０は、疎行列Ａの行数（ｎ行）をメモリチャンクに含まれるデータ数と同じ数またはその倍数（ただし大きな値ではない）に従い複数の部分に分割し、分割された部分毎に並替えを行なう。これにより、並替えの範囲をメモリチャンクに含まれるデータ数（＝４）の倍数に収めることができて、後述するベクトルｙのアクセス（スキャッター）をメモリチャンクの倍数に収めることが可能となり、スキャッターのサイクル数の増加を抑えることができる。実施の形態では、「サイクル」は、メモリアクセスの実行に要する時間であり、ギャザーまたはスキャッターでは、メモリチャンク単位のアクセス回数を示す。
【００６０】
（Ｓ１７−スコアに基づく疎行列の並替え）
次に、疎行列並替モジュール３０は、スコアに基づき疎行列Ａの要素を並替える（ステップＳ１７）。図９は、実施の形態に係る疎行列Ａをスコアに従い並替える手順の一例を説明するための図である。
【００６１】
具体的には、疎行列並替モジュール３０は、図７（Ａ）、図７（Ｂ）および図７（Ｃ）のＥＬＬＰＡＣＫ−Ｒ形式のリストの行または要素を、図９（Ｄ）の非零要素行位置リストrowind［］を用いて並替えることにより、並替え後の非零要素リストvalue［］（図９（Ａ）参照）、並替え後の非零要素列位置リストcolind［］（図９（Ｂ））および並替え後の非零要素数リストrowlen［］（図９（Ｃ））をそれぞれ生成する。疎行列並替モジュール３０は、図９（Ａ）〜（Ｄ）に示す並替え後の疎行列の情報１１９を記憶装置１１４に格納する。
【００６２】
上記に述べたように、疎行列ＡのＥＬＬＰＡＣＫ−Ｒ形式の情報からヒストグラムに基づくスコアが計算され、次に、スコアに基づく疎行列Ａの行の並替えが実施されることにより、並替え後の疎行列の情報１１９を取得することができる。
【００６３】
図７〜図９に示す並替えでは、メモリチャンクに含まれるデータ数の２倍である８行（疎行列Ａの全行数）を、並替えの範囲としている。ＳｐＭＶモジュール３１は、後述するように、ＳｐＭＶプログラムを、行数「８」の疎行列Ａに対し、並替後の疎行列の情報１１９に基づき、並列度に従った４行単位で２回繰返し実行する（loopする）ことにより、ＳｐＭＶの計算を実行する。
【００６４】
本実施の形態では、効率的に並列演算処理を実施するために、図８に示す疎行列ＡのＥＬＬＰＡＣＫ−Ｒ形式の情報すなわち並替え前の疎行列の情報１１８および図９に示す並替え後の疎行列の情報１１９は、いずれも、列優先の順序に従い記憶装置１１４に格納される。なお、図７〜図９のリストは、記憶装置１１４の領域Ｅ１における物理的な配置とは切り離されたデータ構造を説明するものであり、これらリストの要素は、上記に述べたように記憶装置１１４の領域Ｅ１では、列優先の順番に従いで格納される。
【００６５】
（ＳｐＭＶを並列処理するために必要なデータのメモリ配置の方式）
図１０は、実施の形態に係るＳｐＭＶを並列処理するために必要なデータの格納形式の一例を説明するための図である。図１０（Ａ）は、並替え前の疎行列の情報１１８のメモリ配置の方式を示し、図１０（Ｂ）は並替え後の疎行列の情報１１９のメモリ配置の方式を示す。図１０（Ａ）と図１０（Ｂ）では、行単位で並列処理する実行ユニット１１１間で、連続領域を並列アクセスするように、列優先の順番に従いデータが並べられる。
【００６６】
図１０（Ａ）の並替え前の疎行列の情報１１８および図１０（Ｂ）の並替え後の疎行列の情報１１９は、メモリアクセスのサイズ境界（メモリチャンク）の先頭から格納される。
【００６７】
（疎行列並替モジュール３０の処理の変形例）
図１１は、実施の形態に係る疎行列並替モジュール３０の処理の変形例を示すフローチャートである。図１２は、実施の形態に係るスコアの他の例を説明するための図である。図１３は、実施の形態に係る疎行列Ａをスコアに従い並替える手順の他の例を説明するための図である。図１４は、実施の形態に係るＳｐＭＶを並列処理するために必要なデータのメモリ配置の方式の他の例を説明するための図である。
【００６８】
上述の図５に示された指標生成モジュール３２の処理では、メモリチャンクの位置ごとのヒストグラム（図８（Ｂ））からスコアを生成することにより、疎行列Ａを並替えるための指標を取得したが、指標生成モジュール３２は、当該変形例に示すようにヒストグラムを介さずにスコアを生成してもよい。
【００６９】
当該変形例では、疎行列Ａの各行に対応のスコアは、当該行の非零要素に掛け合わせるべきベクトルｘの対応する要素が格納されるメモリチャンクの位置に、当該要素を格納するメモリチャンクのアクセス（参照）の順序に基づく重みを掛け合わせた値を示す。
【００７０】
具体的には、図１１を参照して、疎行列並替モジュール３０の指標生成モジュール３２は、データをアクセスすべきメモリチャンクの位置を計算し（ステップＳ１３）、計算された位置からスコアを計算する（ステップＳ１５ａ）。疎行列並替モジュール３０は、計算されたスコアを並替え（ステップＳ１６ａ）、並替えたスコアに基づき疎行列Ａの要素を並替える（ステップＳ１７ａ）。この変形例においても、図６の疎行列Ａを処理する。したがって、図７（Ａ）〜図７（Ｃ）に示すＥＬＬＰＡＣＫ−Ｒ形式の情報、すなわち並替え前の疎行列の情報１１８が予め記憶装置１１４に格納されている。
【００７１】
図１１の各ステップの処理について、図１２〜図１４を参照して説明する。
まず、指標生成モジュール３２は図５のステップＳ１３の処理と同様に、ＥＬＬＰＡＣＫ−Ｒ形式の情報とアーキテクチャ情報１２０からメモリチャンクの位置を計算し、計算結果を示す図１２（Ａ）のメモリチャンクの位置リストを作成する（ステップＳ１３）。図１２（Ａ）のメモリチャンクの位置リストの作成手順は、図８（Ａ）のメモリチャンクの位置リストの作成手順と同じであるが、パディングの扱い方は異なる。つまり、図１２（Ａ）のメモリチャンクの位置リストにはパディングとして０またはメモリチャンクの最大値Ｍ−１があてられる。
【００７２】
次に、指標生成モジュール３２は、図１２（Ａ）のメモリチャンクの位置リストを各行において全ての要素（パディングを含めて）の個数分走査することにより、ｎ行のサイズを有した疎行列Ａの行毎のスコアを計算し、計算結果を示す図１２（Ｂ）および図１２（Ｃ）のスコアのリストを作成する（ステップＳ１５ａ）。具体的には、図１２（Ｂ）のスコアのリストの各行には、当該行に対応した図１２（Ａ）のメモリチャンクの位置リストの行に格納された要素の値（「０」または「１」）を並べた２進数値が格納される。図１２（Ｃ）のスコアのリストは、各行に、当該行に対応した図１２（Ｂ）のリストの２進数値から変換された１０進数値が格納される。疎行列並替モジュール３０は、このような手順に従い、疎行列Ａの要素を並替えるためのスコア（図１２（Ｃ）参照）を算出することができる。
【００７３】
次に、疎行列並替モジュール３０は、疎行列Ａの各行に対応のスコアを並替える（ステップＳ１６ａ）。具体的には、疎行列並替モジュール３０は、図１２（Ｂ）または図１２（Ｃ）のスコアを用いて行を並べ替えることで、図１３（Ｄ）の非零要素行位置リストrowind［］を生成する。図１３（Ｄ）の非零要素行位置リストrowind［］は、疎行列Ａの行の番号（０〜７）をスコアの値に従い並替えたリストを示す。この図１３（Ｄ）の非零要素行位置リストrowind［］の生成の手順は、ヒストグラムに基いた図９（Ｄ）の非零要素行位置リストrowind［］の生成の手順と同様であるので説明は繰返さない。
【００７４】
次に、疎行列並替モジュール３０は、図１３（Ｄ）の行の番号に基づき疎行列Ａの要素を並替える（ステップＳ１７ａ）。
【００７５】
具体的には、疎行列並替モジュール３０は、図７（Ａ）、図７（Ｂ）および図７（Ｃ）のＥＬＬＰＡＣＫ−Ｒ形式のリストの行または要素を、図１３（Ｄ）の非零要素行位置リストrowind［］を用いて並替えることにより、並替え後の非零要素リストvalue［］（図１３（Ａ）参照）、並替え後の非零要素列位置リストcolind［］（図１３（Ｂ））および並替え後の非零要素数リストrowlen［］（図１３（Ｃ））をそれぞれ生成する。疎行列並替モジュール３０は、図１３（Ａ）〜（Ｄ）に示す並替え後の疎行列の情報１１９を記憶装置１１４に格納する。
【００７６】
上記に述べたように、指標生成モジュール３２は、疎行列ＡのＥＬＬＰＡＣＫ−Ｒ形式の情報からヒストグラムを介さずにスコアを計算し、次に、疎行列並替モジュール３０は、算出されたスコアに基づく疎行列Ａの行の並替えを実施することにより、並替え後の疎行列の情報１１９を取得する。図１４（Ａ）と（Ｂ）には、それぞれ、変形例における、並替え前の疎行列の情報１１８と並替え後の疎行列の情報１１９の格納例が示される。図１４（Ａ）と（Ｂ）のデータは、図１０（Ａ）と（Ｂ）と同様に、メモリアクセスのサイズ境界（メモリチャンク）の先頭から列優先の順番に従い格納される。
【００７７】
（ＳｐＭＶの処理）
ＳｐＭＶモジュール３１は、疎行列並替モジュール３０により取得された並替え後の疎行列の情報１１９に従い疎行列Ａを用いたＳｐＭＶプログラムを実行する。ここでは、ＳｐＭＶプログラムを実行するために図１４（Ｂ）の並替え後の疎行列の情報１１９を用いるケースを説明する。なお、図１０（Ｂ）の並替え後の疎行列の情報１１９を用いる場合であっても、当該ケースと同様にＳｐＭＶプログラムを実行することができるので、ここでは説明を繰返さない。
【００７８】
図１５は、実施の形態に係るＳｐＭＶプログラムの記述の一例を概略的に示す図である。図１５（Ａ）と（Ｂ）は、ＳｐＭＶプログラムをスレッドの実行単位に分割する前のＳｐＭＶプログラムの記述の一例を示している。図１５（Ｃ）と（Ｄ）は、ＳｐＭＶプログラムをスレッドの実行単位に分割した後のＳｐＭＶプログラムの記述の一例を示している。図１５（Ｃ）と（Ｄ）のＳｐＭＶプログラムは、図１５（Ａ）と（Ｂ）のＳｐＭＶプログラムにおいて、行に関する外側のループ（インデックスｉのループ）を展開し、１つのループを１つのスレッドに割り当て、インデックスｉをパラメータとしたスレッド共通のプログラムを示す。図１５（Ａ）と（Ｃ）は、図７（Ａ）〜図７（Ｃ）のＥＬＬＰＡＣＫ−Ｒ形式の情報である並替え前の疎行列の情報１１８（図１４（Ａ））を用いるＳｐＭＶプログラムを示す。これに対して、図１５（Ｂ）と（Ｄ）は、図１３（Ａ）〜（Ｄ）が示す並替え後の疎行列の情報１１９（図１４（Ｂ）参照）を用いるＳｐＭＶプログラムを示す。
【００７９】
さらに、実施の形態では、並替えの範囲は、メモリチャンクに含まれるデータ数（または当該データ数の１倍、２倍・・・の倍数）に制限されている。実施の形態では、この倍数の値（１、２、３・・・）が、ベクトルｙのスキャッターにおけるアクセス回数の最大値となる。
【００８０】
上記に述べたように、実施の形態によれば、疎行列並替モジュール３０は、疎行列ＡのＥＬＬＰＡＣＫ−Ｒ形式の行をスコアに従い並替え、且つ並替えの範囲をメモリチャンクに含まれるデータ数（の倍数）に制限することで、ＳｐＭＶの計算において、実行ユニット１１１によるベクトルｘのギャザーとベクトルｙのスキャッターにおけるメモリへのアクセス回数、すなわちサイクル数を削減することが可能となる。
【００８１】
図１６は、実施の形態に係るＳｐＭＶプログラムの実行ユニット１１１への割当ての一例を模式的に示す図である。図１６（Ａ）は、図１５（Ｃ）のＳｐＭＶプログラムを各実行ユニット１１１に割当てた状態を示す。これに対して、図１６（Ｂ）は、割当てモジュール２９により、例えば図４のステップＳ１の処理時に、または、例えばステップＳ２の処理の開始前に、図１５（Ｄ）のＳｐＭＶプログラムを各実行ユニット１１１に割当てた状態を示す。これにより、疎行列Ａの非零要素と入力ベクトルｘの対応する要素との積和演算から構成される出力ベクトルの各要素の計算は、処理単位として、複数の実行ユニット１１１が実行する複数のスレッドそれぞれに割当てられる。
【００８２】
割当てモジュール２９は、各実行ユニット１１１にインデックスｉの値（スレッド番号）を割当てることで、各スレッドにＳｐＭＶプログラムが、すなわち図１５（Ｄ）に示されるようなインデックスｉをパラメータとしたスレッド共通のプログラムが割当てられる。なお、実行ユニットの数がスレッドの数より少ない場合、実行ユニット１１１に繰り返しスレッドが割当てられる。
【００８３】
その後、ＳｐＭＶモジュール３１は、並列化後（スレッドに分割した後）の図１５（Ｄ）のＳｐＭＶプログラムを実行する。具体的には、各実行ユニット１１１では、割当てモジュール２９により割当てられたインデックスｉにより指定される図１６（Ｂ）のＳｐＭＶプログラムが実行される。図１６（Ｂ）の各実行ユニット１１１のＳｐＭＶプログラム中では、非零要素数リストrowlen[]、非零要素リストvalue[]、非零要素列位置リストcolind[]および非零要素行位置リストrowind[]の要素は、当該実行ユニット１１１に割当てられたインデックスｉ（ｉ＝０、１、２・・・Ｎ−１）を用いて指定される。
【００８４】
なお、図３では、割当てモジュール２９は、ＳｐＭＶモジュール３１とは独立して備えられるが、モジュールの実装形式はこれに限定されない。すなわち、各実行ユニット１１１にＳｐＭＶプログラムの割当てがなされた後に、各実行ユニット１１においてＳｐＭＶプログラムが実行されるのであれば、ＳｐＭＶモジュール３１内に割当てモジュール２９が備えられる実装方式であってもよい。
【００８５】
図１７は、実施の形態に係るＳｐＭＶプログラムによる処理の一例を示すフローチャートである。実行ユニット１１１がＳｐＭＶプログラムを実行すると、図１７の処理が実現される。図１７（Ａ）は、図１６（Ａ）のＳｐＭＶプログラムの処理を示す。これに対して、図１７（Ｂ）は、図１６（Ｂ）のＳｐＭＶプログラムの処理を示す。プロセッサ１１０はＳｐＭＶモジュール３１を起動するとき、ＳｐＭＶプログラムを記憶装置１１４から読出し、読出されるＳｐＭＶプログラムは各実行ユニット１１１を用いて並列に実行される。
【００８６】
各実行ユニット１１１は、図１４（Ｂ）に示す並替え後の疎行列の情報１１９が示す値を変数に設定しながら計算を実行する。したがって、疎行列並替モジュール３０は、並替え後の疎行列の情報１１９を生成することにより、疎行列Ａに含まれる各行の非零要素とベクトルｘの対応する要素との積算を処理単位として、各実行ユニット１１１に、同一のメモリチャンクに格納されたベクトルｘの要素をアクセスするように当該積算を割当てることを可能にしている。
【００８７】
図１４（Ｂ）を参照して、実施の形態に係るＳｐＭＶプログラムを各実行ユニット１１１が実行することによるＳｐＭＶの並列処理を説明する。図１４（Ｂ）に示す並替え後の疎行列の情報１１９は、記憶装置１１４に格納されている。まず、実行ユニット１１１（実行ユニット[ｉ]）は、当該実行ユニット１１１に割当てられたインデックスｉの値を取得する（ステップＴ１）。実行ユニット１１１は、疎行列Ａの対応の行の要素（図１３（Ａ）のＥＬＬＰＡＣＫ−Ｒ形式の行列の要素）とベクトルｘの要素との積の総和を格納するための変数svalを初期化する（ステップＴ２）。実行ユニット１１１は、非零要素数リストrowlen［］の先頭からｉ番目の値を取得する（ステップＴ３）。実行ユニット１１１は、並替え後の疎行列Ａの非零要素リストvalue［］のｉ行目の要素の値mvalと、ベクトルｘのｉ番目（col）の要素の値xvalとの積（mval×xval）を算出し、算出された値を変数svalに積算する（ステップＴ４、Ｔ５、Ｔ６およびＴ７）。実行ユニット１１１は、このような積算処理を、非零要素リストvalue［］のｉ番目の行の全ての要素について繰返し実行する（ステップＴ３〜Ｔ８）。
【００８８】
実行ユニット１１１は、上記の積算処理の値を示す変数svalの値を、ベクトルｙの対応の行に格納する（ステップＴ１０、Ｔ１１）。具体的には、実行ユニット１１１は、非零要素行位置リストrowindのｉ番目の要素の値を取得し（ステップＴ１０）、取得した行位置の要素に対応するベクトルｙの配列の要素に、変数svalが示す積算値を設定する（ステップＴ１１）。
【００８９】
上記に述べたステップＴ１〜Ｔ１１の処理が複数の実行ユニット１１１（実行ユニット[ｉ]）において、マルチスレッドにより互いに並列に実施されて、ベクトルｙが算出される。
【００９０】
本実施の形態では、ベクトルｙの各要素の計算を、疎行列Ａの非零要素とベクトルｘの対応する要素との積和演算としているが、当該計算はこれに限定されない。例えば、ベクトルｙの各要素の計算は、当該積和演算と、他の演算（例えば、当該積和演算による算出値と或る値との演算（例えば加算、減算など））とを含んでもよい。
【００９１】
（ギャザーおよびスキャッターのメモリアクセス回数）
ＳｐＭＶプログラムの並列処理における、ギャザーとスキャッターのメモリアクセス回数について説明する。
【００９２】
疎行列Ａとベクトルｘのロードは、疎行列Ａの（非零要素の）列数だけ繰り返されるが、ベクトルｙのストアは１回のみ実施される。このため、疎行列Ａとベクトルｘのロードにおけるメモリチャンク単位のメモリアクセスの回数が、ＳｐＭＶの並列処理の速度を決定し得る支配的な要因となる。
【００９３】
具体的には、疎行列Ａのロード（ギャザー）１回におけるメモリチャンク単位のメモリアクセスは、ＥＬＬＰＡＣＫ−Ｒ形式と列優先のメモリ配置により、必ず１回である。これがＥＬＬＰＡＣＫ−Ｒ形式の情報を用いたことによる利点である。一方、ベクトルｘのロード（ギャザー）１回におけるメモリチャンク単位のメモリアクセスの回数は、疎行列Ａの非零構造（およびベクトルｘが格納されるメモリチャンク数）に依存して、１回以上となる。また、ベクトルｙのストア（スキャッター）１回におけるメモリチャンク単位のメモリアクセスの回数は、並替え前は１回のみ、並替え後は１回以上となる。
【００９４】
したがって、上記の述べた疎行列並替モジュール３０は、ベクトルｙのストアにおけるメモリチャンク単位のメモリアクセスの回数の増加が許容できる範囲で、ベクトルｘのロードにおけるメモリチャンク単位のメモリアクセス回数を削減することが可能となるよう疎行列Ａの並替えを実施する。なお、上記の「メモリアクセスの回数の増加が許容できる範囲」とは、例えばスキャッター回数とギャザー回数を疎行列Ａの並替えの前後で比較した場合に、スキャッター回数の増加に対してギャザー回数の削減が大きい場合は、当該許容できる範囲と言える。
【００９５】
（並替え前後におけるギャザーおよびスキャッター回数の比較）
実施の形態による並替え前後におけるギャザーおよびスキャッター回数の比較を、図１４（Ｂ）の並替え後の疎行列の情報１１９を用いるケースを例に説明する。なお、図１０（Ｂ）の並替え後の疎行列の情報１１９を用いる場合であっても、当該ケースと同様に、並替え前後におけるギャザーおよびスキャッター回数の比較を示すことができるので、説明は繰返さない。
【００９６】
図１８と図１９を参照して、ＳｐＭＶプログラムを実行する場合のギャザーとスキャッターによるメモリチャンクのアクセス回数を説明する。図１８は、疎行列Ａのアクセスを模式的に示す図である。図１８（Ａ）は、並替えがなされていない疎行列Ａのアクセス回数を示し、図１８（Ｂ）は並替えがなされた疎行列Ａのアクセス回数を示す。図１９は、記憶装置１１４に格納されたベクトルｘのアクセスとベクトルｙのアクセスを模式的に示す図である。図１９（Ａ）は、図１８（Ａ）の疎行列Ａを用いてＳｐＭＶプログラムを実行する場合のベクトルｘのアクセス回数を示し、図１９（Ｂ）は、図１８（Ｂ）の疎行列Ａを用いてＳｐＭＶプログラムを実行する場合のベクトルｘのアクセス回数を示す。以下の説明では、図１８と図１９の井げた記号付きの数値（０，１，２，３）を、括弧付の（０）、（１）、（２）、（３）に置き換えて説明する。
【００９７】
実施の形態では、ＳｐＭＶモジュール３１が、実行ユニット１１１に、図１４（Ｂ）の並替後の疎行列の情報１１９に従いＳｐＭＶプログラムを実行させる。これにより、４個の実行ユニット１１１のそれぞれが、ＳｐＭＶプログラムを１回実行すると、図１９（Ｂ）に示すように、疎行列Ａの４行分の要素を用いたＳｐＭＶの計算が実行される。ＳｐＭＶモジュール３１は、４個の実行ユニット１１１に、このような４行分の要素を用いたＳｐＭＶの計算を２回繰返し実行させる（loop（１）とloop（２））。
【００９８】
具体的には、まず、図１８（Ｂ）を参照して、４個の実行ユニット１１１（実行ユニット１１１（０）〜（４））は、図１４（Ｂ）の非零要素リストvalue［］のｉ番目の行の全ての要素について、図１４（Ｂ）の並替え後の非零要素列位置リストcolind［］に従い２回（loop（１）とloop（２））計算を繰返す。
【００９９】
loop（１）の処理を説明する。各実行ユニット１１１は、まず非零要素列位置リストcolind［］の列（１）が示す疎行列Ａの要素とベクトルｘの対応する要素とを積算する場合、図１４（Ｂ）に示すようにベクトルｘの０番目と１番目の要素がアクセスされる。ベクトルｘはメモリチャンクのデータ数である「４」でアライメントされているから、ベクトルｘの０番目と１番目の要素は同一のメモリチャンクに位置する（図１２（Ａ）参照）。このように、列（１）の積算においては、各実行ユニット１１１のアクセス先のメモリチャンクを同一にすることができる。これにより、列（１）の積算は１回のサイクル（cycle（１））で済ませることができる。
【０１００】
次の、非零要素列位置リストcolind［］の列（２）が示す疎行列Ａの要素とベクトルｘの対応する要素とを積算する場合、図１４（Ｂ）に示すようにベクトルｘの１番目と２番目の要素がアクセスされる。ベクトルｘの１番目と２番目の要素は同一のメモリチャンクに位置するから（図１２（Ａ）参照）、列（２）の積算も１回のサイクル（cycle（２））で済ませることができる。
【０１０１】
列（３）と列（４）についても、疎行列Ａの要素とベクトルｘの対応する要素とを積算する場合は、各実行ユニット１１１は同一のメモリチャンクをアクセスする。これにより、列（３）と列（４）の積算も、それぞれ、１サイクル（cycle（３）とcycle（４））で済ませることができる。
【０１０２】
loop（１）のＳｐＭＶの計算では、ベクトルｙへのアクセス（スキャッター）においては、図１４（Ｂ）または図１８（Ｂ）の非零要素行位置リストrowind[]に示すように、ベクトルｙの０番目、４番目、１番目および５番目の要素がアクセスされる。ベクトルｙの０番目、４番目、１番目および５番目の要素は異なるメモリチャンクに位置する。したがって、loop（１）のＳｐＭＶの計算では、図１９（Ｂ）に示すように、ベクトルｙへのアクセス（スキャッター）には、２サイクル（Cycle（５）およびCycle（６））を要する。
【０１０３】
次に、loop（２）の処理を説明する。各実行ユニット１１１は、非零要素列位置リストcolind［］の列（１）が示す疎行列Ａの要素とベクトルｘの対応する要素とを積算する場合、図１４（Ｂ）に示すようにベクトルｘの３番目と５番目の要素をアクセスする。ベクトルｘの３番目と５番目の要素は異なるメモリチャンクに位置する（図１２（Ａ）参照）。これにより、loop（２）の処理の列（１）の積算においては、各実行ユニット１１１は異なるメモリチャンクを個別にアクセスするため、当該列（１）の積算に２サイクル（cycle（７）とcycle（８））を必要とする。
【０１０４】
loop（２）の処理の以降の列（２）〜列（４）の積算においては、各実行ユニット１１１はベクトルｘのアクセスに関して同一のメモリチャンクをアクセスする。したがって、列（２）〜列（４）の各列の積算は１回のサイクル（cycle（９）、cycle（１０）、cycle（１１））で済ませることができる。
【０１０５】
loop（２）のＳｐＭＶの計算では、ベクトルｙへのアクセス（スキャッター）においては、図１４（Ｂ）または図１８（Ｂ）の非零要素行位置リストrowind[]に示すように、ベクトルｙの２番目、６番目、３番目および７番目の要素がアクセスされる。ベクトルｙの２番目、６番目、３番目および７番目の要素は異なるメモリチャンクに位置する。したがって、図１９（Ｂ）に示すようにベクトルｙへのアクセス（スキャッター）には、２サイクル（Cycle（１２）およびCycle（１３））を要する。
【０１０６】
このように、並替え後の疎行列の情報１１９に従うＳｐＭＶの計算では、図１９（Ｂ）に示すように、ベクトルｘのアクセス（ギャザー）に７サイクルと、ベクトルｙのアクセス（スキャッター）に６サイクルの計１３サイクルを要する。
【０１０７】
また、並替え後の疎行列の情報１１９に従うＳｐＭＶの計算では、疎行列Ａの要素とベクトルｘの対応する要素とを積算する場合に、各実行ユニット１１１のベクトルｘの要素のアクセス先は同一のメモリチャンクとすることができる(loop（１）とloop（２）における列（１）〜列（４）の積算処理を参照）。すなわち、各実行ユニット１１１によるベクトルｘのギャザーを局所化することができる。
【０１０８】
これに対して、図１４（Ａ）の並替え前の疎行列の情報１１８に従うＳｐＭＶの計算では、疎行列Ａの要素とベクトルｘの対応する要素とを積算する場合に、図１４（Ａ）または図１８（Ａ）の非零要素列位置リストcolind[]に示されるように、loop（１）とloop（２）における列（４）の積算処理では、各実行ユニット１１１のベクトルｘの要素のアクセス先は同一のメモリチャンクである（すなわち、ベクトルｘのギャザーを局所化する）が、列（１）〜列（３）それぞれの積算処理では、各実行ユニット１１１のベクトルｘの要素のアクセス先は異なるメモリチャンクであり、上記の局所化ができない。このように局所化が実現できないために、図１４（Ａ）の並替え前の疎行列の情報１１８に従うＳｐＭＶの計算では、図１９（Ａ）に示すように、図１４（Ｂ）の並替え後の疎行列の情報１１９に従うＳｐＭＶの計算の所要サイクル数よりも多い、計１６サイクルを要する。
【０１０９】
実施の形態では、疎行列並替モジュール３０は、互いに並列にＳｐＭＶの計算を実行する実行ユニット１１１の間で、ベクトルｘのギャザーを局所化する（アクセス先を同一のメモリチャンクに収めることを可能にする）並替え後の疎行列の情報１１９を作成し、ＳｐＭＶモジュール３１は、各実行ユニット１１１に並替え後の疎行列の情報１１９を用いてＳｐＭＶの計算を並列に実施させる。これにより、プロセッサ１１０は、ＳｐＭＶの並列処理を実施する場合に、記憶装置１１４へのアクセス回数を削減し、ＳｐＭＶの並列計算を高速化することができる。
【０１１０】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【０１１１】
１  並列処理装置、２９  割当てモジュール、３０  疎行列並替モジュール、３１  ＳｐＭＶモジュール、３２  指標生成モジュール、１１０  プロセッサ、１１１  実行ユニット、１１３  入出力装置、１１４  記憶装置、１１７  記録媒体、１１８  並替え前の疎行列の情報、１１９  並替え後の疎行列の情報、１２０  アーキテクチャ情報、１１１１  演算ユニット、１１１２  レジスタ、１１１３  ストアユニット、１１２１  アドレスコアレスユニット、１１２２  メモリインターフェースユニット、Ａ  疎行列、Ｅ１，Ｅ２  領域、colind［］  非零要素列位置リスト、rowind［］  要素行位置リスト、rowlen［］  非零要素数リスト、value［］  非零要素リスト、ｘ  入力ベクトル、ｙ  出力ベクトル。
【図１】
2020080048.tif 000007
【図２】
2020080048.tif 000008
【図３】
2020080048.tif 000009
【図４】
2020080048.tif 000010
【図５】
2020080048.tif 000011
【図６】
2020080048.tif 000012
【図７】
2020080048.tif 000013
【図８】
2020080048.tif 000014
【図９】
2020080048.tif 000015
【図１０】
2020080048.tif 000016
【図１１】
2020080048.tif 000017
【図１２】
2020080048.tif 000018
【図１３】
2020080048.tif 000019
【図１４】
2020080048.tif 000020
【図１５】
2020080048.tif 000021
【図１６】
2020080048.tif 000022
【図１７】
2020080048.tif 000023
【図１８】
2020080048.tif 000024
【図１９】
2020080048.tif 000025