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