線云隱私攻擊算法的并行加速研究*

郭宸良,閻少宏,宗晨琪

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 線云隱私攻擊算法原理

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

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

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

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

(1)

(2)

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

(3)

其中,當(dāng)βij<β時(shí),Iβij<β=1,否則Iβij<β=0。

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

(4)

(5)

(6)

(7)

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

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

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

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

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

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

4.1 多進(jìn)程實(shí)現(xiàn)流程

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

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

Figure 2 Timing diagram of CPU parallelized linecloud privacy attack

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

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

Figure 3 Splitting process of CPU multi-process data

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

算法1 CPU多進(jìn)程求鄰近區(qū)域算法輸入:線云Lines,線條數(shù)Count,進(jìn)程數(shù)t。輸出:鄰近點(diǎn)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.依次啟動(dòng)進(jìn)程p并等待結(jié)果;

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

4.3 多進(jìn)程求鄰近區(qū)域極值點(diǎn)

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

然后,根據(jù)設(shè)定的進(jìn)程數(shù)量依次啟動(dòng)各進(jìn)程,按照算法1中的方法分配對(duì)應(yīng)任務(wù)數(shù)量。各進(jìn)程執(zhí)行過程中,首先按距離升序排列待篩選估計(jì)點(diǎn);之后根據(jù)式(2)和式(3)求鄰近區(qū)域的概率分布函數(shù)及柯伊伯統(tǒng)計(jì)量,并循環(huán)執(zhí)行該步驟直到篩選后的估計(jì)點(diǎn)數(shù)不大于5個(gè)或柯伊伯統(tǒng)計(jì)量不大于0.3[3];最后將多個(gè)估計(jì)點(diǎn)距離的中值作為最終估計(jì)點(diǎn),從而得到概率密度極大值點(diǎn)。該過程如圖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多進(jìn)程的并行改進(jìn)算法已得到所求點(diǎn)云,可以進(jìn)一步采用文獻(xiàn)[1]中的方法還原場(chǎng)景圖像。

4.4 局限性

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

5 GPGPU并行實(shí)現(xiàn)

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

5.1 GPGPU實(shí)現(xiàn)流程

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

5.2 GPGPU求鄰近區(qū)域

Figure 6 Splitting process of GPGPU data

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

算法2 GPGPU求鄰近區(qū)域算法輸入:線云Lines,線條數(shù)Count,GPU單次輸入數(shù)據(jù)大小Size。輸出:鄰近點(diǎn)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.擴(kuò)充Lines到Size×round行,填充零值20.StartThread(RunGPUThread(Lines,Lines));21.StartThread(RunCPUThread(Lines));22.等待線程結(jié)果并得到結(jié)果Neighbors[0:Count]

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

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

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

5.4 局限性

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

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

在接下來的實(shí)驗(yàn)中,將對(duì)上述算法進(jìn)行測(cè)試,以評(píng)估并行算法的實(shí)際效果。

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

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

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

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

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

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

Figure 7 Bar chart of relative error percentage of different algorithms

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

6.3 CPU多進(jìn)程并行實(shí)驗(yàn)結(jié)果及分析

本節(jié)實(shí)驗(yàn)利用Python中multiprocessing庫進(jìn)行并行加速,在M6700個(gè)人計(jì)算機(jī)、云服務(wù)器和實(shí)驗(yàn)室服務(wù)器上對(duì)多種數(shù)據(jù)類型進(jìn)行測(cè)試。實(shí)驗(yàn)結(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可以看出,在不同平臺(tái)上,隨著進(jìn)程數(shù)的增加,算法執(zhí)行時(shí)間明顯縮短,相比單進(jìn)程的加速比情況如表1所示。從表1可以看出,在M6700個(gè)人計(jì)算機(jī)上從1個(gè)進(jìn)程增加到6個(gè)進(jìn)程時(shí),加速比增速逐漸放緩,受限于物理核心數(shù),在進(jìn)程數(shù)超過4后,繼續(xù)增加進(jìn)程數(shù)量對(duì)于程序性能的提高逐漸變得緩慢,總體來說,性能還是不斷提高,計(jì)算時(shí)間不斷減少,加速比最高達(dá)到3.12;而對(duì)于擁有更多物理核心的實(shí)驗(yàn)室服務(wù)器,可以進(jìn)一步增加進(jìn)程數(shù),在10個(gè)進(jìn)程時(shí)達(dá)到的最高加速比為8.48,加速效果明顯。

Table 1 Program speedup ratio under multi-process

6.4 GPU加速實(shí)驗(yàn)結(jié)果及分析

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

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

Figure 10 Program running time of each dataset under GPGPU

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

6.5 融合CPU與GPU算法實(shí)驗(yàn)結(jié)果及分析

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

Table 3 Program speedup ratio of fusion algorithm

Figure 11 Program speedup ratio of fusion algorithm

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

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

6.6 實(shí)驗(yàn)總結(jié)

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

7 結(jié)束語

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