郭宸良,閻少宏,宗晨琪

(華北理工大學理學院,河北 唐山 063210)

1 引言

近年來,網(wǎng)絡空間安全領(lǐng)域的隱私保護正面臨著計算資源緊張和高實時性要求的雙重挑戰(zhàn)。在此背景下,多核并行計算和異構(gòu)計算技術(shù)的快速發(fā)展,不僅為緩解這些問題提供了強大的算力支持,而且還推動了整個行業(yè)向綠色計算和低碳節(jié)能的可持續(xù)發(fā)展方向邁進。

針對線云的隱私攻擊研究從傳統(tǒng)基于照片的定位方法的隱私安全問題延伸而來。在基于照片的定位方法中,首先需要獲取照片特征點,再通過求解n點透視PnP(Perspective-n-Point)等方法得到點云,最后通過ICP(Interative Closest Point)求解得到相機的運動姿態(tài),這個過程也是視覺同時定位與地圖構(gòu)建SLAM(Simultaneous Localization And Mapping)或運動中恢復結(jié)構(gòu)的內(nèi)容之一。這種方法形成的點云實際是現(xiàn)實世界的特征點,攜帶了場景隱私信息。Pittaluga等[1]經(jīng)過研究,設計了一種通過級聯(lián)神經(jīng)網(wǎng)絡從尺度不變特征變換SIFT(Scale-Invariant Feature Transform)點云和特征描述子恢復原始場景圖像的方法,指出傳統(tǒng)基于點云的定位方法存在隱私安全隱患。這促使研究人員尋找新的具有隱私保護的定位方法,其中基于線云的定位方法被提出并逐漸得到關(guān)注。

線云是指空間中一組方向隨機或按某種特定規(guī)律分布的直線?；诰€云的定位方法最早是由Speciale等[2]提出的,該方法將點云中的點替換為經(jīng)過該點的直線,這些直線的方向呈均勻分布,以此來隱匿原始點,避免了針對點云的隱私攻擊。而根據(jù)Chelani等[3]的研究,這種方式仍存在缺陷:通過計算三維線云鄰近線間最短距離點,能夠得到近似點云,從而恢復出場景細節(jié)。該研究揭露了線云的隱私安全問題。

針對線云隱私安全問題的研究目前相對較少,形成的隱私攻擊和保護算法較為單一。更多的是對算法理論可行性的關(guān)注,缺少性能研究,導致這些算法仍然需要大量時間進行實驗,對后續(xù)研究較為不利。在線云隱私攻擊算法的實驗中,盡管該算法能夠有效地恢復點云數(shù)據(jù),但其處理過程常常受限于較長的等待時間,特別是在增加優(yōu)化迭代次數(shù)以提高結(jié)果精度時,這一限制變得尤為突出。這是因為該算法沒有經(jīng)過并行優(yōu)化,無法充分利用現(xiàn)代多核心中央處理器CPU(Central Processing Unit)的計算資源,而且計算過程中涉及大量的矩陣計算,未能調(diào)用圖形處理器GPU(Graphics Processing Unit)進行加速處理。這給線云隱私安全研究工作帶來了較多不便。

為此,本文針對線云隱私攻擊算法計算時間開銷大的問題展開研究,提出一種并行優(yōu)化算法,采用CPU多核并行和圖形處理器通用計算GPGPU(General-Purpose computing on Graphics Processing Units)并行方法,在個人計算機、高性能計算機和云服務器3個平臺上,基于6個數(shù)據(jù)集測試其經(jīng)過并行優(yōu)化算法的性能和加速效果。實驗結(jié)果表明,本文所提算法的計算性能得到了顯著提升。

2 相關(guān)工作

本節(jié)主要介紹視覺SLAM方法、隱私保護的基于圖像的定位方法、針對這種定位方法的線云隱私攻擊算法以及當前主流并行化方法。

