趙艷偉 于璐 張寧 劉凱 徐海旭

指控系統(tǒng)作為武器系統(tǒng)裝備的一個(gè)重要組成部分,是整個(gè)武器系統(tǒng)的信息處理中心,也是指揮員了解戰(zhàn)場態(tài)勢、進(jìn)行指揮決策的重要手段.而要在復(fù)雜的多維空間戰(zhàn)場進(jìn)行指揮控制,必須處理極為龐大和繁雜的戰(zhàn)術(shù)信息.其中60%與地理背景密切相關(guān)[1],尤其在野戰(zhàn)過程中,指揮決策對(duì)于地理信息及其相關(guān)地理屬性的依賴性更為突出,地理信息直接影響作戰(zhàn)方案的制定和戰(zhàn)術(shù)思想的落實(shí).通過指控系統(tǒng)的GIS功能,可實(shí)現(xiàn)對(duì)戰(zhàn)場地理空間的實(shí)時(shí)綜合處理和直觀可視化分析,形象表示敵我態(tài)勢,從而輔助指揮員進(jìn)行戰(zhàn)場指揮決策.

在指控系統(tǒng)中,最為常用的GIS功能就是戰(zhàn)場電子地圖的瀏覽與戰(zhàn)場空間查詢,根據(jù)查詢條件,指揮員可以找到一定地理范圍空間內(nèi)的目標(biāo)數(shù)據(jù),例如戰(zhàn)場軍事標(biāo)注點(diǎn)、遠(yuǎn)程分隊(duì)的覆蓋區(qū)域等.

隨著網(wǎng)絡(luò)化、一體化作戰(zhàn)模式的發(fā)展,指控系統(tǒng)需要處理的各類數(shù)據(jù)越來越復(fù)雜,數(shù)據(jù)量越來越龐大,僅地理信息數(shù)據(jù)就能達(dá)到TB級(jí)以上,現(xiàn)有的指控系統(tǒng)在面對(duì)如此密集的計(jì)算任務(wù)時(shí),傳統(tǒng)的處理方式已無法滿足應(yīng)用對(duì)大規(guī)模計(jì)算的實(shí)時(shí)性需求[2].當(dāng)面對(duì)海量戰(zhàn)場空間數(shù)據(jù)的查詢與分析等復(fù)雜處理任務(wù)時(shí),數(shù)據(jù)處理周期通常需要控制在幾百毫秒乃至數(shù)毫秒內(nèi),而傳統(tǒng)基于樹型索引的空間查詢方法,當(dāng)數(shù)據(jù)越來越集中時(shí),空間要素的重疊度也將越來越高,過高的重疊必然導(dǎo)致空間檢索過程中出現(xiàn)冗余路徑,嚴(yán)重影響了檢索效率,現(xiàn)有的GIS空間查詢功能已無法滿足指控實(shí)時(shí)性的需求.

從當(dāng)今計(jì)算機(jī)科學(xué)發(fā)展的前景來看,多機(jī)集群、分布式、并行處理將成為應(yīng)對(duì)大規(guī)模復(fù)雜計(jì)算模式的主流趨勢,鑒于指揮控制系統(tǒng)的軍事應(yīng)用需求及應(yīng)用特點(diǎn),采用并行處理架構(gòu)將成為必然.GPGPU(General Purpose Graphic Processing Unit)憑借其大規(guī)模并行計(jì)算能力和易編程性已成為高性能計(jì)算和科學(xué)計(jì)算應(yīng)用的重要加速手段,并廣泛應(yīng)用于其他通用計(jì)算領(lǐng)域.GPU通用計(jì)算為復(fù)雜性超出CPU解決能力和計(jì)算需求的應(yīng)用,提供了一個(gè)使用較少能耗卻能發(fā)揮更高性能的解決方案[3].

在指控系統(tǒng)對(duì)密集型計(jì)算任務(wù)的實(shí)時(shí)處理需求下以及GPU通用計(jì)算迅猛發(fā)展的背景下,本文提出了一種基于GPGPU的指控系統(tǒng)空間查詢優(yōu)化方法.

