許 俊 ，龔源泉 ，李 麗

（1.盛科網(wǎng)絡(luò)蘇州有限公司，江蘇 蘇州 215021；2.南京大學(xué) 江蘇省光電信息功能材料重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210093）

1 TCAM簡(jiǎn)介

三態(tài)內(nèi)容尋址存儲(chǔ)器 （TCAM）是一類特殊的存儲(chǔ)器，傳統(tǒng)的存儲(chǔ)器都是根據(jù)地址讀出內(nèi)容，例如靜態(tài)存儲(chǔ)器（SRAM）和動(dòng)態(tài)存取器（DRAM），但是 TCAM是根據(jù)存儲(chǔ)的內(nèi)容得到對(duì)應(yīng)的地址，輸入一個(gè)數(shù)據(jù)（稱為查找內(nèi)容或者查找key），TCAM內(nèi)部就把這個(gè) key和它所有存儲(chǔ)的條目作并行比較，然后把匹配的地址輸出，如果有多個(gè)條目都與這個(gè)查找key匹配，那么輸出最小的地址。

TCAM又有外掛和片上（內(nèi)嵌）之分，外掛TCAM原來(lái)有多家廠商提供，經(jīng)過(guò)一系列的并購(gòu)，目前只有博通公司和瑞薩電子可以提供商用的TCAM芯片。外掛TCAM一般適用于交換容量在100 Gb/s量級(jí)的路由交換芯片或者安全芯片。對(duì)于帶寬超過(guò)100 Gb/s以上的路由交換芯片或者安全芯片而言，直接在芯片內(nèi)部集成TCAM不失為一種好的選擇，特別是做并行訪問(wèn)控制列表（ACL）查找時(shí)，就特別需要片上TCAM。

片上TCAM有多個(gè)廠家可以提供不同的工藝庫(kù)，其中IBM的片上TCAM工藝庫(kù)是目前為止面積最優(yōu)、功耗最小且速度最快的片上TCAM工藝庫(kù)之一。

TCAM的基本單元由一個(gè)數(shù)據(jù)位（data）和一個(gè)掩碼位（mask）構(gòu)成，所以顧名思義稱為三態(tài)存儲(chǔ)器，當(dāng)輸入1 bit數(shù)據(jù)（input）時(shí)，當(dāng) input=data& mask，才算匹配。這時(shí)，TCAM會(huì)輸出一個(gè)命中（hit）指示，表示這個(gè)條目命中，這個(gè)特性讓TCAM在ACL、路由查表的最長(zhǎng)前綴匹配和模糊查找中特別有用。

但是TCAM也有不足之處，主要體現(xiàn)在兩個(gè)方面：一個(gè)是相比較于SRAM和DRAM，它的存儲(chǔ)密度很低，擺放密度也低；另外，TCAM做查找的時(shí)候，功耗特別大（因?yàn)樾枰械臈l目并行作比較）。

圖1顯示IBM 45 nm工藝下的TCAM與SRAM、DRAM的比較，TCAM只有1.10%的存儲(chǔ)容量（百萬(wàn)比特?cái)?shù)），卻占用所有存儲(chǔ)器8.64%的面積（如果考慮到擺放面積，這個(gè)數(shù)字還要加倍）和消耗10.31%的功耗。

圖1 TCAM和SRAM、DRAM的比較（IBM 45 nm）

本文基于IBM 32 nm工藝庫(kù)提供的TCAM的一些新特性和提供的優(yōu)先級(jí)編碼器硬核，通過(guò)特別設(shè)計(jì)的電路，可以同時(shí)滿足 160 bit、320 bit和 640 bit數(shù)據(jù)的查找，并且減少TCAM的塊數(shù)、降低TCAM的功耗。

2 片上TCAM外圍電路的設(shè)計(jì)

2.1 多種查找寬度電路設(shè)計(jì)

此前為了實(shí)現(xiàn)多種位寬key的查找，必須以最小key的位寬作為TCAM的位寬選擇。例如，需要同時(shí)支持160 bit、320 bit和 640 bit 3種 key位寬的查找，需要選擇TCAM的位寬必須是160 bit的，然后通過(guò)橫向拼接的方式實(shí)現(xiàn)320 bit和640 bit位寬的key寬度查找。

