并行編程報(bào)告

1、并行編程報(bào)告課程名稱：并行編程原理專業(yè)班級(jí)：物聯(lián)網(wǎng) 1102 班學(xué)號(hào) :U201114483學(xué)生姓名：陳炳良指導(dǎo)教師：金海報(bào)告日期：2014-6-11計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院精選文庫目錄實(shí)驗(yàn)一：利用pthread 并行實(shí)現(xiàn)矩陣的乘法運(yùn)算3實(shí)驗(yàn)?zāi)康?實(shí)驗(yàn)概述3實(shí)驗(yàn)結(jié)果3實(shí)驗(yàn)代碼5實(shí)驗(yàn)總結(jié)9實(shí)驗(yàn)二：使用并行方法優(yōu)化K-means 算法10實(shí)驗(yàn)?zāi)康?0實(shí)驗(yàn)概述10實(shí)驗(yàn)結(jié)果10實(shí)驗(yàn)代碼.11實(shí)驗(yàn)總結(jié).182精選文庫實(shí)驗(yàn)一：利用 pthread并行實(shí)現(xiàn)矩陣的乘法運(yùn)算實(shí)驗(yàn)?zāi)康脑搶?shí)驗(yàn)旨在讓學(xué)生掌握利用pthread 進(jìn)行并行程序設(shè)計(jì)和性能優(yōu)化的基本原理和方法，了解并行程序設(shè)計(jì)中數(shù)據(jù)劃分和任務(wù)劃分的基本方法，并能

2、夠利用pthread 實(shí)現(xiàn)矩陣的乘法運(yùn)算的并行算法， 然后對(duì)程序執(zhí)行結(jié)果進(jìn)行簡單分析和總結(jié)。具體包括： 利用 for循環(huán)編寫串行的矩陣乘法運(yùn)算； 熟悉 pthread 進(jìn)行線程創(chuàng)建、 管理和銷毀的基本原理和方法；利用 pthread 對(duì)上述串行的矩陣乘法運(yùn)算加以改造；通過調(diào)整數(shù)據(jù)劃分和任務(wù)劃分的粒度( 改變工作線程的數(shù)目 ) ，測試并行程序的執(zhí)行效率；對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行總結(jié)和分析。實(shí)驗(yàn)概述使用 pThread 完成這項(xiàng)工作。創(chuàng)建一個(gè)新的線程：int pthread_create( pthread_t *thread,const pthread_attr_t *attr,void *(*func)

3、(void *),void *arg);thread表示線程 ID ，與線程中的pid概念類似attr表示設(shè)定線程的屬性，可以暫時(shí)不用考慮func表示新創(chuàng)建的線程會(huì)從這個(gè)函數(shù)指針處開始運(yùn)行arg表示這個(gè)函數(shù)的參數(shù)指針返回值為 0 代表成功，其他值為錯(cuò)誤編號(hào)。主進(jìn)程等待線程結(jié)束：int pthread_join( pthread_t thread, void *retval );thread表示線程 ID ，與線程中的pid概念類似retval用于存儲(chǔ)等待線程的返回值兩個(gè)矩陣相乘：一個(gè) m 行 n 列的矩陣與一個(gè)n行 p 列的矩陣可以相乘，得到的結(jié)果是一個(gè)m 行 p列的矩陣，其中的第 i行第 j

4、列位置上的數(shù)為第一個(gè)矩陣第i 行上的 n 個(gè)數(shù)與第二個(gè)矩陣第 j 列上的 n個(gè)數(shù)對(duì)應(yīng)相乘后所得的n 個(gè)乘積之和。實(shí)驗(yàn)結(jié)果3精選文庫實(shí)驗(yàn)隨機(jī)產(chǎn)生的矩陣B 的數(shù)據(jù)4精選文庫并行以及串行計(jì)算時(shí)間對(duì)比實(shí)驗(yàn)代碼1. 并行計(jì)算矩陣相乘代碼：#include<stdio.h>#include<time.h>#include<pthread.h>#include<stdlib.h>#include<unistd.h>#include<memory.h>/* 定義矩陣中元素的上限，避免相乘后溢出*/#define RANGE 150/* 矩

5、陣 A有 M行 N列，矩陣 B有 N行 M列*/#define M 200#define N 300int matrixAMN;int matrixBNM;int arrMMN;int resMM=0;void *func(void *arg);void put();void *func(void *arg)/每個(gè)子線程要完成的任務(wù)int k=*(int *)arg;5精選文庫int i,j;for(i=0;i<M;i+)for(j=0;j<M;j+)arrijk=matrixAik*matrixBkj;pthread_exit(NULL);main()/ 隨即產(chǎn)生兩個(gè)矩陣int

