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

二分法簡介

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

假定表的深度為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è)計(jì)中，什么場景可以用到二分法查找呢？只有一個(gè)條件，那就是表項(xiàng)是一個(gè)有序表。要得到一個(gè)有序表，有幾種情況：

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

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

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

實(shí)現(xiàn)方案

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

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

總結(jié)

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