本文關鍵詞：基于MIC的主從式并行遺傳算法的研究和實現(xiàn)，由筆耕文化傳播整理發(fā)布。

【摘要】：在高新技術快速發(fā)展的現(xiàn)今社會,科學研究、軍事國防和國民經(jīng)濟在向高科技靠攏的過程中遇到了很多挑戰(zhàn),需要解決的問題在其深度和廣度上都呈現(xiàn)指數(shù)發(fā)展趨勢,因此高性能計算和大數(shù)據(jù)等新的研究方向和科學技術應運而生。日常生活中存在很多諸如TSP(旅行商問題)、組合問題和任務分配等NP-Hard問題,這樣的問題很難通過精確的數(shù)學運算得到最優(yōu)解,其最優(yōu)解的獲取具有一定的隨機性。遺傳算法由達爾文的生物進化論和孟德爾的遺傳學說而來,是通過模擬自然進化過程搜索最優(yōu)解的方法,被證明可以很好的解決NP-Hard問題,是一種隨機、高效和全局搜索的有效方法。并行遺傳算法是遺傳算法的延伸,并行遺傳算法可以在處理數(shù)據(jù)規(guī)模很大問題時成倍的減少搜索時間,在現(xiàn)在數(shù)據(jù)大爆炸的時代具有很大的研究價值。并行遺傳算法的主要并行方式分為主從式、分島式和細胞式。不同的并行方案對不同的硬件環(huán)境有不同的優(yōu)勢和缺點,主從模式的遺傳算法的硬件處理節(jié)點分為主節(jié)點和從節(jié)點,其中主節(jié)點負責整個種群的選擇、交叉和變異等操作,而從節(jié)點主要評價種群個體的適應值,這樣的任務分配很明顯會浪費從節(jié)點的計算資源；細胞式并行遺傳算法中每個單獨的節(jié)點只可以和相鄰的節(jié)點進行雜交,這樣得到的問題的解明顯會是局部最優(yōu)解,而且這種模式實現(xiàn)起來非常復雜；分島式實現(xiàn)方式并行性很高,但在實現(xiàn)中容易出現(xiàn)內(nèi)存不足,使得加速效率降低,也會容易陷入局部最優(yōu)解。本文中研究了主從結構模式的并行遺傳算法,根據(jù)MIC的硬件和軟件架構提出基于MIC的主從式并行遺傳算法(IPMSPGA), IPMSPGA充分利用MIC提供的多核多線程、VPU單元提供的SIMD單元和函數(shù)庫等特性加速了整個計算過程,根據(jù)計算任務的特性采用MIC提供的Offload模式。一般來說,隨機數(shù)在遺傳算法中處于重要地位,我們根據(jù)Xeon Phi的架構特性和計算任務的特點,在Offload模式下采用異步傳輸隨機數(shù)從CPU端到MIC的輸送,隨機數(shù)的質量直接決定最優(yōu)解的接近程度,從而異步傳輸保證了IPMSPGA最終結果的優(yōu)越性。IPMSPGA采用線程并行和VPU并行兩層并行方案,其中線程并行通過多線程來實現(xiàn)單指令多數(shù)據(jù)并行、VPU并行通過KCi指令來獲得數(shù)據(jù)并行。提出的IPMSPGA_All和IPMSPGA_Part算法在不同的參數(shù)設定下體現(xiàn)不同的性能,IPMSPGA和傳統(tǒng)的主從式并行遺傳算法和多核的主從式并行遺傳算法的比較得出IPMSPGA不僅在運行時間上優(yōu)于其他算法,而且也保證了問題解的質量。其實驗結果相對基于CPU的傳統(tǒng)MSPGA和host端運行的multi-core MSPGA分別可達到12倍和4倍的提升。IPMSPGA是在單片MIC卡上實現(xiàn)的,單片MIC卡模擬生物進化中的一個種群可以減少MIC卡之間的信息傳輸。針對多個MIC卡,我們后面的研究將在多個MIC中模擬分島模式,單個MIC卡模擬一個種群,N個MIC卡模擬N個種群,每個種群進行獨立的物種進化,到了每個特定的時刻,種群間通過SCIF傳輸高質量的個體。在單點多MIC卡的模式下,host端只作為隨機數(shù)生成器,PCIe總線將高質量隨機數(shù)順序的傳遞到MIC卡上。
【關鍵詞】：并行遺傳算法 Xeon Phi 主從式 高性能計算 異構計算
【學位授予單位】：山東大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP338.6;TP18
【目錄】：

