楊 銘，陳建峰

(上海市測(cè)繪院浦東分院，上海200129)

一、引 言

傳統(tǒng)的kNN查詢算法一般都是首先通過(guò)空間層次結(jié)構(gòu)找到待查詢點(diǎn)所處節(jié)點(diǎn)及其周圍節(jié)點(diǎn)，然后對(duì)這些節(jié)點(diǎn)內(nèi)的采樣點(diǎn)進(jìn)行距離計(jì)算，以此減少參與查詢的采樣點(diǎn)個(gè)數(shù)，從而提高查詢效率。此類算法通常都是串行算法，比較適合傳統(tǒng)的單核CPU系統(tǒng)，其查詢效率能在一定程度上滿足應(yīng)用需要。然而隨著三維激光掃描技術(shù)的不斷發(fā)展，所能獲得的點(diǎn)云數(shù)據(jù)量越來(lái)越大，原有的基于單核CPU的kNN查詢算法的實(shí)現(xiàn)效率已經(jīng)遠(yuǎn)遠(yuǎn)無(wú)法滿足海量點(diǎn)云數(shù)據(jù)后處理的要求。近年來(lái)，GPU硬件性能得到了飛速提升，而nVIDIA公司推出的CUDA技術(shù)更使得我們可以利用GPU高性能的并行計(jì)算能力解決許多原來(lái)無(wú)法解決的問(wèn)題。據(jù)此，本文提出了一種基于CUDA的海量點(diǎn)云數(shù)據(jù)快速kNN查詢算法。

二、CUDA編程技術(shù)

CUDA是nVIDIA公司于2007年6月推出的一種將GPU作為數(shù)據(jù)并行計(jì)算設(shè)備的軟硬件體系，其是第一種不需要借助圖形學(xué)API就可以使用類C語(yǔ)言進(jìn)行通用計(jì)算的開(kāi)放環(huán)境與軟件系統(tǒng)。由于其在性能、成本和開(kāi)發(fā)時(shí)間上較傳統(tǒng)的CPU解決方案有明顯優(yōu)勢(shì)，CUDA的推出在學(xué)術(shù)界和產(chǎn)業(yè)界引起了強(qiáng)烈反響?，F(xiàn)在，CUDA已經(jīng)在天文學(xué)、信號(hào)處理、圖像處理、模式識(shí)別、視頻壓縮等領(lǐng)域獲得廣泛應(yīng)用，并取得了豐碩成果。

CUDA的開(kāi)發(fā)十分簡(jiǎn)單，其采用了比較容易掌握的類C語(yǔ)言進(jìn)行開(kāi)發(fā)，而不需要借助任何圖形學(xué)API。熟悉C語(yǔ)言的開(kāi)發(fā)人員能夠比較平穩(wěn)的從CPU過(guò)渡到GPU，而不必重新學(xué)習(xí)語(yǔ)法。CUDA編程技術(shù)主要包含3個(gè)方面的內(nèi)容：CUDA編程模型、CUDA存儲(chǔ)器模型及CUDA軟件體系。其中，CUDA編程模型將CPU作為主機(jī)，將GPU作為設(shè)備或協(xié)處理器(如圖1(a)所示)，在該模型中，CPU與GPU各司其職，協(xié)同工作，它們各自擁有相互獨(dú)立的存儲(chǔ)器地址空間：主機(jī)端的內(nèi)存和設(shè)備端的顯存。除了編程模型，CUDA也規(guī)定了存儲(chǔ)器模型。在程序運(yùn)行期間，CUDA線程可以訪問(wèn)處于多個(gè)不同存儲(chǔ)器空間中的數(shù)據(jù)(如圖1(b)所示)。CUDA的軟件體系則由3個(gè)層次構(gòu)成：CUDA driver API、CUDA runtime API和 CUDA Library(如圖 1(c)所示)。CUDA軟件體系的核心是CUDA C語(yǔ)言，其包含C語(yǔ)言的最小擴(kuò)展集和一個(gè)運(yùn)行時(shí)庫(kù)，使用這些擴(kuò)展與運(yùn)行時(shí)庫(kù)的源文件必須通過(guò)nvcc編譯器進(jìn)行編譯。

