(杭州電子科技大學(xué)電子信息學(xué)院，浙江 杭州310018)

0 引 言

內(nèi)容可尋址存儲(chǔ)器(Content Addressable Memory，CAM)是一種特殊的存儲(chǔ)器件，不僅能存儲(chǔ)數(shù)據(jù)，而且能將輸入數(shù)據(jù)與內(nèi)部所有數(shù)據(jù)進(jìn)行比較，從而判定輸入數(shù)據(jù)是否已經(jīng)存在于存儲(chǔ)器內(nèi)。CAM可以在單個(gè)時(shí)鐘周期內(nèi)并行完成所有比較查找運(yùn)算，相比其他基于硬件或軟件的搜索系統(tǒng)，具有更高的查找效率，因而被廣泛運(yùn)用于網(wǎng)絡(luò)協(xié)議包分類與發(fā)送、數(shù)據(jù)包內(nèi)容檢測(cè)過濾、高速緩存和數(shù)據(jù)加密等眾多領(lǐng)域[1]。傳統(tǒng)CAM的設(shè)計(jì)與實(shí)現(xiàn)通常依靠專用集成電路技術(shù)(Application Specific Integrated Circuit，ASIC)，相關(guān)產(chǎn)品具有容量大、集成度高、速度快等優(yōu)點(diǎn)，但也存在價(jià)格昂貴、功耗偏高等不足[1-3]，這顯然不利于在更多的場(chǎng)合靈活地應(yīng)用CAM的強(qiáng)大功能。近年來，多種基于現(xiàn)場(chǎng)可編程邏輯陣列(Field Programmable Logic Array，F(xiàn)PGA)的CAM 等效功能塊構(gòu)建方案[4-6]出現(xiàn)。大多數(shù)方案成功模擬實(shí)現(xiàn)了傳統(tǒng)CAM 器件的高速查找特性，但在實(shí)用中卻普遍存在片內(nèi)資源開銷過多的缺點(diǎn)。本文在一種現(xiàn)有電路[5]的基礎(chǔ)上進(jìn)行了改進(jìn)，提出了一種新穎的等效邏輯電路。電路簡(jiǎn)潔易行，可根據(jù)實(shí)際存儲(chǔ)的單位數(shù)據(jù)字長(zhǎng)和數(shù)據(jù)控制精度調(diào)整數(shù)據(jù)寄存器與狀態(tài)寄存器的組成比例，從而在實(shí)現(xiàn)CAM 功能的同時(shí)減少邏輯資源的開銷。

1 CAM的傳統(tǒng)電路模型

單個(gè)CAM 單元實(shí)現(xiàn)兩種功能:1)存儲(chǔ)1 bit 預(yù)設(shè)數(shù)據(jù);2)將當(dāng)前輸入數(shù)據(jù)與預(yù)設(shè)數(shù)據(jù)進(jìn)行比較并輸出比較結(jié)果。在傳統(tǒng)電路模型中，一般使用單個(gè)SRAM 單元實(shí)現(xiàn)功能1，再在此基礎(chǔ)上額外添加若干晶體管實(shí)現(xiàn)功能2，如圖1所示。圖1中，兩個(gè)背靠背的反相器即構(gòu)成了一個(gè)SRAM 存儲(chǔ)單元，晶體管M1和M3以及晶體管M2和M4 分別構(gòu)成了兩條互補(bǔ)的查找電路，分別用于查找存儲(chǔ)在SRAM 單元中的數(shù)據(jù)“1”和數(shù)據(jù)“0”。查找成功時(shí)，數(shù)據(jù)匹配線ML為高電平，反之則為電平。由于SRAM 中預(yù)設(shè)存儲(chǔ)數(shù)據(jù)非‘0’即‘1’，該類CAM 單元總處于兩種狀態(tài)之一，因此通常被稱為二態(tài)內(nèi)容可尋址存儲(chǔ)器(Binary Content Addressable Memory，BCAM)。BCAM 只能存儲(chǔ)查找固定長(zhǎng)度的數(shù)據(jù)，為了避免為同時(shí)存儲(chǔ)不同長(zhǎng)度的數(shù)據(jù)而反復(fù)搭建不同長(zhǎng)度規(guī)格的BCAM 電路，可以使用長(zhǎng)度規(guī)格統(tǒng)一的三態(tài)內(nèi)容可尋址存儲(chǔ)器(Ternary Content Addressable Memory，TCAM)。TCAM 相比BCAM，優(yōu)勢(shì)在于多出一個(gè)“無關(guān)”狀態(tài)，即從“二態(tài)”變?yōu)榱恕叭龖B(tài)”。被設(shè)置為“無關(guān)”狀態(tài)的TCAM 單元不會(huì)對(duì)最終匹配結(jié)果產(chǎn)生影響，因此通過靈活調(diào)整設(shè)置不同TCAM 單元滿足對(duì)不同長(zhǎng)度數(shù)據(jù)的存儲(chǔ)與查找需求。典型的TCAM 單元結(jié)構(gòu)電路如圖2所示。圖2中，當(dāng)兩個(gè)SRAM 單元中存儲(chǔ)數(shù)據(jù)不一致時(shí)，分別表示BCAM 中已存在的兩種數(shù)據(jù)存儲(chǔ)狀態(tài);當(dāng)兩個(gè)數(shù)據(jù)同時(shí)為“1”時(shí)，表示TCAM 特有的“無關(guān)”狀態(tài);不允許兩個(gè)數(shù)據(jù)同時(shí)為“0”。

