Cannon乘法的MPI實現(xiàn)

《Cannon乘法的MPI實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、專業(yè)資料《并行算法實踐》要求學(xué)生在KD60實驗平臺上設(shè)計并行算法并實現(xiàn)。實驗平臺由一塊處理板、一塊監(jiān)控板和一塊背板等組成。處理板邏輯結(jié)構(gòu)如圖1所示。處理板承載4個處理單元，每個處理單元包括一個龍芯3號四核CPU、2GBDDR2內(nèi)存、RTL8110千兆以太網(wǎng)卡芯片、BIOSFlash、串口收發(fā)芯片以及電源變換電路等。四個龍芯3號處理器通過HT總線實現(xiàn)互連。監(jiān)控電路檢測4個處理單元的狀態(tài)，并實現(xiàn)對其控制。圖1處理板邏輯結(jié)構(gòu)實驗平臺的系統(tǒng)軟件以開源軟件為主（見圖2），具有兼容性強、易維護、易升級、易使用等特點。處理單元操作系統(tǒng)為DebianGNU/Linux無盤系統(tǒng)，采用穩(wěn)定高效的2.6.2

2、7內(nèi)核。圖2軟件系統(tǒng)結(jié)構(gòu)要求選修《并行算法實踐》同學(xué)在下面表1中選一個題目，（1）闡述基本原理（包括對算法改進和優(yōu)化方法）；(2)根據(jù)KD60實驗平臺設(shè)計實驗方法和步驟（包括主要調(diào)試過程要求拷屏）。(3)數(shù)據(jù)及結(jié)果分析：根據(jù)不同的實驗內(nèi)容，記錄具體的實驗數(shù)據(jù)或程序運行結(jié)果（要求拷屏）。實驗數(shù)據(jù)量較大時，最好制成表格形式。附上程序功能、模塊說明、完整源代碼，源代碼中盡量多帶注釋；(4)分析和總結(jié)：對程序與算法性能改進結(jié)論，總結(jié)和體會。word完美格式專業(yè)資料表1《并行算法實踐》題目序號題目名稱基本方法和內(nèi)容要求1LU分解的OpenMP實現(xiàn)編寫LU分解的OpenMP程序2KMP算法的Ope

3、nMP實現(xiàn)編寫KMP算法的OpenMP程序3高斯消元法解線性方程組的OpenMP實現(xiàn)編寫高斯消元法解線性方程組的OpenMP程序4高斯消元法解線性方程組的MPI實現(xiàn)編寫高斯消元法解線性方程組的MPI程序5高斯-塞德爾迭代解線性方程組的MPI實現(xiàn)編寫高斯-塞德爾迭代解線性方程組的MPI程序6Cannon乘法的MPI實現(xiàn)編寫Cannon乘法的MPI程序7LU分解的MPI實現(xiàn)編寫LU分解的MPI程序8隨機串匹配算法的MPI實現(xiàn)編寫隨機串匹配算法的MPI程序9單源最短路徑Dijkstra算法的MPI實現(xiàn)編寫單源最短路徑Dijkstra算法的MPI程序10快速排序算法的MPI實現(xiàn)編寫快速排序算法

4、的MPI程序11KMP串匹配的MPI實現(xiàn)編寫KMP串匹配算法的MPI程序圖2軟件系統(tǒng)結(jié)構(gòu)word完美格式專業(yè)資料Cannon乘法的MPI實現(xiàn)及性能分析摘要：cannon算法是矩陣的并行乘法，屬于數(shù)值并行算法MPI編程實現(xiàn)一篇，其中關(guān)于數(shù)值并行算法MPI編程由于要處理的數(shù)據(jù)量巨大，程序循環(huán)次數(shù)多，對于串行而言，處理時間將非常長，將其并行化非常必要。本文將矩陣數(shù)據(jù)進行棋盤劃分成多個子矩陣，再分別指派給多個處理器，使個處理器并行運算。關(guān)鍵字：cannon乘法并行計算數(shù)據(jù)劃分一、Cannon乘法的MPI實現(xiàn)基本原理Cannon乘法屬于數(shù)值并行算法MPI編程實現(xiàn)一篇，其中關(guān)于數(shù)值并行算法MPI編

5、程由于要處理的數(shù)據(jù)量巨大，程序循環(huán)次數(shù)多，對于串行而言，處理時間將非常長，使其并行化的一般方法有：1）數(shù)據(jù)相關(guān)分析2）數(shù)據(jù)劃分和處理器指派3）循環(huán)重構(gòu)對原有程序并行化，首先要分析計算程序中所有語句間的依賴關(guān)系，這稱之為相關(guān)分析。本項目Cannon乘法的mpi實現(xiàn)，是矩陣運算，階往往都很高，而且行列之間數(shù)據(jù)依賴關(guān)系也不強，所以就對矩陣進行劃分，然后指派給不同的處理器進行處理。最常用的矩陣劃分有帶狀劃分和塊狀劃分。1．帶狀劃分方法帶狀劃分又叫行列劃分，就是將矩陣整行或整列地分成若干組，各組指派給一個處理器。也可以將若干行或列指派給一個處理器，而且這些行和列可以是連續(xù)的，也可以是等間距的，前

6、者稱為塊帶狀的，后者稱為循環(huán)帶狀的。2.塊狀劃分方法塊狀劃分又叫棋盤劃分，就是將矩陣劃分成若干個子矩陣，每個子矩陣指派給一個處理器，此時任意處理器均不含整行或整列。和帶狀劃分類似，棋盤劃分也可分為塊棋盤劃分和循環(huán)棋盤劃分。棋盤劃分比帶狀劃分可開發(fā)更高的并行度，Cannon乘法的mpi實現(xiàn)也正是基于棋盤劃分的并行實現(xiàn)。循環(huán)重構(gòu)是指在數(shù)據(jù)分解之后，相應(yīng)地將串行程序循環(huán)部分進行重構(gòu)，以實現(xiàn)這種劃分所確定的并行計算，主要方法有1）循環(huán)交換2）拉伸法3）分裂法4）輪轉(zhuǎn)法5）并列法在三種程序并行化的方法中，數(shù)據(jù)相關(guān)分析和循環(huán)重構(gòu)目的都是挖掘語句間的并行性，而數(shù)據(jù)劃分和處理器指派則重在策略，宏觀上挖

7、掘并行性。Cannon算法是一種存儲有效的算法，設(shè)矩陣和相乘。為了使兩矩陣下標(biāo)滿足相乘的要求，和帶狀的并行分塊乘法不同，不是僅僅讓B矩陣的各列塊循環(huán)移動，而是有目的地讓A的各行塊以及B的各列塊皆施行循環(huán)移位，從而實現(xiàn)對C的子塊的計算。將矩陣A和B分成p個方塊Aij和Bij，，每塊大小為，并將它們分配給個處理器。開始時處理器Pij存放塊Aij和Bijword完美格式專業(yè)資料，并負責(zé)計算塊Cij，然后算法開始執(zhí)行：⑴將塊Aij向左循環(huán)移動i步；將