三、基于CUDA的窮舉式kNN查詢

kNN查詢算法雖然經(jīng)過(guò)多年研究已基本發(fā)展成熟，但在某些情況下其效率仍然不盡如人意。近年來(lái)，隨著GPU硬件的快速發(fā)展，基于GPU的通用計(jì)算技術(shù)已被廣泛應(yīng)用于眾多計(jì)算密集型領(lǐng)域。本章將根據(jù) GPU軟硬件的特性，提出一種通過(guò)CUDA實(shí)現(xiàn)的窮舉式kNN查詢算法。

1．算法基本流程

假設(shè)R為一個(gè)包含有m個(gè)點(diǎn)的d維參考點(diǎn)集，而Q是一個(gè)在同一空間中包含有n個(gè)點(diǎn)的查詢點(diǎn)集。kNN查詢的任務(wù)就是根據(jù)某一距離計(jì)算原則，在點(diǎn)集R中找到每個(gè)查詢點(diǎn)的k個(gè)最近鄰域點(diǎn)。對(duì)于窮舉式kNN算法(以下簡(jiǎn)稱BF-kNN)，其基本流程如圖2所示。

圖1 CUDA編程技術(shù)

圖2 窮舉式kNN算法的基本流程

不難發(fā)現(xiàn)，上述算法的時(shí)間復(fù)雜度非常巨大：進(jìn)行n×m次距離計(jì)算的時(shí)間復(fù)雜度為O(nmd)，而n次排序操作的時(shí)間復(fù)雜度為O(nmlogm)。然而窮舉式kNN算法具有高度的并行特性，即各點(diǎn)的距離計(jì)算以及排序操作相互獨(dú)立，能夠同時(shí)進(jìn)行，這與GPU的并行計(jì)算特性十分吻合，利用GPU實(shí)現(xiàn)窮舉式kNN算法可以充分利用當(dāng)前GPU強(qiáng)大的并行計(jì)算能力。

2．排序算法

窮舉式kNN查詢算法的第2步是對(duì)距離值進(jìn)行排序。對(duì)于點(diǎn)云數(shù)據(jù)，kNN查詢只關(guān)心前k個(gè)最小的距離值，而一般情況下k值遠(yuǎn)遠(yuǎn)小于參考點(diǎn)個(gè)數(shù)m。基于這一點(diǎn)，本文使用了一種適合于GPU實(shí)現(xiàn)的排序算法——改進(jìn)的插入排序算法。

插入排序算法是一種簡(jiǎn)單直觀的排序算法，其基本思想是將一個(gè)元素插入到已排好序的有序表中，從而得到一個(gè)新的、元素?cái)?shù)量增一的有序表。為了只獲得前k個(gè)最小值，本文對(duì)基本的插入排序算法做了一些修改，具體實(shí)現(xiàn)步驟如下。

1)根據(jù)基本的插入排序算法對(duì)數(shù)列中的前k個(gè)元素進(jìn)行排序。

2)訪問(wèn)數(shù)列中的第k+1個(gè)元素，從后到前逐個(gè)判斷其與前k個(gè)元素的大小，當(dāng)找到第1個(gè)比其小的元素后，將其插入到該元素之后。

3)遍歷第k+1個(gè)元素之后的所有元素，重復(fù)步驟2)。

改進(jìn)的插入排序算法易于實(shí)現(xiàn)，當(dāng)k值較小時(shí)能獲得較快的查詢速度。

3．CUDA實(shí)現(xiàn)

鑒于該查詢算法由距離計(jì)算和排序兩部分組成，本文將CUDA的實(shí)現(xiàn)分為兩個(gè)階段(即兩個(gè)kernels函數(shù))。

