片上TCAM的研究和應(yīng)用

許 俊 ，龔源泉 ，李 麗

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

1 TCAM簡介

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

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

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

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

但是TCAM也有不足之處，主要體現(xiàn)在兩個方面：一個是相比較于SRAM和DRAM，它的存儲密度很低，擺放密度也低；另外，TCAM做查找的時候，功耗特別大（因為需要所有的條目并行作比較）。

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

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

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

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

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

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

IBM 32 nm工藝庫提供的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查找時，F(xiàn)E0和FE2自動拼接成160 bit與key做匹配，并且結(jié)果輸出到MLLA[1 023：0]，每個 bit代表一個條目的查找結(jié)果，F(xiàn)E1和FE3自動拼接成另外一個160 bit與key做匹配，并且輸出結(jié)果到MLLB[1 023：0]，通過外部設(shè)計的電路，先把MLLA[1 023：0]中最小的匹配地址找出來（通過優(yōu)先級編碼器），同時把MLLB[1 023：0]中最小匹配地址找出來，最后比較MLLA和MLLB中哪個匹配地址最小，取小優(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ù)多少直接影響到芯片的面積大小，前面提到過TCAM本身物理的面積就比DRAM和SRAM大，此外，TCAM由于在做查找時需要把輸入的內(nèi)容和存儲的所有條目同時作比較，會導(dǎo)致片上供給TCAM的電源噪聲變大。為了解決這個問題，一般需要在TCAM之間插入大的片上去耦電容，再加上需要把優(yōu)先級編碼電路和相關(guān)的寄存器緊靠著TCAM擺放，因此需要TCAM塊與塊之間有一定的間隔。圖3顯示了在45 nm工藝下16塊TCAM在硅片上的擺放面積是 3.231 5 mm2（=2.81 mm×1.15 mm），相比較于 TCAM本身的面積（1.59 mm2），大了將近一倍。所以，從這個層面上而言，構(gòu)建相同大小的查找表，TCAM的塊數(shù)越多越不好。

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

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

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

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

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

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

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

此外，方案（a）比方案（b）會多一級流水線的延遲。

采用圖 5（b）所示的電路，可以實現(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]， 同時，TCAM#1 輸出 MLLA_1[63：0]和MLLB_1[63：0]。

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

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

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

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

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

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

（2）MLLA_0[63：0]每 個 比 特 和MLLB_0[63：0]的每個對應(yīng)比特位進(jìn)行“與”運算，得到 MLLAB_0[63：0]，再輸入到一個專門的6～64優(yōu)先級編碼器 ，輸 出 index320_0[5：0]和 hit320_0（圖中沒有標(biāo)示）；對于 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]， 過 程與前述類似，得到 index320[6：0]和 hit320。

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

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

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

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

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

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

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

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

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

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

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

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

[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.