基于MIC的主从式并行遗传算法的研究和实现

发布时间：2017-05-14 12:19

  本文关键词：基于MIC的主从式并行遗传算法的研究和实现，由笔耕文化传播整理发布。

【摘要】：在高新技术快速发展的现今社会,科学研究、军事国防和国民经济在向高科技靠拢的过程中遇到了很多挑战,需要解决的问题在其深度和广度上都呈现指数发展趋势,因此高性能计算和大数据等新的研究方向和科学技术应运而生。日常生活中存在很多诸如TSP(旅行商问题)、组合问题和任务分配等NP-Hard问题,这样的问题很难通过精确的数学运算得到最优解,其最优解的获取具有一定的随机性。遗传算法由达尔文的生物进化论和孟德尔的遗传学说而来,是通过模拟自然进化过程搜索最优解的方法,被证明可以很好的解决NP-Hard问题,是一种随机、高效和全局搜索的有效方法。并行遗传算法是遗传算法的延伸,并行遗传算法可以在处理数据规模很大问题时成倍的减少搜索时间,在现在数据大爆炸的时代具有很大的研究价值。并行遗传算法的主要并行方式分为主从式、分岛式和细胞式。不同的并行方案对不同的硬件环境有不同的优势和缺点,主从模式的遗传算法的硬件处理节点分为主节点和从节点,其中主节点负责整个种群的选择、交叉和变异等操作,而从节点主要评价种群个体的适应值,这样的任务分配很明显会浪费从节点的计算资源；细胞式并行遗传算法中每个单独的节点只可以和相邻的节点进行杂交,这样得到的问题的解明显会是局部最优解,而且这种模式实现起来非常复杂；分岛式实现方式并行性很高,但在实现中容易出现内存不足,使得加速效率降低,也会容易陷入局部最优解。本文中研究了主从结构模式的并行遗传算法,根据MIC的硬件和软件架构提出基于MIC的主从式并行遗传算法(IPMSPGA), IPMSPGA充分利用MIC提供的多核多线程、VPU单元提供的SIMD单元和函数库等特性加速了整个计算过程,根据计算任务的特性采用MIC提供的Offload模式。一般来说,随机数在遗传算法中处于重要地位,我们根据Xeon Phi的架构特性和计算任务的特点,在Offload模式下采用异步传输随机数从CPU端到MIC的输送,随机数的质量直接决定最优解的接近程度,从而异步传输保证了IPMSPGA最终结果的优越性。IPMSPGA采用线程并行和VPU并行两层并行方案,其中线程并行通过多线程来实现单指令多数据并行、VPU并行通过KCi指令来获得数据并行。提出的IPMSPGA_All和IPMSPGA_Part算法在不同的参数设定下体现不同的性能,IPMSPGA和传统的主从式并行遗传算法和多核的主从式并行遗传算法的比较得出IPMSPGA不仅在运行时间上优于其他算法,而且也保证了问题解的质量。其实验结果相对基于CPU的传统MSPGA和host端运行的multi-core MSPGA分别可达到12倍和4倍的提升。IPMSPGA是在单片MIC卡上实现的,单片MIC卡模拟生物进化中的一个种群可以减少MIC卡之间的信息传输。针对多个MIC卡,我们后面的研究将在多个MIC中模拟分岛模式,单个MIC卡模拟一个种群,N个MIC卡模拟N个种群,每个种群进行独立的物种进化,到了每个特定的时刻,种群间通过SCIF传输高质量的个体。在单点多MIC卡的模式下,host端只作为随机数生成器,PCIe总线将高质量随机数顺序的传递到MIC卡上。
【关键词】：并行遗传算法 Xeon Phi 主从式 高性能计算 异构计算
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP338.6;TP18
【目录】：

• 摘要8-10
• ABSTRACT10-13
• 第一章 绪论13-18
• 1.1 研究背景13-14
• 1.2 国内外研究现状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 章节小结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随机数处理32-33
• 3.3 章节小结33-34
• 第四章 IPMSPGA的实现和优化34-44
• 4.1 IPMSPGA的实现34-36
• 4.1.1 IPMSPGA伪代码34-35
• 4.1.2 IPMSPGA具体实现35-36
• 4.2 IPMSPGA的优化设计36-43
• 4.2.1 性能优化36-37
• 4.2.2 OpenMP优化37-38
• 4.2.3 Nocopy38-40
• 4.2.4 向量化优化40-43
• 4.2.5 offload异步传输43
• 4.3 章节小结43-44
• 第五章 系统测试44-50
• 5.1 环境设置44-45
• 5.2 性能测试和结论分析45-49
• 5.2.1 参数选择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
• 攻读硕士期间发表的学术论文58-59
• 学位论文评阅及答辩情况表59

