【摘要】：針對傳統(tǒng)的并行哈希劃分算法不能高效地利用多核處理器的并行資源,且不能較好處理有傾斜的輸入數(shù)據(jù)的問題,提出了一種在多核處理器中基于MapReduce的哈希劃分算法,并且提出了存儲結(jié)構(gòu)優(yōu)化、多步劃分優(yōu)化、數(shù)據(jù)傾斜優(yōu)化3種優(yōu)化策略。該算法將輸入數(shù)據(jù)分成若干塊后提交給各個線程并行處理,并選擇合適的策略避免寫沖突,使其能夠高效地利用多核處理器的并行資源。文中提出的哈希表能夠提高cache效率,從而提升算法的整體性能。引入MapReduce模型可使多步哈希劃分在Map過程和Reduce過程中分別進行;數(shù)據(jù)傾斜優(yōu)化策略能使算法適應有傾斜的輸入數(shù)據(jù),且具有較好的效果。實驗結(jié)果表明:在多核處理器中,文中提出的算法能夠適應各種分布的輸入數(shù)據(jù),并且使哈希劃分的整體性能得到提升。
[Abstract]:Aiming at the problem that the traditional parallel hash partition algorithm can not efficiently utilize the parallel resources of the multi-core processor and can not handle the skewed input data, a hash partition algorithm based on MapReduce in the multi-core processor is proposed. Three optimization strategies, storage structure optimization, multi-step partition optimization and data skew optimization, are proposed. The algorithm divides the input data into several blocks and submits them to each thread for parallel processing, and selects appropriate strategies to avoid write conflicts, so that it can efficiently utilize the parallel resources of multi-core processors. The hash table proposed in this paper can improve the efficiency of cache and improve the overall performance of the algorithm. By introducing MapReduce model, the multi-step hash partition can be carried out in the Map process and the Reduce process, and the data skew optimization strategy can adapt the algorithm to the skewed input data, and it has a good effect. Experimental results show that the proposed algorithm can adapt to all kinds of distributed input data and improve the overall performance of hash partitioning in multi-core processors.
【作者單位】： 西安電子科技大學計算機學院;
【基金】：國家科技支撐計劃資助項目(2012BAH01B05) 陜西省科技統(tǒng)籌創(chuàng)新工程計劃資助項目(2012KTZD-02-05-2)
【分類號】：TP332

【參考文獻】

相關期刊論文 前1條

1 鄧亞丹;景寧;熊偉;;基于共享Cache多核處理器的Hash連接優(yōu)化[J];軟件學報;2010年06期

【共引文獻】

相關期刊論文 前3條

1 陳偉;杜凌霞;陳紅;;多核架構(gòu)下的數(shù)據(jù)處理算法優(yōu)化策略綜述[J];計算機科學與探索;2011年12期

2 黎建輝;劉勇;王衛(wèi)華;周園春;薛興亞;;MapReduce計算模型下的化合物LC-MS鑒定[J];計算機科學與探索;2011年12期

3 顏堅;畢碩本;汪大;郭憶;;多核架構(gòu)下計算凸殼的并行算法[J];計算機科學;2013年02期

相關會議論文 前1條

1 孫莉;郝大騰;王梅;;列存儲數(shù)據(jù)倉庫中Hash連接改進算法研究[A];第29屆中國數(shù)據(jù)庫學術會議論文集（B輯）（NDBC2012）[C];2012年

【相似文獻】

相關期刊論文 前10條

1 馮磊;;多核處理器的數(shù)量裸奔[J];信息系統(tǒng)工程;2006年11期

2 張浩;蘭峰;;多核處理器基本原理及其在汽車領域中應用的展望[J];汽車科技;2007年03期

3 何軍;王飆;;多核處理器的結(jié)構(gòu)設計研究[J];計算機工程;2007年16期

4 肖紅;;基于多核處理器系統(tǒng)開發(fā)中的幾個問題[J];廣東廣播電視大學學報;2007年04期

5 張健浪;;三大于二,多核CPU之田忌賽馬[J];新電腦;2008年06期

6 都思丹;;前言:嵌入式多核處理器系統(tǒng)及視頻信號處理技術研究進展[J];南京大學學報(自然科學版);2009年01期

7 黃國睿;張平;魏廣博;;多核處理器的關鍵技術及其發(fā)展趨勢[J];計算機工程與設計;2009年10期

8 張戈;胡偉武;黃琨;曾洪博;王君;;片上多核處理器的結(jié)構(gòu)級功耗建模與優(yōu)化技術研究[J];自然科學進展;2009年12期

9 萬志濤;章恒;張若淵;;基于多核處理器的深度包檢測的實現(xiàn)和性能評估[J];電信科學;2009年S2期

10 李晉惠;寇立濤;喬永興;;用軟件來提高多核處理器性能的方法分析[J];工業(yè)儀表與自動化裝置;2010年01期

相關會議論文 前10條

1 郭建軍;戴葵;王志英;;一種多核處理器存儲層次性能評估模型[A];第八屆全國信息隱藏與多媒體安全學術大會湖南省計算機學會第十一屆學術年會論文集[C];2009年

