一種基于GPU的移動對象并行處理框架

韋春丹　龔奕利　李文海，2*

1(武漢大學計算機學院　湖北 武漢 430072) 2(軟件工程國家重點實驗室　湖北 武漢 430072)

?

一種基于GPU的移動對象并行處理框架

韋春丹1龔奕利1李文海1，2*

1(武漢大學計算機學院湖北 武漢 430072)2(軟件工程國家重點實驗室湖北 武漢 430072)

PGrid是一個基于格網索引的移動對象并行處理框架。通過分析PGrid框架不利于在GPU上并行的因素，提出基于GPU的無鎖并行處理G-LFPP(GPU Based Lock Free Parallel Processing)框架。采用基于操作分解/聚類的無鎖更新策略，消除更新過程中并發控制對更新性能的影響；為了實現細粒度并行查詢，提出基于候選集映射表和查詢確認表的快速查詢索引。實驗表明，該方法更新和查詢策略有利于大規模線程并發處理更新和查詢。當移動對象的數量達到千萬級時，更新速率和查詢速率仍然可以超過每秒1100萬次和110萬次。與PGrid相比，并發處理更新和查詢的速度提高了6.61倍。

并行計算圖形處理單元異構計算格網索引移動對象數據庫

0　引　言

近年來，隨著移動互聯網、車聯網、物聯網的普及，移動端設備上涌現了眾多LBS應用。例如，在我國免費打車軟件“滴滴打車”中，服務器端持續向移動客戶端報告隨機位置特定大小范圍內所有計程車的位置和狀態。這類應用通常包括單個處理位置信息的服務器和數量巨大的移動端設備——移動對象。移動對象可持續地向服務器端發送自身的坐標等位置信息，服務器端則負責實時更新移動對象的位置信息并響應對移動對象的查詢請求。隨著移動對象數量增多、更新/查詢頻率的提高，服務器端的工作負載也將顯著增加，在實時性和響應速度上挑戰服務器端的處理能力，基于CPU的移動對象并行處理技術已經越來越難以滿足LBS的應用需求。

自從GPGPU(General Purpose GPU)的概念被提出之后，NVIDIA和AMD等顯卡廠商均各自推出以GPU為協處理器的通用并行計算解決方案。其中，CUDA(Computer Unified Device Architecture)是NVIDIA推出的GPU通用計算解決方案。它提供的CUDA編程語言擴展、Kernel函數等機制，將大規模并行計算邏輯通過一種簡單、有效的方式表達，成為充分利用GPU硬件實現程序加速的關鍵因素。如今，GPU已經在許多領域獲得廣泛的應用，研究基于GPU的移動對象處理技術，拓展GPU在數據庫領域的應用范圍，具有極其重要的意義。

1　相關工作

基于多核CPU的移動對象并行處理技術的研究成果已經頗為豐碩，主要包括索引結構、緩存技術和并發控制等研究方向。

在索引結構上，傳統時空數據庫廣泛采用具有深度平衡特性的R樹及其變種[1,2]。考慮到R樹MBR交疊對并發控制以及查詢性能的不利影響，基于空間填充降維思想的索引相繼出現。其中，Bx利用空間填充曲線對索引進行降維，在更新性能上取得了顯著提升。然而，由于Bx采用的MBR查詢策略使得候選對象數量增長過快，不可避免地造成了查詢效率相對低下。針對B+樹[3,4]的并發策略，也因索引層次過深、路徑遍歷太長[5]、并發處理的鎖代價等因素導致性能提升受限制。由于多線程并行處理要求任務分割的均勻性和無交疊性[6]，因此，結構相對平坦的格網結構被引入移動對象數據庫中[7,8]。

與此同時，基于GPU的并行算法也在各個領域得到了廣泛應用。Elnaggar等人[11]通過取消線程分歧策略和細粒度并行算法，使GPU遍歷NegaMax樹的速度達到了多核CPU的 80倍。文獻[12]通過研究天文數據抽取工具SExtractor中的并行性，利用剪枝策略使SExtractor在GPU上的處理性能比CPU版本高出6倍。文獻[13]通過將決策樹轉換為完全平衡的范圍樹，實現線程負載均衡，使得網絡流量分類算法性能相比其CPU版本提高了16倍。

