◆張 磊 吳中軍 康令州 郭志君 盧宇浩

?

基于SRAM的TCAM設(shè)計(jì)與FPGA實(shí)現(xiàn)

◆張 磊 吳中軍 康令州 郭志君 盧宇浩

（中國(guó)電子科技集團(tuán)公司第三十研究所 四川 610041）

三態(tài)內(nèi)容可尋址存儲(chǔ)器TCAM是一種基于內(nèi)容查找地址的特殊存儲(chǔ)器，本文提出了在Kintex-7 FPGA芯片上，基于SRAM實(shí)現(xiàn)了512×36 TCAM的設(shè)計(jì)方法，突破了傳統(tǒng)TCAM不能在FPGA上實(shí)現(xiàn)的限制，而且給出了4種不同設(shè)計(jì)方法的所需資源數(shù)量、時(shí)延和功耗。因此，SR-TCAM是傳統(tǒng)CAM的實(shí)用且有效的替代方案，可以在硬件防火墻、入侵檢測(cè)等網(wǎng)絡(luò)安全領(lǐng)域廣泛應(yīng)用。

網(wǎng)絡(luò)安全；TCAM；FPGA；匹配地址

0 引言

CAM是基于內(nèi)容查找匹配地址的存儲(chǔ)器，CAM因其高速搜索性能受到歡迎。CAM最初是在交換路由設(shè)備中應(yīng)用[1]，目前廣泛應(yīng)用于網(wǎng)絡(luò)安全系統(tǒng)的硬件防火墻的五元組匹配、入侵檢測(cè)、病毒識(shí)別中的模式匹配[2]。

然而，CAM的速度是以高功耗，低有效bit密度和每bit成本高為代價(jià)的[3]。三態(tài)CAM（TCAM）的每bit成本比DDR SRAM高出約30倍，每bit耗電量比SRAM高150倍。表1說(shuō)明SRAM在bit密度，速度和功耗方面優(yōu)于TCAM[4]。

表1 TCAM和SRAM的比較

因此，需要一種創(chuàng)新的TCAM設(shè)計(jì)，在較低成本、較低功耗時(shí)，實(shí)現(xiàn)可以實(shí)用的搜索性能[5]。本文旨在介紹這種解決方案，使用SRAM存儲(chǔ)器實(shí)現(xiàn)TCAM功能，稱這種架構(gòu)為SR-TCAM（基于SRAM的TCAM），并可以在FPGA芯片上將其實(shí)現(xiàn)。

1 架構(gòu)設(shè)計(jì)

首先提出一個(gè)垂直分區(qū)VP的概念，VP的意思是將寬度為W位的TCAM字被分成n個(gè)子字，每個(gè)子字的寬度為w位。

圖1 SR-TCAM的體系架構(gòu)

SR-TCAM垂直分區(qū)VP將TCAM表按照列劃分為n個(gè)子表，這些子表被處理存儲(chǔ)在相應(yīng)的SRAM塊中。SRAM塊被稱做地址位置表APT(Address Position Table)和比特位置表BPT(bit Position Table)。圖1所示的SR-TCAM體系結(jié)構(gòu)的主要組成部分包括n個(gè)BPT、n個(gè)APT、n個(gè)APT地址（APTA）發(fā)生器、優(yōu)先級(jí)編碼器（PE）和AND運(yùn)算。每個(gè)垂直分區(qū)都有其對(duì)應(yīng)的BPT、APTA生成器和APT。

w個(gè)位的最大可能組合是2w，其中每個(gè)組合代表一個(gè)子字。我們的目標(biāo)是將2w個(gè)子字映射到2w個(gè)比特，使得每個(gè)子字在其對(duì)應(yīng)的存儲(chǔ)器中由單個(gè)比特表示。

