基于SRAM的TCAM設計與FPGA實現

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

?

基于SRAM的TCAM設計與FPGA實現

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

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

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

網絡安全；TCAM；FPGA；匹配地址

0 引言

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

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

表1 TCAM和SRAM的比較

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

1 架構設計

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

圖1 SR-TCAM的體系架構

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

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

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

圖2 比特位置表BPT

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

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

圖3 地址位置表APT

2 工作流程

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

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

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

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

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

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

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

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

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

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

3 基于FPGA實現

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

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

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

表2 各種設計所需資源和功耗

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

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

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

4 結束語

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

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

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

[3]張建偉.一種低功耗、抗軟錯誤的TCAM系統設計[J].微電子學與計算機，2015．

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

[5]劉瀟， 高峻.用FPGA實現較大規模的CAM[J].電子工程師，2013.

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