最近幾年，GPU也被越來越多地應用于數據挖掘和機器學習領域。文獻[16]通過Kernel函數的融合和分裂算法，解決了利用GPU查詢數據倉庫時數據傳輸開銷過大的問題。文獻[17]利用GPU將機器學習中的卷積和深層神經網絡算法的速度提高了450倍。深度信念網絡是深度學習中進行數據建模的強有力工具，基于GPU的深度信念網絡[18]版本執行速度比CPU版本快7到11倍。Rathi等人[19]將XML數據結構進行反串行化，實現了GPU線程在XML數據并發執行數據挖掘算法。

綜上所述，面向LBS的移動對象處理技術研究已在索引結構、并發控制策略等層次深入展開，基于GPU的并行算法也在各個領域獲得了廣泛應用。因而研究基于GPU的移動對象并行處理技術，拓展GPU在數據庫領域的應用范圍，具有較強的理論研究價值和現實意義。

2　GPU并行計算概述

圖形處理單元[21]GPU是顯卡的計算核心，原本用以分擔中央處理器CPU的二維和三維圖形計算任務。通用計算GPU技術致力于利用可編程GPU執行CPU的通用計算任務。GPU具有計算能力強大、體積小、功耗低、成本低的優勢，目前已經成為傳統超級計算機的替代品，并且已經被大部分應用軟件和操作系統采納為第二個通用處理器。

2.1GPU架構與性能分析

GPU強大的計算能力源于它的體系結構和CPU的區別。作為通用處理單元，CPU通常只有若干(2～16)個算術邏輯單元，并且設計重心被放在復雜的緩存結構以及分支預測、亂序發射等控制邏輯上。相比之下，GPU沒有復雜的緩存和控制邏輯，GPU芯片上大部分晶體管都服務于算術邏輯單元。這些架構差異決定了GPU雖然在靈活性和通用性上不如CPU，但是浮點計算能力卻遠遠勝出。與CPU相比，GPU的緩存相對較小，GPU核心和顯存之間數據交換很大程度依賴于簡單的顯存訪問，嚴重影響到GPU的計算效率。為了解決這個問題，GPU架構中引入了兩個特性：首先，設計較大的顯存帶寬來減少訪問顯存的等待時間；其次，GPU通過同時并發大量線程來彌補架構簡單帶來的不足。當某個線程在等待訪存結果時，調度器會立即阻塞該線程，將另外的線程切換到GPU核心上執行。快速切換正在執行的線程可以掩蓋訪存延遲，使得GPU的計算性能不會因為頻繁的訪存請求而降低。

2.2并行計算平臺CUDA

計算機統一設備架構[20]CUDA是NVIDIA面向GPGPU的一整套解決方案，在本質上是一個由CPU和GPU組成的異構計算平臺。NVIDIA提供了一種基于C/C++語言的擴展編程語言——CUDA C/C++，用于在CUDA平臺上開發GPU代碼。CUDA C/C++ 是應用最廣泛的CUDA編程語言，也是本文開發CUDA程序的編程語言。

CUDA采用一種分層的編程模型來組織線程。在開始計算之前，開發人員為程序配置自定義數量的線程，并且設計線程與數據的映射規則。在計算過程中，線程被劃分為若干線程塊(Block)，每個Block被映射到GPU上的一組處理單元上。同一個Block內的線程會被同時創建、銷毀。Block之間互不相干，所有Block根據GPU的具體硬件規格并發或者順序地被激活。被Block映射到的硬件實現被稱為流式多處理器SMX(Streaming Multiprocessor)，每個SMX包含若干個標量處理器SP(Scalar Processor)，SP也被稱為CUDA核心。SP是具體計算指令的執行單位，SMX是擁有完整計算資源的最小單位。當控制器將一個Block分配給一個SMX之后，SMX中的SP會并行執行所有線程中的指令。一個支持CUDA計算的NVIDIA顯卡中至少包含一個SMX。

CUDA的線程組織模型有利于開發人員充分利用GPU的計算資源，細化并行計算的粒度，并且有效地解決了實現線程控制時遇到的最大問題——硬件的不對等性，從而使同樣的CUDA程序能夠高效地在硬件規格不同的GPU上執行。

3　PGrid并行處理框架和瓶頸

由于多核CPU和GPU的并行計算模型不相同，PGrid雖然在多核CPU上表現優秀，但不能直接應用在GPU平臺上。因此，本節主要分析PGrid框架中不利于在GPU上并行的因素。

3.1更新和查詢請求定義

3.2格網索引結構

格網(Grid)索引結構是文獻[14]提出的基于空間分區的移動對象索引結構，文獻[8]在此基礎上提出了可以并發多線程并行處理更新和查詢的格網索引結構(PGrid)。