圖1 BCAM 單元傳統(tǒng)結(jié)構(gòu)電路

圖2 TCAM 單元傳統(tǒng)結(jié)構(gòu)電路

2 CAM 基于FPGA的等效邏輯電路

本文提出一種CAM 基于FPGA的等效邏輯電路，電路在實(shí)現(xiàn)傳統(tǒng)TCAM 單元邏輯功能的同時(shí)，根據(jù)不同數(shù)據(jù)單位字長(zhǎng)和數(shù)據(jù)控制精度要求優(yōu)化對(duì)寄存器和組合邏輯函數(shù)等片內(nèi)邏輯資源的開銷，從而獲得更高的資源利用效率。

2.1 CAM 單元結(jié)構(gòu)組成

等效邏輯電路主要包含:預(yù)存數(shù)據(jù)寄存器組、“無關(guān)”狀態(tài)寄存器、“已使用”狀態(tài)寄存器、數(shù)據(jù)比較器、掩碼電路和查找結(jié)果輸出寄存器。預(yù)存數(shù)據(jù)寄存器組的中寄存器的數(shù)量等于單位數(shù)據(jù)的字長(zhǎng)，還可按照實(shí)際需求進(jìn)行調(diào)整;數(shù)據(jù)比較器用于判定輸入待查找數(shù)據(jù)和預(yù)存數(shù)據(jù)的是否相同;“無關(guān)”狀態(tài)寄存器指示該CAM 單元的數(shù)據(jù)寄存器中相應(yīng)數(shù)據(jù)段是否處于“無關(guān)”狀態(tài)，其中數(shù)據(jù)為“1”表示處于“無關(guān)”狀態(tài)，“0”表示處于“相關(guān)”狀態(tài);“已使用”狀態(tài)寄存器記錄指示當(dāng)前CAM 單元是否已被啟用，即是否被寫入了有效數(shù)據(jù)，從而避免將未啟用單元中的初始數(shù)據(jù)誤認(rèn)為有效數(shù)據(jù)，進(jìn)而導(dǎo)致查找錯(cuò)誤;掩碼電路對(duì)數(shù)據(jù)比較器的輸出和“無關(guān)”狀態(tài)寄存器中內(nèi)容進(jìn)行求“或”運(yùn)算，再將結(jié)果與“已使用”狀態(tài)寄存器中內(nèi)容求“與”，只有在當(dāng)前CAM 單元已被啟用，且輸入數(shù)據(jù)與預(yù)設(shè)數(shù)據(jù)完全相同，或者不同部分已被設(shè)為“無關(guān)”，才會(huì)計(jì)算得出匹配成功的結(jié)果;最后的計(jì)算結(jié)果經(jīng)查找結(jié)果輸出寄存器寄存后，作為該CAM 單元的最終查找匹配結(jié)果輸出。

相比文獻(xiàn)[5]中的電路，新電路的改進(jìn)在于數(shù)據(jù)寄存器與“無關(guān)”狀態(tài)寄存器的數(shù)量比值不再被固定為1∶1，而是可以根據(jù)實(shí)際應(yīng)用需求靈活調(diào)整，該比值被稱為“無關(guān)”狀態(tài)寄存器的控制粒度?？刂屏６仍酱?，表示單個(gè)“無關(guān)”狀態(tài)寄存器可以控制更多的數(shù)據(jù)寄存器，從而減少“無關(guān)”狀態(tài)寄存器的數(shù)量。現(xiàn)有電路的控制粒度固定為1，每個(gè)“無關(guān)”狀態(tài)寄存器只控制一個(gè)數(shù)據(jù)寄存器，控制精度達(dá)到最高，但卻未必是所有應(yīng)用都需要的。例如使用CAM 查找字符串，由ASCII 碼描述的單個(gè)字符的字長(zhǎng)為8 bit，一旦將CAM 中某字符串的一個(gè)字符設(shè)置為“無關(guān)”，則相應(yīng)的8 bit數(shù)據(jù)總是同時(shí)受到掩蔽，因此完成上述功能只需使用一個(gè)“無關(guān)”狀態(tài)寄存器?？梢允褂每刂屏６葹?的新CAM 單元實(shí)現(xiàn)相同的功能，每個(gè)CAM 單元中，“無關(guān)”狀態(tài)寄存器的數(shù)量只相當(dāng)于現(xiàn)有單元電路中數(shù)量的1/8。圖3中顯示了一個(gè)經(jīng)綜合后生成的控制粒度為8，單位數(shù)據(jù)字?jǐn)?shù)為4的新型CAM 單元，新電路中每1 bit“無關(guān)”狀態(tài)碼都可以通過或門(虛線框內(nèi)所示)掩蔽8 bit數(shù)據(jù)碼的比較結(jié)果，而現(xiàn)有電路中則只能掩蔽1 bit數(shù)據(jù)碼的比較結(jié)果，因此節(jié)省了邏輯資源開銷。

