(57)【要約】【課題】本開示は、疎行列ベクトル積を並列計算するアクセラレータ装置において、必要とするハードウェア資源を削減することができるアクセラレータ装置を提供する。【解決手段】本開示のアクセラレータ装置１００は、疎行列ベクトル積の計算を含む演算処理を実行するアクセラレータ装置である。アクセラレータ装置１００は、ＳｐＭＶユニット３０と、データバッファ２０とを備えている。ＳｐＭＶユニット３０部は、データロードユニット３４と、ＦＭＡアレイ３５と、疎行列ロードユニット３１（挿入部）とを有する。疎行列ロードユニット３１は、データロードユニット３４がデータバッファ２０に記憶している入力ベクトルの要素の各々に対して並列にアクセスする順序に従い、疎行列の非零要素の各々の配置にパディングを挿入する。【選択図】図２
2020166368.tif 000002
【特許請求の範囲】
【請求項１】
疎行列ベクトル積の計算を含む演算処理を実行するアクセラレータ装置であって、
疎行列の非零要素の各々と入力ベクトルの要素の各々との積和を含む出力ベクトルの要素の各々の計算処理を並列に実行する並列計算部と、
前記疎行列の非零要素の各々、前記入力ベクトルの要素の各々、および前記出力ベクトルの要素の各々を格納する記憶部と、を備え、
前記並列計算部は、
前記記憶部に記憶している要素の各々に対して並列にアクセスすることができるデータロード部と、
前記データロード部がアクセスした前記入力ベクトルの要素の各々と、前記疎行列の非零要素の各々との積和を計算する演算部と、
前記データロード部が前記記憶部に記憶している前記入力ベクトルの要素の各々に対して並列にアクセスする順序に従い、前記疎行列の非零要素の各々の配置にパディングを挿入する挿入部とを有する、アクセラレータ装置。
【請求項２】
前記挿入部は、
前記入力ベクトルの要素の各々に対して並列にアクセスする順序において、予め定められたストライド幅とデータ幅とで規定されるアクセス単位で並列にアクセスする場合、
前記アクセス単位に含まれない前記疎行列の非零要素の配置に対して前記パディングを挿入する、請求項１に記載のアクセラレータ装置。
【請求項３】
前記データロード部は、
前記入力ベクトルの要素の各々に対して並列にアクセスする場合に、メモリバンクごとにアクセスするアドレスを生成するアドレス生成部と、
前記アドレス生成部で生成したアドレスに対応する前記メモリバンクからの出力データを選択するデータ出力部とを有する、請求項２に記載のアクセラレータ装置。
【請求項４】
前記データロード部は、
前記アクセス単位の前記ストライド幅を１つの前記メモリバンクが有するデータの列数とし、
前記アクセス単位の前記データ幅を全ての前記メモリバンクが有するデータの列数の合計数とする、請求項３に記載のアクセラレータ装置。
【請求項５】
前記データロード部は、
前記メモリバンクの数を変更することができる、請求項４に記載のアクセラレータ装置。
【請求項６】
前記アクセラレータ装置は、ＦＰＧＡで構成される、請求項１〜請求項５のいずれか１項に記載のアクセラレータ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、疎行列ベクトル積を並列計算するアクセラレータ装置に関する。
【背景技術】
【０００２】
近年、ＡＩ（Artificial  Intelligence）、機械学習の分野では、その計算過程において大規模な行列を用いた計算が行われる。例えば、全結合型ニューラルネットワークの計算では、大規模なパラメータ行列が用いられ、当該パラメータ行列の計算をプロセッサで処理されている。大規模なパラメータ行列をプロセッサで処理する場合、計算量が多くなり計算の処理負担が大きくなる。
【０００３】
そのため、パラメータ行列をプルーニング（Pruning）などでパラメータを削減することで、多くの要素が零で構成されている疎行列に変換して、パラメータ容量および計算量を削減する処理が行われている。疎行列は要素の多くが零で構成される行列であるので、プロセッサでは非零要素のみを計算することになり計算量を削減できる。
【０００４】
このような大規模なパラメータ行列を変換して得られた疎行列を計算するためにアクセラレータ装置が開発されている。アクセラレータ装置として、例えば、特許文献１、非特許文献１，２などに開示されている。これらアクセラレータ装置では、疎行列ベクトル積（ＳｐＭＶ：Sparse  Matrix-Vector  Multiplication）を並列計算することで、高速計算を実現している。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許出願公開第２０１８／００４６９００号明細書
【非特許文献】
【０００６】
【非特許文献１】Fowers, J. et al. 、” A High Memory Bandwidth FPGA Accelerator for Sparse Matrix-Vector Multiplication"、IEEE Int. Symp. on Field-Programmable Custom Computing Machines (2014)
【非特許文献２】Song Han. et al. 、"ESE: Efficient Speech Recognition Engine with Sparse LSTM on FPGA"、International Symposium on FPGA 2017
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、疎行列ベクトル積（ＳｐＭＶ）では、疎行列の非零要素と、それに対応する入力ベクトルの要素との積和から、出力ベクトルの要素を計算する。そのため、疎行列ベクトル積（ＳｐＭＶ）を行うアクセラレータ装置では、疎行列の非零要素のみを計算するので、入力ベクトルの要素へのアクセスが疎行列の非零要素の構造に基づいて不連続なアクセスとなる。
【０００８】
また、アクセラレータ装置において、疎行列ベクトル積（ＳｐＭＶ）を並列計算するには、例えば、出力ベクトルの１つの要素の計算を、１つの並列実行の単位（スレッド）に割当て、並列計算することになる。この場合、アクセラレータ装置では、並列実行するスレッド間で、不連続な入力ベクトルの要素に対して並列アクセスするための機構を設ける必要があった。
【０００９】
アクセラレータ装置では、入力ベクトルの要素への不連続なアクセスを行うため入力データを複製してスレッドごとのメモリに格納する構成が必要であった。また、アクセラレータ装置では、不連続な入力ベクトルの要素に対して並列アクセスするために、入力データを分割して多数の独立したメモリバンクに格納し、スレッド間の並列アクセスを分散する構成が必要であった。アクセラレータ装置では、これらの構成を設けることでスレッドごとに冗長な複製メモリが必要であったり、また多数の独立したメモリバンクが必要であったりするなど、多くのハードウェア資源を必要とする問題があった。
【００１０】
そこで、本開示は、上述した課題を解決するためのものであり、疎行列ベクトル積を並列計算するアクセラレータ装置において、必要とするハードウェア資源を削減することができるアクセラレータ装置を提供することを目的としている。
【課題を解決するための手段】
【００１１】
本開示のある実施形態に従うと、疎行列ベクトル積の計算を含む演算処理を実行するアクセラレータ装置であって、疎行列の非零要素の各々と入力ベクトルの要素の各々との積和を含む出力ベクトルの要素の各々の計算処理を並列に実行する並列計算部と、疎行列の非零要素の各々、入力ベクトルの要素の各々、および出力ベクトルの要素の各々を格納する記憶部と、を備え、並列計算部は、記憶部に記憶している要素の各々に対して並列にアクセスすることができるデータロード部と、データロード部がアクセスした入力ベクトルの要素の各々と、疎行列の非零要素の各々との積和を計算する演算部と、データロード部が記憶部に記憶している入力ベクトルの要素の各々に対して並列にアクセスする順序に従い、疎行列の非零要素の各々の配置にパディングを挿入する挿入部とを有する。
【発明の効果】
【００１２】
本開示のアクセラレータ装置では、記憶部に記憶している入力ベクトルの要素の各々に対して並列にアクセスする順序に従い、疎行列の非零要素の各々の配置にパディングを挿入することで、必要とするハードウェア資源を削減することができる。
【図面の簡単な説明】
【００１３】
【図１】本実施の形態１に係るアクセラレータ装置の構成を示すブロック図である。
【図２】本実施の形態１に係るＳｐＭＶユニットの構成を示すブロック図である。
【図３】本実施の形態１に係るポストプロセスユニットの構成を示すブロック図である。
【図４】要素の多くが零で構成される疎行列の一例を示す図である。
【図５】図４に示した疎行列のＥＬＬＰＡＣＫ形式で表した一例を示す図である。
【図６】外部メモリに格納されるＥＬＬＰＡＣＫ形式の疎行列の一例を示す図である。
【図７】疎行列ベクトル積の計算処理を行うプログラムの一例を示した図である。
【図８】疎行列の行ごとの疎行列ベクトル積の計算処理を行うプログラムの一例を示した図である。
【図９】図８に示すプログラムを、疎行列の行ごと複数のスレッドとして並列実行する場合の一例を示す図である。
【図１０】疎行列のインデックスのリストの一例を示す図である。
【図１１】図１０に示す疎行列のインデックスのリストに基づいて入力ベクトルの要素にアクセスする順序の一例を示す図である。
【図１２】図１０に示す疎行列のインデックスのリストに対してパディングを平準化して挿入した一例を示す図である。
【図１３】疎行列のインデックスのリストに対してパディングを平準化して挿入する手順について示すフローチャートである。
【図１４】本実施の形態１に係るデータバッファのメモリ構成を示すブロック図である。
【図１５】図１４に示すデータバッファにアクセスするためのインデックスの一例を示す図である。
【図１６】本実施の形態１に係るロードユニットの構成を示すブロック図である。
【図１７】本実施の形態２に係るデータバッファのメモリ構成を示すブロック図である。
【図１８】図１７に示すデータバッファにアクセスするためのインデックスの一例を示す図である。
【図１９】本実施の形態２に係るロードユニットの構成を示すブロック図である。
【発明を実施するための形態】
【００１４】
以下に、本開示の実施の形態に係るアクセラレータ装置について図面を参照して詳しく説明する。なお、図中同一符号は同一または相当部分を示す。
【００１５】
（実施の形態１）
大規模な疎行列を高速計算するハードウェアのアクセラレータ装置として、例えばＦＰＧＡ（Field  Programmable  Gate  Array）を用いて実現することができる。ＦＰＧＡを用いたアクセラレータ装置では、メモリ、ロジック、演算器などのハードウェア資源を用いて、疎行列ベクトル積（ＳｐＭＶ）を並列計算している。以下の実施の形態では、ＦＰＧＡを用いたアクセラレータ装置について説明するが、ハードウェアで構成されたアクセラレータ装置であれば、ＦＰＧＡを用いたアクセラレータ装置に限定されない。
【００１６】
まず、疎行列ベクトル積（ＳｐＭＶ）を並列計算するＦＰＧＡを用いたアクセラレータ装置の構成について説明する。図１は、本実施の形態１に係るアクセラレータ装置１００の構成を示すブロック図である。図１に示すアクセラレータ装置（FPGA  Accelerator）１００は、例えば全結合型ニューラルネットワークの計算を実行するためのアクセラレータ装置である。アクセラレータ装置１００は、ホストプロセッサ（図示せず）と接続するシステムバス（System  Bus）２００、および外部メモリ（External  Memory）３００とそれぞれ接続されている。
【００１７】
アクセラレータ装置１００において全結合型ニューラルネットワークの計算を行う場合、ホストプロセッサからの入力データおよび出力データは、システムバス２００を経由して、アクセラレータ装置１００の内部のデータバッファに格納される。全結合型ニューラルネットワークの計算に用いる重みパラメータ（疎行列）は、ホストプロセッサからシステムバス２００、アクセラレータ装置１００を経由して外部メモリ３００に格納される。
【００１８】
アクセラレータ装置１００は、メモリインターフェース／インターコネクト（Memory  Interface／Interconnect）１０、データバッファ（Data  Buffer）２０、ＳｐＭＶユニット（SpMV  Unit）３０、ポストプロセスユニット（Post-Process  Unit）４０を含んでいる。メモリインターフェース／インターコネクト１０は、システムバス２００、および外部メモリ３００とそれぞれ接続されている。メモリインターフェース／インターコネクト１０は、システムバス２００を介してホストプロセッサと接続されている。メモリインターフェース／インターコネクト１０は、アクセラレータ装置１００の内部のデータバッファ２０、ＳｐＭＶユニット３０、およびポストプロセスユニット４０の間を相互接続している。
【００１９】
データバッファ２０は、ホストプロセッサからの入力データおよび出力データ（次層の入力データ）を格納する。ＳｐＭＶユニット３０は、データバッファ２０から読み出した入力データ列（入力ベクトルの要素）と、外部メモリ３００から読み出した重みパラメータ列（疎行列の非零要素）との積和を並列計算する。ポストプロセスユニット４０は、ＳｐＭＶユニット３０の後処理を行い。例えば、バイアスを加算する処理および活性化関数の処理を並列計算して出力データ列（出力ベクトルの要素）をデータバッファ２０に格納する。
【００２０】
次に、ＳｐＭＶユニット３０の構成について説明する。図２は、本実施の形態１に係るＳｐＭＶユニット３０の構成を示すブロック図である。ＳｐＭＶユニット３０は、疎行列ロードユニット（Sparse  Matrix  Load  Unit）３１、疎行列のインデックスのリストを格納するインデックスバッファ（Index  Buffer）３２、疎行列の非零要素の値のリストを格納するバリューバッファ（Value  Buffer）３３、データロードユニット（Data  Load  Unit）３４、ＦＭＡ（Fused  Multiply  Add：融合積和演算）アレイ（FMA  Array）３５、コントロールユニット（Control  Unit）３６を含んでいる。
【００２１】
疎行列ロードユニット３１は、外部メモリ３００から重みパラメータ列（疎行列の非零要素）を読み出し、読み出した重みパラメータ列（疎行列の非零要素）から疎行列のインデックスのリストをインデックスバッファ３２に、疎行列の非零要素のリストをバリューバッファ３３にそれぞれ格納する。インデックスバッファ３２およびバリューバッファ３３は、並列計算に必要なデータ幅に構成されている。
【００２２】
データロードユニット３４は、インデックスバッファ３２に格納した疎行列のインデックスのリストから並列計算を行うインデックス列を参照し、データバッファ２０から並列計算を行う入力データ列（入力ベクトルの要素）を読み出す。なお、データロードユニット３４が、疎行列のインデックスのリストに基づき、データバッファ２０にアクセスして入力ベクトルの要素を読み出す処理については、以下で詳しく説明する。
【００２３】
ＦＭＡアレイ３５は、複数のＦＭＡユニットで構成され、各々のＦＭＡユニットでデータロードユニット３４から入力データ列（入力ベクトルの要素）、バリューバッファ３３から疎行列の非零要素のデータ列をそれぞれ受け取り、融合積和を並列計算する。ＦＭＡアレイ３５は、疎行列の全ての列を並列計算した後、出力データ列（出力ベクトルの要素）をポストプロセスユニット４０に転送する。コントロールユニット３６は、全結合型ニューラルネットワークの各層の計算を繰り返し実行するためのシーケンス制御を行う。
【００２４】
なお、ＳｐＭＶユニット３０では、疎行列ベクトル積（ＳｐＭＶ）を並列計算するために、疎行列ロードユニット３１、データロードユニット３４、およびＦＭＡアレイ３５を構成するＦＭＡユニットがスレッドに対応してそれぞれ複数存在し、それぞれが並列に接続されている。
【００２５】
次に、ポストプロセスユニット４０の構成について説明する。図３は、本実施の形態１に係るポストプロセスユニット４０の構成を示すブロック図である。ポストプロセスユニット４０は、バイアスロードユニット（Bias  Load  Unit）４１、バイアスを格納するバイアスバッファ（Bias  Buffer）４２、バイアスを加算する処理を行うバイアス加算ユニット（Bias  Add）４３、ＬＵＴ（Look  Up  Table）ロードユニット（LUT  Load  Unit）４４、活性化関数の処理を実行するアクティベーションユニット（Activation）４５、データストアユニット（Data  Store  Unit）４６、コントロールユニット（Control  Unit）４７を含んでいる。
【００２６】
バイアスロードユニット４１は、外部メモリ３００からバイアスパラメータを読み出し、バイアスバッファ４２に格納する。このバイアスバッファ４２は、並列計算に必要なデータ幅に構成されている。バイアス加算ユニット４３は、ＳｐＭＶユニット３０の出力データ列（出力ベクトルの要素）と、バイアスバッファ４２から対応するバイアスパラメータ列を受け取り、バイアスを加算する並列計算を行う。
【００２７】
ＬＵＴロードユニット４４は、活性化関数のアルゴリズム（ＬＵＴ構成とする）を事前に設定する。アクティベーションユニット４５は、バイアス加算ユニット４３からの出力データに対して活性化関数を処理する並列計算を行う。データストアユニット４６は、アクティベーションユニット４５からの出力データ列を受け取り、メモリインターフェース／インターコネクト１０を経由して、データバッファ２０に格納（書き戻す）する。コントロールユニット４７は、全結合型ニューラルネットワークの各層の計算を繰り返し実行するためのシーケンス制御を行う。
【００２８】
なお、ポストプロセスユニット４０では、バイアスを加算する処理および活性化関数の処理を並列計算するために、バイアスロードユニット４１、バイアス加算ユニット４３、ＬＵＴロードユニット４４、アクティベーションユニット４５、およびデータストアユニット４６がスレッドに対応してそれぞれ複数存在し、それぞれが並列に接続されている。
【００２９】
次に、アクセラレータ装置１００において、疎行列ベクトル積を並列計算する場合の疎行列の処理について詳しく説明する。疎行列は、非零要素のみに圧縮したデータ形式で、外部メモリ３００に格納される。本実施の形態では、疎行列の格納形式の一例としてＥＬＬＰＡＣＫ形式を用いる。ＥＬＬＰＡＣＫ形式では、疎行列の非零要素の値のリストと、非零要素の列位置を示す疎行列のインデックスのリストとで疎行列を表す形式である。
【００３０】
ＥＬＬＰＡＣＫ形式で表した疎行列について具体例を示して説明する。図４は、要素の多くが零で構成される疎行列の一例を示す図である。図５は、図４に示した疎行列のＥＬＬＰＡＣＫ形式で表した一例を示す図である。図５に示す要素のうち「＊」で示した要素はパディングを挿入した要素を示している。なお、パディングを挿入した要素の値は任意とする。ＥＬＬＰＡＣＫ形式では、データ（ｄａｔａ）には、疎行列の非零要素の値が格納され、インデックス（ｉｎｄｅｘ）には、非零要素の値の列位置が格納される、例えば、図１に示す０行（ｒｏｗ）目［３，７，０，０］は、非零要素が０列（ｃｏｌｕｍｎ）目と１列目とに存在する。そのため、ＥＬＬＰＡＣＫ形式で表わすと、ｄａｔａ［３，７］でｉｎｄｅｘ［０，１］となる。なお、２行目［１，０，５，９］は、非零要素の値が３つあるので、他の行目にはパディングが挿入されている。
【００３１】
図５に示すＥＬＬＰＡＣＫ形式の疎行列を外部メモリ３００に格納する場合、列優先で格納される。図６は、外部メモリ３００に格納されるＥＬＬＰＡＣＫ形式の疎行列の一例を示す図である。図６に示すｄａｔａでは、疎行列の非零要素の値を１列目、２列目、３列目の順に並べて外部メモリ３００に格納されている。また、図６に示すｉｎｄｅｘでは、非零要素の値の列位置を１列目、２列目、３列目の順に並べて外部メモリ３００に格納されている。
【００３２】
次に、ＥＬＬＰＡＣＫ形式で表した疎行列に対する疎行列ベクトル積（ＳｐＭＶ）の計算処理について説明する。図７は、疎行列ベクトル積（ＳｐＭＶ）の計算処理を行うプログラムの一例を示した図である。図７に示すプログラムでは、Ａを疎行列、ｘとｙとをそれぞれ列ベクトルとした場合に、ｙ＝Ａｘを計算している。疎行列ＡのサイズはＭ行×Ｎ列とし、ＥＬＬＰＡＣＫ形式で表した疎行列ＡのサイズはＭ行×Ｋ（≦Ｎ）列となる。なお、パディングで挿入する値は、計算に影響を与えない値（零）とし、疎行列ベクトル積（ＳｐＭＶ）での計算で処理をスキップさせる。また、図７に示すプログラムは、図１に示すＳｐＭＶユニット３０で実行される。
【００３３】
本実施の形態では、複数のデータに対して同じ処理を適用するＳＩＭＤ（Single  Instruction  Multiple  Data）方式で、疎行列ベクトル積（ＳｐＭＶ）の並列計算を行ってもよい。このＳＩＭＤ方式では、複数のスレッド間で並列計算を行う際に、並列計算に必要なデータ幅で構成された実行機構を共有することができる。そのため、ＳｐＭＶユニット３０にＳＩＭＤ方式を採用することで、スレッドごとに機構を実装する方式に比べて、少ないハードウェア資源で疎行列ベクトル積（ＳｐＭＶ）の並列計算を実現することができる。
【００３４】
さらに、本実施の形態では、図７に示したプログラムを疎行列の行（ｒｏｗ）ごとに展開できるようなループ形式のプログラムを構成している。図８は、疎行列の行ごとの疎行列ベクトル積（ＳｐＭＶ）の計算処理を行うプログラムの一例を示した図である。図８に示す疎行列ベクトル積のプログラムを、疎行列の行ごと複数のスレッドとして並列実行することで、疎行列ベクトル積（ＳｐＭＶ）の並列計算を実現することができる。図９は、図８に示すプログラムを、疎行列の行ごと複数のスレッドとして並列実行する場合の一例を示す図である。ＳｐＭＶユニット３０は、ＳＩＭＤ方式を採用した場合、図８に示すプログラムを図９に示す方式で並列実行することで実現することができ、複数のデータに対して同じプログラムを適用する。
【００３５】
本実施の形態では、疎行列を格納する外部メモリ３００、入力データ（入力ベクトル）および出力データ（出力ベクトル）を格納するデータバッファ２０のそれぞれが、共有メモリ方式としスレッド間で同じメモリをアクセスする。なお、疎行列のインデックスのリストを格納するインデックスバッファ３２、疎行列の非零要素の値のリストを格納するバリューバッファ３３のそれぞれも共有メモリ方式である。
【００３６】
外部メモリ３００から疎行列を読み出す場合、疎行列ロードユニット３１は、スレッド間で連続する要素を並列アクセスすることができる。また、データバッファ２０から出力ベクトルを読み出す場合、データロードユニット３４は、スレッド間で連続する要素を並列アクセスすることができる。しかし、データバッファ２０から入力ベクトルを読み出す場合、データロードユニット３４は、インデックスバッファ３２に格納した疎行列のインデックスのリストで間接参照して、スレッド間で不連続な要素を並列アクセスすることになる。
【００３７】
具体例を示して説明する。図１０は、疎行列のインデックスのリストの一例を示す図である。図１１は、図１０に示す疎行列のインデックスのリストに基づいて入力ベクトルの要素にアクセスする順序の一例を示す図である。データロードユニット３４は、図１０に示すｉｎｄｅｘの０列目の［４，６，２，９］を１回目の繰り返し処理（Iteration1）で読み出し、ｉｎｄｅｘの１列目の［１３，１０，７，１３］を２回目の繰り返し処理（Iteration2）で読み出す（図１１）。
【００３８】
しかし、ＳｐＭＶユニット３０が、ＳＩＭＤ方式を採用した場合、並列実行するスレッド間でメモリアクセスの機構や演算器などの実行機構が共有される。そのため、データロードユニット３４は、データバッファ２０から入力ベクトルを読み出す場合、並列計算に必要なデータ幅でメモリへのアクセスが構成され、スレッド間で連続するデータ列を並列にアクセスすることになる。
【００３９】
データロードユニット３４は、スレッド間で不連続なデータ（要素）を並列アクセスするときに、メモリアクセスのデータ幅に不連続なデータ（要素）が収まらない場合がある。この場合、データロードユニット３４は、メモリアクセスを複数回繰り返して、不連続なデータ（要素）を連続するデータ列に寄せ集める機構（Gather機構）が必要となる。
【００４０】
ここで、疎行列は、ＥＬＬＰＡＣＫ形式などにより一定の割合で要素の削減が行われる。これにより、疎行列の非零要素はある間隔で並び、またスレッド間で並列アクセスする非零要素は、ある範囲のデータ幅に収まる確率が高い。この間隔と範囲とは、例えば、非零要素間距離の平均と標準偏差の倍数としてもよい。図１０示す例では、疎行列の非零要素は４要素の間隔で並び、スレッド間で並列アクセスする非零要素は６要素の範囲のデータ幅に収まっている。
【００４１】
そこで、データロードユニット３４は、不連続なデータ（要素）を連続するデータ列に寄せ集める機構（Gather機構）が必要となる。データロードユニット３４は、当該機構により、この間隔をメモリアクセスのストライド幅と、この範囲をメモリアクセスのデータ幅としてデータバッファ２０に対してスレッド間で並列アクセスすることができるようになる。
【００４２】
しかし、ＳｐＭＶユニット３０では、例えばデータロードユニット３４によりスレッド間で並列アクセスする入力ベクトルの複数の要素が、１回のメモリアクセスのデータ幅に収まるように、疎行列のインデックスのリストに対してパディングを挿入することができる。ＳｐＭＶユニット３０で疎行列のインデックスのリストに対してパディングを挿入することで、データロードユニット３４において寄せ集める機構（Gather機構）を不要にできる。具体的に、ＳｐＭＶユニット３０では、疎行列のインデックスの各列に含まれるパディングを挿入した要素の数が平準化するようにパディングを挿入する。つまり、ＳｐＭＶユニット３０は、例えば、疎行列ロードユニット３１で疎行列のインデックスのリストに対してパディングを挿入する。
【００４３】
疎行列ロードユニット３１は、外部メモリ３００から疎行列の非零要素を読み出し、疎行列のインデックスの各列に含まれるパディングの要素の数が平準化するようにパディングを挿入して、疎行列のインデックスのリストを生成してインデックスバッファ３２に格納する。疎行列ロードユニット３１は、パディングを挿入する挿入部として機能している。図１０に示す疎行列のインデックスのリストに対して、各列に含まれるパディングの要素の数が平準化するようにパディングを挿入した例を説明する。図１２は、図１０に示す疎行列のインデックスのリストに対してパディングを平準化して挿入した一例を示す図である。図１２に示す例では、疎行列のインデックスの各列がメモリアクセスの４要素のストライド幅、８要素のデータ幅に収まるように、パディングを平準化して挿入している。
【００４４】
図１２に示すｉｎｄｅｘの０列目の［４，６，２，＊］を１回目の繰り返し処理（Iteration1）で読み出し、ｉｎｄｅｘの１列目の［＊，１０，７，１３］を２回目の繰り返し処理（Iteration2）で読み出す。そのため、データロードユニット３４は、１回目の繰り返し処理（Iteration1）で０番目〜７番目までの８要素のデータ幅に対してメモリアクセスを行い、２回目の繰り返し処理（Iteration2）で４番目〜１１番目までの８要素のデータ幅に対してメモリアクセスを行うことになる。つまり、データロードユニット３４は、メモリアクセスを複数回繰り返す必要がなく、不連続なデータ（要素）を連続するデータ列に寄せ集める機構（Gather機構）も必要ない。
【００４５】
次に、疎行列ロードユニット３１で疎行列のインデックスのリストに対してパディングを平準化して挿入する手順について説明する。図１３は、疎行列のインデックスのリストに対してパディングを平準化して挿入する手順について示すフローチャートである。
【００４６】
まず、疎行列ロードユニット３１は、ＥＬＬＰＡＣＫ形式の疎行列の１列目から順に、全ての列に対して以下の処理を繰り返す（ステップＳ１）。疎行列ロードユニット３１は、列に含まれる要素の中で最小のインデックスを求める（ステップＳ２）。次に、疎行列ロードユニット３１は、ストライド幅のメモリ領域をメモリブロック、データ幅のメモリブロックをウィンドウとして、ステップＳ２で求めた最小のインデックスが含まれるメモリブロックから始まるウィンドウの範囲を求める（ステップＳ３）。
【００４７】
疎行列ロードユニット３１は、ウィンドウの範囲外の要素に対して、対応する行に１列分のパディングを挿入する（ステップＳ４）。例えば、図１１に示す例では、１回目の繰り返し処理（Iteration1）で０番目〜７番目までの８要素のデータ幅をウィンドウの範囲とすると、疎行列のインデックスの９番目はウィンドウの範囲外となるのでパディングを挿入する。疎行列のインデックスの９番目に対応する行に１列分のパディングを挿入すると、図１２に示す１回目の繰り返し処理（Iteration1）のようになる。疎行列ロードユニット３１は、１列の処理が終わった場合、次の列に対して処理を繰り返す（ステップＳ５）。
【００４８】
次に、データバッファ２０のメモリ構成について説明する。図１４は、本実施の形態１に係るデータバッファ２０のメモリ構成を示すブロック図である。図１４に示すデータバッファ２０では、データ数が２５６のバッファの構成例であり、１つのメモリバンクを３２行×４列（４要素のデータ幅）のメモリで構成し、２つのメモリバンクで１つのバッファを構成している。
【００４９】
１つのメモリバンクのデータ幅は、メモリアクセスのストライド幅に相当し、全てのメモリバンクを合わせたデータ幅は、メモリアクセスのデータ幅に相当する。図１４に示す例では、メモリアクセスのストライド幅は４、データ幅は２×４となる。
【００５０】
データロードユニット３４は、図１４に示すデータバッファにアクセスする場合、８ビットのインデックスでアクセスを行う。図１５は、図１４に示すデータバッファにアクセスするためのインデックスの一例を示す図である。図１５に示すインデックスでは、データの行を５ビットで、メモリバンクを１ビットで、データの列を２ビットでそれぞれ表している。
【００５１】
次に、図１４に示すデータバッファに対して複数のインデックスで並列アクセスするロードユニットの構成について説明する。図１６は、本実施の形態１に係るロードユニットの構成を示すブロック図である。
【００５２】
図１６に示すロードユニットでは、２つのメモリバンクごとのアドレスを生成するアドレスコアレスユニット（アドレス生成部）３４ａと、２つのメモリバンクからの出力データを選択するデータクロスバ（データ出力部）３４ｂとを含んでいる。
【００５３】
アドレスコアレスユニット３４ａは、並列アクセスの複数のインデックスからメモリバンクごとに行（ｒｏｗ）インデックスを融合し、メモリバンクごとのアドレスを生成する。並列アクセスの複数のインデックスは、同一のメモリアクセスの範囲に制限されているため、メモリバンクごとのアドレス（行インデックス）は１つに決まる。
【００５４】
データクロスバ３４ｂは、並列アクセスの複数のインデックスごとに、図１５に示すメモリバンクインデックスでメモリバンクを選択し、列（ｃｏｌｕｍｎ）インデックスでメモリバンクからの出力データを選択する。
【００５５】
以上のように、本実施の形態１に係るアクセラレータ装置１００は、疎行列ベクトル積の計算を含む演算処理を実行するアクセラレータ装置である。アクセラレータ装置１００は、疎行列の非零要素の各々と入力ベクトルの要素の各々との積和を含む出力ベクトルの要素の各々の計算処理を並列に実行するＳｐＭＶユニット３０と、疎行列の非零要素の各々、入力ベクトルの要素の各々、および出力ベクトルの要素の各々を格納するデータバッファ２０とを備えている。ＳｐＭＶユニット３０部は、データロードユニット３４と、ＦＭＡアレイ３５と、疎行列ロードユニット３１（挿入部）とを有する。データロードユニット３４は、データバッファ２０に記憶している要素の各々に対して並列にアクセスすることができる。ＦＭＡアレイ３５は、データロードユニット３４がアクセスした入力ベクトルの要素の各々と、疎行列の非零要素の各々との積和（融合積和）を計算する。疎行列ロードユニット３１は、データロードユニット３４がデータバッファ２０に記憶している入力ベクトルの要素の各々に対して並列にアクセスする順序に従い、疎行列の非零要素の各々の配置にパディングを挿入する。
【００５６】
これにより、本実施の形態１に係るアクセラレータ装置１００では、記憶部に記憶している入力ベクトルの要素の各々に対して並列にアクセスする順序に従い、疎行列の非零要素の各々の配置にパディングを挿入することで、不連続なデータ（要素）を連続するデータ列に寄せ集める機構が不要で、ハードウェア資源を削減することができる。
【００５７】
疎行列ロードユニット３１は、入力ベクトルの要素の各々に対して並列にアクセスする順序において、予め定められたストライド幅とデータ幅とで規定されるアクセス単位で並列にアクセスする場合、アクセス単位に含まれない疎行列の非零要素の配置に対して前記パディングを挿入する。これにより、ＳｐＭＶユニット３０では、疎行列のインデックスの各列に含まれるパディングを挿入した要素の数が平準化してパディングを挿入することができる。
【００５８】
データロードユニット３４は、入力ベクトルの要素の各々に対して並列にアクセスする場合に、メモリバンクごとにアクセスするアドレスを生成するアドレスコアレスユニット３４ａと、アドレスコアレスユニット３４ａで生成したアドレスに対応するメモリバンクからの出力データを選択するデータクロスバ３４ｂとを有してもよい。これにより、データバッファ２０に対して複数のインデックスで並列アクセスするデータロードユニット３４を構成することができる。
【００５９】
データロードユニット３４は、アクセス単位のストライド幅を１つのメモリバンクが有するデータの列数とし、アクセス単位のデータ幅を全てのメモリバンクが有するデータの列数の合計数としてもよい。これにより、データロードユニット３４は、データバッファ２０に対してメモリバンクの粒度でアクセスすることができる。
【００６０】
アクセラレータ装置１００は、ＦＰＧＡで構成されてもよい。これにより、アクセラレータ装置１００のコストを低減することができる。
【００６１】
なお、パディングを平準化して挿入する挿入部の例として、疎行列ロードユニット３１を説明したが、疎行列ロードユニット３１以外に、別途挿入部を設けてもよい。
【００６２】
（実施の形態２）
実施の形態１に係るアクセラレータ装置１００では、１つのメモリバンクを３２行×４列（４要素のデータ幅）のメモリで構成し、２つのメモリバンクで１つのバッファを構成している例を説明した。データバッファ２０は、メモリバンクの粒度でアクセスを行うため、疎行列の非零要素の構造により不要なメモリアクセスが発生することになる。
【００６３】
メモリアクセスの粒度を細かくする場合、メモリバンクのデータ幅がメモリアクセスのストライド幅を等分したサイズとし、メモリバンクの総数はメモリアクセスのデータ幅に合わせる必要がある。本実施の形態２に係るアクセラレータ装置では、メモリアクセスの粒度を細かくした場合について説明する。なお、本実施の形態２に係るアクセラレータ装置では、実施の形態１に係るアクセラレータ装置１００とデータバッファの構成を除いて同じ構成であり、詳細な説明は繰り返さない。
【００６４】
本実施の形態２に係るデータバッファのメモリ構成について説明する。図１７は、本実施の形態２に係るデータバッファのメモリ構成を示すブロック図である。図１７に示すデータバッファでは、データ数が２５６のバッファの構成例であり、１つのメモリバンクを３２行×２列（２要素のデータ幅）のメモリで構成し、４つのメモリバンクで１つのバッファを構成している。
【００６５】
１つのメモリバンクのデータ幅は、メモリアクセスのストライド幅に相当し、全てのメモリバンクを合わせたデータ幅は、メモリアクセスのデータ幅に相当する。図１７に示す例では、メモリアクセスのストライド幅は２、データ幅は４×２となる。
【００６６】
データロードユニット３４は、図１７に示すデータバッファにアクセスする場合、８ビットのインデックスでアクセスを行う。図１８は、図１７に示すデータバッファにアクセスするためのインデックスの一例を示す図である。図１８に示すインデックスでは、データの行を５ビットで、メモリバンクを２ビットで、データの列を１ビットでそれぞれ表している。
【００６７】
次に、図１７に示すデータバッファに対して複数のインデックスで並列アクセスするロードユニットの構成について説明する。図１９は、本実施の形態２に係るロードユニットの構成を示すブロック図である。
【００６８】
図１９に示すロードユニットでは、４つのメモリバンクごとのアドレスを生成するアドレスコアレスユニット（アドレス生成部）３４ｃと、４つのメモリバンクからの出力データを選択するデータクロスバ（データ出力部）３４ｄとを含んでいる。
【００６９】
アドレスコアレスユニット３４ｃは、並列アクセスの複数のインデックスからメモリバンクごとに行（ｒｏｗ）インデックスを融合し、メモリバンクごとのアドレスを生成する。並列アクセスの複数のインデックスは、同一のメモリアクセスの範囲に制限されているため、メモリバンクごとのアドレス（行インデックス）は１つに決まる。
【００７０】
データクロスバ３４ｄは、並列アクセスの複数のインデックスごとに、図１８に示すメモリバンクインデックスでメモリバンクを選択し、列（ｃｏｌｕｍｎ）インデックスでメモリバンクからの出力データを選択する。
【００７１】
図１７に示したようにメモリアクセスの粒度を細かくすると、メモリバンク数が増加してハードウェア構成が複雑になる。一方、スレッドの並列数を増やすと、メモリアクセスが均一化することで、不要なメモリアクセスが低減されるが、並列計算に必要となるメモリ帯域幅が増える。これらから、メモリアクセスの粒度（メモリバンクの数）は、疎行列の非零要素構造とスレッドの並列数とのトレードオフで決めることになる。
【００７２】
以上のように、本実施の形態２に係るアクセラレータ装置では、データロードユニット３４が、メモリバンクの数を変更することができる。これにより、本実施の形態２に係るアクセラレータ装置では、疎行列の非零要素構造とスレッドの並列数とのバランスを考慮してメモリバンクの数を決定することができる。
【００７３】
なお、以上の実施の形態１，２において、処理可能なスレッド数が疎行列の行数よりも少ない場合（処理可能なスレッド数＜疎行列の行数）、疎行列の行をスレッド数で分割して、上述した処理を繰り返し実行することになる。
【００７４】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した実施の形態ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【００７５】
１０  メモリインターフェース／インターコネクト、２０  データバッファ、３０  ＳｐＭＶユニット、３１  行疎列ロードユニット、３２  インデックスバッファ、３３  バリューバッファ、３４  データロードユニット、３４ａ，３４ｃ  アドレスコアレスユニット、３４ｂ，３４ｄ  データクロスバ、３５  ＦＭＡアレイ、３６，４７  コントロールユニット、４０  ポストプロセスユニット、４１  バイアスロードユニット、４２  バイアスバッファ、４３  バイアス加算ユニット、４４  ロードユニット、４５  アクティベーションユニット、４６  データストアユニット、１００  アクセラレータ装置、２００  システムバス、３００  外部メモリ。
【図１】
2020166368.tif 000003
【図２】
2020166368.tif 000004
【図３】
2020166368.tif 000005
【図４】
2020166368.tif 000006
【図５】
2020166368.tif 000007
【図６】
2020166368.tif 000008
【図７】
2020166368.tif 000009
【図８】
2020166368.tif 000010
【図９】
2020166368.tif 000011
【図１０】
2020166368.tif 000012
【図１１】
2020166368.tif 000013
【図１２】
2020166368.tif 000014
【図１３】
2020166368.tif 000015
【図１４】
2020166368.tif 000016
【図１５】
2020166368.tif 000017
【図１６】
2020166368.tif 000018
【図１７】
2020166368.tif 000019
【図１８】
2020166368.tif 000020
【図１９】
2020166368.tif 000021