GPU環(huán)境下加速移動(dòng)對(duì)象可視化更新的方法研究

冒艷純，許建秋

南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106

隨著移動(dòng)通信、智能交通、現(xiàn)代物流等技術(shù)的不斷發(fā)展，與時(shí)間和空間相關(guān)的移動(dòng)對(duì)象數(shù)據(jù)[1]的數(shù)量和種類越來(lái)越多。這些數(shù)據(jù)具有規(guī)模大、更新快等特點(diǎn)。移動(dòng)對(duì)象是用于描述位置隨時(shí)間連續(xù)變化的空間對(duì)象。在數(shù)據(jù)庫(kù)中按照時(shí)間順序存儲(chǔ)其位置記錄，構(gòu)成移動(dòng)對(duì)象時(shí)空運(yùn)動(dòng)軌跡。在移動(dòng)對(duì)象數(shù)據(jù)庫(kù)系統(tǒng)中，索引和查詢處理[2]是數(shù)據(jù)庫(kù)的主要技術(shù)。但是在數(shù)據(jù)庫(kù)系統(tǒng)中的移動(dòng)對(duì)象可視化[3]也同樣重要，數(shù)據(jù)可視化可以將查詢結(jié)果以直觀的、便于可讀的視覺(jué)形式呈現(xiàn)給用戶，方便用戶理解和分析數(shù)據(jù)。

現(xiàn)有的移動(dòng)對(duì)象可視化工具[4-7]應(yīng)用廣泛，但是忽略了移動(dòng)對(duì)象數(shù)據(jù)規(guī)模大和更新頻繁造成的可視化效率問(wèn)題。GPU（graphic processing unit）[8]作為一種擅長(zhǎng)處理大規(guī)模和并行數(shù)據(jù)計(jì)算的設(shè)備[9]，相較于CPU，有強(qiáng)大的計(jì)算能力和高性能的內(nèi)存使用率。移動(dòng)對(duì)象可視化的時(shí)間瓶頸主要在查詢處理上，且GPU的并行可視化主要應(yīng)用在體繪制技術(shù)的并行[10-11]，所以需要應(yīng)用GPU來(lái)加速數(shù)據(jù)的查詢處理能力，提高移動(dòng)對(duì)象可視化效率。R-Tree、KD-Tree是常見(jiàn)的存儲(chǔ)移動(dòng)對(duì)象數(shù)據(jù)的索引，針對(duì)GPU并行架構(gòu)，研究人員提出了一些并行RTree構(gòu)造和查詢處理算法[12-15]，但都存在局限性。傳統(tǒng)的R-Tree索引結(jié)構(gòu)并不適用于GPU，簡(jiǎn)單的線性數(shù)據(jù)結(jié)構(gòu)才能更容易地在CPU主內(nèi)存和GPU設(shè)備內(nèi)存之間傳輸。同時(shí)，由于移動(dòng)對(duì)象查詢結(jié)果集的不確定性，查詢輸出所需的內(nèi)存空間可能相差很大。但是在GPU上沒(méi)有真正的動(dòng)態(tài)內(nèi)存分配，必須靜態(tài)分配緩沖區(qū)，因此造成內(nèi)存的額外開(kāi)銷。

本文主要研究移動(dòng)對(duì)象可視化查詢的效率提升，提高繪制查詢窗口內(nèi)移動(dòng)對(duì)象軌跡的速度?？蓱?yīng)用在移動(dòng)對(duì)象的時(shí)間范圍查詢、最近鄰的連續(xù)時(shí)間查詢等移動(dòng)對(duì)象可視化查詢?？梢暬樵兊臅r(shí)間瓶頸主要在：

（1）移動(dòng)對(duì)象查詢：移動(dòng)對(duì)象更新實(shí)際上是移動(dòng)對(duì)象的索引查詢，由于移動(dòng)對(duì)象數(shù)據(jù)規(guī)模大、查詢復(fù)雜，因此代價(jià)較高。