圖3 新型CAM 單元實(shí)例

綜合生成1個(gè)控制粒度為n，單位數(shù)據(jù)字?jǐn)?shù)為k的新型CAM 單元所需的寄存器總量Areg為:

組合邏輯函數(shù)的開銷總量Alut可通過以下經(jīng)驗(yàn)歸納公式得到近似估算:

2.2 CAM 單元功能時(shí)序

首先執(zhí)行電路復(fù)位。執(zhí)行寫入操作時(shí)，讀寫模式使能端wren 置為高電平，使能預(yù)存數(shù)據(jù)寄存器組、“無關(guān)”狀態(tài)寄存器和“已使用”狀態(tài)寄存器，然后在下一個(gè)時(shí)鐘上升沿到來時(shí)通過預(yù)存數(shù)據(jù)輸入端wdata和“無關(guān)”狀態(tài)設(shè)置端dncare 對(duì)二者中數(shù)據(jù)進(jìn)行更新，“已使用”狀態(tài)寄存器中寫入“1”，表示該CAM 單元以得到使用，其中存儲(chǔ)的數(shù)據(jù)有效;同時(shí)通過掩碼電路中的多路選擇器，將查找匹配結(jié)果鎖定在低電平，表示未執(zhí)行查找操作;執(zhí)行查找操作時(shí)，wren 置為低電平，允許掩碼電路正常工作，然后從查找數(shù)據(jù)輸入端sdata 寫入數(shù)據(jù)，在下一個(gè)時(shí)鐘上升沿到來時(shí)，查找匹配結(jié)果輸出端mhit 輸出相應(yīng)的查找結(jié)果，高、低電平分別表示“找到”和“未找到”。對(duì)圖3中電路執(zhí)行寫入操作和查找操作的功能時(shí)序如圖4所示。其中，執(zhí)行寫入操作1時(shí)未將CAM 單元中任何數(shù)據(jù)段置為“無關(guān)”狀態(tài)，因此執(zhí)行查找操作1時(shí)CAM 單元報(bào)告只能找到數(shù)據(jù)“abcd”而未找到數(shù)據(jù)“abce”;執(zhí)行寫入操作2時(shí)將CAM 單元中最后8 bit數(shù)據(jù)置為“無關(guān)”狀態(tài)，因此執(zhí)行查找操作2時(shí)CAM 單元報(bào)告既可以找到數(shù)據(jù)“abcd”也可以找到數(shù)據(jù)“abce”。

圖4 實(shí)例CAM 單元的操作功能時(shí)序圖

2.3 完整的CAM 模塊

完整的CAM 功能模塊主要包括:CAM 單元矩陣、預(yù)設(shè)數(shù)據(jù)寄存器、預(yù)設(shè)地址譯碼器、命中信號(hào)生成器和查找地址編碼器。CAM 單元矩陣用于存儲(chǔ)特定規(guī)格的預(yù)設(shè)數(shù)據(jù)，它的列數(shù)即為預(yù)設(shè)單位數(shù)據(jù)的字長(zhǎng)，行數(shù)即為預(yù)設(shè)單位數(shù)據(jù)的最大可能存儲(chǔ)量，行內(nèi)CAM 單元的數(shù)據(jù)匹配線級(jí)聯(lián)，行內(nèi)所有CAM 單元的同時(shí)匹配成功才等價(jià)于當(dāng)前完整輸入數(shù)據(jù)的匹配成功，行間CAM 單元并聯(lián)，以實(shí)現(xiàn)對(duì)所有行的并行查找;數(shù)據(jù)寄存器用于在預(yù)設(shè)數(shù)據(jù)和查找數(shù)據(jù)時(shí)暫時(shí)寄存輸入內(nèi)容;預(yù)設(shè)地址譯碼器工作于預(yù)設(shè)數(shù)據(jù)階段，它將輸入的二進(jìn)制地址轉(zhuǎn)變?yōu)楠?dú)熱碼，然后激活相應(yīng)的CAM 單元行，使之接受數(shù)據(jù)寫入操作;命中信號(hào)生成器和查找地址編碼器都工作于數(shù)據(jù)查找階段，前者指示當(dāng)前輸入內(nèi)容是否得到匹配，后者負(fù)責(zé)將CAM 單元矩陣輸出的獨(dú)熱碼轉(zhuǎn)變?yōu)槎M(jìn)制地址輸出。完整的CAM 模塊圖如圖5所示。

