【摘要】：隨著多核計算機的日益普及,大規(guī)模科學(xué)與工程計算、事務(wù)處理與商業(yè)計算的需求,以及數(shù)據(jù)挖掘應(yīng)用領(lǐng)域的不斷擴大,基于多核平臺的線性方程組數(shù)值求解算法和大數(shù)據(jù)量數(shù)值關(guān)聯(lián)規(guī)則算法的研究顯得非常重要。由于多核技術(shù)會增加多線程的創(chuàng)建、通信和銷毀等開銷,如何有效發(fā)現(xiàn)程序中的可并行性能、優(yōu)化多核并行程序及發(fā)揮多核的最佳性能,成為高性能計算領(lǐng)域研究的重要課題。 本文給出了Cholesky分解算法的詳細推導(dǎo)過程,分析了Cholesky分解并行按照塊分配的任務(wù)分配策略存在負載不均衡,提出了塊交叉分配方案,并與卷簾分配方案對比。對這三種算法均采用了提前發(fā)送策略,并在MPI集群系統(tǒng)上進行了實驗和分析。針對Cholesky分解基于MPI的并行算法設(shè)計復(fù)雜、進程負載均衡困難、消息傳遞和數(shù)據(jù)移動開銷大問題,以及基于多核采用OpenMP并行化的并行性開銷增大和線程負載不平衡的問題,著重考慮多核計算機的優(yōu)勢,提出了一種基于任務(wù)劃分的Cholesky分解多核并行優(yōu)化算法。該算法將大循環(huán)問題劃分成各個相互獨立的小任務(wù),并運用遞歸技術(shù)任務(wù)竊取技術(shù)和動態(tài)負載均衡算法使這些任務(wù)能夠并行完成。 在分析了關(guān)聯(lián)規(guī)則挖掘Apriori算法及其并行算法存在的不足的基礎(chǔ)上,提出了一種改進的關(guān)聯(lián)規(guī)則挖掘的多核并行優(yōu)化算法。該算法對Apriori算法的壓縮矩陣進行了改造,并在多核平臺下利用OpenMP技術(shù)和TBB技術(shù),對串行程序進行循環(huán)并行化和任務(wù)分配的并行化設(shè)計,最大限度地實現(xiàn)并行關(guān)聯(lián)規(guī)則挖掘,提高關(guān)聯(lián)規(guī)則挖掘效率和多核CPU的利用率。 算法程序設(shè)計過程引入了Intel Parallel Studio并行套件,對基于多核的并行算法進行內(nèi)存線程檢查和性能優(yōu)化,消除采用多核平臺并行化所造成的數(shù)據(jù)泄漏數(shù)據(jù)競爭死鎖和效率低等問題。實驗結(jié)果證明基于多核所提出的算法具有較高的并行效率和較好的加速比。
【學(xué)位授予單位】：遼寧師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2011
【分類號】：TP338.6
【圖文】：

allel Composer：編譯器和庫組建并調(diào)試 C/C++應(yīng)用軟件，主要器、IPP 性能庫、TBB 多線程開發(fā)庫。編譯器中含有 OpenMP 多線的支持；而 TBB 多線程開發(fā)庫集合了很多多線程算法和數(shù)據(jù)結(jié)程的開發(fā)。allel Inspector：內(nèi)存與多線程錯誤檢查器，可以尋找會造成從而驗證并進而提高代碼的可靠性和質(zhì)量。allel Amplifier：是一個性能分析器，迅速查找多線程程序在，告訴使用者軟件的擴展性和并行度，快速提高應(yīng)用軟件本身llel Studio 工具上對程序并行化開發(fā)，流程一般按照圖 3.1 所

3) 安裝英特爾 Parallel Studio 并導(dǎo)入授權(quán)文件，具體組件包括： Paser、性能基本庫 IPP、線程構(gòu)建模塊 TBB、Parallel Inspector 及 Pafier。4) 安裝后，Parallel Studio 工具和 Visual Studio 2008 的開發(fā)界面如圖

圖 4.1 塊與節(jié)點的存儲對應(yīng)關(guān)系ock and the corresponding relationship between th算法具體步驟如下：下三角部分分別發(fā)送到各個進程, 按照務(wù),每塊的大小m= n /( 2 p) ，每個節(jié)點p-1依次計算；ank==i)進行如下操作:1塊進行計算：k,j) f(k,j) ,并廣播f(k,j);…,m-1),(k=j+m*my_rank,…,M-1)2塊進行計算：k)-f(w,j)*f(m*my_rank+k,j)/f(j+m*my_a(0,w,j+1)；(k=j+1,…,m-1), (w= j+m*ank!=i) 進行如下操作:

【參考文獻】

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

1 張錦雄;韋化;;基于OpenMP的對稱矩陣LDL~T分解并行算法實現(xiàn)[J];廣西科學(xué)院學(xué)報;2008年03期

2 陳建平,Jerzy Wasniew ski;Cholesky分解遞歸算法與改進[J];計算機研究與發(fā)展;2001年08期

3 宋威;楊炳儒;徐章艷;高靜;;一種改進的頻繁閉項集挖掘算法[J];計算機研究與發(fā)展;2008年02期

4 葉德謙;趙世磊;;基于線性回歸的關(guān)聯(lián)規(guī)則相關(guān)性方法的研究[J];計算機研究與發(fā)展;2008年S1期

5 曾萬聃;周緒波;戴勃;常桂然;李春平;;關(guān)聯(lián)規(guī)則挖掘的矩陣算法[J];計算機工程;2006年02期

6 李成軍;楊天奇;;一種改進的加權(quán)關(guān)聯(lián)規(guī)則挖掘方法[J];計算機工程;2010年07期

7 楊川;楊斌;;基于TBB的傅里葉變換多核并行化實現(xiàn)[J];計算機工程;2010年16期

8 鄔貴明;竇勇;王淼;;Cholesky分解細粒度并行算法[J];計算機工程與科學(xué);2010年09期

9 單瑩;吳建平;王正華;;基于SMP集群的多層次并行編程模型與并行優(yōu)化技術(shù)[J];計算機應(yīng)用研究;2006年10期

10 王丹陽;田衛(wèi)東;胡學(xué)鋼;;一種有效的并行頻繁項集挖掘算法[J];計算機應(yīng)用研究;2008年11期

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

1 邢芳;基于集群系統(tǒng)并行求解線性方程組的設(shè)計與實現(xiàn)[D];遼寧師范大學(xué);2010年

2 陰斐;LINUX集群可視化監(jiān)測工具的研究與實現(xiàn)技術(shù)[D];鄭州大學(xué);2005年

3 孫靜姝;一種改進的并行關(guān)聯(lián)規(guī)則挖掘算法[D];哈爾濱工程大學(xué);2007年

4 佟強;Linux集群上并行I/O與核外存儲策略的研究與實現(xiàn)[D];哈爾濱工業(yè)大學(xué);2002年

5 王熒;并行關(guān)聯(lián)規(guī)則算法優(yōu)化的研究[D];山東科技大學(xué);2007年

6 伊君翰;基于多核的并行編程模型[D];復(fù)旦大學(xué);2008年

7 郭慎;基于多核的程序并行優(yōu)化的研究與實現(xiàn)[D];蘇州大學(xué);2010年

8 陳林;基于多核架構(gòu)體系的圖像配準(zhǔn)并行計算方法研究[D];云南大學(xué);2010年

本文編號：2801647