基于GPU的大規(guī)模無人機(jī)編隊(duì)控制并行仿真方法*

李文光,王 強(qiáng),曹 嚴(yán)

(北京理工大學(xué)宇航學(xué)院, 北京 100081)

0 引言

相比于單個無人機(jī),多無人機(jī)作戰(zhàn)具有顯著的優(yōu)勢,比如作戰(zhàn)半徑大、偵查范圍廣等,因此受到很多學(xué)者的關(guān)注,成為研究的熱點(diǎn)[1]。編隊(duì)控制算法是多無人機(jī)協(xié)同作戰(zhàn)的一項(xiàng)關(guān)鍵技術(shù),基于一致性的協(xié)同編隊(duì)控制算法是眾多編隊(duì)控制算法的一種,也是一種典型的分布式算法,與傳統(tǒng)的集中式算法相比,具有通信與控制結(jié)構(gòu)靈活、無人機(jī)規(guī)模不受限制等優(yōu)點(diǎn),因此在編隊(duì)控制問題中具有重要的應(yīng)用[2]。

仿真為算法的可行性驗(yàn)證提供了良好的手段。但是當(dāng)仿真模型規(guī)模較大時,仿真耗時問題相對突出,其成為制約仿真發(fā)展的重要因素。為提高仿真效率,并行仿真憑借其高效、可重用等特點(diǎn)越來越多地受到青睞[3]。并行仿真的主要任務(wù)是將仿真目標(biāo)分解為多個子目標(biāo)并將其分布在不同處理機(jī)上同時仿真,從而提高仿真的整體效率。在大規(guī)模的無人機(jī)編隊(duì)仿真中,由于無人機(jī)數(shù)量龐大,同樣會面臨仿真耗時長的問題?；诖?文中研究了一種并行仿真方法,并充分利用GPU強(qiáng)大的計(jì)算能力和高效的并行性以提高仿真效率。

1 基于一致性的協(xié)同控制建模

無人機(jī)的運(yùn)動學(xué)方程為：

(1)

式中：xi(t)為無人機(jī)的位置向量;vi(t)為無人機(jī)的速度向量；ui(t)為無人機(jī)的控制向量；N為無人機(jī)數(shù)量。

(2)

(3)

ui(t)=ui-form(t)+ui-vel(t)

(4)

根據(jù)個體控制律式,可得系統(tǒng)的控制向量u(t)：

(5)

式中：n為無人機(jī)模型維度,L為系統(tǒng)的Laplace矩陣,E與期望的編隊(duì)隊(duì)形相關(guān),具體定義如下:

(6)

(7)

Li=[li1,li2,…,liN]

(8)

(9)

整理可得閉環(huán)系統(tǒng)的狀態(tài)方程：

(10)

2 復(fù)雜系統(tǒng)的并行仿真方法

并行仿真的第一步是將整個模型拆分為多個子模型以減小模型的規(guī)模。編隊(duì)控制模型是一個連續(xù)時間模型,其一般形式如式(11)所示：

(11)

而f=[f1,f2,…,fN]T為狀態(tài)轉(zhuǎn)移矩陣,x=[x1,x2,…,xN]T為狀態(tài)向量。

連續(xù)時間模型的分割實(shí)際上就是將式(11)中的N個等式方程劃分為M組,每組中的全部狀態(tài)變量及其狀態(tài)轉(zhuǎn)移方程即組成了新的子模型Si(i=1,2,…,M)。模型分割要考慮的首要問題是降低子模型間的耦合,因?yàn)轳詈鲜窃斐蓵r延誤差的關(guān)鍵因素。

構(gòu)造N×N階雅可比矩陣,如式(12)：

(12)

圖1 矩陣變換最終結(jié)果示意圖

并行仿真的第二步是將已分割的子模型分布在多個仿真機(jī)上并行求解。由于子模型間存在耦合,需要以合適的通信步長完成子模型間的數(shù)據(jù)通信。通信步長的選取至關(guān)重要,是影響求解誤差的重要因素[4]。

3 GPU體系結(jié)構(gòu)與CUDA

3.1 GPU及其內(nèi)部體系結(jié)構(gòu)

GPU(graphic processing unit)是一種擴(kuò)展的計(jì)算設(shè)備,稱為協(xié)處理器。與CPU相比,GPU的優(yōu)勢體現(xiàn)在其高效的并行性、強(qiáng)大的浮點(diǎn)計(jì)算能力等。

