[發(fā)明專利]哈希混合加速系統(tǒng)及應(yīng)用其進(jìn)行哈希連接的方法

有效

• 申請?zhí)枺?/td>: 201711469611.0
• 申請日: 2017-12-28
• 公開（公告）號(hào): CN108182084B
• 公開（公告）日: 2021-05-11
• 發(fā)明（設(shè)計(jì)）人: 吳林陽;郭雪婷;陳云霽
• 申請（專利權(quán)）人: 中國科學(xué)院計(jì)算技術(shù)研究所
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38;G06F16/22
• 代理公司: 中科專利商標(biāo)代理有限責(zé)任公司 11021
• 代理人: 任巖

1.一種哈希混合加速系統(tǒng)，其特征在于包括：

哈希分區(qū)加速器，配置為集成于內(nèi)存上，用于加速處理哈希連接分區(qū)階段，所述內(nèi)存為3D堆疊DRAM，該哈希分區(qū)加速器配置為集成到3D堆疊DRAM的邏輯層上，該哈希分區(qū)加速器包括：

哈希單元，用于從內(nèi)存中讀取分塊的關(guān)系表中多個(gè)元組，然后并行的處理所述多個(gè)元組的鍵，產(chǎn)生多個(gè)哈希索引；

直方圖單元，用于根據(jù)所述多個(gè)哈希索引，并行的更新存儲(chǔ)在該直方圖單元中直方圖數(shù)據(jù)的多個(gè)副本，并將更新后的各副本整合為數(shù)據(jù)一致性的直方圖數(shù)據(jù)表單；

混排單元，用于依據(jù)所述多個(gè)哈希索引，確定各元組存儲(chǔ)于目標(biāo)地址數(shù)組中的位置，將關(guān)系表中的元組復(fù)制到目標(biāo)數(shù)組，實(shí)現(xiàn)對關(guān)系表的劃分；

主機(jī)處理器，包括SIMD單元或者GPU，該SIMD單元或者GPU用于處理哈希連接的構(gòu)造階段和探測階段；

其中，所述哈希分區(qū)加速器與主機(jī)處理器通過總線或者插入器與所述內(nèi)存通信。

2.根據(jù)權(quán)利要求1所述的系統(tǒng)，其特征在于，各3D堆疊DRAM中vault的數(shù)量為4-16，DRAM層為4-8層，所述哈希分區(qū)加速器中哈希單元、直方圖單元和混排單元的并行度為16。

3.根據(jù)權(quán)利要求1所述的系統(tǒng)，其特征在于，所述哈希單元包括多個(gè)并行處理單元及與所述并行處理單元相同數(shù)量的多路選擇器：

所述并行處理單元用于處理各元組的鍵，產(chǎn)生各元組對應(yīng)的哈希索引；

所述多路選擇器連接于各并行處理單元后端，用于選擇哈希索引的輸出為直方圖單元或者混排單元。

4.根據(jù)權(quán)利要求1所述的系統(tǒng)，其特征在于，所述直方圖單元包括多個(gè)并行的增量單元和規(guī)約單元：

所述增量單元分別用于根據(jù)所述多個(gè)哈希索，并行的更新各直方圖數(shù)據(jù)的副本；

所述規(guī)約單元用于將各自第一本地存儲(chǔ)器的更新后表單整合為數(shù)據(jù)一致性的表單。

5.根據(jù)權(quán)利要求1所述的系統(tǒng)，其特征在于，所述混排單元包括：

多個(gè)并行的地址讀取子單元：根據(jù)各所述哈希索引從目標(biāo)地址數(shù)組中讀取目標(biāo)地址；

沖突處理子單元，依據(jù)多個(gè)目標(biāo)地址，對有沖突的目標(biāo)地址，產(chǎn)生基于原始目標(biāo)地址的偏移，同時(shí)也產(chǎn)生相同目標(biāo)地址的計(jì)數(shù)值；

分散子單元，用于根據(jù)所述偏移和原始目標(biāo)地址將元組移動(dòng)到正確的位置，如無沖突則將元組移動(dòng)至無偏移的目標(biāo)地址；

更新子單元，根據(jù)所述計(jì)數(shù)值更新目標(biāo)地址。

6.根據(jù)權(quán)利要求5所述的系統(tǒng)，其特征在于，所述沖突處理子單元包括復(fù)用XNOR網(wǎng)絡(luò)，輸入為沖突的目標(biāo)地址，輸出分別為標(biāo)地址的偏移和計(jì)數(shù)值。

7.根據(jù)權(quán)利要求5所述的系統(tǒng)，其特征在于，各所述地址讀取子單元包括第二本地存儲(chǔ)器，用于存儲(chǔ)目標(biāo)地址。

8.一種應(yīng)用權(quán)利要求1-7任一所述系統(tǒng)進(jìn)行哈希連接的方法，其特征在于包括：

進(jìn)行分區(qū)操作，包括：

應(yīng)用哈希單元從內(nèi)存中讀取分塊的關(guān)系表中多個(gè)元組，然后并行的處理所述多個(gè)元組的鍵，產(chǎn)生多個(gè)哈希索引；

應(yīng)用直方圖單元根據(jù)所述多個(gè)哈希索引，并行的更新存儲(chǔ)在該直方圖單元中直方圖數(shù)據(jù)的多個(gè)副本，并更新后的各副本整合為數(shù)據(jù)一致性的表單；

應(yīng)用混排單元依據(jù)所述多個(gè)哈希索引，確定各元組存儲(chǔ)于目標(biāo)地址數(shù)組中的位置，將關(guān)系表中的元組復(fù)制到目標(biāo)數(shù)組，實(shí)現(xiàn)對關(guān)系表的劃分；

進(jìn)行構(gòu)造操作，應(yīng)用主機(jī)處理器使用較小的關(guān)系表構(gòu)建內(nèi)存中的哈希表；

進(jìn)行探測操作，應(yīng)用主機(jī)處理器在較大的關(guān)系表上對哈希表進(jìn)行核對以完成連接。