視覺SLAM方法最早是由Se等[4]在2002年提出的,該方法利用相機圖像實現(xiàn)定位和建圖,被廣泛應用于機器人、自動駕駛和擴展現(xiàn)實等領(lǐng)域。盡管具有較低的傳感器需求和支持實現(xiàn)物體識別等優(yōu)點[5],但其涉及的隱私保護問題也逐漸引起關(guān)注。2019年P(guān)ittaluga等[1]提出從三維點云還原場景圖像的方法,之后Speciale等[2]提出了基于圖像的隱私保護定位方法,引入了線云的概念。

然而,Chelani等[3]發(fā)現(xiàn)這種基于線云的定位方法依然存在安全隱患,提出了一種基于密度的線云隱私攻擊算法。該算法采用串行策略,效率較低。為了解決這個問題,并行化改進原算法將成為關(guān)鍵。

并行計算可以大幅提升算法效率,實現(xiàn)程序高效運行。在這種背景下,本文將研究并行計算在解決線云隱私攻擊問題上的應用。根據(jù)Li等[6]的總結(jié),當前的并行程序可以分為主/從模式、單程序多數(shù)據(jù)SPMD(Single Program Multiple Data)模式、數(shù)據(jù)流水模式、分治模式、推測多線程模式和混合模式6種模式。計算機視覺任務一般是計算密集型,可以采用這些模式來提高并行度,降低時間開銷。另外,計算機視覺任務的并行化處理可分為高、中、低3個層次[7]。高層次視覺任務往往采用基于數(shù)據(jù)的并行方法,如Chen等[8]提出的Eyeriss架構(gòu)和Hanif等[9]提出的大規(guī)模并行神經(jīng)陣列MPNA(Massively-Parallel Neural Array)架構(gòu);中層次的計算機視覺任務,如區(qū)域分割、運動分析和三維重建,其并行化方法往往需要有針對性的改進,如Wu等[10]和Rodriguez-Losada等[11]在GPU上實現(xiàn)的集束調(diào)整和ICP求解算法。低層次的計算機視覺任務,如平滑化、直方圖生成、聚類等,現(xiàn)有系統(tǒng)就可以并行完成這些任務[12]。

對于線云隱私攻擊算法的并行優(yōu)化問題,可以結(jié)合上述并行計算模式和層次進行設計。后續(xù)將詳細討論如何具體應用這些方法。

3 線云隱私攻擊算法原理

本節(jié)主要介紹基于密度的線云隱私攻擊算法的原理,并按照求線云鄰近區(qū)域、求極值和結(jié)果優(yōu)化3個步驟進行闡述,之后分析這3個步驟的時間復雜度并找出最耗時的步驟,最后對其進行并行化改進分析。

考慮在空間中的一個點,當將其擴展為一條線時,線上各個點的概率密度呈均勻分布,這有助于隱藏原始點的位置。然而,在考慮點云時,這些點在空間中的分布存在密度差異,即使將它們擴展為線,密度信息仍然保留。通過找到這些線之間的最近點,可以較好地估計原始點的位置,并還原原始點云。

上述過程整體流程如圖1所示[3]。該流程主要將點云恢復任務分為3個步驟:(1)根據(jù)線云中的任意2線間距離,求出每條線的鄰近區(qū)域。(2)根據(jù)找出的鄰近區(qū)域和鄰近點,通過求極值的方式找出位于最大重疊密度區(qū)域的鄰近點,并將其作為備選點來恢復點云。(3)在初次粗還原出點云后,先通過求交集的方式排除穿過鄰近區(qū)域而不包含鄰近點的線;再按照步驟(1)和步驟(2)求點云,得到更優(yōu)的結(jié)果;不斷循環(huán)該步驟,直到達到設定的優(yōu)化次數(shù)。

Figure 1 Process and time complexity of density-based line cloud privacy attack algorithm

(1)

(2)

其中,vi為線li的方向向量。

(3)

其中,當βij<β時,Iβij<β=1,否則Iβij<β=0。

柯伊伯統(tǒng)計量KS(Kuiper Static)則定義如式(4)～式(6)所示:

(4)

(5)

(6)

(7)

其中,N(li)為排除穿過線li的鄰近區(qū)域且不包含鄰近點的線的索引集合。將所得的線繼續(xù)按照步驟(1)和步驟(2)的做法還原點云,并循環(huán)至設定次數(shù)。

