(57)【要約】  一実施形態において、畳み込みニューラルネットワークにおける畳み込み層の演算方法が提供される。演算方法は、畳み込み層に入力される特徴マップを一列に展開することによって得られる入力ベクトル（ｘ）に対応するように、畳み込み層で使用されるカーネルを変換することによって係数行列（Ａ）を生成するステップと、係数行列に含まれる非零要素を検索するステップと、係数行列に含まれる各非零要素と入力ベクトルの対応する要素との乗算を処理単位として、互いに並列処理可能な複数の演算器（ＣＬ）の各々での処理単位数が平準化するように、当該乗算を各演算器に割り当てるステップと、各演算器が割当てられた乗算を順次実行し、乗算の結果を出力ベクトル（ｆ）の対応する要素に積算するステップとを備える。
2019053835.tif 000002
【特許請求の範囲】
【請求項１】
非零要素と零要素とを含む係数行列に右から入力ベクトルを掛け、演算結果を出力ベクトルに出力するための演算回路であって、制御プロセッサと、互いに並列処理可能な複数の演算器とを備え、
前記制御プロセッサは、前記係数行列に含まれる各非零要素と前記入力ベクトルの対応する要素との乗算を処理単位として、各前記演算器での処理単位数が平準化するように当該乗算を各前記演算器に割り当てるように構成され、
各前記演算器は、割り当てられた前記乗算を順次実行し、前記乗算の結果を前記出力ベクトルの対応する要素に積算するように構成される、演算回路。
【請求項２】
前記演算回路は、畳み込みニューラルネットワークにおける畳み込み層の演算を実行するためのものであり、
前記入力ベクトルは、前記畳み込み層に入力される特徴マップを一列に展開したものであり、
前記係数行列は、前記畳み込み層で利用されるカーネルに対応する、請求項１に記載の演算回路。
【請求項３】
前記係数行列に含まれる非零要素のみを取り出して格納するための係数ベクトルをさらに備え、
各前記演算器は、前記係数ベクトルから取り出した対応の非零要素を使用することによって、前記乗算を実行するように構成される、請求項１または２に記載の演算回路。
【請求項４】
畳み込みニューラルネットワークにおける畳み込み層の演算方法であって、
前記畳み込み層に入力される特徴マップを一列に展開することによって得られる入力ベクトルに対応するように、前記畳み込み層で使用されるカーネルを変換することによって係数行列を生成するステップと、
前記係数行列に含まれる非零要素を検索するステップと、
前記係数行列に含まれる各非零要素と前記入力ベクトルの対応する要素との乗算を処理単位とし、互いに並列処理可能な複数の演算器の各々での処理単位数が平準化するように、当該乗算を各前記演算器に割り当てるステップと、
各前記演算器が割当てられた前記乗算を順次実行し、前記乗算の結果を出力ベクトルの対応する要素に積算するステップとを備える、演算方法。
【請求項５】
前記出力ベクトルの初期値としてバイアスベクトルを入力するステップをさらに備える、請求項４に記載の演算方法。
【請求項６】
前記係数行列に含まれる非零要素のみを取り出して係数ベクトルに格納するステップをさらに備え、
各前記演算器は、前記係数ベクトルから取り出した対応の非零要素を使用することによって、前記乗算を実行する、請求項４または５に記載の演算方法。
【請求項７】
請求項４〜６のいずれか１項に記載の演算方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、演算回路、演算方法、およびこの演算方法を実行するためのプログラムに関し、たとえば、畳み込みニューラルネットワークにおける畳み込み層の演算において好適に用いられる。
【背景技術】
【０００２】
パターン認識等の画像処理、声紋分析、ロボディクスなどの多くの分野において、畳み込みニューラルネットワーク（ＣＮＮ：Convolutional  Neural  Network）と呼ばれる演算方法がしばしば用いられる。一般にＣＮＮは、畳み込み演算を行う畳み込み層、局所統計量を計算するプーリング層、および全結合層で構成される。畳み込み層は、カーネル（フィルタとも称する）を入力特徴マップ上において画素単位で走査させながら、入力特徴マップの対応部分とカーネルとの積和演算を繰り返して行い、最終的な積和演算結果を非線形変換することによって出力特徴マップを生成する。【０００３】
特開２０１０−１３４６９７号公報（特許文献１）は、畳み込み演算を並列処理で実行するための演算回路を開示する。具体的に、この文献に記載された演算回路は、カーネルの列方向サイズの個数分の乗算器および累積加算器を用いて並列演算を行う。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−１３４６９７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記の特許文献に記載の演算回路では、特徴マップおよびカーネルをそのまま使用して演算しているために演算の繰り返し回数が増えて処理が遅くなるという問題がある。【０００６】
そこで、処理時間の短縮のために、特徴マップまたはカーネルを１列に展開してから演算する方法がしばしば用いられる。この方法によれば、畳み込み演算は、係数行列とベクトルとの積、すなわち係数行列の各行の要素とベクトルの要素との積和演算に帰着する。たとえば、係数行列の行数分の積和演算器によって並列演算を行うことができる。【０００７】
ここで、各積和演算器によって単純に積和演算器を実行すると、係数行列の要素に０が含まれている場合には、無駄な演算に時間を費やすことになることに注意しなければならい。したがって、通常は、係数行列のうち０の要素を除いて積和演算器による演算を実行する方法が採られる。ところが、非零要素の数は係数行列の行により異なるので、係数行列全体として非零要素の数が少なくても、最も多い行の非零要素の数で全体の処理時間が決定される。このため、非零要素の多い行が１行でもあれば、その行での積和演算に全体の処理時間が律速され、結果として全体の処理時間を思うほど短縮できないことになる。【０００８】
この開示は、上記の問題を考慮したものであり、その目的は、要素に０を含む係数行列とベクトルとの掛け算を行う際に全体の処理時間を短縮することが可能な演算回路および演算方法を提供することである。なお、この開示による演算回路および演算方法は、ＣＮＮにおける畳み込み演算において好適に用いられるものであるが、ＣＮＮに限らず他の分野にも適用することができる。
【課題を解決するための手段】
【０００９】
一実施形態における演算回路は、非零要素と零要素とを含む係数行列に右から入力ベクトルを掛け、演算結果を出力ベクトルに出力するためのものである。演算回路は、制御プロセッサと、互いに並列処理可能な複数の演算器とを備える。制御プロセッサは、係数行列に含まれる各非零要素と入力ベクトルの対応する要素との乗算を処理単位とし、各演算器での処理単位数が平準化するように当該乗算を各演算器に割り当てる。各演算器は、割り当てられた乗算を順次実行し、乗算の結果を出力ベクトルの対応する要素に積算する。
【発明の効果】
【００１０】
上記の実施形態によれば、係数行列に含まれる各非零要素と入力ベクトルの対応する要素との乗算を処理単位とし、各演算器での処理単位数が平準化するように当該乗算を各演算器に割り当てるので、全体の処理時間を短縮することができる。
【図面の簡単な説明】
【００１１】
【図１】ＣＮＮによる演算処理を示すフローチャートである。
【図２】畳み込み演算について説明するための図である。
【図３】特徴マップおよびカーネルの展開について説明するための図である。
【図４】並列計算機の構成の一例を示すブロック図である。
【図５】畳み込み演算の手順の概要を示すフローチャートである。
【図６】畳み込み演算の手順の詳細を示すフローチャートである。
【図７】図４の並列計算機の各演算器における単位積和演算の実行手順の一例を示すフローチャートである。
【図８】実施の形態１の効果を説明するための図である。
【図９】実施の形態２による畳み込み演算の手順を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、各実施の形態について図面を参照して詳しく説明する。なお、同一または相当する部分には同一の参照符号を付して、その説明を繰り返さない。
【００１３】
実施の形態１．
［ＣＮＮについて］
最初にＣＮＮについて簡単に説明する。図１は、ＣＮＮによる演算処理を示すフローチャートである。
【００１４】
図１を参照して、ＣＮＮは、入力層Ｓ２０１と、畳み込み層Ｓ２０２，Ｓ２０４と、プーリング層Ｓ２０３，Ｓ２０５と、全結合層Ｓ２０６と、出力層Ｓ２０７とを含む。
【００１５】
入力層Ｓ２０１は、画像データなどの処理対象のデータの入力を受ける。出力層Ｓ２０７は、データ処理後の最終結果を出力する。図１では、簡単のために畳み込み層とプーリング層の組み合わせ（Ｓ２０２，Ｓ２０３；Ｓ２０４，Ｓ２０５）が２回繰り返されているが、さらに多数回繰り返されていてもよい。
【００１６】
畳み込み層に入力されるデータを入力特徴マップといい、畳み込み層から出力されたデータを出力特徴マップという。畳み込み層Ｓ２０２，Ｓ２０４は、カーネル（フィルタとも称する）を入力特徴マップ上において画素単位で走査しながら、入力特徴マップの対応部分とカーネルとの積和演算を繰り返して行い、最終的な積和演算結果を非線形変換することによって出力特徴マップを生成する。カーネルの要素（「重み」とも称する）は事前に学習によって決定される。畳み込み演算の詳細は図２を参照して後述する。
【００１７】
プーリング層Ｓ２０３，Ｓ２０５は、出力特徴マップの局所領域をひとつの要素にまとめるような動作を行うことによって特徴マップの空間サイズを小さくするものである。プーリング層Ｓ２０３，Ｓ２０５は、たとえば、局所領域の最大値を取ったり、局所領域に含まれる要素を平均化したりする。
【００１８】
全結合層Ｓ２０６は、出力層Ｓ２０７に隣接して１または複数層設けられる。全結合層のＳ２０６の各ニューロンは、隣接層の全てのニューロンとの結合を有する。
【００１９】
［畳み込み演算について］
図２は、畳み込み演算について説明するための図である。図２に示すように、入力特徴マップとしての入力データ１００とカーネル１０１との畳み込み演算によって出力データ１０２が生成される。出力データ１０２の各要素にバイアスを加算し、さらに活性化関数を施すことによって出力特徴マップが生成される。活性化関数として、たとえば、ＲｅＬＵ（Rectified  Linear  Unit）などの非線形関数が用いられる。
【００２０】
図２の例では、簡単のために入力データサイズを（７，７）とし、カーネルサイズを（３，３）としている。出力データサイズの調整のために、入力データ１００の周囲１０４が固定データ（たとえば、０）で埋められていてもよい。これをパッディングと称する。図２の入力データ１００には、幅が１で値が０のパディングが適用されている。
【００２１】
畳み込み演算では、パディングの部分を含めた入力データ１００の上においてカーネル１０１を一定間隔でスライドさせながら、カーネル１０１の要素と対応する入力データ１００の要素とを乗算し、それらの和が求められる。すなわち、積和演算が実行される。積和演算の結果は、出力データ１０２の対応する要素に格納される。カーネル１０１をスライドさせる間隔をストライドと称する。図２の場合、ストライドは１である。
【００２２】
具体的に、カーネル１０１の配置が図２の太い実線の枠１０３に対応している場合、積和演算結果である「３０」は出力データ１０２の対応する要素１０６の位置に格納される。カーネル１０１の配置が図２の太い破線の枠１０５に対応している場合、積和演算結果である「１３」は、出力データ１０２の対応する要素１０７の位置に格納される。
【００２３】
［特徴マップおよびカーネルの展開］
図３は、特徴マップおよびカーネルの展開について説明するための図である。本実施の形態の場合、畳み込み演算の処理時間を短縮するために、特徴マップの各行をつなぎ合わせることによって特徴マップが１列に展開される。
【００２４】
具体的に、図２および図３を参照して、図２の入力データ１００の各行をつなぎ合わせることによって図３の入力ベクトル１１０が生成される。入力データ１００に対応する入力ベクトル１１０の要素数は７×７＝４９である。図２の出力データ１０２も行ごとにつなぎ合わせることによって１列に展開される。出力データ１０２に対応する出力ベクトルの要素数も４９である。
【００２５】
図２のカーネル１０１は、入力ベクトル１１０を右から掛けたときに、図２の出力データ１０２に対応する出力ベクトルが生成されるように行列に展開される。これによって係数行列１１１が生成される。係数行列１１１の行数は第１行から第４９行までの４９であり、係数行列１１１の列数は第１列から第４９列までの４９である。なお、図３に示す係数行列１１１において空白部分のマス目の要素は０である。
【００２６】
具体的に、係数行列１１１の第１行は、（３，２，０，０，０，０，０，１，３，０，…，０）であり、図２のカーネル１０１が特徴マップ１００上の太い破線の枠１０５に位置する場合に相当する。この係数行列１１１の第１行と入力ベクトル１１０との積和演算が実行されることによって、図２の出力データ１０２の対応する要素１０７の位置に格納されるデータ「１３」が生成される。
【００２７】
同様に、係数行列１１１の第９行は、（３，２，１，０，０，０，０，１，３，２，０，０，０，０，２，１，３，０，…，０）であり、図２のカーネル１０１が特徴マップ１００上の太い実線の枠１０３に位置する場合に相当する。この係数行列１１１の第９行と入力ベクトル１１０との積和演算が実行されることによって、図２の出力データ１０２の対応する要素１０６に位置に格納されるデータ「３０」が生成される。
【００２８】
図２においてパディングが適用されていない場合には、入力データ１００に対応する入力ベクトル１１０には変更はなく、その要素数は４９である。出力データ１０２のデータサイズは（５，５）になるので、出力データ１０２に対応する出力ベクトルの要素数は、５×５＝２５になる。また、カーネル１０１に対応する係数行列１１１の行数は２５になり、その列数は４９になる。
【００２９】
畳み込み演算において実行される行列演算式は一般に（１）式で表される。すなわち、畳み込み演算の出力ベクトルｆは、係数行列Ａに入力ベクトルｘを右から掛け、その演算結果にバイアスベクトルｂを加算することによって得られる。ここで、係数行列Ａは、値が０である要素を比較的多く含んでいる点に特徴がある。
【００３０】
【数１】
2019053835.tif 000003
【００３１】
この明細書では、出力ベクトルｆの要素をｆ1，…，ｆnとする。第ｉ番目の出力ベクトルｆの要素をｆiまたはｆ（ｉ）と記載する。入力ベクトルｘの要素をｘ1，…，ｘmとする。第ｊ番目の入力ベクトルｘの要素をｘjまたはｘ（ｊ）と記載する。バイアスベクトルｂの要素をｂ1，…，ｂnとする。第ｉ番目のバイアスベクトルｂの要素をｂiまたはｂ（ｉ）と記載する。また、係数行列Ａは、第１から第ｎまでのｎ行と第１から第ｍまでのｍ行で構成される。第ｉ行第ｊ列の係数行列Ａの要素をＡijまたはＡ（ｉ，ｊ）と記載する。
【００３２】
［並列計算機の構成］
上記（１）式で示される行列演算は、複数の演算器を含む並列計算機によって実行することができる。以下、汎用的な並列計算機の構成例を示す。図４の例と異なり、互いに並列処理可能な演算器を複数備えたＡＳＩＣ（Application  Specific  Integrated  Circuit）によって上記の（１）式で示される行列演算を実行してもよい。
【００３３】
図４は、並列計算機の構成の一例を示すブロック図である。図４を参照して、並列計算機１２０は、各々が複数個の演算器ＣＬ０，ＣＬ１，…を含む複数の処理ユニット１２１Ａ，１２１Ｂ，…と、Ｌ２キャッシュメモリ（Level  2  Cache  Memory）１２５と、専用メモリ１２６とを備える。
【００３４】
各処理ユニット１２１（１２１Ａ，１２１Ｂ，…）は、複数の演算器ＣＬ０，ＣＬ１，…と、それぞれの演算器に対応するレジスタ群Ｒ０，Ｒ１，…と、Ｌ１キャッシュメモリ（Level  1  Cache  Memory）１２２とを含む。同じ処理ユニット１２１に含まれる演算器ＣＬ（ＣＬ０，ＣＬ１，…）は、Ｌ１キャッシュメモリ１２２を共有する。
【００３５】
上記の構成において、複数の処理ユニット１２１Ａ，１２１Ｂ，…は互いに並列的にプログラムを実行可能である。さらに、各処理ユニット１２１の複数の演算器ＣＬ０，ＣＬ１，…は互いに並列的にプログラムを実行可能である。なお、プログラムは、ネットワークを介して提供されてもよいし、磁気的または光学的な方法または半導体メモリなどを使用することによりプログラムを非一時的に記憶する記憶媒体によって提供されてもよい。
【００３６】
並列計算機１２０は、プログラム全体を制御するＣＰＵ（Central  Processing  Unit）１３０と高速インターフェイスを介して接続されていてもよい。この場合、ＣＰＵ１３０用のメモリ１３１と、並列計算機１２０の専用メモリ１２６との間でダイレクトメモリアクセスによってデータ転送できるようにしてもよい。図４の構成と異なり、上記の制御用のＣＰＵ１３０およびメモリ１３１は、並列計算機１２０に内蔵されていてもよい。
【００３７】
［畳み込み演算の手順の概要］
以下、畳み込み演算の手順の概要、特に（１）式の行列演算の手順の概略について説明する。
【００３８】
図５は、畳み込み演算の手順の概要を示すフローチャートである。畳み込み演算に用いるカーネルの各要素は既に学習済みであるとする。図５に示すように、畳み込み演算処理は、最初に１回のみ行われる前処理Ｓ５００と、入力データに応じて繰り返される積和演算Ｓ５１０とに区分できる。前処理は、汎用のＣＰＵ（たとえば、図４のＣＰＵ１３０）によって実行することができる。一方、積和演算は、たとえば、図４の並列計算機１２０によって主として実行され、その全体的な制御は例えばＣＰＵ１３０によって実行される。
【００３９】
前処理段階では、まず、ステップＳ５０１において、図２および図３で説明したようにＣＰＵ等のプロセッサは、学習済みのカーネルから係数行列Ａを生成する。生成した係数行列Ａはメモリに格納される。
【００４０】
次のステップＳ５０２において、プロセッサは、係数行列Ａのうちの非零要素を全て検索する。検索結果はメモリに格納される。これによって係数行列Ａに含まれる非零要素の総数が判明する。なお、入力データは、一列に展開されることによって入力ベクトルに変換されることが想定されている。
【００４１】
次のステップＳ５０３において、プロセッサは、検索した各非零要素と入力ベクトルｘの対応する要素との乗算を処理単位とし、並列計算機１２０に備えられた各演算器ＣＬでの処理単位数が平準化するように当該乗算を各演算器ＣＬに割当てる。これによって、各演算器での処理時間をほぼ等しくすることができる。以上で前処理段階が終了する。
【００４２】
次の積和演算では、まず、ステップＳ５１１において、出力ベクトルｆにバイアスベクトルｂが初期値として入力される。なお、バイアスベクトルｂは、積和演算の最後に出力ベクトルｆに加算するようにしてもよい。
【００４３】
次のステップＳ５１２において、並列計算機１２０の各演算器ＣＬは、割り当てられた乗算を順次実行する。各演算器ＣＬは、各乗算結果を出力ベクトルｆの対応する要素において現在格納されている値に加算する。すなわち、乗算結果は、出力ベクトルｆの対応する要素に積算されていくことになる。ステップＳ５１２は、割当てられた乗算が全て終了するまで（ステップＳ５１３でＹＥＳとなるまで）繰り返される。
【００４４】
なお、ステップＳ５１２，Ｓ５１３では、係数行列Ａの各行と入力ベクトルｘとの積和演算が、単位積和演算に分解されて実行されると考えることができる。ここで、単位積和演算は、係数行列Ａの１つの非零要素と入力ベクトルの対応する要素との乗算と、乗算結果の出力ベクトルｆの対応する要素への加算とから構成される。
【００４５】
以下、簡単な具体例を挙げて説明する。たとえば、（１）式の係数行列Ａにおいて、ｎ＝ｍとし、対角要素のみが非零要素であったとする。また、演算器ＣＬの総数はｎ個であったとする。この場合、第ｉ番目（１≦ｉ≦ｎ）の演算器ＣＬは、Ａiiとｘｉとの乗算を行い、乗算結果を出力ベクトルｆの要素ｆiにおいて現在格納されているバイアス値ｂiに加算する。
【００４６】
別の例として、（１）式係数行列Ａにおいて、第１行目の要素Ａ11〜Ａ1ｍのみが非零要素であったとする。また、演算器ＣＬの総数はｍ個であったとする。この場合、第ｉ番目（１≦ｉ≦ｍ）の演算器ＣＬは、Ａ1i・ｘiの演算を行い、演算結果を出力ベクトルｆの第１番目の要素ｆ1において現在格納されている値に加算する。この場合、各演算器ＣＬにおいて加算演算は互いに競合するので排他制御される。たとえば、第１番目の演算器ＣＬは、Ａ11・ｘ1の演算結果を、出力ベクトルｆの要素ｆ1の初期値ｂ1に加算する。この加算演算の終了後に、第２番目の演算器ＣＬは、Ａ12・ｘ2の演算結果を、出力ベクトルｆの要素ｆ1において現在格納されているｂ1＋Ａ11・ｘ1に加算する。以下同様に、加算演算が順次繰り返される。
【００４７】
［畳み込み演算の手順の詳細］
図６は、畳み込み演算の手順の詳細を示すフローチャートである。
【００４８】
図６を参照して、ステップＳ１０１からステップＳ１０８までが、図５のステップＳ５００の前処理に相当する。
【００４９】
まず、ステップＳ１０１において、変数の初期化が行われる。具体的に、プロセッサは、行方向変数ｉおよび列方向変数ｊをともに１に初期化し、非零要素数（すなわち、単位積和演算数）ｋを０に初期化する。
【００５０】
次のステップＳ１０２において、非零要素か否かの判定が実行される。具体的に、プロセッサは、係数行列Ａの要素Ａ（ｉ，ｊ）の値を検査し、その値が０であれば要素Ａ（ｉ，ｊ）は積和演算の非対象要素であるため、行方向変数ｉをカウントアップするためのステップＳ１０５へ処理を進める。一方、要素Ａ（ｉ，ｊ）の値が０でなければ要素Ａ（ｉ，ｊ）は、積和演算の対象要素であるため、プロセッサは、非零要素を格納するためのステップＳ１０３へ処理を進める。
【００５１】
ステップＳ１０３において、検索された非零要素へのポインタが格納される。具体的に、プロセッサは、積和演算の対象要素Ａ（ｉ，ｊ）へのポインタを記憶するため、行番号の格納用配列ＡROW（ｋ）へ行方向変数ｉを、列番号の格納用配列ＡCOL（ｋ）へ列方向変数ｊを格納する。
【００５２】
次のステップＳ１０４において、非零要素数ｋのカウントアップが実行される。具体的に、プロセッサは、非零要素数を表す変数ｋをインクリメントする。
【００５３】
次のステップＳ１０５において、プロセッサは、次の行を検査するため、行方向変数ｉをインクリメントする。
【００５４】
次のステップＳ１０６において、１列分の処理が完了したら次の列へ処理を移行するため、係数行列の１列分の処理が完了したかの判定が実行される。具体的に、プロセッサは、行方向変数ｉと係数行列の行数ｎとを比較することによって、現在の列の処理が完了したか否かを判定する。プロセッサは、行方向変数ｉが行数ｎより大きければ現在の列の処理が完了した判断し、次の列の処理を行うために、列方向変数ｊを更新するためのステップＳ１０７へ処理を進める。一方、プロセッサは、行方向変数ｉが行数ｎより大きくなければまだ現在の列の処置が完了していないと判断し、次の行の処理を行うために非零要素か否かの判定を行うためのステップＳ１０２へ処理を進める。
【００５５】
ステップＳ１０７において、次列の処理のために変数の更新が行われる。具体的に、プロセッサは、次列の１行目から処理を行うために、行方向変数ｉを１に初期化する。さらに、プロセッサは、列方向変数ｊをインクリメントする。
【００５６】
次のステップＳ１０８において、全列の処理が完了したか否かの判定が実行される。具体的に、プロセッサは、全列の処理が完了したか判断するため、列方向変数ｊと係数行列Ａの行数ｍとを比較することによって全行列の処理が完了したか否かを判定する。プロセッサは、列方向変数ｊが列数ｍより大きければ全行列の処理が完了したと判断し、積和演算の変数ｆ（出力ベクトルに対応する）を初期化するためのステップＳ１０９へ処理を進める。一方、プロセッサは、列方向変数ｊが列数ｍより大きくなければ、未処理の列が残っていると判断し、非零要素を判定するためのステップＳ１０２へ処理を進める。
【００５７】
次のステップＳ１０９からステップＳ１１２までが図５の積和演算Ｓ５１０に相当する。これらのステップは、主として図４の並列計算機１２０または並列演算が可能な専用のＡＳＩＣなどによって実行される。
【００５８】
まず、ステップＳ１０９において、積和演算に用いられる各変数の初期化が実行される。具体的に、全体の動作を制御するプロセッサ（たとえば、図４のＣＰＵ１３０）は、行番号および列番号の格納用配列のインデックス変数ｏを０に初期化する。さらに、プロセッサは、積和演算計算を出力する出力ベクトルｆ（１）からｆ（ｎ）をそれぞれバイアスベクトルｂの要素ｂ（１）からｂ（ｎ）に初期化する。
【００５９】
次のステップＳ１１０において、総数ｋ個の単位積和演算がｎ個の積和演算器により順番に実行される。具体的に、行番号の格納用配列ＡROW（ｐ）および列番号の格納用配列ＡCOL（ｐ）を係数行列Ａへのポインタとして利用し、以下の（２）式で示す単位積和演算を第ｐ番目の演算器ＣＬが実行する。
【００６０】
【数２】
2019053835.tif 000004
【００６１】
ここで、ｎ個の演算器により並列に単位積和演算を行うため、上記（２）式の変数ｐはｐ＝ｏからｐ＝ｏ＋ｎ−１までのｎ個の値をとる。さらに非零要素数ｋを超えて積和演算を行わないため、ｐ＜ｋを満たす場合にのみ積和演算が実施される。
【００６２】
次のステップＳ１１１において、積和演算用変数のカウントアップが実行される。具体的に制御用プロセッサは、行番号の格納用配列ＡROW（ｐ）および列番号の格納用配列ＡCOL（ｐ）のインデックス変数ｏを演算器の数ｎだけインクリメントすることによって、次のｎ個の積和演算に備える。
【００６３】
次のステップＳ１１２において、単位積和演算が全て完了したか否かが判定される。具体的に、制御用プロセッサは、行番号および列番号の格納用配列のインデックス変数ｏと非零要素数ｋとを比較することによって、全ての非零要素の積和演算が完了したか否かを判定する。制御用プロセッサは、行番号および列番号の格納用配列のインデックス変数ｏが非零要素数ｋ以上であれば、すべての積和演算が完了したと判定し、積和演算処理を終了する。一方、制御用プロセッサは、行番号および列番号の格納用配列のインデックス変数ｏが非零要素数ｋ以上でなければ、残りの積和演算を行うため、積和演算を行うためのステップＳ１１０へ処理を進める。
【００６４】
なお、上記の演算手順において、係数行列Ａの非零要素の検査を行、列の順に行ったが、列、行の順に行ってもよい。また、演算器ＣＬの総数を行の数ｎに等しくしたが、列の数ｍに等しくしてもよいし、任意の数に設定してもよい。
【００６５】
図７は、図４の並列計算機の各演算器における単位積和演算の実行手順の一例を示すフローチャートである。なお、以下の手順において第１レジスタおよび第２レジスタは、各演算器ＣＬに対応するレジスタ群Ｒに備えられている。
【００６６】
ステップＳ３０１において、各演算器ＣＬは、専用メモリ１２６またはＬ１キャッシュメモリ１２２またはＬ２キャッシュ１２５から、係数行列の対応する要素Ａ（ＡROW（ｐ），ＡCOL（ｐ））を読出して、対応する第１レジスタに格納する。
【００６７】
次のステップＳ３０２において、各演算器ＣＬは、専用メモリ１２６またはＬ１キャッシュメモリ１２２またはＬ２キャッシュ１２５から、入力ベクトルの対応する要素ｘ（ＡCOL（ｐ））を読出して、対応する第２レジスタに格納する。なお、ステップＳ３０２は、ステップＳ３０１と同時に実行してもよいし、ステップＳ３０１の前に実行してもよい。
【００６８】
次のステップＳ３０３において、各演算器ＣＬは、第１レジスタに格納された値と第２レジスタに格納された値とを乗算し、乗算結果をたとえば第１レジスタに格納する。
【００６９】
以降のステップは、出力ベクトルの対応する要素ｆ（ＡROW（ｐ））へのアクセスが可能な場合、すなわち、競合していない場合（ステップＳ３０４でＹＥＳ）に実行される。
【００７０】
まず、ステップＳ３０５において、各演算器ＣＬは、専用メモリ１２６またはＬ１キャッシュメモリ１２２またはＬ２キャッシュ１２５から、ｆ（ＡROW（ｐ））を読出して第２レジスタに格納する。
【００７１】
次のステップＳ３０６において、第１レジスタに格納された値（すなわち、ステップＳ３０３の演算結果）と第２レジスタに格納された値とを加算し、加算結果をたとえば第１レジスタに格納する。
【００７２】
次のステップＳ３０７において、各演算器ＣＬは、第１レジスタに格納された値（すなわち、ステップＳ３０６の演算結果）を、Ｌ１キャッシュメモリ１２２の対応するアドレスに格納する。以上によって、単位積和演算が完了する。
【００７３】
［畳み込み演算の具体例］
以下、数値例を挙げて、図６の畳み込み演算の手順をさらに詳しく説明する。具体的に、係数行列Ａ、入力ベクトルｘ、およびバイアスベクトルｂを以下の（３）式のように設定する。
【００７４】
【数３】
2019053835.tif 000005
【００７５】
仮に、上記の行列演算の各行を対応する演算器ＣＬで個別に実行したとすれば、以下の（４）式に示す４つの演算が、４個の演算にそれぞれ割り当てられる。
【００７６】
【数４】
2019053835.tif 000006
【００７７】
したがって、この場合、１番目の演算器の演算数が最も多くなり、３番目および４番目の演算器の演算数が最も少なくなる。そして、１番目の演算器の演算時間によって全体の処理時間が律速されることになる。
【００７８】
一方、（３）式の数値例を、本実施の形態の図６のステップＳ１０１〜Ｓ１０８に適用すると、行番号の格納用配列ＡROW（ｐ）および列番号の格納用配列ＡCOL（ｐ）は、次の表１のようになる。
【００７９】
【表１】
2019053835.tif 000007
【００８０】
参考までに、上記の表１のインデックスｐを係数行列Ａに添え字として記入すると、次の（５）式のとおりである。（５）式に示すように、非零要素の総数、すなわち、単位積和演算の総数は７個である。
【００８１】
【数５】
2019053835.tif 000008
【００８２】
上記の格納用配列ＡROW（ｐ）および列番号の格納用配列ＡCOL（ｐ）に基づいて、係数行列Ａにおいて実行すべき単位積和演算を書き下すと、次の（６．１）〜（６．７）式が得られる。
【００８３】
【数６】
2019053835.tif 000009
【００８４】
演算器ＣＬの個数ｎは４であるので、最初のステップで、（６．１）〜（６．４）式の単位積和演算が第０番目から第３番目の演算器ＣＬ０〜ＣＬ３によってそれぞれ実行される。この場合、（６．１）式、（６．２）式、および（６．４）式の各単位積和演算のうち、出力ベクトルの対応する要素ｆ（１）へのアクセスについては排他制御されることになる。
【００８５】
次のステップで、（６．５）〜（６．７）式の単位積和演算が第０番目から第２番目の演算器ＣＬ０〜ＣＬ２でそれぞれ実行される。
【００８６】
［効果］
以上のように、実施の形態１によれば、係数行列Ａの非零要素を検索し、検索結果に基づいて、各非零要素について単位積和演算が各演算器に分配されて実行される。これによって、各演算器における単位積和演算の処理数を平準化できるので、複数の演算器による積和演算を効率的に実行することができる。
【００８７】
図８は、実施の形態１の効果を説明するための図である。図８（Ａ）は比較例を示し、図８（Ｂ）は本実施の形態の場合を示す。
【００８８】
図８（Ａ）では、係数行列Ａの各行と入力ベクトルｘとの積和演算を各演算器ＣＬに個別に割り振った場合が示されている。この場合、非零要素のみを計算したとしても、非零要素数が係数行列の行ごとに異なっていれば、非零要素数の最も多い行に対応する演算器ＣＬでの演算によって全体の演算時間が律速される。
【００８９】
図８（Ｂ）に示す本実施の形態の場合には、各単位積和演算が各演算器にほぼ均等に割り当てらる。すなわち、図８（Ａ）の場合に演算器（１）および演算器（２）で実行されていた単位積和演算の一部が他の演算器に割当てられることになる。これによって、全体の処理時間を削減することができる。
【００９０】
実施の形態２．
図６に示すフローチャートのステップＳ１１０では、ｎ個ある演算器ＣＬは、行番号の格納用配列ＡROW（ｐ）および列番号の格納用配列ＡCOL（ｐ）を通じてｎ行ｍ列の係数行列Ａに一斉にアクセスする。このため、大規模な係数行列Ａの処理負荷が高くなるという問題がある。そこで、実施の形態２においては行番号の格納用配列ＡROW（ｐ）および列番号の格納用配列ＡCOL（ｐ）を通じてｎ行ｍ列の係数行列Ａにアクセスするのではなく、非零要素を除いた係数配列Ａ’（係数ベクトルＡ’とも称する）を新しく定義し、ｎ個ある演算器ＣＬを係数配列Ａ’にアクセスするようにする。これによって、ｎ行ｍ列の係数行列Ａへのアクセスの集中を防止することができる。
【００９１】
図９は、実施の形態２による畳み込み演算の手順を示すフローチャートである。図９のステップＳ４０１〜Ｓ４１２は、図６のステップＳ１０１〜Ｓ１１２にそれぞれ対応している。ただし、ステップＳ４０３とステップＳ４１２とでの処理が一部異なっている。以下では、処理の異なるステップＳ４０３，Ｓ４１２について主に説明し、図６と同じ処理のステップについては説明を繰り返さない。
【００９２】
図９を参照して、ステップＳ４０３において、係数行列Ａに含まれる非零要素の値とその行番号および列番号が格納される。具体的に、プロセッサは、積和演算の対象要素Ａ（ｉ，ｊ）を記憶するため、行番号の格納用配列ＡROW（ｋ）に行方向変数ｉを格納し、列番号の格納用配列ＡCOL（ｋ）に列方向変数ｊを格納し、さらに、係数配列Ａ’（ｋ）に係数行列Ａの要素Ａ（ｉ，ｊ）を記憶する。
【００９３】
具体的に、前述の（３）式の数値例の場合について説明する。この場合、係数配列Ａ’は次の表２で与えられる。
【００９４】
【表２】
2019053835.tif 000010
【００９５】
ステップＳ４１０において、総数ｋ個の単位積和演算がｎ個の演算器ＣＬにより順番に実行される。具体的に、行番号の格納用配列ＡROW（ｐ）および列番号の格納用配列ＡCOL（ｐ）を出力ベクトルｆおよび入力ベクトルｘへのポインタとしてそれぞれ利用し、以下の（７）式で示す単位積和演算を、第ｐ番目の演算器ＣＬが実行する。
【００９６】
【数７】
2019053835.tif 000011
【００９７】
ここで、ｎ個の演算器により並列に単位積和演算を行うため、上記（７）式の変数ｐはｐ＝ｏからｐ＝ｏ＋ｎ−１までのｎ個の値をとる。さらに非零要素数ｋを超えて積和演算を行わないため、ｐ＜ｋを満たす場合にのみ積和演算が実施される。
【００９８】
上記のとおり、実施の形態２によれば、実施の形態１の場合と同様の効果を奏するとともに、ｎ行ｍ列の係数行列Ａへのアクセスの集中を防止することができる。
【００９９】
今回開示された実施の形態はすべての点で例示であって制限的なものでないと考えられるべきである。この発明の範囲は上記した説明ではなくて請求の範囲によって示され、請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【０１００】
１００  入力データ（入力特徴マップ）、１０１  カーネル、１０２  出力データ、１１０，ｘ  入力ベクトル、１１１，Ａ  係数行列、１２０  並列計算機、１２１  処理ユニット、１２２  Ｌ１キャッシュメモリ、１２５  Ｌ２キャッシュメモリ、１２６  専用メモリ、１３０  ＣＰＵ、１３１  メモリ、Ａ’  係数配列（係数ベクトル）、ＣＬ  演算器、Ｒ  レジスタ群、ｂ  バイアスベクトル、ｆ  出力ベクトル。
【図１】
2019053835.tif 000012
【図２】
2019053835.tif 000013
【図３】
2019053835.tif 000014
【図４】
2019053835.tif 000015
【図５】
2019053835.tif 000016
【図６】
2019053835.tif 000017
【図７】
2019053835.tif 000018
【図８】
2019053835.tif 000019
【図９】
2019053835.tif 000020
【手続補正書】
【提出日】令和2年3月4日(2020.3.4)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
この明細書では、出力ベクトルｆの要素をｆ1，…，ｆnとする。第ｉ番目の出力ベクトルｆの要素をｆiまたはｆ（ｉ）と記載する。入力ベクトルｘの要素をｘ1，…，ｘmとする。第ｊ番目の入力ベクトルｘの要素をｘjまたはｘ（ｊ）と記載する。バイアスベクトルｂの要素をｂ1，…，ｂnとする。第ｉ番目のバイアスベクトルｂの要素をｂiまたはｂ（ｉ）と記載する。また、係数行列Ａは、第１から第ｎまでのｎ行と第１から第ｍまでのｍ列で構成される。第ｉ行第ｊ列の係数行列Ａの要素をＡijまたはＡ（ｉ，ｊ）と記載する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
次のステップＳ１０８において、全列の処理が完了したか否かの判定が実行される。具体的に、プロセッサは、全列の処理が完了したか判断するため、列方向変数ｊと係数行列Ａの列数ｍとを比較することによって全行列の処理が完了したか否かを判定する。プロセッサは、列方向変数ｊが列数ｍより大きければ全行列の処理が完了したと判断し、積和演算の変数ｆ（出力ベクトルに対応する）を初期化するためのステップＳ１０９へ処理を進める。一方、プロセッサは、列方向変数ｊが列数ｍより大きくなければ、未処理の列が残っていると判断し、非零要素を判定するためのステップＳ１０２へ処理を進める。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
ステップＳ３０１において、各演算器ＣＬは、専用メモリ１２６またはＬ１キャッシュメモリ１２２またはＬ２キャッシュメモリ１２５から、係数行列の対応する要素Ａ（ＡROW（ｐ），ＡCOL（ｐ））を読出して、対応する第１レジスタに格納する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００６７
【補正方法】変更
【補正の内容】
【００６７】
次のステップＳ３０２において、各演算器ＣＬは、専用メモリ１２６またはＬ１キャッシュメモリ１２２またはＬ２キャッシュメモリ１２５から、入力ベクトルの対応する要素ｘ（ＡCOL（ｐ））を読出して、対応する第２レジスタに格納する。なお、ステップＳ３０２は、ステップＳ３０１と同時に実行してもよいし、ステップＳ３０１の前に実行してもよい。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
まず、ステップＳ３０５において、各演算器ＣＬは、専用メモリ１２６またはＬ１キャッシュメモリ１２２またはＬ２キャッシュメモリ１２５から、ｆ（ＡROW（ｐ））を読出して第２レジスタに格納する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００７５
【補正方法】変更
【補正の内容】
【００７５】
仮に、上記の行列演算の各行を対応する演算器ＣＬで個別に実行したとすれば、以下の（４）式に示す４つの演算が、４個の演算器にそれぞれ割り当てられる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００９０
【補正方法】変更
【補正の内容】
【００９０】
実施の形態２．
図６に示すフローチャートのステップＳ１１０では、ｎ個ある演算器ＣＬは、行番号の格納用配列ＡROW（ｐ）および列番号の格納用配列ＡCOL（ｐ）を通じてｎ行ｍ列の係数行列Ａに一斉にアクセスする。このため、大規模な係数行列Ａの処理負荷が高くなるという問題がある。そこで、実施の形態２においては行番号の格納用配列ＡROW（ｐ）および列番号の格納用配列ＡCOL（ｐ）を通じてｎ行ｍ列の係数行列Ａにアクセスするのではなく、零要素を除いた係数配列Ａ’（係数ベクトルＡ’とも称する）を新しく定義し、ｎ個ある演算器ＣＬを係数配列Ａ’にアクセスするようにする。これによって、ｎ行ｍ列の係数行列Ａへのアクセスの集中を防止することができる。
【手続補正８】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2019053835.tif 000021
【国際調査報告】
2019053835.tif 000022
2019053835.tif 000023