Hash算法在網絡處理器中的實現

付仲滿,張 輝,李 苗,劉 濤

(中國電子科技集團公司第三十二研究所,上海200233)

Hash算法在網絡處理器中的實現

付仲滿,張 輝,李 苗,劉 濤

(中國電子科技集團公司第三十二研究所,上海200233)

提出一種應用于網絡處理器的Hash算法,通過建立新型查找表的結構和構造兩級Hash函數,能夠有效地解決Hash沖突的問題。描述Hash表的軟件建立流程和硬件查找過程,在Hash查找的基礎上,給出硬件表項的學習過程和老化方法,簡化表項的更新操作。針對不同的應用,建立不同類型的Hash表,合理地利用內外部存儲資源,兼顧了存儲資源和處理速度的平衡。實驗結果表明,該算法對各種查找表中不同的表項數目和關鍵詞長度均具有較好的兼容性,成功查找的平均長度為2,減少了存儲器的訪存次數,其單個微引擎的查找速度高達25 Mb/s,能夠滿足網絡處理器接口處理帶寬20 Gb/s的要求。

網絡處理器;Hash表;查找效率;學習;老化

1 概述

隨著因特網速度的日益提高、網絡流量的持續增加和查找表項數目的不斷增大,查找效率逐漸成為網絡處理設備性能的瓶頸[1]。影響查表效率的因素主要有2個方面:(1)表的結構即建表的方法; (2)查表的方法[2],即以盡可能少的存儲資源,獲得較快的查表速度。

在傳統的數據結構中,如線性表、Trie等[3-4],記錄在結構中的相對位置是隨機的,和記錄的關鍵字Key之間不存在確定的關系,查找過程中需要大量的存儲器訪問操作。上述算法是建立在比較基礎上的查找算法[5],在數據增長的過程中,查找的速度會因為查找所進行比較次數的增多而下降,而且也將占有更多的存儲資源。

理想的情形是不經過任何比較,一次訪存存儲器就能得到所查的結果[6]。這就要求在Key和其存儲位置之間建立一個確定的對應關系,在查找時,只要根據這個對應關系即可找到給定Key的映射f (Key),直接獲得結果,這種對應關系稱為Hash函數,以這種對應方式建立的表稱為Hash表[7]。

然而,Hash函數是一個壓縮映射函數,在Hash表中不同的Key可能得到同一Hash地址,即不可避免地會產生沖突,因此,需要一種在發生Hash沖突時,解決沖突的方法[8]。處理Hash沖突的方法有很多,常用的有開放定址法、再哈希法、鏈地址法以及建立公共溢出區等[9]。但是采用這些沖突解決的方法,其查找成功所對應存儲器的平均訪存次數,即平均查找長度是裝填因子α的函數,將隨著查找表中記錄數的增多而增加,從而導致了查找次數的不確定性[10]。

為解決可能存在的Hash沖突,本文構造了2個Hash函數,第1個函數把Key轉換成一個存儲地址,第2個函數把Key轉換成一個標簽。然后把所有這些沖突的Key的實際地址即索引值都存放在索引表的同一位置,但分別位于不同的行,通過標簽加以區分。此外,在索引表中每個位置上存放的索引值個數可根據實際需求進行設定,從而節省網絡處理器的存儲資源。

2 算法的提出

通常,網絡處理器在運行時需要對各種表進行頻繁的查表操作,這些表的容量大小和訪問頻率各不相同。如果把這些表都建立在內部存儲器SRAM中,由于SRAM的容量較小,將占用寶貴的內部存儲資源,甚至發生溢出;如果都建立在外部存儲器DRAM中,由于DRAM的存取速度不高,每次訪存所需的時間較長,而且由于不可避免的Hash沖突問題,一次查表請求需要對存儲器進行多次訪問,從而導致了數據吞吐率的下降。

針對網絡處理器的不同應用,如二三層交換的MAC+VLAN表,IP路由的 IPv4表、IPv6表和MPLS表,所要求的查找速度和對存儲資源的占用是不同的,因此,本文建立了一種兩級查找表,把存儲索引值的索引表和存放實際待查表項的結果表分開存放。根據表項的大小以及查找速度的要求,把索引表和結果表容量都較小的表存放在訪存速度高但存儲容量小的內部存儲器中;為節省網絡處理器內部寶貴的存儲資源,把索引表和結果表容量都較大的表存放在訪存速度不高但存儲容量大的外部存儲器中;為兼顧查找速度和存儲資源的平衡,把索引表容量較小而結果表容量較大的表分別存放于內、外部存儲器中,即分別建立內部 intHash表、外部extHash表和內外部混合mixHash表。

