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

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

1(武漢大學(xué)計(jì)算機(jī)學(xué)院　湖北 武漢 430072) 2(軟件工程國家重點(diǎn)實(shí)驗(yàn)室　湖北 武漢 430072)

?

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

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

1(武漢大學(xué)計(jì)算機(jī)學(xué)院湖北 武漢 430072)2(軟件工程國家重點(diǎn)實(shí)驗(yàn)室湖北 武漢 430072)

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

并行計(jì)算圖形處理單元異構(gòu)計(jì)算格網(wǎng)索引移動對象數(shù)據(jù)庫

0　引　言

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

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

1　相關(guān)工作

基于多核CPU的移動對象并行處理技術(shù)的研究成果已經(jīng)頗為豐碩，主要包括索引結(jié)構(gòu)、緩存技術(shù)和并發(fā)控制等研究方向。

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

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

最近幾年，GPU也被越來越多地應(yīng)用于數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域。文獻(xiàn)[16]通過Kernel函數(shù)的融合和分裂算法，解決了利用GPU查詢數(shù)據(jù)倉庫時(shí)數(shù)據(jù)傳輸開銷過大的問題。文獻(xiàn)[17]利用GPU將機(jī)器學(xué)習(xí)中的卷積和深層神經(jīng)網(wǎng)絡(luò)算法的速度提高了450倍。深度信念網(wǎng)絡(luò)是深度學(xué)習(xí)中進(jìn)行數(shù)據(jù)建模的強(qiáng)有力工具，基于GPU的深度信念網(wǎng)絡(luò)[18]版本執(zhí)行速度比CPU版本快7到11倍。Rathi等人[19]將XML數(shù)據(jù)結(jié)構(gòu)進(jìn)行反串行化，實(shí)現(xiàn)了GPU線程在XML數(shù)據(jù)并發(fā)執(zhí)行數(shù)據(jù)挖掘算法。

綜上所述，面向LBS的移動對象處理技術(shù)研究已在索引結(jié)構(gòu)、并發(fā)控制策略等層次深入展開，基于GPU的并行算法也在各個(gè)領(lǐng)域獲得了廣泛應(yīng)用。因而研究基于GPU的移動對象并行處理技術(shù)，拓展GPU在數(shù)據(jù)庫領(lǐng)域的應(yīng)用范圍，具有較強(qiáng)的理論研究價(jià)值和現(xiàn)實(shí)意義。

2　GPU并行計(jì)算概述

圖形處理單元[21]GPU是顯卡的計(jì)算核心，原本用以分擔(dān)中央處理器CPU的二維和三維圖形計(jì)算任務(wù)。通用計(jì)算GPU技術(shù)致力于利用可編程GPU執(zhí)行CPU的通用計(jì)算任務(wù)。GPU具有計(jì)算能力強(qiáng)大、體積小、功耗低、成本低的優(yōu)勢，目前已經(jīng)成為傳統(tǒng)超級計(jì)算機(jī)的替代品，并且已經(jīng)被大部分應(yīng)用軟件和操作系統(tǒng)采納為第二個(gè)通用處理器。

2.1GPU架構(gòu)與性能分析

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

2.2并行計(jì)算平臺CUDA

計(jì)算機(jī)統(tǒng)一設(shè)備架構(gòu)[20]CUDA是NVIDIA面向GPGPU的一整套解決方案，在本質(zhì)上是一個(gè)由CPU和GPU組成的異構(gòu)計(jì)算平臺。NVIDIA提供了一種基于C/C++語言的擴(kuò)展編程語言——CUDA C/C++，用于在CUDA平臺上開發(fā)GPU代碼。CUDA C/C++ 是應(yīng)用最廣泛的CUDA編程語言，也是本文開發(fā)CUDA程序的編程語言。

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

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

3　PGrid并行處理框架和瓶頸

由于多核CPU和GPU的并行計(jì)算模型不相同，PGrid雖然在多核CPU上表現(xiàn)優(yōu)秀，但不能直接應(yīng)用在GPU平臺上。因此，本節(jié)主要分析PGrid框架中不利于在GPU上并行的因素。

3.1更新和查詢請求定義

3.2格網(wǎng)索引結(jié)構(gòu)

格網(wǎng)(Grid)索引結(jié)構(gòu)是文獻(xiàn)[14]提出的基于空間分區(qū)的移動對象索引結(jié)構(gòu)，文獻(xiàn)[8]在此基礎(chǔ)上提出了可以并發(fā)多線程并行處理更新和查詢的格網(wǎng)索引結(jié)構(gòu)(PGrid)。

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

移動對象通過位置坐標(biāo)與Cell映射。格網(wǎng)索引結(jié)構(gòu)的索引只有一層索引節(jié)點(diǎn)。當(dāng)格網(wǎng)被劃分好之后，索引節(jié)點(diǎn)不需要進(jìn)行分裂或者合并。因此，格網(wǎng)索引的索引層次比較淺，索引路徑長度均勻，維護(hù)操作比樹型索引簡單，維護(hù)的時(shí)間開銷也比較小。

