王昉 閆振林 張兵 楊怡平 靳新波

摘要：隨著網(wǎng)絡(luò)應(yīng)用的不斷豐富，包括路由、QoS保障等在內(nèi)的復(fù)雜業(yè)務(wù)對(duì)以太網(wǎng)通信設(shè)備的數(shù)據(jù)檢索匹配能力提出了更高的要求，因此基于內(nèi)容可尋址存儲(chǔ)器（Content Addressalle Memory，CAM）的以太網(wǎng)通信芯片及其數(shù)據(jù)查找機(jī)制成為研究的熱點(diǎn)。然而此類通信芯片存儲(chǔ)器所使用的優(yōu)先級(jí)編碼及檢索方法大多針對(duì)固定位寬數(shù)據(jù)，難以支持新業(yè)務(wù)對(duì)多種位寬數(shù)據(jù)進(jìn)行靈活檢索的需求。針對(duì)這一問題，提出了一種以太網(wǎng)通信芯片的優(yōu)先級(jí)編碼方法，使得CAM支持適應(yīng)多種查找模式。通過比較，該方法能使以太網(wǎng)通信芯片具有更多位寬數(shù)據(jù)的搜索能力，同時(shí)減少對(duì)線道的要求。

關(guān)鍵詞：以太網(wǎng)通信芯片；內(nèi)容可尋址存儲(chǔ)器；多種搜索位寬；優(yōu)先級(jí)編碼

中圖分類號(hào)：TP333文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2022）24-60-4

0引言

在以太網(wǎng)通信設(shè)備中，用來存放程序和數(shù)據(jù)[1]的存儲(chǔ)器有著不可或缺的作用。傳統(tǒng)的計(jì)算機(jī)存儲(chǔ)器（RAM或ROM）使用地址來指示存儲(chǔ)單元的位置，并且輸出該位置存儲(chǔ)單元中的數(shù)據(jù)。而內(nèi)容可尋址存儲(chǔ)器（Content Addressalle Memory，CAM）則接收外部檢索數(shù)據(jù)，比較該數(shù)據(jù)與CAM中存儲(chǔ)的數(shù)據(jù)是否匹配，并且輸出該匹配數(shù)據(jù)在CAM中的地址。由于存儲(chǔ)器中與檢索數(shù)據(jù)相一致的數(shù)據(jù)通常不限于一個(gè)，因此，當(dāng)以太網(wǎng)通信芯片CAM中有多個(gè)與檢索數(shù)據(jù)相一致的數(shù)據(jù)時(shí)，一般需要使用優(yōu)先級(jí)編碼器對(duì)從存儲(chǔ)單元輸出的一致信號(hào)（表示與檢索數(shù)據(jù)相一致的信號(hào)）進(jìn)行編碼，并返回優(yōu)先級(jí)最高的地址信號(hào)。因此，以太網(wǎng)通信使用的存儲(chǔ)器通常為CAM。

由于CAM的應(yīng)用越來越廣泛，而不同領(lǐng)域的應(yīng)用所需的搜索數(shù)據(jù)位寬往往是不一樣的。因此需要在不損失容量的情況下，提供多種搜索位寬的選擇。傳統(tǒng)做法是由多個(gè)最小寬度的模塊來進(jìn)行拼接，將每個(gè)小模塊的匹配結(jié)果都輸出到優(yōu)先級(jí)編碼器中，并進(jìn)行不同的組合，計(jì)算出不同配置下最高優(yōu)先級(jí)的地址。很顯然，這種方式每增加一種位寬，布線通道就需增加一倍，不能滿足集成電路的需求。同時(shí)，隨著復(fù)雜路由、QoS保障等業(yè)務(wù)對(duì)以太網(wǎng)通信芯片的CAM提出了越來越靈活又復(fù)雜的數(shù)據(jù)搜索需求，其突出表現(xiàn)為搜索數(shù)據(jù)對(duì)象位寬往往非固定，使得針對(duì)固定位寬的優(yōu)先級(jí)編碼方法難以適應(yīng)。針對(duì)這個(gè)問題，本文從優(yōu)先級(jí)編碼方法的改進(jìn)入手，提出了一種以太網(wǎng)通信芯片的優(yōu)先級(jí)編碼方法。