（2）同一時(shí)間片移動(dòng)對(duì)象的重復(fù)查詢和繪制：現(xiàn)有方法在每次時(shí)間片更新時(shí)，是將整個(gè)查詢時(shí)間窗口內(nèi)的移動(dòng)對(duì)象重新查詢和繪制，這會(huì)造成同一時(shí)間片重復(fù)查詢和繪制，存在不必要的時(shí)間消耗。

針對(duì)問(wèn)題（1），本文提出了GPU環(huán)境下移動(dòng)對(duì)象更新方法，使用一維數(shù)組存儲(chǔ)移動(dòng)對(duì)象數(shù)據(jù)，并且將移動(dòng)對(duì)象串行查詢改為基于CPU/GPU的異構(gòu)并行查詢方法，通過(guò)GPU內(nèi)部大量獨(dú)立的計(jì)算單元，實(shí)現(xiàn)移動(dòng)對(duì)象查詢加速，從而提高查詢效率。該方法簡(jiǎn)單有效，更加適合GPU內(nèi)存，減少了查詢結(jié)果集的不確定性，帶來(lái)的額外內(nèi)存開(kāi)銷。針對(duì)問(wèn)題（2），本文提出了移動(dòng)對(duì)象更新函數(shù)的優(yōu)化方法，通過(guò)比較當(dāng)前可視化查詢的時(shí)間區(qū)間與上一次可視化查詢的時(shí)間區(qū)間，找出需要更新的時(shí)間片，避免整個(gè)時(shí)間區(qū)間的更新。

1 相關(guān)工作

移動(dòng)對(duì)象的可視化是研究移動(dòng)對(duì)象的重要方向之一。國(guó)內(nèi)外許多研究人員已經(jīng)開(kāi)發(fā)了各種移動(dòng)對(duì)象的可視化系統(tǒng)，得到廣泛的應(yīng)用。Ortal等人[4]提出了使用谷歌地圖實(shí)時(shí)展示移動(dòng)對(duì)象的web應(yīng)用程序，該系統(tǒng)可以為移動(dòng)領(lǐng)域的研究人員提供可視化支持，以分析運(yùn)動(dòng)物體的軌跡，評(píng)估預(yù)測(cè)模型。Wang等人[5]提出了一個(gè)交互式的可視化分析系統(tǒng)，來(lái)分析大規(guī)模道路網(wǎng)絡(luò)中的交通擁堵。該系統(tǒng)將行駛軌跡映射到道路網(wǎng)絡(luò)，并計(jì)算道路速度。在估計(jì)各路段的自由流速度后，基于相對(duì)低速的檢測(cè)，自動(dòng)檢測(cè)道路上的交通堵塞事件。Güting等人[6-7]提出的開(kāi)源數(shù)據(jù)庫(kù)SECONDO中實(shí)現(xiàn)了多種基于Java-GUI圖形用戶界面的可視化工具，用于可視化移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡、查詢結(jié)果和數(shù)據(jù)結(jié)構(gòu)等。這些移動(dòng)對(duì)象可視化工具[4-7]雖然應(yīng)用廣泛，但是忽略了移動(dòng)對(duì)象數(shù)據(jù)規(guī)模大和更新頻繁造成的可視化效率問(wèn)題。

GPU[8]作為一種擅長(zhǎng)處理大規(guī)模數(shù)據(jù)和并行數(shù)據(jù)計(jì)算的設(shè)備[9]，相較于CPU，有強(qiáng)大的計(jì)算能力和高性能的內(nèi)存使用率。現(xiàn)有的GPU并行可視化技術(shù)，主要應(yīng)用于體繪制技術(shù)的并行實(shí)現(xiàn)[10]，體繪制是由三維數(shù)據(jù)場(chǎng)產(chǎn)生屏幕上二維圖像的技術(shù)，應(yīng)用于醫(yī)學(xué)影像、氣象氣候?qū)W[11]等復(fù)雜三維圖像繪制領(lǐng)域。本文研究的移動(dòng)對(duì)象可視化，主要是繪制簡(jiǎn)單的點(diǎn)和線段，所以GPU的并行可視化不適用于本文研究的移動(dòng)對(duì)象可視化，并且移動(dòng)對(duì)象可視化更新的時(shí)間瓶頸主要在查詢處理上。因此要提高移動(dòng)對(duì)象可視化效率，需要將GPU運(yùn)用到移動(dòng)對(duì)象的數(shù)據(jù)查詢處理。

