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