基于直方圖算法進(jìn)行FPGA架構(gòu)設(shè)計

引言

直方圖統(tǒng)計在圖像增強(qiáng)和目標(biāo)檢測領(lǐng)域有重要應(yīng)用，比如直方圖均衡，梯度直方圖。直方圖的不同種類和統(tǒng)計方法請見之前的文章。本章就是用FPGA來進(jìn)行直方圖的計算，并且利用FPGA的特性對計算過程進(jìn)行加速。安排如下：

首先基于直方圖算法進(jìn)行FPGA架構(gòu)設(shè)計，這里主要考慮了如何加速以及FPGA資源的利用兩個因素；最后基于system Verilog搭建一個驗證系統(tǒng)。

FPGA設(shè)計架構(gòu)

不論是圖像灰度直方圖還是梯度直方圖，本質(zhì)上是對數(shù)據(jù)的分布進(jìn)行計數(shù)。從FPGA角度來看，只關(guān)心以下幾點：

1） 根據(jù)數(shù)據(jù)大小確定其分布區(qū)間，統(tǒng)計分布在不同區(qū)間的數(shù)據(jù)個數(shù)，區(qū)間的大小可以調(diào)節(jié)，比如灰度直方圖區(qū)間為1，梯度直方圖通常大于1；

2） 如何利用FPGA對直方圖統(tǒng)計進(jìn)行加速，以及如何考慮到芯片有限資源；

首先來考慮加速方式，直方圖統(tǒng)計過程用偽代碼表示為：

For(int i=0;i Index = get_index(data[i]);
Hist[index]++;
}

Get_index函數(shù)是為了確定數(shù)據(jù)屬于哪個區(qū)間，如果區(qū)間大小為1，那么index就是數(shù)據(jù)自身。如果區(qū)間是平均分布，那么就需要進(jìn)行數(shù)據(jù)的大小比較。如果區(qū)間大小是2的冪次，那么index只需要數(shù)據(jù)進(jìn)行移位得到。

FPGA在加速計算中最主要就是利用并行化和流水線，并行化就是將一個任務(wù)拆解成多個子任務(wù)，多個子任務(wù)并行完成。而流水線是在處理一個子任務(wù)的時候，下一個來的子任務(wù)也可以進(jìn)行處理，處理模塊不會等待。流水線本質(zhì)上是對子任務(wù)也進(jìn)行“分割”，分割的每一塊可以在處理模塊中同時進(jìn)行。

統(tǒng)計N個數(shù)據(jù)，可以將N分成M份，在FPGA上同時進(jìn)行M個統(tǒng)計，用偽代碼表示為：

For(int k=0;k //并行化
For(int i=0;i Index = get_index(data[k][i]);
Hist[k][index]++;
}
}

如果區(qū)間不是2的冪次，就需要比較器，這樣并行M次，就需要M個同等比較器，這對資源消耗很大。因此目前設(shè)計僅僅支持2的冪次的區(qū)間。整個設(shè)計架構(gòu)如圖1.2。

圖2.1 流水線處理

圖2.2 直方圖統(tǒng)計架構(gòu)

主要分為以下幾個模塊：

1）statis:這個是核心計算模塊，統(tǒng)計數(shù)據(jù)分布。ram中存放直方圖統(tǒng)計數(shù)據(jù)，地址對應(yīng)著數(shù)據(jù)分布區(qū)間。這里有一個問題需要考慮，在對ram中直方圖統(tǒng)計數(shù)據(jù)計數(shù)時，需要讀出然后計數(shù)。如果ram讀端口沒有寄存器，那么讀出來直接加1，再寫入。但是這樣并不好，因為ram不經(jīng)過寄存器時序不好。所以增加了一級寄存器，這樣就造成了寫入的延時，那么有可能下一次數(shù)據(jù)來臨也會讀取同樣地址的數(shù)據(jù)，此時讀取到的直方圖數(shù)據(jù)就是還沒有寫入的。為了解決這個問題，判斷進(jìn)入的前后兩個數(shù)據(jù)是否相同，如果相同就不寫入而繼續(xù)計數(shù)，如果不同就寫入。并行多個statis模塊的代碼為：

