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

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

本文以 leading zero count 為例來看一下分治法的應用。

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

Casex 優先級選擇器

我們可以用最簡單的 casex 優先級選擇器來實現。假設輸入的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

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

圖1 - leading zero count 1

分治法 - Tree Structure

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

首先將 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

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

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

如果左邊是 0xxx，那么結果為 0[左邊]

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

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

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

按照2bit分解： 00 00 01 11

Encoded value: 10 10 01 00

兩兩組合： 100 001

再組合： 0101 = 5 leading zeros

當輸入為64bit的vector時，此 tree structure 的設計綜合結果如圖2所示。Vivado綜合后預估的slack為8.600ns，critical path為4級，消耗38個LUT。

圖2 - leading zero count 2

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

總結

分治法的思想也可以應用在FPGA開發中。尤其是當我們遇到大位寬數據的處理時，分治法往往可以提升設計的資源使用率和時序結果。