Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

FPGA内蔵メモリを使ったアキュムレータ(フォワーディングによるインターロックなしヒストグラム集計)

More than 1 year has passed since last update.

はじめに

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 という動作パターンになります。

  1. メモリから値を読み出す
  2. 値を加算する
  3. 結果を書き戻す

この時にFPGAは1サイクルに1つの処理しかできません。
もちろん1個のデータ毎に3サイクルかけて計算しても良いのですが、しばし1サイクルに1データのスループットが必要になります。

そこでこの3つの演算を3ステージとしてパイイプライン的に計算したくなります。

しかしながらその際に、同じメモリアドレスに対する演算が3サイクル中に2つ以上出てくると、

まだ先行する書き込まれていない古いデータを元に計算してしまう

ということが起こります。
いわゆるRAW(read after write)ハザードと呼ばれるものです。

解決方法

解決方法は大きく2つ考えられます。

  • ハザードが発生しそうになったら書き込み完了まで後続を待たせる(インターロック)
  • 書き込み完了前の先行するパイプラインからデータを取得してくる(フォワーディング)

今回は後者のフォワーディングを行います。

フォワーディングの動作

下記が、フォワーディングを加味したパイプラインの動作図です。

forwarding.png

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などの低レベル設計時にはまだまだ必要なテクニックかと思います。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away