發(fā)布時(shí)間：2017-05-14 12:19

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

【摘要】：在高新技術(shù)快速發(fā)展的現(xiàn)今社會(huì),科學(xué)研究、軍事國防和國民經(jīng)濟(jì)在向高科技靠攏的過程中遇到了很多挑戰(zhàn),需要解決的問題在其深度和廣度上都呈現(xiàn)指數(shù)發(fā)展趨勢,因此高性能計(jì)算和大數(shù)據(jù)等新的研究方向和科學(xué)技術(shù)應(yīng)運(yùn)而生。日常生活中存在很多諸如TSP(旅行商問題)、組合問題和任務(wù)分配等NP-Hard問題,這樣的問題很難通過精確的數(shù)學(xué)運(yùn)算得到最優(yōu)解,其最優(yōu)解的獲取具有一定的隨機(jī)性。遺傳算法由達(dá)爾文的生物進(jìn)化論和孟德爾的遺傳學(xué)說而來,是通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法,被證明可以很好的解決NP-Hard問題,是一種隨機(jī)、高效和全局搜索的有效方法。并行遺傳算法是遺傳算法的延伸,并行遺傳算法可以在處理數(shù)據(jù)規(guī)模很大問題時(shí)成倍的減少搜索時(shí)間,在現(xiàn)在數(shù)據(jù)大爆炸的時(shí)代具有很大的研究價(jià)值。并行遺傳算法的主要并行方式分為主從式、分島式和細(xì)胞式。不同的并行方案對不同的硬件環(huán)境有不同的優(yōu)勢和缺點(diǎn),主從模式的遺傳算法的硬件處理節(jié)點(diǎn)分為主節(jié)點(diǎn)和從節(jié)點(diǎn),其中主節(jié)點(diǎn)負(fù)責(zé)整個(gè)種群的選擇、交叉和變異等操作,而從節(jié)點(diǎn)主要評價(jià)種群個(gè)體的適應(yīng)值,這樣的任務(wù)分配很明顯會(huì)浪費(fèi)從節(jié)點(diǎn)的計(jì)算資源；細(xì)胞式并行遺傳算法中每個(gè)單獨(dú)的節(jié)點(diǎn)只可以和相鄰的節(jié)點(diǎn)進(jìn)行雜交,這樣得到的問題的解明顯會(huì)是局部最優(yōu)解,而且這種模式實(shí)現(xiàn)起來非常復(fù)雜；分島式實(shí)現(xiàn)方式并行性很高,但在實(shí)現(xiàn)中容易出現(xiàn)內(nèi)存不足,使得加速效率降低,也會(huì)容易陷入局部最優(yōu)解。本文中研究了主從結(jié)構(gòu)模式的并行遺傳算法,根據(jù)MIC的硬件和軟件架構(gòu)提出基于MIC的主從式并行遺傳算法(IPMSPGA), IPMSPGA充分利用MIC提供的多核多線程、VPU單元提供的SIMD單元和函數(shù)庫等特性加速了整個(gè)計(jì)算過程,根據(jù)計(jì)算任務(wù)的特性采用MIC提供的Offload模式。一般來說,隨機(jī)數(shù)在遺傳算法中處于重要地位,我們根據(jù)Xeon Phi的架構(gòu)特性和計(jì)算任務(wù)的特點(diǎn),在Offload模式下采用異步傳輸隨機(jī)數(shù)從CPU端到MIC的輸送,隨機(jī)數(shù)的質(zhì)量直接決定最優(yōu)解的接近程度,從而異步傳輸保證了IPMSPGA最終結(jié)果的優(yōu)越性。IPMSPGA采用線程并行和VPU并行兩層并行方案,其中線程并行通過多線程來實(shí)現(xiàn)單指令多數(shù)據(jù)并行、VPU并行通過KCi指令來獲得數(shù)據(jù)并行。提出的IPMSPGA_All和IPMSPGA_Part算法在不同的參數(shù)設(shè)定下體現(xiàn)不同的性能,IPMSPGA和傳統(tǒng)的主從式并行遺傳算法和多核的主從式并行遺傳算法的比較得出IPMSPGA不僅在運(yùn)行時(shí)間上優(yōu)于其他算法,而且也保證了問題解的質(zhì)量。其實(shí)驗(yàn)結(jié)果相對基于CPU的傳統(tǒng)MSPGA和host端運(yùn)行的multi-core MSPGA分別可達(dá)到12倍和4倍的提升。IPMSPGA是在單片MIC卡上實(shí)現(xiàn)的,單片MIC卡模擬生物進(jìn)化中的一個(gè)種群可以減少M(fèi)IC卡之間的信息傳輸。針對多個(gè)MIC卡,我們后面的研究將在多個(gè)MIC中模擬分島模式,單個(gè)MIC卡模擬一個(gè)種群,N個(gè)MIC卡模擬N個(gè)種群,每個(gè)種群進(jìn)行獨(dú)立的物種進(jìn)化,到了每個(gè)特定的時(shí)刻,種群間通過SCIF傳輸高質(zhì)量的個(gè)體。在單點(diǎn)多MIC卡的模式下,host端只作為隨機(jī)數(shù)生成器,PCIe總線將高質(zhì)量隨機(jī)數(shù)順序的傳遞到MIC卡上。
【關(guān)鍵詞】：并行遺傳算法 Xeon Phi 主從式 高性能計(jì)算 異構(gòu)計(jì)算
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：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 論文的組織結(jié)構(gòu)16-18
• 第二章 相關(guān)知識(shí)18-28
• 2.1 遺傳算法18-21
• 2.1.1 自然進(jìn)化與遺傳算法18-19
• 2.1.2 串行遺傳算法19
• 2.1.3 并行遺傳算法19-21
• 2.2 相關(guān)研究21-24
• 2.2.1 基于GPU的遺傳算法21-22
• 2.2.2 基于集群的遺傳算法22-24
• 2.3 MIC高性能計(jì)算24-26
• 2.4 章節(jié)小結(jié)26-28
• 第三章 基于MIC的主從式并行遺傳算法IPMSPGA28-34
• 3.1 HCSP28-29
• 3.2 IPMSPGA總體設(shè)計(jì)29-33
• 3.2.1 Offload模式30-31
• 3.2.2 IPMSPGA框架31-32
• 3.2.3 IPMSPGA隨機(jī)數(shù)處理32-33
• 3.3 章節(jié)小結(jié)33-34
• 第四章 IPMSPGA的實(shí)現(xiàn)和優(yōu)化34-44
• 4.1 IPMSPGA的實(shí)現(xiàn)34-36
• 4.1.1 IPMSPGA偽代碼34-35
• 4.1.2 IPMSPGA具體實(shí)現(xiàn)35-36
• 4.2 IPMSPGA的優(yōu)化設(shè)計(jì)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é)小結(jié)43-44
• 第五章 系統(tǒng)測試44-50
• 5.1 環(huán)境設(shè)置44-45
• 5.2 性能測試和結(jié)論分析45-49
• 5.2.1 參數(shù)選擇45
• 5.2.2 遺傳操作比較45-46
• 5.2.3 結(jié)論分析46-48
• 5.2.4 MIC性能分析48-49
• 5.3 本章小結(jié)49-50
• 第六章 總結(jié)與展望50-52
• 6.1 總結(jié)50
• 6.2 展望50-52
• 參考文獻(xiàn)52-56
• 致謝56-57
• 攻讀學(xué)位期間參加的項(xiàng)目57-58
• 攻讀碩士期間發(fā)表的學(xué)術(shù)論文58-59
• 學(xué)位論文評閱及答辯情況表59

【相似文獻(xiàn)】

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

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

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

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

4 章小龍;;標(biāo)準(zhǔn)并行遺傳算法改進(jìn)研究[J];福建電腦;2007年09期

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

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

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

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

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

10 馮小丹;婁自婷;王文元;;并行遺傳算法的研究及應(yīng)用進(jìn)展[J];電腦知識(shí)與技術(shù);2014年10期

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

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

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

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

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

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

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

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

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

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

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

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

1 岳]Z;粗粒度并行遺傳算法的計(jì)算性能及其應(yīng)用研究[D];華中科技大學(xué);2008年

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

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

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

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

3 吳昊;并行遺傳算法的研究與應(yīng)用[D];安徽大學(xué);2001年

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

5 劉嵩;改進(jìn)的并行遺傳算法應(yīng)用研究[D];大連交通大學(xué);2006年

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

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

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

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

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

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

，

本文編號：365181