3 算法設計實現

網絡處理器的系統硬件結構如圖1所示。網絡處理器包括Parse,Search,Resolve和Modify這4種類型的數據包處理模塊,以及一些連接存儲器和網絡收發等接口,每個模塊內部的多個處理器并行運行,模塊之間采取功能流水的方式進行數據包處理。

圖1 網絡處理器系統硬件結構

Hash算法用于網絡處理器的查找模塊Search中,在該模塊中執行Hash查找,并在此基礎上,實現學習和老化等功能。Hash算法的硬件實現結構如圖2所示。

圖2 算法的硬件框圖

該算法通過Hash運算單元、查找邏輯、空閑指針隊列和內外部存儲器等模塊實現,其中:

(1)Hash運算單元把關鍵字Key轉換成偏移量和標簽,其中,偏移量和Hash表的基地址共同確定了標簽等信息在索引表中的存儲位置,產生沖突的Key通過標簽加以區分。

(2)查找邏輯的功能是控制查表過程,依據查找流程實現狀態機保證查找的順利執行。

(3)空閑指針隊列與每個Hash表一一對應。在建表和學習時提供空閑指針,作為Key的實際存放地址,即索引值,該指針是順序產生的;此外,該隊列還用于在執行老化機制時,回收被老化表項的地址,此后該地址將繼續作為學習時的空閑指針。

(4)內部存儲器用來存放一些較小的Hash表的索引表和結果表等信息。

(5)外部存儲器用來存放一些較大的Hash表的索引表和結果表等信息。

(6)在查找的基礎上,學習機制執行表項的更新和添加等操作。

(7)老化機制周期性地輪詢各個表項,刪除長時間不用的表項。

3.1 Hash表的結構

本文建立的Hash表如圖3所示,每個Hash表由2個子表構成。其中,第1個子表為索引表,第2個子表為結果表。

圖3 Hash表的結構

在索引表中,一個存儲位置對應一頁(Page),每頁包括n行的3列信息:有效位Valid、標簽Label和索引值Index。有效位Valid表明該表項是否有效,在添加該表項時該位置1,而在老化時不需要進行表項遷移等額外的操作,僅需要把該位清零即可,從而減少了存儲器的訪存次數;索引值Index為關鍵字Key在結果表中的實際存放位置;標簽Label用來區分各個Page中每個索引值Index為哪個Key的存放地址。

此外每頁還包括:下一頁有效位Link_page_valid和下一頁地址Link_page_addr。當多于n個Key產生Hash沖突時,表明該頁已滿,此時下一頁有效位Link_ page_valid置1,標簽Label和索引值Index存放于下一頁地址Link_page_addr所指向的位置。

在結果表中,每個條目中存放關鍵字Key和相應的結果Result。

3.2 Hash函數實現

Hash函數指出了關鍵字與其存儲位置之間的對應關系,其選取原則是構造簡單、發生沖突的概率小。常用的構造Hash函數的方法有直接定址法、數值分析法、除留余數法、平方取中法、折疊法和隨機數法等[11],這些方法受限于關鍵字Key的范圍和形態。

對于網絡處理器,不同應用中Key的長度和組成方式,以及Hash表的容量大小和類型均有所不同[12],為使Hash地址能夠均勻地映射到所指定的存儲空間中,盡可能地減少沖突的發生,本文采用以下方式構造Hash函數。

(1)Hash函數H1(Key)的計算:

1)把關鍵字Key按位從最低位起,每13位組成一組,最高的一組如果不足13位高位補0,其中,G0=Key[12:0];G1=Key[25:13];G2=Key[38: 26];G3=Key[51:39],依此類推。

2)對所有的組Gi按位進行異或運算,得到13位的數據LSB[12:0]。

3)對所有下標為偶數的組G2i按位進行異或運算,得到13位的數據MSB[12:0]。