現(xiàn)有的移動(dòng)對(duì)象查詢和索引[12-15]都可以在GPU上實(shí)現(xiàn)。Gowanlock等人[12]提出了適用于GPU的友好索引方法，將其應(yīng)用于相似軌跡查詢，該方法與CPU版本相比，速度提高了15.2倍。文獻(xiàn)[13]提出了用于并發(fā)構(gòu)建R-Tree和在GPU上查詢移動(dòng)對(duì)象的算法。但是該方法為每個(gè)R-Tree節(jié)點(diǎn)分配了固定數(shù)量的內(nèi)存，從而造成了設(shè)備全局內(nèi)存的浪費(fèi)和相應(yīng)的性能損失。文獻(xiàn)[14-15]都提出了基于GPU使用簡(jiǎn)單線性陣列構(gòu)建R-Tree的批量加載方法，并對(duì)大型地理空間數(shù)據(jù)進(jìn)行并行空間查詢。簡(jiǎn)單的線性數(shù)據(jù)結(jié)構(gòu)可以很容易地在CPU主內(nèi)存和GPU設(shè)備內(nèi)存之間傳輸，并且不需要序列化。但是在GPU上基于R-Tree的查詢還是會(huì)有局限性，即查詢輸出所需的內(nèi)存空間可能相差很大，由于GPU資源的有限性，無(wú)法在最壞的情況下進(jìn)行內(nèi)存預(yù)分配。并且GPU上沒(méi)有真正的動(dòng)態(tài)內(nèi)存分配，因此必須靜態(tài)分配緩沖區(qū)，從而造成內(nèi)存的額外開(kāi)銷。本文提出的方法，相比較于上述方法，簡(jiǎn)單有效且更加適合GPU內(nèi)存，并減少了查詢結(jié)果集不確定性，而帶來(lái)額外的內(nèi)存開(kāi)銷。

2 基本概念

2.1 移動(dòng)對(duì)象

移動(dòng)對(duì)象在二維平面上移動(dòng)的軌跡實(shí)際上是一條有向曲線，利用定位設(shè)備對(duì)其進(jìn)行采樣可以得到一系列的采樣點(diǎn)，如圖1所示，依照時(shí)間順序?qū)⒉蓸狱c(diǎn)連接起來(lái)，就組成了移動(dòng)對(duì)象的時(shí)空運(yùn)動(dòng)軌跡。

圖1 移動(dòng)對(duì)象軌跡示意圖Fig.1 Moving objects trajectory schematic diagram

定義1（移動(dòng)對(duì)象軌跡）

其中，p表示采樣點(diǎn)，且p=(lng,lat,t)，其中t表示采樣點(diǎn)的時(shí)間信息，lng表示采樣點(diǎn)的經(jīng)度，lat表示采樣點(diǎn)的緯度。兩個(gè)連續(xù)采樣點(diǎn)之間的位置，通過(guò)線性差分的方法獲取。

定義2（時(shí)間區(qū)間）

其中，ts表示時(shí)間區(qū)間T的開(kāi)始時(shí)刻，te表示時(shí)間區(qū)間T的結(jié)束時(shí)刻，且滿足ts＜te。

表1列出了本文中使用的符號(hào)含義。

表1 符號(hào)表示Table 1 Symbol table

2.2 GPU

