利用gpu片上樹群實現二維數據近鄰搜索的並行方法
2023-05-10 07:17:51 1
利用gpu片上樹群實現二維數據近鄰搜索的並行方法
【專利摘要】本發明提供一種利用GPU片上樹群實現二維數據近鄰搜索的並行方法，涉及基於NVIDIA的GPU+CUDA計算架構的高效四分樹群數據結構和基於此數據結構的並行搜索近鄰算法，該方法能夠為各種應用中的近鄰搜索提供性能加速。根據本發明，該方法包括步驟：將數據拷貝到GPU全局存儲；在GPU片上存儲中構建四分樹群，將數據點組織到樹群內；並行在GPU片上存儲中搜索若干四分樹，為每個數據點查找出其一定範圍內的鄰居；根據具體應用需要對查找到的鄰居做進一步的計算處理。該並行近鄰搜索方法性能優越，在圖像處理、地理信息系統等領域具有重要的應用價值。
【專利說明】利用GPU片上樹群實現二維數據近鄰搜索的並行方法
【技術領域】
[0001]本發明涉及樹型數據結構和並行計算，具體涉及四分樹群的構建、基於該數據結構的近鄰搜索和GPU+CUDA架構編程。
【背景技術】
[0002]四分樹是一種用於組織二維空間數據的多層次樹狀數據結構，在樹內每個非葉節點最多有四個子節點。它將一個正方形區域規則地劃分為4個子區域，每一個子區域再分為4個子區域，如此逐次劃分，直至所有子區域最多只包含一個數據點為止。四分樹的優點是空間關係隱含在數據模型之中，檢索和處理速度較快。該數據結構被廣泛用於圖像處理、地理信息系統和機器人等領域中的近鄰搜索。
[0003]圖形處理器(GPU)是當前蓬勃發展的並行計算平臺。它起源於圖形渲染，現在已出現高級語言支持GPU上的便捷編程。NVIDIA為其GPU提供了 Compute Unified DeviceArchitecture (CUDA)編程模型，擁有類C語言的編程接口。結合CUDA的GPU提供了強大的計算能力和非常高的存儲帶寬，適合於高度並行、計算密集的應用。比如:NVIDIA TeslaC2070擁有1.03TFL0PS/s的單精度浮點峰值和144GB/s的帶寬峰值。儘管計算能力強大，但NVIDIA GPU的花銷較低，而且普遍存在於PC或工作站等不太昂貴的機器中。目前，GPU+CUDA架構已被應用於加速各個科學計算領域中的計算密集型處理。
[0004]在硬體層次，支持CUDA的GPU是一些單指令多數據流(SMD)流多處理器(streammultiprocessor)的集合,每個流多處理器有32個流處理器(stream processor)。比如:NVIDIA Tesla C2070處理器有14個流多處理器，共448個流處理器。每個流多處理器有一個容量有限的快速片上共享存儲，可被一個流多處理器內的所有流處理器共享。每個流處理器擁有一定數量的32位寄存器。流多處理器之間通過延遲較高的片外全局/設備存儲進行通信。全局存儲可被主機讀寫，而且在同一程序的不同核函數之間是一致的。共享存儲顯式地由程式設計師管理。與CPU相比，GPU將更多的電晶體用於製作計算單元，因此GPU的浮點計算峰值比CPU高一個數量級。同時，NVIDIA的特殊優化使得GPU的帶寬也比CPU高一個數量級。
[0005]在軟體層次，CUDA模型是大量並行執行線程的集合，CUDA程序以線程並行的模式執行。由主機控制調度、GPU實際執行的基本任務單元稱為核函數，其形式和功能類似C語言中定義的函數。計算被組織成由一些線程塊構成的線程網格(見圖2)。在指令層次，同一個線程塊內的32個連續線程構成一個最小執行單元，稱為線程warp。一個線程塊是一批次同一時刻在同一流多處理器上SMD並行運行的線程warp的集合。每個流多處理器同一時刻並發執行一個或多個線程塊。對於任一線程，它的索引被用於確定其應該處理的數據。同一個線程塊內的線程通過片上共享存儲進行通信。
[0006]建立在NVIDIA的GPU+CUDA並行計算架構上的四分樹將能極大地提升基於四分樹的近鄰搜索的性能。然而，CUDA計算模型被認為不適合諸如建樹和搜索樹之類的不規則計算；目前，使用CUDA在GPU上建立一個樹型數據結構方面的工作較少。Zhou Kun等在GPU上構建了一個針對多維數據的KD-tree，他們將樹的節點信息等存儲在GPU的全局存儲上，並使用該數據結構加速圖像渲染中的光線追蹤和K個最近鄰搜索。一個混合的四分樹構建方法首先在CPU上構建樹的頂部若干層，然後將數據傳輸到GPU全局存儲，在其上構建樹的剩餘層。該方法也將四分樹建在訪問延遲較高的GPU全局存儲上。而且，沒有正式出版的文檔或公布的代碼可供參考。
[0007]在大體運動模擬中，計算天體間的重力影響涉及找出每個天體的大量鄰居，特別是對單個天體重力影響最大的周圍臨近的鄰居。Martin和Keshav在NVIDIA的GPU+CUDA架構上實現了一個高性能的N-body並行模擬算法，在模擬中他們構建了一個八分樹，以加速查找每個天體的近鄰。實驗證明該基於CUDA的八分樹極大提升了模擬算法的性能。不過，該樹型結構仍然構建在延遲較高的全局存儲上。
[0008]在此類問題的研究中，現有工作集中於在GPU的全局存儲上構建一個單一的樹型數據結構。這樣的策略導致大量效率較低的無法優化的對全局存儲的訪問，而且由於線程競爭著將數據點插入到樹中，致使CUDA程序的線程並行度較低，性能受到很大影響。
【發明內容】
[0009]本發明的目的是提供一種基於NVIDIA的GPU+CUDA計算架構的高效四分樹群和基於此數據結構的並行搜索近鄰的方法，能夠為各種應用中的近鄰搜索提供性能加速。
[0010]為實現上述目的，一種利用GPU片上樹群實現二維數據近鄰搜索的並行方法，步驟如下:
[0011](I)將待組織的數據拷貝到GPU全局存儲；
[0012](2)在GPU片上存儲中構建四分樹群，將數據點組織到樹群內；
[0013](3)並行在GPU片上存儲中搜索若干四分樹，為每個數據點查找出其一定範圍內的鄰居；
[0014](4)根據應用需要對查找到的鄰居做進一步的計算處理。
[0015]與以往已在GPU上實現的樹型數據結構不同，本發明利用GPU高速但有限的片上存儲實現四分樹的構建和搜索，極大地提升了存儲訪問的效率。同時，樹群以每個CUDA線程塊為單位實現一棵較小的四分樹，線程並行度相對一個單一的四分樹要高許多倍，從而提升了建樹的效率。該基於四分樹群的近鄰搜索算法性能優越，在圖像處理和計算機仿真等領域中具有重要的應用價值。
【專利附圖】
【附圖說明】
[0016]圖1利用GPU片上樹群實現二維數據近鄰搜索的結構
[0017]圖2主機端代碼的順序執行和設備端代碼的並行執行
[0018]圖3區域格的二維層次遞歸劃分
[0019]圖4區域格四分樹形式的數據點組織
【具體實施方式】
[0020]本發明的核心思想是構建一種可駐留於GPU高速片上存儲的數據結構-四分樹群，使用其組織各種應用中的數據點，在計算中作為加速數據結構，提升並行為全部數據點查找近鄰的性能。
[0021]下面結合附圖和算法實現偽碼詳細描述本發明中的數據結構、該數據結構的構建和使用該數據結構並行搜索數據點的近鄰等算法。
[0022](I)數據點的組織
[0023]四分樹群是一個包含了大量規模較小的CUDA四分樹的森林。本發明將整個數據點部署區域等分為大量正方形區域格，使得每個區域格包含不多於設定閾值數目的數據點(實驗測試中閾值設定為64，即每個區域格最多包含64個數據點)。每個區域格中的數據點用一個CUDA四分樹組織起來。如圖3所示，一個區域格首先劃分為四個更小、均等的區域小格，然後每個區域小格再迭代劃分，直到其包含不多於一個的數據點。最終，圖3區域格內的所有數據點組織到了圖4所示的CUDA四分樹中，空間相近的數據點在樹中互為兄弟節點。
[0024]與一棵大樹相比，樹群可最大化建樹時的CUDA線程並行度；每個CUDA四分樹較小，可完全駐留在GPU快速片上存儲中，避免了訪問全局存儲招致的高延遲，能帶來相當可觀的性能提升。
[0025]⑵GPU片上存儲構建四分樹群
[0026]首先，數據集由內存複製到GPU全局存儲。依據數據分布的範圍和對分布密度的經驗預估將數據分布區域劃分成區域格。每個線程持有一個數據點，根據其坐標將其劃歸到特定的區域格中。如果每個區域格包含的數據點數大於設定的閾值，則每個區域格分裂為四個更小的區域格；反之，停止數據點的劃歸。
[0027]在生成四分樹群時，每個CUDA線程塊負責一個區域格，構建一棵CUDA-quadtree。其中，每個線程持有一個數據點，將其插入樹中。為了便利在CUDA-quadtree中搜索近鄰，每個區域子格的中心點和邊長組合構成「虛節點」以代表該區域，即CUDA-quadtree中的非葉節點。比如:以區域格的中心點和區域格邊長組合四分樹的「根虛節點」，代表該區域格覆蓋的區域。假設一個區域格內最多有η個數據點，則生成的四分樹最大可能佔用空間為η*4+1，據此在共享存儲上分配一固定大小的數組，以保存四分樹信息。該信息數組逆序填充，即當有新數據點插入到CUDA-quadtree時,在數組已保存的數據點前一空白處存儲新數據點信息。
[0028]如表I偽碼所示，線程插入數據點是一個反覆嘗試的過程，其間線程競爭獲取一次插入機會。首先，線程O初始化「根虛節點」並創建四個空葉節點。然後，每個線程根據持有數據點在區域格中的位置尋找合適的葉節點執行插入操作。當這樣的位置找到後，一個競爭勝出線程對其添加唯一寫入權限鎖，獨佔該位置，插入持有的數據點(將該數據點寫入信息數組)，釋放該位置，退出插入操作。如果一個線程競爭失敗，沒有鎖住合適的葉節點，則該線程等待下一次機會重新嘗試前述插入操作。然而，在第二輪中，一個線程找到並鎖住的葉節點位置已經被其他插入的數據點佔用。於是，該線程創建一個帶有四個空葉節點的子樹，插入到該位置，並將原有節點和自己持有的數據點插入到該子樹的葉節點中，釋放該位置，退出插入操作。其餘線程繼續如表一所示繼續嘗試，直到其持有的數據點插入到CUDA-quadtree的一個葉節點中。最後，線程塊內線程協同一次性以訪存效率最優的數據融合方式將四分樹信息數組寫入全局存儲。
[0029]表IGPU片上數據點插入的偽碼示例
【權利要求】
1.一種利用GPU片上樹群實現二維數據近鄰搜索的並行方法，包括步驟: (1)將待組織的數據拷貝到GPU全局存儲； (2)在GPU片上存儲中構建四分樹群，將數據點組織到樹群內； (3)並行在GPU片上存儲中搜索若干四分樹，為每個數據點查找出其一定範圍內的鄰居； (4)根據應用需要對查找到的鄰居做進一步的計算處理。
2.按照權利要求1所述的方法，其特徵在於所述的方法充分利用GPU高效的片上存儲，構建四分樹群和搜索四分樹群的工作均在該存儲中進行，構建好的四分樹由線程協同以訪存最優的存儲融合的方式寫入全局存儲；在搜索四分樹時，以相同的方式將四分樹由全局存儲讀入片上存儲，然後再進行搜索。
3.按照權利要求1所述的方法，其特徵在於所構建的數據結構為由許多四分樹組成的樹群，每個線程塊負責一個四分樹的構建和搜索，以便保證數據結構能夠載入有限的片上存儲和保證CUDA線程並行度儘可能大。
4.按照權利要求1所述的方法，其特徵在於每個線程負責一個數據點，在四分樹的構建過程中將該數據點插入到四分樹中，在近鄰搜索過程中為一個數據點搜索其周圍的鄰居。
5.按照權利要求1所述的方法，其特徵在於為數據點搜索近鄰時逐一將四分樹以訪存最優的方式載入片上存儲，在高效的片上存儲中完成查找工作。
【文檔編號】G06F17/30GK104050175SQ201310078697
【公開日】2014年9月17日 申請日期:2013年3月13日 優先權日:2013年3月13日
【發明者】易衛東, 菅立恆 申請人:中國科學院大學