編 者 按? ?

TCAM(Ternary content-addressable memory)在FPGA里并沒有專門的資源，其在網(wǎng)絡(luò)應(yīng)用上是一個比較常見的資源。關(guān)于如何在FPGA中實(shí)現(xiàn)TCAM功能有不少的論文，在翻閱借鑒之后，本文就TCAM在FPGA上的最優(yōu)化實(shí)現(xiàn)進(jìn)行探討。?

01

TCAM基本原理

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

這里通過TCAM和RAM實(shí)現(xiàn)了一張路由表，輸入報(bào)文通過TCAM獲取對應(yīng)的命中Entry地址，隨后通過該地址查找RAM獲取對應(yīng)的端口信息。

做邏輯設(shè)計(jì)的都清楚，X只存在于仿真中。在FPGA里不存在X態(tài)的概念。回到上面這個4輸入的TCAM表中，X意味著0或者1都可以，那么這里就可以給出完整的表項(xiàng)：

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

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

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

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

02

input膨脹問題

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

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

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

03

資源選取

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

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

我們實(shí)現(xiàn)一個54 key width，32 entry的TCAM所需要消耗的資源分別為：

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

除此之外，還有一個重要的點(diǎn)就是在TCAM的實(shí)現(xiàn)中，還牽涉到TCAM表項(xiàng)的插入。在這種結(jié)構(gòu)里，每一個entry是在RAM的每個entry里占據(jù)一個比特。如果要插入一條表項(xiàng)，那就要將RAM所有的Entry進(jìn)行更新，這里采用BRAM就帶來表項(xiàng)的更新需要512個時鐘周期，而LUT RAM僅需64個時鐘周期，對于表項(xiàng)的插入速度顯然也是LUT RAM也更具優(yōu)勢。

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

04

性能/資源平衡

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

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

審核編輯：黃飛

?