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