在高新技术快速发展的现今社会,科学研究、军事国防和国民经济在向高科技靠拢的过程中遇到了很多挑战,需要解决的问题在其深度和广度上都呈现指数发展趋势,因此高性能计算和大数据等新的研究方向和科学技术应运而生。日常生活中存在很多诸如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卡上。