Ryuzのブログ

乗算器を使わないバイリニア補間のコードを書いています。その過程の線形補間の作成でちょっと面白い最適化に気がついたので記事にしておきます。

線形補間は２点の比なので、中心(足して２で割る)を求めて片方とリプレースすることを繰り返せば、加算器１段ごとに１bitづつ精度を上げていけます(いわゆる挟み撃ち法)。4bit程度しか精度が要らない今回の場合は、乗算器を使うよりお得かもしれません。

そこで最初下記のような計算ステージ１段で下記のようなことを行うコードを書いていたのですが、

always @(posedge clk) begin
  tmp    = (din0 + din1) / 2;
  dout0 <= sel ? tmp  : din0;
  dout1 <= sel ? din1 : tmp;
end

下記のように書けばコンパクトになるのではないかと思いやってみたところ、見事に(ISEの合成レポート上は)小さくなりました。  

always @(posedge clk) begin
  dout0 <= (din0 + (sel ? din1 : din0)) / 2;
  dout1 <= (din1 + (sel ? din0 : din1)) / 2;
end

リプレースをセレクタによって選択的に行うのではなく、置き換えない場合は自分自身を足して２で割ることで、値をキープするように書き換えています（実際には２で割る部分は最後に纏めてシフトするのが精度の点では良いようですが、今回は説明用ということで）。
前者は加算器２個、後者は１個なのになぜ？ と思われる方もおられるかもしれません。

以下、XILINX社のUG474の図2-4を引用させて頂いて説明します。

　XILINXのZynqの属するXILINX 7シリーズのSLICEはLUTの後ろに加算などをサポートするキャリーチェーンが必ずついているようです。
　なので

• LUTを使う場合、キャリーチェーンの利用の有無は消費スライスに影響しない
• キャリーチェーンを使う後にもロジックがあるとさらにLUTが必要になる

　ということになります。
　なので、加算が２個に増えることによるリソース増加はなく、演算の最後が加算で終わるように書き直すことによるLUT削減の方の効果が出るという一見不思議なことが起こるようです。
　もっとも、別の回路とくっつけて合成したら、結局はいい感じに収まる可能性もありますが。

　ただ、筆者の経験上、加減算を行う場合、FFへの代入の最後の演算が加減算で終わるように式変形してやると若干改善するケースは幾つかあるように思います。
　これはFPGA特有のテクニックで、LSI向けのRTLを書く場合は、回路が増えるデメリットだけだとは思いますので、果たして推奨するべきかは非常に微妙ですが、こういうこともあるのだなという面白い例かとは思います。

　なお、バイリニアなどの線形補間と良く似た計算でアルファブレンディングがあります。線形補間との違いは、線形補間は 256が1.0になるのに対して、アルファブレンディングは255が1.0であることです。

　この問題は、

http://www.cqpub.co.jp/dwm/contents/0104/dwm010400780.pdf

https://qiita.com/andantissimo/items/84be23b0f2937f8b3d90

とかに詳しい解説があるようで、それほど大きな追加コストはなく 256/255倍の計算は出来るように思います。

とはいえちょっと工夫すればはさみうち法でもアルファブレンディングが出来そうに思っています。

これはまた今度機会があれば考えてみたいと思います。