下面分析該算法的時間復雜度。步驟(1)中,假設要處理的線云數(shù)據(jù)集S中有n條線(對應n個點),在求線云中任意2線最小歐氏距離集合dll時,采用窮舉法進行計算的時間復雜度為O(n2);而為了得到線云中所有線各自最近的K條線,采用堆排序的時間復雜度為O(n2logK)。因此,該步驟總的時間復雜度為O(n2logK)。步驟(2)中,求n條線上的k個鄰近區(qū)域的極值點,時間復雜度為O(nk2)。步驟(3)中,根據(jù)還原點云求鄰近線和根據(jù)線云求鄰近點,時間復雜度分別為O(n2logt1)和O(n2logt2);求每條線上t1個鄰近點以及對應的t2個鄰近線的交集,時間復雜度為O(n(t1+t2))。因此,該步驟總的時間復雜度為O(n2log (t1+t2))。

在考慮并行優(yōu)化時,這3步中后2步分別需要上一步的結(jié)果,因此整體上它們應該串行執(zhí)行。每個步驟內(nèi)部不存在先后順序,所以并行優(yōu)化應在每個步驟內(nèi)部進行。步驟(1)和步驟(3)的數(shù)據(jù)容易拆分且主要涉及矩陣計算,可以采用CPU和GPU處理。而對于步驟(2),其時間復雜度相對較低;且每條線上的待選點在求交集后數(shù)量彼此不一定相等,這種不平衡的數(shù)據(jù)將難以直接交給GPU進行并行計算。另外,該步驟計算包含較多跳轉(zhuǎn)指令,更適合直接交由CPU處理。因此,步驟(2)的并行優(yōu)化應該考慮采用CPU并行。

4 CPU多核并行實現(xiàn)

本節(jié)主要介紹基于CPU的并行化線云隱私攻擊算法和對應的數(shù)據(jù)拆分方法,并討論該并行化算法的局限性,分別從多進程求鄰近區(qū)域和多進程求鄰近區(qū)域極值點2方面進行闡述。

為了減少原算法在實際計算時的時間開銷,需要對其進行并行化改進,尤其是對時間復雜度較高的部分。CPU多核并行可以采用多線程方法和多進程方式。在具體實現(xiàn)上,部分編程語言,如Python,受限于全局解釋器鎖GIL(Global Interpreter Lock),多線程算法無法充分利用計算機多核心CPU的計算資源[13],因此采用多進程算法具有更好的通用性。采用SPMD模式,通過創(chuàng)建多個進程實體,對線云隱私攻擊算法進行并行化改進,以實現(xiàn)在諸如求線線間歐氏距離、尋找鄰近點、求鄰近區(qū)域極值點等CPU密集型任務中得到較高的加速比。

4.1 多進程實現(xiàn)流程

由于多進程間通信存在額外開銷,為了減少這種開銷,劃分每個進程任務后不再調(diào)整任務量,直到該進程結(jié)束。分別將線云隱私攻擊算法的3個步驟進行并行化改進。設其總?cè)蝿樟糠謩e為N1,N2和N3,將其分為t組,分配到對應t個進程中,每個進程的任務量為N1/t,N2/t和N3/t。由于創(chuàng)建新進程存在額外開銷,因此即使每個進程任務量相同且分配到相同規(guī)格的CPU核心,其結(jié)束時間也存在先后差異,造成并行度下降。為了進一步減少這種差異,當多出的任務量n

上述過程如圖2所示。第1步,求鄰近區(qū)域需要計算得出線云中任意2條線間的距離并取最近的k條線,速度最快。第2步,粗還原中對所有待選區(qū)域求其極值點,未排除偏差較大的區(qū)域,其還原效果較差,時間成本也較高。第3步,迭代求臨近區(qū)域極值點,由于需要迭代優(yōu)化結(jié)果,速度最慢,其并行程度將直接影響整體的加速比,因此應重點關(guān)注該部分。其中,求交集步驟時間復雜度相對較低,實際運行中原算法速度已經(jīng)足夠快,并行化改進效果提升較小,甚至可能導致運行時間延長,因此這個部分依然采用原算法。

