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

【摘要】：眾核協(xié)處理器因其良好的并行計(jì)算能力和能源效率,正成為當(dāng)前高性能計(jì)算普遍采用的加速設(shè)備.無劃分哈希連接算法是多核平臺上一種簡單高效的連接算法,但隨著眾核上并發(fā)線程數(shù)的增加,其共享哈希表的鎖同步問題正成為算法并行化的瓶頸.為解決上述問題,該文提出一種面向眾核協(xié)處理器的自適應(yīng)無鎖哈希連接算法ALFHJ.該算法通過評估數(shù)據(jù)集的潛在沖突度動(dòng)態(tài)調(diào)整算法參數(shù)及處理流程,支持基于CAS(比較與交換)原子操作的無鎖共享哈希表構(gòu)建,并利用SIMD指令進(jìn)行哈希表探測.同時(shí),該文進(jìn)行了熱點(diǎn)代碼分析,討論了一致性問題、ABA問題以及收斂性問題.在Xeon Phi上的實(shí)驗(yàn)結(jié)果表明,相比最新的基于鎖同步的NPO(優(yōu)化的無分區(qū)哈希連接)算法,ALFHJ算法有以下兩點(diǎn)優(yōu)勢:(1)在提高哈希表空間利用率的同時(shí),更能保持性能的相對穩(wěn)定;(2)并行執(zhí)行時(shí)間對于均勻數(shù)據(jù)集減少約10%,對于傾斜數(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.
【作者單位】： 中國人民大學(xué)數(shù)據(jù)工程與知識工程國家教育部重點(diǎn)實(shí)驗(yàn)室;中國人民大學(xué)信息學(xué)院;西南林業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院;
【基金】：國家自然科學(xué)基金(61532021,61772537,61772536,61702522) 國家重點(diǎn)研發(fā)計(jì)劃(2016YFB1000702) 國家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目基金(2014CB340402) 云南省應(yīng)用基礎(chǔ)研究基金(2011FB070)資助~~
【分類號】：TP301.6;TP332

【相似文獻(xiàn)】

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

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

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

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

4 朱樟明,周端,楊銀堂,徐陽揚(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];中國公共安全(綜合版);2006年06期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 建苗　編譯;Java扮演嵌入式應(yīng)用開發(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ò)展性及能效問題研究[D];西北工業(yè)大學(xué);2015年

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

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

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

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

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

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

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

4 龐博;高性能專用數(shù)字協(xié)處理器的設(shè)計(jì)與測試[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 賴明澈;數(shù)據(jù)并行協(xié)處理器體系結(jié)構(gòu)的研究與實(shí)現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2005年

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

，

本文編號：1656680