棋盤劃分下的矩陣—向量乘法

1、*實踐教學(xué)*大學(xué) 理學(xué)院 2016年春季學(xué)期 并行計算 課程設(shè)計專業(yè)班級：_ 姓 名： _學(xué) 號：_指導(dǎo)教師：_ 成 績：_棋盤劃分下的矩陣向量乘法摘要并行計算是計算機科學(xué)中重要研究內(nèi)容，已有幾十年的發(fā)展歷程，它是在串行計算的基礎(chǔ)上演變而來的。創(chuàng)建和應(yīng)用并行計算的最主要原因是因為它是解決單處理機速度瓶頸的最好的方法之一。并行計算的發(fā)展是大型復(fù)雜科學(xué)、工程問題的計算需求以及與當(dāng)代社會相關(guān)問題的需求。并行計算的研究需要并行計算機系統(tǒng)、并行算法和并行程序設(shè)計等專家以及并行應(yīng)用領(lǐng)域?qū)＜业墓餐瑓⑴c。矩陣向量乘法同樣可以有帶狀劃分和棋盤劃分下兩中并行算法。所謂棋盤劃分（Checker Board

2、 Partitioning）就是將方陣劃分成若干個子方陣，每個子方陣指派給一個處理器，此時任意處理器均不包含整行或整列。目 錄一、題目及要求2二、設(shè)計算法、算法原理2三、 算法描述、設(shè)計流程33.1算法描述33.2設(shè)計流程圖4四、源程序代碼及運行結(jié)果54.1源代碼54.2題目運行結(jié)果示意圖12五、算法分析、優(yōu)缺點125.1算法分析125.2優(yōu)缺點12六、總 結(jié)13七、參考文獻(xiàn)14一、題目及要求棋盤劃分的矩陣-向量乘法已知，求二、設(shè)計算法、算法原理所謂棋盤劃分（Checker Board Partitioning）就是將方陣劃分成若干子方陣，每個子方陣指派給一個處理器，此時任一處理器均

3、不包含整行整列。和帶狀劃分類似，棋盤劃分可分為塊棋盤劃分（Block- Checker Board Partitioning）和循環(huán)棋盤劃分（Cycile-Checker Board Partitioning）。如圖一所示：（a 塊棋盤劃分） （b.循環(huán)棋盤劃分）圖一 兩種棋盤劃分矩陣劃分成棋盤狀可和處理器連成二維網(wǎng)孔相對應(yīng)。對與一個nn的方陣和的二維處理器，每個處理器均勻的分配有2/p個矩陣元素。值得指出的是，和帶狀劃分相比，棋盤劃分可開發(fā)出更高的并行度。例如，對于一個nn的方陣，棋盤劃分最多可以使用n2個處理器進(jìn)行并行計算，但使用帶狀劃分可用的處理器不能多于n個。3、 算法描述、設(shè)計流程3

4、.1算法描述劃分(塊棋盤劃分): Pij存放ai,j, xi置入Pi,i中算法: 對p=n2情形 每個Pi,i向Pj,i播送xi(一到多播送)； 按行方向進(jìn)行乘-加與積累運算，最后一列Pi,n-1收集的結(jié)果為yi；注: 對p<n2情形,p個處理器排成的二維網(wǎng)孔， 算法中Pi,i向Pj,i播送X中相應(yīng)的個分量 (1)網(wǎng)孔連接的計算時間Tp(CT): .X中相應(yīng)分量置入Pi,i的通訊時間: .按列一到多播送時間: .按行單點積累的時間:示例如圖二所示：圖二 p時棋盤劃分的矩陣向量乘法3.2設(shè)計流程圖mpi的頭文件相關(guān)變量聲明MPI_INIT()MPI_COMM_RANK()MPI_COMM_