IBM 32 nm工藝庫(kù)提供的TCAM支持一種稱為列使能的方式。以1 024深度320 bit寬度的TCAM為例，圖2表示將320 bit寬度分成4列，每一列有80 bit位寬，4列分別是 FE0、FE1、FE2和FE3，其中 FE0和FE2是偶數(shù)列，F(xiàn)E1和FE3是奇數(shù)列。當(dāng)進(jìn)行160 bit查找時(shí)，F(xiàn)E0和FE2自動(dòng)拼接成160 bit與key做匹配，并且結(jié)果輸出到MLLA[1 023：0]，每個(gè) bit代表一個(gè)條目的查找結(jié)果，F(xiàn)E1和FE3自動(dòng)拼接成另外一個(gè)160 bit與key做匹配，并且輸出結(jié)果到MLLB[1 023：0]，通過(guò)外部設(shè)計(jì)的電路，先把MLLA[1 023：0]中最小的匹配地址找出來(lái)（通過(guò)優(yōu)先級(jí)編碼器），同時(shí)把MLLB[1 023：0]中最小匹配地址找出來(lái)，最后比較MLLA和MLLB中哪個(gè)匹配地址最小，取小優(yōu)先，如果值相等，則優(yōu)先取MLLA的結(jié)果作為最終結(jié)果。

圖2 TCAM列查找示意（IBM 32 nm）

這樣，TCAM的最小寬度就不必是160 bit，可以是320 bit，與之前的需要 160 bit寬度的 TCAM相比，構(gòu)建相同大小的查找表，TCAM的塊數(shù)可以減少一半。

TCAM的塊數(shù)多少直接影響到芯片的面積大小，前面提到過(guò)TCAM本身物理的面積就比DRAM和SRAM大，此外，TCAM由于在做查找時(shí)需要把輸入的內(nèi)容和存儲(chǔ)的所有條目同時(shí)作比較，會(huì)導(dǎo)致片上供給TCAM的電源噪聲變大。為了解決這個(gè)問(wèn)題，一般需要在TCAM之間插入大的片上去耦電容，再加上需要把優(yōu)先級(jí)編碼電路和相關(guān)的寄存器緊靠著TCAM擺放，因此需要TCAM塊與塊之間有一定的間隔。圖3顯示了在45 nm工藝下16塊TCAM在硅片上的擺放面積是 3.231 5 mm2（=2.81 mm×1.15 mm），相比較于 TCAM本身的面積（1.59 mm2），大了將近一倍。所以，從這個(gè)層面上而言，構(gòu)建相同大小的查找表，TCAM的塊數(shù)越多越不好。

圖3 片上TCAM擺放面積（2.81 mm×1.15 mm，IBM 45 nm）

此前為了解決TCAM查找結(jié)果MLL（匹配位）輸出的時(shí)序問(wèn)題，可行的做法是將匹配的結(jié)果先用寄存器鎖存起來(lái)，再送給后續(xù)的優(yōu)先級(jí)編碼器。IBM 32 nm的工藝庫(kù)新提供了6～64的優(yōu)先級(jí)編碼器硬核，可以解決時(shí)序問(wèn)題。

圖4顯示 IBM 32 nm提供的6～64的優(yōu)先級(jí)編碼器硬核，輸出信號(hào) HIT表示所有 MLL[63：0]作位“或”運(yùn)算之后的結(jié)果。

圖4 IBM 32 nm優(yōu)先級(jí)編碼器硬核（IBM 32 nm）

圖5（a）中顯示了采用用戶自己設(shè)計(jì)的6～64的優(yōu)先級(jí)編碼器時(shí)，必須將TCAM輸出的匹配結(jié)果先用寄存器鎖存一拍，然后才送給優(yōu)先級(jí)編碼器。圖 5（b）顯示，采用IBM 32 nm提供的優(yōu)先級(jí)編碼器硬核，可以直接把TCAM的匹配結(jié)果經(jīng)過(guò)一個(gè)或者兩個(gè)與門之后與優(yōu)先級(jí)編碼器的輸入對(duì)接，優(yōu)先級(jí)編碼器的輸出再進(jìn)入寄存器鎖存起來(lái)。

