一種以太網通信芯片的優先級編碼方法

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

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

關鍵詞：以太網通信芯片；內容可尋址存儲器；多種搜索位寬；優先級編碼

中圖分類號：TP333文獻標志碼：A文章編號：1008-1739（2022）24-60-4

0引言

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

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

1相關理論

1.1 CAM

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

一次典型的CAM查找操作過程為：首先，CAM接收外部的查找命令并把查找數據存儲到比較寄存器中，比較寄存器和掩碼寄存器的內容共同組成系統的一個查找字（search word），這些查找字廣播到每一組相關聯字中，每一組相關聯字都有一個匹配鏈（matchline），匹配鏈指示查找字與存儲字是否一致（匹配或不匹配），匹配鏈把結果反饋到優先譯碼器中，優先譯碼器產生一個二進制的匹配位置定位和一個匹配命中信號[3]。由于在CAM中可能存在多個字同時匹配，因而使用了一個優先譯碼器而不是簡單的譯碼器。當有多個字同時匹配時，優先譯碼器選擇最高優先權的匹配地址映射到匹配結果，在CAM中低地址字具有高優先權[4]。

1.2優先級編碼

編碼器是一種將信息由一種特定格式（或編碼）轉換為其他特定格式（或編碼）的傳感器、軟件或算法，轉換的目的可能是為了標準化、速度、保密性、保安或是為了壓縮數據。而優先編碼器允許同時在幾個輸入端有輸入信號，編碼器按輸入信號排定的優先順序，只對同時輸入的幾個信號中優先權最高的一個進行編碼[5]。優先編碼器常用于在處理最高優先級請求時控制中斷請求。如果同時有2個或以上的輸入作用于優先編碼器，優先級最高的輸入將會被優先輸出[6]。

2設計思路

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

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

3優先級編碼方法

3.1傳統優先級編碼方式

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

3.2支持多種查找模式的優先級編碼方法

因此，本文提出了一種以太網通信芯片的優先級編碼方法，對以太網通信芯片CAM進行如下操作：

①將CAM陣列分組，每組有一個底層優先級編碼器，該優先級編碼器放置于該分組物理實現的中間位置；

②底層優先級編碼器對CAM陣列分組中每個字的比較結果進行處理，按照不同的配置計算出是否匹配，并將該新的匹配結果輸出給上一層的優先級編碼器A，底層優先級編碼器同時生成組內CAM模塊的塊地址；

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

④優先級編碼器B對優先級編碼器A的匹配結果進行處理，按照不同的配置進行計算，計算出是否匹配，并將該匹配結果輸出給優先級編碼器B的上一層優先級編碼器C，優先級編碼器B同時需要對優先級編碼器A產生的低位塊地址進行選擇，與該編碼器生成的高位塊地址合在一起，生成新的塊地址；

⑤以此類推，直至頂層；

⑥頂層優先級編碼器對下一層優先級編碼器的匹配結果進行處理，按照不同的配置計算出是否匹配，并對該匹配結果進行優先級編碼，產生行地址；頂級優先級編碼器同時需對下一層編碼器產生的低位塊地址進行選擇，與該編碼器生成的高位塊地址合在一起，生成最終的塊地址。

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

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

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

3.3線道數目比較

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

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

4結束語

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

參考文獻

[1]劉挺.計算機硬件材料的現狀及發展趨勢[J].造紙裝備及材料， 2021， 50（8）：62-63.

[2]許培紅.基于模糊聚類分析的單詞翻譯緩存分區管理系統設計[J].齊齊哈爾大學學報（自然科學版）， 2021，37（5）： 26-30.

[3]王明玉.工業異構網絡地址統一分配管理機制研究與實現[D].北京：北京交通大學， 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]丁憲忠.基于非易失存儲器的混合TCAM研究與設計[D].濟南：山東大學， 2018.

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

[8]康耀鵬，汪鵬君，張會紅，等.基于CNFET的三值內容尋址存儲器單元設計[J].華東理工大學學報：自然科學版， 2018， 44（5）：724-729.

[9]廖澴桓，張躍軍，丁代魯，等.一種密碼芯片上的固定位寬密鑰產生方法： 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的數據庫查詢硬件加速方法[J].信息工程大學學報， 2019， 20（2）： 217-221.

[12]謝升旭，邢長友，張國敏，等. OpenFlow交換機流表溢出緩解技術研究綜述[J].計算機研究與發展， 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]崔興龍，方沛昱.一種路由查找方法，裝置和存儲介質： CN107896194A[P]. 2018-04-10.