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

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

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

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

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

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

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