1)第1個(gè)kernels函數(shù)負(fù)責(zé)大小為m×n的距離矩陣計(jì)算。由于各點(diǎn)之間的距離計(jì)算完全獨(dú)立，距離矩陣的計(jì)算可完全并行完成，每個(gè)線程根據(jù)所給的查詢點(diǎn)qi和參考點(diǎn)rj獨(dú)立完成距離計(jì)算。

研究發(fā)現(xiàn)，MYB基因的表達(dá)可受多種非生物脅迫誘導(dǎo)而出現(xiàn)節(jié)律性的晝夜變化[39]，如遮光處理會(huì)抑制花青素苷合成通路中結(jié)構(gòu)基因的表達(dá)，影響花被片著色[40]。光照處理后，‘索邦’花蕾中LhsorMYB12的表達(dá)量明顯高于黑暗處理，說(shuō)明該基因的表達(dá)受到光照調(diào)節(jié)。啟動(dòng)子分析結(jié)果顯示，LhsorMYB12序列上存在多個(gè)光響應(yīng)元件，推測(cè)這些光響應(yīng)元件可能與光照誘導(dǎo)LhsorMYB12表達(dá)上調(diào)相關(guān)。此外，光照處理4 h后 LhsorMYB12的表達(dá)量低于處理2 h和8 h時(shí)的表達(dá)量，說(shuō)明該基因的表達(dá)可能還受到其他因子的調(diào)控，其啟動(dòng)子中存在的參與晝夜節(jié)律調(diào)控的元件可能與LhsorMYB12表達(dá)量的變化相關(guān)。

2)第2個(gè)kernels函數(shù)對(duì)計(jì)算好的距離矩陣進(jìn)行排序。由于每個(gè)查詢點(diǎn)的距離排序完全獨(dú)立，n個(gè)查詢點(diǎn)各自的排序操作可完全并行完成，每個(gè)線程負(fù)責(zé)一個(gè)查詢點(diǎn)的距離排序操作。

CUDA程序一般由主機(jī)端代碼與設(shè)備端代碼組成，基于CUDA的窮舉式kNN查詢的實(shí)現(xiàn)流程如圖3所示。

四、基于外存的kNN查詢

海量點(diǎn)云數(shù)據(jù)一般無(wú)法完全導(dǎo)入到內(nèi)存中，因此只能將大部分?jǐn)?shù)據(jù)存入硬盤。針對(duì)這一情況有必要設(shè)計(jì)一種通過(guò)CUDA實(shí)現(xiàn)的基于外存的kNN查詢算法，從而實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)高效的 kNN查詢。

1．雙層查詢結(jié)構(gòu)

傳統(tǒng)的kNN查詢算法為了提高查詢效率，往往通過(guò)空間層次結(jié)構(gòu)建立，并只考慮查詢點(diǎn)周圍節(jié)點(diǎn)內(nèi)的采樣點(diǎn)，計(jì)算它們與查詢點(diǎn)的距離。此類算法一般情況下只需要少量計(jì)算便可得到最終的結(jié)果，具有不錯(cuò)的效率。但對(duì)于海量點(diǎn)云，由于其無(wú)法將所有的數(shù)據(jù)都放入內(nèi)存，過(guò)深的層次結(jié)構(gòu)不僅會(huì)增加建樹(shù)時(shí)間，還會(huì)因節(jié)點(diǎn)過(guò)多增加磁盤數(shù)據(jù)訪問(wèn)延遲，從而降低查詢效率;而過(guò)于簡(jiǎn)化的層次結(jié)構(gòu)又會(huì)增加參與距離計(jì)算的采樣點(diǎn)個(gè)數(shù)，同樣也會(huì)影響查詢效率。

圖3 基于CUDA的窮舉式kNN查詢算法的實(shí)現(xiàn)流程

