《電子技術應用》
您所在的位置:首頁 > 嵌入式技術 > 設計應用 > 基于TMS320C6678的粒子群算法并行設計
基于TMS320C6678的粒子群算法并行設計
2018年電子技術應用第2期
張慶祥,,郭緒濤,,王 晶
哈爾濱工業(yè)大學 電子工程技術研究所,黑龍江 哈爾濱150001
摘要: 針對粒子群算法在實際應用中的實時性需求,,對算法的并行性進行分析,,并根據(jù)TMS320C6678多核處理器的架構特點,,設計出局部并行全局串行的并行模型,高效地將應用程序映射到多核處理器中,。實驗數(shù)據(jù)表明,,該設計充分發(fā)揮了TMS320C6678的性能優(yōu)勢,有效提高了系統(tǒng)的實時處理能力,。該設計有效地推進了PSO算法在實際中的應用,,對其他各種群智能算法有重要的借鑒意義。
中圖分類號: TN915.04
文獻標識碼: 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.

The parallel processing design of particle swarm optimization based on TMS320C6678
Zhang Qingxiang,Guo Xutao,,Wang Jing
Institute of Electronic Engineeing Technology,,Harbin Institute of Technology,Harbin 150001,,China
Abstract: In view of the real-time requirement of PSO in practical applications, the parallelism of the algorithm is analyzed. According to the architecture characteristics of TMS320C6678 multi-core processor, this paper designs a local parallel and global serial model, and maps the application program to multi-core processor efficiently. The experimental data shows that the design gives full play to the performance advantage of C6678 and improves the real-time processing capability of the system effectively. The design promotes the application of PSO algorithm in practice effectively and is of important significance to other kinds of swarm intelligent algorithm.
Key words : particle swarm optimization,;TMS320C6678;parallel processing,;speedup rate

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è)界最高性能的量產多核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ù)如下公式來更新自己的速度和位置:

     qrs1-gs1-2.gif

式中,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,。

qrs1-t1.gif

2 多核DSP任務并行設計

2.1 算法并行性分析

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

     qrs1-gs3.gif

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

2.2 并行處理模型設計

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

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

qrs1-t2.gif

qrs1-t3.gif

qrs1-t4.gif

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

qrs1-t5.gif

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ù)僅僅在主核與從核之間建立雙向連接,。主核首先進行整個粒子群的初始化,主要包括隨機產生粒子的位置和速度,,計算出每個粒子的適應度值作為局部最優(yōu)解,求出對應的全局最優(yōu)解等任務,。主核在完成初始化工作后,,將數(shù)據(jù)分為8份,通過MesssageQ_put()函數(shù)將每個核對應的數(shù)據(jù)的地址發(fā)送到對應的核,,并啟動從核進行相應的處理,。之后所有的核進行循環(huán)迭代處理,實現(xiàn)算法對應的進化尋優(yōu)處理,。同時判斷當前解是否滿足預定的最小適應閾值或達到最大迭代次數(shù),。最后直到從核完成迭代,通知主核完成所有運算,,輸出最優(yōu)解,。

qrs1-t6.gif

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所示,。

qrs1-t7.gif

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所示,。

qrs1-b1.gif

    由表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)的加速比如下:

qrs1-gs4-5.gif

    通過以上分析可以看出,,通過增加并行處理單元個數(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.

此內容為AET網(wǎng)站原創(chuàng),未經授權禁止轉載,。