genvar i;
generate
for(i=0;i

statis #(
.PIX_BW(PIX_BW),
.HIST_BW(HIST_BW),
.ADDR_BW(HIST_LEN_BW),
.BIN_W(BIN_W)

)u_statis(
.clk(clk),
.rst(rst),
.clr(clr),

.enable(1'b1),
.pix_valid(pix_valid),
.pix(img_i[i*PIX_BW +: PIX_BW]),

.hist_rd(branch_hist_rd),
.hist_raddr(branch_hist_raddr),
.hist(branch_hist[i*HIST_BW +: HIST_BW])
);

end
endgenerate

2）serders：這個是并轉(zhuǎn)串。M個statis模塊會產(chǎn)生M組hist結(jié)果，這些結(jié)果還要進(jìn)行求和，那么就要用到加法樹，如果M較大，會造成加法樹很大，多以這里加了serders可以調(diào)節(jié)加法樹資源。

3） addTree：加法樹。
module addTree #(
parameter DATA_BW = 32,//bit width of data
parameter TREE_DEPTH = 3,//depth of the add tree
parameter ADD_N = 4//add number
)
(
input clk,
input rst,
input [ADD_N*DATA_BW-1:0] adnd_x,
input [ADD_N*DATA_BW-1:0] adnd_y,
input adnd_valid,
output reg[DATA_BW-1:0] finl_sum,
output reg finl_sum_valid

);

reg [TREE_DEPTH-1:0]midl_valid;

genvar dept_i, leaf_i;
generate
for(dept_i=TREE_DEPTH-1;dept_i>=0;dept_i=dept_i-1)begin: ADD_DPET
localparam LEAF_N = 2**dept_i;

wire[DATA_BW-1:0] midl_sum[LEAF_N-1:0];

for(leaf_i=0;leaf_i

reg [DATA_BW-1:0] midl_add_x;
reg [DATA_BW-1:0] midl_add_y;

if(dept_i==TREE_DEPTH-1)begin
always @(posedge clk)begin
midl_add_x midl_add_y end
end
else begin
always @(posedge clk)begin
midl_add_x midl_add_y end
end

adder #(
.DATA_BW(DATA_BW)
)
u_adder(
.adnd_x(midl_add_x),
.adnd_y(midl_add_y),
.sum(midl_sum[leaf_i])

);

end

if(dept_i==TREE_DEPTH-1)
always @(posedge clk)begin
midl_valid[dept_i] end
else
always @(posedge clk)begin
midl_valid[dept_i] end

end

endgenerate

always @(posedge clk)begin
finl_sum end

always @(posedge clk)begin
if(rst)
finl_sum_valid else
finl_sum_valid end

endmodule

4） accum：累加器。如果加法樹沒有完成M個hist數(shù)據(jù)的求和，那么就需要通過累加器來完成。

圖2.3 對ram的處理

驗證結(jié)構(gòu)

1） img_trans：這個是隨機(jī)化圖像數(shù)據(jù)定義，主要通過SV中constraint來對圖像大小做一些約束；

class img_trans;

rand int img_w;
rand int img_h;
rand int img_blank;
rand logic[`PIX_BW-1:0] img[`MAX_IMG_W*`MAX_IMG_H];

constraint img_cfg_cnst{
img_w img_w > 0;
img_w % `PARALL == 0;
img_h img_h > 0;
img_blank img_blank >= 0;

}

extern function void write(input string f_name);

endclass

2） driver：產(chǎn)生image并且發(fā)送給DUT，同時通過mailbox發(fā)送給ref_model用于對比；
class img_obj;
logic [`PIX_BW-1:0] img_que[$];
endclass

class driver;

int img_w;
int img_h;
int img_blank;
logic [`PARALL*`PIX_BW-1:0] img;
logic [`PIX_BW-1:0] img_ele;
img_obj imgObj;
img_trans imgTrans;

extern task drive(mailbox img_mbx, virtual img_inf.test imgInf);

endclass

3） ref_model：自己統(tǒng)計直方圖和DUT的結(jié)果進(jìn)行比對；

class ref_modl;

logic [`PIX_BW-1:0] img;
int addr;
img_obj imgObj;
int hist[`HIST_LEN];

extern task calc(input logic clk, mailbox img_mbx);
extern task comp(virtual img_inf.test imgInf);
extern task run(input logic clk, mailbox img_mbx, virtual img_inf.test imgInf);
extern function void clear();

endclass

圖3.1 驗證架構(gòu)圖

最后添加一下modelsim仿真波形文件和結(jié)果，純粹為了增加篇幅。

圖3.2 modelsim仿真波形和結(jié)果

編輯：hfy