Figure 2 Timing diagram of CPU parallelized linecloud privacy attack

4.2 多進程求鄰近區(qū)域

下面介紹求鄰近區(qū)域的多進程改進部分。在該過程中首先需要計算出線云中任意2條線間的距離,之后繼續(xù)求出其鄰近的k條線,這可以通過對每條線和其余線的距離進行排序得到。

Figure 3 Splitting process of CPU multi-process data

該過程可以表示為算法1。

算法1 CPU多進程求鄰近區(qū)域算法輸入:線云Lines,線條數(shù)Count,進程數(shù)t。輸出:鄰近點Neighbors。1.function RunProcess_i(lindex,rindex,value1,value2):2. for i=lindex→rindex do3. for j=0→Countdo4. dst[i][j]=GetDistance(value1[i],value2[j]);5. end for6. Neighbors[i]=GetNeighbor(value1[i],dst[i]);7. end for8. return Neighbors;9.end function10.p=CreateProcess(t);11.bulk_size=Count/t+1;12.for i=0→t-1 do13. p[i]=RunProcess_i (bulk_size×i,bulk_size×(i+1)-1,Lines,Lines);14.end for15.p[t-1]=RunProcess_i (bulk_size×(t-1),Count-1,Lines,Lines);16.依次啟動進程p并等待結(jié)果;

至此,線云中每條線的鄰近區(qū)域已經(jīng)求出,下一步將通過求線上概率分布函數(shù)極值點的方式求估計點。

4.3 多進程求鄰近區(qū)域極值點

在求鄰近區(qū)域極值點之前,需要先去除穿過鄰近區(qū)域而非鄰近點的線?？梢韵惹蟮镁嚯x估計點最近的k條線和距離目標線最近的k個點,然后取交集。該過程也可以并行化處理。首先,分別以估計點和目標線為基準求其到其他線的距離。具體來說,每個進程的任務中,采用算法1中的RunProcess_i函數(shù),其value1和value2分別為線和估計點,求出估計點的鄰近線;然后交換value1和value2的值,得到目標線的鄰近點;最后再取其交集,得到篩選后的鄰近區(qū)域。

然后,根據(jù)設定的進程數(shù)量依次啟動各進程,按照算法1中的方法分配對應任務數(shù)量。各進程執(zhí)行過程中,首先按距離升序排列待篩選估計點;之后根據(jù)式(2)和式(3)求鄰近區(qū)域的概率分布函數(shù)及柯伊伯統(tǒng)計量,并循環(huán)執(zhí)行該步驟直到篩選后的估計點數(shù)不大于5個或柯伊伯統(tǒng)計量不大于0.3[3];最后將多個估計點距離的中值作為最終估計點,從而得到概率密度極大值點。該過程如圖4所示。

Figure 4 Flow chart of getting peak in neighbors using CPU multi-process

Figure 5 Parallelized linecloud privacy attack timing diagrm of GPGPU

至此,CPU多進程的并行改進算法已得到所求點云,可以進一步采用文獻[1]中的方法還原場景圖像。

4.4 局限性

多進程并行算法在創(chuàng)建新的進程和進程間通信等方面相比多線程算法會產(chǎn)生更多的開銷,因此這種算法總體上性能不如多線程算法,但對于現(xiàn)代具有較多核心的計算機來說這種開銷是可以接受的。另外,采用CPU多核并行可以實現(xiàn)線性的性能提升。但是,隨著數(shù)據(jù)量的增加,CPU性能增速往往已經(jīng)不能滿足需求,此時應該考慮采用其他計算機架構(gòu)進行加速計算。GPGPU的出現(xiàn)為解決大規(guī)模矩陣計算問題提供了新思路,下面將介紹該并行化算法。

5 GPGPU并行實現(xiàn)

