« Cosmo-Zの32ch版用のアルミケースを作りました・・と思ったら | トップページ | Cosmo-Zのアクリルケース入り »

2016.01.23

FPGA向きのFFTアルゴリズム

今、FPGAでハードウェアFFTを行わなければならない案件を2つ抱えています。そのうちの1つは、65536ポイント~1Mポイント程度のFFTをつなぎ目なく行うというものです。

FFTのアルゴリズムですが、もっとも基本的な基数2のCooley-Tukeyアルゴリズムを考えてみます。

Fft1_3

これは基数2の16ポイントFFTなので、ステージ0,1,2,3と4つあります。

ごく普通のFFTなのですが、これを65536ポイントや1Mポイントでやろうとした場合、厄介なことが生じます。それは、FFTする途中経過のデータを格納するアドレスが連続しないという問題です。

最初のステージでは、データの0と1、2と3・・を演算します。

次のステージでは、データの0と2、1と3・・を演算します。

・・

だんだんバラバラになってきます。

1Mポイントとかとなると、

・アドレス0とアドレス524288を計算
・アドレス1とアドレス524289を計算
・アドレス2とアドレス524290を計算

という風に、読み出す場所がかなり離れてしまいます。

プログラムで書くと、

int b = 2;
for (stage = 0; stage < N; stage++) {
  for (i = 0; i < DataLength / b; i++) {
    int offset = b * i;
    for (j = 0; j < b / 2; j++) {
    	Complex A = mem[offset + j];
      Complex B = mem[offset + j + b / 2] * W[j * DataLength / b];
      mem[offset + j] = A + B;
      mem[offset + j + b / 2] = A - B;
    }
  }
  b = b * 2;
}

このようになります。アドレスが飛ぶところをbという変数にしていますが、ややこしいですね。シーケンシャルではなく、ランダムアクセスになってしまいます。

FPGA内のBRAMに収まるサイズのFFTなら無理やりできますが、1Mポイントだと内蔵BlockRAMに納まらないのでDDR3などの外部メモリを使うことになります。

DDR3メモリはランダムアクセスが苦手です。つまり、通常のFFTのアルゴリズムでは大きなサイズのFFTがやりにくくなります。

sun

そこで、私が提案するのは、以下のようなアルゴリズムです。VFFTと呼びます。

Fft2

VFFTは、普通のCooley-Tukeyのアルゴリズムとやっていること同じなのですが、計算のフローをねじった形になっています。

このFFTでは、データの読み書きするアドレスが独特です。

  • アドレス0とアドレス1のデータを演算→アドレス0とアドレス8に格納
  • アドレス2とアドレス3のデータを演算→アドレス1とアドレス9に格納
  • アドレス4とアドレス5のデータを演算→アドレス2とアドレス10に格納
    ・・・
  • アドレス12とアドレス13のデータを演算→アドレス6とアドレス14に格納
  • アドレス14とアドレス15のデータを演算→アドレス7とアドレス15に格納

と、連続した番地へメモリアクセスができます

計算結果は2本のFIFOを用意すれば、256バイト程度に分けて、連続したアドレスに書き込みができます。

それに嬉しいことにステージが変わっても、読み書きするアドレスは変わらないので、メモリの読み書きアドレスを計算するためのロジックが軽くてすみます。

プログラムで書くと、

Complex *work = new Complex[DataLength];
int mask = ~((2 << (N-2))-1);
for (stage = 0; stage < N; stage++) {
  int offset = DataLength/2;
  for (j = 0; j < DataLength / 2; j++) {
    Complex A = mem[j*2];
    Complex B = mem[j*2+1] * W[j & mask];
    work[j] = A + B;
    work[j + DataLength/2] = A - B;
  }
  mask = mask >> 1;
  for (j = 0; j < DataLength; j++) {
    mem[j] = work[j];
  }
}
delete[] work;

と、元のFFTは3重のループだったのが、2重のループになっていることがわかります。

メリットは、

  • メモリが連続アクセスできる
  • ステージが変わってもアドレスの生成規則が変わらない

ということで、FPGA向きだと思います。

欠点は、メモリの読み書きアドレスが異なるので、ワークメモリ用に2倍のメモリを使うことです。

メモリの必要量が2倍になっても気にならない場合には、ぜひ、検討してみてください。

|

« Cosmo-Zの32ch版用のアルミケースを作りました・・と思ったら | トップページ | Cosmo-Zのアクリルケース入り »

コメント

コメントを書く



(ウェブ上には掲載しません)




« Cosmo-Zの32ch版用のアルミケースを作りました・・と思ったら | トップページ | Cosmo-Zのアクリルケース入り »