賀 成,施華君

(中國電子科技集團(tuán)公司第三十二研究所,上海 201808)

當(dāng)今許多尖端技術(shù)的解決都離不開并行處理,許多國家都將其列入關(guān)鍵技術(shù).并行機(jī)的發(fā)展和智能計算等實際應(yīng)用的需要共同促進(jìn)了并行算法的研究[1,2].算法是求解問題的步驟和方法[3].簡單的講,并行算法是用多臺處理器聯(lián)合求解問題的方法和步驟[4,5].并行算法不能僅通過時間復(fù)雜度[6]來進(jìn)行評價,因為人們在對計算速度的渴求的同時,對于并行處理所需要的處理器數(shù)量急劇增長的問題也開始關(guān)心.所以,評判并行算法綜合性能的指標(biāo)“成本”顯得格外的重要.并行算法的成本是指并行算法在并行機(jī)各處理器上運(yùn)行時間總和Cost=Tp?P[7],Tp代表每個處理器處理問題的運(yùn)行時間,P代表處理器數(shù)量.并行算法相比串行算法而言,可以在更短的時間內(nèi)給出問題的答案,滿足了應(yīng)用對于實時性的要求.但是并行算法所帶來的額外開銷也是不容忽視的,其中并行算法對于處理器數(shù)量的要求導(dǎo)致并行算法的實現(xiàn)是昂貴的.這無疑給有些并行算法的實現(xiàn)帶來一定的限制.其中并行算法中最大值查找就存在成本過高的問題.

本文以最大值查找算法為基礎(chǔ),探討了3種并行化查找最大值的方法(平衡樹方法、雙對數(shù)深度樹方法、快速查找法),進(jìn)而提出提出了一種比平衡樹算法,快速查找法,雙對數(shù)深度樹方法并行成本(Cost)更優(yōu)的基于數(shù)據(jù)劃分方法的最大值查找并行算法.該方法通過減少處理器使用的數(shù)量,維持處理問題時間與平衡樹方法一致,以此取得相比平衡樹方法,雙對數(shù)深度樹方法,快速查找法在并行成本上表現(xiàn)更優(yōu)的算法.為之后的相關(guān)并行算法的優(yōu)化提供一個改進(jìn)的方向,為大數(shù)據(jù)處理中查找最大值提供了一個可行的辦法.

本文并行算法研究是在PRAM[8,9]模型下進(jìn)行的,但微型計算機(jī)CPU架構(gòu)中的SIMD并行機(jī)制,由于實現(xiàn)指令的復(fù)雜性,幾乎沒有編譯程序?qū)⒏呒壵Z言設(shè)計的程序優(yōu)化到SIMD指令級別[10].因此本文通過模擬仿真實驗對幾種并行查找算法的實際運(yùn)行時間進(jìn)行對比.

1 并行查找最大值的算法

1.1 平衡樹查找方法

1.1.1 算法原理

利用平衡二叉樹[11-13](Balanced Binary Tree)抽象出并行求解最大值的方法,樹的葉節(jié)點(diǎn)是輸入元素集合,樹的非葉節(jié)點(diǎn)用于比較操作,樹的高度為H.在樹的同一深度上內(nèi)節(jié)點(diǎn)并行計算.樹中的節(jié)點(diǎn)都包含兩個子節(jié)點(diǎn),所以每個節(jié)點(diǎn)只需要一個處理器就可以在常數(shù)時間內(nèi)做出比較操作,同一深度并行計算需要的處理器數(shù)目與內(nèi)節(jié)點(diǎn)數(shù)相同,這樣僅需要O(H)的時間就可以完成最大值查找.需要處理器數(shù)目為2H-1.如圖1.

下面是平衡樹方法的偽代碼[14]:

輸入:n = 2m個數(shù)存于數(shù)組A(n:2n-1)中.輸出:最大值,位于A(1).Balance(Element A[]){for k=m-1 to 0 do for j=2k to 2k+1-1 par-do A[j]=max{A[2j],A[2j+1]}}

圖1 平衡樹查找最大值

1.1.2 算法分析

平衡二叉樹算法的運(yùn)行時間為Tp=O(logN),處理器數(shù)目P(n)=O(N/2),并行成本Cost=Tp?P=O(NlogN).從時間復(fù)雜度上來看,平衡樹算法運(yùn)行速度較快.該方法能快速縮減待比較的數(shù)據(jù)量,因此速度得到了極大的提升.但是由于每次操作之后待比較數(shù)據(jù)都減少一半,所以每輪操作之后都有一半當(dāng)前參與工作的處理器無事可做.直到樹根時,僅僅有一個處理器在工作.平衡樹方法的優(yōu)點(diǎn)是可以快速縮減待比較數(shù)據(jù)量,從而提高查找速度.但是由于其自身結(jié)構(gòu)的原因,導(dǎo)致了處理器負(fù)載不均衡[15,16],處理器利用率不高.