本文首先介紹了GPU通用計(jì)算的相關(guān)理念,在此基礎(chǔ)上重點(diǎn)設(shè)計(jì)了一種可應(yīng)用于指控系統(tǒng)GIS分系統(tǒng)的CPU+GPU并行空間查詢方法,并通過實(shí)驗(yàn)數(shù)據(jù)證明了本方法的高效性,為未來實(shí)現(xiàn)GPU通用計(jì)算在軍事領(lǐng)域上的應(yīng)用提供可行的技術(shù)參考.

1 GPU通用計(jì)算

圖形處理器(Graphic Processing Unit,GPU)從誕生之日起就以超越摩爾定律的速度發(fā)展,運(yùn)算能力不斷提升.業(yè)界很多研究者注意到GPU進(jìn)行計(jì)算的潛力,于2003年SIGGRAPH大會(huì)上提出了GPGPU的概念.GPU逐漸從由若干專用的固定功能單元(Fixed Function Unit)組成的專用并行處理器向以通用計(jì)算資源為主,固定功能單元為輔的架構(gòu)轉(zhuǎn)變.GPU無論在浮點(diǎn)運(yùn)算能力上還是存儲(chǔ)帶寬上都遠(yuǎn)遠(yuǎn)超過了同時(shí)期的主流CPU,GPU通用計(jì)算是一片正在被打開的潛力巨大的市場[4].

近幾年,越來越多的學(xué)者開始把對(duì)并行計(jì)算計(jì)算性能的提升關(guān)注重點(diǎn)從CPU轉(zhuǎn)移到GPU上來,GPU內(nèi)部集成了數(shù)百個(gè)并行流處理器,其并行計(jì)算效率比CPU要高很多,而且已經(jīng)有很多學(xué)者和廠商將GPU應(yīng)用于科學(xué)計(jì)算領(lǐng)域,取得了非常好的效果[5].例如猶他州大學(xué)在醫(yī)學(xué)成像領(lǐng)域使用GPU可獲得146倍加速效果;馬里蘭大學(xué)在基因排序領(lǐng)域使用GPU可獲得30倍加速比,除此之外,GPU在分子運(yùn)動(dòng)、視頻轉(zhuǎn)換、量子化學(xué)、線性代數(shù)等領(lǐng)域都有不同程度的性能提升[6].

目前,在國內(nèi),GPU應(yīng)用在軍事指揮控制系統(tǒng)上主要用來處理圖形圖像等傳統(tǒng)問題,針對(duì)計(jì)算密集型的指控信息計(jì)算,尚無成熟的基于CPU+GPU進(jìn)行加速的指控功能的相關(guān)研究.

2 基于GPGPU的并行空間查詢方法

通常,為了提升空間查詢的效率,首先需要為空間數(shù)據(jù)建立索引機(jī)制,其中,樹型索引(R樹、R*樹[7]、R+樹等)是采用最為廣泛的一類索引結(jié)構(gòu).由于樹型索引在空間查詢時(shí)需要大量使用指針及遞歸操作,這樣的操作方式在顯存中是不支持的,在GPU環(huán)境下,傳統(tǒng)的樹型索引并不適用.因此,本文設(shè)計(jì)了一種適用于GPU環(huán)境的并行柵格索引.

另外,為解決由于過濾和精煉過程帶來的CPU與GPU頻繁進(jìn)行數(shù)據(jù)交換的問題,本文在柵格索引基礎(chǔ)上,設(shè)計(jì)了一種CPU與GPU協(xié)同加速空間查詢方法,將傳統(tǒng)的粗糙過濾和精煉兩個(gè)空間查詢步驟進(jìn)行合并,盡可能地最大限度過濾非相關(guān)戰(zhàn)場空間要素,避免了內(nèi)存和顯存的頻繁數(shù)據(jù)交換,提高了空間查詢的整體效率.

