矩陣相乘 并行算法

《矩陣相乘 并行算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、并行處理技術(shù)課程設(shè)計(jì)分析報(bào)告課程設(shè)計(jì)題目矩陣相乘并行算法設(shè)計(jì)姓名廖杰學(xué)號(hào)M201372880專業(yè)計(jì)算機(jī)技術(shù)任課教師金海石宣化所在學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院報(bào)告提交日期2014-01-13一、實(shí)驗(yàn)?zāi)康?、學(xué)習(xí)使用集群；2、掌握并行處理或分布計(jì)算的編程方法；3、學(xué)會(huì)以并行處理的思想分析問(wèn)題。二、實(shí)驗(yàn)要求1、自行生成矩陣作為算法的輸入；2、使用并行處理技術(shù)編程，例如：MPI、OpenMP、MR；3、矩陣大小至少為1000*1000；4、加速比越大成績(jī)?cè)礁?。三、?shí)驗(yàn)內(nèi)容3.1、矩陣的劃分：對(duì)于矩陣相乘的并行算法，可以有三種：對(duì)矩陣按行劃分、按列劃分和棋盤式分塊劃分。和按行或列劃

2、分相比，棋盤式劃分可以開發(fā)出更高的并行度。對(duì)于一個(gè)n×n的方陣，棋盤劃分最多可以使用n^2個(gè)處理器進(jìn)行并行計(jì)算，但使用按行或列分解最多可以使用n個(gè)。對(duì)矩陣相乘采用棋盤式劃分的算法通常稱作Cannon算法。A）行列劃分又叫帶狀劃分（StripedPartitioning），就是將矩陣整行或者整列分成若干個(gè)組，每個(gè)組指派給一個(gè)處理器。下圖所例為4個(gè)CPU，8×8矩陣的帶狀劃分。在帶狀劃分情況下，每個(gè)CPU將會(huì)均勻分配到2行(列)數(shù)據(jù)。8×8矩陣變成了一個(gè)1×4或4×1的分塊矩陣，每個(gè)CPU所屬的分塊矩陣大小為8×2或2×8。B）棋盤劃分就是將矩陣分成若干個(gè)子矩陣，每個(gè)子矩

3、陣指派給一個(gè)處理器，此時(shí)任一處理器均不包含整行或者整列。下圖所示即為4個(gè)處理器情況下8×8矩陣的棋盤劃分，其中處理器陣列為2×2，每個(gè)處理器分配到的子矩陣大小為4×4。矩陣劃分成棋盤狀可以和處理器連成二維網(wǎng)孔相對(duì)應(yīng)。對(duì)于一個(gè)n×n維矩陣和p×p的二維處理器陣列，每個(gè)處理器均勻分配有（n/p）×(n/p)=n^2/p^2個(gè)元素。使用棋盤式劃分的矩陣相乘算法一般有兩種，Cannon算法和Summa算法。SUMMA算法能夠計(jì)算m*l的A矩陣和l*n的B矩陣相乘（m、l、n可不相等），而cannon算法只能實(shí)現(xiàn)n*n的A矩陣和n*n的B矩陣相乘，具有很大的局限性。3.2、算法

4、原理A)行劃分法假設(shè)是M*N，計(jì)算前，將矩陣N發(fā)送給所有從進(jìn)程，然后將矩陣M分塊，將M中數(shù)據(jù)按行分給各從進(jìn)程，在從進(jìn)程中計(jì)算M中部分行數(shù)據(jù)和N的乘積，最后將結(jié)果發(fā)送給主進(jìn)程。這里為了方便，有多少進(jìn)程，就將M分了多少塊，除最后一塊外的其他數(shù)據(jù)塊大小都相等，最后一塊是剩下的數(shù)據(jù)，大小大于等于其他數(shù)據(jù)塊大小，因?yàn)榫仃囆袛?shù)不一定整除進(jìn)程數(shù)。最后一塊數(shù)據(jù)在主進(jìn)程中計(jì)算，其他的在從進(jìn)程中計(jì)算。定義兩個(gè)矩陣M和N，N所有進(jìn)程都需要，M可以只在主進(jìn)程中定義。其他的變量視主進(jìn)程和從進(jìn)程需要按要求定義在合適的位置。代碼參見附錄部分。B)Cannon算法Cannon算法的基本思想可以如下表

5、示：假設(shè)兩個(gè)矩陣A和B相乘，把A和B矩陣劃分成p個(gè)方塊，進(jìn)程的編號(hào)從到，并在最初把子矩陣和分配給。雖然第i行的每個(gè)進(jìn)程需要全部的個(gè)子矩陣，但我們還是能調(diào)度第i行個(gè)進(jìn)程的計(jì)算，使得每個(gè)進(jìn)程在任何時(shí)刻都是用不同的。每完成一次矩陣乘法，這些塊在各進(jìn)程之間被輪流使用，似的每次輪流之后每個(gè)進(jìn)程都可以得到新的。對(duì)列使用同樣的調(diào)度，則在任何時(shí)刻，任何進(jìn)程至多擁有每個(gè)矩陣的一個(gè)塊，在所有進(jìn)程中，改算法需要的總內(nèi)存量為。下圖為此算法中不同進(jìn)程上子矩陣乘法的調(diào)度過(guò)程。假如矩陣C=A*B,則C的的計(jì)算公式如下：進(jìn)程P存儲(chǔ)分塊矩陣這一部分。塊矩陣乘法要計(jì)算所有匹配的和，然而只有在主對(duì)角線的才

6、是匹配的。因此需要采用循環(huán)移動(dòng)分塊矩陣的方法來(lái)使每個(gè)進(jìn)程都有一對(duì)可以直接相乘的匹配的塊，具體方法如下：(1)將排第i行的塊循環(huán)左移i個(gè)位置，將第列．塊循環(huán)上移j個(gè)位置；(2)進(jìn)程執(zhí)行乘一加運(yùn)算，然后將移動(dòng)得到的塊循環(huán)左移1個(gè)位置，將移動(dòng)得到的塊循環(huán)上移1個(gè)位置；(3)重復(fù)第2步(一1)次，每次移動(dòng)后進(jìn)程執(zhí)行乘一加運(yùn)算。經(jīng)過(guò)以上操作后就可以得到矩陣C的解。代碼請(qǐng)參見附錄部分C)Summa算法SUMMA算法首先將A,B和C劃分為相同大小的矩陣，對(duì)應(yīng)放在mesh_r×mesh_c的二維mesh上。但SUMMA算法將矩陣乘法分解為一系列的秩nb修正,即各處理器中的A和B分別被

7、分解為nb大小的列塊和行塊進(jìn)行相乘，前面所說(shuō)的分塊尺寸就是指nb的大小。算法中,廣播實(shí)現(xiàn)為邏輯處理器行環(huán)或列環(huán)上的流水線傳送,達(dá)到了計(jì)算與通信的重疊.具體描述如算法1所示。C=0fori=0tok-1stepnbdo　curcol=i×c/n　currow=i×r/m　ifmycol=currol向本行廣播A從imod(k/c)列開始的nb列,存于A′　ifmyrow=currow向本列廣播B從imod(k/r)行開始的nb行,存于B′　C=A′×B′endforSUMMA算法的核心思想是：各處理器收集來(lái)自同一行處理器中A矩陣子塊的所有列和同一列處理