分治法是經(jīng)典優(yōu)化算法之一。分治分治，即分而治之。分治，就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

分治法的思想我們也可以用在FPGA開發(fā)中，使得設(shè)計更加高效。

本文以 leading zero count 為例來看一下分治法的應(yīng)用。

這個題目是計算一個 vector 的 leading zero 的數(shù)目。比如 8'b00001111，結(jié)果為4，而8'b00111111，結(jié)果為2。

Casex 優(yōu)先級選擇器

我們可以用最簡單的 casex 優(yōu)先級選擇器來實現(xiàn)。假設(shè)輸入的vector位寬為64。

always_comb begin
    count = 0;
    casex (vector)
       64'b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000 : count = 64;
       64'b1???????_????????_????????_????????_????????_????????_????????_???????? : count = 0;
       64'b01??????_????????_????????_????????_????????_????????_????????_???????? : count = 1;
       64'b001?????_????????_????????_????????_????????_????????_????????_???????? : count = 2;
       ...
       64'b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001 : count = 63;
    encase
end

綜合結(jié)果如圖一所示。Vivado綜合完預(yù)估的slack為8.572ns，critical path是5級，共消耗71個LUT。

圖1 - leading zero count 1

分治法 - Tree Structure

現(xiàn)在我們使用分治法來實現(xiàn)這個功能。通過一個 balanced tree structure 來實現(xiàn)。

首先將 64bit 的 vector 分成32個 2bit 的小 vector。先對2bit的小 vector 做encode：

case(small_vector)
    2'b00: encoded = 2'b10;  // 2 leading zeros
    2'b01: encoded = 2'b01;  // 1 leading zero
    2'b10: encoded = 2'b00;  // 0 leading zero
    2'b11: encoded = 2'b00;  // 0 leading zero
endcase

然后按照如下規(guī)則將相鄰的 encoded value 進行組合：

如果兩邊都是 1xxx，那么結(jié)果為 10..0

如果左邊是 0xxx，那么結(jié)果為 0[左邊]

如果左邊是 1xxx，那么結(jié)果為 01[右邊[msb-1:0]]

可以看到每個組合的操作是一個mux。每次組合后，新的vector位寬加1，然后新的vector再兩兩組合，直到得出最終的結(jié)果。

我們以8bit輸入的vector為例：8'b00000111

按照2bit分解： 00 00 01 11

Encoded value: 10 10 01 00

兩兩組合： 100 001

再組合： 0101 = 5 leading zeros

當(dāng)輸入為64bit的vector時，此 tree structure 的設(shè)計綜合結(jié)果如圖2所示。Vivado綜合后預(yù)估的slack為8.600ns，critical path為4級，消耗38個LUT。

圖2 - leading zero count 2

可以看到相比于casex的設(shè)計，tree structure節(jié)省了超過50%的LUT，同時邏輯級數(shù)也減少了一級。

總結(jié)

分治法的思想也可以應(yīng)用在FPGA開發(fā)中。尤其是當(dāng)我們遇到大位寬數(shù)據(jù)的處理時，分治法往往可以提升設(shè)計的資源使用率和時序結(jié)果。