« XILINXのDSP推論 | トップページ | バイリニア補間するユニット »

2016年10月29日 (土)

除算の検討(回復法と非回復法)

引き続きなぜか除算に迷走しています(苦笑)。
除算にはいろいろなやり方がありますが、今回はシェーダーとかのプログラマブルロジックではなく、固定グラフィックスパイプライン内のパースペクティブ補正に組み込むことを前提にスループット1の整数除算器を考えてみます。

除算器の種類とかはwikipediaに書かれているレベルでもいろいろ存在するようです。

CPUなどに内蔵される除算器は、そもそもグラフィックスのように除算のみが大量に押し寄せることも稀なので、スループット1未満のマルチサイクル除算器の構成が多く、SRT法など(Pentiumの有名な除算バグのアレです)が高速化に効果的なようです。ただしSRT法でスループット1でパイプラインを組むと各ステージにテーブルが必要になってしまい規模的に現実的ではないと思われます。

となると、地道に減算系のパイプラインを組むしかないので、回復法と、非回復法を検討して見ました。グラフィックスパイプラインなのでレイテンシは一旦気にせずにロジックスライス内のFFの使用率を上げて周波数を稼ぐとすると、気になるのはどうコンパクトに収まるかになってきます。

各ステージでの計算としての大きな違いは、

回復法)
  減算してみて負なら元に戻す
  つまり減算器の後ろにセレクタ
  符号の扱いは別途ケアが必要

非回復法)
  非除数と除数の符号を見て、加算と減算を切り替える
  つまり加算器手前の符号の反転/非反転をセレクト
  パイプラインの最後に正規化が必要

の違いなので、1ステージの計算が規模的にあまり変わらない可能性もあり、それなら最後の正規化の無い回復法もありかなとか考えていました(周波数に極端な差が出ないない前提で)。

なので先立って、1ステージ分の計算回路の実験です。

// 回復法の1ステージ分
module div_test_restoring(
            input   wire                    reset,
            input   wire                    clk,
            input   wire                    cke,

            input   wire            [31:0]  a,
            input   wire            [31:0]  b,

            output  reg             [31:0]  c
        );

    wire     [31:0]  t = a - b;

    always @(posedge clk) begin
        if ( reset ) begin
            c <= 0;
        end
        else if ( cke ) begin
            c <= t[31] ? a : t;
        end
    end

endmodule

// 非回復法の1ステージ分
module div_test_non_restoring(
            input   wire                    reset,
            input   wire                    clk,
            input   wire                    cke,

            input   wire    signed  [31:0]  a,
            input   wire    signed  [31:0]  b,

            output  reg     signed  [31:0]  c
        );

    always @(posedge clk) begin
        if ( reset ) begin
            c <= 0;
        end
        else if ( cke ) begin
            c <= (a[31] == b[31]) ? a - b : a + b;
        end
    end

endmodule

XC7Z010向けのISE14.7での合成結果、

 回復法    : LUT 64個消費
  非回復法 : LUT 32個消費

という結果です。2倍の差ですね。

XILINXのCLBは LUT とFFの間に、加算器のためのキャリーチェーンがあるので、加算前に細工を施す非回復法はLUTにロジックを閉じ込められるようですが、加算器の後に処理の入る回復法だともう一つ別のLUTが必要になるようですね。

これは非回復法での設計が正解なようです。

<蛇足>
  「Xilinx のIPコア使えばいいのではないか?」という声も聞こえてきそうですが、GUIで生成するIPコアには幾つか欠点もあります。

  • parameter などでビット幅など変える汎用的なモジュールが作り難い
  • IPコアがいるモジュールはOOC(Out of Context)出来ない
  • veritakなど外部のシミュレータが使いにくくなる
  • AXI4S系のI/Fの場合、内部ブラックボックスなので、パイプライン数やサイクル数を仮定したコードがかけない(valid/readyでの待ち合わせが必須)

など、細かな課題があったりもします。

 

« XILINXのDSP推論 | トップページ | バイリニア補間するユニット »

FPGA」カテゴリの記事

コメント

この記事へのコメントは終了しました。

トラックバック


この記事へのトラックバック一覧です: 除算の検討(回復法と非回復法):

« XILINXのDSP推論 | トップページ | バイリニア補間するユニット »