2.1 適用于GPU環(huán)境的并行柵格索引的構(gòu)造

為了最大化地利用GPU的多線程機(jī)制,本文考慮采用柵格結(jié)構(gòu)建立空間索引,一方面利于計(jì)算任務(wù)均勻劃分,另一方面可以極大地保證處于激活狀態(tài)的線程塊數(shù)量.

整個(gè)柵格索引渲染過程算法框架如圖1所示.首先,輸入矢量要素信息,該信息包括組成矢量要素的點(diǎn)坐標(biāo),并通過坐標(biāo)轉(zhuǎn)換通道進(jìn)行坐標(biāo)轉(zhuǎn)換,將矢量要素坐標(biāo)精確到亞像素精度.然后進(jìn)入算法核心,該核心包括兩部分,第1部分(圖1中左側(cè)部分)是矢量要素柵格化過程,第2部分(圖1中右側(cè)部分)是要素索引與對(duì)應(yīng)柵格的解析過程.

要素渲染過程分為3步,第1步,提取矢量要素的輪廓信息;第2步,利用柵格控制器,掃描輪廓并計(jì)算填充格網(wǎng)區(qū)域;第3步,按照水平掃描的方式對(duì)填充區(qū)域進(jìn)行跨段或跨單元填充.索引解析過程,通過輸入的矢量要素獲得索引信息,通過索引轉(zhuǎn)換引擎將其映射到對(duì)應(yīng)的柵格單元中,最后與矢量要素柵格化的結(jié)果通過渲染緩存生成柵格索引.

2.2 索引在主機(jī)端與設(shè)備端的傳輸與替換

由于顯存空間的大小受限,因此,對(duì)于大比例尺下的空間圖層要素,其柵格索引無法一次性全部加載到顯存空間中.為了解決這個(gè)問題,需要將柵格索引進(jìn)行瓦片分割.采用預(yù)生成及預(yù)裝配技術(shù),在初始化時(shí),按照顯存內(nèi)分配的索引空間大小將部分瓦片索引預(yù)傳輸?shù)皆O(shè)備端.如果查詢請(qǐng)求的范圍內(nèi)無法獲得有效的顯存柵格索引,則采取瓦片替換策略對(duì)索引進(jìn)行更新.

由于地理空間的連續(xù)性,用戶在查詢某一個(gè)區(qū)域的時(shí)候很可能再訪問其相鄰的區(qū)域,因此,在替換更新時(shí)需要對(duì)相鄰區(qū)域進(jìn)行考慮.若令索引瓦片為TileIndex(i,j),其中i代表索引所在行,j代表索引所在列.則該瓦片的相鄰區(qū)域采用如圖2表示,形式化定義為:

圖1 并行柵格索引生成過程

圖2 領(lǐng)域瓦片范圍

每次訪問顯存內(nèi)的索引瓦片,其對(duì)應(yīng)位置的計(jì)數(shù)器都會(huì)進(jìn)行累加.若當(dāng)前訪問的索引TileIndex(i,j)不在顯存內(nèi),則按照LFU替換策略,利用CUDA并行歸并排序算法統(tǒng)計(jì)訪問頻率,最先移出最少使用的索引瓦片TileIndex(s,t).其中需要多考慮的一個(gè)步驟是,如果TileIndex(s,t)∈?i,j,則不進(jìn)行替換,按照索引訪問頻率選取下一個(gè)待替換的瓦片.

2.3 并行空間查詢算法的設(shè)計(jì)與實(shí)現(xiàn)