1相關(guān)理論

1.1 CAM

CAM是以內(nèi)容進(jìn)行尋址的存儲(chǔ)器，是一種特殊的存儲(chǔ)陣列RAM。CAM在其每個(gè)存儲(chǔ)單元都包含了一個(gè)內(nèi)嵌的比較邏輯，寫入CAM的數(shù)據(jù)會(huì)和其內(nèi)部存儲(chǔ)的每一個(gè)數(shù)據(jù)進(jìn)行比較，并返回與端口數(shù)據(jù)相同的所有內(nèi)部數(shù)據(jù)的地址[2]。RAM是一個(gè)根據(jù)地址讀、寫數(shù)據(jù)的存儲(chǔ)單元，而CAM和RAM恰恰相反，返回的是與端口數(shù)據(jù)內(nèi)容相匹配的地址。

一次典型的CAM查找操作過程為：首先，CAM接收外部的查找命令并把查找數(shù)據(jù)存儲(chǔ)到比較寄存器中，比較寄存器和掩碼寄存器的內(nèi)容共同組成系統(tǒng)的一個(gè)查找字（search word），這些查找字廣播到每一組相關(guān)聯(lián)字中，每一組相關(guān)聯(lián)字都有一個(gè)匹配鏈（matchline），匹配鏈指示查找字與存儲(chǔ)字是否一致（匹配或不匹配），匹配鏈把結(jié)果反饋到優(yōu)先譯碼器中，優(yōu)先譯碼器產(chǎn)生一個(gè)二進(jìn)制的匹配位置定位和一個(gè)匹配命中信號(hào)[3]。由于在CAM中可能存在多個(gè)字同時(shí)匹配，因而使用了一個(gè)優(yōu)先譯碼器而不是簡(jiǎn)單的譯碼器。當(dāng)有多個(gè)字同時(shí)匹配時(shí)，優(yōu)先譯碼器選擇最高優(yōu)先權(quán)的匹配地址映射到匹配結(jié)果，在CAM中低地址字具有高優(yōu)先權(quán)[4]。

1.2優(yōu)先級(jí)編碼

編碼器是一種將信息由一種特定格式（或編碼）轉(zhuǎn)換為其他特定格式（或編碼）的傳感器、軟件或算法，轉(zhuǎn)換的目的可能是為了標(biāo)準(zhǔn)化、速度、保密性、保安或是為了壓縮數(shù)據(jù)。而優(yōu)先編碼器允許同時(shí)在幾個(gè)輸入端有輸入信號(hào)，編碼器按輸入信號(hào)排定的優(yōu)先順序，只對(duì)同時(shí)輸入的幾個(gè)信號(hào)中優(yōu)先權(quán)最高的一個(gè)進(jìn)行編碼[5]。優(yōu)先編碼器常用于在處理最高優(yōu)先級(jí)請(qǐng)求時(shí)控制中斷請(qǐng)求。如果同時(shí)有2個(gè)或以上的輸入作用于優(yōu)先編碼器，優(yōu)先級(jí)最高的輸入將會(huì)被優(yōu)先輸出[6]。

2設(shè)計(jì)思路

隨著網(wǎng)絡(luò)應(yīng)用的發(fā)展，包括復(fù)雜路由、QoS保障在內(nèi)的業(yè)務(wù)對(duì)以太網(wǎng)通信芯片提出了更為靈活和復(fù)雜的數(shù)據(jù)搜索需求，傳統(tǒng)芯片固定位寬的優(yōu)先級(jí)編碼方式很難滿足其需求[7]。因此，在不損失CAM容量的前提下，本文擬對(duì)現(xiàn)有存儲(chǔ)器的編碼方法進(jìn)行改進(jìn)，使其支持多種搜索位寬，具體改進(jìn)思路如下：為了實(shí)現(xiàn)多種搜索位寬，首先提出最小寬度模塊的概念，通過多個(gè)最小寬度模塊來進(jìn)行拼接，將每個(gè)小模塊的匹配結(jié)果都輸出到優(yōu)先級(jí)編碼器（PE）中，在優(yōu)先級(jí)編碼器中進(jìn)行不同的組合，并計(jì)算出不同配置下最高優(yōu)先級(jí)的地址[8]。支持4種不同搜索位寬的CAM芯片傳統(tǒng)實(shí)現(xiàn)方法結(jié)構(gòu)如圖1所示，將PE放在中間，CAM陣列放在兩邊。該示例共放置了8個(gè)CAM陣列，能實(shí)現(xiàn)4種不同比較位寬的配置（即1，2，4，8倍位寬），CAM陣列在版圖上需要提供3走線通道。如果放置16個(gè)陣列，則可以多一種16倍位寬的配置，走線通道則上升到7根[9]。

