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 の使い方を参考にして解決しました。