基于maprence模型的矩陣并行l(wèi)u分解

基于maprence模型的矩陣并行l(wèi)u分解

內(nèi)聯(lián)是google提出的并行分布式編程模型。在MapRedcue模型中用戶只須指定一個map函數(shù)來處理一個輸入的key/value對,產(chǎn)生中間結(jié)果key/value對,再通過一個由用戶指定的reduce函數(shù)來處理中間結(jié)果中具有相同key值的value。借鑒Hadoop,以BoostMPI為基礎(chǔ)實現(xiàn)了MapReduce系統(tǒng)——高性能MapReduce(HighPerformanceMapReduce,HPMR),它更適應(yīng)于數(shù)值計算。本文分析矩陣的LU分解算法在HPMR上的應(yīng)用,闡述運用MapReduce模型解決并行問題的方法,該方法清晰簡潔。1map創(chuàng)造算法在傳統(tǒng)并行編程過程中,程序員必須花大量的精力去處理進程間通信。WordCount被用來統(tǒng)計輸入數(shù)據(jù)中各單詞出現(xiàn)的次數(shù)。以WordCount為例,MPI的一種實現(xiàn)方式為:在各個MPI進程完成各自的統(tǒng)計任務(wù)后,將結(jié)果匯總給某一個進程,然后由該進程進行最終統(tǒng)計。該實現(xiàn)方式很容易在完成最終統(tǒng)計任務(wù)的進程處形成通信瓶頸,而最終統(tǒng)計任務(wù)是以順序方式完成,會導(dǎo)致統(tǒng)計效率低下。采用并行分類統(tǒng)計能提升效率,即收集各個進程獲得的關(guān)于某個相同單詞的局部統(tǒng)計信息,并將這些信息匯總給某個進程處進行分類統(tǒng)計。然而由于這種實現(xiàn)方式僅確定能產(chǎn)生某個單詞統(tǒng)計信息的進程范圍,因此會增加編程復(fù)雜度。在MapReduce模型下,完成單詞統(tǒng)計的具體步驟為:(1)用戶編寫Map程序?qū)Τ霈F(xiàn)的單詞word產(chǎn)生中間結(jié)果key/value偶對,如<word,1>。(2)這些分布產(chǎn)生的中間結(jié)果將按key值的不同進行匯總處理,產(chǎn)生key(word)相同的value列表,如<word,1,1,1,…>,并作為Reduce階段的輸入,這個階段的工作將由MapReduce運行系統(tǒng)自動完成。(3)用戶提供的Reduce程序只須將獲得的value累加即可得到結(jié)果。Map算法和Reduce算法如下:圖1是在MapReduce模型下的WordCount運行示意圖。由上文可知,與傳統(tǒng)并行編程模型相比,MapReduce模型具有較高的并行表述抽象性。用戶僅須提供Map和Reduce操作函數(shù)即可。與MPI類似,MapReduce是一種顯式數(shù)據(jù)劃分的并行分布式編程模型。在Map階段局部數(shù)據(jù)處理通常產(chǎn)生局部結(jié)果。用戶可以借助MapReduce模型提供的key/value策略,把對全局(或階段性)計算結(jié)果有影響且有關(guān)聯(lián)的value采用相同key標志。由于這種策略的簡單抽象,因此用戶可以較容易地把握局部和全局關(guān)系,從而確保問題求解并行實現(xiàn)的正確性,并進一步降低并行分布式編程的難度。2矩陣計算中的hpmr應(yīng)用2.1不同子矩陣描述及描述在矩陣并行計算前須對矩陣進行劃分,即把一個大矩陣劃分成若干子矩陣,每個子矩陣分配給不同進程或線程處理。在HPMR中,每個矩陣子塊稱為sub_matrix類,包含2個部分的內(nèi)容:子矩陣描述和子矩陣數(shù)據(jù)。子矩陣描述包含劃分相關(guān)的信息,如劃分方式、總塊數(shù)、本塊塊號、子塊起始/終止行(或列)號等,以及和矩陣計算特征有關(guān)的信息,如LU分解中的主行行號。而子矩陣數(shù)據(jù)為實際存儲子塊數(shù)據(jù)地址的指針,如圖2所示。2.2矩陣、并行流分解算法2.2.1map和run的工藝流程LU分解算法是把一個給定的n階方陣A分解成一個下三角陣。在分解的過程中,主要計算是利用主行k(k:1~n)依次對其余各行i(i>k)做初等變換,各行計算之間沒有數(shù)據(jù)相關(guān)性,因此,可以對矩陣A按行劃分實現(xiàn)并行計算。LU分解主要串行代碼如下:由于MapReduce依然屬于顯式數(shù)據(jù)劃分與并行計算模型,因此須按照特定數(shù)據(jù)劃分策略將待分解的矩陣劃分為若干個子數(shù)據(jù)塊,所用的劃分方法可以是按行連續(xù)劃分或按行交錯劃分等方式。然后根據(jù)LU分解串行計算的語義及劃分方式,可以較容易地寫出Map和Reduce處理過程,描述如下:(1)Map:檢查當前數(shù)據(jù)子塊是否要使用當前主行進行變換。1)如果Map持有的數(shù)據(jù)子塊不包含主行號i的數(shù)據(jù)行,且主行號i沒有超越本地數(shù)據(jù)子塊所持有行的行號范圍,則產(chǎn)生<key=本地數(shù)據(jù)子塊號#current_block,Val=本地數(shù)據(jù)子塊>;2)如果Map持有的數(shù)據(jù)子塊包含了主行號i的數(shù)據(jù)行,則產(chǎn)生<key=本地數(shù)據(jù)子塊號#current_block,Val=本地數(shù)據(jù)子塊>,然后針對所有其他需要變換的劃分子塊分別產(chǎn)生<key=其他數(shù)據(jù)子塊號#other_block,Val=主行數(shù)據(jù)>。(2)Reduce:對要變換的數(shù)據(jù)子塊實施相應(yīng)主行變換。1)對經(jīng)過MapReduce運行時匯聚后的<key=數(shù)據(jù)子塊號#block,Val1=子塊號為#block的數(shù)據(jù)子塊,Val2=主行數(shù)據(jù)>中的數(shù)據(jù)子塊進行相應(yīng)主行變換;2)產(chǎn)生<key=數(shù)據(jù)子塊號#block,Val=變換后的子塊號為#block的數(shù)據(jù)子塊(主行號增1)>作為下一輪MapReduce的輸入。圖3顯示了某輪MapReduce過程中Map產(chǎn)生的key/val,其中,左邊給出進行LU分解的矩陣劃分,如子塊b0,b1和b2;右邊給出了Map產(chǎn)生的key/val偶對序列,b0因含有主行i而產(chǎn)生4個key/val偶對,而其余劃分分別只產(chǎn)生1個key/val偶對。經(jīng)過一輪MapReduce過程,完成了以某一行為主行的LU變換,對于n階的方陣來說,完成整個LU變換的過程僅要進行n-1輪的變換。HPMR為用戶提供了控制迭代次數(shù)的接口,通過這些接口可以設(shè)置MapReduce循環(huán)的輪數(shù)和循環(huán)停止的條件。2.2.2廣播方式與hpmr比較2000階、4000階、6000階、8000階矩陣LU分解分別如圖4~圖7所示。由此可知,當進程數(shù)較少時,HPMR的性能與Boost_MPI相當,當進程數(shù)為10時,HPMR的性能略高。在LU分解中總有一個進程將主行發(fā)送給其他需要變換的進程,這種一到多的通信方式,在Boost_MPI實現(xiàn)的LU分解程序中是通過廣播實現(xiàn)的,在HPMR中采用點到點的通信方式。根據(jù)本文測試,在進程數(shù)目較少的情況下,采用點對點通信方式實現(xiàn)的LU分解比采用廣播方式實現(xiàn)的性能好。但當進程數(shù)目增多的時候廣播方式的性能更好。當進程數(shù)目大于30時采用廣播通信的Boost_MPI程序的性能比HPMR好得多,但是在進程數(shù)小于25時,HPMR有很好的加速性能。20個進程的性能比較如圖8所示,由此可知,在進程數(shù)為20時,隨著矩陣規(guī)模的增大,HPMR的性能接近于Boost_MPI,但在進程數(shù)增多時,用點對點方式實現(xiàn)影響了一到多通信的性能。2.2.3map創(chuàng)造時間MapReduce程序在每一輪的運行中都有3個過程:(1)Map過程,時間用tm表示;(2)中間結(jié)果的處理過程,時間用tp表示;(3)Reduce過程,時間用tr表示。數(shù)據(jù)分發(fā)過程所需時間用td表示,最后結(jié)果收集所需時間用tq表示,整個MapReduce過程的迭代次數(shù)用n表示,整個過程所用的時間用T表示。使用大同步并行(BulkSynchronousParallel,BSP)模型對MapRedcue進行分析。MapRedcue一個超級計算步的成本為其中,L為每輪之間的路障同步時間。整個MapRedcue程序所需時間為由于tm和tr是數(shù)據(jù)處理過程所需要的時間,與具體應(yīng)用的算法有關(guān),在系統(tǒng)中很難進行優(yōu)化。tp除了同步外,key的統(tǒng)計和key/value對的通信占了很大比例。因此,