關于基于TMS320C6678的粒子群算法并行的設計

0 引言

粒子群優化(Particle Swarm Optimization，PSO)算法[1]是由KENNEDY J和EBERHART R C等開發的一種新的進化算法。相對于遺傳算法[2]等，該算法參數較少、容易實現，能夠解決復雜的優化問題，因此在眾多優化問題領域都得到了廣泛的應用[3]，如控制決策、目標跟蹤、深度學習等。然而，粒子群優化算法在實際應用中往往難以達到實時性的要求，特別是求解復雜的多維問題時，速度問題更加突出，難以滿足實際應用的需求。

隨著嵌入式領域對性能、功耗和成本越來越高的要求，多核處理器應運而生[4]。其中TI公司推出的基于KeyStone架構的多核處理器TMS320C6678[5]是目前業界最高性能的量產多核DSP。其具有8個1.25 GHz DSP內核，最高可實現160 GFLOP的性能。與FPGA相比其具有更好的浮點性能和實時處理能力，并且具有較高的靈活性和可編程性，為實現更為復雜的算法提供了便利。因此其在4G通信、航空電子、機器視覺等領域得到了廣泛的應用。

本文針對粒子群算法在實際應用中的實時性需求，在對算法進行并行性分析的基礎上，根據TMS320C6678多核處理器的架構特點，設計出高效的應用程序，充分發揮了TMS320C6678的性能優勢，有效地提高了系統的實時處理能力。實驗數據表明了該設計的合理性與有效性。

1 PSO算法簡介

PSO流程圖如圖1所示。粒子群算法的數學描述如下：m維的解空間中，X={x1，x2，…，xn}表示整個種群，該種群由n個粒子組成。因此整個種群中的第i個粒子的位置可以表示為xi={xi1，xi2，…，xim}，該粒子對應的求解速度可以表示為vi={vi1，vi2，…，vim}，每個粒子對應的個體最優解表示為pi={pi1，pi2，…，pim}，整個種群的全局最優解可以表示為gi={gi1，gi2，…，gim}。在每一次的迭代中，每個粒子將個體最優解pbest和全局最優解gbest作為飛行經驗，根據如下公式來更新自己的速度和位置：

式中，t表示當前迭代次數，xi(t)對應粒子當前時刻的位置，xi(t+1)對應粒子下一時刻的位置，vi(t)和vi(t+1)分別表示粒子當前時刻和下一時刻的速度，ω為慣性因子，c1和c2為學習因子，r1和r2表示在0~1之間的隨機數。此外在每一維，粒子都有最大的限制速度vmax，如果vi>vmax，則有vi=vmax；如果vi

2 多核DSP任務并行設計

2.1 算法并行性分析

粒子群算法和其他一些進化算法相比，其優勢在于步驟簡單、參數少、容易實現、無需梯度信息等。更重要的是粒子群算法是一種并行算法，非常適合在多核處理器上實現其并行計算。算法中各個粒子具有很高的獨立性，所以各個粒子可以獨立地完成信息的更新，從根本上實現各個粒子間的并行操作處理，提高算法的實時性。根據處理器的核心數，將粒子的更新任務平均映射到8個核上。運行時使用如下基本測試函數對該方案進行驗證：

其中，n表示維數，該函數在x=(0，0，…，0)處取得全局最小值fmax=0。另外該函數比較復雜，是一個多峰函數。

2.2 并行處理模型設計

將程序映射到多核處理器的第一步就是確定任務的并行性，并選擇一種最合適的處理模型。前面已經分析了算法的并行性。

兩種最主要的模型是主從模型和數據流模型[6]，分別如圖2、圖3所示。主從模型是一種控制集中、執行分布的模型。數據流模型代表分布式控制和執行。除此之外還有OpenMP模型[7]，該模型是一種在共享內存并行體系中應用發展多線程的應用程序編程接口，如圖4所示。

結合前面算法的并行性分析，考慮到處理流程時間上的并行性和空間上的并行性，這其中包含了流水操作和并發操作，使用單一的模型都無法有效地解決，因此，突破性地將二者結合起來，設計出局部并行全局串行的并行模型，如圖5所示，從而取得良好的并行度和加速比，這在測試數據及結果分析中可以看出。

2.3 處理器之間的通信交流

多核處理器中內核之間如何進行高效的通信交流，是多核系統所面臨的主要難點。處理器之間的通信交流主要包括數據移動和同步[8]。TMS320C6678提供了多種處理器之間的通信機制。軟件是基于SYS/BIOS實時操作系統開發的?？紤]到開發的難易程度及性能，采用IPC核間通信的組件來完成核間數據搬移和同步。該組件有“消息隊列”(MessageQ)和“通知”(Notify)兩種模型。除了Notify通知機制，還可以利用MessageQ來實現更為復雜的核間通信?？紤]到需要同時實現數據搬移和同步，所以采用“消息隊列”(MessageQ)模型。0核作為主核負責向從核發送事件，激活從核并進行一定的運算。主核與從核之間有相互連接。1~7核為從核，主要負責運算，從核之間沒有連接。