通過這個(gè)方式，每增加一種位寬，布線通道就需增加一倍，這在集成電路領(lǐng)域是不可取的。特別是隨著特征尺寸的減小，CAM基本單元面積越來越小，形狀也會(huì)越來越扁，版圖上所能提供的走線資源更加稀缺，一般只有幾根而已[9]。而這個(gè)方法在支持多種位寬搜索時(shí)，由于對(duì)芯片內(nèi)部布線通道需求巨大，其所能提供的不同位寬模式種類也受到極大限制，無法提供更多模式來滿足不同應(yīng)用領(lǐng)域的需求。因此，這種優(yōu)先級(jí)編碼的方式很難提供4種或4種以上不同位寬配置的以太網(wǎng)通信芯片CAM。為此，提出了一種以太網(wǎng)通信芯片的優(yōu)先級(jí)編碼方法來克服這個(gè)問題，使一顆芯片具有支持更多搜索位寬的能力。

3優(yōu)先級(jí)編碼方法

3.1傳統(tǒng)優(yōu)先級(jí)編碼方式

在CAM單元整列中存儲(chǔ)數(shù)據(jù)，搜索的數(shù)據(jù)從搜索數(shù)據(jù)寄存器發(fā)送至CAM單元整列，如圖2所示。然后，將該搜索數(shù)據(jù)與存儲(chǔ)在CAM單元整列中的數(shù)據(jù)進(jìn)行比較，如果存儲(chǔ)的數(shù)據(jù)與搜索的數(shù)據(jù)相匹配，則將匹配線的邏輯電平設(shè)為高，反之則為低。最后，匹配線檢測(cè)單元檢測(cè)匹配線的邏輯電平。優(yōu)先級(jí)編碼器接收來自該檢測(cè)單元的輸出，并且輸出匹配的CAM單元的字線地址[10]。

3.2支持多種查找模式的優(yōu)先級(jí)編碼方法

因此，本文提出了一種以太網(wǎng)通信芯片的優(yōu)先級(jí)編碼方法，對(duì)以太網(wǎng)通信芯片CAM進(jìn)行如下操作：

①將CAM陣列分組，每組有一個(gè)底層優(yōu)先級(jí)編碼器，該優(yōu)先級(jí)編碼器放置于該分組物理實(shí)現(xiàn)的中間位置；

②底層優(yōu)先級(jí)編碼器對(duì)CAM陣列分組中每個(gè)字的比較結(jié)果進(jìn)行處理，按照不同的配置計(jì)算出是否匹配，并將該新的匹配結(jié)果輸出給上一層的優(yōu)先級(jí)編碼器A，底層優(yōu)先級(jí)編碼器同時(shí)生成組內(nèi)CAM模塊的塊地址；

③優(yōu)先級(jí)編碼器A對(duì)底層優(yōu)先級(jí)編碼器的匹配結(jié)果進(jìn)行處理，按照不同的配置進(jìn)行計(jì)算，計(jì)算出是否匹配，并將該匹配結(jié)果輸出給更上層的優(yōu)先級(jí)編碼器B，優(yōu)先級(jí)編碼器A同時(shí)需要對(duì)底層編碼器產(chǎn)生的低位塊地址進(jìn)行選擇，與該編碼器生成的高位塊地址合在一起，生成新的塊地址；

④優(yōu)先級(jí)編碼器B對(duì)優(yōu)先級(jí)編碼器A的匹配結(jié)果進(jìn)行處理，按照不同的配置進(jìn)行計(jì)算，計(jì)算出是否匹配，并將該匹配結(jié)果輸出給優(yōu)先級(jí)編碼器B的上一層優(yōu)先級(jí)編碼器C，優(yōu)先級(jí)編碼器B同時(shí)需要對(duì)優(yōu)先級(jí)編碼器A產(chǎn)生的低位塊地址進(jìn)行選擇，與該編碼器生成的高位塊地址合在一起，生成新的塊地址；

