GPU環境下加速移動對象可視化更新的方法研究

冒艷純，許建秋

南京航空航天大學 計算機科學與技術學院，南京 211106

隨著移動通信、智能交通、現代物流等技術的不斷發展，與時間和空間相關的移動對象數據[1]的數量和種類越來越多。這些數據具有規模大、更新快等特點。移動對象是用于描述位置隨時間連續變化的空間對象。在數據庫中按照時間順序存儲其位置記錄，構成移動對象時空運動軌跡。在移動對象數據庫系統中，索引和查詢處理[2]是數據庫的主要技術。但是在數據庫系統中的移動對象可視化[3]也同樣重要，數據可視化可以將查詢結果以直觀的、便于可讀的視覺形式呈現給用戶，方便用戶理解和分析數據。

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

本文主要研究移動對象可視化查詢的效率提升，提高繪制查詢窗口內移動對象軌跡的速度。可應用在移動對象的時間范圍查詢、最近鄰的連續時間查詢等移動對象可視化查詢?？梢暬樵兊臅r間瓶頸主要在：

（1）移動對象查詢：移動對象更新實際上是移動對象的索引查詢，由于移動對象數據規模大、查詢復雜，因此代價較高。

（2）同一時間片移動對象的重復查詢和繪制：現有方法在每次時間片更新時，是將整個查詢時間窗口內的移動對象重新查詢和繪制，這會造成同一時間片重復查詢和繪制，存在不必要的時間消耗。

針對問題（1），本文提出了GPU環境下移動對象更新方法，使用一維數組存儲移動對象數據，并且將移動對象串行查詢改為基于CPU/GPU的異構并行查詢方法，通過GPU內部大量獨立的計算單元，實現移動對象查詢加速，從而提高查詢效率。該方法簡單有效，更加適合GPU內存，減少了查詢結果集的不確定性，帶來的額外內存開銷。針對問題（2），本文提出了移動對象更新函數的優化方法，通過比較當前可視化查詢的時間區間與上一次可視化查詢的時間區間，找出需要更新的時間片，避免整個時間區間的更新。

1 相關工作

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

GPU[8]作為一種擅長處理大規模數據和并行數據計算的設備[9]，相較于CPU，有強大的計算能力和高性能的內存使用率?，F有的GPU并行可視化技術，主要應用于體繪制技術的并行實現[10]，體繪制是由三維數據場產生屏幕上二維圖像的技術，應用于醫學影像、氣象氣候學[11]等復雜三維圖像繪制領域。本文研究的移動對象可視化，主要是繪制簡單的點和線段，所以GPU的并行可視化不適用于本文研究的移動對象可視化，并且移動對象可視化更新的時間瓶頸主要在查詢處理上。因此要提高移動對象可視化效率，需要將GPU運用到移動對象的數據查詢處理。

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

2 基本概念

2.1 移動對象

移動對象在二維平面上移動的軌跡實際上是一條有向曲線，利用定位設備對其進行采樣可以得到一系列的采樣點，如圖1所示，依照時間順序將采樣點連接起來，就組成了移動對象的時空運動軌跡。

圖1 移動對象軌跡示意圖Fig.1 Moving objects trajectory schematic diagram

定義1（移動對象軌跡）

其中，p表示采樣點，且p=(lng,lat,t)，其中t表示采樣點的時間信息，lng表示采樣點的經度，lat表示采樣點的緯度。兩個連續采樣點之間的位置，通過線性差分的方法獲取。

定義2（時間區間）

其中，ts表示時間區間T的開始時刻，te表示時間區間T的結束時刻，且滿足ts＜te。

表1列出了本文中使用的符號含義。

表1 符號表示Table 1 Symbol table

2.2 GPU

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

圖2 GPU架構Fig.2 GPU architecture

3 關鍵技術

本章首先介紹現有的移動對象更新方法，然后介紹了GPU環境下的移動對象更新方法，并提出了基于GPU的移動對象并行查詢算法。最后，介紹了移動對象更新函數的優化方法。

3.1 現有更新函數

本文主要研究移動對象查詢可視化的效率提升，提高繪制查詢窗口內移動對象軌跡的速度。例如在基于時間范圍的可視化查詢時，用戶改變查詢的時間范圍，系統就需要更新對應的可視化內容。開源數據庫SECONDO[6-7]中的移動對象更新函數如算法1所示。

算法1首先判斷移動對象軌跡是否在可視化查詢時間區間內（行2）。然后，對于在可視化查詢時間區間內的移動對象，按秒數遞增，for循環查詢時間區間內T的時間點t，調用getCTIndex()函數用二分法查找對應時間點t的移動對象索引（行7）。然后，通過索引定位到該時間點t移動對象對應的坐標（行6）。算法1的時間瓶頸主要在同一時間片移動對象的重復查詢和繪制（行3）和移動對象查詢的時間消耗（行4）。

3.2 GPU環境下的移動對象更新方法

在GPU基礎上發展起來的計算統一設備架構[16]（compute unified device architecture，CUDA），支持C、C++等多種編程語言。CUDA的高性能計算能力，是通過CPU與GPU的異步執行來實現的。在CUDA模型中，通常將CPU稱作主機端，GPU稱作設備端。數據初始化、內存分配、數據拷貝和啟動核函數等串行任務在主機端進行，設備端負責處理高度線程化的并行任務，又稱為核函數。

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

圖3 基于GPU的移動對象更新流程圖Fig.3 Moving objects updating flow chart based on CUDA

由2.1節可知，移動對象軌跡數據由一組采樣點構成，每個采樣點包括時間和空間信息。數據預處理是將移動對象數據的時間信息提取出來，存放在一維數組中，如圖4所示，時間數據和擁有該時間數據的采樣點具有相同的索引（數組下標），數據傳輸時，僅把時間數據從CPU拷貝到GPU。即將數據變成簡單的一維數組，使得數據更容易在CPU內存和GPU內存之間傳輸。

圖4 移動對象數據Fig.4 Moving objects data

并行查詢區間的大小決定了查詢集的大小。每個移動對象有不同的時間區間Ttraj，查詢時間區間為T，則并行查詢的時間區間TP=Ttraj∩T，對應的時間點為{t1,t2,…,tn}(TP.ts≤t1＜ti＜tn≤TP.te)，每個時間點ti間隔1 s。按時間點ti分割成N個查詢任務，一個查詢任務返回一個移動對象的索引，則查詢集大小為N。

內存分配和數據拷貝完成后，主機端啟動核函數，將需要執行的N個查詢任務交給設備端處理。當核函數映射到GPU后，會被分配到網格上，網格中有多個線程塊，每個線程塊由多個線程構成，并在同一個多處理器上運行。單個線程處理一個獨立的時間點查詢任務，N個查詢任務并行執行結束后，設備端返回查詢集。再根據查找集內的索引，得到移動對象對應的位置坐標，將所有坐標點連接構成查詢范圍內的移動對象軌跡。移動對象并行索引查詢如算法2所示。

算法2基于GPU的移動對象并行查詢算法

算法2中，首先獲取對應的線程索引（行1），并且一個線程索引對應一個時間點t的查詢任務。然后，運用二分法查找算法，查找對應時間點t的移動對象索引（行2～行17）。最后，將查找到的索引存放在索引數組中（行18）。

3.3 優化更新函數

在移動對象可視化查詢時，移動對象的更新函數是將查找的整個時間區間內的移動對象軌跡全部更新，這會造成同一時間片的重復更新。所以，提出了優化更新函數的方法。

首先，判斷需要更新的時間片。如圖5所示，當上一次可視化查詢的時間區間T1與當前可視化查詢的時間區間T2相交時，比較T1和T2的重疊區間，以此分情況討論。然后，根據找出的需要更新的時間區間，對移動對象進行相應的可視化更新操作。

圖5 更新函數優化方法Fig.5 Optimization method of update function

情況1當T2.ts＜T1.ts且T2.te＜T1.te時，需要更新的時間區間為[T2.ts,T1.ts]。

情況2分兩種情況。（1）當T2.ts＞T1.ts且T2.te＜T1.te時，T2的整個時間區間都在T1的時間區間內，所以沒有需要更新的時間片。（2）當T2.ts＜T1.ts且T2.te＞T1.te時，需要更新時間區間為[T2.ts,T1.ts]和[T1.te,T2.te]。

情況3當T2.ts＞T1.ts且T2.te＞T1.te時，則需更新的時間區間為[T1.te,T2.te]。

算法1第3行的for循環查找的時間區間T，替換為上述情況討論的需要更新的時間區間。

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

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

4 實驗評估

本文實驗CPU采用Intel?Core?i7-5500@2.4 GHz，內 存8 GB，4核；GPU采用NVIDIA公司的GeForce GTX 1660 Ti，支持CUDA 10.0的驅動版本，顯存容量為6 GB；操作系統為Ubuntu 14.04；實驗代碼使用CUDA C編寫。

4.1 實驗數據

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

表2 數據集Table 2 Dataset

4.2 實驗結果

4.2.1 查詢性能對比

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

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

在處理數據規模為1 000萬條時，比較GPU_Parallel查詢方法和其他3種查詢方法在不同時間范圍上的查詢性能，如圖6所示。

圖6 時間范圍對查詢性能的影響Fig.6 Effect of time ranges on query performance

主機和設備的數據傳輸消耗的時間會影響整個程序的效率，經測試本實驗使用的GPU設備的數據傳輸時間大約占整個GPU運行時間的23%。所以只有當計算數據足夠大時，才能顯示出GPU的并行計算的優勢。因此在圖6（a）中，當可視化查詢時間區間只有3個小時，數據傳輸時間大約為76 ms，使得GPU_Parallel運行時間大于CPU_Serial的運行時間，加速比為0.94。

為了使實驗效果明顯，在不同規模的數據集上的比較測試，查詢時間范圍設置為16小時，比較GPU_Parallel查詢方法和其他3種查詢方法在不同數據規模上的查詢性能，如圖7所示。

圖7 數據規模對查詢性能的影響Fig.7 Effect of data sizes on query performance

從圖6和圖7中的結果可以看出，隨著查詢的數據規模和時間范圍的遞增，CPU_R-Tree和CPU_Serial方法的運行時間快速增長，而GPU_R-Tree和GPU_Parallel方法的運行時間變化不大。雖然GPU_R-Tree方法與GPU_Parallel方法在不同時間范圍和數據規模上運行時間相差不大，但是GPU_R-Tree方法還有構建R-Tree的時間消耗，且其查詢集不確定，必須靜態分配緩沖區，這會造成內存的額外開銷。因此GPU_Parallel方法更優，與其他查詢方法相比，加速比最高可達18.48。

4.2.2 優化更新函數

本小節實驗數據使用Cabs_Data數據集，用加速效率作為衡量算法性能提升的指標，加速效率越大表明實驗效果越好，加速效率S的定義如公式（1）所示：

其中，TO表示現有更新函數可視化查詢時間，TN表示優化后的更新函數可視化查詢時間。

實驗測試發現，如圖8所示，加速效率與鄰近的兩次可視化查詢時間片段的重疊范圍有關。

圖8 加速效率Fig.8 Acceleration efficiency

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

5 結束語

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