3 基于TMS320C6678的PSO算法的實現

軟件部分是基于SYS/BIOS操作系統開發的，同時利用IPC組件。在實現過程中，利用DSP集成開發環境CCS5.2進行相應的編程開發。SYS/BIOS用來實現核間任務調度，IPC用來實現核間同步和通信。

基于TMS320C6678的PSO算法系統框圖如圖6所示。首先是系統啟動，8個核進行相應的初始化配置。初始化配置之后調用Ipc_start()函數將自動實現相應模塊的配置，各個核進入同步等待的狀態，直到8個核都進入同步等待狀態，程序才會繼續執行。一般情況下，在使用IPC組件時直接讓每個核同所有核之間都有連接，而且各核之間連接都是相同且雙向的，這樣的配置方法并不高效，影響運行效率。因此這里有選擇地進行核間連接，使用Ipc.ProcSync_PAIR在.cfg文件中進行配置，之后使用Ipc_attach()函數僅僅在主核與從核之間建立雙向連接。主核首先進行整個粒子群的初始化，主要包括隨機產生粒子的位置和速度，計算出每個粒子的適應度值作為局部最優解，求出對應的全局最優解等任務。主核在完成初始化工作后，將數據分為8份，通過MesssageQ_put()函數將每個核對應的數據的地址發送到對應的核，并啟動從核進行相應的處理。之后所有的核進行循環迭代處理，實現算法對應的進化尋優處理。同時判斷當前解是否滿足預定的最小適應閾值或達到最大迭代次數。最后直到從核完成迭代，通知主核完成所有運算，輸出最優解。

4 實驗結果分析

4.1 存儲空間分析

KeyStone架構是一款精心設計且效率極高的多核心內存架構，其具備3個存儲等級[9]。處理器的每個內核都擁有自己的一級程序（L1P）和數據(L1D)存儲器，均為32 KB大小，這里默認配置成cache使用。二級存儲器L2可以做代碼和數據存儲器，為了提高程序性能，這里把L2的32 KB大小的空間也設置成cache，其余空間用作SRAM。當數據量太大時需要將數據置于DDR3中。該實驗中設計粒子的個數為50，維度也為50，則算法對應的數據量大概為60 KB。另外考慮到共享存儲器有4 MB大小，可以將程序運行涉及的主要數據存放在共享存儲器里，包括粒子的位置、速度、個體最優解、全局最優解等。占用全部片內共享存儲器（MSM）資源的1.5%左右。CCS仿真時的平均收斂曲線如圖7所示。

4.2 運行時間分析

TMS320C6678處理器每個內核頻率為1.25 GHz，可以提供每秒高達40 GB MAC定點運算和20 GFLOP浮點運算能力；1片8核的TMS320C6678提供等效達10 GHz的內核頻率，單精度浮點并行運算能力理論上可達160 GB FLOP。實驗中有關算法的運行時間是通過C語言庫中的clock()函數測量的。處理器運行時的主頻配置為1.0 GHz，則算法迭代500次時運行時鐘數如表1所示。

由表1可以看出，基于TMS320C6678的PSO算法系統得到了較好的核間通信和并行處理性能。在相同的參數環境下，該系統的處理能力是C66x單核的5.19倍。實驗結果表明，基于TMS320C6678的并行粒子群算法的實時處理能力有顯著提升。

4.3 加速比和并行效率

加速比[10]和并行效率是衡量并行處理器性能的兩個重要的指標。加速比(Speedup Rate)用來衡量并行系統或程序并行化的性能和效果。并行效率(Parallel Efficiency)表示在并行機執行并行算法時，平均每個處理機的執行效率。下面根據Amdahl定律[11]來具體計算加速比和并行效率。

假設一個任務在有N個單元的處理器上運行，其中可并行執行的部分為Tp，只能串行的部分為Ts。則在單處理器上運行時間為Tser=Ts+Tp，Tpar=Ts+Tp/P。這里用Sr來表示加速比，則根據表1測試的數據可以求出該系統的加速比如下：

通過以上分析可以看出，通過增加并行處理單元個數可以提高加速比，但是其增加的倍數和增加的處理器的個數并不是嚴格對應的。這是因為處理器個數的增加會帶來額外的通信開銷，甚至在某些情況下會導致系統效率的下降。因此在設計系統時，應綜合考慮處理單元個數、并行結構設計和任務的映射等因素。

5 結論

本文針對粒子群算法在實際應用中的實時性需求，首先對算法進行并行性分析，并根據TMS320C6678多核處理器的架構特點，設計出局部并行全局串行的并行模型，高效地將應用程序映射到多核處理器。該設計也適用于其他架構的并行處理器，具有廣泛的應用性。實驗數據表明該設計充分發揮了TMS320C6678的性能優勢，與單核處理相比有效提高了系統的實時處理能力。因此，該設計有效地推進了PSO算法在實際中的應用，對其他各種群智能算法有重要的借鑒意義。