反觀基于CUDA的窮舉式kNN查詢算法，由于其充分利用了GPU強(qiáng)大的并行計(jì)算能力，因此其查詢效率與傳統(tǒng)的查詢算法相比優(yōu)勢(shì)巨大。然而對(duì)于海量點(diǎn)云數(shù)據(jù)(特別是上千萬(wàn)甚至過(guò)億的點(diǎn)云數(shù)據(jù))，單純依靠該算法同樣也會(huì)造成巨大的時(shí)間消耗，因此需要做相關(guān)改進(jìn)。

通過(guò)以上分析不難發(fā)現(xiàn)單純依靠GPU或單純依靠空間層次結(jié)構(gòu)都不能較好的實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)的高效kNN查詢，因此本文將這兩種方法進(jìn)行有機(jī)結(jié)合，提出了一種雙層查詢結(jié)構(gòu)。基本做法為：對(duì)整個(gè)點(diǎn)云數(shù)據(jù)進(jìn)行遍歷，以較大的劃分閾值建立空間層級(jí)結(jié)構(gòu)，其中閾值可根據(jù)點(diǎn)云數(shù)據(jù)量的大小確定(對(duì)于5000萬(wàn)的點(diǎn)云，閾值大小可設(shè)為100萬(wàn))。在查詢時(shí)只需要進(jìn)行少量的節(jié)點(diǎn)訪問(wèn)便能獲得要進(jìn)行距離計(jì)算的節(jié)點(diǎn)，然后根據(jù)窮舉式kNN查詢算法，利用GPU強(qiáng)大的并行計(jì)算能力對(duì)這些節(jié)點(diǎn)中的采樣點(diǎn)進(jìn)行鄰域計(jì)算，快速獲得最近鄰域點(diǎn)，從而完成整個(gè)查詢操作。

2．具體實(shí)現(xiàn)

對(duì)于通過(guò)空間劃分獲得的，且具有顯式層次信息的點(diǎn)云多分辨率層次結(jié)構(gòu)，在進(jìn)行查詢時(shí)首先對(duì)該結(jié)構(gòu)進(jìn)行遍歷，確定查詢點(diǎn)所處葉子節(jié)點(diǎn);然后利用窮舉式kNN查詢算法找到該葉子節(jié)點(diǎn)中與查詢點(diǎn)最近鄰的點(diǎn)。具體流程如下。

1)對(duì)于某個(gè)查詢點(diǎn)首先訪問(wèn)層次結(jié)構(gòu)的根節(jié)點(diǎn)，計(jì)算查詢點(diǎn)到根節(jié)點(diǎn)包圍盒的距離，并將其放入到節(jié)點(diǎn)包圍盒隊(duì)列(pqBoxes)中。

2)從pqBoxes中彈出第1個(gè)元素并對(duì)其進(jìn)行訪問(wèn)(第1次訪問(wèn)時(shí)為根節(jié)點(diǎn))，遍歷其所有子節(jié)點(diǎn)，計(jì)算它們的包圍盒與查詢點(diǎn)間的距離，然后逐個(gè)加入到pqBoxes中。

4)當(dāng)pqKNN不為空后，判斷其最小距離值(對(duì)應(yīng)的隊(duì)列元素記為pqKNN．top)是否小于pqBoxes中的最小距離值，如果是，則pqKNN中的最小距離值所對(duì)應(yīng)的采樣點(diǎn)就是當(dāng)前情況下的最近鄰點(diǎn);如果不是，則繼續(xù)遍歷pqBoxes中的元素，重復(fù)步驟3)和步驟4)。

5)對(duì)于第2個(gè)查詢點(diǎn)，首先判斷其是否處于pqBoxes所維護(hù)的各個(gè)節(jié)點(diǎn)中，如果是，則只需重新計(jì)算查詢點(diǎn)與各節(jié)點(diǎn)間的距離并重新放入pqBoxes中，然后重復(fù)步驟3)和步驟4)即可;如果不是，則得首先訪問(wèn)根節(jié)點(diǎn)，重復(fù)步驟1)～步驟4)。

