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

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

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