FPGA設(shè)計中二分法查表算法的實現(xiàn)

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

二分法簡介

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

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

應(yīng)用場景

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

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

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

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

實現(xiàn)方案

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

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

總結(jié)

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