本文選題：哈希連接　切入點(diǎn)：無(wú)鎖　出處：《計(jì)算機(jī)學(xué)報(bào)》2017年10期

【摘要】：眾核協(xié)處理器因其良好的并行計(jì)算能力和能源效率,正成為當(dāng)前高性能計(jì)算普遍采用的加速設(shè)備.無(wú)劃分哈希連接算法是多核平臺(tái)上一種簡(jiǎn)單高效的連接算法,但隨著眾核上并發(fā)線程數(shù)的增加,其共享哈希表的鎖同步問(wèn)題正成為算法并行化的瓶頸.為解決上述問(wèn)題,該文提出一種面向眾核協(xié)處理器的自適應(yīng)無(wú)鎖哈希連接算法ALFHJ.該算法通過(guò)評(píng)估數(shù)據(jù)集的潛在沖突度動(dòng)態(tài)調(diào)整算法參數(shù)及處理流程,支持基于CAS(比較與交換)原子操作的無(wú)鎖共享哈希表構(gòu)建,并利用SIMD指令進(jìn)行哈希表探測(cè).同時(shí),該文進(jìn)行了熱點(diǎn)代碼分析,討論了一致性問(wèn)題、ABA問(wèn)題以及收斂性問(wèn)題.在Xeon Phi上的實(shí)驗(yàn)結(jié)果表明,相比最新的基于鎖同步的NPO(優(yōu)化的無(wú)分區(qū)哈希連接)算法,ALFHJ算法有以下兩點(diǎn)優(yōu)勢(shì):(1)在提高哈希表空間利用率的同時(shí),更能保持性能的相對(duì)穩(wěn)定;(2)并行執(zhí)行時(shí)間對(duì)于均勻數(shù)據(jù)集減少約10%,對(duì)于傾斜數(shù)據(jù)集減少約30%~50%.
[Abstract]:Due to its good parallel computing capability and energy efficiency, multi-core coprocessor is becoming a widely used accelerator in high performance computing. Non-partition hash join algorithm is a simple and efficient join algorithm on multi-core platform. However, with the increase of the number of concurrent threads on the multikernel, the lock synchronization problem of the shared hash table is becoming the bottleneck of the parallelization of the algorithm. In this paper, an adaptive unlocked hashing algorithm ALFHJ for multi-kernel coprocessor is proposed. The algorithm dynamically adjusts the parameters and processing flow of the algorithm by evaluating the potential conflict degree of the data set. It supports the construction of unlocked shared hash table based on CAS atomic operation, and detects the hash table using SIMD instruction. At the same time, the hot spot code analysis is carried out in this paper. The consistency problem and convergence problem are discussed. The experimental results on Xeon Phi show that, Compared with the new Lock Synchron-based NPO (optimized Partition Free Hash join) algorithm, ALFHJ has the following two advantages: 1) improving the utilization rate of hash table space, A relatively stable parallel execution time is reduced by about 10 for uniform data sets and 30, 50 for tilted datasets.
【作者單位】： 中國(guó)人民大學(xué)數(shù)據(jù)工程與知識(shí)工程國(guó)家教育部重點(diǎn)實(shí)驗(yàn)室;中國(guó)人民大學(xué)信息學(xué)院;西南林業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院;
【基金】：國(guó)家自然科學(xué)基金(61532021,61772537,61772536,61702522) 國(guó)家重點(diǎn)研發(fā)計(jì)劃(2016YFB1000702) 國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目基金(2014CB340402) 云南省應(yīng)用基礎(chǔ)研究基金(2011FB070)資助~~
【分類(lèi)號(hào)】：TP301.6;TP332

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張健浪;;協(xié)處理器平臺(tái)打造戰(zhàn)略核心[J];個(gè)人電腦;2006年10期

2 張雨濃;馬偉木;李克訥;易稱(chēng)福;;簡(jiǎn)述協(xié)處理器發(fā)展歷程及前景展望[J];中國(guó)科技信息;2008年13期

3 趙成彥;;80387協(xié)處理器的選購(gòu)與安裝[J];電腦愛(ài)好者;1995年07期

4 朱樟明,周端,楊銀堂,徐陽(yáng)揚(yáng);嵌入式協(xié)處理器初等函數(shù)的快速統(tǒng)一實(shí)現(xiàn)[J];電子與信息學(xué)報(bào);2004年02期

5 金釗;;32位嵌入式CPU中系統(tǒng)控制協(xié)處理器的設(shè)計(jì)與實(shí)現(xiàn)[J];電子設(shè)計(jì)應(yīng)用;2006年10期

6 吳康;;應(yīng)用安全協(xié)處理器構(gòu)建一個(gè)金融終端中的安全嵌入式系統(tǒng)[J];中國(guó)公共安全(綜合版);2006年06期

7 孫季豐;袁春林;盛艷青;劉斌;;一種通用安全協(xié)處理器[J];計(jì)算機(jī)工程;2008年22期

8 孫俊杰;;閃存大佬推協(xié)處理器將閃存推向更廣闊市場(chǎng)[J];中國(guó)電子商情(基礎(chǔ)電子);2012年08期

9 張慧娟;;新型語(yǔ)音協(xié)處理器提升快速精確語(yǔ)言識(shí)別及處理能力[J];電子設(shè)計(jì)技術(shù);2012年09期