在格網索引中，移動對象位置表示模型采用點模型，并將應用場景抽象為二維矩形歐氏空間。二維歐式空間被劃分為均勻大小的單元格(Cell)。由于應用場景的大小不變，因此，可以通過調整Cell的大小來調整被劃分出來的Cell總數。

移動對象通過位置坐標與Cell映射。格網索引結構的索引只有一層索引節點。當格網被劃分好之后，索引節點不需要進行分裂或者合并。因此，格網索引的索引層次比較淺，索引路徑長度均勻，維護操作比樹型索引簡單，維護的時間開銷也比較小。

格網索引的組織方式如圖1所示。在實現過程中，每個Cell包含一個Bucket的序列，每個Bucket是一個固定長度的數組，用以存儲移動對象。為了通過移動對象標識符直接查找移動對象，PGrid框架在主索引結構基礎上增加了一個副索引。副索引是存放移動對象元數據信息的哈希表，移動對象元數據包括移動對象所屬的Cell、Bucket指針以及對象在Bucket中存儲的位置。

圖1　格網索引結構組織方式

3.3PGrid不利于GPU并行的因素分析

(1) 更新瓶頸：線程相關和線程分歧

基于格網索引的移動對象更新請求可以分為兩種基本類型：跨Cell更新和原地更新。跨Cell更新是指導致移動對象更新前后的位置不在同一個Cell里的更新請求，處理跨Cell更新請求需要將移動對象從舊Cell里刪除，然后插入新Cell里。原地更新是指移動對象更新前后，位置仍然在同一個Cell里的更新請求，只需要刷新移動對象的位置坐標、時間戳。

PGrid并行處理更新請求的方式是將Cell與線程映射，每個Cell中的移動對象所提交的更新請求由該Cell映射到的線程負責處理。由于跨Cell更新的請求之間會存在數據相關，因此需要對Cell上鎖進行并發控制。并發更新的線程規模越大，發生鎖沖突的概率就越大，并發線程更新的效率反而會降低。此外，當GPU線程并發處理跨Cell更新和原地更新請求時，會導致線程分歧。

(2) 查詢瓶頸：粗粒度并行

在PGrid框架中，查詢請求屬于范圍查詢，包含在查詢范圍內部或者與查詢范圍邊界相交的Cell，稱為被查詢覆蓋到的Cell。其中，完全包含在查詢范圍內的Cell屬于完全被覆蓋，與查詢范圍邊界相交的Cell，屬于部分被覆蓋。完全被覆蓋和部分被覆蓋的Cell內的移動對象構成了查詢請求的目標集。

當進行并行查詢時，PGrid將查詢請求與線程映射，每個線程需要遍歷與之映射的查詢請求的目標集。若目標集是部分被覆蓋的，還需要將移動對象坐標與查詢范圍進行比較。由于GPU的工作頻率比CPU低很多，因此單個GPU線程處理一個查詢請求的速度就要比單個CPU線程慢很多，而且單個查詢請求內部的并行性并沒有得到開發。此外，由于處理部分被覆蓋Cell和完全被覆蓋Cell中移動對象的指令不一致，因此會出現線程分歧。綜上，粗粒度并行方式和線程分歧，導致PGrid的并行查詢策略無法在GPU上獲得良好的性能。

4　基于GPU的無鎖并行處理框架G-LFPP

通過對PGrid的分析，本文提出了基于GPU的無鎖并行處理G-LFPP框架。

4.1G-LFPP工作方式

利用NVIDIA Kpeler架構GPU的Hyper-Q特性，G-LFPP可以使三個Kernel函數并發工作：分發Kernel、更新Kernel、查詢Kernel。配置給這三個Kernel的GPU線程，分別稱為分發線程、更新線程、查詢線程。

G-LFPP工作流程如圖2所示，更新/查詢請求首先到達主機內存，分發Kernel根據先來先服務(FCFS)的原則從主機內存中獲取更新/查詢請求，進行預處理并寫入更新/查詢緩沖區。更新Kernel和查詢Kernel分別從更新、查詢緩沖區獲取相應的請求。

圖2　G-LFPP工作流程

G-LFPP框架采用緩存和批處理技術，從移動端發送進來的更新/查詢請求會被緩存在主機內存上的請求隊列里。分發Kernel每隔一段時間從請求隊列中獲取一批請求，這些被分批獲取的請求被稱為請求隊列片段。

在運行時，分發Kernel與更新Kernel通過更新緩沖區進行同步，分發Kernel與查詢Kernel通過查詢緩沖區進行同步，而更新Kernel與查詢Kernel通過分發Kernel間接地進行同步。

