編 者 按? ?

TCAM(Ternary content-addressable memory)在FPGA里并沒有專門的資源，其在網絡應用上是一個比較常見的資源。關于如何在FPGA中實現TCAM功能有不少的論文，在翻閱借鑒之后，本文就TCAM在FPGA上的最優化實現進行探討。?

01

TCAM基本原理

我們都知道RAM是根據地址查找對應的數據，而對于CAM，則恰好相反，是已知數據查找其對應的地址。像在網絡報文處理里，根據報文的五元組的一些信息去查詢其所屬的規則地址，隨后通過該地址去查詢對應的RAM獲取對應的Action信息。而TCAM，其只不過是在CAM的基礎上引入了 X(don't care)狀態。借助一篇論文里的圖來說明：

這里通過TCAM和RAM實現了一張路由表，輸入報文通過TCAM獲取對應的命中Entry地址，隨后通過該地址查找RAM獲取對應的端口信息。

做邏輯設計的都清楚，X只存在于仿真中。在FPGA里不存在X態的概念?；氐缴厦孢@個4輸入的TCAM表中，X意味著0或者1都可以，那么這里就可以給出完整的表項：

????在FPGA里，所具備的資源無非是LUT，RAM，寄存器。TCAM的結構本質上看更像是RAM類型的使用風格。針對Input的輸入，如果我們將input key作為地址輸入進行查找,每個RAM存儲一個entry，RAM中存儲是否命中當前Entry,四個Entry進行并行查找，那么四個entry ram 的存儲結構就是：

上面每一列對應一個Entry RAM存儲表項。如果輸入為0100(addr=4),那么在4個Entry RAM中，只有PortA RAM中地址4存儲值為1，意味著命中PortA。對于input，我們同時查找4個RAM 得到四個查找，經過譯碼即可獲取對應的命中結果。在FPGA中對應的結構即為：

如此我們借助四個16D(Depth)1W(Width) RAM、一個Prority Decoder(用于判斷選取哪個命中)、一個Action RAM實現了上面的一個簡單的路由表。?

更進一步，由于四個RAM的地址線是接到的同一個信號源，那么我們可以更進一步，將四個16D1W RAM合并成一個16D4W的RAM，每個Entry占據其中的一個比特用于存儲對應的Entry RAM值：

02

input膨脹問題

通過上面的內容，大概能夠明白，其實TCAM在FPGA上的實現基本就是一種暴力展開，對于input key，每個entry會遍歷所有的key進行展開來判定是否命中。那么隨之而來的就是input key width膨脹問題。按照上面的思路，每個entry需要存儲的比特容量是1<

顯然，無腦的展開勢必帶來資源的爆炸。那么，可以采用分而治之的思想。我們將key按比特進行拆分，每段key分別查詢不同的ram，最終所有的RAM查詢結構都為1則才表示命中。我們以16bit input key為例，則可以表述為：

如此，對于一個Entry的存儲，其僅需4個16D1W存儲空間加上一個&操作即可，共計64bit存儲空間。

03

資源選取

到此，如何在FPGA中實現TCAM，其核心原理大概你已經相對來講比較清楚了。那么回到具體的實現上。在FPGA中實現這種結構，我們所能采用的無外乎Block RAM或者LUT RAM來實現。那么究竟采用哪種資源更合適呢？先說結果：采用LUT RAM更合適。

這里我們采用最常規的配置來進行說明。Block RAM可以配置成512D32W模式，LUT RAM采用64D1W模式。參照上面的結構，一個512D32W的Block RAM地址位寬為9，也就意味著其所能容納的key width為9 bit。而64D1W所能容納的key width為6 bit。

我們實現一個54 key width，32 entry的TCAM所需要消耗的資源分別為：

對比下來，采用LUT RAM每個Entry所消耗的存儲資源遠小于BlockRAM，而且采用BRAM33 Entry與64Entry所消耗的資源量是一致的。

除此之外，還有一個重要的點就是在TCAM的實現中，還牽涉到TCAM表項的插入。在這種結構里，每一個entry是在RAM的每個entry里占據一個比特。如果要插入一條表項，那就要將RAM所有的Entry進行更新，這里采用BRAM就帶來表項的更新需要512個時鐘周期，而LUT RAM僅需64個時鐘周期，對于表項的插入速度顯然也是LUT RAM也更具優勢。

同時參照之前的文章《LUT RAM，Xilinx VS Altera》，無論是Xilinx還是Intel，都是可以將LUT RAM設置成32x2的模式，那么采用LUT RAM還能夠進一步的資源優化：

04

性能/資源平衡

看到這兒，也許你已經意識到，RAM的深度越淺，其所消耗的資源也就越少。在上面的論述里，其相當于都是1拍出結果。對于FPGA跑三四百MHz的頻率時，這么高的PPS可能不是我們所必需的。根據我們的設計需求，我們完全可以兩拍或者四拍出一個結果，那么相當于可以將一個LUTRAM 變相的拆分成一個16D4W、8D8W的RAM，同樣以上面的54 key width，32 entry為例：

除此之外，對于后面的Prority Decoder而言,單拍/兩拍/四拍出結果對資源的消耗在隨著Entry數的增加時所帶來的資源節省也有著顯著的降低。?

審核編輯：黃飛

?