五、試驗(yàn)與分析

本節(jié)將根據(jù)上文提出的算法設(shè)計(jì)相關(guān)試驗(yàn)，通過(guò)對(duì)比分析驗(yàn)證算法的有效性。試驗(yàn)平臺(tái)基本性能如下：Intel Core2 Q8200處理器(頻率2．33GHz)，3GB DDRⅡ內(nèi)存，GeForce 9800 GT顯卡。試驗(yàn)數(shù)據(jù)為實(shí)際采集數(shù)據(jù)，具體信息如表1所示。

表1 實(shí)際采集數(shù)據(jù)相關(guān)信息

1)試驗(yàn)1為基于CUDA的窮舉式kNN查詢算法與ANN[1]查詢算法在查詢效率方面的比較。其是基于內(nèi)存實(shí)現(xiàn)的，即所有數(shù)據(jù)都導(dǎo)入內(nèi)存，對(duì)比試驗(yàn)結(jié)果(k=20)如表2所示。

表2 窮舉式kNN查詢算法與ANN查詢算法的試驗(yàn)結(jié)果對(duì)比 ms

試驗(yàn)結(jié)果表明：當(dāng)所有數(shù)據(jù)全部導(dǎo)入到內(nèi)存后，基于CUDA的kNN算法的查詢速度較基于ANN的kNN算法有大幅提升，特別是當(dāng)數(shù)據(jù)量較大時(shí)，查詢速度增幅顯著。

2)試驗(yàn)2基于CUDA的雙層查詢算法與普通的基于外存查詢算法在查詢效率上的比較。其主要針對(duì)海量點(diǎn)云數(shù)據(jù)的kNN查詢。改進(jìn)的雙層查詢算法與基本算法的區(qū)別在于：在kNN查詢的第2階段，改進(jìn)算法是利用基于CUDA的窮舉式kNN查詢算法獲得葉子節(jié)點(diǎn)中的k個(gè)最近鄰點(diǎn);而基本算法是利用ANN類庫(kù)來(lái)實(shí)現(xiàn)k最近鄰域查詢。當(dāng)nmax為65 536，k為20時(shí)，對(duì)比試驗(yàn)結(jié)果如表3所示。

表3 基本kNN查詢算法與改進(jìn)查詢算法的實(shí)驗(yàn)結(jié)果對(duì)比ms

試驗(yàn)結(jié)果表明：本文提出的改進(jìn)算法較基本算法在查詢速度上有所提升，但增幅較試驗(yàn)1有明顯下降。究其原因主要是頻繁的數(shù)據(jù)調(diào)度產(chǎn)生了較大的訪問(wèn)延遲，其對(duì)查詢速度的影響已經(jīng)成為制約kNN查詢效率的首要影響因素。

在基于外存的kNN查詢算法中，節(jié)點(diǎn)大小是查詢效率的重要影響因子，以下試驗(yàn)展示了不同節(jié)點(diǎn)大小(即不同的nmax值)對(duì)kNN查詢效率的影響。如圖4所示。

圖4 不同節(jié)點(diǎn)大小對(duì)kNN查詢效率的影響