格網(wǎng)索引的組織方式如圖1所示。在實(shí)現(xiàn)過程中，每個(gè)Cell包含一個(gè)Bucket的序列，每個(gè)Bucket是一個(gè)固定長度的數(shù)組，用以存儲移動對象。為了通過移動對象標(biāo)識符直接查找移動對象，PGrid框架在主索引結(jié)構(gòu)基礎(chǔ)上增加了一個(gè)副索引。副索引是存放移動對象元數(shù)據(jù)信息的哈希表，移動對象元數(shù)據(jù)包括移動對象所屬的Cell、Bucket指針以及對象在Bucket中存儲的位置。

圖1　格網(wǎng)索引結(jié)構(gòu)組織方式

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

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

基于格網(wǎng)索引的移動對象更新請求可以分為兩種基本類型：跨Cell更新和原地更新?？鏑ell更新是指導(dǎo)致移動對象更新前后的位置不在同一個(gè)Cell里的更新請求，處理跨Cell更新請求需要將移動對象從舊Cell里刪除，然后插入新Cell里。原地更新是指移動對象更新前后，位置仍然在同一個(gè)Cell里的更新請求，只需要刷新移動對象的位置坐標(biāo)、時(shí)間戳。

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

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

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

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

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

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

4.1G-LFPP工作方式

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

G-LFPP工作流程如圖2所示，更新/查詢請求首先到達(dá)主機(jī)內(nèi)存，分發(fā)Kernel根據(jù)先來先服務(wù)(FCFS)的原則從主機(jī)內(nèi)存中獲取更新/查詢請求，進(jìn)行預(yù)處理并寫入更新/查詢緩沖區(qū)。更新Kernel和查詢Kernel分別從更新、查詢緩沖區(qū)獲取相應(yīng)的請求。

圖2　G-LFPP工作流程

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

在運(yùn)行時(shí)，分發(fā)Kernel與更新Kernel通過更新緩沖區(qū)進(jìn)行同步，分發(fā)Kernel與查詢Kernel通過查詢緩沖區(qū)進(jìn)行同步，而更新Kernel與查詢Kernel通過分發(fā)Kernel間接地進(jìn)行同步。

4.2更新算法

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

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

更新緩沖區(qū)的結(jié)構(gòu)如圖3所示，分發(fā)Kernel預(yù)處理后的輸出結(jié)果分別寫入刪除、插入、原地更新隊(duì)列里。刪除、插入、原地更新隊(duì)列分別與Cell映射。

圖3　緩沖隊(duì)列與Cell映射

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

4.3查詢算法

1) 雙索引策略

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

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

在雙索引結(jié)構(gòu)中，每一個(gè)更新請求都需要在兩個(gè)索引上得到體現(xiàn)，相比單索引結(jié)構(gòu)，更新Kernel的工作負(fù)載增加了一倍。

2) 候選集映射表及映射規(guī)則

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

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

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

圖4　候選集映射表

候選集映射規(guī)則包含兩個(gè)步驟：

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

∈γdi∈Dgj∈Gimodj=j

(1)

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

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

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

(2)

y=rmodL

(3)

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

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

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

第一階段由分發(fā)Kernel負(fù)責(zé)處理。當(dāng)分發(fā)Kernel從主機(jī)內(nèi)存中獲取查詢請求分段之后，首先把本周期的所有查詢請求所覆蓋到的Cell添加到候選Cell列表Candidate_List中，候選Cell列表是候選Cell集合的實(shí)現(xiàn)形式。然后，將覆蓋到每個(gè)候選Cell的所有查詢請求寫入查詢確認(rèn)表Confirmation_Table里。查詢確認(rèn)表是一個(gè)二維表，表中每一行對應(yīng)候選Cell的一個(gè)私有查詢請求隊(duì)列，通過對應(yīng)的私有查詢請求隊(duì)列可以獲取本周期中覆蓋到某個(gè)候選Cell的所有查詢請求。候選Cell列表以及查詢確認(rèn)表最后被寫入查詢緩沖區(qū)。

第二階段由查詢Kernel負(fù)責(zé)處理。查詢Kernel從查詢緩沖區(qū)中獲取候選Cell列表和查詢確認(rèn)表，然后通過下列三個(gè)步驟生成候選集映射表。

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

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

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

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

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

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

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

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

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

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

(1) 實(shí)現(xiàn)細(xì)粒度的并行，減少線程分歧和線程閑置。

(2) 減少線程訪問設(shè)備內(nèi)存次數(shù)。