5、SIZE()進(jìn)入MPI系統(tǒng)矩陣內(nèi)部的通信應(yīng)用控制實體：矩陣內(nèi)部的計算程序MPI_FINALIZE()退出MPI系統(tǒng)結(jié)束開始循環(huán)直至結(jié)束圖三 程序流程設(shè)計圖四、源程序代碼及運行結(jié)果4.1源代碼#include<stdio.h>#include<stdlib.h>#include "mpi.h"#define intsize sizeof(int)#define floatsize sizeof(float)#define A(x,y) Ax*N+y#define B(x) Bx#define C(x) Cx#define a(x) ax#define

6、b(x) bx#define c(x) cxfloat *a,*b,*c;float *A,*B,*C;int M,N,K,P;int m,n;int myid;FILE *dataFile;MPI_Status status;double time1;double starttime,endtime;void readData() int i,j; starttime=MPI_Wtime(); dataFile=fopen("dataIn.txt","r"); fscanf(dataFile,"%d%d",&M,&N

7、); A=(float*)malloc(floatsize*M*N); for(i=0;i<M;i+) for(j=0;j<N;j+) fscanf(dataFile,"%f",A+i*N+j); fscanf(dataFile,"%d",&K); if(N!=K) printf("the input is wrongn"); exit(1); B=(float*)malloc(floatsize*K); for(i=0;i<K;i+) fscanf(dataFile,"%f",B+i);