GPU是一種眾核架構(gòu)處理器，主要用于高度并行計(jì)算，所以其運(yùn)算單元占比很大。GPU的控制和緩存單元主要是負(fù)責(zé)數(shù)據(jù)合并和轉(zhuǎn)發(fā)，因此GPU不擅長(zhǎng)復(fù)雜的邏輯運(yùn)算，但面對(duì)海量且單一的運(yùn)算時(shí)，GPU的速度比CPU快很多。如圖2所示，GPU包含多個(gè)流式多處理器（streaming multiprocessors，SM）。每個(gè)SM包含多個(gè)流處理器（streaming processors，SP）、共享內(nèi)存等部件。線程束是SM中執(zhí)行的基本線程單元。一個(gè)線程束由32個(gè)連續(xù)的線程組成，線程束內(nèi)的線程之間必定是并行執(zhí)行的，并在同一時(shí)間執(zhí)行相同的指令。

圖2 GPU架構(gòu)Fig.2 GPU architecture

3 關(guān)鍵技術(shù)

本章首先介紹現(xiàn)有的移動(dòng)對(duì)象更新方法，然后介紹了GPU環(huán)境下的移動(dòng)對(duì)象更新方法，并提出了基于GPU的移動(dòng)對(duì)象并行查詢算法。最后，介紹了移動(dòng)對(duì)象更新函數(shù)的優(yōu)化方法。

3.1 現(xiàn)有更新函數(shù)

本文主要研究移動(dòng)對(duì)象查詢可視化的效率提升，提高繪制查詢窗口內(nèi)移動(dòng)對(duì)象軌跡的速度。例如在基于時(shí)間范圍的可視化查詢時(shí)，用戶改變查詢的時(shí)間范圍，系統(tǒng)就需要更新對(duì)應(yīng)的可視化內(nèi)容。開(kāi)源數(shù)據(jù)庫(kù)SECONDO[6-7]中的移動(dòng)對(duì)象更新函數(shù)如算法1所示。

算法1首先判斷移動(dòng)對(duì)象軌跡是否在可視化查詢時(shí)間區(qū)間內(nèi)（行2）。然后，對(duì)于在可視化查詢時(shí)間區(qū)間內(nèi)的移動(dòng)對(duì)象，按秒數(shù)遞增，for循環(huán)查詢時(shí)間區(qū)間內(nèi)T的時(shí)間點(diǎn)t，調(diào)用getCTIndex()函數(shù)用二分法查找對(duì)應(yīng)時(shí)間點(diǎn)t的移動(dòng)對(duì)象索引（行7）。然后，通過(guò)索引定位到該時(shí)間點(diǎn)t移動(dòng)對(duì)象對(duì)應(yīng)的坐標(biāo)（行6）。算法1的時(shí)間瓶頸主要在同一時(shí)間片移動(dòng)對(duì)象的重復(fù)查詢和繪制（行3）和移動(dòng)對(duì)象查詢的時(shí)間消耗（行4）。

3.2 GPU環(huán)境下的移動(dòng)對(duì)象更新方法

在GPU基礎(chǔ)上發(fā)展起來(lái)的計(jì)算統(tǒng)一設(shè)備架構(gòu)[16]（compute unified device architecture，CUDA），支持C、C++等多種編程語(yǔ)言。CUDA的高性能計(jì)算能力，是通過(guò)CPU與GPU的異步執(zhí)行來(lái)實(shí)現(xiàn)的。在CUDA模型中，通常將CPU稱作主機(jī)端，GPU稱作設(shè)備端。數(shù)據(jù)初始化、內(nèi)存分配、數(shù)據(jù)拷貝和啟動(dòng)核函數(shù)等串行任務(wù)在主機(jī)端進(jìn)行，設(shè)備端負(fù)責(zé)處理高度線程化的并行任務(wù)，又稱為核函數(shù)。

由算法1可知移動(dòng)對(duì)象可視化更新的時(shí)間消耗主要在移動(dòng)對(duì)象的串行索引查詢，因此為了提高移動(dòng)對(duì)象可視化效率，提出了GPU環(huán)境下的移動(dòng)對(duì)象更新方法，將移動(dòng)對(duì)象更新函數(shù)中的串行索引查詢方法改為基于GPU的并行查詢方法，流程圖如圖3所示。