如圖2所示，在BPT中，存儲(chǔ)器的2w個(gè)比特被排列成2w-b行，每行有2個(gè)或更多比特。每行補(bǔ)充一個(gè)長(zhǎng)度為w + 1位的稱為最后索引（LI）值。輸入子字的w-b高位用于選擇BPT中的特定行，從而充當(dāng)?shù)刂稡PTA。比特位置指示符（BPI）的b個(gè)低位比特用于指示所選行中的特定比特位置，如果BPI指示的比特位置為高，則意味著存在該輸入子字，否則不存在。

圖2 比特位置表BPT

APTA生成器生成一個(gè)地址，稱為APTA，用于在相應(yīng)的APT中對(duì)這一行進(jìn)行索引。APTA生成器包含1的計(jì)數(shù)器和加法器。1的計(jì)數(shù)器在選定的BPT行指定比特位置，然后將該信息轉(zhuǎn)發(fā)給加法器，然后加法器加1，將所選行的LI的輸出。

APT的大小為2w× K，其中2w代表行數(shù)，K代表每行中代表地址位置的位數(shù)，該地址位置對(duì)應(yīng)于其初始地址，如圖3所示。

圖3 地址位置表APT

2 工作流程

SR-TCAM按照如下所述的步驟完成搜索操作。

步驟1：將待搜索的字輸入進(jìn)SR-TCAM；

步驟2：將字分成n個(gè)子字，這些子字然后并行輸入到它們對(duì)應(yīng)的BPT；

步驟3：然后將一個(gè)子字分為兩部分：BPTA和BPI。步驟3并行發(fā)生在所有的子字上；

步驟4：讀取由BPTA選擇的行里面，由BPI指示的BPT中的比特位置。如果讀出的位為高，則表明輸入子字被認(rèn)為存在，但是在哪個(gè)地址仍然是未知的。步驟4也針對(duì)所有BPT并行執(zhí)行；

步驟5：對(duì)步驟4中所有BPT的讀出位都進(jìn)行了“與”運(yùn)算。步驟5對(duì)應(yīng)于圖1中的1位與運(yùn)算。此1位與運(yùn)算的結(jié)果指定搜索操作是繼續(xù)還是停止。如果1位“與”結(jié)果為低，則意味著發(fā)生了不匹配并顯示搜索階段結(jié)束，否則TCAM將繼續(xù)搜索操作并進(jìn)入步驟6；

步驟6：APTA生成器通過(guò)將所選行中的1的數(shù)目加到BPI所指示的比特位置（包括BPT所選行）的LI和LI的數(shù)目來(lái)計(jì)算APTA。為了計(jì)算所有的APTA，步驟6也并行進(jìn)行；

步驟7：從步驟6開(kāi)始，APTA同時(shí)從相應(yīng)的APT中讀出行；

步驟8：與圖1中的K-bit與相對(duì)應(yīng)的比特進(jìn)行與運(yùn)算。在步驟7中讀出的所有行的相應(yīng)位都進(jìn)行與運(yùn)算。在與運(yùn)算后，地址位置保持高位被認(rèn)為是可能的匹配地址PMA；

步驟9：這是最后一步。PE解碼輸出匹配地址MA。

3 基于FPGA實(shí)現(xiàn)

在Xilinx Kintex-7 FPGA開(kāi)發(fā)平臺(tái)上實(shí)現(xiàn)并驗(yàn)證了512×36 SR-TCAM的設(shè)計(jì)[6]。該設(shè)計(jì)的功能已經(jīng)通過(guò)大量測(cè)試用例，并使用ModelSim SE驗(yàn)證工具得到了廣泛的驗(yàn)證。

首先將36位的輸入字分成三個(gè)子字，每個(gè)子字是12位。然后將每個(gè)子字作為地址應(yīng)用于其相應(yīng)的BPT，其大小為512×21位。對(duì)于該設(shè)計(jì)，總共需要三個(gè)BPT。每個(gè)BPT的大小通過(guò)將子字細(xì)分為9bit和3bit位兩部分來(lái)決定，因此需要29 = 512的地址空間和23 + 13（LI）= 21位的字大小。每個(gè)APT的大小為4096×512位，來(lái)自所有行APT的讀出隨后被逐位進(jìn)行“與”運(yùn)算，以使用PE解碼得到匹配地址MA。