利用上述這種適合在GPU環(huán)境下實(shí)現(xiàn)并行空間查詢的柵格索引機(jī)制,這部分主要討論兩類最常用的空間選擇查詢:BBOX范圍選擇查詢和多邊形選擇查詢.這兩種查詢?cè)贕PU設(shè)備端的并行查詢的區(qū)別在于,多邊形選擇查詢需要額外再多計(jì)算一步,即將不規(guī)則的查詢多邊形柵格化,并且在多線程并行計(jì)算時(shí),每個(gè)線程需要多進(jìn)行一次柵格判斷.其余整體算法步驟可按照BBOX范圍選擇查詢來處理.因此,本部分先主要介紹BBOX范圍選擇查詢的具體算法,再對(duì)該算法進(jìn)行擴(kuò)展,從而能處理任意多邊形選擇查詢請(qǐng)求.整體流程如圖3所示.

2.3.1 索引在顯存內(nèi)的存儲(chǔ)模式

考慮到GPU多線程對(duì)顯存空間訪問的特性,索引在設(shè)備端的存儲(chǔ)需要滿足合并訪問的原則.采取的具體方法如圖4所示.

首先,對(duì)于給定的顯存大小,確定待存儲(chǔ)索引的范圍,若假設(shè)包含m行n列瓦片,則應(yīng)存儲(chǔ)的索引集合為然后對(duì)各個(gè)瓦片之間,采用Hilbert曲線的方式進(jìn)行存儲(chǔ),其中指定的瓦片在顯存空間內(nèi)的起始位置可通過(H?code?1)×size快速定位.最后針對(duì)每個(gè)瓦片內(nèi)部,采取行掃描的方式存儲(chǔ),并且保證行寬度為(W1,W2,W3,W4)字長的16的倍數(shù).

采用這樣的方法主要基于兩點(diǎn)考慮:由于相鄰?fù)咂饕趯?shí)際的地理空間上具有相近性,而Hilbert曲線可以將相鄰索引進(jìn)行聚集,由此在各個(gè)瓦片之間極大地保證了空間數(shù)據(jù)良好的局部性,使得在空間查詢時(shí)能夠訪問顯存內(nèi)連續(xù)的一段空間,為合并訪問打下基礎(chǔ).另外對(duì)于每個(gè)瓦片的內(nèi)部,上述方法能使得Half-warp中的16個(gè)線程只經(jīng)過一次傳輸便可以完成整個(gè)Half-warp對(duì)顯存的訪問請(qǐng)求.經(jīng)過上述步驟處理后,顯存空間的瓦片索引既實(shí)現(xiàn)了線性存儲(chǔ),同時(shí)也滿足了合并訪問的原則,從而實(shí)現(xiàn)合并讀取,提高線程對(duì)顯存的訪問效率.

圖3 算法流程

圖4 索引瓦片在顯存內(nèi)的存儲(chǔ)方式

2.3.2 線程塊計(jì)算過程

這個(gè)過程主要計(jì)算參與并行空間查詢的線程塊數(shù)量和每個(gè)塊內(nèi)的線程數(shù)量.其中線程數(shù)量以二維方式指定,且保證每個(gè)塊內(nèi)線程總數(shù)不超過512,設(shè)為TN(32,16).為了保證每個(gè)線程處理一個(gè)柵格單元,需要按照查詢請(qǐng)求的MBR范圍來計(jì)算線程塊數(shù)量.

假設(shè)查詢范圍為Bbox(x1,y1,x2,y2),且每個(gè)索引瓦片的寬為idwidth,高為idheight.那么此范圍覆蓋的瓦片索引集合為SIdx(s,t),其中,

2.3.3 kernel并行查詢過程

根據(jù)BN(bnx,bny)和TN(32,16)的線程啟動(dòng)策略,通過3層偏移關(guān)系可以計(jì)算出線程處理的空間位置.首先,在設(shè)備端并行空間查詢的核函數(shù)中可利用threadIdx內(nèi)建變量,確定當(dāng)前線程在線程塊中的偏移位置,然后再根據(jù)Grid中Block-Dim、BlockIdx內(nèi)建變量計(jì)算出線程在整個(gè)Grid中的全局位置,最后根據(jù)Grid覆蓋的起始瓦片在顯存索引中的偏移來進(jìn)一步確定當(dāng)前線程應(yīng)處理的單元的空間位置.空間位置的確定如圖5所示.

