はじめに
FPGAなどで画像処理などをしているとヒストグラム集計など統計情報を計算したくなる時があります。
そこでCPUの設計などで用いられるフォワーディングというテクニックを用いて、インターロックなしでメモリに値を集計するモジュールの説明をします。
RTLレベルでの話になりますが、ひょっとすると高位合成言語でも知っていればボトルネック除去に役立つケースがあるかもしれません。
やりたいこと
やりたい演算をC言語で書くと下記のようになります。
int mem[256];
void accumulate_to_mem(int addr, int data)
{
mem[addr] += data
}
使い方としては例えば画像データの輝度ヒストグラムが欲しければ
memset(mem, 0, sizeof(mem));
for (int y = 0; y < height; ++y) {
for (int x = 0; x < width; ++x) {
accumulate_to_mem(image[y*width + x], 1);
}
}
のような感じの集計がやりたいわけです。
ここで accumulate_to_mem と同じ動作をするものをFPGAに効率よく実行するにはどういうRTLを実装すればいいかというのが今回の内容です。
何が課題なのか
やりたい演算は
mem[addr] += data
といういたってシンプルな計算ですが、ここには3つの要素が含まれています。
いわゆる Read-Modify-Write という動作パターンになります。
- メモリから値を読み出す
- 値を加算する
- 結果を書き戻す
この時にFPGAは1サイクルに1つの処理しかできません。
もちろん1個のデータ毎に3サイクルかけて計算しても良いのですが、しばし1サイクルに1データのスループットが必要になります。
そこでこの３つの演算を３ステージとしてパイイプライン的に計算したくなります。
しかしながらその際に、同じメモリアドレスに対する演算が3サイクル中に2つ以上出てくると、
まだ先行する書き込まれていない古いデータを元に計算してしまう
ということが起こります。
いわゆるRAW(read after write)ハザードと呼ばれるものです。
解決方法
解決方法は大きく2つ考えられます。
- ハザードが発生しそうになったら書き込み完了まで後続を待たせる(インターロック)
- 書き込み完了前の先行するパイプラインからデータを取得してくる(フォワーディング)
今回は後者のフォワーディングを行います。
フォワーディングの動作
下記が、フォワーディングを加味したパイプラインの動作図です。
3つの処理ステージに対して、1つ先、または2つ先のステージで同じメモリアドレスに対して処理を行っていた場合にその値を使うことで整合をとります。
コード紹介
だいぶ前に書いたコードですが、このテクニックを使ったVerilogで書いた集計モジュールのコードがこちらとなります。
コードの全体としては、FPGAのデュアルポートRAMを用いて、片方のポートを1ステージ目のREADに、もう片方を3ステージ目のWRITEに割り当てています。
また、メモリの読出しやクリアの為に片方のポートを横取りして、ダイレクトにアクセスできる機能も付与しております。
ソースコード(L114)の読み出しステージの段階で
st1_fw_st2 <= st0_valid && st1_valid && (st0_addr == st1_addr);
st1_fw_st3 <= st0_valid && st2_valid && (st0_addr == st2_addr);
として、先行するステージが有効でかつ同じ同じアドレスかどうかを見ておき
ソースコード(L75)の部分で、メモリ読み出しの結果を
always @* begin
st1_rdata = st1_dout;
if ( st1_fw_st3 ) begin st1_rdata = st3_data; end
if ( st1_fw_st2 ) begin st1_rdata = st2_data; end
end
のように上書きしています。
おわりに
最近は高位合成などの進歩も著しいので、いずれこのようなことを気にしなくてもよいようになってくるのかもしれませんが、並列プログラミングでもっと大きな単位でソフトウェアパイプラインを組む場合などでも概念としては同じですし、知っておくと案外応用の効く手法かも知れません。
いずれにせよ、Verilogなどの低レベル設計時にはまだまだ必要なテクニックかと思います。