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

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

【共引文獻(xiàn)】

相關(guān)期刊論文 前3條

1 胡曉斌;閆利;;改進(jìn)的Wiener濾波在圖像恢復(fù)中的應(yīng)用[J];宿州學(xué)院學(xué)報(bào);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)星影像的空間后方交會(huì)[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2013年11期

相關(guān)博士學(xué)位論文 前1條

1 蔣平;機(jī)械制造的工藝可靠性研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2010年

，

本文編號(hào)：1656022