GPU的優(yōu)勢得益于其內(nèi)部體系結(jié)構(gòu),GPU有多種架構(gòu),比如NVIDIA公司的Tesla、Fermi、Kepler、Maxwell、Pascal等等,不同GPU架構(gòu)的內(nèi)部體系結(jié)構(gòu)略有差別[5]。以Fermi為例,其內(nèi)部體系結(jié)構(gòu)簡化圖如圖2所示。

圖2 Fermi架構(gòu)GPU內(nèi)部體系結(jié)構(gòu)

圖2包含了幾個GPU中非常重要的結(jié)構(gòu),分別是：

1)Core：流處理器,也稱為SP(streaming processor)。是GPU中最基本的計(jì)算單元,能單獨(dú)完成雙精度運(yùn)算和32位整數(shù)運(yùn)算。

2)寄存器：32位寄存器,是每個線程私有的,用于存儲局部變量。

3)共享存儲器：用于存儲共享變量。與寄存器相比,共享存儲器中的數(shù)據(jù)是一個線程塊中所有線程共享的,但訪問速度較慢。

4)線程調(diào)度器：用于線程調(diào)度。

5)SM：多核流處理器。一個GPU中包含一個或多個SM,一個SM通常包含線程調(diào)度器、共享存儲器、多個SP以及上萬個寄存器。

6)全局存儲器：在某種意義上等同于GPU的顯存,一個kernel函數(shù)中所有線程都能訪問,存儲空間大,但訪問速度最慢。

雖然每個SM中有數(shù)以萬計(jì)的SP,但并不是所有的SP都同時被調(diào)度。warp是SM中的線程調(diào)度單元,每個warp包含連續(xù)的32個線程,物理上占用32個SP用于計(jì)算。SM在任一時刻按照單指令多數(shù)據(jù)模式通過線程調(diào)度器執(zhí)行一個warp中的所有線程,也就是說,同一個warp中的32個線程同時執(zhí)行同一條指令,但分別處理各自的數(shù)據(jù)。

3.2 CUDA

CUDA是NVIDIA公司推出的編程模型,為用戶提供簡單的接口以實(shí)現(xiàn)CPU和GPU異構(gòu)系統(tǒng)開發(fā)。

CUDA編程模型中引入主機(jī)端(CPU)和設(shè)備端(GPU)的概念,一個完整的CUDA程序包括主機(jī)端和設(shè)備端兩部分代碼。主機(jī)端代碼在CPU上執(zhí)行；設(shè)備端代碼又稱為kernel函數(shù),在GPU上執(zhí)行。

啟動kernel函數(shù)時需要指定線程網(wǎng)格劃分,之后CUDA運(yùn)行時系統(tǒng)生成一個兩級結(jié)構(gòu)的線程網(wǎng)格：一個網(wǎng)格由多個線程塊組成,每個線程塊又由多個線程組成。所有線程執(zhí)行同一個kernel函數(shù),每個線程在運(yùn)行時在物理上占用一個SP和多個寄存器(寄存器占用數(shù)量跟kernel函數(shù)中代碼相關(guān)),因此,GPU設(shè)備對kernel函數(shù)的網(wǎng)格劃分是有數(shù)量限定的[6]。

此外,CUDA提供了一系列函數(shù)用于操作和管理GPU設(shè)備。比如數(shù)據(jù)傳輸函數(shù)cudaMemcpy (),用于完成CPU與GPU間數(shù)據(jù)的傳輸；線程管理函數(shù)cudaDeviceSynchronize(),用于CPU和GPU間的同步等等[5]。

4 仿真設(shè)計(jì)與驗(yàn)證

仿真實(shí)驗(yàn)所用計(jì)算機(jī)的CPU為Inter core i7,頻率3.4 GHz,內(nèi)存8 GB；GPU為Fermi體系結(jié)構(gòu),SM數(shù)量為1,Core數(shù)量為48,寄存器數(shù)量為32 768個。

4.1 模型分割

首先對模型進(jìn)行分割。系統(tǒng)的雅克比矩陣即為式(10)中矩陣A,計(jì)算可得系統(tǒng)Laplace矩陣如式(13)所示：

(13)

將式(13)代入矩陣A,可以看出,每架無人機(jī)的位置向量和速度向量之間存在耦合關(guān)系；不同無人機(jī)之間一定存在且只存在與相連兩架無人機(jī)的耦合。因此,同一個無人機(jī)模型的所有狀態(tài)變量應(yīng)通過行列置換作為一個整體,不同無人機(jī)模型按位置順序排列。此時,在任一位置將模型分割,分割位置相連兩無人機(jī)模型間的耦合即為分開后兩模型間的耦合,子模型間的耦合最小?？紤]到負(fù)載均衡和實(shí)驗(yàn)設(shè)備的限制,將整個模型拆分為5個子模型,每個子模型包含連續(xù)的200架無人機(jī)模型。