⑤以此類推，直至頂層；

⑥頂層優(yōu)先級(jí)編碼器對(duì)下一層優(yōu)先級(jí)編碼器的匹配結(jié)果進(jìn)行處理，按照不同的配置計(jì)算出是否匹配，并對(duì)該匹配結(jié)果進(jìn)行優(yōu)先級(jí)編碼，產(chǎn)生行地址；頂級(jí)優(yōu)先級(jí)編碼器同時(shí)需對(duì)下一層編碼器產(chǎn)生的低位塊地址進(jìn)行選擇，與該編碼器生成的高位塊地址合在一起，生成最終的塊地址。

其中，底層編碼器的電路由1個(gè)最高優(yōu)先級(jí)電路和1024個(gè)匹配計(jì)算單元組成[11]。CAM陣列的結(jié)果會(huì)輸出給相應(yīng)行的匹配計(jì)算單元，得出不同配置下的匹配結(jié)果MOUT；在80 bit模式下，mf0，mf1，mf2和mf3中只要有一個(gè)匹配，則輸出是匹配的，并用塊地址[1；0]來表示是哪一個(gè)模塊匹配，1 024個(gè)計(jì)算單元會(huì)得出1 024個(gè)匹配結(jié)果MOUT[12]；底層優(yōu)先級(jí)電路則會(huì)判斷出命中的匹配單元中優(yōu)先級(jí)最高的那個(gè)，并將該單元所在模塊的塊地址作為底層PE的塊地址輸出[13]。

在上述步驟⑥中，底層PE輸出的匹配結(jié)果MOUT會(huì)作為頂層匹配計(jì)算單元的輸入，在80/160/320 bit模式中，只要MOUTO或MOUT1中有1個(gè)匹配，則輸出MO是匹配的，并用塊地址來表示相應(yīng)的CAM陣列[14]；頂層最高優(yōu)先級(jí)電路會(huì)判斷出命中的匹配單元中優(yōu)先級(jí)最高的那個(gè)，輸出該單元的行地址，同時(shí)將該單元的塊地址作為該頂層PE的塊地址輸出。

在該優(yōu)先級(jí)編碼方法中，8個(gè)CAM陣列被分成2組，如圖3所示，每組CAM陣列的匹配結(jié)果都被輸出到底層PE中，底層PE會(huì)輸出不同配置下的匹配結(jié)果，并輸出匹配的塊地址；頂層PE會(huì)根據(jù)底層優(yōu)先級(jí)編碼器PE的匹配結(jié)果判斷出最終的匹配結(jié)果，并計(jì)算出行地址和最高位的塊地址。根據(jù)該高位塊地址，可以選出最終的低位塊地址；每個(gè)字需2條走線，一條線是BLK3將匹配結(jié)果輸出給底層PE，另一條線則是底層PE將新的匹配結(jié)果輸出給頂層PE。

3.3線道數(shù)目比較

不同于傳統(tǒng)CAM芯片將所有匹配輸出都送到一個(gè)優(yōu)先級(jí)編碼器生成所有地址的方式，本方法中有不同層次的PE，其中頂層優(yōu)PE只生成行地址，塊地址則是在局部編碼器中生成，所有輸入頂層PE的匹配線結(jié)果都會(huì)在局部PE中進(jìn)行簡(jiǎn)化處理。利用該方式，4種不同位寬的配置的芯片只需2條布線通道，5種位寬的配置也只需3條線道，大大減少了版圖對(duì)布線通道的需求。同時(shí)通過這種方式，一款CAM芯片就可以擁有更多種的位寬配置，在同時(shí)支持多種位寬模式時(shí)，降低了版圖對(duì)布線通道的需求，可以使芯片擁有更多種的位寬配置，被更靈活地應(yīng)用于多重領(lǐng)域。

傳統(tǒng)方式所需線道數(shù)目是2-1-1，而本方法所需線道數(shù)目是-2，如圖4所示，傳統(tǒng)方法所需線道數(shù)目明顯比本方法所需的線道數(shù)目多。由此可見，本方法能大大減少支持多種搜索位寬的以太網(wǎng)通信芯片對(duì)線道的需求，可以使一顆以太網(wǎng)通信芯片具有支持更多搜索位寬的能力。

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

