本文選題：遺傳算法　切入點：片上多核處理器　出處：《上海交通大學》2012年碩士論文

【摘要】：遺傳算法是一種被廣泛應用在工程領域的隨機算法。它是一種模擬自然界生物進化和自然淘汰的計算模型。在遺傳算法的主要操作算子(選擇、交叉和變異)中,種群中每個個體之間的數(shù)據(jù)獨立性強,非常適合并行化,因此,遺傳算法的并行化研究也隨著遺傳算法的誕生而開始。當前,隨著多核處理器的普及,進行遺傳算法并行化計算的研究的成本也隨之降低。大多數(shù)研究人員將注意力放在了遺傳算法本身的研究以及特定的應用場景。然而,由于缺乏對多核處理器體系結(jié)構(gòu)的深入理解,并沒有針對體系結(jié)構(gòu)角度的遺傳算法性能分析和優(yōu)化的通用結(jié)論。 本文首先立足于片上多核處理器的系統(tǒng)結(jié)構(gòu),根據(jù)片上多核處理器的結(jié)構(gòu)特點分析了并行遺傳算法的三種模型——主從式、分島式和混合式的性能表現(xiàn),并提出了達到指定精度的速度這一分析性能的全新角度。對于主從式模型,我們提出了線程對齊的指導意見,從而避免了額外的性能開銷;對于分島式模型,我們從理論角度分析了同步與異步方式在性能上的優(yōu)劣;對于混合式模型,我們引入了并行度(PD)的概念,提出了存在一個PD值可以使得混合式模型在片上多核處理器上最快地達到指定精度。我們的實驗驗證了存在這樣的一個最優(yōu)的PD值點,使得混合式模型在速度和精度上具有最好的折中,從而具有達到指定精度的最快速度。 根據(jù)混合式模型的性能表現(xiàn),本文將目標系統(tǒng)進一步延伸到對稱多處理器上。我們在分析了對稱多處理器的體系結(jié)構(gòu)特點的基礎上,提出了遺傳算法混合式模型的線程組織優(yōu)化策略,力圖從降低處理器之間的維護緩存一致性的開銷的角度來提升混合式模型的性能。該線程組織優(yōu)化策略可以指導用戶在使用混合式模型時,手動去分配線程與處理器的處理核心的綁定關系。實驗證明,優(yōu)化的線程組織策略可以提升混合式模型10%的性能。 本文最后從增加遺傳算法本身隨機性的角度出發(fā),提出了一個衍生的隨機數(shù)模型。該模型試圖犧牲遺傳算法程序的空間復雜度,從而換取在結(jié)果的精度上的提升。實驗表明,該衍生隨機數(shù)模型對遺傳算法的諸多模型具有普遍的精度提升效果。
[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

【共引文獻】

相關期刊論文 前3條

1 胡曉斌;閆利;;改進的Wiener濾波在圖像恢復中的應用[J];宿州學院學報;2013年10期

2 ZHU Lin;GONG Huili;LI Xiaojuan;LI Yongyong;SU Xiaosi;GUO Gaoxuan;;Comprehensive Analysis and Artificial Intelligent Simulation of Land Subsidence of Beijing, China[J];Chinese Geographical Science;2013年02期

3 閆利;胡曉斌;;利用GA求解衛(wèi)星影像的空間后方交會[J];武漢大學學報(信息科學版);2013年11期

相關博士學位論文 前1條

1 蔣平;機械制造的工藝可靠性研究[D];國防科學技術大學;2010年

，

本文編號：1656022