4)H1(Key)={MSB,LSB}。

(2)Hash函數H2(Key)的計算:

1)把關鍵字Key按位從最低位起,每12位組成一組,最高的一組如果不足12位高位補0,其中,G0=Key[11:0];G1=Key[23:12];G2=Key[35:24];G3=Key[47:36],依此類推。

2)對所有的組Gi按位進行異或運算,得到12位的數據L[11:0]。

3)對所有下標為偶數的組G2i按位進行異或運算,得到12位的數據M[11:0]。

4)對于12位的數據L[11:0],從最低位起,每3位作一組,對所有的組按位進行異或運算,得到3位的數據LSB[2:0]。

5)以同樣的方式,對于12位的數據M[11:0],從最低位起,每3位作一組,對所有的組按位進行異或運算,得到3位的數據MSB[2:0]。

6)H2(Key)={MSB,LSB}。

3.3 軟件建立流程

Hash表建立的流程如圖4所示。

圖4 Hash表建立流程

Hash表建立過程如下:

(1)提取用于建表的關鍵字Key以及Hash表的類型Hash_type和該表的基地址Base_address等信息,根據Hash表的類型信息,確定待建立的表屬于內部Hash表、外部Hash表還是內外部混合Hash表。

(2)計算函數H1(Key),把關鍵字Key轉換成一個地址偏移量Offset,該偏移量和基地址共同確定了該Key的索引值在索引表中的存放地址;同時計算函數H2(Key),把關鍵字Key轉換成一個標簽Label。

(3)讀出索引表的信息。

(4)判斷該頁中標簽數目,如果該頁已滿,轉步驟(5),否則轉步驟(9)。

(5)下一頁有效位Link_page_valid為1,轉步驟(6),否則轉步驟(7)。

(6)讀出下一頁的信息,轉步驟(4)。

(7)請求2個空閑指針,第1個指針作為下一頁地址Link_page_addr,第2個指針作為索引值Index,轉步驟(8)。

(8)創建下一頁,把標簽Label和索引值Index等信息存放在該頁的第1行,轉步驟(11)。

(9)請求一個空閑指針作為索引值Index,轉步驟(10)。

(10)找出第1個標簽為空的行,把標簽Label和索引值Index等信息存放于該行,轉步驟(11)。

(11)把關鍵字Key和結果Result寫入結果表中索引值所指向的位置,結束。

3.4 硬件查找設計

Hash表查找的流程如圖5所示。

圖5 Hash表查找流程

Hash表查找的過程如下:

(1)從接收的報文中提取用于建表的關鍵字Key以及Hash表的類型Hash_type和該表的基地址Base_address等信息,根據Hash表的類型信息,確定待建立的表屬于內部Hash表、外部Hash表還是內外部混合Hash表。

(2)計算函數H1(Key),把關鍵字Key轉換成一個地址偏移量Offset,該偏移量和基地址共同確定了該Key的索引值在索引表中的存放地址;同時計算函數H2(Key),把關鍵字Key轉換成一個標簽Label。

(3)讀出位于索引表的該存放位置中的信息。

(4)如果該頁中至少有一個標簽Label匹配并且相應的有效位Valid有效,轉步驟(5),否則轉步驟(9)。

(5)根據位于標簽同一行的索引值Index讀出結果表中的條目Entry,轉步驟(6)。

(6)如果該條目Entry中的Key和查找的Key相匹配,轉步驟(7),否則轉步驟(8)。

(7)查找成功,返回條目中的結果Result,查找結束。

(8)如果該頁中尚有其他標簽Label匹配并且相應的有效位 Valid有效的未匹配項,轉向步驟(5),否則轉步驟(9)。

(9)該頁中下一頁有效位Link_page_valid為1,根據下一頁地址Link_page_addr讀出下一頁信息,轉步驟(3),否則轉步驟(10)。

(10)查找失敗,返回失敗的結果,查找結束。

3.5 硬件表項的學習及老化

瀏陽市委常委、市紀委書記、市監委主任秦躍平在致辭中說，胡耀邦家風與廉政思想對于瀏陽的黨風廉政影響深遠，瀏陽的歷史性變化與其密不可分，瀏陽未來前行更需要將其傳承發揚光大。