4.2更新算法

在更新算法中，本文將Cell與GPU線程進行映射。由于處理跨Cell更新請求時，需要在舊Cell和新Cell里分別執行刪除、插入兩個子操作。當線程將移動對象插入新Cell時，就會與負責更新新Cell的線程發生沖突。換言之，更新線程處理跨Cell更新請求時，不能在自己所負責的Cell內一步到位完成所有操作，還需要在其他線程所負責的Cell內執行部分操作。因此，如果將對新Cell進行插入的子操作轉移給負責新Cell的線程，則Cell沖突的問題就可以解決了。為了實現子操作轉移，首先要將跨Cell更新操作分解為刪除和插入兩個子操作。此時，在G-LFPP框架中，更新操作被分為三種基本類型：刪除、插入、原地更新。

在分發階段，分發線程首先判斷更新請求的基本類型。如果屬于跨Cell更新，則將更新操作分解為刪除和插入子操作之后，再寫入更新緩沖區，這個過程被稱為更新操作的分解。

更新緩沖區的結構如圖3所示，分發Kernel預處理后的輸出結果分別寫入刪除、插入、原地更新隊列里。刪除、插入、原地更新隊列分別與Cell映射。

圖3　緩沖隊列與Cell映射

在更新Kernel中，更新線程分三個階段處理本周期的所有更新請求：1) 執行完本更新周期的所有刪除操作，然后進行線程同步；2) 執行所有的插入操作，然后進行線程同步；3) 執行所有的原地更新操作，然后進行線程同步。由于更新線程之間訪問的數據都是相互獨立的，因此G-LFPP在更新過程中并不需要對線程上鎖。

4.3查詢算法

1) 雙索引策略

在G-LFPP框架中，更新Kernel和查詢Kernel并發執行更新和查詢操作。為了實現查詢時無掛起更新，G-LFPP采用了文獻[7]提出的雙索引思想，在框架中維護兩個索引：索引0和索引1。更新Kernel和查詢Kernel周期性地在這兩個索引上輪替工作。輪替工作模式可以描述如下：

在第k周期，更新Kernel在索引kmod 2上執行更新操作，查詢Kernel在索引(k+1) mod 2上執行查詢操作。

在雙索引結構中，每一個更新請求都需要在兩個索引上得到體現，相比單索引結構，更新Kernel的工作負載增加了一倍。

2) 候選集映射表及映射規則

為了開發查詢過程中的并行性，實現細粒度并行，本文提出了候選集映射算法。所謂候選集映射，就是在每個查詢周期中將候選集中的移動對象與查詢線程進行映射。在這里，候選Cell集合是指每個查詢周期中被所有查詢請求所覆蓋到的Cell的集合，候選移動對象集合是候選Cell集合中所有移動對象的集合，簡稱候選集。

候選集是一個邏輯集合，集合中的移動對象實際分布在不同的候選Cell里。為了獲得這些移動對象的存儲位置，候選集映射算法借助一個輔助的候選集映射表，將候選Cell中已經存儲了移動對象的存儲位置都映射到查詢線程上。

候選集映射表如圖4所示，候選集中的移動對象通過映射參數和映射規則，間接地與查詢線程映射。

圖4　候選集映射表

候選集映射規則包含兩個步驟：

第一步，候選集映射表中的索引號與查詢線程進行映射，映射關系γ定義如式(1)所示：

∈γdi∈Dgj∈Gimodj=j

(1)

其中，D是候選集映射表中索引號的集合，G是查詢線程的集合，映射關系γ是滿射。

第二步，將候選Cell集合中已經保存有移動對象的存儲位置與候選集映射表中的索引號進行單射。

在候選集映射表中，每一列記錄候選Cell中一個存儲位置的映射參數。其中，每列第一行記錄的是候選集映射表中的索引號d，第二行記錄的是候選Cell的索引號c，第三行記錄的是已經存儲了移動對象的存儲位置的索引號r。第二、第三行參數經過式(2)和式(3)所示的存儲位置換算公式，就可以得到Cell中一個已經存儲有移動對象的位置。

(2)

y=rmodL

(3)

其中，x表示Bucket在Cell中的索引號；y表示Bucket中的位置；L是Bucket長度。

3) 候選集映射表生成算法

候選集映射表的生成過程包含兩個階段：

