CAM在FPGA上的最優(yōu)化實(shí)現(xiàn)方案

編 者 按? ?

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

01

TCAM基本原理

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

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

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

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

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

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

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

02

input膨脹問(wèn)題

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

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

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

03

資源選取

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

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

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

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

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

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

04

性能/資源平衡

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

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

審核編輯：黃飛

?