一種散列表的FPGA設計與實現
加入技術交流群
2．3 空閑存儲區管理
為了實現存儲區的快速分配和有效管理，空閑存儲區管理模塊根據用戶設定的存儲區大小、分塊大小，把緩沖區分塊并組織成鏈表，并根據主控制器請求完成表元的刪除和添加。
(1)本模塊在接到復位信號后進入空閑狀態；
(2)接收到空閑存儲區初始化請求后，修改SRAM中每一表元的頭部數據建立鏈表，存儲鏈表首地址；
(3)接收到獲取緩沖區請求后，直接返回鏈表首地址，并根據鏈表首地址訪問SRAM中的表元頭部數據，得到下一表元地址并作為新的鏈表首地址進行存儲；
(4)接收到釋放緩沖區請求后，把鏈表首地址寫入到待釋放表元的下一表元地址字段，把鏈表首地址修改為待釋放表元地址。
2．4 表元查找
表元查找模塊在接到復位、放棄請求信號后，進入空閑狀態，等待主控制器發起查找請求。在收到查找請求后根據輸入的鏈表首地址從SRAM讀取第一塊數據區的頭部數據(含關鍵字、下一表元地址)，在訪問成功后進行關鍵字比較，成功則查找結束并返回當前表元地址和前一表元地址，否則根據下一表元地址循環查找直至最后一個表元，狀態轉換如圖4所示。表元刪除模塊需要使用當前表元地址及前一表元地址。本文引用地址：http://www.104case.com/article/189637.htm
2．5 表元添加
表元添加模塊在接到復位信號后，進入空閑狀態，等待主控制器發起表元添加請求。在收到添加請求后把鏈表首地址添加到新表元頭部數據的下一表元地址字段，修改鏈表首地址為新添加表元地址。
2．6 表元刪除
表元刪除模塊在接到復位信號后，進入空閑狀態，等待主控制器發起表元刪除請求。在收到待刪除表元地址及其前一表元地址后，讀取待刪除表元頭部數據，獲取下一表元地址(A-NEXT)字段，并寫入前一表元的下一表元地址(BA-NEXT)字段，完成表元刪除。
2．7 數據輸入／輸出
數據輸入／輸出模塊主要完成輸入緩沖區、輸出緩沖區與SRAM之間的數據搬移，輸入參數有SRAM地址、操作類型、數據長度等信息。
2．8 快速查找緩沖模塊
為了提高散列表的查找效率，使用FPGA構建小容量的CAM，CAM表中存儲HASH值、關鍵字、表元地址及前一表元地址。主控制器在生成表元查找請求時，使用CAM進行查找，如果CAM查找成功則放棄表元查找，否則在表元查找成功后，把新的表元HASH值、關鍵字、表元地址等信息寫入CAM表項。
CAM表采用簡單的循環更換方式作為表元替換策略，具有簡單高效的特點，但并不排除某些特定應用命中率不高的問題。FPGA邏輯實現過程中，保證CAM表中沒有兩個HASH值相同的表項。
2．9 存儲訪問仲裁器
存儲訪問仲裁器采用Wishbone接口方式，可處理空閑緩沖區管理、表元查找、表元添加、表元刪除、數據輸入／輸出等五個模塊的SRAM訪問請求信號，仲裁器采用輪詢方式處理各個模塊的請求信號，建立與SRAM接口控制器之間的連接。SRAM接口控制器采用Brust方式實現對SRAM芯片的讀／寫操作。
3 結論
本設計方案通過模塊仿真和在Spartan-3EXC3S1600E芯片的實際測試，實驗結果表明，基于FPGA和SRAM實現的分離鏈接散列表對于大數據量管理具有良好的應用價值。但是，由于每個散列表應用場景不同，如關鍵字長度、管理數據量、FPGA資源等，因此具體實現過程中，需要根據實際情況對散列表各功能模塊進行差異化處理。
評論