基于PRAM并行模型最大值查找的方法與改進①

賀 成,施華君

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

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

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

本文并行算法研究是在PRAM[8,9]模型下進行的,但微型計算機CPU架構中的SIMD并行機制,由于實現指令的復雜性,幾乎沒有編譯程序將高級語言設計的程序優化到SIMD指令級別[10].因此本文通過模擬仿真實驗對幾種并行查找算法的實際運行時間進行對比.

1 并行查找最大值的算法

1.1 平衡樹查找方法

1.1.1 算法原理

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

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

輸入:n = 2m個數存于數組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 算法分析

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

1.2 快速查找方法

1.2.1 算法原理

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

表1 邏輯關系表

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

輸入:存有n個不同元素的數組A.輸出:布爾數組M,當且僅當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 算法分析

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

1.3 雙對數深度樹查找方法

1.3.1 算法原理

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

圖2 雙對數深度樹

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

22k輸入: n = 個數存于數組A(1:n)中.輸出:布爾數組M,當且僅當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 算法分析

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

2 基于數據劃分的最大值查找算法

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

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

最終實現了一種比平衡樹算法,快速查找法,雙對數深度樹方法并行成本額Cost更優的高度可行的基于數據劃分查找最大值的并行算法.

2.1 算法原理

從邏輯上將集合中的數據進行分組,假設共N個元素,分為logN組,每組N/logN個元素,共N/logN個處理器.

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

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

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

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

下面是基于數據劃分算法的偽代碼:

輸入: n個數存放于A[logn][logn]數組中輸出:最大值A[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),并且在該模型上實現了平衡樹與雙對數深度樹查找的并行算法[21].由于實驗條件所限,無法實現真正搭建并行機和LARPBS.鑒于此種情況,本文采用多核并行計算進行仿真模擬實驗.深度學習[22]中神經網絡利用Tensor flow學習庫來構建計算圖,通過GPU進行計算圖中部分節點并行計算,從而實現并行加速效果.因此本文也使用基于TensorFlow的GPU[23,24]處理框架來進行仿真模擬實驗.

3.1 實驗原理

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

圖3 數據量為8的平衡二叉樹方法tensorflow計算圖

3.2 實驗環境

操作系統:Windows7

編程語言:Python3.6

機器學習庫:Tensorflow-GPU 1.12.0

處理器:CPU i7-4790 3.6 GHz

加速器:GPU GTX1070

編輯器:Pycharm Community Edition 2017.1.2

圖4 數據量為16的雙對數深度樹tensorflow計算圖

圖5 數據量為4的快速查找算法計算圖

圖6 數據量為16的數據劃分方法計算圖

3.3 實驗結果與分析

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

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

表2 實驗結果時間對比表

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

圖7 算法運行時間對比圖

表3 模擬處理器數量對比表

圖8 算法使用處理器數目對比圖

4 結論與展望

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

表4 運行成本對比表

圖9 算法成本對比圖

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