第一階段由分發Kernel負責處理。當分發Kernel從主機內存中獲取查詢請求分段之后，首先把本周期的所有查詢請求所覆蓋到的Cell添加到候選Cell列表Candidate_List中，候選Cell列表是候選Cell集合的實現形式。然后，將覆蓋到每個候選Cell的所有查詢請求寫入查詢確認表Confirmation_Table里。查詢確認表是一個二維表，表中每一行對應候選Cell的一個私有查詢請求隊列，通過對應的私有查詢請求隊列可以獲取本周期中覆蓋到某個候選Cell的所有查詢請求。候選Cell列表以及查詢確認表最后被寫入查詢緩沖區。

第二階段由查詢Kernel負責處理。查詢Kernel從查詢緩沖區中獲取候選Cell列表和查詢確認表，然后通過下列三個步驟生成候選集映射表。

第一步，將每個候選Cell中移動對象的數目寫入數組Bound_Table中。數組Bound_Table是映射邊界表的輸入數組，為了方便下面生成映射邊界表，令Bound_Table[0]等于0，Bound_Table[i]等于第i個候選Cell的移動對象數目。

第二步，生成映射邊界表。映射邊界表記錄候選Cell中已經存儲了移動對象的存儲位置映射到候選集映射表索引號的上界up_bound和下界down_bound，簡稱為映射上界和映射下界。當候選Cell中的移動對象個數為m時，它需要映射到候選集映射表中的m個索引號上。當已知映射下界down_bound之后，映射上界up_bound就可以通過計算公式down_bound+m-1得到。

在候選Cell列表中，只有當位置i-1中的候選Cell的映射上界確定之后，才能確定位置i中的候選Cell的映射下界。所以，生成映射邊界表的過程，實質上是確定候選Cell列表中每個Cell的映射下界和上界的過程。由于候選Cell的映射下界依賴于其前續的映射上界，因此，對候選Cell的映射邊界的確定只能按照候選Cell在候選Cell列表中的排列順序依次進行。

由于位置i中的候選Cell的映射下界和位置i-1中的候選Cell的映射上界保存的信息重復，為了減少存儲空間以及GPU線程訪問設備內存的次數，這兩個信息只需要保留一個即可，另一個信息可以通過計算獲得。在實現過程中，G-LFPP的邊界映射表只保存映射下界。由于候選Cell列表中第一個候選Cell的映射下界是0，因此，在前文的第一步中，令Bound_Table[0]等于0，這個值對應第一個候選Cell的映射下界。以此類推，第i個候選Cell的映射下界保存在Bound_Table[i-1]中。

映射邊界表在輸入數組Bound_Table的基礎上生成，生成映射邊界表的偽代碼如下所示：

第三步，根據映射邊界表生成候選集映射表。生成映射邊界表之后，只要將候選Cell和線程進行映射，線程就可以通過映射邊界表界定其在候選集映射表上的工作邊界。所以，映射邊界表使得GPU線程可以并行工作生成候選集映射表。生成候選集映射表的偽代碼如下所示。

4) 快速查詢索引：候選集映射表與查詢確認表

生成候選集映射表之后，查詢線程通過結合候選集映射表和查詢確認表處理本周期的所有查詢請求。

候選集映射表和查詢確認表還有另一個作用：同一周期中，當移動對象所在的Cell被兩個以上查詢請求覆蓋到時，查詢線程只需要讀取移動對象一次，就可以滿足覆蓋到該對象的所有查詢請求，從而減少查詢線程訪問設備內存的次數。

綜上所述，候選集映射表和查詢確認表有兩個重要的輔助作用：

(1) 實現細粒度的并行，減少線程分歧和線程閑置。

(2) 減少線程訪問設備內存次數。

候選集映射表在本質上是對移動對象的索引，查詢確認表是對查詢請求的索引。通過這兩個數據結構的輔助，加快了GPU線程處理查詢請求的速度。

5　實驗結果

為了驗證G-LFPP并發處理更新和查詢的能力，本文設計了三組實驗。實驗主機的CPU型號為 Intel Xeon E5-2650；主機內存容量為16 GB；主板PCI-E接口為PCI-E 3.0；GPU型號為NVIDIA Tesla K40。

操作系統版本為CentOS release 6.2 (Final)，Linux內核版本號為2.6.32-220.el6.x86_64，CUDA版本為CUDA 6.5。

實驗數據由文獻[15]給出的MOIBenchmark生成，移動對象總數為一千萬，分布方式是均勻分布。由于以下各個實驗驗證目標不同，因此其他具體實驗參數將在實驗中設定。

5.1Cell總數對性能的影響

