本文選題：哈希連接　切入點：無鎖　出處：《計算機學報》2017年10期

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

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關會議論文 前4條

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

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

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

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

相關重要報紙文章 前10條

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

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

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

4 馬文方;AMD收購ATi值不值？[N];中國計算機報;2006年

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

6 ;新品速遞[N];計算機世界;2001年

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

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

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

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

相關博士學位論文 前4條

1 鄭喬石;暗硅時代CoDA架構可擴展性及能效問題研究[D];西北工業(yè)大學;2015年

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

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

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

相關碩士學位論文 前10條

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

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

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

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

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

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

7 范凱;基于動態(tài)可重構技術的陣列型協(xié)處理器架構設計與實現(xiàn)[D];上海交通大學;2010年

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

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

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

，

本文編號：1656680