本節(jié)的內(nèi)容結(jié)構(gòu)與上一節(jié)的類似,主要介紹GPGPU并行化線云隱私攻擊算法、對應的數(shù)據(jù)拆分方式以及該并行化算法的局限性,重點對并行求鄰近區(qū)域部分進行闡述。

5.1 GPGPU實現(xiàn)流程

在原算法中,求線線間歐氏距離和尋找鄰近點的任務都需要進行大量的矩陣計算,而傳統(tǒng)的基于CPU的程序在執(zhí)行這些任務時效率不高。為了充分利用現(xiàn)代計算機的計算資源以實現(xiàn)更好的效果,采用GPU進行處理。這是因為,GPU內(nèi)部配備大量的流處理器,可以高效并行求解,從而提高速度。因此,采用GPGPU的方式并行化改進原算法是非常合適的。然而,對于那些數(shù)據(jù)不平衡、包含不確定計算結(jié)果且計算資源消耗相對較少的任務,如鄰近區(qū)域求極值點,采用GPU難以達到理想的加速效果,因此仍然采用CPU進行計算。對于適合進行GPU并行改進的部分,根據(jù)GPU的計算原理,在設計算法時應增加單次計算的數(shù)據(jù)量,從而減少循環(huán)。為此,將原有的二維數(shù)組轉(zhuǎn)為三維數(shù)組,在單次計算中同時得到一組結(jié)果,這樣更適合GPU進行數(shù)據(jù)處理。利用飛槳框架的GPU計算平臺,采用數(shù)據(jù)流水模式,通過創(chuàng)建CPU和GPU線程,分別執(zhí)行對應的任務。對于所含線條數(shù)為Count的數(shù)據(jù)集,設GPU線程和CPU線程處理一輪數(shù)據(jù)的時間分別為s1和s2,共處理R輪。當s1>s2時,總運行時間為R×s1+s2,如圖5中上半部分所示;當s1≤s2時,總運行時間為s1+R×s2,如圖5中下半部分所示。

5.2 GPGPU求鄰近區(qū)域

Figure 6 Splitting process of GPGPU data

然而,在求鄰近區(qū)步驟中,GPU在面對具有大量判斷和跳轉(zhuǎn)命令的程序時性能表現(xiàn)不佳[14],因此這部分任務依然采用CPU處理。同時,為了進一步提高并行度,采用多線程算法,使CPU處理本輪數(shù)據(jù)時GPU能繼續(xù)處理下一輪數(shù)據(jù)。這樣就形成了一種數(shù)據(jù)流水模式,充分利用了CPU和GPU的并行處理能力,提高了整個過程的計算效率。首先,使用2個臨界區(qū)互斥信號量SemaphoreGPU和SemaphoreCPU,分別用于控制GPU線程和CPU線程的訪問。然后,通過創(chuàng)建2個線程來實現(xiàn)GPU和CPU的并行計算。GPU線程負責計算線與線之間的距離,而CPU線程則負責查找最近的線。在GPU線程中,通過鎖住SemaphoreGPU來確保GPU鄰界區(qū)的互斥訪問,然后進行線與線距離的計算,并釋放SemaphoreCPU。在CPU線程中,通過鎖住SemaphoreCPU來確保CPU鄰界區(qū)的互斥訪問,然后進行最近線的查找,并在完成后釋放SemaphoreGPU。這個過程如算法2所示。

算法2 GPGPU求鄰近區(qū)域算法輸入:線云Lines,線條數(shù)Count,GPU單次輸入數(shù)據(jù)大小Size。輸出:鄰近點Neighbors。1.SemaphoreGPU=1;2.SemaphoreCPU=0;3.round=(Count+1)/Size+1;4.function RunGPUThread(value1,value2):5. for i=0→rounddo6. dst_tmp=GetDistance(value1[Size×i:Size×(i+1)],value2);7. P(SemaphoreGPU);8. dst=dst_tmp;9. V(SemaphoreCPU);10. end for11.end function12.function RunCPUThread(value):13. fori=0→round do14. P(SemaphoreCPU);15. Neighbors[Size×i:Size×(i+1)]=GetNeigh-bor(value[Size×i:Size×(i+1)],dst);16. V(SemaphoreGPU);17. end for18.end function19.擴充Lines到Size×round行,填充零值20.StartThread(RunGPUThread(Lines,Lines));21.StartThread(RunCPUThread(Lines));22.等待線程結(jié)果并得到結(jié)果Neighbors[0:Count]