若該空間位置在查詢外包內(nèi),則需要對(duì)柵格進(jìn)行提取.否則,當(dāng)前線程不參與運(yùn)算.對(duì)于Bbox范圍選擇查詢,可按上述方式過濾非相關(guān)線程的計(jì)算;對(duì)于多邊形選擇查詢,需要按照查詢條件的外包進(jìn)行二值柵格化,即多邊形范圍內(nèi)柵格化為1,外包內(nèi)且多邊形外部柵格化為0.線程在并行提取柵格單元時(shí),需與對(duì)應(yīng)位置的查詢條件進(jìn)行柵格運(yùn)算,如圖6所示.

圖5 三層偏移計(jì)算關(guān)系

圖6 不規(guī)則范圍查詢處理情況

顯存內(nèi)對(duì)應(yīng)位置柵格單元的具體提取過程:首先通過上述步驟得到的每個(gè)線程處理的空間位置,計(jì)算出該空間位置所屬的索引瓦片,根據(jù)瓦片Hilbert曲線排序?qū)?yīng)的H-code進(jìn)一步確定該索引在顯存內(nèi)的偏移.由于瓦片內(nèi)部采用行掃描順序存儲(chǔ),因此,只需根據(jù)空間位置在瓦片內(nèi)部的偏移按照行列順序獲取具體的柵格單元.

影響CUDA性能的一個(gè)重要因素是全局存儲(chǔ)器的訪問效率[8],由于在多線程提取索引單元時(shí)需要對(duì)顯存進(jìn)行大量的讀寫,因此,介紹一下本方法在對(duì)全局存儲(chǔ)器讀取進(jìn)行的優(yōu)化,這也是生成柵格索引采用四字節(jié)的原因.在構(gòu)造柵格索引結(jié)構(gòu)時(shí),采用三字節(jié)這種存儲(chǔ)方式對(duì)于中等數(shù)據(jù)量的空間信息來說能夠保存的索引數(shù)據(jù)已經(jīng)足夠,但如果是這樣的話無法保證同一half-warp中的線程訪問顯存的地址對(duì)齊到可合并訪問的段內(nèi),因此,將導(dǎo)致數(shù)據(jù)分為16次串行傳輸.如圖7所示.

圖7 合并訪問方式

由于CUDA支持32 bit字長的合并訪問,第1種情況,索引的(W1,W2,W3)字長無法對(duì)齊到可合并的段內(nèi),造成線程訪問顯存的效率較低.而第2種情況,雖然在存儲(chǔ)時(shí)多了一個(gè)字節(jié),但卻正好滿足全局存儲(chǔ)器內(nèi)存融合訪問模式,索引與合并段一一對(duì)齊,因此,half-warp中16個(gè)線程訪問的數(shù)據(jù)只需進(jìn)行一次傳輸,優(yōu)化了訪問效率.如圖8所示.

圖8 并行排除冗余索引

采取的具體做法是:利用CUDPP[9]的并行歸并算法對(duì)提取的有效索引ID進(jìn)行排序,對(duì)排序后的索引集合使每個(gè)線程分別處理一個(gè)元素,計(jì)算該元素與其前驅(qū)的差值并保存為標(biāo)識(shí)量flag.這樣,flag中不為0的元素位置,對(duì)應(yīng)的索引集合中的矢量要素ID一定是不重復(fù)的.相反,flag中為0的一個(gè)或者連續(xù)一段元素對(duì)應(yīng)的索引ID說明為冗余值,可忽略不計(jì).因此,根據(jù)flag的標(biāo)識(shí)性質(zhì),對(duì)索引集合利用CUDPP compact進(jìn)行并行壓縮,將標(biāo)識(shí)量非0的要素ID前置,最后利用并行Prefix sum方法求得最終ID結(jié)果集,只將該部分集合傳遞回主存中,這樣便可以大大減少傳輸量,提高并行查詢效率.