1.2 快速查找方法

1.2.1 算法原理

通過比較手段快速獲取集合中的最大值[17],每次操作就需要確定更多元素之間的大小關(guān)系,也就是每次操作需要更多元素進(jìn)行比較.快速并行算法利用一個n*n的邏輯二維表來存儲某一個元素與集合中其余元素的大小關(guān)系(0表示小于,1表示不小于),如表1.當(dāng)某一行或者某一列元素關(guān)系都為“大于”時,該行(列)代表的元素為最大值.

表1 邏輯關(guān)系表

下面是快速并行算法的偽代碼[14]:

輸入:存有n個不同元素的數(shù)組A.輸出:布爾數(shù)組M,當(dāng)且僅當(dāng)A(i)=max{A}時,M(i)=1.Quick(Element A[]){(1)for 1＜=i,j＜=n par-do

if A[i] ＞= A[j]B[i][j] = 1 else B[i][j] = 0(2)for 1＜=i＜=n par-do M[i]=B[i][1]∩B[i][2]∩… ∩B[i][n]}

該算法要求步驟(1)同時讀,步驟(2)要求同時寫.

1.2.2 算法分析

算法執(zhí)行時間為Tp(n)=O(1),使用了P(n)=O(N2)個處理器,成本為Cost=Tp?P=O(N2).從時間復(fù)雜度上看,該算法是目前已知運(yùn)行速度最快的最大值查找并行算法.與平衡樹方法和雙對數(shù)方法每輪操作只能確定部分元素之間大小關(guān)系,該算法每輪操作都可以確定一個元素與其余所有元素的大小關(guān)系.利用這一并行思想可以快速確定所有元素之間的關(guān)系,但是該方法缺點(diǎn)就是所需要的處理器數(shù)目過多,處理器數(shù)目將會以元素個數(shù)的指數(shù)增長,并且對于處理器之間的通信速度要求極高,算法實現(xiàn)要求條件苛刻.

1.3 雙對數(shù)深度樹查找方法

1.3.1 算法原理

所有輸入數(shù)據(jù)作為葉節(jié)點(diǎn),節(jié)點(diǎn)u的子節(jié)點(diǎn)數(shù)為其中Nu是節(jié)點(diǎn)u所包含的葉節(jié)點(diǎn)的數(shù)目.規(guī)定節(jié)點(diǎn)u的層為u到根路徑的邊數(shù),顯然根節(jié)點(diǎn)的層為0[14].假定共有元素則第i層有 個節(jié)點(diǎn),每個節(jié)點(diǎn)有個子節(jié)點(diǎn).由此可以計算出樹的高度為k+1=loglogN.圖2為當(dāng)N=16時的雙對數(shù)深度樹[18].

圖2 雙對數(shù)深度樹

下面是雙對數(shù)深度樹方法的偽代碼:

22k輸入: n = 個數(shù)存于數(shù)組A(1:n)中.輸出:布爾數(shù)組M,當(dāng)且僅當(dāng)A(i)=max{A}時,M(i)=1.

DoubleTree(Element A[]){(1)for j=1 to n/2 do A[j]=max{A[2j-1],A[2j]}(2)for i=k-1 to 0 do 22k?2k?i for m=0 to m= par-do 22k?i?122k?i?1 Quick(A[m* :(m+1)* ])}

1.3.2 算法分析

算法執(zhí)行時間Tp(n)=O(loglogN),使用了P(n)=O(N)個處理器,成本為Cost=Tp?P=O(NloglogN).雙對數(shù)深度樹每次比較操作之后,待比較數(shù)據(jù)量減少的速度比平衡樹方法更快,每個處理器的工作量相比平衡樹方法都有更好的提升,所以雙對數(shù)深度樹的查找時間比平衡樹更快.但是雙對數(shù)深度樹的每個節(jié)點(diǎn)的最大值都是通過調(diào)用快速查找算法而實現(xiàn)的,所以雙對數(shù)深度樹的方法的實現(xiàn)的難度仍然很大.

2 基于數(shù)據(jù)劃分的最大值查找算法

基于數(shù)據(jù)劃分的最大值查找算法(以下簡稱為“數(shù)據(jù)劃分方法”)針對平衡樹算法處理器工作分配不均導(dǎo)致工作效率低下,快速查找算法對于處理器數(shù)量需求過大,以及雙對數(shù)深度樹方法難以實現(xiàn)的問題進(jìn)行了改進(jìn).汲取了雙對數(shù)深度樹中處理器工作飽滿,查找時間快,快速查找算法邏輯表比較數(shù)據(jù)法的優(yōu)點(diǎn).提出了一種比平衡樹算法,快速查找法,雙對數(shù)深度樹方法并行成本Cost更優(yōu)的基于數(shù)據(jù)劃分方法的最大值查找并行算法,通過降低處理器(P)數(shù)量,保證處理時間(Tp)達(dá)到O(logn)量級,來達(dá)到降低并行成本的目的.

