文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.173115
中文引用格式: 張慶祥,郭緒濤,王晶. 基于TMS320C6678的粒子群算法并行設計[J].電子技術應用,2018,44(2):23-26.
英文引用格式: Zhang Qingxiang,Guo Xutao,Wang Jing. The parallel processing design of particle swarm optimization based on TMS320C6678[J]. Application of Electronic Technique,2018,44(2):23-26.
0 引言
粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法[1]是由KENNEDY J和EBERHART R C等開發(fā)的一種新的進化算法。相對于遺傳算法[2]等,該算法參數(shù)較少、容易實現(xiàn),能夠解決復雜的優(yōu)化問題,因此在眾多優(yōu)化問題領域都得到了廣泛的應用[3],如控制決策、目標跟蹤、深度學習等。然而,粒子群優(yōu)化算法在實際應用中往往難以達到實時性的要求,特別是求解復雜的多維問題時,速度問題更加突出,難以滿足實際應用的需求。
隨著嵌入式領域對性能、功耗和成本越來越高的要求,多核處理器應運而生[4]。其中TI公司推出的基于KeyStone架構的多核處理器TMS320C6678[5]是目前業(yè)界最高性能的量產(chǎn)多核DSP。其具有8個1.25 GHz DSP內核,最高可實現(xiàn)160 GFLOP的性能。與FPGA相比其具有更好的浮點性能和實時處理能力,并且具有較高的靈活性和可編程性,為實現(xiàn)更為復雜的算法提供了便利。因此其在4G通信、航空電子、機器視覺等領域得到了廣泛的應用。
本文針對粒子群算法在實際應用中的實時性需求,在對算法進行并行性分析的基礎上,根據(jù)TMS320C6678多核處理器的架構特點,設計出高效的應用程序,充分發(fā)揮了TMS320C6678的性能優(yōu)勢,有效地提高了系統(tǒng)的實時處理能力。實驗數(shù)據(jù)表明了該設計的合理性與有效性。
1 PSO算法簡介
PSO流程圖如圖1所示。粒子群算法的數(shù)學描述如下:m維的解空間中,X={x1,x2,…,xn}表示整個種群,該種群由n個粒子組成。因此整個種群中的第i個粒子的位置可以表示為xi={xi1,xi2,…,xim},該粒子對應的求解速度可以表示為vi={vi1,vi2,…,vim},每個粒子對應的個體最優(yōu)解表示為pi={pi1,pi2,…,pim},整個種群的全局最優(yōu)解可以表示為gi={gi1,gi2,…,gim}。在每一次的迭代中,每個粒子將個體最優(yōu)解pbest和全局最優(yōu)解gbest作為飛行經(jīng)驗,根據(jù)如下公式來更新自己的速度和位置:
式中,t表示當前迭代次數(shù),xi(t)對應粒子當前時刻的位置,xi(t+1)對應粒子下一時刻的位置,vi(t)和vi(t+1)分別表示粒子當前時刻和下一時刻的速度,ω為慣性因子,c1和c2為學習因子,r1和r2表示在0~1之間的隨機數(shù)。此外在每一維,粒子都有最大的限制速度vmax,如果vi>vmax,則有vi=vmax;如果vi<vmax,則有vi=-vmax。
2 多核DSP任務并行設計
2.1 算法并行性分析
粒子群算法和其他一些進化算法相比,其優(yōu)勢在于步驟簡單、參數(shù)少、容易實現(xiàn)、無需梯度信息等。更重要的是粒子群算法是一種并行算法,非常適合在多核處理器上實現(xiàn)其并行計算。算法中各個粒子具有很高的獨立性,所以各個粒子可以獨立地完成信息的更新,從根本上實現(xiàn)各個粒子間的并行操作處理,提高算法的實時性。根據(jù)處理器的核心數(shù),將粒子的更新任務平均映射到8個核上。運行時使用如下基本測試函數(shù)對該方案進行驗證:
其中,n表示維數(shù),該函數(shù)在x=(0,0,…,0)處取得全局最小值fmax=0。另外該函數(shù)比較復雜,是一個多峰函數(shù)。
2.2 并行處理模型設計
將程序映射到多核處理器的第一步就是確定任務的并行性,并選擇一種最合適的處理模型。前面已經(jīng)分析了算法的并行性。
兩種最主要的模型是主從模型和數(shù)據(jù)流模型[6],分別如圖2、圖3所示。主從模型是一種控制集中、執(zhí)行分布的模型。數(shù)據(jù)流模型代表分布式控制和執(zhí)行。除此之外還有OpenMP模型[7],該模型是一種在共享內存并行體系中應用發(fā)展多線程的應用程序編程接口,如圖4所示。
結合前面算法的并行性分析,考慮到處理流程時間上的并行性和空間上的并行性,這其中包含了流水操作和并發(fā)操作,使用單一的模型都無法有效地解決,因此,突破性地將二者結合起來,設計出局部并行全局串行的并行模型,如圖5所示,從而取得良好的并行度和加速比,這在測試數(shù)據(jù)及結果分析中可以看出。
2.3 處理器之間的通信交流
多核處理器中內核之間如何進行高效的通信交流,是多核系統(tǒng)所面臨的主要難點。處理器之間的通信交流主要包括數(shù)據(jù)移動和同步[8]。TMS320C6678提供了多種處理器之間的通信機制。軟件是基于SYS/BIOS實時操作系統(tǒng)開發(fā)的。考慮到開發(fā)的難易程度及性能,采用IPC核間通信的組件來完成核間數(shù)據(jù)搬移和同步。該組件有“消息隊列”(MessageQ)和“通知”(Notify)兩種模型。除了Notify通知機制,還可以利用MessageQ來實現(xiàn)更為復雜的核間通信??紤]到需要同時實現(xiàn)數(shù)據(jù)搬移和同步,所以采用“消息隊列”(MessageQ)模型。0核作為主核負責向從核發(fā)送事件,激活從核并進行一定的運算。主核與從核之間有相互連接。1~7核為從核,主要負責運算,從核之間沒有連接。
3 基于TMS320C6678的PSO算法的實現(xiàn)
軟件部分是基于SYS/BIOS操作系統(tǒng)開發(fā)的,同時利用IPC組件。在實現(xiàn)過程中,利用DSP集成開發(fā)環(huán)境CCS5.2進行相應的編程開發(fā)。SYS/BIOS用來實現(xiàn)核間任務調度,IPC用來實現(xiàn)核間同步和通信。
基于TMS320C6678的PSO算法系統(tǒng)框圖如圖6所示。首先是系統(tǒng)啟動,8個核進行相應的初始化配置。初始化配置之后調用Ipc_start()函數(shù)將自動實現(xiàn)相應模塊的配置,各個核進入同步等待的狀態(tài),直到8個核都進入同步等待狀態(tài),程序才會繼續(xù)執(zhí)行。一般情況下,在使用IPC組件時直接讓每個核同所有核之間都有連接,而且各核之間連接都是相同且雙向的,這樣的配置方法并不高效,影響運行效率。因此這里有選擇地進行核間連接,使用Ipc.ProcSync_PAIR在.cfg文件中進行配置,之后使用Ipc_attach()函數(shù)僅僅在主核與從核之間建立雙向連接。主核首先進行整個粒子群的初始化,主要包括隨機產(chǎn)生粒子的位置和速度,計算出每個粒子的適應度值作為局部最優(yōu)解,求出對應的全局最優(yōu)解等任務。主核在完成初始化工作后,將數(shù)據(jù)分為8份,通過MesssageQ_put()函數(shù)將每個核對應的數(shù)據(jù)的地址發(fā)送到對應的核,并啟動從核進行相應的處理。之后所有的核進行循環(huán)迭代處理,實現(xiàn)算法對應的進化尋優(yōu)處理。同時判斷當前解是否滿足預定的最小適應閾值或達到最大迭代次數(shù)。最后直到從核完成迭代,通知主核完成所有運算,輸出最優(yōu)解。
4 實驗結果分析
4.1 存儲空間分析
KeyStone架構是一款精心設計且效率極高的多核心內存架構,其具備3個存儲等級[9]。處理器的每個內核都擁有自己的一級程序(L1P)和數(shù)據(jù)(L1D)存儲器,均為32 KB大小,這里默認配置成cache使用。二級存儲器L2可以做代碼和數(shù)據(jù)存儲器,為了提高程序性能,這里把L2的32 KB大小的空間也設置成cache,其余空間用作SRAM。當數(shù)據(jù)量太大時需要將數(shù)據(jù)置于DDR3中。該實驗中設計粒子的個數(shù)為50,維度也為50,則算法對應的數(shù)據(jù)量大概為60 KB。另外考慮到共享存儲器有4 MB大小,可以將程序運行涉及的主要數(shù)據(jù)存放在共享存儲器里,包括粒子的位置、速度、個體最優(yōu)解、全局最優(yōu)解等。占用全部片內共享存儲器(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()函數(shù)測量的。處理器運行時的主頻配置為1.0 GHz,則算法迭代500次時運行時鐘數(shù)如表1所示。
由表1可以看出,基于TMS320C6678的PSO算法系統(tǒng)得到了較好的核間通信和并行處理性能。在相同的參數(shù)環(huán)境下,該系統(tǒng)的處理能力是C66x單核的5.19倍。實驗結果表明,基于TMS320C6678的并行粒子群算法的實時處理能力有顯著提升。
4.3 加速比和并行效率
加速比[10]和并行效率是衡量并行處理器性能的兩個重要的指標。加速比(Speedup Rate)用來衡量并行系統(tǒng)或程序并行化的性能和效果。并行效率(Parallel Efficiency)表示在并行機執(zhí)行并行算法時,平均每個處理機的執(zhí)行效率。下面根據(jù)Amdahl定律[11]來具體計算加速比和并行效率。
假設一個任務在有N個單元的處理器上運行,其中可并行執(zhí)行的部分為Tp,只能串行的部分為Ts。則在單處理器上運行時間為Tser=Ts+Tp,Tpar=Ts+Tp/P。這里用Sr來表示加速比,則根據(jù)表1測試的數(shù)據(jù)可以求出該系統(tǒng)的加速比如下:
通過以上分析可以看出,通過增加并行處理單元個數(shù)可以提高加速比,但是其增加的倍數(shù)和增加的處理器的個數(shù)并不是嚴格對應的。這是因為處理器個數(shù)的增加會帶來額外的通信開銷,甚至在某些情況下會導致系統(tǒng)效率的下降。因此在設計系統(tǒng)時,應綜合考慮處理單元個數(shù)、并行結構設計和任務的映射等因素。
5 結論
本文針對粒子群算法在實際應用中的實時性需求,首先對算法進行并行性分析,并根據(jù)TMS320C6678多核處理器的架構特點,設計出局部并行全局串行的并行模型,高效地將應用程序映射到多核處理器。該設計也適用于其他架構的并行處理器,具有廣泛的應用性。實驗數(shù)據(jù)表明該設計充分發(fā)揮了TMS320C6678的性能優(yōu)勢,與單核處理相比有效提高了系統(tǒng)的實時處理能力。因此,該設計有效地推進了PSO算法在實際中的應用,對其他各種群智能算法有重要的借鑒意義。
參考文獻
[1] KENNEDY J,EBERHART R C.Particle swarm optimization[C].IEEE International Conference on Neural Networks,1995:1942-1948.
[2] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[3] Jin Nanbo,RAHMAT-SAMII Y.Advances in particle swarm optimization for antenna designs:real-number,Binary,single-objective and multiobjective implementations[J].IEEE Transactions on Antennas and Propagation,2007,55(3):556-567.
[4] 郝朋朋,周煦林,唐藝菁,等.基于TMS320C6678多核處理器體系結構的研究[J].微電子學與計算機,2012,29(12):171-175.
[5] Texas Instruments.TMS320C6678 mulicore fixed and floating-point digital signal processor[Z].2010.
[6] Texas Instruments. Multicore programming guide(Literature Number:SPRAB27B)[Z].2011.
[7] 牛金海.TMS320C66x KeyStone架構多核DSP入門與實例精解[M].上海:上海交通大學出版社,2014.
[8] 吳灝,肖吉陽,范紅旗,等.TMS320C6678多核DSP的核間通信方法[J].電子技術應用,2012,38(9):11-13.
[9] Texas Instruments.KeyStone architecture multicore shared memory controller(MSMC)(Literature Number:SPRUGW7A)[Z].2011.
[10] 謝超,麥聯(lián)叨,都志輝,等.關于并行計算系統(tǒng)中加速比的研究與分析[J].計算機工程與應用,2003,39(26):66-68.
[11] 李文石,姚宗寶.基于阿姆達爾定律和蘭特法則計算多核架構的加速比[J].電子學報,2012,40(2):230-234.