基于MIC的主從式并行遺傳算法的研究和實(shí)現(xiàn).pdf

1、在高新技術(shù)快速發(fā)展的現(xiàn)今社會(huì)，科學(xué)研究、軍事國(guó)防和國(guó)民經(jīng)濟(jì)在向高科技靠攏的過(guò)程中遇到了很多挑戰(zhàn)，需要解決的問(wèn)題在其深度和廣度上都呈現(xiàn)指數(shù)發(fā)展趨勢(shì)，因此高性能計(jì)算和大數(shù)據(jù)等新的研究方向和科學(xué)技術(shù)應(yīng)運(yùn)而生。日常生活中存在很多諸如TSP（旅行商問(wèn)題）、組合問(wèn)題和任務(wù)分配等NP-Hard問(wèn)題，這樣的問(wèn)題很難通過(guò)精確的數(shù)學(xué)運(yùn)算得到最優(yōu)解，其最優(yōu)解的獲取具有一定的隨機(jī)性。遺傳算法由達(dá)爾文的生物進(jìn)化論和孟德?tīng)柕倪z傳學(xué)說(shuō)而來(lái)，是通過(guò)模擬自然進(jìn)化過(guò)程搜索

2、最優(yōu)解的方法，被證明可以很好的解決NP-Hard問(wèn)題，是一種隨機(jī)、高效和全局搜索的有效方法。
　　并行遺傳算法是遺傳算法的延伸，并行遺傳算法可以在處理數(shù)據(jù)規(guī)模很大問(wèn)題時(shí)成倍的減少搜索時(shí)間，在現(xiàn)在數(shù)據(jù)大爆炸的時(shí)代具有很大的研究?jī)r(jià)值。并行遺傳算法的主要并行方式分為主從式、分島式和細(xì)胞式。不同的并行方案對(duì)不同的硬件環(huán)境有不同的優(yōu)勢(shì)和缺點(diǎn)，主從模式的遺傳算法的硬件處理節(jié)點(diǎn)分為主節(jié)點(diǎn)和從節(jié)點(diǎn)，其中主節(jié)點(diǎn)負(fù)責(zé)整個(gè)種群的選擇、交叉和變異等操作，

3、而從節(jié)點(diǎn)主要評(píng)價(jià)種群個(gè)體的適應(yīng)值，這樣的任務(wù)分配很明顯會(huì)浪費(fèi)從節(jié)點(diǎn)的計(jì)算資源;細(xì)胞式并行遺傳算法中每個(gè)單獨(dú)的節(jié)點(diǎn)只可以和相鄰的節(jié)點(diǎn)進(jìn)行雜交，這樣得到的問(wèn)題的解明顯會(huì)是局部最優(yōu)解，而且這種模式實(shí)現(xiàn)起來(lái)非常復(fù)雜;分島式實(shí)現(xiàn)方式并行性很高，但在實(shí)現(xiàn)中容易出現(xiàn)內(nèi)存不足，使得加速效率降低，也會(huì)容易陷入局部最優(yōu)解。
　　本文中研究了主從結(jié)構(gòu)模式的并行遺傳算法，根據(jù)MIC的硬件和軟件架構(gòu)提出基于MIC的主從式并行遺傳算法(IPMSPGA)，IP

4、MSPGA充分利用MIC提供的多核多線(xiàn)程、VPU單元提供的SIMD單元和函數(shù)庫(kù)等特性加速了整個(gè)計(jì)算過(guò)程，根據(jù)計(jì)算任務(wù)的特性采用MIC提供的Offload模式。一般來(lái)說(shuō)，隨機(jī)數(shù)在遺傳算法中處于重要地位，我們根據(jù)Xeon Phi的架構(gòu)特性和計(jì)算任務(wù)的特點(diǎn)，在Offload模式下采用異步傳輸隨機(jī)數(shù)從CPU端到MIC的輸送，隨機(jī)數(shù)的質(zhì)量直接決定最優(yōu)解的接近程度，從而異步傳輸保證了IPMSPGA最終結(jié)果的優(yōu)越性。 IPMSPGA采用線(xiàn)程并行和VP

5、U并行兩層并行方案，其中線(xiàn)程并行通過(guò)多線(xiàn)程來(lái)實(shí)現(xiàn)單指令多數(shù)據(jù)并行、VPU并行通過(guò)KCi指令來(lái)獲得數(shù)據(jù)并行。提出的IPMSPGA_ All和IPMSPGA_ Part算法在不同的參數(shù)設(shè)定下體現(xiàn)不同的性能，IPMSPGA和傳統(tǒng)的主從式并行遺傳算法和多核的主從式并行遺傳算法的比較得出IPMSPGA不僅在運(yùn)行時(shí)間上優(yōu)于其他算法，而且也保證了問(wèn)題解的質(zhì)量。其實(shí)驗(yàn)結(jié)果相對(duì)基于CPU的傳統(tǒng)MSPGA和host端運(yùn)行的multi-core MSPGA分

6、別可達(dá)到12倍和4倍的提升。
　　IPMSPGA是在單片MIC卡上實(shí)現(xiàn)的，單片MIC卡模擬生物進(jìn)化中的一個(gè)種群可以減少M(fèi)IC卡之間的信息傳輸。針對(duì)多個(gè)MIC卡，我們后面的研究將在多個(gè)MIC中模擬分島模式，單個(gè)MIC卡模擬一個(gè)種群，N個(gè)MIC卡模擬N個(gè)種群，每個(gè)種群進(jìn)行獨(dú)立的物種進(jìn)化，到了每個(gè)特定的時(shí)刻，種群間通過(guò)SCIF傳輸高質(zhì)量的個(gè)體。在單點(diǎn)多MIC卡的模式下，host端只作為隨機(jī)數(shù)生成器，PCIe總線(xiàn)將高質(zhì)量隨機(jī)數(shù)順序的傳遞到