本文所設(shè)計(jì)的并行空間查詢方法較一般空間查詢的區(qū)別如圖9所示.第1種情況是使用樹型索引的傳統(tǒng)兩步空間查詢,即根據(jù)查詢條件W的MBR,先進(jìn)行空間過濾,篩選出候選集合R1和R2.再通過精煉步驟,對(duì)空間要素進(jìn)行精確檢測,找到查詢結(jié)果為R1.第2種情況是并行柵格查詢方法,只要根據(jù)查詢條件W通過對(duì)柵格索引對(duì)應(yīng)位置的并行提取,便能夠確定查詢結(jié)果集.這種方法合并了原始方法的過濾和精煉兩步,既避免了候選集在顯存與主存中的頻繁傳輸,也避免了精確匹配時(shí)大量的計(jì)算過程.

圖9 傳統(tǒng)空間查詢步驟與本文方法對(duì)比

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)部分主要分為兩個(gè)部分,第1部分主要將本文所述的基于GPGPU的并行空間查詢方法與傳統(tǒng)CPU中的空間查詢做對(duì)比,第2部分主要分析主機(jī)端與設(shè)備端之間數(shù)據(jù)傳輸對(duì)本文算法的整體性能影響.實(shí)驗(yàn)環(huán)境配置如下:CPU處理器采用InteCoreTMi7-9202.67GHz,內(nèi)存為6GB;GPU顯卡采用GeForce GTX 260(192 SP,1.3),顯存為2GB.利用CUDA 4.0[10]工具集在Microsoft Visual Studio 2008進(jìn)行程序開發(fā).

3.1 與CPU方法對(duì)比

這部分實(shí)驗(yàn)的目標(biāo)是測試本方法與采用R*空間索引的CPU中的空間查詢方法,在相同benchmark測試集及相同查詢請(qǐng)求情況下的空間檢索時(shí)間及空間過濾度.測試集主要是針對(duì)點(diǎn)、線、面3類不同類型的地理要素,為保證查詢的公平性及均勻性,空間查詢請(qǐng)求通過隨機(jī)生成,并且每個(gè)測試圖層按照不同的查詢范圍進(jìn)行8組實(shí)驗(yàn)(每組包含500個(gè)查詢請(qǐng)求),查詢范圍則通過與整個(gè)圖層的比例關(guān)系進(jìn)行確定.例如查詢結(jié)果橫坐標(biāo)120表示將原始圖層范圍的1/120作為查詢條件.

對(duì)于稠密的點(diǎn)數(shù)據(jù),雖然本文方法的計(jì)算時(shí)間較R*方法少,但若計(jì)算數(shù)據(jù)傳輸時(shí)間,與CPU中采用R*索引的空間查詢時(shí)間相當(dāng),如圖10所示.

圖10 點(diǎn)圖層查詢結(jié)果

對(duì)于海量密集的線圖層和面圖層來說,本方法在空間查詢時(shí)間方面較CPU中基于R*樹型結(jié)構(gòu)索引的空間查詢具有絕對(duì)優(yōu)勢.由于數(shù)據(jù)量較大,樹型索引的高度將急劇增加,又由于數(shù)據(jù)密集,導(dǎo)致索引中間節(jié)點(diǎn)的MBR重疊度較高,因此,樹型索引在處理這類空間數(shù)據(jù)上效率較低.從圖11中可以看出,對(duì)于每組數(shù)據(jù)采用R*索引的查詢時(shí)間平均超過了1600ms,而本文提出的方法即使計(jì)算數(shù)據(jù)的傳輸時(shí)間也可以控制在50ms左右,此時(shí)數(shù)據(jù)傳輸時(shí)間與CPU中的計(jì)算時(shí)間相比可忽略不計(jì),因此,在本文提出的方法在處理密集線數(shù)據(jù)上可以得到32倍的加速比.同樣的,從圖12中可以看出,由于密集面數(shù)據(jù)具有較高的MBR重疊度,采用R*索引平均需要500ms左右,而本文提出的方法需要50ms左右,其加速比也能達(dá)到10倍左右.