本節實驗主要驗證在線程數量保持不變的情況下，Cell的劃分粒度分別給更新和查詢性能帶來的影響。在實驗中，實驗場景為固定大小的二維矩形區域，該矩形區域被劃分為均勻大小的Cell。當Cell的尺寸越小，即Cell的劃分粒度越細時，Cell的總數就會越大，相應地，G-LFPP框架的性能也會受到影響。

(1) 實驗參數

實驗模擬場景大小100 km×100 km；移動對象總數1千萬；移動對象分布方式為均勻分布；移動對象移動速率1～1000 m/s；更新次數4000萬；更新線程12 288；查詢次數400萬；查詢線程8192；查詢范圍邊長取實驗場景邊長的0.001，即100 km×0.001=100 m,查詢范圍大小為10 000 m2。

(2) 實驗方案

測試更新性能時，只啟動分發Kernel和更新Kernel。測試查詢性能的過程分為兩步：1) 只啟動分發Kernel和更新Krenel進行4000萬次更新；2) 終止更新Krenel，啟動查詢Kernel，進行400萬次查詢。

(3) 更新性能測試及結果分析

圖5展示了在更新線程數量不變的前提下，隨著Cell劃分粒度的變化，即Cell的總數變化時，更新性能的變化情況。從圖5中可以看到，當Cell的總數小于更新線程總數時，隨著Cell數量的增加，更新性能獲得提升；而當Cell的總數超過更新線程總數之后，隨著Cell數量的增加，更新性能反而下降。

圖5　Cell劃分粒度對更新性能的影響

由于在G-LFPP框架中，Cell與更新線程是滿射關系，當Cell數量小于更新線程數量時，更新Krenel中還有可用的更新線程。隨著Cell總數的增加，參與更新操作的線程數量也隨著增加。此外，由于每個周期更新請求分段長度固定，當Cell總數增加之后，每個Cell中需要進行的更新操作會相對減少，因此，在這個階段中，更新性能也隨著Cell總數的增加而提升。

當Cell總數超過更新線程數量時，更新Kernel中已經沒有多余的更新線程。隨著Cell總數的進一步增加，映射到每一個更新線程上的Cell也增加，每個更新線程需要負責更新的Cell數目增加。因此，在這種情況下，更新性能反而會隨著Cell總數的增加而下降。

綜上所述，在更新線程數量不變的前提下，當Cell的數量和更新線程數量大致相等時，更新Krenel達到最優性能。在本次實驗中，更新線程數量為12 288，因此，當Cell總數為16 384時，更新速率最快。而當Cell數量小于或者大于更新線程數量時，更新性能均會下降。

(4) 查詢性能測試及結果分析

實驗結果如圖6所示，隨著Cell總數不斷增加，查詢性能呈現出和更新性能相似的趨勢，先提升后下降。

圖6　Cell劃分粒度對查詢性能的影響

查詢過程中，生成映射邊界表和候選集映射表的時間開銷與候選Cell集合的大小相關，而查詢線程遍歷候選集中移動對象的時間開銷與候選集大小有關。

為了方便分析，設x為候選Cell集合大小，y為候選集大小，生成邊界映射表和候選集映射表的時間開銷為f(x)，查詢線程遍歷候選集中移動對象的時間開銷為g(y)。則每個周期查詢時間的計算公式如式(4)所示：

t=f+g+C

(4)

其中，C是常數，表示查詢過程中不會受Cell尺寸影響的固定時間開銷。查詢時間隨著Cell尺寸變化如式(5)所示：

Δt=Δf+Δg

(5)

隨著Cell尺寸的縮小，候選Cell集合規模保持增加，但是候選集的規模卻一直減小。因此，有Δf的符號為正，Δg的符號為負。此時，查詢時間變化如式(6)所示：

Δt=|Δf|-|Δg|

(6)

在開始階段，隨著Cell尺寸的減小，候選Cell集合規模增加的速度小于候選集規模減小的速度。此時有|Δf|<|Δg|，Δt<0，查詢時間遞減，查詢性能提升。

隨著Cell尺寸進一步減小，候選Cell集合規模增加的速度加快，而候選集規模減小的速度放緩。此時有|Δf|>|Δg|，Δt>0，查詢時間開銷遞增，查詢性能下降。

綜上所述，隨著Cell尺寸的縮小，查詢性能先提升后下降。實驗結果顯示，當Cell總數在26萬左右時，查詢性能接近最大值。

5.2線程數量對性能的影響

本節實驗主要驗證當Cell劃分粒度不變，即Cell的總數不變的情況下，線程規模對更新和查詢性能的影響。