6、i,j,k;srand(unsigned)time(NULL);for(i=0;i<M;i+)for(j=0;j<N;j+)matrixAij = rand()%RANGE;for(i=0;i<N;i+)for(j=0;j<M;j+)matrixBij = rand()%RANGE;clock_t start=clock();/開始計(jì)時(shí)pthread_t tidsN;for(i=0;i<N;i+)if(pthread_create(&tidsi,NULL,func,(void*)&i)/產(chǎn)生線程， 去完成矩陣相乘的部分工作量perror("

7、;pthread_create");exit(1);for(i=0;i<N;i+)pthread_join(tidsi,NULL);/等待所有的子線程計(jì)算結(jié)束for(i=0;i<M;i+) /合。for(j=0;j<M;j+)for(k=0;k<N;k+)resij+=arrijk;clock_t finish=clock();/結(jié)束計(jì)算printf("并行計(jì)算用時(shí)%.2f 秒 n",(long)(finish-start)/1E6);put();exit(0);void put()FILE *file1,*file2,*file3;6精選

8、文庫if(file1=fopen("matrixA","wt")=NULL)perror("fopen");exit(1);if(file2=fopen("matrixB","wt")=NULL)perror("fopen");exit(1);if(file3=fopen("res","wt")=NULL)perror("fopen");exit(1);int i,j,k;for(i=0;i<M;i+)for(

9、j=0;j<N;j+)fprintf(file1,"%-8d",matrixAij);fprintf(file1,"n");fclose(file1);for(i=0;i<N;i+)for(j=0;j<M;j+)fprintf(file2,"%-8d",matrixBij);fprintf(file2,"n");fclose(file2);for(i=0;i<M;i+)for(j=0;j<M;j+)fprintf(file3,"%-8d",resij);fprint

10、f(file3,"n");fclose(file3);2. 串行計(jì)算矩陣相乘代碼：#include<stdio.h>#include<time.h>#include<pthread.h>#include<stdlib.h>#include<unistd.h>7精選文庫#include<memory.h>/* 定義矩陣中元素的上限，避免相乘后溢出*/#define RANGE 150/* 矩陣 A有 M行 N列，矩陣 B有 N行 M列*/#define M 200#define N 300int matr

11、ixAMN;int matrixBNM;int arrMMN;int resMM=0;void *func(void *arg);void put();main()/ 隨即產(chǎn)生兩個(gè)矩陣int i,j,k;srand(unsigned)time(NULL);for(i=0;i<M;i+)for(j=0;j<N;j+)matrixAij = rand()%RANGE;for(i=0;i<N;i+)for(j=0;j<M;j+)matrixBij = rand()%RANGE;clock_t start=clock();/開始計(jì)時(shí)for(i=0;i<M;i+)for(j

12、=0;j<M;j+)for(k=0;k<N;k+)resij+=matrixAik*matrixBkj;clock_t finish=clock();/結(jié)束計(jì)算printf("串行計(jì)算用時(shí)%.2f 秒 n",(long)(finish-start)/1E6);put();exit(0);void put()FILE *file1,*file2,*file3;if(file1=fopen("matrixA","wt")=NULL)perror("fopen");exit(1);8精選文庫if(file2=

13、fopen("matrixB","wt")=NULL)perror("fopen");exit(1);if(file3=fopen("res","wt")=NULL)perror("fopen");exit(1);int i,j,k;for(i=0;i<M;i+)for(j=0;j<N;j+)fprintf(file1,"%-8d",matrixAij);fprintf(file1,"n");fclose(file1);fo

14、r(i=0;i<N;i+)for(j=0;j<M;j+)fprintf(file2,"%-8d",matrixBij);fprintf(file2,"n");fclose(file2);for(i=0;i<M;i+)for(j=0;j<M;j+)fprintf(file3,"%-8d",resij);fprintf(file3,"n");fclose(file3);實(shí)驗(yàn)總結(jié)由于本次隨機(jī)矩陣相乘的計(jì)算量不是很大， 所以最終的比較結(jié)果是， 串行計(jì)算時(shí)間要遠(yuǎn)遠(yuǎn)小于并行計(jì)算時(shí)間， 其主要原因是因?yàn)椴?/p>

15、行計(jì)算中要?jiǎng)?chuàng)建， 銷毀線程， 這個(gè)過程消耗了大部分時(shí)間。與此同時(shí)，我對(duì)串行編程有了更加深刻的了解，對(duì)并行編程也有了初步的感官，對(duì)我日后的優(yōu)化編程有了很深的啟發(fā)。9精選文庫實(shí)驗(yàn)二：使用并行方法優(yōu)化K-means 算法實(shí)驗(yàn)?zāi)康脑擁?xiàng)目要求學(xué)生了解并掌握對(duì)復(fù)雜問題進(jìn)行并行程序設(shè)計(jì)和優(yōu)化的方法。在相關(guān)工具和框架的幫助下， 利用數(shù)據(jù)劃分和任務(wù)劃分方法實(shí)現(xiàn)并行算法，并對(duì)并行算法進(jìn)行優(yōu)化。在了解熟悉 K-means問題的基礎(chǔ)上建立合適的數(shù)據(jù)結(jié)構(gòu)與程序結(jié)構(gòu)，編寫程序求解K-means問題，分析算法的時(shí)間與空間復(fù)雜度。 根據(jù)并行算法并行化過程中的問題分解和解除數(shù)據(jù)相關(guān)的方法。自行選取相關(guān)的并行程序開發(fā)工具和框架，