5.3 GPGPU的訪存優(yōu)化

在實現(xiàn)GPGPU算法時,優(yōu)化訪存模式是提高性能和效率的關(guān)鍵手段之一。通過合理管理數(shù)據(jù)的讀取和寫入操作,并充分利用GPU的顯存存儲結(jié)構(gòu),可以減少訪存延遲并提高數(shù)據(jù)訪問速度。本文算法主要采用數(shù)據(jù)重用來進行優(yōu)化。

對于經(jīng)常需要重復使用的數(shù)據(jù),如線云Lines,可以將其傳輸?shù)紾PU后一直存儲在顯存中,直到所有組計算結(jié)束。當使用單精度浮點數(shù)且數(shù)量為十萬時,其所占用的顯存空間約為2.29 MB,這是完全可接受的。此外,由于在數(shù)據(jù)拆分過程中按照順序分組,數(shù)組采用順序存儲,在同一組計算過程中不同流處理器訪存地址接近,具有較好的空間局部性,其訪存時間也比較接近,具有較好的時間局部性,所以通過利用一級緩存和二級緩存,可以減少對全局存儲器的訪存流量,降低訪存時間。另外,在GPU計算過程中生成的一些中間值數(shù)組如矩陣叉乘結(jié)果NS,其大小為3×Size×Count,對于數(shù)量為十萬大小的線云,取Size為2 000時,占用顯存2.2 GB,如果每次循環(huán)都要重新創(chuàng)建,將花費較多時間。事實上,在前R′-1組循環(huán)中它們的大小和維度保持不變,可以重復利用,無需重新開辟顯存空間。最后,在CPU單核性能尚未達到瓶頸且顯存充足的情況下,應盡量增加Size的大小,以減少GPU對內(nèi)存的訪存次數(shù),使GPU訪問顯存的時間更長。

5.4 局限性

雖然采用GPU進行處理相比采用CPU具有許多優(yōu)勢,但也存在一些局限性需要考慮。首先,與CPU處理不同,GPU處理需要將數(shù)據(jù)從內(nèi)存轉(zhuǎn)移到顯存,并根據(jù)GPU硬件的具體支持情況調(diào)整數(shù)據(jù)精度,例如,從雙精度降至單精度浮點數(shù)。因此,在實際應用中,需要通過實驗對數(shù)據(jù)轉(zhuǎn)換引起的結(jié)果差異進行測量和評估,以確保最終結(jié)果的準確性。

其次,GPU在計算過程中主要負責計算任務,如求線線距離,而CPU任務較為有限,主要為數(shù)據(jù)轉(zhuǎn)換和轉(zhuǎn)移。此外,實際實驗中不同型號的CPU和GPU之間性能也存在差異,導致兩者負載并不均衡,降低了算法的并行度。為了解決這個問題,可以采用CPU多進程和GPGPU融合的計算方式。具體而言,對于多核CPU,當其單核性能較弱時,GPU的數(shù)據(jù)填充速率較低,導致吞吐率較低。這時,可以增加額外的GPGPU計算進程,利用多個進程向GPU發(fā)送任務,以提高GPU的利用率。由于這些GPGPU進程優(yōu)先級一致,為了使其在相近的時間點結(jié)束,其任務量也應保持一致。CPU在運行GPGPU進程后,若仍有空閑時間可用,為了進一步利用這些空余資源,可以根據(jù)第3節(jié)的方法增加CPU計算進程。為了確定最佳任務分配策略,需要通過實驗進行測定。

在接下來的實驗中,將對上述算法進行測試,以評估并行算法的實際效果。

6 實驗與結(jié)果分析

