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

有效

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

1.一種基于動(dòng)態(tài)內(nèi)存分配存儲(chǔ)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)存儲(chǔ)滑動(dòng)窗口內(nèi)的數(shù)據(jù)，為哈希控制模塊提供HASH插入鏈表、移出鏈表、待編碼字符串的數(shù)值；

哈希控制模塊控制原始數(shù)據(jù)的讀取，將原始數(shù)據(jù)轉(zhuǎn)成3個(gè)連續(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個(gè)通道分別進(jìn)行HASH表的建立和維護(hù)，通過并行處理的方式加快HASH鏈表的維護(hù)及指針的更新；

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

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

2.一種根據(jù)權(quán)利要求1所述的基于動(dòng)態(tài)內(nèi)存分配存儲(chǔ)HASH鏈表的FPGA實(shí)現(xiàn)裝置的方法，其特征在于：

步驟一：將原始數(shù)據(jù)按順序?qū)⒁呀?jīng)插入HASH鏈表的數(shù)據(jù)存入緩存模塊，并且為哈希控制模塊提供插入鏈表的數(shù)值，緩存模塊為32K字節(jié)大小的雙端口RAM，是一個(gè)循環(huán)寫入的緩存，通過指針的方式指示當(dāng)前滑動(dòng)窗口的位置；

步驟二：哈希控制模塊控制原始數(shù)據(jù)的讀取，將原始數(shù)據(jù)轉(zhuǎn)成3個(gè)連續(xù)字符串一組的數(shù)據(jù)流并計(jì)算其HASH值，將已插入到哈希表的數(shù)據(jù)指針發(fā)送給緩存模塊控制滑動(dòng)窗口的移動(dòng)；在計(jì)算HASH值的同時(shí)對(duì)3個(gè)連續(xù)字符串的數(shù)據(jù)流進(jìn)行比較，統(tǒng)計(jì)輸入數(shù)據(jù)的重復(fù)次數(shù)，在后續(xù)進(jìn)行插入鏈表及移出鏈表的操作時(shí)可以同時(shí)操作這些重復(fù)的字符串加快維護(hù)鏈表的速度；

步驟三：哈希計(jì)算結(jié)果調(diào)度模塊將哈希控制模塊產(chǎn)生的HASH計(jì)算結(jié)果進(jìn)行分發(fā)調(diào)度，產(chǎn)生8個(gè)通道的HASH維護(hù)請(qǐng)求，通過并行處理的方式加快HASH鏈表的維護(hù)及指針的更新；

步驟四：哈希鏈表處理模塊建立并維護(hù)沖突表存儲(chǔ)信息，根據(jù)哈希計(jì)算結(jié)果調(diào)度模塊下發(fā)的請(qǐng)求命令，以HASH值為尋址指針將HASH值相同的字符串存儲(chǔ)在一起，同時(shí)將滑動(dòng)窗口外的數(shù)據(jù)移出鏈表，通過動(dòng)態(tài)分配緩存的方式靈活的構(gòu)建一部變化的HASH鏈表；對(duì)于查找操作請(qǐng)求，通過HASH值尋址的方式快速的給出相同匹配字符串的位置信息；

步驟五：對(duì)于8個(gè)并行的哈希鏈表處理模塊提供的相同匹配字符串查找結(jié)果，查找結(jié)果調(diào)度模塊將其合并在一起，同時(shí)檢查其字符串信息是否和要求查找的字符串相等，剔除掉HASH結(jié)算結(jié)果相等但實(shí)際字符串不相等的查找結(jié)果。

3.根據(jù)權(quán)利要求2所述的基于動(dòng)態(tài)內(nèi)存分配存儲(chǔ)HASH鏈表的FPGA實(shí)現(xiàn)裝置的方法，其特征在于：所述步驟四哈希鏈表處理模塊采用兩片RAM來存儲(chǔ)HASH鏈表，一片RAM為數(shù)據(jù)空間，即存儲(chǔ)HASH鏈表地址，另一片RAM為控制空間，存儲(chǔ)每一個(gè)HASH地址鏈表的長(zhǎng)度及首尾指針、已經(jīng)分配的存儲(chǔ)空間的數(shù)量和每一個(gè)分配的存儲(chǔ)空間的首地址，在查找匹配結(jié)果時(shí)根據(jù)控制RAM的值讀取匹配結(jié)果。

4.根據(jù)權(quán)利要求3所述的基于動(dòng)態(tài)內(nèi)存分配存儲(chǔ)HASH鏈表的FPGA實(shí)現(xiàn)裝置的方法，其特征在于：所述步驟四具體實(shí)現(xiàn)方法為：(1)鏈表地址空間采用動(dòng)態(tài)分配的方式，為每個(gè)存儲(chǔ)在沖突的HASH地址在表中分配一段固定大小的連續(xù)空間，用于沖突表項(xiàng)的存儲(chǔ)，沒有沖突的HASH地址則不分配該地址空間；當(dāng)鏈表長(zhǎng)度超過已分配的固定大小的連續(xù)空間時(shí)，繼續(xù)分配一片固定大小的連續(xù)空間，每次分配的存儲(chǔ)空間為連續(xù)空間，空間大小根據(jù)配置的參數(shù)選取；(2)將鏈表存儲(chǔ)的首尾地址存儲(chǔ)在控制RAM中，插入鏈表、移出鏈表操作以及查找表時(shí)快速的定位、讀取該位置的存儲(chǔ)結(jié)果，提高速率；(3)將沖突鏈表分配的存儲(chǔ)空間數(shù)量及首地址存儲(chǔ)在控制鏈表中，這樣可以在查找匹配字符串時(shí)快速的讀出所有相同HASH地址；(4)采取并行的運(yùn)行模式，將沖突鏈表分成8個(gè)部分，8個(gè)部分能同時(shí)操作，這樣就能同時(shí)進(jìn)行8個(gè)HASH值的操作，極大的提高HASH存儲(chǔ)及查找的速度。