表1比較了兩種方案所需要的資源，可以看到，TCAM的匹配結(jié)果需要的鎖存寄存器可以全部節(jié)約下來(lái)，只要TCAM的深度越大，節(jié)約的寄存器就越多，以支持 16 384個(gè) 160 bit寬度的 ACL條目為例，方案（a）需要額外多出16 384個(gè)寄存器。

表1 兩種方案所需要的資源比較

此外，方案（a）比方案（b）會(huì)多一級(jí)流水線的延遲。

采用圖 5（b）所示的電路，可以實(shí)現(xiàn) 160 bit、320 bit和640 bit 3種key寬度的查找。

160 bit寬度key的查找流程如下：

（1）TCAM#0 輸 出 匹 配 結(jié) 果 MLLA_0 [63：0]和MLLB_0[63：0]， 同時(shí)，TCAM#1 輸出 MLLA_1[63：0]和MLLB_1[63：0]。

（2）MLLA_0[63：0]經(jīng) 過(guò) 6～64 優(yōu) 先 級(jí) 編碼 器，輸 出indexA_0[5：0]和 hitA_0（圖中沒(méi)有標(biāo)示出來(lái)）。 同樣地，對(duì)于 MLLB_0[63：0]、MLLA_1[63：0]和 MLLB_1[63：0]經(jīng)過(guò)各自對(duì)應(yīng)的優(yōu)先級(jí)編碼器， 輸出 indexB_0[5：0]、indexA_1[5：0]和 indexB_1[5：0]， 以及對(duì)應(yīng)的 hitB_0、hitA_1和 hitB_1。

（3）indexA_0[6：0]和 indexB_0[6：0]比較，如果 hitA_0和hitB_0二者只有一個(gè)為1，那么選擇對(duì)應(yīng)的index輸出；如果 hitA_0和 hitB_0均為 1（表示都有匹配到），則選擇indexA_0輸出。當(dāng)選中indexA_0時(shí)，輸出indexAB_0[6：0]={indexA_0[5：0]，1′b0}， 最 低 位補(bǔ)0；當(dāng)選中indexB_0時(shí)，輸出indexAB_0 [6：0]={indexB_0[5：0]，1′b1}，最低位補(bǔ)1，此外還需要把 hitA_0和hitB_0作位“或”運(yùn)算輸出 hitAB_0。

（4）對(duì) 于 indexA_1 [6：0]和indexB_1[6：0]有同樣的操作，得到結(jié)果 indexAB_1[6：0]和 hitAB_1。

（5）比 較 indexAB_0 [6：0]和indexAB_1[6：0]，操作過(guò)程類似于步驟（3）， 最 后 得 到 index160 [7：0]和hit160。

320 bit寬度key的查找流程如下：

（1）TCAM#0 輸 出 匹 配 結(jié) 果MLLA_0[63：0]和 MLLB_0[63：0]， 同時(shí) ，TCAM#1 輸 出 MLLA_1[63：0]和MLLB_1[63：0]。

（2）MLLA_0[63：0]每 個(gè) 比 特 和MLLB_0[63：0]的每個(gè)對(duì)應(yīng)比特位進(jìn)行“與”運(yùn)算，得到 MLLAB_0[63：0]，再輸入到一個(gè)專門的6～64優(yōu)先級(jí)編碼器 ，輸 出 index320_0[5：0]和 hit320_0（圖中沒(méi)有標(biāo)示）；對(duì)于 MLLA_1[63：0]和MLLB_1[63：0]，有 同 樣 的 操 作 ，把 MLLAB_1[63：0]（=MLLA_1[63：0]&MLLB_1[63：0]）輸出 index320_1[5：0]和 hit320_1。

（3）比 較 index320_0[5：0]和 index320_1[5：0]， 過(guò) 程與前述類似，得到 index320[6：0]和 hit320。

640 bit寬度key的查找流程如下。

（1）將前述 320 bit寬度 key查找流程的步驟（2）得到的 MLLAB_0[63：0]和 MLLAB_1[63：0]再作一級(jí)按位“與”操作（MLLAB_0[63：0]& MLLAB_1[63：0]），結(jié)果輸出到優(yōu)先級(jí)編碼器中，得到 index640[5：0]和 hit640。