本文實驗分別在包含室內(nèi)、室外場景的不同數(shù)據(jù)集上進行測試。首先對于數(shù)據(jù)集中的原始圖像利用colmap得到點云;然后對比原算法、CPU多核并行優(yōu)化算法和GPGPU優(yōu)化算法在處理相同數(shù)據(jù)集時的精度和性能差異;最后結(jié)合CPU多核并行算法和GPGPU優(yōu)化算法實現(xiàn)異構(gòu)計算,以得到最佳性能。

6.1 實驗環(huán)境及數(shù)據(jù)集

為了在更廣泛的硬件平臺測試本文算法的加速效果,本文實驗在3個具有代表性的平臺上展開:代表低功耗的個人筆記本電腦M6700(配備i7-3740QM的4核心CPU和Quadro?P4000的GPU)、具有多CPU核心的HPC的實驗室服務器(配備Xeon?E5-2680 v4的14核心CPU)和配備更強CPU和GPU的云服務器(配備Xeon?Gold 6148的虛擬化雙核心CPU和Tesla?V100的GPU)。采用4個公開數(shù)據(jù)集(Gatehouse[15]、South Building[16]、KingsCollege[17]和Indoor Screens(luke)[18,19])和2個私有數(shù)據(jù)集(實驗室、圖書館),共包含2個室內(nèi)場景和4個室外場景,室外場景中包含3個地面拍攝場景和1個航拍場景,具有不同的尺度大小和點云密度分布情況,能夠較為全面地測試算法攻擊效果。通過對比在不同平臺上的計算時間和效率來驗證本文并行算法的實際效果。各數(shù)據(jù)集為圖像序列,為了從圖像序列獲取點云,采用colmap3.5(CUDA?)自動模式進行重建,質(zhì)量選擇為“高”,生成txt格式的點云數(shù)據(jù)并輸入到實驗程序中。

6.2 并行優(yōu)化算法的精度測試及分析

精度測試主要驗證所提并行優(yōu)化算法的正確性,以確保其不會改變原算法的結(jié)果。在本節(jié)實驗中,由于GPGPU計算方式中采用32位和64位浮點數(shù)時精度不同,且運行速度有較大差異,因此需要分別考慮這2種方式。本節(jié)實驗環(huán)境為M6700個人計算機,設定迭代次數(shù)為2,得到的線云還原的點云相對原算法的誤差百分比如圖7所示。

Figure 7 Bar chart of relative error percentage of different algorithms

由圖7可知,CPU多進程并行優(yōu)化算法和原方法誤差百分比都為0,表明基于CPU的多進程并行優(yōu)化算法不影響算法結(jié)果;而GPGPU算法的誤差百分比都在0.4%以內(nèi),對結(jié)果的影響極小,且在實驗中,采用32位時相比采用64位的具有更高的運行速度和更低的顯存占用。綜上,本文實驗采用32位浮點數(shù)表示進行GPGPU計算,因為其在運行速度和顯存占用方面具有更高的性能。

6.3 CPU多進程并行實驗結(jié)果及分析

本節(jié)實驗利用Python中multiprocessing庫進行并行加速,在M6700個人計算機、云服務器和實驗室服務器上對多種數(shù)據(jù)類型進行測試。實驗結(jié)果如圖8和圖9所示。

Figure 8 Programs running time of M6700 personal computer under multi-process

Figure 9 Program running time of cloud server and laboratory server under multi-process

從圖8和圖9可以看出,在不同平臺上,隨著進程數(shù)的增加,算法執(zhí)行時間明顯縮短,相比單進程的加速比情況如表1所示。從表1可以看出,在M6700個人計算機上從1個進程增加到6個進程時,加速比增速逐漸放緩,受限于物理核心數(shù),在進程數(shù)超過4后,繼續(xù)增加進程數(shù)量對于程序性能的提高逐漸變得緩慢,總體來說,性能還是不斷提高,計算時間不斷減少,加速比最高達到3.12;而對于擁有更多物理核心的實驗室服務器,可以進一步增加進程數(shù),在10個進程時達到的最高加速比為8.48,加速效果明顯。

Table 1 Program speedup ratio under multi-process

6.4 GPU加速實驗結(jié)果及分析

