[發(fā)明專利]一種基于動態(tài)內(nèi)存分配存儲HASH鏈表的FPGA實(shí)現(xiàn)裝置及方法

有效

• 申請?zhí)枺?/td>: 201811525145.8
• 申請日: 2018-12-13
• 公開（公告）號: CN109670083B
• 公開（公告）日: 2023-03-24
• 發(fā)明（設(shè)計(jì)）人: 陳伯芳;王曉斌;詹萬鵬;危必波;鄭蓉
• 申請（專利權(quán)）人: 武漢中元華電科技股份有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/9032
• 代理公司: 武漢開元知識產(chǎn)權(quán)代理有限公司 42104
• 代理人: 唐正玉

本發(fā)明涉及一種基于動態(tài)內(nèi)存分配存儲HASH鏈表的FPGA實(shí)現(xiàn)裝置及方法，裝置包括緩存模塊、哈希控制模塊、哈希計(jì)算結(jié)果調(diào)度模塊、哈希鏈表處理模塊、查找結(jié)果調(diào)度模塊，緩存模塊與哈希控制模塊相連，哈希計(jì)算結(jié)果調(diào)度模塊分別與哈希控制模塊、哈希鏈表處理模塊、查找結(jié)果調(diào)度模塊相連，哈希鏈表處理模塊與查找結(jié)果調(diào)度模塊相連。本發(fā)明應(yīng)用于FPGA實(shí)現(xiàn)HASH鏈表存儲的領(lǐng)域，采用一種動態(tài)內(nèi)存靈活分配的方法，利用FPGA并行化處理的優(yōu)勢，快速實(shí)現(xiàn)HASH鏈表的存儲及查找功能。本發(fā)明可以應(yīng)用于使用HASH鏈表進(jìn)行數(shù)據(jù)存儲、相同字符串匹配查找的應(yīng)用領(lǐng)域，比如FPGA方法實(shí)現(xiàn)GZIP壓縮、LZ77壓縮、網(wǎng)絡(luò)報文統(tǒng)計(jì)等領(lǐng)域，該發(fā)明滿足HASH算法對于速度、資源及準(zhǔn)確性的要求。

技術(shù)領(lǐng)域：

本發(fā)明涉及一種動態(tài)內(nèi)存靈活分配的方法，特別涉及一種基于動態(tài)內(nèi)存分配存儲HASH鏈表的FPGA實(shí)現(xiàn)裝置及方法，應(yīng)用于FPGA實(shí)現(xiàn)HASH鏈表存儲的領(lǐng)域，本發(fā)明可以應(yīng)用于使用HASH鏈表進(jìn)行數(shù)據(jù)存儲、相同字符串匹配查找的應(yīng)用領(lǐng)域，比如FPGA方法實(shí)現(xiàn)GZIP壓縮、LZ77壓縮、網(wǎng)絡(luò)報文統(tǒng)計(jì)等領(lǐng)域。

背景技術(shù)：

一般HASH表采用鏈地址法存儲，即所有HASH地址相同的字符串都被映射到同一個鏈表中，HASH地址不相同的字符串映射到不同的鏈表中。同一個HASH地址的沖突越大時，其對應(yīng)的鏈表長度越長。在極端壞(100％沖突)情況下，所有的數(shù)據(jù)都被映射到同一個鏈表中；在極端好(0％沖突)情況下，所有的鏈表都只有一個節(jié)點(diǎn)。存在查找字符串匹配速度慢，浪費(fèi)資源等缺陷。

發(fā)明內(nèi)容：

本發(fā)明目的為了克服上述現(xiàn)有技術(shù)存在的問題和缺陷，提供一種基于動態(tài)內(nèi)存分配存儲HASH鏈表的FPGA實(shí)現(xiàn)裝置及方法，本發(fā)明采用并行方式大大提高HASH鏈表的插入、移出及查找表速度。采用動態(tài)分配方式，為每個存在沖突的HASH地址在表中分配一段動態(tài)大小的連續(xù)空間，節(jié)省邏輯資源；采用首尾指針方式指示鏈表位置，實(shí)現(xiàn)快速定位；采用動態(tài)開放地址法存儲沖突表，實(shí)現(xiàn)快速讀出所有相同HASH地址。該發(fā)明方法可應(yīng)用于采用HASH算法實(shí)現(xiàn)相同字符串查找、統(tǒng)計(jì)并且邏輯資源有限的場合。

本發(fā)明的技術(shù)方案為：

一種基于動態(tài)內(nèi)存分配存儲HASH鏈表的FPGA實(shí)現(xiàn)裝置，包括緩存模塊、哈希控制模塊、哈希計(jì)算結(jié)果調(diào)度模塊、哈希鏈表處理模塊、查找結(jié)果調(diào)度模塊，其特征在于：緩存模塊與哈希控制模塊相連，哈希計(jì)算結(jié)果調(diào)度模塊分別與哈希控制模塊、哈希鏈表處理模塊、查找結(jié)果調(diào)度模塊相連，哈希鏈表處理模塊與查找結(jié)果調(diào)度模塊相連，

緩存模塊為32KB大小的雙端口RAM，循環(huán)存儲滑動窗口內(nèi)的數(shù)據(jù)，為哈希控制模塊提供HASH插入鏈表、移出鏈表、待編碼字符串的數(shù)值；

哈希控制模塊控制原始數(shù)據(jù)的讀取，將原始數(shù)據(jù)轉(zhuǎn)成3個連續(xù)字符串一組的數(shù)據(jù)流并計(jì)算HASH值；將已插入到哈希表的數(shù)據(jù)指針發(fā)送給緩存模塊；完成輸入原始數(shù)據(jù)的比較，統(tǒng)計(jì)輸入數(shù)據(jù)的重復(fù)次數(shù)，后續(xù)一起插入HASH表；

哈希計(jì)算結(jié)果調(diào)度模塊實(shí)現(xiàn)HASH計(jì)算結(jié)果的分發(fā)調(diào)度，將計(jì)算結(jié)果下發(fā)到8個通道分別進(jìn)行HASH表的建立和維護(hù)，通過并行處理的方式加快HASH鏈表的維護(hù)及指針的更新；

哈希鏈表處理模塊建立并維護(hù)沖突表存儲信息，以HASH值為尋址指針將HASH值相同的字符串存儲在一起，同時將滑動窗口外的數(shù)據(jù)移出鏈表，通過動態(tài)分配緩存的方式靈活的構(gòu)建一部變化的HASH鏈表。在進(jìn)行匹配字符串查找時，通過HASH值尋址查找的方式提供相同匹配字符串的地址信息，由于HASH值相同的字符串是鏈接在一起的，所以可以快速的得到相同匹配字符串的地址信息；

查找結(jié)果調(diào)度模塊實(shí)現(xiàn)相同字符串匹配值查找的控制，對HASH鏈表給出的查找結(jié)果進(jìn)行判斷，剔除掉不在滑動窗口內(nèi)的匹配值，按距離滑動窗口右側(cè)的距離由近及遠(yuǎn)輸出匹配結(jié)果。

一種基于動態(tài)內(nèi)存分配存儲HASH鏈表的FPGA實(shí)現(xiàn)裝置的方法，其特征在于按以下步驟進(jìn)行：