表項的學習是基于Hash查找實現的,具體流程如圖6所示。

對于一個待學習的Key,首先執行Hash查找,如果查找成功,表明該表項已存在,此時更新條目Entry中的結果Result;反之,如果查找失敗,表明該表項不存在,此時需添加這個表項。

Hash表的老化模塊負責周期性地執行表項的老化操作,即刪除表項操作。實現老化功能時為每個表項增加1位刷新位,在查找和學習表項時,對該位置1。在老化過程中如果發現該刷新位為1,則清除該位,本老化周期內不刪除該表項,否則該表項將被老化,這就保證了一個表項至少能夠維持一個周期。結合本文給出的Hash表的結構,老化一個表項只需在索引表中把該表項對應的有效位Valid清除即可。

圖6 Hash表項學習流程

4 算法實現和舉例

本文采用Verilog HDL對Hash查找進行功能描述,在Mentor公司的Questasim 10.1b上進行功能仿真驗證。其中,地址0x0127的頁中存放了4個Key的信息,如圖7所示。

圖7 Hash表示意圖

(1)對于一個查找的Key:0x00011B81,位于地址0x0127的Page,標簽為0x11。從圖8所示的仿真波形圖可以看出,查找時,首先根據Page_addr(0x0127)讀出該Page的內容,發現與第1行相匹配,然后根據該行的索引值0x2000讀出Entry(0x00011b81_00000001),進行二次匹配,Key一致,返回其結果 0h00000001,查找成功。

圖8 RTL仿真波形圖1

(2)對于一個查找的Key:0x0003E896,位于地址0x0127的Page,標簽為0x13。從圖9所示的仿真波形圖可以看出,查找時,首先根據 Page_addr (0x0127)讀出該Page的內容,發現與第2行、第3行均匹配,此時首先根據第2行的索引值讀出地址0x2001讀出Entry(0x0002509b_00000002),進行二次匹配,Key不相同,接著根據第3行的索引值讀出地址0x2002讀出Entry(0x0003e896_00000003),進行二次匹配,Key一致,讀出返回其結果0x00000003,查找成功。

圖9 RTL仿真波形圖2

(3)對于一個學習的Key:0x00062EB8,其偏移量為0x0089,標簽為0x15。首先執行Hash查找,根據偏移量讀出該頁的內容,可以發現與第4行相匹配,此時根據第4行的索引值讀出地址0x2003的內容,進行二次匹配,Key不相同,匹配失敗。然后添加該表項:該頁的第5行為空,此時請求一個指針0x2004作為索引,把 Key(0x00062EB8)和 Result (0x00000005)寫入結果表中,接著更新索引表。學習后的Hash表如圖10所示。

圖10 學習后的Hash表

5 性能分析

影響Hash查找效率的主要因素是選用的Hash函數和沖突解決的方法,通過實驗分析,本文提出的Hash函數具有良好的均勻性,可以有效地減少Hash沖突。此外,對于常用的解決Hash沖突的方法,由于其平均查找長度是裝填因子α的函數,導致了查找次數的不確定性。而本文構造的兩級Hash函數,當第1個Hash函數發生沖突,通過第2個Hash函數很容易區分這些沖突的Key,因此,通過兩級查找,其命中率將高達98%,只有大約2%的情形下才需要更多次的查找,本文算法的查找次數是確定的,即只需要2次存儲器的訪問。

本文算法同時還具有良好的可擴展性。傳統的查找算法往往受限于硬件查找表中表項的數目和關鍵字的長度,而本文算法通過在建表時預分配Hash表的2個子表的存儲空間,同時為保證98%的命中率,每個結果表的深度是其相應索引表的4倍,考慮到Hash函數良好的均勻性,可以認為平均每個Page下存有4個Key的信息。增加表項的數目,即增加結果表的深度,為保證其命中率,需要相應地增加索引表的深度。

本文算法所支持的表的類型和大小等信息如表1所示。

表1 本文算法支持的表結構

圖11是FPGA硬件驗證平臺,現已在該平臺下完成了算法的原型驗證。目前該網絡處理器正在采用55 nm工藝進行后端設計,工作頻率為500 MHz,內嵌一個容量為256 KB的內部存儲器SRAM,通過DDR3接口外接的800 MHz的DRAM存儲器,容量為2 GB。

