[發(fā)明專利]基于FPGA的并行哈希連接加速方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 202110792999.8
• 申請日: 2021-07-14
• 公開（公告）號: CN113468181B
• 公開（公告）日: 2022-10-11
• 發(fā)明（設(shè)計(jì)）人: 方健;徐實(shí);張擁軍;張光達(dá);王會(huì)權(quán);黃安文;溫家輝;張鴻云
• 申請（專利權(quán)）人: 中國人民解放軍軍事科學(xué)院國防科技創(chuàng)新研究院
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/27;G06F16/23
• 代理公司: 北京奧文知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11534
• 代理人: 張文

1.一種基于FPGA的并行哈希連接加速方法，其特征在于，包括：

在哈希連接的構(gòu)建階段的每個(gè)設(shè)定周期，從第一數(shù)據(jù)表中讀取多個(gè)元組數(shù)據(jù)，利用預(yù)設(shè)的預(yù)劃分函數(shù)計(jì)算每個(gè)元組數(shù)據(jù)對應(yīng)的分區(qū)號，將每個(gè)元組數(shù)據(jù)引導(dǎo)到分區(qū)號對應(yīng)的分區(qū)中，從每個(gè)分區(qū)中讀取一個(gè)元組數(shù)據(jù)構(gòu)建哈希表和鏈表，直至處理完第一數(shù)據(jù)表的所有元組數(shù)據(jù)；

在哈希連接的探測階段的每個(gè)設(shè)定周期，從第二數(shù)據(jù)表中讀取多個(gè)元組數(shù)據(jù)，利用預(yù)設(shè)的預(yù)劃分函數(shù)計(jì)算每個(gè)元組數(shù)據(jù)對應(yīng)的分區(qū)號，將每個(gè)元組數(shù)據(jù)引導(dǎo)到分區(qū)號對應(yīng)的分區(qū)中，從每個(gè)分區(qū)中讀取一個(gè)元組數(shù)據(jù)探測匹配構(gòu)建階段構(gòu)建的哈希表和鏈表，若存在匹配，則進(jìn)行連接操作并輸出連接結(jié)果，直至處理完第二數(shù)據(jù)表的所有元組數(shù)據(jù)；

其中，第一數(shù)據(jù)表和第二數(shù)據(jù)表為待進(jìn)行哈希連接的兩個(gè)數(shù)據(jù)表，一個(gè)分區(qū)號對應(yīng)一個(gè)分區(qū)，分區(qū)數(shù)不小于同時(shí)處理的元組數(shù)據(jù)數(shù)，哈希表和鏈表采用分區(qū)的形式組織，哈希表包括多個(gè)不同的哈希表分區(qū)，鏈表包括多個(gè)不同的鏈表分區(qū)，不同的哈希表分區(qū)和不同的鏈表分區(qū)存儲(chǔ)在FPGA內(nèi)部設(shè)置的不同的存儲(chǔ)體中，不同的存儲(chǔ)體具有獨(dú)立的讀寫端口，哈希連接的構(gòu)建階段和探測階段均在FPGA內(nèi)部完成。

2.根據(jù)權(quán)利要求1所述的基于FPGA的并行哈希連接加速方法，其特征在于，預(yù)劃分函數(shù)采用哈希函數(shù)實(shí)現(xiàn)，哈希函數(shù)用于將元組數(shù)據(jù)映射到分區(qū)對應(yīng)的分區(qū)號。

3.根據(jù)權(quán)利要求1或2所述的基于FPGA的并行哈希連接加速方法，其特征在于，每個(gè)分區(qū)設(shè)置有分區(qū)隊(duì)列，根據(jù)元組數(shù)據(jù)對應(yīng)的分區(qū)號，每個(gè)元組數(shù)據(jù)被引導(dǎo)到對應(yīng)分區(qū)的分區(qū)隊(duì)列中，分區(qū)隊(duì)列用于對元組數(shù)據(jù)進(jìn)行緩存。

4.根據(jù)權(quán)利要求3所述的基于FPGA的并行哈希連接加速方法，其特征在于，從分區(qū)中讀取一個(gè)元組數(shù)據(jù)構(gòu)建哈希表和鏈表，包括：

從分區(qū)隊(duì)列中讀取一個(gè)元組數(shù)據(jù)，利用哈希函數(shù)計(jì)算當(dāng)前讀取的元組數(shù)據(jù)的哈希值，使用哈希值和分區(qū)號確定當(dāng)前讀取的元組數(shù)據(jù)需要訪問的哈希表的哈希入口地址，讀出哈希入口地址對應(yīng)的項(xiàng)，根據(jù)當(dāng)前讀取的元組數(shù)據(jù)生成一個(gè)新的項(xiàng)，將新的項(xiàng)寫入哈希入口地址的位置，以覆蓋哈希入口地址對應(yīng)的項(xiàng)，其中，哈希表的每一項(xiàng)是一個(gè)鏈表的首節(jié)點(diǎn)，包括元組和下一元組指針，下一元組指針表示指向鏈表中下一個(gè)具有相同哈希值的元組存儲(chǔ)的位置，新的項(xiàng)中的元組為當(dāng)前讀取的元組數(shù)據(jù)，新的項(xiàng)中的下一元組指針通過預(yù)設(shè)的地址分配方式生成；

將讀出的哈希入口地址對應(yīng)的項(xiàng)寫入鏈表中，其中，寫入鏈表地址為新的項(xiàng)中的下一元組指針指向的地址，鏈表中的元組對應(yīng)該哈希入口地址對應(yīng)的項(xiàng)中的元組，鏈表中的下一元組指針對應(yīng)該哈希入口地址對應(yīng)的項(xiàng)中的下一元組指針，其中，鏈表的每一項(xiàng)是一個(gè)鏈表的中間節(jié)點(diǎn)或尾節(jié)點(diǎn)，包括元組和下一元組指針，下一元組指針表示指向下一個(gè)具有相同哈希值的元組存儲(chǔ)的位置，若一個(gè)節(jié)點(diǎn)為尾節(jié)點(diǎn)，則當(dāng)前節(jié)點(diǎn)中的元組位置存儲(chǔ)的數(shù)據(jù)無效。