hash算法在FPGA中的實(shí)現(xiàn)(1)

在FPGA的設(shè)計(jì)中，尤其是在通信領(lǐng)域，經(jīng)常會(huì)遇到hash算法的實(shí)現(xiàn)。hash算法在FPGA的設(shè)計(jì)中，它主要包括2個(gè)部分，第一個(gè)就是如何選擇一個(gè)好的hash函數(shù)，減少碰撞；第二個(gè)就是如何管理hash表。本文不討論hash算法本身，僅說(shuō)明hash表的管理。

原理

先對(duì)齊本文中要說(shuō)明的幾個(gè)概況，如下圖所示，hash函數(shù)的輸入稱(chēng)為key，hash函數(shù)的輸出，稱(chēng)為hash值，或者index。以上稱(chēng)呼可能不標(biāo)準(zhǔn)，但是不影響對(duì)方案的理解即可。

hash算法的實(shí)現(xiàn)可以用一個(gè)很簡(jiǎn)單的圖來(lái)表示，如下圖所示，對(duì)輸入的key做hash運(yùn)算后，得到index，以index作為地址，把key值存入到其index對(duì)應(yīng)的hash表中。同理，在查詢的時(shí)候，也是先對(duì)key計(jì)算hash值，然后查hash表，如果hash表無(wú)效，說(shuō)明沒(méi)有命中，如果有效，則判斷hash表中的key和輸入的key是否相等，相等則為命中。

舉2個(gè)例子簡(jiǎn)單說(shuō)明下，假定key5，計(jì)算出index = 0，但是add0為空，所以key5沒(méi)有命中，或者說(shuō)，hash表中沒(méi)有key5這個(gè)元素。假定key6，計(jì)算hash后得到index = 3，hash表addr3中有數(shù)據(jù)，但是存放在addr3中的數(shù)據(jù)為key4，不等于key6，所以key6也沒(méi)有命中。

hash表構(gòu)建

上圖hash表的示意圖其實(shí)已經(jīng)說(shuō)明了一個(gè)簡(jiǎn)單的hash表的構(gòu)建，在FPGA內(nèi)部，常用BRAM來(lái)存放一個(gè)hash表，上圖所示hash表的深度為N，每個(gè)hash表中存放一個(gè)key。假如key的位寬為50個(gè)bit，hash后的index位寬為9bit。那么hash表就需要一個(gè)64bit*512表項(xiàng)，消耗1個(gè)M36K（以xilinx的資源為例）。

但是事情肯定沒(méi)有這么簡(jiǎn)單，因?yàn)橹灰衕ash的地方就有沖突。那么下一步就是要解決hash沖突的問(wèn)題。

解決hash沖突最常見(jiàn)的方案就是hash鏈表，如下圖所示，key1、key5、key7具有相同的hash值，可以通過(guò)一個(gè)鏈表的形式將他們串聯(lián)在一起。這種方案在軟件是可能是非常好實(shí)現(xiàn)的，但是在FPGA里實(shí)現(xiàn)可能就比較難了，比如鏈表的最大深度為多少呢？每個(gè)hash桶的鏈表是單獨(dú)存放還是所有的存放在一起呢？

我們知道一個(gè)好的hash函數(shù)，應(yīng)該是要盡可能地減少?zèng)_突的。如果從算法上我們證明了，我們的沖突最多不超過(guò)4次，那就有更加簡(jiǎn)單的方案來(lái)實(shí)現(xiàn)這個(gè)hash表了。

我們把hash表做一個(gè)改進(jìn)，如下圖所示，我們每個(gè)hash桶中，不再是存放一個(gè)key，而是最多存放4個(gè)key，也就是不用鏈表來(lái)解決hash沖突問(wèn)題。

這樣做的好處有2個(gè)，一個(gè)是沒(méi)有了對(duì)鏈表的處理，比較簡(jiǎn)單，第二個(gè)就是處理速度快，一次讀操作就把具有相同hash值的所有key值全部讀出來(lái)進(jìn)行比較。那這種方案在FPGA的ram中如何實(shí)現(xiàn)呢？還是以key的寬度為50bit，index的位寬為9bit為例。

一個(gè)桶的內(nèi)部結(jié)果如下圖所示，每個(gè)key還需要1bit指示是否有效，那么4個(gè)key需要514 = 204bit，用一個(gè)216bit512的BRAM即可，消耗2.5個(gè)M36K。

如果key的位寬非常大，比如是五元組，一共104bit，如果用上述的方案，那就是105*4 = 420bit，那就需要6個(gè)M36K來(lái)存放。可見(jiàn)，key的位寬越大，消耗的資源就越多。

hash表的優(yōu)化

如果我的設(shè)計(jì)，要的就是速度，對(duì)資源的消耗不是很關(guān)系，那用上述的結(jié)構(gòu)即可，如果我的設(shè)計(jì)可以犧牲一點(diǎn)點(diǎn)性能，但是需要減少資源的消耗，怎么辦呢？

我們可以把hash桶的內(nèi)部結(jié)構(gòu)修改下，由拼位寬改成拼深度，如下圖所示：

分別以50bit和104bit的key為例，對(duì)于50bit的key，需要的存儲(chǔ)為64bit5124，需要4個(gè)M36K。對(duì)于104bit的key，需要的存儲(chǔ)為108bit5124，需要6塊?？此菩枰木彺娌](méi)有減少，有的情況下甚至增加了。

如果hash值是8bit了，那情況就不一樣了。因?yàn)閔ash值為8bit和9bit的時(shí)候，BRAM的深度的增加，并沒(méi)有帶來(lái)額外的資源消耗，但是表項(xiàng)的寬度卻只有原來(lái)的一半，資源也就可以減少一半。比如原來(lái)hash表位 288bit256，需要消耗4個(gè)M36K，采用上述的優(yōu)化方案后，表項(xiàng)變成144512，只需要消耗2個(gè)M36K。

除了上述的對(duì)hash桶的改進(jìn)外，有時(shí)候可以同時(shí)拼寬度和深度，如下圖所示：

總結(jié)

hash表的設(shè)計(jì)，需要兼顧資源和性能問(wèn)題。主要的考慮點(diǎn)就是充分利用BRAM 的特性來(lái)實(shí)現(xiàn)資源和性能的平衡。

當(dāng)然，hash表也可以不放在BRAM中，存放在DDR里，那就演變成另外一個(gè)話題，如何高效地讀寫(xiě)DDR中的hash表了。