根據(jù)具體硬件條件合理設定GPU的數(shù)據(jù)量。在本文實驗中,對于80 000條線組成的線云,當取Size為5 000時,可使顯存占用率達到80%以上,效果較好,實驗結(jié)果如圖10所示。從圖10可以看出,在不同平臺上采用GPU方式計算,算法的執(zhí)行時間明顯縮短,相比原程序的加速比情況如表2所示。

Table 2 Program speedup ratio under GPGPU表2 GPGPU下程序加速比

Figure 10 Program running time of each dataset under GPGPU

經(jīng)過多組實驗可知,以Gatehouse數(shù)據(jù)為例,經(jīng)過GPU加速,運行時間大大縮短,相比原程序,其最大加速比為13.70,加速效果顯著。

6.5 融合CPU與GPU算法實驗結(jié)果及分析

本節(jié)實驗將CPU多進程并行和GPU并行算法結(jié)合起來,共同完成從線云恢復點云的任務,從而充分利用計算資源。具體實現(xiàn)上,將原數(shù)據(jù)集進行拆分,分別輸入到CPU進程和GPU進程,從而獲得最優(yōu)性能。如圖11和表3所示是在M6700個人計算機上,在求鄰近線、粗還原和優(yōu)化結(jié)果3個任務中CPU和GPU任務量分配比分別為:0∶1,1∶60和1∶4,且CPU進程數(shù)設置為4時,達到最佳時間和加速比。

Table 3 Program speedup ratio of fusion algorithm

Figure 11 Program speedup ratio of fusion algorithm

可以看到,經(jīng)過多組實驗,經(jīng)過融合后算法的最大加速比達到了15.11,相比單獨采用CPU并行化算法的提高了472.35%,相比單獨采用GPGPU算法的提高了10.29%,具有明顯的提升效果。

在進行融合算法實驗時,針對不同數(shù)據(jù)集以及不同計算平臺,CPU和GPU任務量的分配將對總時間產(chǎn)生較大影響。由于GPGPU方式往往比CPU方式更快,所以應向GPU分配更多任務量,而當不同計算方式之間加速比差距過大時,如在求鄰近線任務中CPU并行加速比為5左右,而GPGPU則達到了25左右,此時應只采用GPGPU方式。另外,由于GPGPU計算方式仍然需要CPU參與,因此,在實際中應考慮為其留出足夠的CPU計算資源,減少搶占CPU需要的等待時間,從而使總吞吐量達到更高值。

6.6 實驗總結(jié)

本文實驗的重點在于測試并行優(yōu)化和異構(gòu)計算優(yōu)化對線云隱私攻擊算法的加速效果。實驗結(jié)果表明,通過并行優(yōu)化和異構(gòu)計算優(yōu)化,能夠在較低的時間成本下獲得較好的攻擊效果。

7 結(jié)束語

通過對線云隱私攻擊算法進行并行化處理,可以解決其速度過慢的問題。利用多進程拆解恢復任務,并通過不同的CPU和GPU核心進行計算,對原算法進行改進,并且在多個平臺和不同數(shù)據(jù)集上進行實驗。結(jié)果表明,該并行算法能夠快速地得到估計點并對結(jié)果進行優(yōu)化,大幅度減少了計算時間,與原有算法相比加速效果明顯,且對結(jié)果影響較小。融合CPU和GPU計算的實驗結(jié)果進一步降低了總時間開銷,充分利用了現(xiàn)代配備多核心處理器和GPU的計算機的計算資源,進一步縮短了等待時間。對于類似包含大量矩陣計算的問題,融合算法的實驗結(jié)果為其性能優(yōu)化提供了有益參考。在未來的工作中,可以針對算法的空間復雜度問題進行改進,并通過縮短GPU等待延遲和提高吞吐量來進一步提高并行效率。此外,針對GPU的Top-K算法優(yōu)化也是一個值得深入研究的問題。該算法直接影響GPU求鄰近區(qū)域的任務,通過優(yōu)化該算法,可以使該任務受益,并進一步提高整體性能。