• 摘要8-10
• ABSTRACT10-13
• 第一章 緒論13-18
• 1.1 研究背景13-14
• 1.2 國內(nèi)外研究現(xiàn)狀14-15
• 1.3 本文的主要工作15-16
• 1.4 論文的組織結構16-18
• 第二章 相關知識18-28
• 2.1 遺傳算法18-21
• 2.1.1 自然進化與遺傳算法18-19
• 2.1.2 串行遺傳算法19
• 2.1.3 并行遺傳算法19-21
• 2.2 相關研究21-24
• 2.2.1 基于GPU的遺傳算法21-22
• 2.2.2 基于集群的遺傳算法22-24
• 2.3 MIC高性能計算24-26
• 2.4 章節(jié)小結26-28
• 第三章 基于MIC的主從式并行遺傳算法IPMSPGA28-34
• 3.1 HCSP28-29
• 3.2 IPMSPGA總體設計29-33
• 3.2.1 Offload模式30-31
• 3.2.2 IPMSPGA框架31-32
• 3.2.3 IPMSPGA隨機數(shù)處理32-33
• 3.3 章節(jié)小結33-34
• 第四章 IPMSPGA的實現(xiàn)和優(yōu)化34-44
• 4.1 IPMSPGA的實現(xiàn)34-36
• 4.1.1 IPMSPGA偽代碼34-35
• 4.1.2 IPMSPGA具體實現(xiàn)35-36
• 4.2 IPMSPGA的優(yōu)化設計36-43
• 4.2.1 性能優(yōu)化36-37
• 4.2.2 OpenMP優(yōu)化37-38
• 4.2.3 Nocopy38-40
• 4.2.4 向量化優(yōu)化40-43
• 4.2.5 offload異步傳輸43
• 4.3 章節(jié)小結43-44
• 第五章 系統(tǒng)測試44-50
• 5.1 環(huán)境設置44-45
• 5.2 性能測試和結論分析45-49
• 5.2.1 參數(shù)選擇45
• 5.2.2 遺傳操作比較45-46
• 5.2.3 結論分析46-48
• 5.2.4 MIC性能分析48-49
• 5.3 本章小結49-50
• 第六章 總結與展望50-52
• 6.1 總結50
• 6.2 展望50-52
• 參考文獻52-56
• 致謝56-57
• 攻讀學位期間參加的項目57-58
• 攻讀碩士期間發(fā)表的學術論文58-59
• 學位論文評閱及答辯情況表59

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 吉培榮;趙青;劉鵠;夏平;;一種新的偽并行遺傳算法(英文)[J];廣西師范大學學報(自然科學版);2006年04期

2 高家全;何桂霞;;并行遺傳算法研究綜述[J];浙江工業(yè)大學學報;2007年01期

3 陳艷;郭慶平;;并行遺傳算法在導熱反問題中的應用[J];計算機與數(shù)字工程;2007年03期

4 章小龍;;標準并行遺傳算法改進研究[J];福建電腦;2007年09期

5 殷新春;仇亮;;基于主從式并行遺傳算法的S盒優(yōu)化算法[J];計算機工程與應用;2008年24期

6 王竹榮;巨濤;馬凡;;多核集群系統(tǒng)下的混合并行遺傳算法研究[J];計算機科學;2011年07期