10 李輝楷;韓軍;翁新釬;賀中柱;曾曉洋;;精簡(jiǎn)指令集計(jì)算機(jī)協(xié)處理器設(shè)計(jì)[J];計(jì)算機(jī)工程;2012年23期

相關(guān)會(huì)議論文 前4條

1 歐慶于;張昌宏;;應(yīng)用安全協(xié)處理器構(gòu)建安全嵌入式系統(tǒng)[A];中國(guó)造船工程學(xué)會(huì)電子技術(shù)學(xué)術(shù)委員會(huì)2006學(xué)術(shù)年會(huì)論文集（上冊(cè)）[C];2006年

2 孟憲元;;FPGA實(shí)現(xiàn)DSP系統(tǒng)的結(jié)構(gòu)模型[A];全國(guó)第二屆嵌入式技術(shù)聯(lián)合學(xué)術(shù)會(huì)議論文集[C];2007年

3 龐博;張長(zhǎng)明;;基于CORDIC算法的數(shù)字協(xié)處理器設(shè)計(jì)與測(cè)試[A];2008年中國(guó)高校通信類(lèi)院系學(xué)術(shù)研討會(huì)論文集（下冊(cè)）[C];2009年

4 李建贏;王虹宇;洪朝群;姜巍;;PIC/MC模型在Intel Xeon Phi上的初步實(shí)現(xiàn)與優(yōu)化[A];第十六屆全國(guó)等離子體科學(xué)技術(shù)會(huì)議暨第一屆全國(guó)等離子體醫(yī)學(xué)研討會(huì)會(huì)議摘要集[C];2013年

相關(guān)重要報(bào)紙文章 前10條

1 記者 周源;英特爾首批至強(qiáng)融合協(xié)處理器問(wèn)世[N];網(wǎng)絡(luò)世界;2012年

2 沈文;AMD+ATI能否雙贏？[N];計(jì)算機(jī)世界;2006年

3 記者　 孫永杰;“核”戰(zhàn)何時(shí)休 客戶(hù)需求最重要[N];中國(guó)電子報(bào);2006年

4 馬文方;AMD收購(gòu)ATi值不值？[N];中國(guó)計(jì)算機(jī)報(bào);2006年

5 Altera公司高級(jí)產(chǎn)品行銷(xiāo)經(jīng)理 Paul Ekas;FPGA協(xié)處理器優(yōu)化汽車(chē)信息系統(tǒng)設(shè)計(jì)[N];中國(guó)電子報(bào);2004年

6 ;新品速遞[N];計(jì)算機(jī)世界;2001年

7 建苗　編譯;Java扮演嵌入式應(yīng)用開(kāi)發(fā)主角[N];計(jì)算機(jī)世界;2005年

8 《網(wǎng)絡(luò)世界》記者 周源;華大基因：Xeon Phi性能超預(yù)期[N];網(wǎng)絡(luò)世界;2014年

9 特約作者 蘇馳;PC系統(tǒng)的新高速公路[N];電腦報(bào);2010年

10 ;TI新型 DSP沖擊720MHz[N];計(jì)算機(jī)世界;2003年

相關(guān)博士學(xué)位論文 前4條

1 鄭喬石;暗硅時(shí)代CoDA架構(gòu)可擴(kuò)展性及能效問(wèn)題研究[D];西北工業(yè)大學(xué);2015年

2 王慶林;基于高性能協(xié)處理器的粒子輸運(yùn)模擬加速關(guān)鍵技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2016年

3 宋宇鯤;動(dòng)態(tài)可重構(gòu)協(xié)處理器研究[D];合肥工業(yè)大學(xué);2006年

4 杜學(xué)亮;定制指令與協(xié)處理器加速機(jī)制的研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2009年

相關(guān)碩士學(xué)位論文 前10條

1 楊靜;基于有限差分的心電模型模擬在CPU與多MIC協(xié)處理器平臺(tái)的并行與優(yōu)化[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

2 梁志力;異構(gòu)多核系統(tǒng)中協(xié)處理器優(yōu)化[D];合肥工業(yè)大學(xué);2015年

3 王捷;一種高性能向量處理器的實(shí)現(xiàn)[D];天津大學(xué);2016年

4 龐博;高性能專(zhuān)用數(shù)字協(xié)處理器的設(shè)計(jì)與測(cè)試[D];電子科技大學(xué);2009年

5 淮侃;手機(jī)多媒體協(xié)處理器芯片的應(yīng)用與實(shí)現(xiàn)[D];西安電子科技大學(xué);2007年

6 金釗;64位高性能嵌入式CPU中系統(tǒng)協(xié)處理器的設(shè)計(jì)與實(shí)現(xiàn)[D];同濟(jì)大學(xué);2007年

7 范凱;基于動(dòng)態(tài)可重構(gòu)技術(shù)的陣列型協(xié)處理器架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)[D];上海交通大學(xué);2010年

8 李鵬;8087數(shù)值協(xié)處理器的分析與設(shè)計(jì)[D];西安電子科技大學(xué);2001年

9 賴(lài)明澈;數(shù)據(jù)并行協(xié)處理器體系結(jié)構(gòu)的研究與實(shí)現(xiàn)[D];國(guó)防科學(xué)技術(shù)大學(xué);2005年

10 姚于斌;面向圖像處理的可重構(gòu)協(xié)處理器結(jié)構(gòu)設(shè)計(jì)研究[D];上海交通大學(xué);2008年

，

本文編號(hào)：1656680