最后還有一級(jí)多路選擇器，根據(jù)全局配置，在index160[7：0]、index320[6：0]和 index640[5：0]三 者 之 間選擇一個(gè)作為最終結(jié)果輸出

上面設(shè)計(jì)的TCAM查找電路，與之前的設(shè)計(jì)相比，在需要同樣大小的查找表情況下，TCAM的塊數(shù)少一半，而且由于應(yīng)用了優(yōu)先級(jí)編碼器硬核，可以把第一級(jí)的鎖存寄存器全部省掉，此外還降低了TCAM的擺放面積和功耗。

2.2 利用TCAM的預(yù)查找功能降低查找功耗

IBM 32 nm工藝庫(kù)中的TCAM為了防止查找時(shí)的瞬間功耗過(guò)大，提供了一種預(yù)查找功能。TCAM橫向的塊稱為一個(gè)Bank，每個(gè)Bank包含128個(gè)條目，每個(gè)條目無(wú)論多少位寬，可以按照80 bit來(lái)切分，每80 bit的存儲(chǔ)數(shù)據(jù)可以分為兩級(jí)進(jìn)行查找，第一級(jí)查找稱為預(yù)查找，只匹配低 bit0～bit7總共 8 bit，如果這 8 bit沒(méi)有匹配，則后面的72 bit就不會(huì)參與比較運(yùn)算。

因此，每80 bit位中的低8 bit又可以稱為預(yù)查找比特位，這個(gè)功能對(duì)于用戶而言是透明的，但是需要用戶精心安排數(shù)據(jù)結(jié)構(gòu)，才能充分發(fā)揮這個(gè)特性，例如，把不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)志號(hào)放在這低8 bit。

從統(tǒng)計(jì)學(xué)上分析，如果所有數(shù)據(jù)足夠隨機(jī)化，每256個(gè)條目只會(huì)有一個(gè)條目匹配，也只有這個(gè)條目的后72 bit才會(huì)參與比較，這樣消耗的功耗只有原來(lái)的10%（=（256×8+72）/（256×80））。

圖6 TCAM預(yù)查找功能示意（IBM 32 nm）

值得一提的是，IBM 32 nm工藝庫(kù)的TCAM還同時(shí)提供功耗門控和深度休眠的方式來(lái)降低TCAM的動(dòng)態(tài)功耗，前者對(duì)于使用者是透明的，后者需要設(shè)計(jì)相應(yīng)的控制電路，而且從深度休眠的模式恢復(fù)到正常工作模式，至少需要100 ns的喚醒時(shí)間。

本文基于IBM 32 nm工藝庫(kù)提供的TCAM和優(yōu)先級(jí)編碼器硬核，通過(guò)設(shè)計(jì)相應(yīng)的外圍電路，充分利用該TCAM的特性和硬核IP，減少所需TCAM的塊數(shù)和外圍寄存器的數(shù)量，節(jié)省了TCAM在硅片上的擺放面積，同時(shí)降低了TCAM的功耗。本文提到的全部設(shè)計(jì)已經(jīng)在公司的第4代以太網(wǎng)路由交換ASIC芯片上實(shí)現(xiàn)。

后續(xù)的工作，將研究如何基于廠家提供的TCAM如何進(jìn)一步提高TCAM的查找性能。另一方面，將研究一些性能要求不高的場(chǎng)合下，如何充分利用TCAM的深度休眠功能，進(jìn)一步降低整個(gè)芯片的功耗。

[1]Embedded memory for Cu-32HP databook， SA15-6397-04，Revision 04[Z].2013.

[2]Embedded memory for Cu-45HP databook， SA15-6218-01，Revision 01[Z].2009.

[3]Huang Xiaohua.GAM cells and differential sense circuits for content addressable memory[P].U.S： US6744653 B1，2004-06-01.

[4]ARSOVSKI I，WISTORT R.Self-referenced sense amplifier for across-chip-variation immune sensing in high performance Content-Addresable Memories[C].Custom Integrated Circuits Conference， CICC′06， 2006：453-456.

[5]CHAO H J，LIU B.High performance switches and routers[M].John Wiley&Sons， Inc.， Publication， 2007.