每個子模型定義如下：

(14)

4.2 CUDA程序設(shè)計(jì)與優(yōu)化

求解式(14)所示的子模型,設(shè)計(jì)的CUDA程序偽代碼如圖3所示。其中,kernel函數(shù)實(shí)現(xiàn)的功能是迭代一個仿真步長。子模型的求解采用Euler法,因此kernel函數(shù)的具體實(shí)現(xiàn)是計(jì)算ξi=ξi+h(Aiξi(t)+Bi+ui)。在該kernel函數(shù)中,網(wǎng)格劃分為1×200,每個線程求解不同無人機(jī)的位置狀態(tài)量和速度狀態(tài)量。

圖3 子模型求解CUDA偽代碼

GPU中,當(dāng)一個warp中的線程訪問全局存儲器的連續(xù)地址時,這些線程的訪問請求會被合并成對連續(xù)單元的合并訪問,以提高數(shù)據(jù)讀取速度。基于此,考慮對上述程序優(yōu)化。在kernel函數(shù)中,每個線程求解時需要獲取系數(shù)矩陣A和狀態(tài)向量ξ的數(shù)據(jù)。在一個warp中,32個線程同時從全局存儲器中獲取矩陣A的同列不同行的元素,如圖4中虛線框所示,此時每個線程同時從矩陣A中讀取的元素是不連續(xù)的。

圖4 優(yōu)化前訪問矩陣元素示意圖

考慮將矩陣A轉(zhuǎn)置后再復(fù)制到GPU存儲器中。這時,kernel函數(shù)在計(jì)算矩陣相乘時如圖5所示,同一warp中不同線程訪問的是連續(xù)的元素。

將設(shè)計(jì)的CUDA程序分布到不同工作站上求解。不同工作站間的通信采用集中式通信：由另外一臺計(jì)算機(jī)作為服務(wù)器,用于接受源節(jié)點(diǎn)的數(shù)據(jù)并發(fā)送到目標(biāo)節(jié)點(diǎn),并且集中控制通信步長,同步子模型的仿真時鐘。仿真實(shí)驗(yàn)分為三組：第一組完全在CPU下求解；第二組采用未優(yōu)化的CUDA程序求解子模型；第三組采用優(yōu)化后的CUDA程序求解子模型。三組仿真耗時情況如圖6所示。

圖5 優(yōu)化后訪問矩陣元素示意圖

圖6 CPU、GPU仿真耗時對比圖

圖6體現(xiàn)出相比CPU,GPU在求解這一類問題上更加高效,而且隨著無人機(jī)規(guī)模的增大,其加速效果更加顯著。同時也體現(xiàn)出經(jīng)過優(yōu)化后的CUDA程序,其效率有了明顯的改善。

4.3 通信步長對誤差和加速比的影響

通信步長是影響誤差與仿真耗時的關(guān)鍵因素。為探究通信步長對誤差和仿真耗時的實(shí)際影響,并為實(shí)際仿真應(yīng)用中通信步長的選取提供依據(jù),設(shè)計(jì)了本節(jié)仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖7和圖8所示,縱坐標(biāo)分別為相對誤差和加速比,橫坐標(biāo)為通信步長與仿真步長的比值,即X=H/h；相對誤差是指GPU下并行仿真結(jié)果相對CPU下串行仿真結(jié)果的誤差,取所有狀態(tài)量相對誤差的均值作為觀測值；加速比是指GPU下并行仿真耗時與CPU下串行仿真耗時的比值。

圖7 X與相對誤差關(guān)系圖

由圖7可以看出,X和誤差成正比；由圖8可以看出,X對加速比的影響在X很小時相對較大,隨著X的增大,其對加速比的影響逐漸減小。結(jié)合圖7、圖8可知,當(dāng)X取仿真步長的5～15倍時,具有較好的效果。

圖8 X與加速比關(guān)系圖

5 結(jié)論

從仿真結(jié)果可知,通信步長對求解誤差以及求解效率有顯著的影響,當(dāng)通信步長取仿真步長的5～15倍時,相對誤差僅為0.01～0.02,驗(yàn)證了該并行仿真方法的正確性；加速比達(dá)到15～20,驗(yàn)證了方法的高效性。圖6體現(xiàn)出了GPU在大規(guī)模數(shù)值仿真中的優(yōu)勢,并且實(shí)驗(yàn)所用GPU性能較差,計(jì)算能力(compute capab-ility)僅為2.1,最新的GPU計(jì)算能力能夠達(dá)到7.1,因此GPU在大規(guī)模仿真中有著廣闊的應(yīng)用前景。