圖11 FPGA硬件原型驗證平臺

對于帶寬20 Gb/s的網絡處理器,以每個數據包長度80 Byte、幀間隔12 Byte來計算,實現線速轉發至少需要達到20 Gb·s-1/((80+12)×8)bit= 27.17 M/s。一次查找時間包括查找狀態機、存儲器仲裁和訪存的時間,對于內部 intHash表、混合mixHash表和外部extHash表,本文設計所需的時間分別為40 ns,125 ns和210 ns,對應的查找速度為25 Mb/s、8 Mb/s和4.8 Mb/s。該網絡處理器中調用了8個硬件查找模塊,8個模塊并行工作,對于3種類型的Hash表都能夠滿足線速處理要求。

6 結束語

本文以查找速率和存儲空間這2個性能為目標,通過優化網絡處理器中Hash查找表的結構和網絡處理的操作過程,以及對不同的工程應用分別建立不同類型的Hash表,各表獨立進行查找、學習和老化操作等方式,具有查找效率高、更新速度快、操作簡單、便于硬件實現等優點,以此提高了網絡處理器的處理速度和存儲器的資源利用率。目前,該Hash算法已成功應用于20 Gb/s處理帶寬的網絡處理器中,由于其較好的擴展性,能夠支持MAC交換表、IPv4和IPv6路由表。

book=274,ebook=280勝負關鍵的結論,并結合相關圖表對模型的合理性進行了分析。下一步工作是將此結論作為高層決策的依據,在sample_field_evaluator.cpp文件中(本文研究以Agent2D底層代碼為例),對傳球動作評估部分的代碼作適當調整,有意識地在函數中加大ThroughPass執行的weight值,以期望YuShan隊在今后其他賽事中取得理想的成績。在做此研究之前,通過對仿真比賽的觀察,目測結果是4類傳球對比賽勝負的貢獻最大,而理論結果卻是5類傳球,造成結論的誤差可能是源于以下因素:(1)采樣的觀測數據量還不夠大,對結果會有一定影響;(2)傳球類型的距離區間是根據經驗來劃分的,如果能把數據離散化工作處理得更好,則能得到更加精確的結論。雖然存在一些不足,但本文重點是對Robocup2D的研究提供了一種新的思路,即數據挖掘。

[1] Li Yefeng,Le Jiajin,Wang Mei.A Column-store Based Bucket Partition Algorithm for Range Queries[J]. Journal of Computer Research and Development,2013, 50(3):54-55.

[2] Comer D E.Network Systems Design Using Network Processors[M].[S.l.]:Prentice Hall,2009:311-312.

[3] Chang Y K,Lin Y C.A Fast and Memory Efficient Dynamic IP Lookups Algorithm Based on B-tree[C]// Proc. of International Conference on Advanced Information Networking and Applications.[S.l.]:IEEE Press,2009:278-284.

[4] Chang Y K.Fast Binary and Multiway Prefix Searches for Packet Forwarding[J].Computer Networks,2007,51 (3):588-605.

[5] 鹿 旸,陳 明.基于樹的平衡路由 P2P查找算法[J].計算機工程,2008,34(6):112-113.

[6] 王子牛,曹凌菲,王 巖.基于雙數組Trie樹法的關鍵字預處理技術及其在CNC語法檢驗中的應用[J].貴州大學學報:自然科學版,2010,27(1):223-224.

[7] 李舉成,易靈芝,王根平.基于Hash函數的RFID系統防碰撞算法的研究[J].計算機測量與控制,2009,17 (10):192-193.

[8] 黃 建,徐 晶.高效雙Hash線速浮動字符串匹配[J].微電子學與計算機,2008,25(2):89-92.

[9] 廖名學,范植華.基于素數序列的Java哈希表性能優化[J].計算機工程與應用,2008,44(3):65-66.

[10] 王亞剛,杜慧敏,楊康平.使用Hash表和樹位圖的兩級IPv6地址查找算法[J].計算機科學,2010,37(9): 36-38.

[11] 崔國敏.基于安全散列算法的FPGA加密方法[J].價值工程,2010,29(7):145-149.

[12] 張朝霞,劉耀軍.有效的哈希沖突解決辦法[J].計算機應用,2010,30(11):288-290.

