遗传算法在多核系统上的性能分析和优化

发布时间：2018-03-24 01:10

本文选题：遗传算法　切入点：片上多核处理器　出处：《上海交通大学》2012年硕士论文

【摘要】：遗传算法是一种被广泛应用在工程领域的随机算法。它是一种模拟自然界生物进化和自然淘汰的计算模型。在遗传算法的主要操作算子(选择、交叉和变异)中,种群中每个个体之间的数据独立性强,非常适合并行化,因此,遗传算法的并行化研究也随着遗传算法的诞生而开始。当前,随着多核处理器的普及,进行遗传算法并行化计算的研究的成本也随之降低。大多数研究人员将注意力放在了遗传算法本身的研究以及特定的应用场景。然而,由于缺乏对多核处理器体系结构的深入理解,并没有针对体系结构角度的遗传算法性能分析和优化的通用结论。本文首先立足于片上多核处理器的系统结构,根据片上多核处理器的结构特点分析了并行遗传算法的三种模型——主从式、分岛式和混合式的性能表现,并提出了达到指定精度的速度这一分析性能的全新角度。对于主从式模型,我们提出了线程对齐的指导意见,从而避免了额外的性能开销;对于分岛式模型,我们从理论角度分析了同步与异步方式在性能上的优劣;对于混合式模型,我们引入了并行度(PD)的概念,提出了存在一个PD值可以使得混合式模型在片上多核处理器上最快地达到指定精度。我们的实验验证了存在这样的一个最优的PD值点,使得混合式模型在速度和精度上具有最好的折中,从而具有达到指定精度的最快速度。根据混合式模型的性能表现,本文将目标系统进一步延伸到对称多处理器上。我们在分析了对称多处理器的体系结构特点的基础上,提出了遗传算法混合式模型的线程组织优化策略,力图从降低处理器之间的维护缓存一致性的开销的角度来提升混合式模型的性能。该线程组织优化策略可以指导用户在使用混合式模型时,手动去分配线程与处理器的处理核心的绑定关系。实验证明,优化的线程组织策略可以提升混合式模型10%的性能。本文最后从增加遗传算法本身随机性的角度出发,提出了一个衍生的随机数模型。该模型试图牺牲遗传算法程序的空间复杂度,从而换取在结果的精度上的提升。实验表明,该衍生随机数模型对遗传算法的诸多模型具有普遍的精度提升效果。
[Abstract]:Genetic algorithm (GA) is a random algorithm widely used in engineering. It is a computational model that simulates natural evolution and natural elimination. The data independence of each individual in the population is very independent and suitable for parallelization. Therefore, the research of genetic algorithm parallelization also began with the birth of genetic algorithm. The cost of parallel computing for genetic algorithms has also been reduced. Most researchers have focused on the genetic algorithm itself and on specific application scenarios. However, Due to the lack of in-depth understanding of the multi-core processor architecture, there is no general conclusion on the performance analysis and optimization of genetic algorithms in terms of architecture. In this paper, based on the system architecture of multi-core processors on a chip, the performance of three kinds of parallel genetic algorithms, including master-slave, island-divided and hybrid, is analyzed according to the characteristics of on-chip multi-core processors. For the master-slave model, we put forward the guidance of thread alignment to avoid the extra performance overhead, and for the island-divided model, we proposed a new angle to analyze the performance of the performance. In the case of the master-slave model, we put forward the guidance of thread alignment to avoid the additional performance overhead. We analyze the performance of synchronous and asynchronous methods from a theoretical point of view, and introduce the concept of parallelism PDs for hybrid models. In this paper, it is proposed that the hybrid model with a PD value can achieve the specified accuracy as quickly as possible on a multi-core processor on a chip. Our experiments verify the existence of such an optimal PD value point. The hybrid model has the best compromise in speed and precision, so it has the fastest speed to achieve the specified precision. According to the performance of the hybrid model, the target system is further extended to symmetric multiprocessors. The optimization strategy of thread organization based on genetic algorithm hybrid model is proposed. It tries to improve the performance of the hybrid model by reducing the overhead of maintaining cache consistency between processors. This thread-organization optimization strategy can guide users to use the hybrid model. Experiments show that the optimized thread organization strategy can improve the performance of the hybrid model by 10%. In the end, from the point of increasing the randomness of genetic algorithm itself, a derived random number model is proposed. The model tries to sacrifice the space complexity of genetic algorithm program in order to improve the accuracy of the result. The derived random number model can improve the accuracy of genetic algorithm.
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP332;TP18

【共引文献】