FPGA上如何求32個(gè)輸入的最大值和次大值：分治

題目

在FPGA上實(shí)現(xiàn)一個(gè)模塊，求32個(gè)輸入中的最大值和次大值，32個(gè)輸入由一個(gè)時(shí)鐘周期給出。

從我個(gè)人的觀點(diǎn)來看，這是一道很好的面試題目：

其一是這大概是某些機(jī)器學(xué)習(xí)算法實(shí)現(xiàn)過程中遇到的問題的簡(jiǎn)化，是很有意義的一道題目；

其二是這道題目不僅要求FPGA代碼能力，還有很多可以在算法上優(yōu)化的可能；

當(dāng)然，輸入的位寬可能會(huì)影響最終的解題思路和最終的實(shí)現(xiàn)可能性。但位寬在一定范圍內(nèi)，譬如8或者32，解題的方案應(yīng)該都是一致的，只是會(huì)影響最終的頻率。后文針對(duì)這一題目做具體分析。（題目沒有說明重復(fù)元素如何處理，這里認(rèn)為最大值和次大值可以是一樣的，即計(jì)算重復(fù)元素）

解法

從算法本身來看，找最大值和次大值的過程很簡(jiǎn)單；通過兩次遍歷：第一次求最大值，第二次求次大值; 算法復(fù)雜度是O（2n）。FPGA顯然不可能在一個(gè)周期內(nèi)完成如此復(fù)雜的操作，一般需要流水設(shè)計(jì)。這一方法下，整個(gè)結(jié)構(gòu)是這樣的

1. 通過比較，求最大值，通過流水線實(shí)現(xiàn)兩兩之間的比較，32-16-8-4-2-1通過5個(gè)clk的延遲可以求得最大值；

2. 由于需要求取次大值，因此需要確定最大值的位置，在求最大值的過程中需要維持最大值的坐標(biāo)；

3. 最大值坐標(biāo)處取值清零（置為最小）

4. 通過流水線實(shí)現(xiàn)兩兩之間的比較，32-16-8-4-2-1，再經(jīng)過5個(gè)clk的延遲可以求得次大值；

這種解法有若干個(gè)缺點(diǎn)，包括：延遲求最大值和次大值分別需要5clk延時(shí)，總延遲會(huì)超過10個(gè)cycles；資源占用較高，維持最大值坐標(biāo)和清零操作耗費(fèi)了較多資源，同時(shí)為了計(jì)算次大值，需要將輸入寄存若干個(gè)周期，寄存器消耗較多。

另一個(gè)種思路考慮同時(shí)求最大值和次大值，由于這一邏輯較為復(fù)雜，可以將其流水化，如下圖。（以8輸入為例，32輸入需要增加兩級(jí)）

其中sort模塊完成對(duì)4輸入進(jìn)行排序，得到最大值和次大值輸出的功能。4個(gè)數(shù)的排序較為復(fù)雜，這一過程大概需要2-3個(gè)cycles完成。對(duì)于32輸入而言，輸入數(shù)據(jù)經(jīng)過32-16-8-4-2輸出得到結(jié)果，延遲大概也有10個(gè)周期。

分治

如果需要在FPGA上實(shí)現(xiàn)一個(gè)特定的算法，那么去找一個(gè)合適的方法去實(shí)現(xiàn)就好了；但如果是要實(shí)現(xiàn)一個(gè)特定的功能，那么需要找一個(gè)優(yōu)秀的且適合FPGA實(shí)現(xiàn)的方法。

求最大值和次大值是一個(gè)很不完全的排序，通過簡(jiǎn)單的查找復(fù)雜度為O（2n），且不利于硬件實(shí)現(xiàn)。對(duì)于排序而言，無論快速排序或者歸并排序都用了分治的思想，如果我們?cè)噲D用分治的思想來解決這一問題?？紤]當(dāng)只有2個(gè)輸入時(shí)，通過一個(gè)比較就可以得到輸出，此時(shí)得到的是一個(gè)長(zhǎng)度為2的有序數(shù)組。如果兩個(gè)有序數(shù)組，那么通過兩次比較就可以得到最大值和次大值。采用歸并排序的思想，查找最大值和次大值的復(fù)雜度為O（1.5n）（即為n/2+n/2+n/4… ，不知道有沒有算錯(cuò)）。采用歸并排序的思想，從算法時(shí)間復(fù)雜度上看更為高效了。

那么這一方案是否適合FPGA實(shí)現(xiàn)呢，答案是肯定的。分治的局部性適合FPGA的流水實(shí)現(xiàn)，框圖如下。（以8輸入為例，32輸入需要增加兩級(jí)）

其中meg模塊內(nèi)部有兩級(jí)的比較器，一般而言1clk就可以完成，輸入數(shù)據(jù)經(jīng)過32-32-16-8-4-2得到結(jié)果，延遲為5個(gè)時(shí)鐘周期。實(shí)現(xiàn)代碼如下

