基于PRAM并行模型最大值查找的方法與改進(jìn)①

賀 成,施華君

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

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

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

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

1 并行查找最大值的算法

1.1 平衡樹查找方法

1.1.1 算法原理

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

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

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

1.2 快速查找方法

1.2.1 算法原理

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

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

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

輸入:存有n個(gè)不同元素的數(shù)組A.輸出:布爾數(shù)組M,當(dāng)且僅當(dāng)A(i)=max{A}時(shí),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)同時(shí)讀,步驟(2)要求同時(shí)寫.

1.2.2 算法分析

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

1.3 雙對(duì)數(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層有 個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)有個(gè)子節(jié)點(diǎn).由此可以計(jì)算出樹的高度為k+1=loglogN.圖2為當(dāng)N=16時(shí)的雙對(duì)數(shù)深度樹[18].

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

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

22k輸入: n = 個(gè)數(shù)存于數(shù)組A(1:n)中.輸出:布爾數(shù)組M,當(dāng)且僅當(dāng)A(i)=max{A}時(shí),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í)行時(shí)間Tp(n)=O(loglogN),使用了P(n)=O(N)個(gè)處理器,成本為Cost=Tp?P=O(NloglogN).雙對(duì)數(shù)深度樹每次比較操作之后,待比較數(shù)據(jù)量減少的速度比平衡樹方法更快,每個(gè)處理器的工作量相比平衡樹方法都有更好的提升,所以雙對(duì)數(shù)深度樹的查找時(shí)間比平衡樹更快.但是雙對(duì)數(shù)深度樹的每個(gè)節(jié)點(diǎn)的最大值都是通過調(diào)用快速查找算法而實(shí)現(xiàn)的,所以雙對(duì)數(shù)深度樹的方法的實(shí)現(xiàn)的難度仍然很大.

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

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

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

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

2.1 算法原理

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

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

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

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

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

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

輸入: n個(gè)數(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 實(shí)驗(yàn)方式

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

3.1 實(shí)驗(yàn)原理

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

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

3.2 實(shí)驗(yàn)環(huán)境

操作系統(tǒng):Windows7

編程語言:Python3.6

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

處理器:CPU i7-4790 3.6 GHz

加速器:GPU GTX1070

編輯器:Pycharm Community Edition 2017.1.2

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

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

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

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

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

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

表2 實(shí)驗(yàn)結(jié)果時(shí)間對(duì)比表

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

圖7 算法運(yùn)行時(shí)間對(duì)比圖

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

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

4 結(jié)論與展望

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

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

圖9 算法成本對(duì)比圖

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