二分化查找算法是在軟件中廣泛應用的一種算法，那么在FPGA的設計中是否可以用這種算法呢？什么場景下會可能用到這種算法呢？

二分法簡介

這里先簡單的說明下二分法查找，不涉及具體的算法原理。要實現二分法查表，有一個前提，那就是這個表是一個有序表。

假定表的深度為N（從0到N-1），那么首先從N/2地址讀出內容比較，如果待比較的值x比從表中讀出的值M小，說明x只可能位于0——（N/2-1）之間，然后采用同樣的方式從0——（N/2-1）中繼續查找；如果待比較的值x比從表中讀出的值M大，說明x只可能位于（N/2+1)——N-1之間，然后采用同樣的方式從（N/2+1)——N-1中繼續查找。

應用場景

在FPGA設計中，什么場景可以用到二分法查找呢？只有一個條件，那就是表項是一個有序表。要得到一個有序表，有幾種情況：

1、表項由邏輯實現寫操作，那么在寫入的過程中，先要把表項中的內容讀出來，和即將要寫入的內容做排序后，再寫回。這種方案相對來說還是比較復雜的，尤其是在高性能的場景下。

2、表項由CPU實現寫操作，如果表項不需要動態更新，那這就是一件很容易的事情了，如果表項需要CPU來更新，那么也需要將表項讀出來后進行排序然后再寫入FPGA。

在網絡通信中，有如下一種場景，就是收到的報文依據源IP地址進行過濾（不是真正意義上的防火墻），只允許特定的IP地址通過，IP地址的個數最多為1024個，由軟件來維護。當然可以采用hash算法，實現稍微復雜點，也可以采用最原始的辦法，就是把每個IP地址讀出來比較，這種方案性能不穩定，最差的情況有可能需要1024個cycle才能出結果。如果用二分法查找，最多只需要10次就可以出結果。

實現方案

知道了原理，其實該算法的方案實現是比較簡單的，就是通過跳表項的讀地址來實現比較，如下圖所示：

對min_addr和max_addr初始化后，計算出raddr，然后從raddr中讀出數據比較比較后，根據比較的結果來刷新min_addr或者max_addr，然后重新計算raddr的值，直到匹配中，或者min_addr=max_addr。

總結

在FPGA中需要查找的表項，如果能實現有序排列，采用二分法查找是一個不錯的選擇。相比其他算法，它在性能上保持一定優勢的前提下，實現也比較簡單。