(57)【要約】【課題】  バタフライ演算に用いられる係数のデータサイズを大幅に削減し、信頼性の高い高速演算を行う。【解決手段】  バタフライ演算図の右側において、１段目では、全体の１／４毎に４回ループ処理が行われる。後ろの３つのループ処理では、正しい係数を掛けるための調整が必要となる。結局、係数データは約１／４となる。なお、１段目は４つのループを融合（一括処理）すれば、１つの係数を４回使用することができる。２段目は、２つのループを融合すれば、１つの係数を４回使用することができる。したがって、処理が高速化される。【選択図】  図７ 
2005071300.tif 000002
【特許請求の範囲】
【請求項１】
バタフライ演算に用いる係数をデータキャッシュメモリ格納可能なデータサイズよりも小さくなるように減縮し、前記バタフライ演算を実行することを特徴とするＦＦＴ演算方法。
【請求項２】
請求項１記載のＦＦＴ演算方法において、
前記係数は、テーブルとして不揮発性メモリに格納されることを特徴とするＦＦＴ演算方法。
【請求項３】
請求項１記載のＦＦＴ演算方法において、
前記係数は、ＦＦＴ演算初期化時に揮発性メモリに格納することを特徴とするＦＦＴ演算方法。
【請求項４】
請求項１記載のＦＦＴ演算方法において、
前記係数は、加法定理を用いてデータサイズを減縮することを特徴とするＦＦＴ演算方法。
【請求項５】
請求項１記載のＦＦＴ演算方法において、
前記係数は、加法定理を用いてデータサイズを減縮し、
前記係数は、前記係数と演算データとを前記データキャッシュメモリに格納することが可能なデータサイズまで減縮することを特徴とするＦＦＴ演算方法。
【請求項６】
バタフライ演算に用いる係数をデータキャッシュメモリ格納可能なデータサイズよりも小さくなるように減縮して前記バタフライ演算を実行し、前記係数は、加法定理を用いてデータサイズを減縮することを特徴とするＦＦＴ演算方法。
【請求項７】
請求項６記載のＦＦＴ演算方法において、
前記係数は、テーブルとして不揮発性メモリに格納されることを特徴とするＦＦＴ演算方法。
【請求項８】
請求項６記載のＦＦＴ演算方法において、
前記係数は、ＦＦＴ演算初期化時に揮発性メモリに格納することを特徴とするＦＦＴ演算方法。
【請求項９】
バタフライ演算に用いる係数をデータキャッシュメモリ格納可能なデータサイズよりも小さくなるように減縮して前記バタフライ演算を実行し、前記係数は、加法定理を用いてデータサイズを減縮し、前記係数は、前記係数と演算データとを前記データキャッシュメモリに格納することが可能なデータサイズまで減縮することを特徴とするＦＦＴ演算方法。
【請求項１０】
請求項９記載のＦＦＴ演算方法において、
前記係数は、テーブルとして不揮発性メモリに格納されたことを特徴とするＦＦＴ演算方法。
【請求項１１】
請求項９記載のＦＦＴ演算方法において、
前記係数は、ＦＦＴ演算初期化時に揮発性メモリに格納することを特徴とするＦＦＴ演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＦＦＴ（高速フーリエ変換、ＦＦＴ：Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）演算技術に関し、特に、バタフライ演算に用いられる係数におけるデータサイズの減縮に適用して有効な技術に関するものである。
【背景技術】
【０００２】
近年、携帯電話の高性能化、高機能化などに伴い、マイクロコンピュータなどの半導体集積回路装置にも高い信号処理能力が要求されているものが増えている。
【０００３】
信号処理の代表例は離散フーリエ変換（ＤＦＴ）であり、この高速算法が高速フーリエ変換である。
【０００４】
たとえば、半導体集積回路装置において高速フーリエ変換による高速算法を実現する命令として、線形変換命令（ＦＴＲＶ：Ｆｌｏａｔｉｎｇ−ｐｏｉｎｔ  Ｔｒａｎｓｆｏｒｍ  Ｖｅｃｔｏｒ）がある。
【０００５】
線形変換命令は、たとえば、ＸＭＴＲＸ（単精度浮動小数点拡張レジスタ行列）で示される、浮動小数点レジスタＸＦ０からＸＦ１５の内容を４行４列の行列として、ＦＶｎなどで示される、浮動小数点レジスタＦＲ（ｎ）から（ｎ＋３）の内容を４次元のベクトルとして、行列とベクトルとの乗算を行い、その結果を該ＦＶｎに格納する。
【０００６】
なお、特開２００２−１６９７９２号公報（特許文献１参照）には、高速フーリエ変換における加法定理を用いたバタフライ演算技術について記載されている。
【特許文献１】特開２００２−１６９７９２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところが、上記のような半導体集積回路装置における高速フーリエ変換による信号処理技術では、次のような問題点があることが本発明者により見い出された。
【０００８】
線形変換命令による高速算法を用いる場合には、大量の定数データが必要である。したがって、定数データの点数が少ない（たとえば、２５６点）場合には有効であったが、点数が増えて、たとえば、１０２４点程度になるとキャッシュ容量が不足してしまいキャッシュミスが多発し、信号処理が困難になってしまうという問題がある。
【０００９】
本発明の目的は、係数に用いられる定数データを大幅に削減し、信頼性の高い高速演算を行うことのできる高速フーリエ変換演算技術を提供することにある。
【００１０】
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１１】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。
【００１２】
本発明ＦＦＴ演算方法は、バタフライ演算に用いる係数をデータキャッシュメモリ格納可能なデータサイズよりも小さくなるように減縮し、該バタフライ演算を実行するものである。
【００１３】
また、本願のその他の発明の概要を簡単に示す。
【００１４】
本発明ＦＦＴ演算方法は、バタフライ演算に用いる係数をデータキャッシュメモリ格納可能なデータサイズよりも小さくなるように減縮して該バタフライ演算を実行し、係数は、加法定理を用いてデータサイズを減縮するものである。
【００１５】
また、本発明ＦＦＴ演算方法は、バタフライ演算に用いる係数をデータキャッシュメモリ格納可能なデータサイズよりも小さくなるように減縮して該バタフライ演算を実行し、係数は、加法定理を用いてデータサイズを減縮し、該係数は、係数と演算データとをデータキャッシュメモリに格納することが可能なデータサイズまで減縮するものである。
【発明の効果】
【００１６】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。
【００１７】
（１）バタフライ演算に用いる係数のデータサイズを大幅に削減することができるので、少ないキャッシュ容量で高速に信号処理を実行することができる。
【００１８】
（２）また、上記（１）により、キャッシュミスなどを防止することができ、半導体集積回路装置の性能、および信頼性を大幅に向上させることができる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。
【００２０】
図１は、本発明の一実施の形態による半導体集積回路装置のブロック図、図２は、図１の半導体集積回路装置による高速フーリエ変換演算法の説明図、図３は、図２の高速フーリエ変換演算法などの乗算演算を対角行列で表現した図、図４は、図３の対角表列をデータ量を減少させるために変形した対角行列の等式を示す図、図５は、図３の対角表列をデータ量を減少させるために変形した対角行列の他の例の等式を示す図、図６は、バタフライ演算を２段目まで示した図、図７は、１６点ＦＦＴの場合におけるバタフライ演算図、図８は、図７のバタフライ演算の一つを行列表現した図、図９は、図１の半導体集積回路装置のＦＦＴ演算処理プログラムの骨格の一例を示す図、図１０は、図９のプログラムによるＦＦＴ演算時のクロック数の説明図、図１１は、図９のバタフライ演算における実行段毎のデータ参照位置を示した図である。
【００２１】
本実施の形態において、半導体集積回路装置１は、たとえば、マイクロプロセッサなどからなり、命令実行部２、命令キャッシュ３、およびデータキャッシュ（データキャッシュメモリ）４などを備える。この半導体集積回路装置１には、外部バスを介してＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などの主メモリ５が接続されている。
【００２２】
主メモリ５は、命令格納領域５ａとデータ格納領域５ｂとを有する。命令格納領域５ａには、命令実行部２が実行する命令が格納されており、データ格納領域５ｂには、命令実行部２が用いるオペランドデータが格納されている。
【００２３】
命令実行部２は、命令キャッシュ３、ならびにデータキャッシュ４が内部バスを介してそれぞれ接続されている。命令キャッシュ３は、主メモリ５から読み出した命令実行部２への命令を一時的に格納し、該命令を高速に命令実行部２に供給する。
【００２４】
データキャッシュ４は、主メモリ５から読み出した命令実行部２へのオペランドデータなどを一時的に格納し、該オペランドデータを高速に命令実行部２に供給する。命令実行部２は、命令キャッシュ３、およびデータキャッシュ４にアクセスし、演算処理を実行する。
【００２５】
次に、半導体集積回路装置１による線形変換命令ＦＴＲＶを用いた高速フーリエ変換（以下、ＦＦＴという）におけるバタフライ演算法についてについて説明する。
【００２６】
まず、ＦＦＴについて、図２を用いて説明する。
【００２７】
最初、配列要素の配置替えを行う。配列要素の要素インデックスにおけるビットパターンの左右を反転したビットパターンの要素インデックスの場所に、配列要素を配置替えする。
【００２８】
たとえば、ｘ［８］はｘ［１］の場所に置き、ｘ［１］はｘ［８］の場所に置く。その後、ｆｆｔ１，ｆｆｔ２，ｆｆｔ３，ｆｆｔ４と順次、バタフライ演算を行うと、その時点の配列内容がＦＦＴの出力となる。
【００２９】
図３は、対角行列を２つ示した図である。この図３において、これらを、［ｘ０，ｘ１，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７］ｔに作用（ｔは転置行列化）させたものを以下に示す。
［ｗ＾０＊ｘ０，ｗ＾１＊ｘ２，ｗ＾２＊ｘ２，ｗ＾３＊ｘ３，ｗ４＾＊ｘ４，ｗ５＾            ＊ｘ５，ｗ＾６＊ｘ６，ｗ＾７＊ｘ７］ｔ    ・・・（Ａ）左の行列
［ｗ＾０＊ｘ０，ｗ＾４＊ｘ１，ｗ＾２＊ｘ２，ｗ＾６＊ｘ３，ｗ＾１＊ｘ４，ｗ＾５          ＊ｘ５，ｗ＾３＊ｘ６，ｗ＾７＊ｘ７］ｔ    ・・・（Ｂ）右の行列
（Ａ）において、データ量を半分にするやり方について検討する。（Ａ）のかけ算を対角行列で考え、その対角表列を、図４に示すように変形する。これにより、データ量が半分になる。ただし、演算量は１．５倍程度になる。
【００３０】
もっとデータ量を減らす場合について以下に述べる。
【００３１】
Ｎ点の時、ｎ１＝ｒｏｏｔ２（Ｎ）程度のｎ１を求め、また、ｎ２＝Ｎ／ｎ１とする。そして、ｎ１個の｛ｗ＾ｉ｝とｎ２個の｛ｗ＾ｊ｝とを用意して２フェーズで計算すればよい。
【００３２】
Ｎ＝８の場合、ｎ１＝４個の｛ｗ＾１，ｗ＾２，ｗ＾３｝とｎ２＝２個の｛ｗ＾０，ｗ＾４｝であったが、Ｎ＝１０２４点の場合は、ｎ１＝３２個の｛ｗ＾０，ｗ＾１，．．．Ｗ＾３１｝とｎ２＝３２個の｛ｗ＾０，ｗ＾３２，ｗ＾６４，．．．ｗ＾９９２｝でよい。
【００３３】
結局、定数データｗ＾ｉの個数は、Ｎから２＊ｒｏｏｔ２（Ｎ）に大幅に削減されることになる。これにより、処理の手間は、１フェーズから２フェーズになり、そのオーバヘッドが増えることになるが、データキャッシュ４の浪費を大幅に削減することができる。
【００３４】
また、定数データを再利用することができるので、線形変換命令ＦＴＲＶを使用することが可能となり、処理速度を大幅に向上させることができる。さらに、ｗ＾４が−１やｉなら、２番目のフェーズは省略できる可能性が高い。
【００３５】
次に、図５は、（Ｂ）のかけ算を対角行列で考えて、その対角行列を変形したものである。
【００３６】
図示するように、以降（Ａ）と同じやり方が適用できることは明らかである。ただし、ｗ＾４が−１やｉなら、２番目のフェーズは省略できる可能性が高い。
【００３７】
また、図６は、バタフライ演算における等式を２つ示した図である。
【００３８】
図６の上側等式の左辺には、図２の関数ｆｆｔ１（）に対応している。この等式の右辺には、ｆｆｔ１（）の定数を少し調整したバタフライ演算を行い、その後、下半分の値を調整すればよいことを示している。以下、こういうやり方の関数をｍ＿ｆｆｔ１（）という。図６下側の等式は、上側の等式に転置を施したものである。
【００３９】
図７は、１６点の場合におけるＦＦＴ演算図の最初の方を示している。
【００４０】
図７の左側が、対策前の１６点ＦＦＴの２段目までに対応し、図７右側が対策後である。対策後の１段目では、全体の１／４毎に４回ループ処理が行われる。後ろの３つのループ処理では、正しい係数を掛けるための調整が必要となる。結局、係数データは約１／４となる。
【００４１】
なお、１段目は４つのループを融合（一括処理）すれば、１つの係数を４回使用することができる。２段目は、２つのループを融合すれば、１つの係数を４回使用することができる。したがって、処理が高速化され、後続の余分な調整（たとえば、ｗ＾２などをかけること）処理の追加時間と相殺することができる。
【００４２】
図７中の個別のバタフライは、図８に示す行列表現とすることができる。
【００４３】
従って、この４＊４行列を裏レジスタ（ＦＴＲＶ命令の暗黙オペランドとなるレジスタ）１６本に載せた状況では、４クロックピッチにＦＴＲＶ命令を発行できる。別にデータ４つのロードとストアが必要であるが、１度に２つロードする命令やストアする命令を使用すれば、パイプラインを構成(ソフトウエアパイプライニング)して、ちょうど４クロックピッチでバタフライ演算をおこなうことが可能となる。ＦＦＴの後ろの方の段では裏レジスタに格納したｃｏｓ，ｓｉｎ(Ｗの実数部、虚数部)の値を何度も使用するので、４クロックピッチに近い速度を実現できる。
【００４４】
しかし、ＦＦＴの前の方の段では問題がある。それは、個別のｃｏｓ，ｓｉｎの値を使用する回数が少ないことに起因する。
【００４５】
例えば、１０２４点のＦＦＴを考える。バタフライの最初の段のｆｆｔ１（）においては、ｗ＝ｅｘｐ（−２πｉ／１０２４）として、以下の値系列
｛  ｗ＾０，ｗ＾２５６，ｗ＾１２８，ｗ＾３８４，…  ｝
を各々１回ずつ順次に使用していく。裏レジスタへの値のロードを速くするには、ロードすべき値をそのまま表の形で用意しておけばいい。すると２要素ロード命令を使用すれば４クロック(正確には４命令)でロード可能となる。具体的に示せば、右がロードすべき値、左がロード対象レジスタ（ＸＦｉ）である。
【００４６】
［  ｃｏｓ  −ｓｉｎ  −ｃｏｓ  ｓｉｎ  ］  ［ＸＦ２  ＸＦ６  ＸＦ１０  ＸＦ１４］
［ｓｉｎ  ｃｏｓ  −ｓｉｎ  −ｃｏｓ］  ［ＸＦ３  ＸＦ７  ＸＦ１１  ＸＦ１５］
従って、｛ｃｏｓ，ｓｉｎ，−ｓｉｎ，ｃｏｓ，−ｃｏｓ，−ｓｉｎ，ｓｉｎ，−ｃｏｓ｝を用意しておいて、ペアロード命令（浮動小数点レジスタ２本分への転送命令）を４命令でＸＦ２−ＸＦ３，ＸＦ６−ＸＦ７，ＸＦ１０−ＸＦ１１，ＸＦ１４−ＸＦ１５にロードすればいい。
【００４７】
これで、裏レジスタへのロードの問題が少し緩和される。しかし、別の問題を引き起こす。今度は、定数データの数が４倍に増加するからである。従って、本発明の係数データ数の削減策が有効となる。
【００４８】
以上、説明したバタフライ演算法をｃｏｍｐｌｅｘＦＦＴ１０２４に適用した場合ついて説明する。
【００４９】
図９は、本発明者が検討した半導体集積回路装置１に用いられるバタフライ演算処理におけるプログラムである。
【００５０】
コメント内のバイトの値は、データサイズ、または命令サイズを示す。コメント内のクロック数は、個別プログラムがキャッシュミスなしで動作したとする場合の期待クロック数を示している。
【００５１】
また、ここでは、話を簡単にするために、命令キャッシュ３、およびデータキャッシュ４におけるキャッシュサイズは、いずれも３２ｋＢとする。また、キャッシュミスのペナルティは３２クロックとする。
【００５２】
キャッシュが空であった状況で、ｃｏｍｐｌｅｘＦＦＴ１０２４が処理し始めると、図９のプログラムにおけるコメント内の値をすべて足した値が期待クロック数となる。データを１度データキャッシュ４へフェッチすればキャッシュミスは発生しない。これは、キャッシュミスのペナルティはちょうどフェッチのバイト数と同じと仮定しているからである。
【００５３】
以上、説明したことから、想定、または状況が少し変化した場合のクロック数を計算することができることになる。そういう計算をしたものを図１０に示す。
【００５４】
図１０の左側は、適用前の値を示している。’初期’欄は、データキャッシュ４が空であったとした場合のクロック値である。次の’ｄａｔａ’欄は、入力配列が直前に設定されていてキャッシュに格納されていた場合のクロック値である。
【００５５】
次の’ｐ＿ｓｉｚｅ’欄は、命令コード全体もキャッシュに格納されていたとした場合のクロック値である。また、’１／２ｃｓ’欄は、ｃｏｓｓｉｎ［］の半分もキャッシュに格納されていたとした場合のクロック値である。最後の’ａｌｌ’欄は、すべてがキャッシュに格納されていたキャッシュミスなしの場合のクロック値である。なお、ｆｆｔ１（）よりもｍ＿ｆｆｔ１の方が時間がかかるとしてあるが、実際にはｆｆｔ１（）が速くなる可能性もある。
【００５６】
また、図１０の右側は、ｆｆｔ１（），ｆｆｔ２（）を修正してｃｏｓｓｉｎ（）を４ｋＢとした場合の期待値を示している。この図１０右側における、’初期’欄、’ｄａｔａ’欄、’ｐ＿ｓｉｚｅ’欄、および’ａｌｌ’欄のそれぞれの意味は、図１０左側と同じである。
【００５７】
図示するように、’初期’欄、や’ｄａｔａ’欄においては、演算速度が向上していることが分かる。しかし、すべてがキャッシュに格納されている状況の場合には、少し速度が低下することを示している。
【００５８】
この場合、たとえば、データアクセスでスラッシングが発生するような状況においては、大いに有効となる。
【００５９】
図１１は、実行段（フェーズ）毎のデータ参照位置（テーブル）を示した図である。図１１の右側は適用前、左側は適用後をそれぞれ示している。また、図１１の中央部の矩形はキャッシュであり、ここでは、たとえば、１６ｋＢとしてある。
【００６０】
図１１において、適用前のコードでＦＦＴ２０４８を実行した際には、かなりスラッシングすることが分かる。一方、適用後においては、ｃｏｓｓｉｎ［］配列などを１／８や１／１６程度とすることができるので、すべてがキャッシュに格納されている状況となっている。
【００６１】
それにより、本実施の形態１によれば、定数データを大幅に削減することができるので、演算処理を高速化することが可能となり、半導体集積回路装置１の信号処理能力を向上させることができる。
【００６２】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【図面の簡単な説明】
【００６３】
【図１】本発明の一実施の形態による半導体集積回路装置のブロック図である。
【図２】図１の半導体集積回路装置による高速フーリエ変換演算法の説明図である。
【図３】図２の高速フーリエ変換演算法などの乗算演算を対角行列を表現した図である。
【図４】図３の左側の対角行列をデータ量を減少させるために変形した対角行列の等式を示す図である。
【図５】図３の右側の対角行列をデータ量を減少させるために変形した対角行列の他の例の等式を示す図である。
【図６】バタフライ演算における等式を示した図である。
【図７】１６点ＦＦＴの場合におけるバタフライ演算を２段まで示した図である。
【図８】図７のバタフライ演算の一例を行列表現した図である。
【図９】図１の半導体集積回路装置に用いられるＦＦＴ演算処理プログラムの骨格の一例を示す図である。
【図１０】図９のプログラムによるＦＦＴ演算時のクロック数の説明図である。
【図１１】図９のＦＦＴ演算における実行段毎のデータ参照位置を示した図である。
【符号の説明】
【００６４】
１  半導体集積回路装置
２  命令実行部
３  命令キャッシュ
４  データキャッシュ（データキャッシュメモリ）
５  主メモリ
５ａ  命令格納領域
５ｂ  データ格納領域
【図１】
2005071300.tif 000003
【図２】
2005071300.tif 000004
【図３】
2005071300.tif 000005
【図４】
2005071300.tif 000006
【図５】
2005071300.tif 000007
【図６】
2005071300.tif 000008
【図７】
2005071300.tif 000009
【図８】
2005071300.tif 000010
【図９】
2005071300.tif 000011
【図１０】
2005071300.tif 000012
【図１１】
2005071300.tif 000013