本文針對(duì)現(xiàn)有以太網(wǎng)通信芯片的CAM對(duì)多種位寬數(shù)據(jù)的檢索模式支持不足，無法滿足當(dāng)前日益復(fù)雜的業(yè)務(wù)需求的問題，從檢索時(shí)的優(yōu)先級(jí)編碼機(jī)制入手，提出了一種以太網(wǎng)通信芯片的優(yōu)先級(jí)編碼方法。通過對(duì)比較單元陣列進(jìn)行分組，利用不同層次的PE來生成最高優(yōu)先級(jí)的命中地址，其中下層編碼器的作用是生成底層模塊列地址，并按照不同的位寬配置計(jì)算相應(yīng)字的匹配結(jié)果，頂級(jí)PE則生成行地址和最終的列地址。該方法能使以太網(wǎng)通信芯片支持多種位寬數(shù)據(jù)的搜索，同時(shí)減少對(duì)線道的需求。

參考文獻(xiàn)

[1]劉挺.計(jì)算機(jī)硬件材料的現(xiàn)狀及發(fā)展趨勢(shì)[J].造紙裝備及材料， 2021， 50（8）：62-63.

[2]許培紅.基于模糊聚類分析的單詞翻譯緩存分區(qū)管理系統(tǒng)設(shè)計(jì)[J].齊齊哈爾大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2021，37（5）： 26-30.

[3]王明玉.工業(yè)異構(gòu)網(wǎng)絡(luò)地址統(tǒng)一分配管理機(jī)制研究與實(shí)現(xiàn)[D].北京：北京交通大學(xué)， 2021.

[4] RAJAEI R， SHARIFI M M， KAZEMI A， et al. Compact Single-phase-search Multistate Content-addressable Memory Design Using One FeFET/Cell[J]. IEEE Transactions on Electron Devices， 2020， 68（1）： 109-117.

[5] WANG P， ZHANG J X， ZHANG X， et al. Convergence of Satellite and Terrestrial Networks： A Comprehensive Survey[J]. IEEE Access， 2019， 8： 5550-5588.

[6]丁憲忠.基于非易失存儲(chǔ)器的混合TCAM研究與設(shè)計(jì)[D].濟(jì)南：山東大學(xué)， 2018.

[7] T·H·金斯利， G·E·帕克斯， Y·夏爾馬，等.具有不同物理尺寸，存儲(chǔ)器格式和操作能力的存儲(chǔ)器裝置，模塊和具有存儲(chǔ)器裝置的系統(tǒng)： CN111630504A[P]. 2020-09-04.

[8]康耀鵬，汪鵬君，張會(huì)紅，等.基于CNFET的三值內(nèi)容尋址存儲(chǔ)器單元設(shè)計(jì)[J].華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版， 2018， 44（5）：724-729.

[9]廖澴桓，張躍軍，丁代魯，等.一種密碼芯片上的固定位寬密鑰產(chǎn)生方法： CN201710200373.7[P]. 2017-09-01.

[10] TAN A J ， CHATTERJEE K ， ZHOU J R， et al. Experimental Demonstration of a Ferroelectric HfO2-based Content Addressable Memory Cell[J]. IEEE Electron Device Letters， 2020， 41（2）： 240-243.

[11]蘇童，唐永鶴，蔣烈輝.基于CAM的數(shù)據(jù)庫(kù)查詢硬件加速方法[J].信息工程大學(xué)學(xué)報(bào)， 2019， 20（2）： 217-221.

[12]謝升旭，邢長(zhǎng)友，張國(guó)敏，等. OpenFlow交換機(jī)流表溢出緩解技術(shù)研究綜述[J].計(jì)算機(jī)研究與發(fā)展， 2021， 58（7）： 1544-1562.

[13] OMER M， ZAHID U， HASSAN M， et al. Fast Pattern Recognition through an LBP Driven CAM on FPGA[J]. IEEE Access， 2018，6： 39525-39531.

[14]崔興龍，方沛昱.一種路由查找方法，裝置和存儲(chǔ)介質(zhì)： CN107896194A[P]. 2018-04-10.