試驗(yàn)結(jié)果表明：對(duì)于基本算法，其查詢時(shí)間在開(kāi)始階段隨nmax值的增大逐漸減少，當(dāng)達(dá)到某個(gè)值后開(kāi)始反向增加;而對(duì)于改進(jìn)算法，其查詢時(shí)間隨著nmax值的增大持續(xù)減少。究其原因主要是改進(jìn)算法所使用的基于CUDA的kNN查詢算法較一般的層次查詢算法在查詢速度上有明顯提升，這使得對(duì)于較大的nmax值該算法仍能獲得較快的查詢速度，而此時(shí)層級(jí)結(jié)構(gòu)的深度較小，節(jié)點(diǎn)數(shù)據(jù)的訪問(wèn)次數(shù)相對(duì)較少，訪問(wèn)延遲有所降低，從而提高了查詢效率。值得注意的是，改進(jìn)算法的查詢時(shí)間也并非一直減少，在nmax值增大過(guò)程中也會(huì)出現(xiàn)一個(gè)最小值。所以，在進(jìn)行kNN查詢時(shí)應(yīng)當(dāng)根據(jù)點(diǎn)云數(shù)據(jù)的實(shí)際情況選擇合適的劃分閾值。

六、結(jié)束語(yǔ)

本文根據(jù)點(diǎn)云數(shù)據(jù)的特點(diǎn)以及當(dāng)前GPU硬件的特性，提出了一種通過(guò)CUDA實(shí)現(xiàn)的窮舉式kNN查詢算法。然后將該算法與傳統(tǒng)的層次查詢算法相結(jié)合，設(shè)計(jì)了一種基于外存的雙層查詢結(jié)構(gòu)，從而實(shí)現(xiàn)了海量點(diǎn)云數(shù)據(jù)的快速kNN查詢。試驗(yàn)證明，筆者的方法與傳統(tǒng)算法相比在效率上有明顯提升，其為海量點(diǎn)云數(shù)據(jù)的后處理工作奠定了較好的基礎(chǔ)。然而，本文提出的窮舉式kNN查詢算法雖然充分利用了GPU強(qiáng)大的并行計(jì)算能力，但是其算法自身的時(shí)間復(fù)雜度過(guò)高，當(dāng)點(diǎn)云數(shù)據(jù)量過(guò)大時(shí)其查詢效率顯著下降。因此，在今后的工作中有必要設(shè)計(jì)一種時(shí)間復(fù)雜度更低的并行查詢算法，以實(shí)現(xiàn)更為高效的kNN查詢。

[1]ARYA S，MOUNT D M，NETANYAHU N S．An Optimal Algorithm for Approximate Nearest Neighbor Searching[J]．Journal of the ACM，1998，45(6)：891-923．

[2]CEDERMAN D，TSIGAS P．GPU-quicksort：A Practical Quicksort Algorithm for Graphics Processors[C]∥Proceedings of the 16th Annual European Symposium on Algorithms．New York：[s．n．]，2008：246-258．

[3]CLARKSON K L．Fast Algorithm for the all Nearest Neighbors Problem[C]∥Proceedings of IEEE symposium on foundations of computer science．[S．l．]：Gengaga Learning Business Press，1983：226-232．

[4]GARCIA V，DEBREUVE E，BARLAUDM．Fast k Nearest Neighbor Search Using Gpu[C]∥Proceedings of IEEE computer society conference on CVPR．[S．l．]：[s．n．]，2008：1107-1112．

[5]ROUSSOPOULOS N，KELLEY S，VINCENT F．Nearest Neighbor Queries[C]∥Proceedings of the ACM SIGMOD conference．New York：[s．n．]，1995：71-79．

[6]SANKARANARAYANAN J，SAMET H，VARSHNEY A．A Fast All Nearest Neighbor Algorithm for Applications Involving Large Point-clouds[J]．Computers ＆ Graphics，2007，31(2)：157-174．

[7]丁鵬．基于 GPU的通用并行計(jì)算庫(kù)的設(shè)計(jì)與研究[D]．成都：西南石油大學(xué)，2007．

[8]黃淼，張海朝，李超．基于八叉樹(shù)空間分割的k近鄰搜索算 法[J]．計(jì) 算 機(jī) 應(yīng) 用，2008，28(8)：2046-2048，2051．

[9]張舒，褚艷利．GPU高性能計(jì)算之CUDA[M]．北京：中國(guó)水利水電出版社，2009．