7 郭絢,石曉虹;并行遺傳算法的性能分析[J];航空計算技術;1998年03期

8 周明,孫樹棟,彭炎午;并行遺傳算法的研究評述[J];南昌航空工業(yè)學院學報;1998年02期

9 侯廣坤,駱江鵬;一種理想并行遺傳算法模型[J];軟件學報;1999年05期

10 馮小丹;婁自婷;王文元;;并行遺傳算法的研究及應用進展[J];電腦知識與技術;2014年10期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 屈喜龍;;并行遺傳算法的分析與實現(xiàn)[A];第六屆中國青年運籌與管理學者大會論文集[C];2004年

2 劉桂萍;韓旭;鐘志華;姜潮;;基于多種群的隔代映射并行遺傳算法[A];中國力學學會學術大會'2005論文摘要集（下）[C];2005年

3 余艷芳;錢鋒;;并行遺傳算法研究[A];上海市化學化工學會2006年度學術年會論文摘要集[C];2006年

4 徐金榮;李允;唐苗苗;;基于杰出選擇策略的偽并行遺傳算法[A];2008'中國信息技術與應用學術論壇論文集（二）[C];2008年

5 蘇琦;馬良;徐建志;;基于偽并行遺傳算法的無人飛行器航路規(guī)劃[A];2013第一屆中國指揮控制大會論文集[C];2013年

6 安竹林;劉曉平;張偉林;;主從式并行遺傳算法框架應用[A];全國第16屆計算機科學與技術應用（CACIS）學術會議論文集[C];2004年

7 李鳳超;樊紅剛;陳乃祥;;基于并行遺傳算法求解可逆式轉輪雙向流場[A];水電設備的研究與實踐——第十七次中國水電設備學術討論會論文集[C];2009年

8 匡兵;;基于并行遺傳算法的公差優(yōu)化設計[A];中國儀器儀表學會第九屆青年學術會議論文集[C];2007年

9 王力生;張欣;;基于多核處理器的動態(tài)負載平衡并行遺傳算法[A];全國第20屆計算機技術與應用學術會議（CACIS·2009）暨全國第1屆安全關鍵技術與應用學術會議論文集（上冊）[C];2009年

10 江瑞;羅予頻;胡東成;司徒國業(yè);;協(xié)同多Agent構建準并行遺傳算法[A];2001年中國智能自動化會議論文集（下冊）[C];2001年

中國博士學位論文全文數(shù)據(jù)庫 前2條

1 岳]Z;粗粒度并行遺傳算法的計算性能及其應用研究[D];華中科技大學;2008年

2 王琦;MDO優(yōu)化算法研究[D];南京航空航天大學;2008年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 易娟;基于MIC的主從式并行遺傳算法的研究和實現(xiàn)[D];山東大學;2015年

2 龔建剛;煮糖罐換熱管清洗路徑優(yōu)化研究[D];廣西大學;2015年

3 吳昊;并行遺傳算法的研究與應用[D];安徽大學;2001年

4 高睿;混合分布式并行遺傳算法的研究與應用[D];電子科技大學;2006年

5 劉嵩;改進的并行遺傳算法應用研究[D];大連交通大學;2006年

6 王冠;并行遺傳算法及其在組合優(yōu)化問題上的分布式應用[D];武漢理工大學;2003年

7 季洋;并行遺傳算法的研究與實現(xiàn)[D];天津工業(yè)大學;2008年

8 曹婷婷;基于多核的并行遺傳算法的研究與實現(xiàn)[D];東北大學;2010年

9 施錦峰;基于多群體并行遺傳算法的混流混合車間魯棒調度研究[D];浙江工業(yè)大學;2010年

10 張翰;一種改進的異步并行遺傳算法在物流配送路徑的研究[D];吉林大學;2013年

  本文關鍵詞：基于MIC的主從式并行遺傳算法的研究和實現(xiàn)，由筆耕文化傳播整理發(fā)布。

，

本文編號：365181