cannon乘法地mpi實(shí)現(xiàn)

《cannon乘法地mpi實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

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

2、元操作系統(tǒng)為DebianGNU/Linux無(wú)盤(pán)系統(tǒng)，采用穩(wěn)定高效的2.6.27內(nèi)核。圖2軟件系統(tǒng)結(jié)構(gòu)要求選修《并行算法實(shí)踐》同學(xué)在下面表1中選一個(gè)題目，（1）闡述基本原理（包括對(duì)算法改進(jìn)和優(yōu)化方法）；(2)根據(jù)KD60實(shí)驗(yàn)平臺(tái)設(shè)計(jì)實(shí)驗(yàn)方法和步驟（包括主要調(diào)試過(guò)程要求拷屏）。(3)數(shù)據(jù)及結(jié)果分析：根據(jù)不同的實(shí)驗(yàn)內(nèi)容，記錄具體的實(shí)驗(yàn)數(shù)據(jù)或程序運(yùn)行結(jié)果（要求拷屏）。實(shí)驗(yàn)數(shù)據(jù)量較大時(shí)，最好制成表格形式。附上程序功能、模塊說(shuō)明、完整源代碼，源代碼中盡量多帶注釋?zhuān)?4)分析和總結(jié)：對(duì)程序與算法性能改進(jìn)結(jié)論，總結(jié)和體會(huì)。標(biāo)準(zhǔn)

3、文檔實(shí)用文案表1《并行算法實(shí)踐》題目序號(hào)題目名稱(chēng)基本方法和內(nèi)容要求1LU分解的OpenMP實(shí)現(xiàn)編寫(xiě)LU分解的OpenMP程序2KMP算法的OpenMP實(shí)現(xiàn)編寫(xiě)KMP算法的OpenMP程序3高斯消元法解線性方程組的OpenMP實(shí)現(xiàn)編寫(xiě)高斯消元法解線性方程組的OpenMP程序4高斯消元法解線性方程組的MPI實(shí)現(xiàn)編寫(xiě)高斯消元法解線性方程組的MPI程序5高斯-塞德?tīng)柕饩€性方程組的MPI實(shí)現(xiàn)編寫(xiě)高斯-塞德?tīng)柕饩€性方程組的MPI程序6Cannon乘法的MPI實(shí)現(xiàn)編寫(xiě)Cannon乘法的MPI程序7LU分解的MPI實(shí)現(xiàn)

4、編寫(xiě)LU分解的MPI程序8隨機(jī)串匹配算法的MPI實(shí)現(xiàn)編寫(xiě)隨機(jī)串匹配算法的MPI程序9單源最短路徑Dijkstra算法的MPI實(shí)現(xiàn)編寫(xiě)單源最短路徑Dijkstra算法的MPI程序10快速排序算法的MPI實(shí)現(xiàn)編寫(xiě)快速排序算法的MPI程序11KMP串匹配的MPI實(shí)現(xiàn)編寫(xiě)KMP串匹配算法的MPI程序圖2軟件系統(tǒng)結(jié)構(gòu)標(biāo)準(zhǔn)文檔實(shí)用文案Cannon乘法的MPI實(shí)現(xiàn)及性能分析摘要：cannon算法是矩陣的并行乘法，屬于數(shù)值并行算法MPI編程實(shí)現(xiàn)一篇，其中關(guān)于數(shù)值并行算法MPI編程由于要處理的數(shù)據(jù)量巨大，程序循環(huán)次數(shù)多，對(duì)于串行

5、而言，處理時(shí)間將非常長(zhǎng)，將其并行化非常必要。本文將矩陣數(shù)據(jù)進(jìn)行棋盤(pán)劃分成多個(gè)子矩陣，再分別指派給多個(gè)處理器，使個(gè)處理器并行運(yùn)算。關(guān)鍵字：cannon乘法并行計(jì)算數(shù)據(jù)劃分一、Cannon乘法的MPI實(shí)現(xiàn)基本原理Cannon乘法屬于數(shù)值并行算法MPI編程實(shí)現(xiàn)一篇，其中關(guān)于數(shù)值并行算法MPI編程由于要處理的數(shù)據(jù)量巨大，程序循環(huán)次數(shù)多，對(duì)于串行而言，處理時(shí)間將非常長(zhǎng)，使其并行化的一般方法有：1）數(shù)據(jù)相關(guān)分析2）數(shù)據(jù)劃分和處理器指派3）循環(huán)重構(gòu)對(duì)原有程序并行化，首先要分析計(jì)算程序中所有語(yǔ)句間的依賴(lài)關(guān)系，這稱(chēng)之為相關(guān)分析。

6、本項(xiàng)目Cannon乘法的mpi實(shí)現(xiàn)，是矩陣運(yùn)算，階往往都很高，而且行列之間數(shù)據(jù)依賴(lài)關(guān)系也不強(qiáng)，所以就對(duì)矩陣進(jìn)行劃分，然后指派給不同的處理器進(jìn)行處理。最常用的矩陣劃分有帶狀劃分和塊狀劃分。1．帶狀劃分方法帶狀劃分又叫行列劃分，就是將矩陣整行或整列地分成若干組，各組指派給一個(gè)處理器。也可以將若干行或列指派給一個(gè)處理器，而且這些行和列可以是連續(xù)的，也可以是等間距的，前者稱(chēng)為塊帶狀的，后者稱(chēng)為循環(huán)帶狀的。2.塊狀劃分方法塊狀劃分又叫棋盤(pán)劃分，就是將矩陣劃分成若干個(gè)子矩陣，每個(gè)子矩陣指派給一個(gè)處理器，此時(shí)任意處理器均不含

7、整行或整列。和帶狀劃分類(lèi)似，棋盤(pán)劃分也可分為塊棋盤(pán)劃分和循環(huán)棋盤(pán)劃分。棋盤(pán)劃分比帶狀劃分可開(kāi)發(fā)更高的并行度，Cannon乘法的mpi實(shí)現(xiàn)也正是基于棋盤(pán)劃分的并行實(shí)現(xiàn)。循環(huán)重構(gòu)是指在數(shù)據(jù)分解之后，相應(yīng)地將串行程序循環(huán)部分進(jìn)行重構(gòu)，以實(shí)現(xiàn)這種劃分所確定的并行計(jì)算，主要方法有1）循環(huán)交換2）拉伸法3）分裂法4）輪轉(zhuǎn)法5）并列法在三種程序并行化的方法中，數(shù)據(jù)相關(guān)分析和循環(huán)重構(gòu)目的都是挖掘語(yǔ)句間的并行性，而數(shù)據(jù)劃分和處理器指派則重在策略，宏觀上挖掘并行性。Cannon算法是一種存儲(chǔ)有效的算法，設(shè)矩陣和相乘。為了使兩矩陣下

8、標(biāo)滿(mǎn)足相乘的要求，和帶狀的并行分塊乘法不同，不是僅僅讓B矩陣的各列塊循環(huán)移動(dòng)，而是有目的地讓A的各行塊以及B的各列塊皆施行循環(huán)移位，從而實(shí)現(xiàn)對(duì)C的子塊的計(jì)算。將矩陣A和B分成p個(gè)方塊Aij和Bij，，每塊大小為，并將它們分配給個(gè)處理器。開(kāi)始時(shí)處理器Pij存放塊Aij和Bij標(biāo)準(zhǔn)文檔實(shí)用文案，并負(fù)責(zé)計(jì)算塊Cij，然后算法開(kāi)始執(zhí)行：⑴將塊Aij向左循環(huán)移動(dòng)i步；將塊Bij向上循環(huán)移動(dòng)j步