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

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

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

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

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

我們可以用最簡(jiǎn)單的 casex 優(yōu)先級(jí)選擇器來(lái)實(shí)現(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級(jí)，共消耗71個(gè)LUT。

圖1 - leading zero count 1

分治法 - Tree Structure

現(xiàn)在我們使用分治法來(lái)實(shí)現(xiàn)這個(gè)功能。通過(guò)一個(gè) balanced tree structure 來(lái)實(shí)現(xiàn)。

首先將 64bit 的 vector 分成32個(gè) 2bit 的小 vector。先對(duì)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 進(jìn)行組合：

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

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

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

可以看到每個(gè)組合的操作是一個(gè)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時(shí)，此 tree structure 的設(shè)計(jì)綜合結(jié)果如圖2所示。Vivado綜合后預(yù)估的slack為8.600ns，critical path為4級(jí)，消耗38個(gè)LUT。

圖2 - leading zero count 2

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

總結(jié)

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