數(shù)據(jù)劃分方法使用比第一節(jié)中3種并行方法更少的處理器,保證處理速度達(dá)到O(logn)級,就必須充分利用每個處理器的工作效率,從而保證數(shù)據(jù)劃分方法不會因為處理器數(shù)目的減少,而使得問題處理速度遠(yuǎn)遠(yuǎn)慢于平衡樹方法.研究過程中發(fā)現(xiàn)利用邏輯表將數(shù)據(jù)進(jìn)行合理的劃分為多個組,可以提升每個處理器的效率,且能快速降低待查找數(shù)據(jù)集.

最終實現(xiàn)了一種比平衡樹算法,快速查找法,雙對數(shù)深度樹方法并行成本額Cost更優(yōu)的高度可行的基于數(shù)據(jù)劃分查找最大值的并行算法.

2.1 算法原理

從邏輯上將集合中的數(shù)據(jù)進(jìn)行分組,假設(shè)共N個元素,分為logN組,每組N/logN個元素,共N/logN個處理器.

Step1.每組都采取兩兩元素比較的方式,使每組元素個數(shù)都減少為N/(2logN)個元素.由于每組需要N/(2logN)個處理器,所以每兩組可以并行計算,共需要(logN)/2步完成所有操作.

Step2.此時每組所剩元素為N/(2logN)個,繼續(xù)采用兩兩比較的方式,使每組元素個數(shù)都減少為N/(4logN).由于每組需要N/(4logN)個處理器,所以每四組可以并行計算,共需要(logN)/4步完成所有操作.

Step3.此時每組所剩元素為N/(4logN)個,繼續(xù)采用兩兩比較的方式,使每組元素個數(shù)都減少為N/(8logN).由于每組需要N/(8logN)個處理器,所以每八組可以并行計算,共需要(logN)/8步完成所有操作.

依次類推,最終的目的是使得每組剩余元素個數(shù)為1.而此時需要log(N/2logN)步完成.當(dāng)每組只剩1個元素的時候,就可以采用平衡樹或雙對數(shù)深度樹進(jìn)行求解最終的最大值.

下面是基于數(shù)據(jù)劃分算法的偽代碼:

輸入: n個數(shù)存放于A[logn][logn]數(shù)組中輸出:最大值A(chǔ)[1][1]Data_Partition(Element A[][]){for i = 1 to log(n/(2logn))for m=1 to logn par-do blance(A[m][1:(logn)/i])Blance(A[1:logn][1])}

2.2 算法分析

3 實驗方式

Pan[19]和Pavel[20]提出了并行計算模型具備可重配置流水線總線的線性陣列模型(Linear Arrays with a Reconfigurable Pipelined Bus System,LARPBS),并且在該模型上實現(xiàn)了平衡樹與雙對數(shù)深度樹查找的并行算法[21].由于實驗條件所限,無法實現(xiàn)真正搭建并行機(jī)和LARPBS.鑒于此種情況,本文采用多核并行計算進(jìn)行仿真模擬實驗.深度學(xué)習(xí)[22]中神經(jīng)網(wǎng)絡(luò)利用Tensor flow學(xué)習(xí)庫來構(gòu)建計算圖,通過GPU進(jìn)行計算圖中部分節(jié)點(diǎn)并行計算,從而實現(xiàn)并行加速效果.因此本文也使用基于TensorFlow的GPU[23,24]處理框架來進(jìn)行仿真模擬實驗.

3.1 實驗原理

利用TensorFlow構(gòu)建各個并行查找算法的計算圖,如圖3-圖6(為了顯示方便,圖中只顯示一定數(shù)據(jù)量下的計算圖),將計算圖中的每個節(jié)點(diǎn)視為并行機(jī)中的一個處理器,計算圖中每個節(jié)點(diǎn)的連線(數(shù)據(jù)傳遞)代表處理器之間的通信.通過TensorFlow自帶的GPU加速來實現(xiàn)同計算層次中節(jié)點(diǎn)的并行計算,以此來仿真并行機(jī)運(yùn)行查找算法的過程.實驗測試數(shù)據(jù)共分為5組,每組數(shù)據(jù)通過隨機(jī)數(shù)生成,每組數(shù)據(jù)個數(shù)依次為512,1024,2048,4096,8192.(為了簡化程序?qū)?shù)據(jù)量都設(shè)置為2n).每組數(shù)據(jù)測試1000次取運(yùn)行時間的平均值,作為最后實驗分析數(shù)據(jù).