16、設(shè)計(jì)并行化的回溯算法，并用其解決K-means 問題，進(jìn)而設(shè)計(jì)和調(diào)整解決BFS 問題并行算法的并行粒度，實(shí)現(xiàn)不同粒度下的并行化算法，對(duì)比分析其性能，最后，要求能夠在Linux環(huán)境下使用C/C+ 語言編程實(shí)現(xiàn)，同時(shí)測量算法執(zhí)行時(shí)間，與串行程序進(jìn)行對(duì)比分析。實(shí)驗(yàn)概述K-means 算法：k-means 算法接受參數(shù)k；然后將事先輸入的n個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)聚類以便使得所獲得的聚類滿足：同一聚類中的對(duì)象相似度較高；而不同聚類中的對(duì)象相似度較小。聚類相似度是利用各聚類中對(duì)象的均值所獲得一個(gè)“中心對(duì)象”（引力中心）來進(jìn)行計(jì)算的。Kmeans 算法具體流程：輸入： k, datan;（ 1） 選擇 k個(gè)初

17、始中心點(diǎn)，例如c0=data0, ck-1=datak-1;（ 2）對(duì)于 data0 .datan,分別與 c0 ck-1比較，假定與ci差值最少，就標(biāo)記為i;（ 3） 對(duì)于所有標(biāo)記為i點(diǎn)，重新計(jì)算ci=所有標(biāo)記為i的 dataj之和 /標(biāo)記為 i的個(gè)數(shù)；（ 4） 重復(fù) (2)(3),直到所有ci值的變化小于給定閾值。實(shí)驗(yàn)結(jié)果10精選文庫隨機(jī)產(chǎn)生的100000 個(gè)數(shù)據(jù)程序運(yùn)行結(jié)果選擇不同的線程數(shù)得到計(jì)算結(jié)果的時(shí)間：線程數(shù)234567計(jì)算時(shí)間0.1476290.0979340.0929820.0991600.1051730.113001實(shí)驗(yàn)代碼1. 隨機(jī)產(chǎn)生 100000 個(gè)數(shù)據(jù)：#includ

18、e<stdio.h>#include<stdlib.h>#include<unistd.h>#define RANGE 200void main()FILE *file;if(file=fopen("cbldata.txt","wt")=NULL)perror("fopen");exit(1);int N=100000;int i=0;11精選文庫for(i=0;i<N;i+)fprintf(file,"%dn",rand();fclose(file);2. Kmeans算

19、法實(shí)現(xiàn)：#include <stdio.h>#include <math.h>#include <stdlib.h>#include "mpi.h"#define TRUE 1#define FALSE 0int N,K;int * AverageIndex;double * Average;double * AverageCopy;double * AllData;double * Cluster;int * ElementNum;int ProcessNum;int MyId;int SourceId;void CreateRando