module test#（

parameter DW = 8

）

（

input clk，

input ［32*DW-1 ：0］ din，

output ［DW-1:0］ max1，

output ［DW-1:0］ max2

）;

wire［DW-1:0］ d［31:0］;

generate

genvar i;

for（i=0;i《32;i=i+1）

begin:loop_assign

assign d［i］ = din［DW*i+DW-1:DW*i］;

end

endgenerate

// stage 1，comp

reg［DW-1:0］ s1_max［15:0］;

reg［DW-1:0］ s1_min［15:0］;

generate

for（i=0;i《16;i=i+1）

begin:loop_comp

always@（posedge clk）

if（d［2*i］》d［2*i+1］）begin

s1_max［i］ 《= d［2*i］;

s1_min［i］ 《= d［2*i+1］;

end

else begin

s1_max［i］ 《= d［2*i+1］;

s1_min［i］ 《= d［2*i］;

end

end

endgenerate

// stage 2，

wire［DW-1:0］ s2_max［7:0］;

wire［DW-1:0］ s2_min［7:0］;

generate

for（i=0;i《8;i=i+1）

begin:loop_megs2

meg u_s2meg（

.clk（clk），

.g1_max（s1_max［2*i］），

.g1_min（s1_min［2*i］），

.g2_max（s1_max［2*i+1］），

.g2_min（s1_min［2*i+1］），

.max1（s2_max［i］），

.max2（s2_min［i］）

）;

end

endgenerate

// stage 3，

wire［DW-1:0］ s3_max［3:0］;

wire［DW-1:0］ s3_min［3:0］;

generate

for（i=0;i《4;i=i+1）

begin:loop_megs3

meg u_s3meg（

.clk（clk），

.g1_max（s2_max［2*i］），

.g1_min（s2_min［2*i］），

.g2_max（s2_max［2*i+1］），

.g2_min（s2_min［2*i+1］），

.max1（s3_max［i］），

.max2（s3_min［i］）

）;

end

endgenerate

// stage 4，

wire［DW-1:0］ s4_max［1:0］;

wire［DW-1:0］ s4_min［1:0］;

generate

for（i=0;i《2;i=i+1）

begin:loop_megs4

meg u_s4meg（

.clk（clk），

.g1_max（s3_max［2*i］），

.g1_min（s3_min［2*i］），

.g2_max（s3_max［2*i+1］），

.g2_min（s3_min［2*i+1］），

.max1（s4_max［i］），

.max2（s4_min［i］）

）;

end

endgenerate

// stage 5，

meg u_s5meg（

.clk（clk），

.g1_max（s4_max［0］），

.g1_min（s4_min［0］），

.g2_max（s4_max［1］），

.g2_min（s4_min［1］），

.max1（max1），

.max2（max2）

）;

endmodule

module meg#（

parameter DW = 8

）

（

input clk，

input ［DW-1 ：0］ g1_max，

input ［DW-1 ：0］ g1_min，

input ［DW-1 ：0］ g2_max，

input ［DW-1 ：0］ g2_min，

output reg ［DW-1:0］ max1，

output reg ［DW-1:0］ max2

）;

always@（posedge clk）

begin

if（g1_max》g2_max） begin

max1 《= g1_max;

if（g2_max》g1_min）

max2 《= g2_max;

else

max2 《= g1_min;

end

else begin

max1 《= g2_max;

if（g1_max》g2_min）

max2 《= g1_max;

else

max2 《= g2_min;

end

end

endmodule

3. 其他

簡(jiǎn)單測(cè)試了上面的代碼，在上一代器件上（20nm FPGA），8bit數(shù)據(jù)輸入模塊能綜合到很高的頻率，邏輯級(jí)數(shù)大概是5級(jí)左右，對(duì)于整個(gè)工程而言瓶頸基本不會(huì)出現(xiàn)在這一部分。32bit數(shù)據(jù)輸入由于數(shù)據(jù)位寬太大，頻率不會(huì)太高，但是通過將meg模塊做一級(jí)流水，也幾乎不會(huì)成為整個(gè)系統(tǒng)的瓶頸。

32bit32輸入情況下，數(shù)據(jù)輸入位寬為1024（不是IO輸入，是內(nèi)部信號(hào)）。之前在通信/數(shù)字信號(hào)處理方面可能不會(huì)用到這么大位寬的數(shù)據(jù)，但對(duì)于AI領(lǐng)域FPGA的應(yīng)用，數(shù)千比特的輸入應(yīng)該是很平常的，這的確會(huì)影響最終FPGA上實(shí)現(xiàn)的效果。要想讓機(jī)器學(xué)習(xí)算法在FPGA上跑得更好，還需要算法和FPGA共同努力才是。