圖5 完整的m×n CAM 模塊圖

3 電路綜合與分析

為了分析構(gòu)建本文提出的新電路所需的資源開銷及其性能，使用Altera 公司出品的Quartus II 12.0軟件在該公司生產(chǎn)的FPGA 芯片EP2C35F484C8 上構(gòu)建規(guī)格為m×128的完整CAM 模塊，其中m 分別取值為8 bit、16 bit、24 bit和32 bit，“無關(guān)”狀態(tài)寄存器的控制粒度g 分別取值為2、4、8。同時(shí)，使用文獻(xiàn)[5]的方法，在同一芯片上構(gòu)建相同規(guī)格的CAM 模塊以供比較。電路分析和綜合的過程中選擇的優(yōu)化策略都為“平衡”。不同規(guī)模下寄存器、組合邏輯函數(shù)和邏輯單元(Logic element，LE)等3種資源的開銷對(duì)比顯示在圖6、圖7和圖8中，最高工作時(shí)鐘頻率的比較則記錄在表1中。

通過分析上述圖表中的數(shù)據(jù)可知，實(shí)現(xiàn)相同規(guī)格的CAM 模塊，新電路的邏輯資源消耗明顯少于現(xiàn)有電路，且隨著控制粒度g的增大，優(yōu)勢(shì)愈發(fā)明顯。此外，經(jīng)過相同強(qiáng)度的時(shí)鐘約束優(yōu)化，新電路的最高工作時(shí)鐘頻率也普遍高于現(xiàn)有電路，且不會(huì)隨著g值變化出現(xiàn)較大的起伏，具有較好的穩(wěn)定性。當(dāng)單位數(shù)據(jù)字長(zhǎng)為32 且g=8時(shí)，新電路的最高工作時(shí)鐘頻率為152.74 MHz，電路的最高吞吐量可達(dá)到4.9 Gbps，足以滿足大部分應(yīng)用需求。上述數(shù)據(jù)分析表明，新電路特別適合于存儲(chǔ)和查找具有較大單位數(shù)據(jù)字長(zhǎng)且所需控制精度不高的數(shù)據(jù)，如ASCII 字符和字符串。

圖6 寄存器開銷對(duì)比

圖7 組合邏輯函數(shù)開銷對(duì)比

圖8 邏輯單元開銷對(duì)比

表1 最高工作時(shí)鐘頻率比較

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

本文提出了一種內(nèi)容可尋址存儲(chǔ)器的等效邏輯電路。本電路可以根據(jù)實(shí)際數(shù)據(jù)字長(zhǎng)需求靈活地調(diào)節(jié)基本單元的電路組成，在實(shí)現(xiàn)CAM 功能的同時(shí)顯著減少寄存器等邏輯資源的開銷，提高FPGA 片內(nèi)邏輯資源的使用效率，同時(shí)還可以運(yùn)行在較高的工作頻率，在較高的工作頻率，因此具有一定的工程實(shí)用價(jià)值。

[1]Kostas P，Ali S.Content-addressable memory (CAM)circuits and architectures:a tutorial and survey[J].IEEE Journal of Solid-State Circuits，2006，41(3):712-727.

[2]Yang B D，Lee Y K，Sung S W，et al.A low power content addressable memory using low swing search lines[J].IEEE Transactions on Circuits and Systems，2011，58(12):2 849-2 858.

[3]Igor A，Travis H，Daniel D，et al.A 32 nm 0.58-fJ/bit/search 1-GHz tenary content addressable memory compiler using silicon-aware early predict late-correct sensing with embedded deep-trench capacitor noise mitigation[J].IEEE Journal of Solid-State Circuits，2013，48(4):932-939.

[4]Brelet J L.Using Block RAM for High Performance Read/Write CAMs[EB/OL].http://www.xilinx.com/support/documentation/application_notes/xapp204.pdf，2000-05-02.

[5]Altera Corporation.Advanced Synthesis Cookbook[EB/OL].www.altera.com/literature/manual/stx_cookbook.pdf，2011-07-01.

[6]Zahid U，Kim I，Sanghyeon B.Hybrid Partitioned SRAM-based ternary content addressable memory[J].IEEE Transactions on Circuits and Systems，2012，59(12):2 969-2 979.