編輯 顧逸斐

偏最小二乘法采用數據信息量分解的思路,根據整體數據的變異程度將信息重組,可以有效剔除重疊無意義的變量,用這種方法來對數據進行降維,在當今海量數據處理困難的形勢下有較大的應用價值。

參考文獻

[1] Stone P.Layered Learning in Multi-agent Systems[D]. Pittsburgh,USA:Carnegie Mellon University,1998.

[2] 中國科學技術大學藍鷹仿真2D球隊.仿真機器人足球:設計與實現[EB/OL].(2013-07-04).http:// wenku.baidu.com/view/ae0c20ee6294dd88d0d26be0. html.

[3] 郭 博,程家興.RoboCup仿真組的傳球策略[J].計算機技術與發展,2006,16(2):129-131.

[4] 周 勇,劉 鋒.基于改進的Q學習的RoboCup傳球策略研究[J].計算機技術與發展,2008,18(4):63-67.

[5] 張家旺,韓光勝,張 偉.C5.0算法在RoboCup傳球訓練中的應用研究[J].計算機仿真,2006,23(4): 132-135.

[6] 章小兵,劉艷春,陳 黎.基于傳球評價函數的RoboCup傳球策略[J].安徽工業大學學報,2011,28(2): 171-174.

[7] 李繼耀,陳 瑋,張 祺.智能算法在機器人足球控制仿真中的應用[J].控制理論與應用,2007,26(9): 7-9.

[8] Wold S,Martens H,Wold H.The Multivariate Calibration Problem in Chemistry Solved by the PLS Method[C]//Proc.of Conference on Matrix Pensils. Berlin,Germany:Springer-Verlag,1983:286-293.

[9] 周 強,歐陽一鳴,胡學鋼,等.數據挖掘中應用偏最小二乘法發現異常值[J].微電子與計算機,2005,22 (1):25-31.

[10] 羅 為,劉 魯.基于偏最小二乘法的軍用無人機研制費用預測[J].北京航空航天大學學報,2010,36 (6):667-670.

[11] 戚浩平,張 利,王 煒,等.基于偏最小二乘回歸法的城市土地利用與交通發生量關系模型研究[J].公路交通科技,2011,28(3):138-143.

[12] 楊 杰,吳中如.觀測數據擬合分析中的多重共線性問題[J].四川大學學報,2005,37(5):19-24.

[13] 劉桂雄,林緒虹.魚類超微弱發光的偏最小二乘回歸分析與建模[J].華南理工大學學報,2006,34(11): 29-32.

[14] 何曉群.應用統計分析[M].北京:中國人民大學出版社,2012.

[15] 王惠文.偏最小二乘回歸方法及其應用[M].北京:國防工業出版社,1999.

[16] 王惠文.偏最小二乘回歸的線性與非線性方法[M].北京:國防工業出版社,2006.

編輯 顧逸斐

Implementation of Hash Algorithm in Network Processor

FU Zhong-man,ZHANG Hui,LI Miao,LIU Tao
(The 32nd Research Institute of China Electronics Technology Group Corporation,Shanghai 200233,China)

A novel Hash algorithm is proposed in this paper for network processor application.It resolves Hash collision problem by constructing new look up table and new two-level Hash function.The software processing and hardware lookup flow of Hash table are descripted,and the learning process and ageing machine for entry of table are designed for simplifying the entry updating operation.For different engineering applications,the algorithm sets up different Hash table, which makes the efficience of memory utilization improved and the tradeoff between memory and processing speed optimized.Simulation results show the algorithm works well despite of the number of table entry and the size of keyword. The average length of look up's success is 2 and the memory access times is reduced dramaticlly.The look up speed of micro-engine is improved to 25 Mb/s,satisfing the requinrement of 20 Gb/s bandwidth performance of network processor.

network processor;Hash table;lookup efficiency;learning;ageing

1000-3428(2014)09-0269-06

A

TP393

10.3969/j.issn.1000-3428.2014.09.054

付仲滿(1978-),男,工程師、碩士,主研方向:網絡處理器設計;張 輝,助理工程師;李 苗,高級工程師;劉 濤,工程師、碩士。

2014-01-23

2014-04-02E-mail:zhaghie@163.com