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

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

?

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

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

（中國電子科技集團公司第三十研究所 四川 610041）

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

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

0 引言

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

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

表1 TCAM和SRAM的比較

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

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

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

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

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

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

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

圖2 比特位置表BPT

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

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

圖3 地址位置表APT

2 工作流程

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

步驟1：將待搜索的字輸入進SR-TCAM；

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

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

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

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

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

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

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

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

3 基于FPGA實現(xiàn)

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

[6]徐欣，李宗華.基于FPGA的內(nèi)容可尋址存儲研究設(shè)計與應(yīng)用[J].國防科技大學(xué)學(xué)報，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.