(1) 實驗參數

實驗模擬場景大小100 km×100 km；移動對象總數1千萬；移動對象分布方式為均勻分布；移動對象移動速率1～1000 m/s；更新次數4000萬；查詢次數400萬；查詢范圍10 000平方米；Cell總數65 536。

由于G-LFPP在運行時需要進行Block之間的同步，因此在Tesla K40 GPU上只能并發15個Block。并且，為了避免分發Kernel成為瓶頸，需要為它配置3個Block。所以，在實驗中更新和查詢Kernel能夠獲得的Block數量最多為12個，可以使用的線程數量上限為12 288。

(2) 實驗結果分析

實驗結果如圖7所示。當線程數量從1024增加到12 288時，查詢性能獲得持續提升。這是因為每個周期候選集中移動對象的數量仍然遠遠超過線程數量，當增加線程時，并行處理的速度就會有提高。而對于更新Kernel來說，當更新線程為9126個時，更新速度達到峰值，接近每秒1800萬次；之后繼續增加更新線程，則更新速度逐漸變慢。這是由于Cell的總數不是更新線程數量的整數倍。每個周期更新中，都會有更新線程閑置，隨著更新線程數量增加，閑置線程也增加。

圖7　線程數量對更新和查詢性能的影響

5.3G-LFPP與PGrid性能比較

本節實驗由5次實驗組成，每次實驗采用不同的更新查詢比，比較 G-LFPP和PGrid并發處理更新和查詢請求性能。其中，在一次實驗中，總更新次數和總查詢次數的比率，稱為更新查詢比。

(1) 實驗參數

實驗模擬場景大小100 km×100 km；移動對象總數1千萬；移動對象分布方式為均勻分布；移動對象移動速率1～1000m/s；更新次數為4000萬次，更新查詢比從100∶10增加到100∶1，即查詢次數從400萬次減少到40萬次；查詢范圍：10 000平方米。

(2) 實驗方案

總共進行5次實驗，每次實驗中G-LFPP和PGrid處理相同數量的更新和查詢請求，但是每次實驗之間的更新查詢比不相同。為G-LFPP配置的GPU線程總數為15 360，其中分發Kernel的線程數量為3072，更新Kernel的線程數量為4096，查詢Kernel的線程數量為8192。為PGrid配置的CPU線程總數為16，其中分發線程數量為2，更新線程數量為4，查詢線程數量為10。

(3) 實驗結果與分析

對G-LFPP和PGrid來說，處理查詢請求的操作都是計算量最大的部分。因此，在分配線程時，查詢線程的數量都會多于更新線程。在G-LFPP和PGrid運行時，查詢線程的比例分別占總線程數的53.33%和75%，這是由于PGrid單個Cell的尺寸比較大，即每個Cell內包含的移動對象數量比較多。這就意味著查詢的待選集規模比較大，查詢的負載相應地要大很多，因而PGrid中處理查詢請求的線程比例高于G-LFPP。

實驗結果如表1所示，從表1中可以看到，當移動對象總數為1000萬、更新次數為4000萬、查詢次數為400萬次，即更新查詢比為10∶1時，G-LFPP同時處理更新和查詢消耗的時間為3.1175秒，每秒處理的更新和查詢次數分別為1283萬和128萬；而PGrid消耗時間為20.6018秒，每秒處理的更新和查詢次數分別為194萬和19.4萬。此時，G-LFPP的處理速度是PGrid的6.61倍。

表1　G-LFPP與PGrid性能比較

當總更新次數不變時，隨著更新查詢比的增加，總查詢次數會相應減少，G-LFPP的加速比也隨之減小。這是因為，G-LFPP主要的提速部分在查詢部分，查詢數量越大，G-LFPP的提速效果就越明顯，加速比越大；反之，加速比越小。

6　結　語

基于操作分解/聚類的無鎖更新策略和基于快速查詢索引的查詢策略是G-LFPP框架的核心，這個兩個策略使得G-LFPP能夠充分利用GPU大規模并發的線程提高處理效率，與PGrid相比，處理速度提高了6.61倍。

但是，本文的算法均以移動對象均勻分布為假設前提，當移動對象呈高斯分布時，處理更新和查詢的線程之間會出現工作負載不均衡，這將是基于GPU的移動對象并行處理框架需要進一步解決的問題。

[1] Lu C T,Dai J,Jin Y,et al.GLIP:A concurrency control protocol for clipping indexing [J].IEEE Transactions on Knowledge and Data Engineering,2009,21(5):714-728.