【相似文献】

中国期刊全文数据库 前10条

1 吉培荣;赵青;刘鹄;夏平;;一种新的伪并行遗传算法(英文)[J];广西师范大学学报(自然科学版);2006年04期

2 高家全;何桂霞;;并行遗传算法研究综述[J];浙江工业大学学报;2007年01期

3 陈艳;郭庆平;;并行遗传算法在导热反问题中的应用[J];计算机与数字工程;2007年03期

4 章小龙;;标准并行遗传算法改进研究[J];福建电脑;2007年09期

5 殷新春;仇亮;;基于主从式并行遗传算法的S盒优化算法[J];计算机工程与应用;2008年24期

6 王竹荣;巨涛;马凡;;多核集群系统下的混合并行遗传算法研究[J];计算机科学;2011年07期

7 郭绚,石晓虹;并行遗传算法的性能分析[J];航空计算技术;1998年03期

8 周明,孙树栋,彭炎午;并行遗传算法的研究评述[J];南昌航空工业学院学报;1998年02期

9 侯广坤,骆江鹏;一种理想并行遗传算法模型[J];软件学报;1999年05期

10 冯小丹;娄自婷;王文元;;并行遗传算法的研究及应用进展[J];电脑知识与技术;2014年10期

中国重要会议论文全文数据库 前10条

1 屈喜龙;;并行遗传算法的分析与实现[A];第六届中国青年运筹与管理学者大会论文集[C];2004年

2 刘桂萍;韩旭;钟志华;姜潮;;基于多种群的隔代映射并行遗传算法[A];中国力学学会学术大会'2005论文摘要集（下）[C];2005年

3 余艳芳;钱锋;;并行遗传算法研究[A];上海市化学化工学会2006年度学术年会论文摘要集[C];2006年

4 徐金荣;李允;唐苗苗;;基于杰出选择策略的伪并行遗传算法[A];2008'中国信息技术与应用学术论坛论文集（二）[C];2008年

5 苏琦;马良;徐建志;;基于伪并行遗传算法的无人飞行器航路规划[A];2013第一届中国指挥控制大会论文集[C];2013年

6 安竹林;刘晓平;张伟林;;主从式并行遗传算法框架应用[A];全国第16届计算机科学与技术应用（CACIS）学术会议论文集[C];2004年

7 李凤超;樊红刚;陈乃祥;;基于并行遗传算法求解可逆式转轮双向流场[A];水电设备的研究与实践——第十七次中国水电设备学术讨论会论文集[C];2009年

8 匡兵;;基于并行遗传算法的公差优化设计[A];中国仪器仪表学会第九届青年学术会议论文集[C];2007年

9 王力生;张欣;;基于多核处理器的动态负载平衡并行遗传算法[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

10 江瑞;罗予频;胡东成;司徒国业;;协同多Agent构建准并行遗传算法[A];2001年中国智能自动化会议论文集（下册）[C];2001年

中国博士学位论文全文数据库 前2条

1 岳]Z;粗粒度并行遗传算法的计算性能及其应用研究[D];华中科技大学;2008年

2 王琦;MDO优化算法研究[D];南京航空航天大学;2008年

中国硕士学位论文全文数据库 前10条

1 易娟;基于MIC的主从式并行遗传算法的研究和实现[D];山东大学;2015年

2 龚建刚;煮糖罐换热管清洗路径优化研究[D];广西大学;2015年

3 吴昊;并行遗传算法的研究与应用[D];安徽大学;2001年

4 高睿;混合分布式并行遗传算法的研究与应用[D];电子科技大学;2006年

5 刘嵩;改进的并行遗传算法应用研究[D];大连交通大学;2006年

6 王冠;并行遗传算法及其在组合优化问题上的分布式应用[D];武汉理工大学;2003年

7 季洋;并行遗传算法的研究与实现[D];天津工业大学;2008年

8 曹婷婷;基于多核的并行遗传算法的研究与实现[D];东北大学;2010年

9 施锦峰;基于多群体并行遗传算法的混流混合车间鲁棒调度研究[D];浙江工业大学;2010年

10 张翰;一种改进的异步并行遗传算法在物流配送路径的研究[D];吉林大学;2013年

  本文关键词：基于MIC的主从式并行遗传算法的研究和实现，由笔耕文化传播整理发布。

，

本文编号：365181