候選集映射表在本質(zhì)上是對移動對象的索引，查詢確認(rèn)表是對查詢請求的索引。通過這兩個(gè)數(shù)據(jù)結(jié)構(gòu)的輔助，加快了GPU線程處理查詢請求的速度。

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

為了驗(yàn)證G-LFPP并發(fā)處理更新和查詢的能力，本文設(shè)計(jì)了三組實(shí)驗(yàn)。實(shí)驗(yàn)主機(jī)的CPU型號為 Intel Xeon E5-2650；主機(jī)內(nèi)存容量為16 GB；主板PCI-E接口為PCI-E 3.0；GPU型號為NVIDIA Tesla K40。

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

實(shí)驗(yàn)數(shù)據(jù)由文獻(xiàn)[15]給出的MOIBenchmark生成，移動對象總數(shù)為一千萬，分布方式是均勻分布。由于以下各個(gè)實(shí)驗(yàn)驗(yàn)證目標(biāo)不同，因此其他具體實(shí)驗(yàn)參數(shù)將在實(shí)驗(yàn)中設(shè)定。

5.1Cell總數(shù)對性能的影響

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

(1) 實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)?zāi)M場景大小100 km×100 km；移動對象總數(shù)1千萬；移動對象分布方式為均勻分布；移動對象移動速率1～1000 m/s；更新次數(shù)4000萬；更新線程12 288；查詢次數(shù)400萬；查詢線程8192；查詢范圍邊長取實(shí)驗(yàn)場景邊長的0.001，即100 km×0.001=100 m,查詢范圍大小為10 000 m2。

(2) 實(shí)驗(yàn)方案

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

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

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

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

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

當(dāng)Cell總數(shù)超過更新線程數(shù)量時(shí)，更新Kernel中已經(jīng)沒有多余的更新線程。隨著Cell總數(shù)的進(jìn)一步增加，映射到每一個(gè)更新線程上的Cell也增加，每個(gè)更新線程需要負(fù)責(zé)更新的Cell數(shù)目增加。因此，在這種情況下，更新性能反而會隨著Cell總數(shù)的增加而下降。

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

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

實(shí)驗(yàn)結(jié)果如圖6所示，隨著Cell總數(shù)不斷增加，查詢性能呈現(xiàn)出和更新性能相似的趨勢，先提升后下降。

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

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

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

t=f+g+C

(4)

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

Δt=Δf+Δg

(5)

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

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

(6)

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

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

綜上所述，隨著Cell尺寸的縮小，查詢性能先提升后下降。實(shí)驗(yàn)結(jié)果顯示，當(dāng)Cell總數(shù)在26萬左右時(shí)，查詢性能接近最大值。

5.2線程數(shù)量對性能的影響

本節(jié)實(shí)驗(yàn)主要驗(yàn)證當(dāng)Cell劃分粒度不變，即Cell的總數(shù)不變的情況下，線程規(guī)模對更新和查詢性能的影響。

(1) 實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)?zāi)M場景大小100 km×100 km；移動對象總數(shù)1千萬；移動對象分布方式為均勻分布；移動對象移動速率1～1000 m/s；更新次數(shù)4000萬；查詢次數(shù)400萬；查詢范圍10 000平方米；Cell總數(shù)65 536。

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

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

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

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

5.3G-LFPP與PGrid性能比較

本節(jié)實(shí)驗(yàn)由5次實(shí)驗(yàn)組成，每次實(shí)驗(yàn)采用不同的更新查詢比，比較 G-LFPP和PGrid并發(fā)處理更新和查詢請求性能。其中，在一次實(shí)驗(yàn)中，總更新次數(shù)和總查詢次數(shù)的比率，稱為更新查詢比。

(1) 實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)?zāi)M場景大小100 km×100 km；移動對象總數(shù)1千萬；移動對象分布方式為均勻分布；移動對象移動速率1～1000m/s；更新次數(shù)為4000萬次，更新查詢比從100∶10增加到100∶1，即查詢次數(shù)從400萬次減少到40萬次；查詢范圍：10 000平方米。

(2) 實(shí)驗(yàn)方案

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

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

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

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

表1　G-LFPP與PGrid性能比較

當(dāng)總更新次數(shù)不變時(shí)，隨著更新查詢比的增加，總查詢次數(shù)會相應(yīng)減少，G-LFPP的加速比也隨之減小。這是因?yàn)?，G-LFPP主要的提速部分在查詢部分，查詢數(shù)量越大，G-LFPP的提速效果就越明顯，加速比越大；反之，加速比越小。

6　結(jié)　語

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

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

[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編程技術(shù) [M].北京:機(jī)械工業(yè)出版社,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。國家自然科學(xué)基金項(xiàng)目(61100020);華為公司創(chuàng)新研究計(jì)劃資助項(xiàng)目。韋春丹，碩士，主研領(lǐng)域：并行計(jì)算。龔奕利，副教授。 李文海，副教授。

TP3

A

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