FPGAの部屋の記事、 RGB 24ビット・データ入出力対応のメディアン・フィルタをVitis HLS 2021.1で作成する1、RGB 24ビット・データ入出力対応のメディアン・フィルタをVitis HLS 2021.1で作成する2にて、HLS記述にてバブルソートを記述し、Interval=1を得ている(1クロック毎にデータを入力できるパイプラインで動作)のを見て、 実はHLSではなく、愚直にRTLで書いてもInterval=1は達成できるのではないかと思い、実験してみました。

ソートをハードウェアで実装するための手法はよく研究されており、ソーティングネットワークと呼ばれているようです。

Wikipediaによれば、3x3(=9)画素のソートを行うためには、7段のソーティングネットワークが最小の段数であるそうです。

“sorting network generator"などと検索すると、ソーティングネットワークの自動生成ツールなどもあり、興味がある方には面白いかもしれません。

書いてみたRTL記述はこちら:

module sort (
    input            CLK,
    input [15:0]     in[0:8],
    output reg[15:0] out
);

    logic[15:0] tmp;
    logic[15:0] in_val[0:8];
    logic[15:0] result;

    int i,j;

    always @(*) begin
        in_val = in;
        for (i = 1; i < 9; i = i + 1) begin
            for (j = 0; j < 9 - i; j = j + 1) begin
                if (in_val[j] < in_val[j+1]) begin
                    tmp         = in_val[j];
                    in_val[j]   = in_val[j+1];
                    in_val[j+1] = tmp;
                end
            end
        end
        result = in_val[4];
    end

    always_ff @(posedge CLK) begin
        out <= result;
    end

endmodule

9個の数値(各16bit)からなる配列inを、上記記事ではC言語で書かれているのと同じ方法でソートしています。 このようなコードは、ある程度RTL記述に慣れた人の方が違和感を感じるかと思います。 ノンブロッキング代入(<=)ではなくブロッキング代入(=)を使っています。

RTLでforループを使用する場合、同じような回路の複数コピーを作成する、というのが用途の大部分を占めると思います。 上記記述もその一例と言えなくは無いですが、どのような回路が合成されるのか、直観的には把握しずらいです。

どのように論理合成が行われるのか、CRC生成回路に実例と共に説明されていますが、要するに、ループ内で使われている変数tmp, in_valに、i, jの値を添え字としてループ毎に別名を付けてあげると思えば、 理論的には展開できるというのが想像できると思います。内側のループ(j)が8,7,6,…,1回回るので、 合計36回ifの部分が展開されることになります。手計算で行おうと思うと気が遠くなりますが、合成ツールは賢いです。

次のようなテストベンチを作ってみます。

module sort_tb;

    logic CLK;
    logic [15:0] in[0:8];
    logic [15:0] out;

    sort dut (.*);

    initial begin
        CLK = 0;
    end

    always #10 CLK <= ~CLK;

    always @(posedge CLK) begin
        in[0]   <=  $urandom();
        in[1]   <=  $urandom();
        in[2]   <=  $urandom();
        in[3]   <=  $urandom();
        in[4]   <=  $urandom();
        in[5]   <=  $urandom();
        in[6]   <=  $urandom();
        in[7]   <=  $urandom();
        in[8]   <=  $urandom();
    end

endmodule

シミュレーションしてみた波形が次です。画面上のsynthはsortに置き換えてください。

緑の入力に対して、1クロック遅れて黄色の出力が得られています。目視でチェックした限り、9つの値の中央値が得られてそうです。

論理合成してみた結果をRTL Viewerで確認してみます。

一番右側に一つだけ16bitのレジスタがあって、残りは比較器とマルチプレクサになっています。 何段になっているか、しっかり数えませんでしたが(12段?)、さすがに最小値の7までは行ってなさそうです。

配置配線まで実行してみたところ、Cyclone Vで、ALM 988個、Total registers 16となりました。

ちなみに、久々にQuartusでシミュレーションしようとしたら、ModelSimの起動方法に手間取って、Quartus Prime と ModelSim の NativeLink の使い方を参考にして解決しました。