圖3 基于GPU的移動(dòng)對(duì)象更新流程圖Fig.3 Moving objects updating flow chart based on CUDA

由2.1節(jié)可知，移動(dòng)對(duì)象軌跡數(shù)據(jù)由一組采樣點(diǎn)構(gòu)成，每個(gè)采樣點(diǎn)包括時(shí)間和空間信息。數(shù)據(jù)預(yù)處理是將移動(dòng)對(duì)象數(shù)據(jù)的時(shí)間信息提取出來(lái)，存放在一維數(shù)組中，如圖4所示，時(shí)間數(shù)據(jù)和擁有該時(shí)間數(shù)據(jù)的采樣點(diǎn)具有相同的索引（數(shù)組下標(biāo)），數(shù)據(jù)傳輸時(shí)，僅把時(shí)間數(shù)據(jù)從CPU拷貝到GPU。即將數(shù)據(jù)變成簡(jiǎn)單的一維數(shù)組，使得數(shù)據(jù)更容易在CPU內(nèi)存和GPU內(nèi)存之間傳輸。

圖4 移動(dòng)對(duì)象數(shù)據(jù)Fig.4 Moving objects data

并行查詢區(qū)間的大小決定了查詢集的大小。每個(gè)移動(dòng)對(duì)象有不同的時(shí)間區(qū)間Ttraj，查詢時(shí)間區(qū)間為T，則并行查詢的時(shí)間區(qū)間TP=Ttraj∩T，對(duì)應(yīng)的時(shí)間點(diǎn)為{t1,t2,…,tn}(TP.ts≤t1＜ti＜tn≤TP.te)，每個(gè)時(shí)間點(diǎn)ti間隔1 s。按時(shí)間點(diǎn)ti分割成N個(gè)查詢?nèi)蝿?wù)，一個(gè)查詢?nèi)蝿?wù)返回一個(gè)移動(dòng)對(duì)象的索引，則查詢集大小為N。

內(nèi)存分配和數(shù)據(jù)拷貝完成后，主機(jī)端啟動(dòng)核函數(shù)，將需要執(zhí)行的N個(gè)查詢?nèi)蝿?wù)交給設(shè)備端處理。當(dāng)核函數(shù)映射到GPU后，會(huì)被分配到網(wǎng)格上，網(wǎng)格中有多個(gè)線程塊，每個(gè)線程塊由多個(gè)線程構(gòu)成，并在同一個(gè)多處理器上運(yùn)行。單個(gè)線程處理一個(gè)獨(dú)立的時(shí)間點(diǎn)查詢?nèi)蝿?wù)，N個(gè)查詢?nèi)蝿?wù)并行執(zhí)行結(jié)束后，設(shè)備端返回查詢集。再根據(jù)查找集內(nèi)的索引，得到移動(dòng)對(duì)象對(duì)應(yīng)的位置坐標(biāo)，將所有坐標(biāo)點(diǎn)連接構(gòu)成查詢范圍內(nèi)的移動(dòng)對(duì)象軌跡。移動(dòng)對(duì)象并行索引查詢?nèi)缢惴?所示。

算法2基于GPU的移動(dòng)對(duì)象并行查詢算法

算法2中，首先獲取對(duì)應(yīng)的線程索引（行1），并且一個(gè)線程索引對(duì)應(yīng)一個(gè)時(shí)間點(diǎn)t的查詢?nèi)蝿?wù)。然后，運(yùn)用二分法查找算法，查找對(duì)應(yīng)時(shí)間點(diǎn)t的移動(dòng)對(duì)象索引（行2～行17）。最后，將查找到的索引存放在索引數(shù)組中（行18）。

3.3 優(yōu)化更新函數(shù)