圖3 數(shù)據(jù)量為8的平衡二叉樹方法tensorflow計算圖

3.2 實驗環(huán)境

操作系統(tǒng):Windows7

編程語言:Python3.6

機(jī)器學(xué)習(xí)庫:Tensorflow-GPU 1.12.0

處理器:CPU i7-4790 3.6 GHz

加速器:GPU GTX1070

編輯器:Pycharm Community Edition 2017.1.2

圖4 數(shù)據(jù)量為16的雙對數(shù)深度樹tensorflow計算圖

圖5 數(shù)據(jù)量為4的快速查找算法計算圖

圖6 數(shù)據(jù)量為16的數(shù)據(jù)劃分方法計算圖

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

從數(shù)據(jù)劃分方法運(yùn)行時間(見表2,圖7)來看,數(shù)據(jù)劃分方法隨著測試數(shù)據(jù)量的增加其實際運(yùn)行時間的增長符合理論時間復(fù)雜度的增長規(guī)律,說明仿真模擬實驗從運(yùn)行時間結(jié)果上來看是滿足實驗需要的,實驗數(shù)據(jù)具有一定的可參考性.表2中有一個現(xiàn)象,快速查找算法理論時間復(fù)雜度是 O (1),但是實際運(yùn)行時間卻跟雙對數(shù)深度樹方法幾乎一樣,甚者運(yùn)行時間表現(xiàn)的更糟糕.這是由于快速查找算法的理想模型機(jī)是MIMD (Multiple Instruction stream Multiple Data stream),tensorflow搭建的計算圖并不能模擬MIMD所具有的性質(zhì),因此運(yùn)行時間表現(xiàn)糟糕.而改進(jìn)算法的實際運(yùn)行時間與平衡樹算法運(yùn)行時間幾乎一致,較其他算法略慢,但是達(dá)到了改進(jìn)算法最初對其運(yùn)行時間的要求.

從運(yùn)行所需的處理器數(shù)量來看(見表3,圖8),隨著數(shù)據(jù)量的增長,快速查找方法所需要的處理器數(shù)量爆炸增長,因而在當(dāng)前坐標(biāo)軸下已經(jīng)無法看到快速查找方法的曲線,而數(shù)據(jù)劃分方法所需要的處理器數(shù)量遠(yuǎn)低于平衡樹查找法和雙對數(shù)深度樹查找法,并且隨著數(shù)據(jù)量的增多,數(shù)據(jù)劃分方法對處理器數(shù)量的需求相較其他查找算法優(yōu)勢越大.達(dá)到了數(shù)據(jù)劃分方法最初對其所需處理器數(shù)量的要求.

表2 實驗結(jié)果時間對比表

從運(yùn)行成本來看(見表4,圖9),由于快速查找方法并行成本過高,因而在當(dāng)前坐標(biāo)軸下已經(jīng)無法看到快速查找方法的曲線.數(shù)據(jù)劃分方法的綜合成本相比于其他最大值查找的并行算法是更優(yōu)的,說明數(shù)據(jù)劃分方法是有效的,達(dá)到了研究目的.

圖7 算法運(yùn)行時間對比圖

表3 模擬處理器數(shù)量對比表

圖8 算法使用處理器數(shù)目對比圖

4 結(jié)論與展望

通過對比實驗,數(shù)據(jù)劃分方法的并行成本(Cost)相較平衡樹方法,雙對數(shù)深度樹方法,快速查找法是更優(yōu)的,說明數(shù)據(jù)劃分方法到達(dá)了最初的研究目的.數(shù)據(jù)劃分方法使用更少處理器,有效降低了所需處理器數(shù)量,保證了問題處理時間達(dá)到并行處理的目的,使其執(zhí)行時間與平衡樹方法一致的改進(jìn)算法,略低于雙對數(shù)深度樹方法.最終減少并行算法的成本,節(jié)約了資源.

表4 運(yùn)行成本對比表

圖9 算法成本對比圖

隨著并行技術(shù)越來越多的應(yīng)用到學(xué)術(shù)研究,生產(chǎn)生活等方面,人們對于算法運(yùn)行產(chǎn)生的并行成本的要求會更高.希望可以保證處理速度的同時,降低并行算法的成本.本文最大值查找算法的改進(jìn),就是在此背景下進(jìn)行的.并行算法眾多,文章通過比較具有代表性的最大值查找算法進(jìn)行改進(jìn).為此后類似并行算法降低并行成本提供一個方向.隨著更多學(xué)者和專家的投入,相信會有更多具有高額成本的并行算法在快速解決問題的同時,有效減低并行技術(shù)產(chǎn)生巨額的成本.