(57)【特許請求の範囲】
【請求項１】
多次元の第１行列データをＦＦＴ演算する演算部と、
前記第１行列データの少なくとも１行の連続する行を含む一部のデータである第２行列データを記憶する第１メモリと、
１回のアクセスでアクセスできる最小ビット数を有し、前記第１行列データを記憶する第２メモリと、
を具備し、 
前記演算部は、
前記第１メモリに記憶された前記第２行列データを前記最小ビット数以上のサイズの行列データであり、前記第２行列データの少なくとも１列の連続する列を含む一部のデータである第３行列データに分割し、前記第３行列データを各々行列転置させ、
前記第２行列データを行列転置された前記第３行列データ単位で前記第１メモリから前記第２メモリの元の位置に記憶させ、
前記第２メモリ内において行列転置された前記第３行列データが列方向に連続する第４行列データを前記第３行列データ単位で前記第２メモリから前記第１メモリに記憶させ、
前記第１メモリに記憶された前記第４行列データを１行単位でＦＦＴ演算することを特徴とする演算装置。
【請求項２】
前記第３行列データのサイズは前記最小ビット数の自然数倍であることを特徴とする請求項１記載の演算装置。
【請求項３】
前記第２メモリはＳＤＲＡＭであり、
前記演算部は、前記第２行列データの同行の列順に複数の前記第３行列データを、前記第２メモリの同行列アドレスにバンクアドレス順に記憶させることを特徴とする請求項１または２記載の演算装置。
【請求項４】
前記演算部は、前記第２行列データの同列の次の行の前記第３行列データを前記第２メモリの同じバンクアドレスの前記第３行列データのサイズに対応する次の行列アドレスに続き記憶させることを特徴とする請求項３記載の演算装置。
【請求項５】
前記演算部は、前記第２行列データを前記第３行列データ単位で前記第２メモリに記憶させる際に、バンクアドレスが一巡する度に、前記第４行列データのサイズに対応する次の行列アドレスに前記第３行列データを記憶させることを特徴とする請求項４記載の演算装置。
【請求項６】
演算装置が多次元の第１行列データをＦＦＴ演算する演算方法であって、
前記第１行列データの少なくとも１行の連続する行を含む一部のデータであり、第１メモリに記憶された第２行列データを、前記第１行列データを記憶する第２メモリに１回のアクセスでアクセスできる最小ビット数以上のサイズの行列データであり、前記第２行列データの少なくとも１列の連続する列を含む一部のデータである第３行列データに分割し、前記第３行列データを各々行列転置させるステップと、
前記第２行列データを行列転置された前記第３行列データ単位で前記第１メモリから前記第２メモリの元の位置に記憶させるステップと、
前記第２メモリ内において行列転置された前記第３行列データが列方向に連続する第４行列データを前記第３行列データ単位で前記第２メモリから第１メモリに記憶させるステップと、
前記第１メモリに記憶された前記第４行列データを１行単位でＦＦＴ演算するステップと、
を含むことを特徴とする演算方法。
【請求項７】
多次元の第１行列データをＦＦＴ演算するプログラムであって、
前記第１行列データの少なくとも１行の連続する行を含む一部のデータであり、第１メモリに記憶された第２行列データを、前記第１行列データを記憶する第２メモリに１回のアクセスでアクセスできる最小ビット数以上のサイズの行列データであり、前記第２行列データの少なくとも１列の連続する列を含む一部のデータである第３行列データに分割し、前記第３行列データを各々行列転置させ、
前記第２行列データを行列転置された前記第３行列データ単位で前記第１メモリから前記第２メモリの元の位置に記憶させ、
前記第２メモリ内において行列転置された前記第３行列データが列方向に連続する第４行列データを前記第３行列データ単位で前記第２メモリから第１メモリに記憶させ、
前記第１メモリに記憶された前記第４行列データを１行単位でＦＦＴ演算する処理を、コンピュータに実行させるプログラム。
【請求項８】
前記演算部は、ＦＦＴ演算された前記第４行列データを前記第３行列データ単位で前記第１メモリから前記第２メモリの元の位置に記憶させることを特徴とする請求項１記載の演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算装置、演算方法およびプログラムに関し、例えば多次元の第１行列データをＦＦＴ演算する演算装置、演算方法およびプログラムに関する。
【背景技術】
【０００２】
ＦＦＴ（Fast Fourier Transform）演算は、ＯＦＤＭ（Orthogonal Frequency Division Multiplex）変復調器等の通信機器、デコーダ等の画像処理機器等に広く用いられている。ＦＦＴの手法として、２次元ＦＦＴ等の多次元ＦＦＴが知られている。多次元ＦＦＴは、多次元データをＦＦＴ演算する場合以外にも、点数の多い１次元データをＦＦＴ演算する場合に、１次元データを多次元データに変換することで、点数の大きい単一の１次元ＦＦＴ演算が、点数の小さい複数の１次元演算で実現できる。
【０００３】
特許文献１には、キャッシュラインサイズをＳＤＲＡＭ（Synchronous Dynamic Random Access Memory）のバーストサイズと一致させる例が記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】国際公開第２００４／０３２４３５号パンフレット
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ＦＦＴ演算する行列データが膨大な場合は、演算装置内の第１メモリ（例えば、キャッシュメモリ）に行列データが収まらない。そこで、演算装置は、演算装置の外部に設けられた第２メモリ（例えば、ＳＤＲＡＭ）に行列データを記憶させる。演算装置は、行列データのうち演算に用いるデータを演算装置内の第１メモリに一次的に格納し、演算を行なう。例えば、キャッシュメモリとＳＤＲＡＭとの間のデータ転送をバースト転送することで、キャッシュメモリとＳＤＲＡＭとの間のデータ転送速度を向上させることができる。
【０００６】
しかしながら、多次元ＦＦＴ演算においては、行列転置が行なわれる。この際は、行列の連続しない各点のデータにアクセスすることになる。このため、キャッシュメモリとＳＤＲＡＭとの間のデータ転送としてバースト転送を用いたとしても高速なデータ転送が行なえない。このため、第１メモリと第２メモリとの間のデータ転送がＦＦＴ演算全体のボトルネックになってしまう。このように、行列転置を行なうＦＦＴ演算においては、第１メモリと第２メモリとの間のデータ転送がＦＦＴ演算全体のボトルネックとなる。
【０００７】
本演算装置、演算方法およびプログラムは、ＦＦＴ演算を高速化することを目的とする。
【課題を解決するための手段】
【０００８】
例えば、多次元の第１行列データをＦＦＴ演算する演算部と、前記第１行列データの少なくとも１行の連続する行を含む一部のデータである第２行列データを記憶する第１メモリと、１回のアクセスでアクセスできる最小ビット数を有し、前記第１行列データを記憶する第２メモリと、を具備し、前記演算部は、前記第１メモリに記憶された前記第２行列データを前記最小ビット数以上のサイズの行列データであり、前記第２行列データの少なくとも１列の連続する列を含む一部のデータである第３行列データに分割し、前記第３行列データを各々行列転置させ、前記第２行列データを行列転置された前記第３行列データ単位で前記第１メモリから前記第２メモリの元の位置に記憶させ、前記第２メモリ内において行列転置された前記第３行列データが列方向に連続する第４行列データを前記第３行列データ単位で前記第２メモリから前記第１メモリに記憶させ、前記第１メモリに記憶された前記第４行列データを１行単位でＦＦＴ演算することを特徴とする演算装置を用いる。
【０００９】
例えば、演算装置が多次元の第１行列データをＦＦＴ演算する演算方法であって、前記第１行列データの少なくとも１行の連続する行を含む一部のデータであり、第１メモリに記憶された第２行列データを、前記第１行列データを記憶する第２メモリに１回のアクセスでアクセスできる最小ビット数以上のサイズの行列データであり、前記第２行列データの少なくとも１列の連続する列を含む一部のデータである第３行列データに分割し、前記第３行列データを各々行列転置させるステップと、前記第２行列データを行列転置された前記第３行列データ単位で前記第１メモリから前記第２メモリの元の位置に記憶させるステップと、前記第２メモリ内において行列転置された前記第３行列データが列方向に連続する第４行列データを前記第３行列データ単位で前記第２メモリから第１メモリに記憶させるステップと、前記第１メモリに記憶された前記第４行列データを１行単位でＦＦＴ演算するステップと、を含むことを特徴とする演算方法。
を用いる。
【００１０】
例えば、多次元の第１行列データをＦＦＴ演算するプログラムであって、前記第１行列データの少なくとも１行の連続する行を含む一部のデータであり、第１メモリに記憶された第２行列データを、前記第１行列データを記憶する第２メモリに１回のアクセスでアクセスできる最小ビット数以上のサイズの行列データであり、前記第２行列データの少なくとも１列の連続する列を含む一部のデータである第３行列データに分割し、前記第３行列データを各々行列転置させ、前記第２行列データを行列転置された前記第３行列データ単位で前記第１メモリから前記第２メモリの元の位置に記憶させ、前記第２メモリ内において行列転置された前記第３行列データが列方向に連続する第４行列データを前記第３行列データ単位で前記第２メモリから第１メモリに記憶させ、前記第１メモリに記憶された前記第４行列データを１行単位でＦＦＴ演算する処理を、コンピュータに実行させるプログラムを用いる。
【発明の効果】
【００１１】
本演算装置、演算方法およびプログラムによれば、ＦＦＴ演算を高速化することができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、実施例１に係る演算装置が用いられるシステムの例を示す図である。
【図２】図２は、演算装置のブロック図である。
【図３】図３は、演算装置が行なう処理のフローチャートである。
【図４】図４（ａ）および図４（ｂ）は、２次元ＦＦＴ演算の例を示す模式図（その１）である。
【図５】図５（ａ）から図５（ｃ）は、２次元ＦＦＴ演算の例を示す模式図（その２）である。
【図６】図６（ａ）から図６（ｄ）は、２次元ＦＦＴ演算の例を示す模式図（その３）である。
【図７】図７は、演算部の行なうフローチャートを示す図（その１）である。
【図８】図８（ａ）から図８（ｃ）は、第１メモリおよび第２メモリを示す模式図（その１）である。
【図９】図９（ａ）および図９（ｂ）は、第１メモリおよび第２メモリを示す模式図（その２）である。
【図１０】図１０は、演算部の行なうフローチャートを示す図（その２）である。
【図１１】図１１（ａ）から図１１（ｃ）は、第１メモリおよび第２メモリを示す模式図（その３）である。
【図１２】図１２（ａ）および図１２（ｂ）は、第１メモリおよび第２メモリを示す模式図（その４）である。
【図１３】図１３（ａ）および図１３（ｂ）は、第１行列データを示す模式図である。
【図１４】図１４（ａ）および図１４（ｂ）は、第１メモリ内の第３行列データを示す模式図である。
【図１５】図１５は、ＳＤＲＡＭ内の領域を示す模式図（その１）である。
【図１６】図１６は、ＳＤＲＡＭ内の領域を示す模式図（その２）である。
【図１７】図１７（ａ）および図１７（ｂ）は、第１メモリ内の領域を示す模式図である。
【発明を実施するための形態】
【００１３】
以下、図面を参考に実施例について説明する。
【実施例１】
【００１４】
図１は、実施例１に係る演算装置が用いられるシステムの例を示す図である。システムは、アナログデジタルコンバータ（ＡＤＣ）３２、演算装置２０、デジタル処理装置３４および第２メモリ１２を備えている。ＡＤＣ２２は、受信したアナログ信号をデジタル化する。演算装置２０は、デジタル信号をＦＦＴ演算する。演算装置２０は、例えば第１メモリ１０を内蔵している。演算装置２０は、例えばＦＦＴ演算専用のＬＳＩ（Large Scale Integrated Circuit）である。または、例えばＦＦＴ演算用にプログラムされたＦＰＧＡ（Field Programmable Gate Array）である。さらに、例えば、ＣＰＵ（Central Processing Unit）のように、汎用の演算装置でもよい。さらに、コンピュータでもよい。第２メモリ１２は、例えば演算装置２０の外部メモリである。第２メモリ１２は、例えばＳＤＲＡＭであり、１回のアクセスでアクセスできる最小ビット数を有している。デジタル処理装置３４は、ＦＦＴ演算されたデジタル信号をデジタル処理する。図１のシステムは、例えば、ＯＦＤＭ（Orthogonal Frequency Division Multiplex）変復調器等の通信機器、デコーダ等の画像処理機器、スペクトルアナライザ等の計測機器の一部として用いられる。
【００１５】
図２は、演算装置のブロック図である。図２のように、演算装置２０は、演算部２１、入力部２２、制御部２３、出力部２４および第１メモリ１０を備えている。演算部２１は、デジタルデータをＦＦＴ演算する。入力部２２は、外部からＦＦＴ演算するデジタル信号およびコマンドを受信する。また、第２メモリ１２からＦＦＴ演算中のデータを受信する。出力部２４は、ＦＦＴ演算したデジタル信号を送信する。また、第２メモリ１２にＦＦＴ演算中のデータを送信する。第１メモリ１０は、演算部２１において、ＦＦＴ演算中のデータを一時格納管する。第１メモリ１０は、例えばキャッシュメモリであり、例えばＦＰＧＡの内部ＲＡＭである。第１メモリ１０は、例えばＳＲＡＭ（Static  ＲＡＭ）である。制御部２３は、演算部２１、入力部２２、出力部２４および第１メモリ１０を制御する。なお、以下の説明では、制御部２３の動作は演算部２１の動作に含め説明する。内部バス２６は、各部間に接続され各部間にデータおよびコマンドを伝送する。
【００１６】
次に、２次元ＦＦＴ演算の例を説明する。図３は、演算装置が行なう処理のフローチャートである。図３のように、入力部２２は、２次元行列データを入力する（ステップＳ１０）。入力された２次元行列データは、第２メモリ１２または第１メモリ１０に格納され、以下の演算中に演算部２１に転送および格納される。演算部２１は、２次元行列データを行列転置する（ステップＳ１２）。演算部２１は、行列転置された２次元行列データの各行毎に１次元ＦＦＴ演算する（ステップＳ１４）。演算部２１は、１次元ＦＦＴ演算した２次元行列データを行列転置する（ステップＳ１６）。演算部２１は、行列転置された２次元行列データの各行毎に１次元ＦＦＴ演算する（ステップＳ１８）。演算部２１は、１次元ＦＦＴ演算した２次元行列データを行列転置する（ステップＳ２０）。出力部２４は、演算した２次元行列データを出力する（ステップＳ２２）。
【００１７】
図４（ａ）から図６（ｄ）は、２次元ＦＦＴ演算の例を示す模式図である。図４（ａ）のように、ステップＳ１０において、０からｍ−１の行と０からｎ−１列のｍ行ｎ列の２次元行列データが入力される。２次元行列データには、ｍ×ｎ点のデータがある。図４（ｂ）のように、ステップＳ１２において、入力された２次元行列データをｎ行ｍ列の２次元行列データに行列転置する。図５（ａ）のように、ステップＳ１４において、０行目のデータを１次元ＦＦＴ演算する。斜線部が１次元ＦＦＴ演算する行を示している。図５（ｂ）のように、次に１行目のデータを１次元ＦＦＴ演算する。このようにして、図５（ｃ）のようにｎ−１行目まで１次元ＦＦＴ演算する。図６（ａ）のように、ステップＳ１６において、各行を１次元ＦＦＴ演算した２次元行列データをｍ行ｎ列の２次元行列データに行列転置する。図６（ｂ）のように、ステップＳ１８において、０行目のデータを１次元ＦＦＴ演算する。図６（ｃ）のように、ｍ−１行目まで１次元ＦＦＴ演算する。図６（ｄ）のように、ステップＳ２０において、各行を１次元ＦＦＴ演算した２次元行列データをさらにｎ行ｍ列の２次元行列データに行列転置する。ステップＳ２２において、行列転置した２次元行列データを出力する。
【００１８】
次に、実施例１における演算部２１の制御を説明する。２次元行列データである第１行列データは、２ｎ点を含み、各点のデータサイズがｍのデータとする。ｎが偶数の場合、例えば２ｎ／２行２ｎ／２列の行列データである。また、ｎが奇数の場合、例えば２ｎ／２＋０．５行２ｎ／２−０．５列の行列データである。例えば、ｎ＝９の場合、２９個（すなわち５１２個）のデータが、例えば３２行１６列状に配置されている。行列の各点にはｍｂｉｔのデータがある、例えば、各点のデータが１６ｂｉｔで量子化されたデジタルデータの場合、ｍは１６である。さらに、各点のデータが複素数の場合、ｍは１６ｂｉｔ×２＝３２ｂｉｔである。
【００１９】
２次元行列データを第１メモリ１０に記憶させる方法について説明する。第１メモリ１０は、ＦＦＴ演算する２次元行列データを全て記憶する容量を備えていない。一方、第２メモリ１２は、２次元行列データを全て記憶する容量を備えている。そこで、演算部２１は、２次元行列データを第２メモリ１２に記憶させる。図７は、演算部の行なうフローチャートを示す図である。図８（ａ）から図９（ｂ）は、第１メモリ１０および第２メモリ１２を示す模式図である。図８（ａ）のように、第１行列データＭ１は、２次元ＦＦＴ演算する２次元行列データである。第１行列データＭ１が入力部２２より入力する、または、第２メモリ１２内の領域に格納されている。図８（ａ）のように、第１行列データＭ１は、第２行列データＭ２１〜Ｍ２４に分割されている。第２行列データＭ２１〜Ｍ２４は、第１行列データＭ１の少なくとも１行の連続する行を含む第１行列データＭ１の一部のデータである。第２行列データＭ２１〜Ｍ２４は、それぞれ第１メモリ１０に格納可能なサイズである。また、第２行列データＭ２１〜Ｍ２４は、例えば互いに同じサイズである。第２行列データＭ２１〜Ｍ２４のサイズは互いに異なっていてもよい。
【００２０】
図８（ｂ）のように、演算部２１は、最初の第２行列データＭ２１を第１メモリ１０に記憶させる（ステップＳ３０）。演算部２１は、第２行列データＭ２１を第３行列データＭ３１〜Ｍ３４に分割する（ステップＳ３２）。第３行列データＭ３１〜Ｍ３４は、それぞれ、最小ビット数以上の大きさの行列データである。例えば、第２メモリ１２がＳＤＲＡＭの場合、データバス幅Ｗが最小ビット数Ｂｍｉｎである。ＳＤＲＡＭにおいては、転送する最初のアドレスを指定すれば、指定されたアドレスからデータバス幅Ｗ分の連続するアドレスのデータをアクセスすることができる。また、第２メモリ１２がＤＤＲ（Double Data Rate）  ＳＤＲＡＭの場合、データバス幅Ｗ×２（プリフェチ分）が最小ビット数Ｂｍｉｎである。この場合、１回のアクセス（例えば、１+回のアドレス指定）で、最小ビット数Ｂｍｉｎの連続するアドレスのデータをアクセスできる。さらに、第２メモリ１２がＤＤＲ２  ＳＤＲＡＭの場合、データバス幅Ｗ×４が最小ビット数Ｂｍｉｎであり、第２メモリ１２がＤＤＲ３  ＳＤＲＡＭの場合、データバス幅Ｗ×８が最小ビット数Ｂｍｉｎである。このように、最初のアドレスを指定することにより、最初のアドレスから連続するアドレスを有する最小ビット数のデータを読み出しまたは記憶するデータのアクセス方法は、バースト転送またはシーケンシャルアドレスアクセスと呼ばれている。
【００２１】
第３行列データの大きさＴｓｉｚｅとしては、最小ビット数Ｂｍｉｎ以上とすることができる。さらに、第３行列データの大きさＴｓｉｚｅは、最小ビット数Ｂｍｉｎの自然数倍であることが好ましい。第３行列データは、Ｔｐｏｉｎｔ＝Ｔｓｉｚｅ／ｍ（ｍは、前述の１点当りのデータサイズである）の点を有する。Ｔｐｏｉｎｔは２のべき乗であることが好ましい。例えば、Ｔｐｏｉｎｔ＝２ｎ３とする。この場合、ｎ３が偶数のとき、第３行列データは、例えば２ｎ３／２行２ｎ３／２列の行列となる。ｎ３が奇数のとき、第３行列データは、例えば２ｎ３／２＋０．５行２ｎ３／２−０．５列の行列となる。
【００２２】
図８（ｂ）のように、演算部２１は、第３行列データＭ３１〜Ｍ３４を各々行列転置させ、第３行列データｍ３１〜ｍ３４とする（ステップＳ３４）。図８（ｃ）のように、演算部２１は、第２行列データＭ２１を転置された第３行列データｍ３１〜ｍ３４単位で第２メモリ１２に記憶させる（ステップＳ３６）。演算部２１は、第２行列データが最後のデータか判断する（ステップＳ３８）。Ｙｅｓの場合、終了する。Ｎｏの場合、次の第２行列データＭ２２にインクリメントする（ステップＳ４０）。
【００２３】
図９（ａ）のように、演算部２１は、第２行列データＭ２２を第１メモリ１０に記憶させる（ステップＳ３０）。演算部２１は、第２行列データＭ２２を第３行列データＭ３５〜Ｍ３８に分割する（ステップＳ３２）。演算部２１は、第３行列データＭ３５〜Ｍ３８毎に行列転置し、第３行列データｍ３５〜ｍ３８とする（ステップＳ３４）。演算部２１は、第２行列データＭ２２を、第３行列データｍ３５〜ｍ３８毎に第２メモリ１２に記憶させる。図９（ｂ）のように、このようにして、第１行列データＭ１中の全ての第３行列データｍ３１〜ｍ３１６が行列転置され、第２メモリ１２に記憶される。
【００２４】
第２メモリ１２に記憶されている２次元行列データを１次元ＦＦＴ演算する方法について説明する。図１０は、演算部２１の行なうフローチャートを示す図である。図１１（ａ）から図１２（ｂ）は、第１メモリ１０および第２メモリ１２を示す模式図である。図１１（ａ）から図１２（ｂ）において、１次元ＦＦＴ演算したデータ領域をハッチングしている。演算部２１は、図９（ｂ）のように第２メモリ１２に格納されている第１行列データＭ１の一部を、図１１（ａ）のように、第３行列データ毎に第１メモリ１０に記憶させる（ステップＳ５０）。このとき、第１行列データＭ１が行列転置されるように、第４行列データｍ４１を第３行列データ単位で第１メモリ１０に記憶させる。図１１（ａ）のように、例えば、第３行列データｍ３１、ｍ３５、ｍ３９およびｍ３１３を第４行列データｍ４１として第１メモリ１０に記憶させる。第４行列データｍ４１の各行は、第１行列データＭ１が行列転置した行に対応する。すなわち、第４行列データｍ４１の１行目は、図８（ａ）の第１行列データＭ１の１列目に対応する。このように、第４行列データは、行列転置された第１行列データＭ１の少なくとも１行の連続する行を含む一部のデータである。
【００２５】
図１１（ｂ）のように、演算部２１は、第４行列データｍ４１の１行目を１次元ＦＦＴ演算する（ステップＳ５２）。演算部２１は、第４行列データｍ４１の最後の行か否かを判断する（ステップＳ５４）。Ｎｏの場合、次の行にインクリメントする（ステップＳ５６）。ステップＳ５２に進み、次の行を１次元ＦＦＴ演算する（ステップＳ５２）。ステップＳ５２においてＹｅｓの場合、図１１（ｃ）のように、第４行列データｍ４１の全ての行の１次元ＦＦＴ演算が終了している。図１２（ａ）のように、演算部２１は第４行列データｍ４１を第３行列データ単位で第２メモリ１２に記憶させる（ステップＳ５８）。
【００２６】
演算部２１は、最後の第４行列データかを判断する（ステップＳ６０）。Ｎｏの場合、次の第４行列データにインクリメントする（ステップＳ６２）。ステップＳ５０に進む。ステップＳ６０においてＹｅｓの場合、図１２（ｂ）のように、第１行列データｍ１の全ての行の１次元ＦＦＴ演算が終了している。演算部２１が図７および図１０の処理を行うことにより、図３の行列転置と１次元ＦＦＴ演算を行なうことができる。
【００２７】
実施例１によれば、演算部２１は、多次元の第１行列データをＦＦＴ演算する。図７のステップＳ３２およびＳ３４のように、演算部２１は、第２行列データを最小ビット数以上のサイズの行列データである第３行列データに分割し、第３行列データを各々行列転置させる。ステップＳ３６のように、演算部２１は、第２行列データを行列転置された第３行列データ単位で第２メモリ１２に記憶させる。図１０のステップＳ５０のように、演算部２１は、第１行列データが行列転置されるように、第３行列データ単位で第４行列データを第１メモリ１０に記憶させる。ステップＳ５２のように、演算部２１は、第１メモリ１０に記憶された第２行列データを１行単位でＦＦＴ演算する。
【００２８】
このように、第２行列データを第２メモリに１回のアクセスでアクセスできる最小ビット数以上のサイズの第３行列データに分割する。第２メモリ１２に、第２行列データを第３行列データ単位で格納する。また、第４行列データを第３行列データ単位で読み出す。これにより、例えばバースト転送を用い高速なデータ転送が行なうことができる。例えば、第１行列データの行列転置の際に、第２メモリ１２から第１行列データの全点をランダムアドレスアクセスする場合に比べ、第２メモリ１２へのアクセスを効率化できる。
【００２９】
第３行列データのサイズは前記最小ビット数の自然数倍であることが好ましい。これにより、例えば、バースト転送した場合に、使用しないデータをアクセスすることを抑制できる。
【００３０】
図１０のステップＳ５０において、演算部２１は、複数の第３行列データを連続するアドレスを用い第２メモリ１２から読み出し、第１メモリ１０に記憶させることが好ましい。例えば、第２メモリ１２の連続するアドレスに格納されている第３行列データを第２メモリ１２から第１メモリ１０に記憶させる。これにより、例えば、より多くのデータをバースト転送できる。よって、第２メモリ１２へのアクセスをより効率化できる。
【００３１】
図７のステップＳ３６において、演算部２１は、複数の第３行列データを連続するアドレスを用い第２メモリ１２から読み出せるように、第２行列データを第２メモリ１２に記憶させることが好ましい。
【実施例２】
【００３２】
実施例２は、実施例１の具体例である。実施例２においては、第２メモリ１２は、データバス幅Ｗが６４ｂｉｔのＤＤＲ２  ＳＤＲＡＭである。この場合、最小ビット数Ｂｍｉｎ＝６４ｂｉｔ×４＝２５６ｂｉｔである。第１行列データの点数２ｎ＝２１９＝５２４２８８であり、２１０＝１０２４行２９＝５１２列の行列である。１点あたりのデータサイズｍは１６ｂｉｔ×２＝３２ｂｉｔである。
【００３３】
図１３（ａ）および図１３（ｂ）は、第１行列データを示す模式図である。図１３（ａ）のように、第１行列データは、１０２４行５１２列の行列である。第１行列データＭ１の上の数は列の番号を、第１行列データＭ１の左の数は行の番号を示している。第１行列データＭ１内の数字は、点の番号を示している。点は０〜５２４２８７まであり、図１７まで、点の番号は共通して使用する。第０行の点を０〜５１１、第１行の点を５１２〜１０２３、第１０２３行の点を５２３７７６〜５２４２８７とする。
【００３４】
図１３（ｂ）を参照し、第３行列データＭ３１〜Ｍ３１２９の点数は、最小ビット数Ｂｍｉｎ×２／ｍ＝２５６×２／３２＝１６＝２４である。そこで、例えば、第３行列データを４行４列の行列とする。図７のステップＳ３０において、第１メモリ１０に転送する第２行列データＭ２１を、例えば第１行列データＭ１の４行分とする。第２行列データＭ２１は第３行列データＭ３１〜Ｍ３１２８に分割されている。
【００３５】
図１４（ａ）および図１４（ｂ）は、第１メモリ内の第３行列データを示す模式図である。図１４（ａ）を参照し、図７のステップＳ３０において、第２行列データＭ２１が第１メモリ１０に転送される。図１４（ｂ）のように、図７のステップＳ３４において、各第３行列データＭ３１〜Ｍ３１２８が行列転置され、それぞれ第３行列データｍ３１〜ｍ３１２８となる。例えば、第３行列データＭ３１の０行目の点０、１、２、３が行列転置された第３行列データｍ３１の０列目となる。第３行列データＭ３１の０列目の点０、５１２、１０２４、１５３６が行列転置された第３行列データｍ３１の０行目となる。
【００３６】
図１５は、ＳＤＲＡＭ内の領域を示す模式図である。図１５のように、第２メモリ１２はバンク０〜３を備えている。各バンクは行列（Row・Column）アドレスが０から順に付されている。１つの行列アドレスのデータサイズは、データバス幅Ｗのｂｉｔ数に対応する。すなわち、１つの行列アドレスを指定するとデータバス幅Ｗ＝６４ｂｉｔのデータを指定することとなる。実施例２においては、点のデータ数ｍ＝３２ｂｉｔである。したがって、１つの行列アドレスで２つの点のデータを記憶できる。例えば、図１５において、バンク０の行列アドレス０は、点０と５１２とのデータを格納できる。よって、１つの第３行列データ（４行×４行×３２ｂｉｔ）は８個の行列アドレスに格納できる。
【００３７】
図７のステップＳ３６において、第３行列データは、バンクアドレス０の行列アドレス０〜７に第３行列データｍ３１を格納する。次に、バンクアドレス１の行列アドレス０〜７に第３行列データｍ３２を格納する。このように、バンクアドレスを＋１（インクリメント）し、同じ行列アドレスに第３行列データを順に格納する。最後のバンクアドレス３に第３行列データｍ３４を格納した後、最初のバンクアドレス０に戻り、行列アドレスを＋２０４８し、第３行列データｍ３５を格納する。同様に、バンクアドレスが一巡する度に行列アドレスを＋２０４８し、第３行列データを格納する。最初の第２行列データＭ２１（第３行列アドレスｍ３１〜ｍ３１２８）を第２メモリ１２に格納した後、行列アドレスを＋８する。同様に次の第２行列データＭ２２の第３行列データｍ３１２９〜ｍ３２５６を格納する。以下、最後の第２行列データまで繰り返す。
【００３８】
図１６は、ＳＤＲＡＭ内の領域を示す模式図である。図１７（ａ）および図１７（ｂ）は、第１メモリ内の領域を示す模式図である。図１０のステップＳ５０において、ＳＤＲＡＭのバンクアドレス０および行列アドレス０から行列アドレス２０４７までを第４行列データｍ４１として第１メモリ１０に転送する。これにより、第３行列データｍ３１、ｍ３１２９…ｍ３３２６４１が連続して第１メモリ１０に転送される。このとき、１つの第３行列データを転送するたびに行列アドレスを＋８増加させることにより、第３行列データを連続して第１メモリ１０に転送できる。図１７（ａ）のように、第３行列データｍ１、ｍ３１２９…ｍ３３２６４１が第１メモリ１０に記憶される。第４行列データｍ４１の１行目のように、１行目の各点は、順に０、５１６、１０２４、１５３６、２０４８、２５６０、３０７２、３５８７…３２３７７６である。これは、図１３（ａ）に図示された第１行列データＭ１の第０列の各点に対応する。このように、第１メモリ１０には、図１３（ａ）に図示された第１行列データＭ１の第０列から第３列が行列転置され、第０行から第３行として格納される。
【００３９】
図１０のステップＳ５２において、図１７（ａ）の第４行列データｍ４１の各行を１次元ＦＦＴ演算することにより、図１３（ａ）の第１行列データＭ１を行列転置した行列の各行を１次元ＦＦＴ演算することができる。次に、バンクアドレス１とし、行列アドレス０から行列アドレス２０４７までを第４行列データｍ４２として第１メモリ１０に転送する。図１７（ａ）のように、第３行列データｍ３５、ｍ３１３３…ｍ３３２６４５が第１メモリ１０に記憶される。このように、バンクアドレスを＋１（インクリメント）し、同じ行列アドレスから第４行列データを第２メモリ１２から順に読み出す。第４行列データｍ４２の各行を１次元ＦＦＴ演算する。最後のバンクアドレス３から第４行列データｍ４４を読み出した後、最初のバンクアドレス０に戻り、行列アドレスを＋２０４８し、第４行列データを読み出す。同様に、バンクアドレスが一巡する度に行列アドレスを＋２０４８し、第４行列データを読み出す。以下、最後の第４行列データまで繰り返す。
【００４０】
実施例２によれば、演算部２１が第２行列データの同行の列順に複数の第３行列データを、第２メモリ１２の同行列アドレスにバンクアドレス順に記憶させる。例えば、図１５のように、第３行列データを同行の列順ｍ３１〜ｍ３４で第２メモリ１２の同行列アドレス０にバンクアドレス順０〜３に記憶させる。これにより、バンクアドレスを切り替えながら行列アドレスは変えずに第２行列データを第２メモリ１２に記憶できるため、オーバーヘッドを縮小できる。
【００４１】
また、演算部２１は、第２行列データの同列の次の行の第３行列データを第２メモリ１２の同じバンクアドレスの第３行列データのサイズに対応する次の行列アドレスに続き記憶させる。例えば、図１５のように、第２行列データの同列の次の行の第３行列データｍ３１２９を、同じバンクアドレス０の第３行列データのサイズに対応する次の行列アドレス８に続き記憶させる。これにより、図１０のステップＳ５０において、図１６のように、同じバンクアドレスの行列アドレス順に第３行列データを第１メモリ１０に転送することにより、図１７（ａ）のように、第１行列データを行列転置することができる。
【００４２】
このように、図１５において、第２行列データを格納する度に行列アドレスを増加させる＋８は、第３行列データのデータサイズ／ＳＤＲＡＭの１アドレスのサイズに対応する。例えば、第３行列データのサイズは、４×４×３２＝５１２ｂｉｔである。ＳＤＲＡＭの行列アドレスのサイズは、ＳＤＲＡＭのデータバス幅Ｗ＝６４ｂｉｔである。よって、第２行列データを格納する度に行列アドレスを５１２／６４＝８増加させればよい。
【００４３】
さらに、演算部２１は、第２行列データを第３行列データ単位で第２メモリ１２に記憶させる際に、バンクアドレスが一巡する度に、第４行列データのサイズに対応する次の行列アドレスに第３行列データを記憶させる。例えば、図１５において、バンクアドレスが一巡する度に増加させる行列アドレスは、＋２０４８である。これは、例えば第２行列データＭ２１を第２メモリ１２に記憶させた後に、次の第２行列データＭ２２を第２メモリに記憶させた際に、行列アドレスに隙間無くデータが埋まるための数字である。すなわち、第３行列データｍ３１、ｍ３１２９…ｍ３３２６４１が隙間無く埋まる行列アドレスである。これは、図１６のように第４行列データｍ４１のサイズに対応する。第４行列データｍ４１は、図１７（ａ）のように、図１３（ａ）に示した第１行列データＭ１の列（１０２４）×第３行列データの行（４）＝４０９６点を含んでいる。各点は、３２ｂｉｔであるから、第４行列データｍ４１のサイズは、１０２４×４×３２ｂｉｔである。一方、１つの行列アドレスのサイズは、６４ｂｉｔである。よって、バンクアドレスが一巡する度に増加させる行列アドレス１０２４×４×３２／６４＝２０４８である。これにより、図１６のように、第２メモリ１２に第４行列データを隙間無く埋めることができる。
【００４４】
このように、実施例２の一例においては、第２メモリ１２から第１メモリ１０に連続したアドレスを用いデータを転送することにより、ＳＤＲＡＭライトアクセス効率を４０％にすることができる。仮に、第１行列データの行列転置を全てランダムアクセスで行なう場合、ＳＤＲＡＭライトアクセス効率は１％である。さらに、第２行列データを第２メモリ１２に記憶する際に、オーバーヘッドを縮小できる効果を加えると、ＳＤＲＡＭライトアクセス効率を６０％にすることができる。
【００４５】
実施例１および実施例２において、２次元ＦＦＴ演算を例に説明したが、多次元ＦＦＴ演算でもよい。
【００４６】
以上、本発明の実施例について詳述したが、本発明は係る特定の実施例に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【００４７】
実施例１および２を含む実施形態に関し、さらに以下の付記を開示する。
付記１：多次元の第１行列データをＦＦＴ演算する演算部と、前記第１行列データの少なくとも１行の連続する行を含む一部のデータである第２行列データを記憶する第１メモリと、１回のアクセスでアクセスできる最小ビット数を有し、前記第１行列データを記憶する第２メモリと、を具備し、前記演算部は、前記第２行列データを前記最小ビット数以上のサイズの行列データである第３行列データに分割し、前記第３行列データを各々行列転置させ、前記第２行列データを行列転置された前記第３行列データ単位で前記第２メモリに記憶させ、前記第１行列データが行列転置されるように、行列転置された前記第１行列データの少なくとも１行の連続する行を含む一部のデータである第４行列データを前記第３行列データ単位で前記第２メモリから前記第１メモリに記憶させ、前記第１メモリに記憶された前記第４行列データを１行単位でＦＦＴ演算することを特徴とする演算装置。
付記２：前記第３行列データのサイズは前記最小ビット数の自然数倍であることを特徴とする付記１記載の演算装置。
付記３：前記演算部は、複数の前記第３行列データを連続したアドレスで前記第２メモリから読み出せるように、前記第２行列データを転置された前記第３行列データ単位で前記第２行列データを前記第２メモリに記憶させることを特徴とする付記１または２記載の演算装置。
付記４：前記第２メモリはＳＤＲＡＭであり、前記演算部は、前記第２行列データの同行の列順に複数の前記第３行列データを、前記第２メモリの同行列アドレスにバンクアドレス順に記憶させることを特徴とする付記１から３のいずれか一項記載の演算装置。
付記４：前記演算部は、前記第２行列データの同列の次の行の前記第３行列データを前記第２メモリの同じバンクアドレスの前記第３行列データのサイズに対応する次の行列アドレスに続き記憶させることを特徴とする付記４記載の演算装置。
付記６：前記第３行列データのサイズに対応する行列アドレスは、第３行列データのサイズ／データバス幅であることを特徴とする付記５記載の演算装置。
付記７：前記演算部は、前記第２行列データを前記第３行列データ単位で前記第２メモリに記憶させる際に、バンクアドレスが一巡する度に、前記第４行列データのサイズに対応する次の行列アドレスに前記第３行列データを記憶させることを特徴とする付記５記載の演算装置。
付記８：前記第４行列データのサイズに対応する行列アドレスは、前記第１行列データの列数×前記第３行列データの行数×各行列の１点当りのデータサイズ／データバス幅であることを特徴とする付記７記載の演算装置。
付記９：演算装置が多次元の第１行列データをＦＦＴ演算する演算方法であって、前記第１行列データの少なくとも１行の連続する行を含む一部のデータである第２行列データを、前記第１行列データを記憶する第２メモリに１回のアクセスでアクセスできる最小ビット数以上のサイズの行列データである第３行列データに分割し、前記第３行列データを各々行列転置させるステップと、前記第２行列データを行列転置された前記第３行列データ単位で前記第２メモリに記憶させるステップと、前記第１行列データが行列転置されるように、行列転置された前記第１行列データの少なくとも１行の連続する行を含む一部のデータである第４行列データを前記第３行列データ単位で前記第２メモリから第１メモリに記憶させるステップと、前記第１行列データを１行単位でＦＦＴ演算するステップと、
を含むことを特徴とする演算方法。
付記１０：多次元の第１行列データをＦＦＴ演算するプログラムであって、前記第１行列データの少なくとも１行の連続する行を含む一部のデータである第２行列データを、前記第１行列データを記憶する第２メモリに１回のアクセスでアクセスできる最小ビット数以上のサイズの行列データである第３行列データに分割し、前記第３行列データを各々行列転置させ、前記第２行列データを行列転置された前記第３行列データ単位で前記第２メモリに記憶させ、前記第１行列データが行列転置されるように、行列転置された前記第１行列データの少なくとも１行の連続する行を含む一部のデータである第４行列データを前記第３行列データ単位で前記第２メモリから第１メモリに記憶させ、前記第１行列データを１行単位でＦＦＴ演算する処理を、コンピュータに実行させるプログラム。
【符号の説明】
【００４８】
１０            第１メモリ
１２            第２メモリ
２１            演算部
【図１】
0005654373.tif 000002
【図２】
0005654373.tif 000003
【図３】
0005654373.tif 000004
【図４】
0005654373.tif 000005
【図５】
0005654373.tif 000006
【図６】
0005654373.tif 000007
【図７】
0005654373.tif 000008
【図８】
0005654373.tif 000009
【図９】
0005654373.tif 000010
【図１０】
0005654373.tif 000011
【図１１】
0005654373.tif 000012
【図１２】
0005654373.tif 000013
【図１３】
0005654373.tif 000014
【図１４】
0005654373.tif 000015
【図１５】
0005654373.tif 000016
【図１６】
0005654373.tif 000017
【図１７】
0005654373.tif 000018