在移動(dòng)對(duì)象可視化查詢時(shí)，移動(dòng)對(duì)象的更新函數(shù)是將查找的整個(gè)時(shí)間區(qū)間內(nèi)的移動(dòng)對(duì)象軌跡全部更新，這會(huì)造成同一時(shí)間片的重復(fù)更新。所以，提出了優(yōu)化更新函數(shù)的方法。

首先，判斷需要更新的時(shí)間片。如圖5所示，當(dāng)上一次可視化查詢的時(shí)間區(qū)間T1與當(dāng)前可視化查詢的時(shí)間區(qū)間T2相交時(shí)，比較T1和T2的重疊區(qū)間，以此分情況討論。然后，根據(jù)找出的需要更新的時(shí)間區(qū)間，對(duì)移動(dòng)對(duì)象進(jìn)行相應(yīng)的可視化更新操作。

圖5 更新函數(shù)優(yōu)化方法Fig.5 Optimization method of update function

情況1當(dāng)T2.ts＜T1.ts且T2.te＜T1.te時(shí)，需要更新的時(shí)間區(qū)間為[T2.ts,T1.ts]。

情況2分兩種情況。（1）當(dāng)T2.ts＞T1.ts且T2.te＜T1.te時(shí)，T2的整個(gè)時(shí)間區(qū)間都在T1的時(shí)間區(qū)間內(nèi)，所以沒(méi)有需要更新的時(shí)間片。（2）當(dāng)T2.ts＜T1.ts且T2.te＞T1.te時(shí)，需要更新時(shí)間區(qū)間為[T2.ts,T1.ts]和[T1.te,T2.te]。

情況3當(dāng)T2.ts＞T1.ts且T2.te＞T1.te時(shí)，則需更新的時(shí)間區(qū)間為[T1.te,T2.te]。

算法1第3行的for循環(huán)查找的時(shí)間區(qū)間T，替換為上述情況討論的需要更新的時(shí)間區(qū)間。

引理更新函數(shù)優(yōu)化后的時(shí)間復(fù)雜度為O(n×cm)(c∈（0，1]）。

證明給定移動(dòng)對(duì)象數(shù)據(jù)的大小為n，可視化查詢時(shí)間區(qū)間的大小為m，臨近的兩次可視化查詢時(shí)間區(qū)間的重疊率為w,c=1-w,w∈[0,1),c∈(0,1]。對(duì)于原有的移動(dòng)對(duì)象更新函數(shù)，首先遍歷移動(dòng)對(duì)象數(shù)據(jù)集，判斷移動(dòng)對(duì)象軌跡是否在可視化查詢時(shí)間區(qū)間內(nèi)，該操作時(shí)間復(fù)雜度為O(n)。然后，對(duì)于在時(shí)間區(qū)間內(nèi)的移動(dòng)對(duì)象，查找其在查詢時(shí)間區(qū)間內(nèi)的索引，該操作的時(shí)間復(fù)雜度為O(m)。所以，移動(dòng)對(duì)象更新函數(shù)的時(shí)間復(fù)雜度為O(n×m)。優(yōu)化后的更新函數(shù)，縮小了移動(dòng)對(duì)象更新的時(shí)間區(qū)間，查詢的時(shí)間區(qū)間由臨近的兩次可視化查詢時(shí)間區(qū)間的重疊范圍決定。當(dāng)臨近的兩次可視化查詢時(shí)間區(qū)間重疊率為w，則需要更新的時(shí)間區(qū)間大小為cm(c=1-w)。因此優(yōu)化后的更新函數(shù)時(shí)間復(fù)雜度為O(n×cm)(c∈(0,1])。

4 實(shí)驗(yàn)評(píng)估

