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

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

Hash算法在網(wǎng)絡(luò)處理器中的實現(xiàn)

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

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

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

網(wǎng)絡(luò)處理器;Hash表;查找效率;學(xué)習(xí);老化

1 概述

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

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

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

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

為解決可能存在的Hash沖突,本文構(gòu)造了2個Hash函數(shù),第1個函數(shù)把Key轉(zhuǎn)換成一個存儲地址,第2個函數(shù)把Key轉(zhuǎn)換成一個標(biāo)簽。然后把所有這些沖突的Key的實際地址即索引值都存放在索引表的同一位置,但分別位于不同的行,通過標(biāo)簽加以區(qū)分。此外,在索引表中每個位置上存放的索引值個數(shù)可根據(jù)實際需求進(jìn)行設(shè)定,從而節(jié)省網(wǎng)絡(luò)處理器的存儲資源。

2 算法的提出

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

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

3 算法設(shè)計實現(xiàn)

網(wǎng)絡(luò)處理器的系統(tǒng)硬件結(jié)構(gòu)如圖1所示。網(wǎng)絡(luò)處理器包括Parse,Search,Resolve和Modify這4種類型的數(shù)據(jù)包處理模塊,以及一些連接存儲器和網(wǎng)絡(luò)收發(fā)等接口,每個模塊內(nèi)部的多個處理器并行運行,模塊之間采取功能流水的方式進(jìn)行數(shù)據(jù)包處理。

圖1 網(wǎng)絡(luò)處理器系統(tǒng)硬件結(jié)構(gòu)

Hash算法用于網(wǎng)絡(luò)處理器的查找模塊Search中,在該模塊中執(zhí)行Hash查找,并在此基礎(chǔ)上,實現(xiàn)學(xué)習(xí)和老化等功能。Hash算法的硬件實現(xiàn)結(jié)構(gòu)如圖2所示。

圖2 算法的硬件框圖

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

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

(2)查找邏輯的功能是控制查表過程,依據(jù)查找流程實現(xiàn)狀態(tài)機(jī)保證查找的順利執(zhí)行。

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

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

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

(6)在查找的基礎(chǔ)上,學(xué)習(xí)機(jī)制執(zhí)行表項的更新和添加等操作。

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

3.1 Hash表的結(jié)構(gòu)

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

圖3 Hash表的結(jié)構(gòu)

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

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

在結(jié)果表中,每個條目中存放關(guān)鍵字Key和相應(yīng)的結(jié)果Result。

3.2 Hash函數(shù)實現(xiàn)

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

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

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

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

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

3)對所有下標(biāo)為偶數(shù)的組G2i按位進(jìn)行異或運算,得到13位的數(shù)據(jù)MSB[12:0]。

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

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

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

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

3)對所有下標(biāo)為偶數(shù)的組G2i按位進(jìn)行異或運算,得到12位的數(shù)據(jù)M[11:0]。

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

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

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

3.3 軟件建立流程

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

圖4 Hash表建立流程

Hash表建立過程如下:

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

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

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

(4)判斷該頁中標(biāo)簽數(shù)目,如果該頁已滿,轉(zhuǎn)步驟(5),否則轉(zhuǎn)步驟(9)。

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

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

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

(8)創(chuàng)建下一頁,把標(biāo)簽Label和索引值Index等信息存放在該頁的第1行,轉(zhuǎn)步驟(11)。

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

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

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

3.4 硬件查找設(shè)計

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

圖5 Hash表查找流程

Hash表查找的過程如下:

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

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

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

(4)如果該頁中至少有一個標(biāo)簽Label匹配并且相應(yīng)的有效位Valid有效,轉(zhuǎn)步驟(5),否則轉(zhuǎn)步驟(9)。

(5)根據(jù)位于標(biāo)簽同一行的索引值Index讀出結(jié)果表中的條目Entry,轉(zhuǎn)步驟(6)。

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

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

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

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

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

3.5 硬件表項的學(xué)習(xí)及老化

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

表項的學(xué)習(xí)是基于Hash查找實現(xiàn)的,具體流程如圖6所示。

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

Hash表的老化模塊負(fù)責(zé)周期性地執(zhí)行表項的老化操作,即刪除表項操作。實現(xiàn)老化功能時為每個表項增加1位刷新位,在查找和學(xué)習(xí)表項時,對該位置1。在老化過程中如果發(fā)現(xiàn)該刷新位為1,則清除該位,本老化周期內(nèi)不刪除該表項,否則該表項將被老化,這就保證了一個表項至少能夠維持一個周期。結(jié)合本文給出的Hash表的結(jié)構(gòu),老化一個表項只需在索引表中把該表項對應(yīng)的有效位Valid清除即可。

圖6 Hash表項學(xué)習(xí)流程

4 算法實現(xiàn)和舉例

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

圖7 Hash表示意圖

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

圖8 RTL仿真波形圖1

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

圖9 RTL仿真波形圖2

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

圖10 學(xué)習(xí)后的Hash表

5 性能分析

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

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

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

表1 本文算法支持的表結(jié)構(gòu)

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

圖11 FPGA硬件原型驗證平臺

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

6 結(jié)束語

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

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

[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].計算機(jī)工程,2008,34(6):112-113.

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

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

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

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

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

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

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

編輯 顧逸斐

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

參考文獻(xiàn)

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

[2] 中國科學(xué)技術(shù)大學(xué)藍(lán)鷹仿真2D球隊.仿真機(jī)器人足球:設(shè)計與實現(xiàn)[EB/OL].(2013-07-04).http:// wenku.baidu.com/view/ae0c20ee6294dd88d0d26be0. html.

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

[4] 周 勇,劉 鋒.基于改進(jìn)的Q學(xué)習(xí)的RoboCup傳球策略研究[J].計算機(jī)技術(shù)與發(fā)展,2008,18(4):63-67.

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

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

[7] 李繼耀,陳 瑋,張 祺.智能算法在機(jī)器人足球控制仿真中的應(yīng)用[J].控制理論與應(yīng)用,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] 周 強(qiáng),歐陽一鳴,胡學(xué)鋼,等.數(shù)據(jù)挖掘中應(yīng)用偏最小二乘法發(fā)現(xiàn)異常值[J].微電子與計算機(jī),2005,22 (1):25-31.

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

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

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

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

[14] 何曉群.應(yīng)用統(tǒng)計分析[M].北京:中國人民大學(xué)出版社,2012.

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

[16] 王惠文.偏最小二乘回歸的線性與非線性方法[M].北京:國防工業(yè)出版社,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-),男,工程師、碩士,主研方向:網(wǎng)絡(luò)處理器設(shè)計;張 輝,助理工程師;李 苗,高級工程師;劉 濤,工程師、碩士。

2014-01-23

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