2 彭林;張小強;劉德峰;謝倫國;田祖?zhèn)?;一種挖掘多核處理器存儲級并行的算法[A];第15屆全國信息存儲技術學術會議論文集[C];2008年

3 劉杰;馬彥;葉維;高劍剛;;多核處理器存儲體系分析[A];第十五屆計算機工程與工藝年會暨第一屆微處理器技術論壇論文集（A輯）[C];2011年

4 潘送軍;胡瑜;李曉維;;多核處理器瞬態(tài)故障敏感性分析[A];第五屆中國測試學術會議論文集[C];2008年

5 萬志濤;章恒;張若淵;;基于多核處理器的深度包檢測的實現(xiàn)和性能評估[A];中國通信學會信息通信網(wǎng)絡技術委員會2009年年會論文集（上冊）[C];2009年

6 方娟;張紅波;;多核處理器預取策略的研究[A];2010年全國開放式分布與并行計算機學術會議論文集[C];2010年

7 何軍;王飆;;通用多核處理器發(fā)展現(xiàn)狀和趨勢研究[A];第十五屆計算機工程與工藝年會暨第一屆微處理器技術論壇論文集（A輯）[C];2011年

8 桂亞東;;高效能計算機技術展望[A];慶祝中國力學學會成立50周年暨中國力學學會學術大會’2007論文摘要集（下）[C];2007年

9 萬志濤;;基于多核處理器的面向時延敏感服務的云基礎架構(gòu)[A];中國通信學會信息通信網(wǎng)絡技術委員會2011年年會論文集（上冊）[C];2011年

10 陳遠知;;多核處理器的里程碑——TILE64[A];全國第三屆信號和智能信息處理與應用學術交流會�？痆C];2009年

相關重要報紙文章 前10條

1 記者 曹繼軍 顏維琦;我國多核處理器研究實現(xiàn)新突破[N];光明日報;2012年

2 慶廣;多核處理器助力無線多媒體業(yè)務拓展[N];中國電子報;2009年

3 北京大學計算語言所副所長 詹衛(wèi)東;多核服務器：計算優(yōu)勢更上層樓[N];計算機世界;2005年

4 北京大學計算語言所副所長 詹衛(wèi)東;雙/多核服務器 計算優(yōu)勢更上層樓[N];網(wǎng)絡世界;2005年

5 江南計算技術研究所 何正未;軟件滯后制約多核應用[N];計算機世界;2006年

6 李梅　編譯;多核處理器新年井噴[N];計算機世界;2007年

7 英特爾產(chǎn)品與平臺市場部門數(shù)字家庭市場經(jīng)理 莊淳杰;多核將大行其道[N];計算機世界;2007年

8 本報記者 陳斌;多核處理器的未來路徑[N];計算機世界;2008年

9 王悅承;Oracle改變多核定價模式[N];中國計算機報;2006年

10 ;多核：技術無懸念應用待拓展[N];計算機世界;2008年

相關博士學位論文 前10條

1 王淼;面向多核處理器的并行編譯及優(yōu)化關鍵技術研究[D];國防科學技術大學;2010年

2 魏海濤;面向多核處理器的數(shù)據(jù)流程序編譯關鍵技術研究[D];華中科技大學;2010年

3 呂海;多核處理器芯片計算平臺中并行程序性能優(yōu)化的研究[D];北京工業(yè)大學;2012年

4 李建華;片上多核處理器緩存子系統(tǒng)優(yōu)化的研究[D];中國科學技術大學;2013年

5 杜建軍;共享高速緩存多核處理器的關鍵技術研究[D];重慶大學;2011年

6 陳銳忠;非對稱多核處理器的若干調(diào)度問題研究[D];華南理工大學;2013年

7 鄧林;單芯片多核處理器存儲優(yōu)化技術研究[D];國防科學技術大學;2011年

8 呂正;多核處理器存儲系統(tǒng)的驗證方法研究[D];西北大學;2013年

9 賴明澈;同步數(shù)據(jù)觸發(fā)多核處理器體系結(jié)構(gòu)關鍵技術研究[D];國防科學技術大學;2008年

10 蔣建春;異構(gòu)多核嵌入式軟件關鍵問題研究[D];重慶大學;2011年

相關碩士學位論文 前10條

1 謝子光;多核處理器核間通信技術研究[D];電子科技大學;2009年

2 王興啟;多核處理器的有鎖編程與非阻塞算法研究[D];中原工學院;2011年

3 尤凱迪;高性能低功耗多核處理器研究[D];復旦大學;2011年

4 楊國芳;多核處理器核間通信技術研究[D];哈爾濱工程大學;2011年

5 姚宗寶;多核處理器的加速比研究與熱設計[D];蘇州大學;2012年

6 韓毅宏;多核處理器網(wǎng)絡應用研究[D];西安電子科技大學;2010年

7 盛肖煒;多核處理器內(nèi)部核間通信研究[D];沈陽理工大學;2013年

8 徐軍;多核處理器功耗和熱量模型研究及實現(xiàn)[D];上海交通大學;2009年

9 奚海波;并行編程技術在多核處理器上的研究與應用[D];東北師范大學;2010年

10 王雪梅;嵌入式多核處理器的仿真器設計[D];國防科學技術大學;2010年

，

本文編號：2313376