本文實(shí)驗(yàn)CPU采用Intel?Core?i7-5500@2.4 GHz，內(nèi) 存8 GB，4核；GPU采用NVIDIA公司的GeForce GTX 1660 Ti，支持CUDA 10.0的驅(qū)動(dòng)版本，顯存容量為6 GB；操作系統(tǒng)為Ubuntu 14.04；實(shí)驗(yàn)代碼使用CUDA C編寫。

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)使用合成數(shù)據(jù)集和真實(shí)出租車軌跡數(shù)據(jù)集，數(shù)據(jù)集信息如表2所示。其中Cabs_Data為舊金山真實(shí)出租車數(shù)據(jù)集[17]，{D1，D2，D3，D4，D5，D6，D7}為Brinkhoff[18]軌跡生成器生成的不同規(guī)模的合成數(shù)據(jù)集。

表2 數(shù)據(jù)集Table 2 Dataset

4.2 實(shí)驗(yàn)結(jié)果

4.2.1 查詢性能對(duì)比

R-Tree是最常見(jiàn)的存儲(chǔ)移動(dòng)對(duì)象數(shù)據(jù)的索引，有較好的查詢性能。移動(dòng)對(duì)象更新時(shí)間消耗主要在是移動(dòng)對(duì)象的索引查詢，因此本小節(jié)實(shí)驗(yàn)對(duì)比了3種查詢方法：（1）CPU上的R-Tree查詢；（2）GPU上的R-Tree查詢；（3）CPU上更新函數(shù)中的串行索引查詢。將這3種查詢方法分別記作CPU_R-Tree、GPU_R-Tree、CPU_Serial。本文提出的方法記作GPU_Parallel，是將移動(dòng)對(duì)象更新函數(shù)中的串行索引查詢方法改為基于GPU的并行查詢方法。

實(shí)驗(yàn)數(shù)據(jù)使用不同規(guī)模的合成數(shù)據(jù)集，對(duì)不同大小的數(shù)據(jù)集和時(shí)間范圍分別使用CPU_R-Tree、GPU_RTree、CPU_Serial、GPU_Parallel這4種方法運(yùn)行測(cè)試，數(shù)據(jù)大小從400萬(wàn)條遞增到1 000萬(wàn)條，查詢時(shí)間范圍從3小時(shí)遞增到16小時(shí)。為了減少實(shí)驗(yàn)誤差，每種規(guī)格的數(shù)據(jù)均運(yùn)行10次，再取平均值。

在處理數(shù)據(jù)規(guī)模為1 000萬(wàn)條時(shí)，比較GPU_Parallel查詢方法和其他3種查詢方法在不同時(shí)間范圍上的查詢性能，如圖6所示。

圖6 時(shí)間范圍對(duì)查詢性能的影響Fig.6 Effect of time ranges on query performance

主機(jī)和設(shè)備的數(shù)據(jù)傳輸消耗的時(shí)間會(huì)影響整個(gè)程序的效率，經(jīng)測(cè)試本實(shí)驗(yàn)使用的GPU設(shè)備的數(shù)據(jù)傳輸時(shí)間大約占整個(gè)GPU運(yùn)行時(shí)間的23%。所以只有當(dāng)計(jì)算數(shù)據(jù)足夠大時(shí)，才能顯示出GPU的并行計(jì)算的優(yōu)勢(shì)。因此在圖6（a）中，當(dāng)可視化查詢時(shí)間區(qū)間只有3個(gè)小時(shí)，數(shù)據(jù)傳輸時(shí)間大約為76 ms，使得GPU_Parallel運(yùn)行時(shí)間大于CPU_Serial的運(yùn)行時(shí)間，加速比為0.94。

為了使實(shí)驗(yàn)效果明顯，在不同規(guī)模的數(shù)據(jù)集上的比較測(cè)試，查詢時(shí)間范圍設(shè)置為16小時(shí)，比較GPU_Parallel查詢方法和其他3種查詢方法在不同數(shù)據(jù)規(guī)模上的查詢性能，如圖7所示。

圖7 數(shù)據(jù)規(guī)模對(duì)查詢性能的影響Fig.7 Effect of data sizes on query performance