8、 fscanf(dataFile,"%d",&P); fclose(dataFile); printf("Input of file dataIn.txtn"); printf("%dt %dn",M,N); for(i=0;i<M;i+) for(j=0;j<N;j+) printf("%ft",A(i,j); printf("n"); printf("%dn",K); for(i=0;i<K;i+) printf("%ft",

9、B(i); printf("n"); C=(float*)malloc(floatsize*M);void printfResult() int i; printf("nOutput of Matrix C=ABn"); for(i=0;i<M;i+) printf("%ft",C(i); printf("n"); endtime=MPI_Wtime(); printf("n"); printf("Whole running time = %f secondsn",en

10、dtime-starttime); printf("Distribute data time = %f secondsn",time1-starttime); printf("Parallel compute time = %f secondsn",endtime-time1);int main(int argc,char *argv) int i,k,group_size,p; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&group_size); MPI_Comm_r

11、ank(MPI_COMM_WORLD,&myid); p=group_size; if(myid=0) readData(); if(myid=0) for(i=0;i<p;i+) MPI_Send(&M,1,MPI_INT,i,i,MPI_COMM_WORLD); MPI_Send(&N,1,MPI_INT,i,i,MPI_COMM_WORLD); MPI_Send(&K,1,MPI_INT,i,i,MPI_COMM_WORLD); else MPI_Recv(&M,1,MPI_INT,0,myid,MPI_COMM_WORLD,&sta

12、tus); MPI_Recv(&N,1,MPI_INT,0,myid,MPI_COMM_WORLD,&status); MPI_Recv(&K,1,MPI_INT,0,myid,MPI_COMM_WORLD,&status); if(myid<p) a=(float *)malloc(floatsize*N); b=(float *)malloc(floatsize*K); c=(float *)malloc(floatsize*1); c(0)=0; if(a=NULL|b=NULL) printf("Allocate spzce for a

13、or b fail"); if(myid=0) for(i=0;i<N;i+) a(i)=A(0,i); b(i)=B(i); if(myid=0) for(i=1;i<p;i+) MPI_Send(&A(i,0),N,MPI_FLOAT,i,i,MPI_COMM_WORLD); MPI_Send(&B(0),N,MPI_FLOAT,i,i,MPI_COMM_WORLD); free(A); free(B); if(myid!=0) MPI_Recv(&a(0),N,MPI_FLOAT,0,myid,MPI_COMM_WORLD,&stat

14、us); MPI_Recv(&b(0),N,MPI_FLOAT,0,myid,MPI_COMM_WORLD,&status); if(myid=0) time1=MPI_Wtime(); for(i=0;i<N;i+) c(0)=c(0)+a(i)*b(i); if(myid!=0) MPI_Send(&c(0),1,MPI_FLOAT,0,myid,MPI_COMM_WORLD); if(myid=0) C(0)=c(0); for(i=1;i<p;i+) MPI_Recv(&C(i),1,MPI_FLOAT,i,i,MPI_COMM_WORLD,

15、&status); if(myid=0) printfResult(); MPI_Finalize(); if(myid<p) free(a); free(b); free(c); if(myid=0) free(C); return(0);4.2題目運行結(jié)果示意圖圖四 運行結(jié)果五、算法分析、優(yōu)缺點5.1算法分析在處理過程中，每個處理器存放有矩陣的一個元素，而向量xi通常是存放在pii中的。如果xi是存放在處理器陣列的最后一列中，則進(jìn)行矩陣向量乘時，先要將向量元素與矩陣主對角線對準(zhǔn)，在列方向上施行向量元素一到多播送；播送完畢后，接著施行乘加和單點累積，最后按行收集結(jié)果向量y。因為

16、每個處理器執(zhí)行乘加操作的時間為常數(shù)，所以在nn的網(wǎng)孔上和n2個處理器的超立方上的并行矩陣向量乘之總時間分別為O（n）和O（），他們不是成本最佳的。5.2優(yōu)缺點 在網(wǎng)孔上用同樣多的處理器，棋盤劃分的矩陣向量乘法比帶狀劃分時要快。如果p>n，則無法使用帶狀劃分，而棋盤劃分不受此限制，即使pn，棋盤劃分也更優(yōu)。值得指出的是，和帶狀劃分相比，棋盤劃分可開發(fā)出更高的并行度。例如，對于一個nn的方陣，棋盤劃分最多可以使用n個處理器進(jìn)行并行計算，但使用帶狀劃分可用的處理器不能多于n個。六、總結(jié)通過本次并行計算課程設(shè)計，通過對所學(xué)知識的融會貫通，我加深了解了并行計算在大數(shù)據(jù)之中的應(yīng)用以及他的優(yōu)點。并行算

17、法是并行計算中非常重要的問題。并行算法研究應(yīng)該確立一個“理論設(shè)計實現(xiàn)應(yīng)用”的系統(tǒng)方法，形成一個完善“架構(gòu)算法編程”的方法論，這樣才能保證并行算法不斷發(fā)展并變得更加實用。在課程設(shè)計中，我遇到了許多問題，而這些問題的產(chǎn)生都是由于我在理論知識和實踐經(jīng)驗的缺乏而造成的。在此過程中，感觸最深的便是實踐聯(lián)系理論的重要性，當(dāng)遇到實際問題時，只要認(rèn)真思考，用所學(xué)的知識，再一步步探索，是完全可以解決遇到的一般問題的。通過老師的指導(dǎo)和自學(xué)克服了很多的困難，我得到了一次難得的鍛煉機會，加深了對理論知識的理解，也讓我更加深刻地體會到自學(xué)能力的重要性。課程設(shè)計讓我真正做到了學(xué)有所用，在設(shè)計當(dāng)中受益匪淺。通過這次的課程學(xué)習(xí)，我也認(rèn)識到了自己的很多不足，對專業(yè)知識的不夠熟悉，以至于在設(shè)計學(xué)習(xí)過程中卡住了好多次，我想在今后的學(xué)習(xí)中我會加大自己的學(xué)習(xí)力度，努力強化自己的專業(yè)知識，同時也學(xué)習(xí)其他同學(xué)思考問題的思路，在以后的學(xué)習(xí)中可以借鑒。在本次課程設(shè)計中老師耐心細(xì)致地給予了我很多的指導(dǎo)，在此深表感謝，我相信通過這次課程設(shè)計的鍛煉，能為我以后處理程序設(shè)計打下堅實的基礎(chǔ)。七、參考文獻(xiàn)1陳國良，章峰，吳俊敏，等.002.并行計算機體系結(jié)構(gòu).北京：高等教育出版社.2陳國良.并行算法的可擴(kuò)放性分析.小型微型計算機系統(tǒng)，16(2):10-16.1995.3陳國良.并行算法的設(shè)計與分析.