文|娛栀
編輯|娛栀
前言
群體智能算法（SIA）在解決優化問題與實際問題時表現出優異的性能，但對于某些複雜問題而言，SIA的計算成本很高，是以需要有效地加速SIA以獲得更好的性能。
此次提出了一個加速SIA（FASI）的高性能通用架構，這與之前僅通過增強并行化來加速SIA的工作不同，FASI既考慮了硬體平台的記憶體架構，又考慮了SIA的資料流，并将SIA的架構重新排程為融合資料流，以提高記憶體通路效率。
FASI通過将算法架構與硬體架構相比對，實作了更高的加速能力，并特定硬體平台的特性設計了FASI并行化和收斂的深度優化結構。
以量子行為粒子群優化算法為例來評估FASI，結果顯示，FASI通過優化硬體實作提高了SIA的吞吐量并提供了更好的性能。
在實驗中，FASI實作了最大290.7Mb/s的吞吐量，并高于幾個現有系統，FPGA上的FASI實作了比GPU和多核CPU更好的加速。
SI的介紹
群體智能（SI），源于去中心化和自組織系統的集體行為，典型的SI系統由一群遵循非常簡單規則并通過作用于當地環境來互相互動的個體組成。
這些個體之間的互相作用可能導緻非常複雜的全球行為的出現，遠遠超出單個個體的能力，自然SI系統中的例子包括鳥群，螞蟻覓食和魚群等。
受自然群體智能的啟發，人們已經提出了一系列用于優化問題的算法，例如粒子群優化（PSO），蟻群優化（ACO）。
PSO的靈感來自鳥群或魚群的社會行為，并廣泛用于實參數優化，ACO模拟蟻群的覓食行為，已成功應用于解決各種組合優化問題。
通常，SI算法（SIA）包括三個階段：（1）分别更新個體;（2）個人的體能評價，（3）所有個人之間的溝通，以實作全球資訊共享，這些階段将疊代多次，直到滿足終止條件。
盡管SIA在解決許多傳統算術和數值方法表現不佳的實際問題方面取得了不同程度的成功，例如無線傳感器網絡中的路由設計和路徑規劃，但它們存在耗時的适應性評估過程導緻的密集計算的缺點，這極大地限制了它們的應用。
但其實已經付出了很多努力來提高SIA的性能，基于群體内的互相作用，SIA自然适合并行化。
SIA的這種固有特性使其非常适合部署在具有并行計算能力的硬體平台上，例如多核CPU，圖形處理單元（GPU）和現場可程式設計門陣列（FPGA）。
但是，如果隻關注并行化的特性，而沒有對硬體平台的屬性給予足夠的關注，那麼性能将沒有足夠的改進。
除了并行化之外，SIA還具有由所有個體之間的互相作用決定的收斂特征，互動應通過每個個體與唯一具有最佳适應度值的個體之間的比較操作來實作。
如果不能根據特定的硬體平台考慮記憶體通路效率來組織好比較，則當群體規模較大時，可能會出現記憶體通路瓶頸和吞吐量限制，進而使算法的性能顯著降低。
為了進一步優化SIA的并行化和收斂性能，人們提出了一個在FPGA、GPU和多核CPU上加速SIA（FASI）的通用架構，FASI提供了由C++語言實作的統一架構，可以部署在不同的硬體平台上。
FPGA上的FASI比其他硬體平台達到更高的加速，與多核CPU相比，FPGA在基準功能球體上最高加速123倍，與GPU相比，FPGA在基準函數SchwefelP9.2上達到了最高22倍的加速。
相關工作
加速SIA已被用于解決許多問題，可盡管已經做出了很大努力，但關于加速補充免疫活動的研究仍處于起步和上升階段，特别好的和令人信服的績效标準還有待提出。
由于密集計算的特點，加速SIA的直接方法是投入更多的計算單元，特别是更多的硬體核心來建構并行計算環境。
FPGA被認為是并行實作SIA的候選硬體平台之一，可以通過其可定制的硬體結構來加速算法，FPGA不僅提供定制的并行結構，還提供靈活的流水線。
提供的乘數專用于矩陣乘法，在應用于SIA時需要對其進行重大修改，還可以使用FPGA實作的吞吐量來評估加速性能。
關于通過FPGA加速SIA的探索很多，其中最重要的是提出了一種針對QPSO的微架構，QPSO的次元更新部分具有明顯的并行化特征，通過并行化計算單元加速，而适應度評估部分仍然是串行的。
與ARM平台相比，這項工作僅實作了加速，而另一項工作更是加速了FPGA上改進的ACO，并将其應用于路徑規劃，路徑規劃也由并行次元更新和串行适應度評估組成。
為了更好地利用硬體資源，人們又所提出的PSO加速器将适應度評估功能打包在一個SP子產品中，該子產品僅計算粒子的适應度值，并由并聯群單元子產品共享。
由于基準功能的複雜性，适應度評估需要花費更多的FPGA資源，是以共享适應度評估功能子產品提供了一種提高并行化程度的經濟方法。
當FPGA晶片上的硬體資源有限時，上部加速政策表現良好，考慮到适應度評估消耗了大部分操作資源和時間，又提出了一種硬體/軟體協同設計加速器。
加速器在異構架構上實作，算法分為兩部分：基準測試功能通過CPU核心中的軟體設計以及左側部分在PFGA中并行部署。
當基準函數發生變化時，這種加速政策是靈活的，并且它可以節省更多的硬體資源，提高并行化程度，然而基準函數和粒子更新之間的通信成為新的性能瓶頸。
為了實作SIA的完全并行化，隻好在PSO的完全并行加速器在單個FPGA晶片上開發，每個粒子都有自己的位置更新單元和适應度評估單元。
除全局資訊共享外，所有粒子均同時運作，然而，加速器仍然沒有達到良好的加速比，主要是因為它們遵循了PSO的原始資料流。
由于群體規模的大小可能會增加，是以制定了多群體政策，粒子被劃分為子群，所有子群自行完成疊代過程。
有一個通信控制器，當它收到更好的全局最佳位置請求時，最佳位置将通過通信結構同步到所有其他子群。
此外，在多個FPGA上也實作了并行遺傳算法（GA），它們都隻是将并行程式設計子產品遷移到FPGA平台，并專注于裝置之間的通信，而沒有充分考慮FPGA的特性，尤其是可定制的流水線。
GPU是用于并行實作SIA的另一種硬體平台，與FPGA相比，GPU具有更多的RAM，可以加速更大資料規模的SIA。
CUDA架構中的PSO實作，旨在加快處理大量資料的問題的算法，GPU的每個處理核心負責整體處理操作的一部分，并且可以充分利用GPU的并行化能力。
GPU上實作了一組生物啟發優化方法（PSO），遺傳算法（GA），模拟退火（SA）和模式搜尋，這可以成為在GPU上實作SIA的良好名額。但是，沒有給出實作細節。
除了以上的算法外，在不同的硬體平台上實作相同的算法并比較實作的性能将為更好地加速算法提供良好的見解。
馬爾可夫鍊蒙特卡洛（MCMC）被實施并進行了深度優化，以便在多核CPU，GPU和FPGA上獲得更好的性能，實驗結果為如何選擇加速平台提供了很好的參考。
在多核CPU、GPU和FPGA上實作了三點維特比譯碼算法，并讨論了解碼吞吐量、程式設計成本和價格成本等性能。
這兩項工作分别加速了每個硬體平台上的算法，較少讨論在不同硬體平台上建構算法的統一并行子產品。
FPGA、GPU和多核CPU的特性和程式設計模型
FPGA接口
FPGA是現場可程式設計門陣列的縮寫，是一種內建電路（IC），制造後可以在現場程式設計，它根據程式連接配接，由于這種靈活的硬體架構，FPGA幾乎沒有總線帶寬限制，它提供了門級并行化和深度可改變的流水線。
經典的FPGA晶片由控制邏輯塊（CLB）組成，CLB是基本功能單元，負載均衡由觸發器和LUT組成，其中觸發器負責存儲，LUT主要用于算術。
考慮到應用對存儲和算術的更高要求，制造商在FPGA中內建了硬核以滿足這些需求和更高的內建度，例如用于存儲的BRAM和用于算術的DSP。
然而，管理如此豐富的資源并不是一項艱巨的任務，功能子產品總是用硬體描述語言（HDL）描述，例如VHDL和Verilog，它們設計用于電路描述，而不是邏輯描述。
程式員必須将算術邏輯轉移到電阻半導體邏輯，這對于使用進階語言的程式員來說具有挑戰性。
圖形處理器
GPU最近作為通用計算裝置變得流行，因為它具有大規模并行架構，并像開發環境提供了改進的可通路性。
GPU由多個相同的計算單元執行個體組成，稱為流多處理器（SM），SM是并行執行一組線程（稱為線程塊）的計算單元。
每個SM都有一個（或多個）單元來擷取指令，多個ALU（即流處理器或CUDA核心）用于并行執行，SM中的所有線程都可以通路的共享記憶體，以及包含每個硬體線程的專用寄存器集的大型寄存器檔案。
線程塊的每個線程都在ALU上處理，由于ALU被分組為共享單個指令單元，是以映射到這些ALU上的線程在每個周期中執行相同的指令，但資料不同。
共享相同指令的每個邏輯線程組稱為warp，此外，屬于不同warps的線程可以在相同的ALU上執行不同的指令，它們雖在不同的時隙中，實際上，ALU在經線之間是分時的。
CUDA提供了一個可通路的編譯器和一個具有熟悉的類C結構的API擴充，在CUDA的程式設計模型中，GPU上的任務是一個網格，其中包含塊。
每個線程都有專用本地記憶體，每個塊都有共享記憶體，對塊的所有線程可見，并且與塊具有相同的生存期，所有線程都必須通路相同的全局記憶體。
紋理記憶體和常量記憶體是隻讀的，它們被緩存以便快速通路，不同的記憶體在帶寬上是完全不同的。
本地記憶體和全局記憶體是通過GDDR5連接配接到GPU的片外DRAM，共享記憶體本質上是容量有限的可程式設計片上一級高速緩存塊。
讨論和結論
FASI是基于算法統一資料流的SIA通用加速架構，大多數SIA具有相同的更新和适應性評估進度，但通信模式不同，FASI将這三個階段分成專用子產品，以便進一步優化。
硬體平台的繁重資料傳輸和分層記憶體架構，通信将成為并行化SIA的吞吐量瓶頸，FASI重新排程SIA的資料流，以減少不同記憶體層次結構之間的資料傳輸，進而提高整體吞吐量。
由于FPAG的分布式記憶體架構和定制的深度可變流水線，FPGA上的FASI可實作更好的吞吐量。
FASI的另一個改進是FASI不會同時并行化所有粒子，而是通過考慮處理器的并行核心數量和記憶體通路的效率将并行粒子分成幾組，在并行化和記憶體帶寬之間可能需要權衡;算法的更好加速應該實作更大的整體吞吐量。
參考文獻：
基于 GPU 的群體智能算法實作調查，IEEE Trans. Cybern，第 46 卷，第 9 期，2016 年 。
定義粒子群優化的标準，IEEE Swarm Intell. Symp，第 120-127 頁，2007 年。
移動自組網中基于群體智能的路由算法綜述，第 1-7 頁，2017 年。
如果你也喜歡我的文章，不妨點個“關注”吧！小生在此謝過了！
END