從圖6和圖7中的結(jié)果可以看出，隨著查詢的數(shù)據(jù)規(guī)模和時(shí)間范圍的遞增，CPU_R-Tree和CPU_Serial方法的運(yùn)行時(shí)間快速增長(zhǎng)，而GPU_R-Tree和GPU_Parallel方法的運(yùn)行時(shí)間變化不大。雖然GPU_R-Tree方法與GPU_Parallel方法在不同時(shí)間范圍和數(shù)據(jù)規(guī)模上運(yùn)行時(shí)間相差不大，但是GPU_R-Tree方法還有構(gòu)建R-Tree的時(shí)間消耗，且其查詢集不確定，必須靜態(tài)分配緩沖區(qū)，這會(huì)造成內(nèi)存的額外開(kāi)銷。因此GPU_Parallel方法更優(yōu)，與其他查詢方法相比，加速比最高可達(dá)18.48。

4.2.2 優(yōu)化更新函數(shù)

本小節(jié)實(shí)驗(yàn)數(shù)據(jù)使用Cabs_Data數(shù)據(jù)集，用加速效率作為衡量算法性能提升的指標(biāo)，加速效率越大表明實(shí)驗(yàn)效果越好，加速效率S的定義如公式（1）所示：

其中，TO表示現(xiàn)有更新函數(shù)可視化查詢時(shí)間，TN表示優(yōu)化后的更新函數(shù)可視化查詢時(shí)間。

實(shí)驗(yàn)測(cè)試發(fā)現(xiàn)，如圖8所示，加速效率與鄰近的兩次可視化查詢時(shí)間片段的重疊范圍有關(guān)。

圖8 加速效率Fig.8 Acceleration efficiency

如果重疊范圍是100%，例如上一次時(shí)間區(qū)間是[7：00，8：00]，當(dāng)前查詢時(shí)間范圍是[7：00，7：30]，那么查詢時(shí)間為2 ms，可忽略不計(jì)。如果兩次時(shí)間范圍有交叉，例如上一次的查詢時(shí)間范圍是[7：00，7：30]，當(dāng)前的查詢時(shí)間范圍是[7：00，7：50]，重疊范圍為60%。只需要更新[7：30，7：50]這20 min內(nèi)的移動(dòng)對(duì)象，時(shí)間消耗就從1 000 ms變成418 ms，速度提升了2.5倍。但是如果兩次查詢時(shí)間沒(méi)有交叉，則沒(méi)有顯著效果。因此，兩次查詢時(shí)間，重疊范圍越大，查詢時(shí)間消耗就越小，加速效率就越高。當(dāng)臨近的兩次可視化查詢時(shí)間區(qū)間完全重疊時(shí)，加速效率接近100%。

5 結(jié)束語(yǔ)

針對(duì)大規(guī)模移動(dòng)對(duì)象數(shù)據(jù)可視化效率問(wèn)題，本文提出了GPU環(huán)境下的移動(dòng)對(duì)象更新方法和優(yōu)化移動(dòng)對(duì)象的更新函數(shù)。通過(guò)GPU加速移動(dòng)對(duì)象查詢，以及比較臨近的兩次可視化查詢時(shí)間區(qū)間的重疊范圍，避免相同時(shí)間片的重復(fù)更新，來(lái)提高可視化效率。實(shí)驗(yàn)表明，與CPU上的R-Tree查詢、GPU上的R-Tree查詢和CPU上更新函數(shù)中的串行索引查詢方法相比，本文所提方法具有較好的查詢性能，加速比最高可達(dá)18.48。更新函數(shù)優(yōu)化后，當(dāng)臨近的兩次可視化查詢時(shí)間區(qū)間重疊范圍越大，加速效果越明顯，當(dāng)臨近的兩次可視化查詢時(shí)間區(qū)間完全重疊時(shí)，加速效率接近100%。下一步的工作考慮優(yōu)化GPU的數(shù)據(jù)傳輸，采用異步流來(lái)縮短數(shù)據(jù)傳輸時(shí)間，以獲得更高的加速比。