從以上對(duì)不同類型及不同特點(diǎn)空間數(shù)據(jù)的查詢效率對(duì)比分析中,我們可進(jìn)行如下總結(jié):本文提出的基于柵格索引及GPGPU并行架構(gòu)的空間查詢方法適用于處理海量密集的線面類空間數(shù)據(jù),與CPU中的樹型索引方法相比,能達(dá)到量級(jí)的效率提升.對(duì)于傳統(tǒng)CPU中的樹型索引查詢方法,數(shù)據(jù)量越大數(shù)據(jù)越密集,查詢效率越低,而本文提出的方法的查詢效率不受數(shù)據(jù)復(fù)雜度的影響,只受查詢范圍及查詢到的ID集合大小影響.

圖11 線圖層查詢結(jié)果

圖12 線圖層查詢結(jié)果

3.2 kernel性能分析

這部分主要針對(duì)本方法的內(nèi)部執(zhí)行過程中,各個(gè)部分所占的時(shí)間比進(jìn)行測試,意在分析主機(jī)端與設(shè)備端之間數(shù)據(jù)傳輸對(duì)整個(gè)算法的性能影響.我們采用的分析工具為CUDA profiler[11],它是NVIDIA公司在CUDA toolkit中提供的一種可視化工具,其中包含了一系列可以反映應(yīng)用程序中CPU和GPU的活動(dòng)行為的時(shí)間表,同時(shí)CUDA profiler還提供了自動(dòng)分析引擎來幫助用戶迅速確定性能瓶頸位置,從而找到可優(yōu)化的策略.如圖13所示.

通過Summary Plot圖表,我們可以直觀地看到kernel函數(shù)和memory copy在總GPU時(shí)間占用的百分比.不難發(fā)現(xiàn),本文提出的方法窗口查詢的計(jì)算部分占到了整個(gè)kernel時(shí)間的76.21%,而數(shù)據(jù)拷貝只占到了20%左右,因此,可以得出結(jié)論,本文提出的方法中數(shù)據(jù)傳輸部分并未造成性能瓶頸.

4 結(jié)論

圖13 CUDA profiler性能分析

為了滿足指揮控制系統(tǒng)對(duì)戰(zhàn)場空間目標(biāo)的實(shí)時(shí)查詢與直觀展示,本文提出了一種基于GPGPU的并行空間查詢方法.首先,設(shè)計(jì)了一種基于柵格結(jié)構(gòu)的并行空間索引機(jī)制,相比于樹型索引,本文設(shè)計(jì)的索引結(jié)構(gòu)具有更小的空間重疊度,同時(shí)能夠充分利用GPU并行環(huán)境的計(jì)算特點(diǎn),為細(xì)粒度的并行查詢提供了有利的契機(jī).在此并行柵格索引機(jī)制的基礎(chǔ)上,本文提出了一種在GPGPU計(jì)算模式下的并行空間查詢算法.通過與已有的研究成果進(jìn)行試驗(yàn)對(duì)比,在執(zhí)行效率方面,本方法對(duì)于處理海量密集型的空間數(shù)據(jù)具有絕對(duì)的優(yōu)勢,加速比可達(dá)到一個(gè)數(shù)量級(jí).

本文提出的方法可應(yīng)用于各級(jí)指揮控制系統(tǒng)的GIS地理信息分系統(tǒng),可有效提高戰(zhàn)場空間目標(biāo)的檢索效率,滿足毫秒級(jí)空間查詢響應(yīng)時(shí)間要求,為輔助戰(zhàn)場指揮決策起到了關(guān)鍵作用.該方法的研究,也為我軍指揮控制系統(tǒng)采用CPU+GPU異構(gòu)計(jì)算模式進(jìn)行指控功能算法加速提供了一種探索性的嘗試,為促進(jìn)我軍指控系統(tǒng)的跨越式發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ).