車慶首，李傳文+，張 軼，鄧慶緒

1.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110004

2.東北大學(xué) 中荷生命與信息學(xué)院，沈陽(yáng) 110004

GAPI：GPU加速的移動(dòng)對(duì)象并行索引方法*

車慶首1，李傳文1+，張 軼2，鄧慶緒1

1.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110004

2.東北大學(xué) 中荷生命與信息學(xué)院，沈陽(yáng) 110004

為減少加鎖操作對(duì)移動(dòng)對(duì)象數(shù)據(jù)庫(kù)并行性能的影響并提高其吞吐量，提出一種由GPU加速的網(wǎng)格結(jié)合四叉樹的索引方法。采用由GPU對(duì)出入節(jié)點(diǎn)對(duì)象進(jìn)行計(jì)數(shù)并持續(xù)計(jì)算節(jié)點(diǎn)拆分/合并條件的方式，在不影響CPU計(jì)算能力的前提下，將存在性能瓶頸的網(wǎng)格節(jié)點(diǎn)轉(zhuǎn)化為四叉樹，從而減少對(duì)象數(shù)據(jù)更新時(shí)加鎖操作造成的其他線程等待時(shí)間。該方法結(jié)構(gòu)簡(jiǎn)單且更適用于對(duì)象不均勻分布的場(chǎng)景，避免了現(xiàn)有索引方式或在熱點(diǎn)區(qū)域存在性能瓶頸，或需花費(fèi)大量計(jì)算資源進(jìn)行結(jié)構(gòu)平衡等缺點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該方法與現(xiàn)有移動(dòng)對(duì)象索引方式相比具有數(shù)據(jù)吞吐量大、響應(yīng)速度快等特點(diǎn)，在移動(dòng)對(duì)象空間分布不均勻的場(chǎng)景下其優(yōu)勢(shì)更為明顯。

移動(dòng)對(duì)象索引；動(dòng)態(tài)網(wǎng)格索引；空間數(shù)據(jù)庫(kù)；GPU加速

1 引言

隨著移動(dòng)計(jì)算、基于位置的服務(wù)、GIS等應(yīng)用的不斷發(fā)展，移動(dòng)對(duì)象數(shù)據(jù)庫(kù)（moving object database，MOD）受到了國(guó)內(nèi)外研究人員越來(lái)越多的關(guān)注[1]。移動(dòng)對(duì)象數(shù)據(jù)庫(kù)旨在對(duì)移動(dòng)對(duì)象提供實(shí)時(shí)的數(shù)據(jù)更新和查詢服務(wù)支持，其主要目標(biāo)是在滿足一定時(shí)間精度和空間精度的前提下為用戶提供一定范圍內(nèi)移動(dòng)對(duì)象的查詢結(jié)果。例如在打車應(yīng)用中，手機(jī)用戶和出租車都是移動(dòng)對(duì)象，為用戶推薦一定距離內(nèi)的出租車就是一種典型的移動(dòng)對(duì)象查詢操作[2]。

對(duì)于海量的移動(dòng)對(duì)象數(shù)據(jù)，傳統(tǒng)的單線程空間數(shù)據(jù)管理方式在效率上已難以滿足實(shí)際應(yīng)用需求。而類似Hadoop、Spark等大數(shù)據(jù)處理平臺(tái)雖然對(duì)于處理海量數(shù)據(jù)具有優(yōu)勢(shì)，但是由于這些平臺(tái)大都是分布式搭建，平臺(tái)節(jié)點(diǎn)之間相互通信所需的時(shí)間代價(jià)使其無(wú)法滿足空間移動(dòng)數(shù)據(jù)管理的實(shí)時(shí)性要求。因此，目前移動(dòng)對(duì)象管理一般采用單機(jī)多線程的方式實(shí)現(xiàn)。

由于對(duì)象位置變化頻率高，為提高IO效率，存儲(chǔ)移動(dòng)對(duì)象的數(shù)據(jù)結(jié)構(gòu)往往采用內(nèi)存數(shù)據(jù)庫(kù)的方式[3]。因此，單機(jī)多線程移動(dòng)對(duì)象管理的性能瓶頸不再是IO操作，而變成了多個(gè)線程之間相互協(xié)調(diào)造成的延時(shí)，其中最主要的是線程對(duì)數(shù)據(jù)結(jié)構(gòu)的加鎖操作對(duì)其他線程造成的影響。如何減少加鎖操作對(duì)其他線程的影響是移動(dòng)對(duì)象管理的研究重點(diǎn)。

目前移動(dòng)對(duì)象索引結(jié)構(gòu)有兩大類：基于網(wǎng)格的索引[4]和基于樹的索引[5]?；诰W(wǎng)格的索引將空間劃分成一致大小的均勻網(wǎng)格，而基于樹的索引以其葉節(jié)點(diǎn)對(duì)空間進(jìn)行覆蓋。移動(dòng)對(duì)象進(jìn)出網(wǎng)格或葉節(jié)點(diǎn)時(shí)需要對(duì)網(wǎng)格或葉節(jié)點(diǎn)加鎖，此時(shí)其他線程對(duì)此網(wǎng)格或葉節(jié)點(diǎn)的更新操作都需要等待。

基于網(wǎng)格的索引方式結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)，但不適用于移動(dòng)對(duì)象分布不均勻的應(yīng)用場(chǎng)景。移動(dòng)對(duì)象負(fù)載不均問題普遍存在，如交通監(jiān)控應(yīng)用中，熱點(diǎn)地區(qū)相對(duì)于普通地區(qū)，或者早晚高峰時(shí)相對(duì)于其他時(shí)段，移動(dòng)對(duì)象在空間和時(shí)間上的負(fù)載就存在明顯不均。而基于樹的索引雖然能使每個(gè)葉節(jié)點(diǎn)包含的移動(dòng)對(duì)象數(shù)大體一致，但實(shí)驗(yàn)結(jié)果顯示其性能不如基于網(wǎng)格的索引方式好[6]。

由于只有對(duì)象進(jìn)出葉節(jié)點(diǎn)時(shí)需要對(duì)節(jié)點(diǎn)鎖定，樹狀索引中葉節(jié)點(diǎn)的劃分不應(yīng)以其中移動(dòng)對(duì)象總數(shù)為標(biāo)準(zhǔn)，而應(yīng)以單位時(shí)間內(nèi)出入葉節(jié)點(diǎn)的對(duì)象數(shù)目為劃分標(biāo)準(zhǔn)。然而對(duì)出入對(duì)象的計(jì)數(shù)涉及到頻繁鎖定計(jì)數(shù)器的原子操作，而且根據(jù)不斷變化的計(jì)數(shù)結(jié)果判斷是否需要對(duì)葉節(jié)點(diǎn)進(jìn)行拆分或合并相鄰葉節(jié)點(diǎn)都需要持續(xù)進(jìn)行大量計(jì)算，這些操作都會(huì)嚴(yán)重影響移動(dòng)對(duì)象數(shù)據(jù)更新效率，因此現(xiàn)有的研究沒有采用出入對(duì)象計(jì)數(shù)對(duì)葉節(jié)點(diǎn)進(jìn)行劃分的索引方法[7]。

鑒于此，本文提出了一種采用GPU加速的移動(dòng)對(duì)象并行索引方法（GPU accelerated parallel indexing method for spatial moving objects，GAPI），采用網(wǎng)格結(jié)合四叉樹結(jié)構(gòu)，將葉節(jié)點(diǎn)出入對(duì)象的計(jì)數(shù)以及葉節(jié)點(diǎn)是否需要拆分或合并的判斷交由GPU處理。這種方式只占用極少量CPU計(jì)算資源，實(shí)現(xiàn)了在不影響數(shù)據(jù)更新和查詢效率的前提下使索引結(jié)構(gòu)不斷優(yōu)化的目的。實(shí)驗(yàn)結(jié)果表明，該索引方法在移動(dòng)對(duì)象更新方面的性能明顯優(yōu)于現(xiàn)有的最好方法。

2 GAPI索引結(jié)構(gòu)

2.1 問題定義

給定空間平面S，移動(dòng)對(duì)象集O={o1,o2,…,on}，其中任一對(duì)象，為oi的唯一標(biāo)識(shí)，為其位置，為最近一次更新時(shí)間。查詢操作集Q={q1,q2,…,qe}，其中任一查詢請(qǐng)求qj={xmin,ymin,xmax,ymax,tq}，前4項(xiàng)定義了一個(gè)矩形查詢框，tq為查詢開始的時(shí)間。移動(dòng)對(duì)象數(shù)據(jù)庫(kù)的目的就是當(dāng)Q中查詢qj到達(dá)時(shí)，將位于查詢框中的移動(dòng)對(duì)象返回給用戶。

這種查詢方式稱為范圍查詢（range query），由于其他種類的查詢?nèi)鏺NN（knearest neighbor）查詢等都可以被轉(zhuǎn)化為一系列的范圍查詢，本文只需討論索引結(jié)構(gòu)對(duì)此種查詢的支持。

2.2 索引結(jié)構(gòu)

移動(dòng)對(duì)象數(shù)據(jù)庫(kù)的主要工作是不斷更新移動(dòng)對(duì)象的位置及根據(jù)查詢需求返回結(jié)果。因此，移動(dòng)對(duì)象索引結(jié)構(gòu)須高效地滿足兩項(xiàng)基本條件：

可采用基于哈希表的輔助索引方式實(shí)現(xiàn)對(duì)條件（1）的支持。

定義1（輔助索引，auxiliary index）輔助索引采用哈希表H根據(jù)值對(duì)所有空間對(duì)象進(jìn)行索引，H中保存形如的鍵-值對(duì)，其中p_bkt為oi在混合索引（參見定義2）中所處桶的內(nèi)存空間位置，idx代表其在桶中的相對(duì)位置。

圖1展示了一個(gè)輔助索引的示例。由哈希表的性質(zhì)可知，利用輔助索引可在常數(shù)時(shí)間內(nèi)根據(jù)找到內(nèi)存中oi的存儲(chǔ)位置。

Fig.1 Example of auxiliary index圖1 輔助索引示例

基于網(wǎng)格的索引和基于樹的索引在滿足條件（2）方面各有優(yōu)缺點(diǎn)。

基于樹的索引方式減少了熱點(diǎn)地區(qū)對(duì)象擁塞的情況，然而每次由對(duì)oi的查找需要從樹根節(jié)點(diǎn)到一系列中間節(jié)點(diǎn)直至葉節(jié)點(diǎn)的多次查詢，降低了查詢效率。對(duì)整體效率影響更大的是，樹狀索引需要不斷調(diào)整結(jié)構(gòu)以適應(yīng)移動(dòng)對(duì)象的分布，計(jì)算葉節(jié)點(diǎn)是否需要調(diào)整以及調(diào)整操作本身都會(huì)消耗大量計(jì)算資源。

本文提出一種網(wǎng)格結(jié)合四叉樹的混合索引方式，避免了上述兩種方式的缺點(diǎn)。

定義2（混合索引，hybrid index）混合索引P將空間平面S劃分為Gnum=2ρ×2ρ個(gè)網(wǎng)格，每個(gè)網(wǎng)格可以根據(jù)條件在網(wǎng)格節(jié)點(diǎn)與四叉樹兩種形式間轉(zhuǎn)換。

混合索引的目標(biāo)是通過將熱點(diǎn)區(qū)域的網(wǎng)格轉(zhuǎn)變?yōu)樗牟鏄鋄8]的方式達(dá)到平衡每個(gè)單元格負(fù)載的目的。ρ為網(wǎng)格劃分參數(shù)，采用文獻(xiàn)[9]給出的選擇條件：

其中，N表示空間中移動(dòng)對(duì)象的總數(shù)量；CL表示葉節(jié)點(diǎn)的容量。

執(zhí)行時(shí)，動(dòng)態(tài)判斷每個(gè)網(wǎng)格中的移動(dòng)對(duì)象出入數(shù)量，將滿足拆分要求的網(wǎng)格轉(zhuǎn)化為四叉樹，將滿足合并要求的四叉樹轉(zhuǎn)化回網(wǎng)格。在各四叉樹內(nèi)部也根據(jù)條件對(duì)其葉節(jié)點(diǎn)進(jìn)行拆分、合并操作。

圖2展示了一個(gè)混合索引的示例。圖中右半部分上層是一個(gè)被劃分為Gnum=2ρ×2ρ個(gè)網(wǎng)格的平面S，其中黑色的網(wǎng)格代表被轉(zhuǎn)換為四叉樹的熱點(diǎn)網(wǎng)格。下面幾層表示的是各級(jí)四叉樹節(jié)點(diǎn)對(duì)應(yīng)的空間區(qū)域，其中黑色節(jié)點(diǎn)代表更進(jìn)一步被細(xì)分的區(qū)域。圖中左半部分顯示的是其中一棵放大的四叉樹，其上方顯示了這棵四叉樹對(duì)其所在網(wǎng)格的劃分?？梢钥闯?，轉(zhuǎn)換為四叉樹后，區(qū)域得到了更精細(xì)的劃分。

每個(gè)網(wǎng)格節(jié)點(diǎn)ci只包含一個(gè)pbucket指針，指向一個(gè)桶鏈表Li，該鏈表包含一系列存放固定數(shù)目的屬于該節(jié)點(diǎn)的所有移動(dòng)對(duì)象的桶。每個(gè)四叉樹節(jié)點(diǎn)ξi表示為ξi={pbucket,pc1,pc2,pc3,pc4}，其中pc1、pc2、pc3、pc4分別為指向以當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的4個(gè)象限中的子節(jié)點(diǎn)的指針。

Fig.2 Example of hybrid index圖2 混合索引示例

2.3 節(jié)點(diǎn)拆合條件

由于對(duì)網(wǎng)格的拆合（拆分/合并）操作與對(duì)四叉樹葉節(jié)點(diǎn)的拆合操作本質(zhì)相同，在討論拆合條件時(shí)網(wǎng)格與葉節(jié)點(diǎn)將被統(tǒng)稱為節(jié)點(diǎn)。

當(dāng)對(duì)象在節(jié)點(diǎn)c內(nèi)部移動(dòng)時(shí)，只需鎖定對(duì)象自身以對(duì)其位置進(jìn)行更新，不涉及鎖定節(jié)點(diǎn)的問題。而當(dāng)移動(dòng)對(duì)象出入節(jié)點(diǎn)c時(shí)，則需在c對(duì)應(yīng)的某個(gè)桶中對(duì)此對(duì)象的信息進(jìn)行添加或刪除，此時(shí)必須鎖定c以避免不同線程同時(shí)對(duì)c進(jìn)行的更新操作可能造成的數(shù)據(jù)沖突。此時(shí)，所有其他線程對(duì)節(jié)點(diǎn)c的更新操作都需要暫停等待。單位時(shí)間內(nèi)移動(dòng)對(duì)象出入c的數(shù)量nc越多，同時(shí)等待的線程就越多。更新操作所需的總時(shí)間φc為操作實(shí)際執(zhí)行時(shí)間ncτ（其中τ為每次更新操作的執(zhí)行時(shí)間）與等待時(shí)間ψc之和，因此更新操作總時(shí)間與節(jié)點(diǎn)單位時(shí)間內(nèi)移動(dòng)對(duì)象出入數(shù)量存在正相關(guān)關(guān)系。

通過拆分節(jié)點(diǎn)可以減少節(jié)點(diǎn)內(nèi)同時(shí)等待的線程數(shù)量。然而，將一個(gè)節(jié)點(diǎn)c拆分為 4 個(gè)節(jié)點(diǎn)c1、c2、c3、c4后，原來(lái)屬于節(jié)點(diǎn)c內(nèi)的對(duì)象移動(dòng)就有可能變成不同節(jié)點(diǎn)之間的移動(dòng)，增加了出入節(jié)點(diǎn)移動(dòng)對(duì)象的總數(shù)量，即

因此，為了減少φ需要對(duì)節(jié)點(diǎn)進(jìn)行適度的拆分，只有當(dāng)式（3）滿足時(shí)：

對(duì)節(jié)點(diǎn)進(jìn)行拆分才有利于提高更新性能。反之，當(dāng)已 拆 分 的 4 個(gè) 節(jié) 點(diǎn)c1、c2、c3、c4滿 足 條 件時(shí)，則需將其合并成一個(gè)節(jié)點(diǎn)。

本節(jié)將定量分析φ與n的關(guān)系。首先討論移動(dòng)對(duì)象每增加一個(gè)更新操作對(duì)總等待時(shí)間的影響。

引理1設(shè)每個(gè)對(duì)象出入節(jié)點(diǎn)所需的更新操作執(zhí)行時(shí)間為τ，當(dāng)單位時(shí)間內(nèi)出入節(jié)點(diǎn)的移動(dòng)對(duì)象數(shù)量為nc(nc＞1)時(shí)，記此nc個(gè)移動(dòng)對(duì)象出入信息更新所需的總等待時(shí)間的期望值為ψ(nc)，則nc+1個(gè)移動(dòng)對(duì)象更新的等待時(shí)間的期望值ψ(nc+1)可表示為：

證明 假設(shè)節(jié)點(diǎn)c單位時(shí)間內(nèi)有nc個(gè)對(duì)象出入，那么第nc+1個(gè)對(duì)象進(jìn)出單元格需要等待nc個(gè)對(duì)象更新完成，記為：

其中，?(nc)為等待時(shí)間與移動(dòng)對(duì)象數(shù)量之間的關(guān)聯(lián)函數(shù)。nc個(gè)對(duì)象之間存在著更新等待時(shí)間重合與不重合的情況。所謂更新等待時(shí)間重合是指某個(gè)對(duì)象的更新開始時(shí)間點(diǎn)出現(xiàn)在另一個(gè)對(duì)象正在執(zhí)行更新操作的時(shí)間段內(nèi)；更新等待時(shí)間不重合是指某個(gè)對(duì)象的更新開始時(shí)間點(diǎn)出現(xiàn)在另一個(gè)對(duì)象更新開始點(diǎn)往前推遲τ的時(shí)間點(diǎn)前，這樣保證了兩個(gè)對(duì)象更新不用相互等待。關(guān)聯(lián)函數(shù)?(nc)的意義就是對(duì)象更新之間重合與不重合的聯(lián)系。

當(dāng)nc個(gè)對(duì)象之間不重合時(shí)，記p1′為第n+1個(gè)對(duì)象落入對(duì)象執(zhí)行時(shí)間段內(nèi)的概率，p1″為落入某個(gè)對(duì)象更新時(shí)間點(diǎn)前τ的時(shí)間點(diǎn)前的概率。

p1′=nc，此時(shí)的等待時(shí)間是函數(shù)τ在[0,τ]上的積分，即：

p1″=nc×τ，此時(shí)的等待時(shí)間是常量1在[0,τ]上的積分，即：

nc個(gè)對(duì)象之間不重合的等待時(shí)間w1可表為：

當(dāng)nc個(gè)對(duì)象之間存在重合，重合部分時(shí)間就需要往后順延，記重合部分的等待時(shí)間為w2，對(duì)象的執(zhí)行時(shí)間為τ，每個(gè)對(duì)象可重合的時(shí)間段往前推延τ，因此可重合的時(shí)間段ot=2τ。

兩個(gè)對(duì)象重合往后順延的時(shí)間記為w2′，w2′是關(guān)于可重合的時(shí)間段ot在[0,τ]上的積分：

nc個(gè)對(duì)象之間只存在nc-1個(gè)重合時(shí)間段，nc個(gè)重合對(duì)象之間往后順延的時(shí)間為：

由兩個(gè)對(duì)象之間重合的概念可知，每個(gè)對(duì)象可重合的時(shí)間段記為ot=2τ，兩個(gè)對(duì)象之間的重合概率就為：

nc個(gè)對(duì)象之間重合的等待時(shí)間w2可表示為：

?(nc)=w1+w2，將上述式子帶入，可得：

由引理1可推出等待時(shí)間ψ(n)的封閉形式。

引理2設(shè)節(jié)點(diǎn)單位時(shí)間出入的移動(dòng)對(duì)象數(shù)量為n，每個(gè)對(duì)象的更新執(zhí)行時(shí)間為τ，則此n次更新操作的總等待時(shí)間ψ(n)為：

證明 由引理1可知，移動(dòng)對(duì)象的更新等待時(shí)間與移動(dòng)對(duì)象的數(shù)量與對(duì)象的更新時(shí)間點(diǎn)有關(guān)，將式（4）遞歸展開：

將ψ(1)ψ(2)…ψ(n)依次帶入，可得：

因此引理得證。 □

引理2描述了對(duì)象更新等待時(shí)間與對(duì)象更新數(shù)量的關(guān)系，而更新的總時(shí)間φ為更新等待時(shí)間ψ與實(shí)際執(zhí)行時(shí)間nτ之和。

定理1設(shè)節(jié)點(diǎn)單位時(shí)間內(nèi)移動(dòng)對(duì)象出入數(shù)量為n，每個(gè)對(duì)象的更新執(zhí)行時(shí)間為τ，則節(jié)點(diǎn)在單位時(shí)間內(nèi)包括等待其他線程的總更新時(shí)間φ(n)可表示為：

證明 將式（5）代入φ(n)=nτ+ψ(n)可證。 □

3 數(shù)據(jù)結(jié)構(gòu)與算法

本章采用類C++的偽代碼對(duì)GAPI索引結(jié)構(gòu)進(jìn)行描述。GAPI索引結(jié)構(gòu)分為輔助索引和混合索引兩部分，其中輔助索引H采用哈希表，即形式為unordered_map＜int,pair＜Bucket*,int＞＞的結(jié)構(gòu)保存鍵-值對(duì)?；旌纤饕捎枚S數(shù)組結(jié)合四叉樹（QuadTree）的形式。接下來(lái)重點(diǎn)討論混合索引數(shù)據(jù)結(jié)構(gòu)以及與其相關(guān)的算法。

混合索引數(shù)據(jù)結(jié)構(gòu)包括網(wǎng)格索引及QuadTree索引兩部分，其主要目的是根據(jù)定理1給出的條件平衡每個(gè)單元格的更新負(fù)載，將對(duì)象數(shù)量少的單元格合并，降低對(duì)四叉樹的查詢成本；將對(duì)象數(shù)量較大的單元格拆分，減少更新等待時(shí)間。

由2.3節(jié)可知，持續(xù)比較節(jié)點(diǎn)c的總執(zhí)行時(shí)間φc與其4個(gè)子節(jié)點(diǎn)的總執(zhí)行時(shí)間φc1+φc2+φc3+φc4的關(guān)系是決定一個(gè)節(jié)點(diǎn)拆分或者合并的關(guān)鍵。由于這些比較操作需消耗大量的計(jì)算資源，GAPI索引方法把這些操作放在GPU運(yùn)行。對(duì)移動(dòng)對(duì)象出入節(jié)點(diǎn)的計(jì)數(shù)工作雖不需太多計(jì)算，但每次增加計(jì)數(shù)值都需要鎖定計(jì)數(shù)器，對(duì)整體并行性能也會(huì)造成嚴(yán)重影響，因此計(jì)數(shù)操作也需要放在GPU運(yùn)行。

本章將從CPU和GPU兩方面對(duì)GAPI索引算法進(jìn)行介紹。所有算法都基于統(tǒng)一的存儲(chǔ)于主存的數(shù)據(jù)結(jié)構(gòu)，GPU運(yùn)算所需的數(shù)據(jù)只在使用時(shí)由主存復(fù)制到顯存中，得到計(jì)算結(jié)果后再由顯存復(fù)制回主存。

3.1 數(shù)據(jù)結(jié)構(gòu)

混合索引中網(wǎng)格索引采用二維數(shù)組實(shí)現(xiàn)：

其中，width和height分別表示網(wǎng)格列數(shù)和行數(shù)；Node類是Cell和QuadTree的父類。Cell代表一個(gè)網(wǎng)格，其中僅包含一個(gè) unique_ptr＜Bucket＞類型的指針，而QuadTree代表一棵四叉樹：

Cell或QuadTree中的對(duì)象用桶鏈表結(jié)構(gòu)存儲(chǔ)。桶用來(lái)存儲(chǔ)葉節(jié)點(diǎn)上的移動(dòng)對(duì)象，桶的大小固定，每個(gè)葉節(jié)點(diǎn)下的桶數(shù)量由移動(dòng)對(duì)象的數(shù)量決定。插入對(duì)象時(shí)如果桶滿，則新建一個(gè)桶；刪除對(duì)象時(shí)如果桶變空，則刪除桶。桶結(jié)構(gòu)如下：

其中Site類保存移動(dòng)對(duì)象數(shù)據(jù)，包括id、x、y以及更新時(shí)間tu。由Site類包含的內(nèi)容可以推斷，其一個(gè)對(duì)象的數(shù)據(jù)至少需要占用128位（在32位機(jī)上4個(gè)int值）內(nèi)存空間，如果不采用保護(hù)措施，并行讀寫Site類時(shí)不同線程之間可能產(chǎn)生訪問沖突。傳統(tǒng)的避免訪問沖突的方法是在讀寫Site對(duì)象時(shí)對(duì)其加鎖。由于Site類是GAPI索引中使用最頻繁的類，為了避免加鎖對(duì)性能造成的影響，將Site類中的4個(gè)數(shù)據(jù)合并為一個(gè)_m128i類型的對(duì)象，采用Intel MMX指令集[10]中的_mm_load_si128和_mm_set_epi32操作對(duì)其中內(nèi)容進(jìn)行讀寫，并采用_mm_extract_epi32提取相應(yīng)的數(shù)據(jù)。采用這種方式，GAPI索引就能在不加鎖的前提下正確地并行讀寫Site數(shù)據(jù)。

GAPI索引中還維護(hù)兩個(gè)list＜Node*＞類型的列表split_candicates和merge_candidates，分別保存需要被GPU計(jì)算是否需要拆分或合并的節(jié)點(diǎn)。

3.2 CPU算法

隨著對(duì)象持續(xù)的更新，四叉樹的結(jié)構(gòu)也隨之變化。對(duì)象的插入算法根據(jù)坐標(biāo)將其插入到合適的節(jié)點(diǎn)上。刪除算法根據(jù)對(duì)象id找到所在桶，將其刪除。單元格的劃分與合并是平衡四叉樹的關(guān)鍵操作，只有滿足拆合條件的單元格才能進(jìn)行劃分與合并。

3.2.1 空間對(duì)象插入算法

算法1對(duì)象o插入葉節(jié)點(diǎn)add_to_leaf

對(duì)象移動(dòng)過程中，隨著位置的變化，對(duì)象會(huì)不斷地在各個(gè)節(jié)點(diǎn)間移動(dòng)，算法1的主要目的是將一個(gè)對(duì)象插入葉子節(jié)點(diǎn)。其思想是根據(jù)對(duì)象的位置查找該對(duì)象應(yīng)該被插入的葉節(jié)點(diǎn)，判斷該節(jié)點(diǎn)的桶狀態(tài)。如果桶未滿，直接插入桶，如果桶滿，則新建一個(gè)桶n_bucket，將新建的桶插入到當(dāng)前節(jié)點(diǎn)的桶列表。然后再把對(duì)象oi插入桶，并且桶存放的對(duì)象數(shù)量加1。

3.2.2 空間對(duì)象刪除算法

算法2從葉節(jié)點(diǎn)刪除對(duì)象oremove_from_leaf

當(dāng)移動(dòng)對(duì)象位置更新時(shí)，不再屬于當(dāng)前葉節(jié)點(diǎn)范圍的對(duì)象需要被插入到其新的所屬葉節(jié)點(diǎn)中，并從當(dāng)前節(jié)點(diǎn)刪除。

3.2.3 單元格劃分算法

算法3單元格劃分split

根據(jù)2.3節(jié)中的節(jié)點(diǎn)拆/合條件可知，當(dāng)葉節(jié)點(diǎn)滿足φc＞φc1

+φc2+φc3

+φc4

條件時(shí)，QuadTree索引結(jié)構(gòu)應(yīng)將葉節(jié)點(diǎn)s_node劃分為4個(gè)子網(wǎng)格，子網(wǎng)格的劃分按照上、下、左、右均分原則進(jìn)行，其中x_middle=(left+right)/2,y_middle=(floor+ceiling)/2，如第1～2行所示。劃分完成后，所有孩子的父節(jié)點(diǎn)均設(shè)置為當(dāng)前葉節(jié)點(diǎn)，將被劃分節(jié)點(diǎn)s_node中的所有對(duì)象移動(dòng)到對(duì)應(yīng)孩子的桶里。如果被劃分節(jié)點(diǎn)的父親在該節(jié)點(diǎn)未劃分之前屬于split_candidates列表，則將其從拆分候選列表split_candidates里刪除，之后將當(dāng)前節(jié)點(diǎn)加入split_candidates列表。

3.2.4 單元格合并算法

算法4單元格合并merge

如算法4所示，當(dāng)節(jié)點(diǎn)滿足合并條件時(shí)，將該節(jié)點(diǎn)的所有孩子的桶鏈接起來(lái)并賦給當(dāng)前節(jié)點(diǎn)的桶。調(diào)整當(dāng)前節(jié)點(diǎn)的桶鏈，刪除空桶。如果當(dāng)前節(jié)點(diǎn)屬于merge_candidates列表，則將當(dāng)前節(jié)點(diǎn)m_node從merge_candidates里刪除。合并后，如果當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)屬于merge_candidates列表，則將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)m_node.parent加入merge_candidates列表。

3.3 GPU算法

GPU由于邏輯運(yùn)算能力較CPU弱，不適用于進(jìn)行較多的邏輯判斷，而較適用于大量的數(shù)據(jù)運(yùn)算。與CPU不同，GPU采用的是單指令多數(shù)據(jù)（single instruction multiply data，SIMD）的工作方式，可以在多組數(shù)據(jù)上同時(shí)執(zhí)行同樣的一條指令，從而達(dá)到提高并行執(zhí)行效率的目的[11]。因此，GAPI索引中交給GPU的工作主要由涉及到大數(shù)據(jù)量計(jì)算的兩部分構(gòu)成：（1）對(duì)出入節(jié)點(diǎn)的移動(dòng)對(duì)象進(jìn)行計(jì)數(shù)；（2）判斷節(jié)點(diǎn)是否需要拆分或合并。

這兩部分操作都涉及到GAPI索引中維護(hù)的兩個(gè)list＜Node*＞類型的列表split_candidates和merge_candidates。

3.3.1 計(jì)數(shù)算法

本小節(jié)以單位時(shí)間內(nèi)對(duì)對(duì)象移入節(jié)點(diǎn)進(jìn)行計(jì)數(shù)的操作對(duì)計(jì)數(shù)算法進(jìn)行說明。若該操作運(yùn)行于CPU，則通常會(huì)根據(jù)CPU并行[12]能力開啟若干線程，分別執(zhí)行如下流程。

算法5基于CPU的計(jì)數(shù)算法CPU_count

其中update_info_list中存儲(chǔ)了系統(tǒng)接收到的一系列對(duì)象移動(dòng)數(shù)據(jù)，包括對(duì)象id，原位置及新位置等信息，每個(gè)CPU線程處理update_info_list中的一部分。在由get_location計(jì)算出對(duì)象移入的節(jié)點(diǎn)后，第3行對(duì)移入的節(jié)點(diǎn)計(jì)數(shù)器進(jìn)行遞增。注意，為了保證對(duì)計(jì)數(shù)器并行讀寫的正確性，在遞增時(shí)必須對(duì)計(jì)數(shù)器進(jìn)行鎖定。

與CPU不同，由于GPU[13]普遍具有上千個(gè)流處理器，可以使每個(gè)流處理器[14]維護(hù)固定數(shù)目的若干節(jié)點(diǎn)的計(jì)數(shù)器。由于每個(gè)計(jì)數(shù)器只可能由固定的某一個(gè)流處理器訪問，計(jì)數(shù)器遞增時(shí)不需要加鎖。算法6演示了每個(gè)流處理器負(fù)責(zé)m×n個(gè)節(jié)點(diǎn)的操作流程。

算法6基于GPU的計(jì)數(shù)算法GPU_count

其中threadIdx是內(nèi)置的由系統(tǒng)自動(dòng)設(shè)置的流處理器index值，count數(shù)組是流處理器的本地?cái)?shù)組，保存了由其負(fù)責(zé)的節(jié)點(diǎn)計(jì)數(shù)器。第3行判斷節(jié)點(diǎn)是否屬于該流處理器負(fù)責(zé)的節(jié)點(diǎn)，如果屬于該流處理器則遞增對(duì)應(yīng)的計(jì)數(shù)器（第4行）。

GAPI索引系統(tǒng)不但對(duì)列表split_candidates和列表merge_candidates中的所有節(jié)點(diǎn)都要調(diào)用GPU_count對(duì)出入節(jié)點(diǎn)的對(duì)象數(shù)進(jìn)行記錄，還會(huì)對(duì)列表split_candidates中每個(gè)節(jié)點(diǎn)可能劃分的4個(gè)子節(jié)點(diǎn)以及merge_candidates中4個(gè)相鄰節(jié)點(diǎn)可能合并的父節(jié)點(diǎn)也調(diào)用GPU_count進(jìn)行計(jì)數(shù)。

3.3.2 拆合判斷算法

以拆分判斷算法為例，由于GAPI索引系統(tǒng)已經(jīng)對(duì)split_candidates列表中的任一節(jié)點(diǎn)c以及其可能拆分成的 4 個(gè)子節(jié)點(diǎn)c1、c2、c3、c4都進(jìn)行了計(jì)數(shù)，只需將split_candidates列表中節(jié)點(diǎn)分配到各個(gè)流處理器上，然后將式（6）代入式（3）進(jìn)行判斷即可。

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

本章將GAPI索引結(jié)構(gòu)與目前最先進(jìn)的PGrid[4]索引結(jié)構(gòu)進(jìn)行對(duì)比。

實(shí)驗(yàn)仿真環(huán)境為Win10系統(tǒng)，Intel Xeon E5-2620 v3六核CPU×2，NVIDIA Quadro K2200 GPU。實(shí)驗(yàn)代碼由C++及CUDA Toolkit 7.5實(shí)現(xiàn)，空間對(duì)象數(shù)據(jù)由基于Brinkhoff[15]算法的開源移動(dòng)對(duì)象生成工具M(jìn)OTO（http://moto.sourceforge.net）生成。實(shí)驗(yàn)參數(shù)如表1所示。

圖3給出了更新/查詢比對(duì)吞吐量影響的實(shí)驗(yàn)結(jié)果。隨著更新/查詢比的升高，兩種索引結(jié)構(gòu)的吞吐量都呈上升趨勢(shì)，其中GAPI的吞吐量在大部分情況下都要高于PGrid，而僅在更新/查詢比較小的情況低于PGrid。這是因?yàn)镚API主要優(yōu)化的是更新操作，通過GPU輔助拆分、合并四叉樹的形式減少了并行更新時(shí)的線程等待時(shí)間，所以平均更新時(shí)間優(yōu)于PGrid。由于對(duì)四叉樹結(jié)構(gòu)的查詢需要由根節(jié)點(diǎn)到葉節(jié)點(diǎn)進(jìn)行多次查詢，GAPI索引的查詢時(shí)間一般會(huì)高于PGrid。

Table 1 Experiment parameters表1 實(shí)驗(yàn)參數(shù)

Fig.3 Effect of throughput on update/query ratio圖3 更新/查詢比對(duì)吞吐量的影響

圖4給出了查詢區(qū)域面積對(duì)吞吐量影響的實(shí)驗(yàn)結(jié)果。由圖可知，在所有情況下，GAPI都優(yōu)于PGrid。隨著查詢區(qū)域面積的增大，整體吞吐量不斷下降。這是因?yàn)椴樵儾僮髡加昧嗽絹?lái)越多的計(jì)算資源。

Fig.4 Effect of throughput on size of queried area圖4 查詢區(qū)域面積對(duì)吞吐量的影響

圖5給出了更新間隔時(shí)間對(duì)吞吐量影響的實(shí)驗(yàn)結(jié)果。更新間隔時(shí)間越長(zhǎng)，對(duì)象移動(dòng)出當(dāng)前節(jié)點(diǎn)的概率就越大。在更新間隔時(shí)間逐漸加大導(dǎo)致PGrid吞吐量急劇下降時(shí)，由于GAPI能夠根據(jù)運(yùn)行時(shí)的實(shí)際情況動(dòng)態(tài)地調(diào)整節(jié)點(diǎn)，GAPI的吞吐量能夠保持穩(wěn)定。從圖5中還可以看出，在所有情況下GAPI的吞吐量都要優(yōu)于PGrid。

Fig.5 Effect of throughput on interval between updating圖5 更新時(shí)間間隔對(duì)吞吐量的影響

圖6給出了移動(dòng)對(duì)象數(shù)對(duì)吞吐量影響的實(shí)驗(yàn)結(jié)果。隨著移動(dòng)對(duì)象數(shù)的增多，兩種索引的吞吐量都逐漸下降。這是因?yàn)橐苿?dòng)對(duì)象數(shù)越多，同一節(jié)點(diǎn)中多個(gè)線程同時(shí)更新的概率就越大，需要進(jìn)行等待的線程就越多。然而隨著移動(dòng)對(duì)象數(shù)的增多，GAPI的吞吐量下降速度明顯慢于PGrid。這是因?yàn)镚API能夠根據(jù)實(shí)際運(yùn)行情況動(dòng)態(tài)地將節(jié)點(diǎn)拆分，從而降低了節(jié)點(diǎn)當(dāng)中對(duì)象的數(shù)量，減少了需要等待的線程數(shù)量，進(jìn)而提高了并行更新效率。

Fig.6 Effect of throughput on number of moving objects圖6 移動(dòng)對(duì)象數(shù)量對(duì)吞吐量的影響

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

本文在網(wǎng)格索引的基礎(chǔ)上，提出了一種結(jié)合四叉樹并采用GPU加速的混合索引方式，避免了基于樹的索引和基于網(wǎng)格的索引的缺點(diǎn)。并通過實(shí)驗(yàn)得出了以下結(jié)論：

（1）GAPI索引將平衡索引結(jié)構(gòu)的計(jì)算工作交由GPU處理，充分利用GPU能快速運(yùn)算大量數(shù)據(jù)的優(yōu)勢(shì)，盡可能地減少了CPU的計(jì)算負(fù)載，從而大大提高了索引優(yōu)化效率。

（2）GAPI索引結(jié)構(gòu)以單位時(shí)間內(nèi)出入葉節(jié)點(diǎn)的對(duì)象數(shù)目為劃分標(biāo)準(zhǔn)，與傳統(tǒng)的以葉節(jié)點(diǎn)存儲(chǔ)數(shù)量為劃分標(biāo)準(zhǔn)的動(dòng)態(tài)索引結(jié)構(gòu)相比，GAPI索引結(jié)構(gòu)具有更好的平衡熱點(diǎn)區(qū)域更新負(fù)載的能力，在移動(dòng)對(duì)象更新方面的性能明顯優(yōu)于現(xiàn)有方法。

[1]Huang Y K.Indexing and querying moving objects with uncertain speed and direction in spatiotemporal databases[J].Journal of Geographical Systems,2014,16(2):139-160.

[2]Nguyen T,He Zhen,Zhang Rui,et al.Boosting moving object indexing through velocity partitioning[J].Proceedings of the VLDB Endowment,2012,5(9):860-871.

[3]?idlauskas D,?altenis S,Jensen C S.Processing of extreme moving-object update and query workloads in main memory[J].The VLDB Journal,2014,23(5):817-841.

[4]?idlauskas D,?altenis S,Jensen C S.Parallel main-memory indexing for moving-object query and update workloads[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,Scottsdale,USA,May 20-24,2012.New York:ACM,2012:37-48.

[5]Yiu M L,Tao Yufei,Mamoulis N.The B dual-tree:indexing moving objects by space filling curves in the dual space[J].The VLDB Journal,2008,17(3):379-400.

[6]?idlauskas D,?altenis S,Christiansen C W,et al.Trees or grids?:indexing moving objects in main memory[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,Seattle,USA,Nov 4-6,2009.NewYork:ACM,2009:236-245.

[7]Nguyen-Dinh L V,Aref W G,Mokbel M.Spatio-temporal access methods:part 2(2003—2010)[J].IEEE Data Engineering Bulletin,2010,33(2):46-55.

[8]Tang Jine,Zhou Zhangbing,Ning Ke,et al.A novel spatial indexing mechanism leveraging dynamic quad-tree regional division[C]//LNEE 210:Proceeding of the 2012 International Conference on Information Technology and Software Engineering,Beijing,Dec 8-10,2012.Berlin,Heidelberg:Springer,2013:909-917.

[9]Chen Su,Ooi B C,Tan K L,et al.ST2B-tree:a self-tunable spatio-temporal B+-tree index for moving objects[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data,Vancouver,Canada,Jun 10-12,2008.New York:ACM,2008:29-42.

[10]Peleg A,Wilkie S,Weiser U.Intel MMX for multimedia PCs[J].Communications of theACM,1997,40(1):24-38.

[11]Cook S.CUDA programming:a developer's guide to parallel computing with GPUs[M].San Francisco,USA:Morgan Kaufmann Publishers Inc,2012:354-388.

[12]Husted N,Myers S,Shelat A,et al.GPU and CPU parallelization of honest-but-curious secure two-party computation[C]//Proceedings of the 29th Annual Computer Security Applications Conference,New Orleans,USA,Dec 9-13,2013.New York:ACM,2013:169-178.

[13]Lettich F,Orlando S,Silvestri C.Processing streams of spatialk-NN queries and position updates on manycore CPUs[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems,Seattle,USA,Nov 3-6,2015.New York:ACM,2015:26.

[14]Tsakalozos K,Tsangaris M,Delis A.Using the graphics processor unit to realize data streaming operations[C]//Proceedings of the 6th Middleware Doctoral Symposium,Urbana Champaign,USA,Nov 30-Dec 4,2009.New York:ACM,2009:3.

[15]Sarma A D,Gollapudi S,Najork M,et al.A sketch-based distance oracle for Web-scale graphs[C]//Proceedings of the 3rd International Conference on Web Search and Web Data Mining,New York,Feb 4-6,2010.New York:ACM,2010:401-410.

2016-08,Accepted 2016-10.

GAPI:GPUAccelerated Parallel Method for Indexing Moving Objects*

CHE Qingshou1,LI Chuanwen1+,ZHANG Yi2,DENG Qingxu1
1.School of Computer Science and Engineering,Northeastern University,Shenyang 110004,China
2.Sino-Dutch Biomedical and Information Engineering School,Northeastern University,Shenyang 110004,China
+Corresponding author:E-mail:lichuanwen@mail.neu.edu.cn

In order to eliminate the parallel performance impact caused by locking operations and improve the throughput of moving object databases,this paper proposes a GPU accelerated indexing method,based on a grid data structure,combined with quad-trees.By using GPU to count object movements and keep deciding whether a particular node should be split or child nodes of a common father should be merged,bottle necked nodes can be translated to quad-tree without interfering CPU,hence waiting time of other threads caused by locking operations raised by object data updating can be reduced.The method is simple while more adaptive to scenarios where the distribution of moving objects is skewed.It also avoids the shortcomings of existing methods that have performance bottle neck on hot area,or spend plenty of calculation resources on structure balancing.The experimental results suggest that,compared with existing indexing methods,the proposed method shows higher throughput and lower response time.The advantage is more significant under skewed distribution of moving objects.

moving object indexing;dynamic grid indexing;spatial database;GPU accelerated

10.3778/j.issn.1673-9418.1608038

*The National Natural Science Foundation of China under Grant No.61300021(國(guó)家自然科學(xué)基金);the Fundamental Research Funds for the Central Universities of China under Grant Nos.N140404008,L1519003(中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-10-19,http://www.cnki.net/kcms/detail/11.5602.TP.20161019.1458.004.html

CHE Qingshou,LI Chuanwen,ZHANG Yi,et al.GAPI:GPU accelerated parallel method for indexing moving objects.Journal of Frontiers of Computer Science and Technology,2017,11(11)：1713-1722.

A

TP391

CHE Qingshou was born in 1992.He is an M.S.candidate at School of Computer Science and Engineering,Northeastern University.His research interests include spatial databases,system software and real time system,etc.

車慶首（1992—），男，云南西疇人，東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)榭臻g數(shù)據(jù)庫(kù)，系統(tǒng)軟件，實(shí)時(shí)系統(tǒng)等。

LI Chuanwen was born in 1982.He received the Ph.D.degree from Northeastern University in 2011.Now he is an associate professor at Northeastern University,and the member of CCF.His research interests include spatial data manage,location based service and complex event processing,etc.

李傳文（1982—），男，山東煙臺(tái)人，2011年于東北大學(xué)計(jì)算機(jī)軟件與理論專業(yè)獲得博士學(xué)位，現(xiàn)為東北大學(xué)副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)榭臻g數(shù)據(jù)管理，位置服務(wù)，復(fù)雜事件處理等。在VLDB、ICDE等國(guó)際會(huì)議發(fā)表多篇論文。

ZHANG Yi was born in 1982.He received the Ph.D.degree from Northeastern University in 2014.Now he is a lecturer at Northeastern University.His research interests include multi-core embedded operating system and highperformance software design,etc.

張軼（1982—），男，遼寧沈陽(yáng)人，2014年于東北大學(xué)計(jì)算機(jī)軟件與理論專業(yè)獲得博士學(xué)位，現(xiàn)為東北大學(xué)講師，主要研究領(lǐng)域?yàn)槎嗪饲度胧讲僮飨到y(tǒng)，高性能軟件設(shè)計(jì)等。

DENG Qingxu was born in 1970.He is a professor and Ph.D.supervisor at Northeastern University,and the senior member of CCF.His research interests include multiprocessor real-time scheduling and reconfigurable computing,etc.

鄧慶緒（1970—），男，河南南陽(yáng)人，博士，東北大學(xué)教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)槎嗵幚砥鲗?shí)時(shí)調(diào)度，可重構(gòu)計(jì)算等。承擔(dān)和完成3項(xiàng)信息領(lǐng)域國(guó)家863課題。