[2] Song S I,Kim Y H,Yoo J S.An enhanced concurrency control scheme for multidimensional index structures [J].IEEE Transactions on Knowledge and Data Engineering,2004,16(1):97-111.

[3] Graefe G,Halim F,Idreos S,et al.Concurrency control for adaptive indexing [C]//Proceedings of the VLDB Endowment,2012,5(7):656-667.

[4] Lomet D.Simple,robust and highly concurrent B-trees with node deletion [C]//Proceedings of the 20th International Conference on Data Engineering (ICDE).Boston,MA,USA,2004:18-27.

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

[6] Popa I S,Zeitouni K,Oria V,et al.Indexing in-network trajectory flows [J].The VLDB Journal.2011,20(5):643-669.

[11] Elnaggar A A,Gadallah M,Aziem M A,et al.Enhanced parallel NegaMax tree search algorithm on GPU [C]//Proceedings of 2014 International Conference on Informatics and Computing (PIC).Shanghai,2014:546-550.

[12] Baoxue Zhao,Qiong Luo,Chao Wu.Parallelizing astronomical source extraction on the GPU [C]//Proceedings of 2013 IEEE 9th International Conference on eScience.Beijing,2013:88-97.

[13] Zhou S J,Nittoor P R,Prasanna V K.High-performance traffic classification on GPU [C]//Proceedings of 2014 IEEE 26th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD).Jussieu,2014:97-104.

[14] Saulys D,Johansen J M,Christiansen C W.Indexing moving objects in main memory [C]//Proceedings of 2008 Annual IEEE Conference on Student Paper.Aalborg,2008:1-5.

[15] Chen S,Jesen C S,Lin D.A benchmark for evaluating moving object indexes [C]//Proceedings of the VLDB Endowment,2008,1(2):1574-1585.

[16] Wu H C,Diamos G,Wang J,et al.Optimizing data warehousing applications for GPUs using Kernel fusion/fission [C]//Proceedings of 2012 IEEE 26th International Conference on Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW).Shanghai,2012:2433-2442.

[17] Yunji Chen,Tao Luo,Shaoli Liu,et al.A machine-learning supercomputer [C]//Proceedings of 2014 47th Annual IEEE/ACM International Symposium Conference on Microarchitecture.Cambridge,2014:609-622.

[18] Zhilu Chen,Jing Wang,Haibo He,et al.A fast deep learning system using GPU [C]//Proceedings of 2014 IEEE International Symposium Conference on Circuits and Systems (ISCAS).Melbourne VIC,2014:1552-1555.

[19] Rathi S,Dhote C A,Bangera V.Accelerating XML mining using graphic processors [C]//Proceedings of 2014 International Conference on Control,Instrumentation,Communication and Computational Technologies (ICCICCT).Kanyakumari,2014:144-148.

[20] Jason Sanders,Edward Kandrot.CUDA by example:an introduction to General-Purpose GPU programming [M].Massachusetts:Addison-Wesley Professional,2010.

[21] 仇德元.GPGPU編程技術 [M].北京:機械工業出版社,2011.

A GPU-BASED MOVING OBJECT PARALLEL PROCESSING FRAMEWORK

Wei Chundan1Gong Yili1Li Wenhai1,2*

1(SchoolofComputer,WuhanUniversity,Wuhan430072,Hubei,China)2(StateKeyLaboratoryofSoftwareEngineering,Wuhan430072,Hubei,China)

PGrid is a parallel processing framework for moving objects based on grid index.This paper proposes a GPU-based lock-free parallel processing (G-LFPP) framework on the basis of analysing the factors of PGrid framework not being conducive to parallel on GPU.It uses a lock-free update strategy,which is based on operation splitting/clustering,to eliminate the impact of concurrency control on update performance in updating process.In order to implement fine-grained parallel queries,the paper also presents a fast query index composed of candidate set mapping table and query confirmation table.Experiments show that the proposed update and query strategies avail the large-scale threads in processing updates and queries concurrently.Whilst the number of moving objects reaches a level of ten million,the update and query rates can still be over 11 million per second and 1.1 million per second respectively,which are 6.61 times higher than those of PGrid.

Parallel computingGPUHeterogeneous computingGrid indexMoving object database

2015-04-29。國家自然科學基金項目(61100020);華為公司創新研究計劃資助項目。韋春丹，碩士，主研領域：并行計算。龔奕利，副教授。 李文海，副教授。

TP3

A

10.3969/j.issn.1000-386x.2016.10.050