20、mArray(int n,int k,int * aveindex)int i=0,j=0;srand(unsigned)time(NULL);for(i=0;i<k;i+)int randtheonly=TRUE;while(randtheonly)int a=rand()%n;for(j=0;j<i;j+)if(aveindexj=a)/重復(fù)randtheonly=TRUE;break;if(j=i)/不重復(fù)12精選文庫aveindexi=a;randtheonly=FALSE;void AverageBackup()/聚類均值數(shù)組的備份int i=0;for(i=0;i<

21、;K;i+)AverageCopyi=Averagei;void InitAverage()int i=0;CreateRandomArray(N,K,AverageIndex);/隨機(jī)產(chǎn)生 K 個(gè)均值序列for(i=0;i<K;i+)Averagei=AllDataAverageIndexi;/將對(duì)應(yīng)數(shù)據(jù)賦值給均值數(shù)組AverageBackup();/均值備份void InitData()/數(shù)據(jù)初始化char * FileName="cbldata.txt"FILE * DF;int i=0;N=0;int DataRead;if(DF=fopen(FileName

22、,"r")=NULL)/判斷文件是否為空printf("File not exist!n");exit(0);while(!feof(DF)/統(tǒng)計(jì)數(shù)據(jù)個(gè)數(shù)fscanf(DF,"%d",&DataRead);N=N+1;13精選文庫N-=1;fclose(DF);K=5;if(K>N)printf("K>N is wrong!");exit(0);Average=(double *)malloc(sizeof(double)*K);AverageIndex=(int *)malloc(sizeof

23、(int)*K);AverageCopy=(double *)malloc(sizeof(double)*K);ElementNum=(int *)malloc(sizeof(int)*K);AllData=(double *)malloc(sizeof(double)*N);Cluster=(double *)malloc(sizeof(double)*K);i=0;DF=fopen(FileName,"r");while(!feof(DF)/從文件讀數(shù)據(jù)fscanf(DF,"%d",&DataRead);if(i=N) break;AllDa

24、tai+=DataRead;fclose(DF);for(i=0;i<K;i+)Clusteri=(double *)malloc(sizeof(double)*N);ElementNumi=0;/初始每個(gè)聚類的元素個(gè)數(shù)為 0InitAverage();/K個(gè)聚類的均值初始化int GetIndex(double value,double * ave)int i=0;int index=i;/距離最小的聚類索引double min=fabs(value-avei);/距聚類均值最小距離for(i=0;i<K;i+)/找到距離最小的聚類索引if(fabs(value-avei)<

25、;min)14精選文庫index=i;min=fabs(value-avei);return index;void UpdateAverage()/添加元素后更新聚類均值int i=0,j=0;double sum=0;for(i=0;i<K;i+)/計(jì)算每個(gè)聚類的均值sum=0;for(j=0;j<ElementNumi;j+)/計(jì)算某聚類的元素值和sum+=Clusterij;if(ElementNumi>0)Averagei=sum/ElementNumi;intEqualJudge(double* ave1,double* ave2)/compare比較前后兩次聚類均

26、值是>否相同int i;for(i=0;i<K;i+)if(fabs(ave1i!=ave2i)return FALSE;return TRUE;void Print()int i,j;printf("-n");15精選文庫for(i=0;i<K;i+)printf("第 %d 組：中心值：%f n",i+1,Averagei);/*printf("聚類成員： n");for(j=0;j<ElementNumi;j+)printf("%f ",Clusterij);if(j+1)%8)=0)

27、/display 8 data per lineprintf("n");printf("n");*/int main(int argc,char *argv)int LocalStart;int Flag=1;int TemAveIndex;int * TemArray;int * TemArrayAdd;int i=0;double star,end;MPI_Status Status;MPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&MyId);MPI_Comm_size(

28、MPI_COMM_WORLD,&ProcessNum);star=MPI_Wtime();if(MyId=0)InitData();MPI_Bcast(&N,1,MPI_DOUBLE,0,MPI_COMM_WORLD);MPI_Bcast(&K,1,MPI_DOUBLE,0,MPI_COMM_WORLD);MPI_Bcast(AllData,N,MPI_DOUBLE,0,MPI_COMM_WORLD);TemArrayAdd=(int *)malloc(sizeof(int)*(N-(N%ProcessNum);MPI_Barrier(MPI_COMM_WORLD);e

29、lseMPI_Bcast(&N,1,MPI_DOUBLE,0,MPI_COMM_WORLD);16精選文庫MPI_Bcast(&K,1,MPI_DOUBLE,0,MPI_COMM_WORLD);AllData=(double *)malloc(sizeof(double)*N);Average=(double *)malloc(sizeof(double)*K);MPI_Bcast(AllData,N,MPI_DOUBLE,0,MPI_COMM_WORLD);MPI_Barrier(MPI_COMM_WORLD);TemArray=(int *)malloc(sizeof(int)*(N/ProcessNum);while(Flag)if(MyId=0)MPI_Barrier(MPI_COMM_WORLD);MPI_Bcast(Average,K,MPI_DOUBL