表2列出了4種不同設(shè)計(jì)參數(shù)的設(shè)計(jì)細(xì)節(jié)。我們?cè)贔PGA上使用了兩種BRAM的綜合優(yōu)化方式[7]。在FPGA開(kāi)發(fā)板xc7k325tffg900上，我們已經(jīng)使用了182個(gè)BRAM[8]。 Kintex-7上的每個(gè)BRAM最大容量可以是36Kbit，并且可以通過(guò)多種方式進(jìn)行配置。

表2 各種設(shè)計(jì)所需資源和功耗

在設(shè)計(jì)1的情況下，通過(guò)使用綜合選項(xiàng)BRAM-AUTO，為所有三個(gè)APT使用了182個(gè)BRAM，并使用分布式BRAM創(chuàng)建了三個(gè)BPT。

在設(shè)計(jì)2的情況下，通過(guò)使用綜合選項(xiàng)BRAM = BLOCK POWER2，其僅使用163個(gè)BRAM用于APT，而3個(gè)BRAM用于BPT。除了使用的BRAM數(shù)量外，這兩種設(shè)計(jì)在LUT數(shù)量和延遲方面也有一些折衷。因此，用戶可以選擇合適的設(shè)計(jì)參數(shù)。

使用Xilinx X-Power工具來(lái)測(cè)量SR-TCAM搜索操作活動(dòng)的功耗數(shù)據(jù)。我們通過(guò)以在100MHz時(shí)鐘速率時(shí)，1000次搜索操作的平均值來(lái)計(jì)算功耗，以獲得更好的功耗估計(jì)。

4 結(jié)束語(yǔ)

本文研究了在Xilinx Kintex-7 FPGA芯片上實(shí)現(xiàn)512×36 SR-TCAM，給出了設(shè)計(jì)架構(gòu)和工作流程，并給出了4種不同的設(shè)計(jì)方法，以驗(yàn)證SR-TCAM的可行性和實(shí)用性。下一步的工作會(huì)將SR-TCAM應(yīng)用于網(wǎng)絡(luò)安全設(shè)備的深度包過(guò)濾、應(yīng)用協(xié)議識(shí)別、病毒檢測(cè)等功能的硬件實(shí)現(xiàn)。

[1]彭坤楊.基于TCAM的高速可擴(kuò)展的正則表達(dá)式匹配技術(shù)[D].安徽:中國(guó)科學(xué)技術(shù)大學(xué)，2013.

[2]屠振，梁進(jìn)山，楊奎武. TCAM在高速路由查找中的應(yīng)用及其FPGA實(shí)現(xiàn)[J].微計(jì)算機(jī)信息，2015.

[3]張建偉.一種低功耗、抗軟錯(cuò)誤的TCAM系統(tǒng)設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(jī)，2015．

[4]陳世文，黃萬(wàn)偉.一種深度包檢查引擎的FPGA硬件實(shí)現(xiàn)[J].測(cè)控技術(shù)，2014.

[5]劉瀟， 高峻.用FPGA實(shí)現(xiàn)較大規(guī)模的CAM[J].電子工程師，2013.

[6]徐欣，李宗華.基于FPGA的內(nèi)容可尋址存儲(chǔ)研究設(shè)計(jì)與應(yīng)用[J].國(guó)防科技大學(xué)學(xué)報(bào)，2011.

[7]K.Pagiamtzis.Content-Addressable Memory (CAM) Circuits and Architectures[J].IEEE Journal of Solid-State Circuits，2012.

[8]Xilinx. ModelSim SE User Guide.http://www.xilinx.com.