(57)【要約】  【課題】  従来のＳＩＭＤ演算装置では、ステップ間で演算装置が詰まってしまい、また、同じデータに対して、複数回の演算が必要になる。  【解決手段】  ＳＩＭＤ演算装置１０は、処理対象データを格納するデータメモリ１１と、係数を格納する係数メモリ１５と、処理対象データと係数とに基づいて計算をするデータ処理部１２と、処理対象データに応じて係数を計算する係数演算部１４と、係数に基づいて新たな係数を計算する係数更新部１６と、処理の繰返し数に応じて係数メモリ１５の参照アドレスを計算するためのポインタを生成する係数ポインタ部１３とを備え、係数Ｐに基づくデータ処理部１２の計算結果において、係数演算部１４が必要とするデータがそろった場合に、係数演算部１４は、次の係数Ｐ＋１の計算を開始するとともに、データ処理部１２は、係数Ｐに基づく計算を継続する。【選択図】  図１
2020057325.tif 000002
【特許請求の範囲】
【請求項１】
処理対象データを格納するデータメモリ（１１）と、
係数を格納する係数メモリ（１５）と、
前記処理対象データと前記係数とに基づいて計算をするデータ処理部（１２）と、
前記処理対象データに応じて前記係数を計算する係数演算部（１４）と、
前記係数に基づいて新たな係数を計算する係数更新部（１６）と、
処理の繰返し数に応じて前記係数メモリの参照アドレスを計算するためのポインタを生成する係数ポインタ部（１３）と、
を備え、
係数Ｐに基づく前記データ処理部の計算結果において、前記係数演算部が必要とするデータがそろった場合に、前記係数演算部は、次の係数Ｐ＋１の計算を開始するとともに、前記データ処理部は、係数Ｐに基づく計算を継続するＳＩＭＤ演算装置。
【請求項２】
前記係数ポインタ部は、前記係数Ｐと継続した繰返し数とを関連付けた進行情報を格納する、請求項１に記載のＳＩＭＤ演算装置。
【請求項３】
前記係数メモリは、前記係数演算部が計算した係数列に加えて、前記係数更新部が計算した累積係数列を格納し、
前記係数更新部は、前記累積係数列と前記係数列に基づいて新たな累積係数を計算する、請求項２に記載のＳＩＭＤ演算装置。
【請求項４】
前記データ処理部が前記次の係数Ｐ＋１に基づく計算を行う際に、前記係数ポインタ部は、前記進行情報に基づいて、前記係数Ｐに基づく計算が完了した前記処理対象データを処理する前記データ処理部には、前記次の係数Ｐ＋１を示すポインタを生成し、前記係数Ｐに基づく演算が完了していないデータを処理する前記データ処理部には、前記次の係数Ｐ＋１までを累積した累積係数を示すポインタを生成する、請求項２又は３に記載のＳＩＭＤ演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理対象データに対してＳＩＭＤ方式で並列処理を行うＳＩＭＤ演算装置に関する。
【背景技術】
【０００２】
データ解析、生産計画、信号処理、経路生成など多岐にわたる応用アプリケーションにおいて、多数のデータ値（例えば、行列Ａとベクトルｂ）から、モデル係数（例えば、ベクトルｘ）を推定する問題がある。
【０００３】
この問題は、モデル係数とデータ値とから想起される連立方程式の問題となる。連立方程式の数値安定解を計算する手法としては、データ行列ＡをＱＲ分解する手法が有効である。図８は、ＱＲ分解による連立方程式の解の計算方法を示す図である。
【０００４】
図８（ａ）に示すように、行列Ａとベクトルｂが与えられたときに係数ｘを求めるために、図８（ｂ）に示すように、行列Ａを直交行列Ｑと上三角行列Ｒに分解し、さらに、両辺にＱの転置行列Ｑ´をかけると、図８（ｃ）に示すようになる。ここで、行列Ｒは三角行列であるので、係数ｘはガウス後退代入によって計算することが可能になる。
【０００５】
行列ＡをＱＲ分解するのに、下式（１）に示すギブンス（Ｇｉｖｅｎｓ）変換を用いることができる。
【数１】
2020057325.tif 000003
ここで、Ｇはギブンス回転行列であり、下式（２）で表される。
【数２】
2020057325.tif 000004
【０００６】
具体的には、まず、行列Ａのｉ＋１行ｋ列を０とするｓｉｎθ及びｃｏｓθをそれぞれ下式（３）で計算する。
【数３】
2020057325.tif 000005
次に、行列Ａにギブンス回転行列Ｇを乗算する。これを行列Ａの下三角がすべて０になるまで繰り返すことで、上三角行列Ｒを得ることができる。
【０００７】
図９は、上記のギブンス変換によるＱＲ分解を模式的に表す図である。図９（ａ）に示すように、値１０１を０とする回転行列１０２を計算して、図９（ｂ）に示すように、この回転行列１０２とベクトル１０３及び１０４の各要素（２×１）を乗算する。そして、図９（ｃ）に示すように、この演算で得たベクトル１０５及び１０６で元の行列Ａを更新する。次に、値１０７を０とする回転行列を計算して、図９（ｂ）と同様にして回転行列と更新されたベクトル１０５及び１０６の各要素を乗算する。これを行列Ａが下三角行列になるまで繰り返す。
【０００８】
特許文献１には、携帯電話やＷｉ−Ｆｉ（登録商標）などで用いられるＭＩＭＯ−ＯＦＤＭ処理をシストリックアレイで効率的に処理する方法が開示されている。しかしながら、この方法では、構造が固定的であるため、異なるサイズの行列や大規模な行列を処理することができない。
【０００９】
特許文献２には、多数のデータに対する画一の処理に対して、ＳＩＭＤ（single instruction multiple data）型の演算装置（以下単に「ＳＩＭＤ演算装置」という。）を用いて高速化をする技術が開示されている。特許文献１のＳＩＭＤ演算装置によれば、図１０に示すように、ＳＩＭＤ幅（即ち、図１０の矢印の長さ）よりも大きな行列Ａを処理する場合には、各ステップ（１つの値を０にする）において、ＳＩＭＤ方式のデータ処理（以下、「ＳＩＭＤ処理」という。）を複数回（図１０の例では３回）実行するなどの実装が可能である。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特表２０１３−５１１８９１号公報
【特許文献２】特開２０１２−１９４７７４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、特許文献２のＳＩＭＤ演算装置では、ステップごとに異なる回転行列の係数が必要であり、係数計算が十数サイクルにもなり、ステップ間で演算装置がストールしてしまう。また、特許文献２のＳＩＭＤ演算装置では、同じデータに対して、複数回（複数ステップ）の演算が必要になる。
【課題を解決するための手段】
【００１２】
本発明の一態様のＳＩＭＤ演算装置（１０）は、処理対象データを格納するデータメモリ（１１）と、係数を格納する係数メモリ（１５）と、前記処理対象データと前記係数とに基づいて計算をするデータ処理部（１２）と、前記処理対象データに応じて前記係数を計算する係数演算部（１４）と、前記係数に基づいて新たな係数を計算する係数更新部（１６）と、処理の繰返し数に応じて前記係数メモリの参照アドレスを計算するためのポインタを生成する係数ポインタ部（１３）とを備え、係数Ｐに基づく前記データ処理部の計算結果において、前記係数演算部が必要とするデータがそろった場合に、前記係数演算部は、次の係数Ｐ＋１の計算を開始するとともに、前記データ処理部は、係数Ｐに基づく計算を継続する構成を有している。
【発明の効果】
【００１３】
本発明によれば、ステップ（Ｎ）の処理が完了しないうちに、ステップ（Ｎ）の残りの処理と並行して次のステップ（Ｎ＋１）の係数の計算を開始するので、ステップ間で演算装置のストールが発生せず、同じ処理対象データに対する重複した演算を回避できる。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の実施の形態のＳＩＭＤ演算装置の構成を示すブロック図である。
【図２】図２は、本発明の実施の形態のＳＩＭＤ演算装置の処理手順を示す図である。
【図３】図２は、本発明の実施の形態のＳＩＭＤ演算装置の処理手順を示す図である。
【図４】図４は、本発明の実施の形態のＳＩＭＤ演算装置による演算を従来手法と比較して示す図である。
【図５】図５は、本発明の実施の形態のＳＩＭＤ演算装置１０による演算のステップ（１）の処理を説明する図である。
【図６】図６は、本発明の実施の形態のＳＩＭＤ演算装置１０による演算のステップ（２）の処理を説明する図である。
【図７】図７は、本発明の実施の形態のＳＩＭＤ演算装置１０による演算のステップ（３）の処理を説明する図である。
【図８】図８は、既存のＱＲ分解による連立方程式の解の計算方法を示す図である。
【図９】図９は、既存のギブンス変換によるＱＲ分解を模式的に表す図である。
【図１０】図１０は、従来のＳＩＭＤ処理を説明する図である。
【発明を実施するための形態】
【００１５】
以下、本発明に係る畳込み演算方法の実施の形態について図面を参照しながら説明する。図１は、本発明の実施の形態におけるＳＩＭＤ演算装置の構成を示すブロック図である。ＳＩＭＤ演算装置１０は、複数のデータメモリ１１と、複数のデータ処理部１２と、複数の係数ポインタ１３と、係数演算部１４と、係数メモリ１５と、係数更新部１６とを備えている。データメモリ１１と、データ処理部１２と、係数ポインタ部１３は、それぞれＳＩＭＤ幅に対応する個数あり、１つのデータメモリ１１と、１つのデータ処理部１２と、１つの係数ポインタ部１３から１つのプロセッサエレメント（以下、「ＰＥ」という。）が構成される。よって、ＳＩＭＤ演算装置１０は、ＳＩＭＤ幅に対応する個数のＰＥを備えている。
【００１６】
データメモリ１１は、処理対象データを格納する。係数メモリ１５は、係数を格納する。データ処理部１２は、データと係数に基づいて計算を行う。係数演算部１４は、処理対象データに応じて係数を計算する。係数更新部１６は、係数どうしに基づいて新たな係数を計算する。係数ポインタ部１３は、処理のステップに応じて係数メモリ１５の参照アドレスを計算する。
【００１７】
本発明の実施の形態のＳＩＭＤ演算装置１０の特徴を説明する。まず、ＳＩＭＤ演算装置１０は、ステップ（Ｎ）の処理で行列Ａの一部が０となった後に、ステップ（Ｎ＋１）の係数計算と、ステップ（Ｎ）の残りの処理を並行して行う。
【００１８】
図２は、この特徴を示す図である。ＳＩＭＤ演算装置１０は、行列Ａのベクトルの一部（ＳＩＭＤ幅に対応する個数）のデータをデータメモリ１１から読み出して、ＳＩＭＤ処理を行う。繰返し数（２）では、データメモリ１１から読み出す位置をスライドさせてＳＩＭＤ処理を行うが、このとき、先の計算によって行列Ａにおける０にすべき値が０になった場合には、次のステップに向けた計算を開始する。
【００１９】
ＳＩＭＤ演算装置１０のもう一つの特徴は、一部のＰＥにおいて、演算に用いる係数の値を他のＰＥと異なる値とすることである。図３を参照してこの特徴を説明する。まず、ステップ（Ｎ＋１）の係数計算が完了すると、ＳＩＭＤ演算装置１０は、図３に示すように、ステップ（Ｎ）からステップ（Ｎ＋１）の計算に切り替える。このステップ（Ｎ＋１）では、ステップ（Ｎ）が完了したデータ２０１も用いて計算をすることになる。
【００２０】
そして、上述のように、ＳＩＭＤ演算を進めていき、図３に示すように、ステップ（Ｎ＋１）にて０にすべき値が０になると、次のステップ（Ｎ＋２）にて０にすべき値に向けた係数の計算を開始する。図３の繰返し数（４）の処理では、一部のデータ２０２については、ステップ（Ｎ）の処理が未完了である。この場合には、当該一部のＰＥについては、ステップ（Ｎ）とステップ（Ｎ＋１）の係数を乗じた係数を用いる。
【００２１】
図４は、本発明の実施の形態のＳＩＭＤ演算装置１０による演算を従来手法と比較して示す図である。図４に示すように、従来は、ＳＩＭＤ幅より大きい行列ＡのＱＲ分解を行う際には、同じデータに対して、最大でステップ数回の重複した演算を行っていたが、本実施の形態のＳＩＭＤ演算装置１０によれば、この重複がなくなる。
【００２２】
即ち、本実施の形態のＳＩＭＤ演算装置１０は、係数Ｐに基づくデータ処理部１２の演算結果において、係数演算部１４が必要とするデータがそろった場合に、計算演算部１４は係数Ｐ＋１の計算を開始して、終了するまで係数Ｐに基づくデータ処理部１２における演算を継続する。また、係数ポインタ部１３は、係数Ｐと継続した繰返し数を関連付けた進行情報を格納する。
【００２３】
そして、ＳＩＭＤ演算装置１０において、係数メモリ１５は、係数演算部１４が計算した係数列に加えて、係数更新部１６が更新した累積係数列を格納する。また、係数更新部１６は、累積係数列と係数列に基づいて、新たな累積係数を計算する。
【００２４】
データ処理部１２が係数Ｐ＋１に基づく計算を行う際には、係数ポインタ部１３に格納した進行情報に基づき、係数Ｐに基づく計算が完了したデータを処理するデータ処理部１２には、係数Ｐ＋１を示すポインタを生成して、係数Ｐに基づく演算が完了していないデータを処理するデータ処理部１２には、係数Ｐ＋１までを累積した累積係数を示すポインタを生成する。
【００２５】
以下、本実施の形態のＳＩＭＤ演算装置１０による演算を具体的に説明する。図５は、ステップ（１）の処理を説明する図である。まず、ＳＩＭＤ演算装置１０は、時刻（１）において、データメモリ１１に、行列ＡのＳＩＭＤ幅分の一部のデータ３１１及び３１２を格納する。係数演算部１４は、データメモリ１１に格納された係数元データ３３１及び３３２に基づいて係数１を計算し、係数メモリ１５に格納する。データ処理部１２は、この係数１とデータメモリ１１上のデータ３１１及び３１２に基づいて計算を行い、演算結果３１３及び３１４をデータメモリ１１の同じ位置に格納する。係数ポインタ部１３は、データ処理部１２の繰返し数（１）をカウントする。
【００２６】
次に、時刻（２）において、係数演算部１４は、データメモリ１１に格納された演算結果３５１（即ち、演算結果３１３及び３１４）中の係数元データ３３３及び３３４に基づいて、係数２の計算を開始する。そして、データ処理部１２は、係数１とデータメモリ１１上のデータ３１３及び３１４に基づいて計算を行い、演算結果３１５及び３１６をデータメモリ１１上の同じ位置に格納する。そして、係数ポインタ部１３は、データ処理部１２の繰返し数（２）をカウントする。
【００２７】
このようにして演算処理を進めていき、ＳＩＭＤ演算装置１０は、時刻（３３）では、計算した係数２と、係数１で処理した繰返し数（３３）と係数２の係数元データ３３３及び３３４の位置のずれ量（１）とをセットにして進行情報として、係数メモリ１４に格納する。係数更新部１６は、係数１と係数２とを基に、累積係数（１＋２）を計算して、係数メモリ１５に格納する。そして、データ処理部１２は、係数１とデータメモリ上のデータ３１５及び３１６に基づいて計算を行い、演算結果３１７及び３１８をデータメモリ１１上の同じ位置に格納する。また、係数ポインタ部１３は、データ処理部１２の繰返し数（３３）をカウントする。
【００２８】
図６は、ステップ（２）の処理を説明する図である。まず、時刻（３４）において、データ処理部１２は、係数２とデータメモリ１１上の係数１の処理済データ３５２に基づいて計算を行い、演算結果３１９及び３２０をデータメモリ１１上の同じ位置に格納する。係数ポインタ部１３は、データ処理部１２の繰返し数（１）をカウントする。
【００２９】
次に、時刻（３５）において、係数演算部１４は、データメモリ１１に格納された処理結果３５３中の係数元データ３３５及び３３６に基づいて、係数３の計算を開始する。データ処理部１２は、係数２とデータメモリ１１上の係数１の処理済データ３５２に基づいて計算を行い、演算結果３２１及び３２２をデータメモリ１１上の同じ位置に格納する。係数ポインタ部１３は、データ処理部１２の繰返し数（２）をカウントする。
【００３０】
このようにして演算処理を進めていき、ＳＩＭＤ演算装置１０は、時刻（６６）では、ＳＩＭＤ演算装置１０は、計算した係数３と、係数２で処理した繰返し数（３３）と係数３の係数元データ３３５及び３３６の位置のずれ量（１）とをセットにして進行情報として、係数メモリ１５に格納する。係数更新部１６は、係数３と累積係数（１＋２）を基に、累積係数（１＋２＋３）を計算し、係数メモリ１５に格納する。データ処理部１２は、係数２とデータメモリ１１上の係数１の処理済データ３５２と、累積係数（１＋２）とデータメモリ１１上の係数１で未処理のデータ３５４に基づいて計算を行い、演算結果３２３及び３２４をデータメモリ１１上の同じ位置に格納する。
【００３１】
係数ポインタ部１３は、係数２とともに格納された繰返し数（３３）と、係数ポインタ部１３がカウントする繰返し数とが同じである場合に、係数２とともに格納されたずれ量（１）に基づいて、右端からずれ量（１）分のデータ処理部１２には、累積係数（１＋２）を、それ以外には係数２を選択する。係数ポインタ部１３は、データ処理部１２の繰返し数（３３）をカウントする。
【００３２】
図７は、ステップ（３）の処理を説明する図である。まず、時刻（６７）において、データ処理部１２は、係数３とデータメモリ１１上の係数２の処理済データ３５５に基づいて計算を行い、演算結果３２５及び３２６をデータメモリ１１上の同じ位置に格納する。係数ポインタ部１３は、データ処理部１２の繰返し数（１）をカウントする。
【００３３】
次に、時刻（６８）において、係数演算部１４は、データメモリ１１に格納された処理結果３５６中の係数元データ３３７及び３３８に基づいて、係数４の計算を開始する。データ処理部１２は、係数３とデータメモリ１１上の係数2の処理済みデータ３５５に基づいて計算を行い、演算結果３３７及び３３８をデータメモリ１１上の同じ位置に格納する。係数ポインタ部１３は、データ処理部１２の繰返し数（２）をカウントする。
【００３４】
このようにして演算処理を進めていき、ＳＩＭＤ演算装置１０は、時刻（９９）では、計算した係数４と、係数３で処理した繰返し数（３３）と係数４の係数元データ３３７及び３３８の位置のずれ量（１）とをセットにして進行情報として、係数メモリ１５に格納する。係数更新部１６は、係数４と累積係数（１＋２＋３）を基に、累積係数（１＋２＋３＋４）を計算し、係数メモリ１５に格納する。データ処理部１２は、係数３とデータメモリ１１上の係数２の処理済データ３５５と、累積係数（１＋２＋３）とデータメモリ１１上の係数１及び係数２での未処理データ３５６に基づいて計算を行い、演算結果をデータメモリ１１上の同じ位置に格納する。
【００３５】
係数ポインタ部１３は、係数３とともに格納された繰返し数（３３）と、係数ポインタ部１３がカウントする繰返し数（３３）とが同じである場合に、係数３とともに格納されたずれ量（１）に基づいて、右端からずれ量（１）分のデータ処理部１２には、累積係数（１＋２）を、それ以外には係数３を選択する。係数ポインタ部１３は、データ処理部１２の繰返し数（３３）をカウントする。
【００３６】
以上のように、本実施の形態のＳＩＭＤ演算装置１０によれば、係数Ｐに基づいてデータ処理部１２にて計算をして得られた演算結果において係数演算部１４が必要とするデータが得られた段階で、係数演算部１４は次の係数Ｐ＋１の計算を開始する。このとき、データ処理部１２は、係数Ｐに基づく処理を継続する。そして、係数ポインタ部１３には、係数Ｐと継続した繰返し数とをセットにして格納する。
【００３７】
係数メモリ１５は、係数演算部１４が計算した係数列だけでなく、係数更新部１６が計算した累積係数列を格納する。係数更新部１６は、累積係数列と係数演算部１４が計算した係数列に基づいて、新たな累積係数を計算する。
【００３８】
データ処理部１２が係数Ｐ＋１に基づく計算を行う際には、係数ポインタ部１３は、格納している進行情報に基づいて、以下のようにポインタ（即ち、係数演算部１４が参照する係数メモリ１５のアドレス）を設定する。すなわち、係数Ｐの処理済データを処理するデータ処理部１２に対しては、係数Ｐ＋１を示すポインタを設定し、係数Ｐでの未処理データを処理するデータ処理部１２に対しては、係数Ｐ＋１までを累積した累積係数を示すポインタを設定する。
【産業上の利用可能性】
【００３９】
以上のように、本発明は、ＳＩＭＤ方式で処理対象データを処理するにあたって、ステップ（Ｎ）の処理が完了しないうちに、ステップ（Ｎ）の残りの処理と並行して次のステップ（Ｎ＋１）の係数の計算を開始するので、ステップ間で演算装置のストールが発生せず、同じ処理対象データに対する重複した演算を回避できるという効果を有し、処理対象データに対してＳＩＭＤ方式で並列処理を行うＳＩＭＤ演算装置等として有用である。
【符号の説明】
【００４０】
１０  ＳＩＭＤ演算装置、１１  データメモリ、１２  データ処理部、
１３  係数ポインタ部、１４  係数演算部、１５  係数メモリ、１６  係数更新部
【図１】
2020057325.tif 000006
【図２】
2020057325.tif 000007
【図３】
2020057325.tif 000008
【図４】
2020057325.tif 000009
【図５】
2020057325.tif 000010
【図６】
2020057325.tif 000011
【図７】
2020057325.tif 000012
【図８】
2020057325.tif 000013
【図９】
2020057325.tif 000014
【図１０】
2020057325.tif 000015