hash算法在FPGA中的實現(1)

在FPGA的設計中，尤其是在通信領域，經常會遇到hash算法的實現。hash算法在FPGA的設計中，它主要包括2個部分，第一個就是如何選擇一個好的hash函數，減少碰撞；第二個就是如何管理hash表。本文不討論hash算法本身，僅說明hash表的管理。

原理

先對齊本文中要說明的幾個概況，如下圖所示，hash函數的輸入稱為key，hash函數的輸出，稱為hash值，或者index。以上稱呼可能不標準，但是不影響對方案的理解即可。

hash算法的實現可以用一個很簡單的圖來表示，如下圖所示，對輸入的key做hash運算后，得到index，以index作為地址，把key值存入到其index對應的hash表中。同理，在查詢的時候，也是先對key計算hash值，然后查hash表，如果hash表無效，說明沒有命中，如果有效，則判斷hash表中的key和輸入的key是否相等，相等則為命中。

舉2個例子簡單說明下，假定key5，計算出index = 0，但是add0為空，所以key5沒有命中，或者說，hash表中沒有key5這個元素。假定key6，計算hash后得到index = 3，hash表addr3中有數據，但是存放在addr3中的數據為key4，不等于key6，所以key6也沒有命中。

hash表構建

上圖hash表的示意圖其實已經說明了一個簡單的hash表的構建，在FPGA內部，常用BRAM來存放一個hash表，上圖所示hash表的深度為N，每個hash表中存放一個key。假如key的位寬為50個bit，hash后的index位寬為9bit。那么hash表就需要一個64bit*512表項，消耗1個M36K（以xilinx的資源為例）。

但是事情肯定沒有這么簡單，因為只要有hash的地方就有沖突。那么下一步就是要解決hash沖突的問題。

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

我們知道一個好的hash函數，應該是要盡可能地減少沖突的。如果從算法上我們證明了，我們的沖突最多不超過4次，那就有更加簡單的方案來實現這個hash表了。

我們把hash表做一個改進，如下圖所示，我們每個hash桶中，不再是存放一個key，而是最多存放4個key，也就是不用鏈表來解決hash沖突問題。

這樣做的好處有2個，一個是沒有了對鏈表的處理，比較簡單，第二個就是處理速度快，一次讀操作就把具有相同hash值的所有key值全部讀出來進行比較。那這種方案在FPGA的ram中如何實現呢？還是以key的寬度為50bit，index的位寬為9bit為例。

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

如果key的位寬非常大，比如是五元組，一共104bit，如果用上述的方案，那就是105*4 = 420bit，那就需要6個M36K來存放?？梢?，key的位寬越大，消耗的資源就越多。

hash表的優化

如果我的設計，要的就是速度，對資源的消耗不是很關系，那用上述的結構即可，如果我的設計可以犧牲一點點性能，但是需要減少資源的消耗，怎么辦呢？

我們可以把hash桶的內部結構修改下，由拼位寬改成拼深度，如下圖所示：

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

如果hash值是8bit了，那情況就不一樣了。因為hash值為8bit和9bit的時候，BRAM的深度的增加，并沒有帶來額外的資源消耗，但是表項的寬度卻只有原來的一半，資源也就可以減少一半。比如原來hash表位 288bit256，需要消耗4個M36K，采用上述的優化方案后，表項變成144512，只需要消耗2個M36K。

除了上述的對hash桶的改進外，有時候可以同時拼寬度和深度，如下圖所示：

總結

hash表的設計，需要兼顧資源和性能問題。主要的考慮點就是充分利用BRAM 的特性來實現資源和性能的平衡。

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