并行编程报告

1、并行编程报告课程名称：并行编程原理专业班级：物联网 1102 班学号 :U201114483学生姓名：陈炳良指导教师：金海报告日期：2014-6-11计算机科学与技术学院精选文库目录实验一：利用pthread 并行实现矩阵的乘法运算3实验目的3实验概述3实验结果3实验代码5实验总结9实验二：使用并行方法优化K-means 算法10实验目的10实验概述10实验结果10实验代码.11实验总结.182精选文库实验一：利用 pthread并行实现矩阵的乘法运算实验目的该实验旨在让学生掌握利用pthread 进行并行程序设计和性能优化的基本原理和方法，了解并行程序设计中数据划分和任务划分的基本方法，并能

2、够利用pthread 实现矩阵的乘法运算的并行算法， 然后对程序执行结果进行简单分析和总结。具体包括： 利用 for循环编写串行的矩阵乘法运算； 熟悉 pthread 进行线程创建、 管理和销毁的基本原理和方法；利用 pthread 对上述串行的矩阵乘法运算加以改造；通过调整数据划分和任务划分的粒度( 改变工作线程的数目 ) ，测试并行程序的执行效率；对实验结果进行总结和分析。实验概述使用 pThread 完成这项工作。创建一个新的线程：int pthread_create( pthread_t *thread,const pthread_attr_t *attr,void *(*func)

3、(void *),void *arg);thread表示线程 ID ，与线程中的pid概念类似attr表示设定线程的属性，可以暂时不用考虑func表示新创建的线程会从这个函数指针处开始运行arg表示这个函数的参数指针返回值为 0 代表成功，其他值为错误编号。主进程等待线程结束：int pthread_join( pthread_t thread, void *retval );thread表示线程 ID ，与线程中的pid概念类似retval用于存储等待线程的返回值两个矩阵相乘：一个 m 行 n 列的矩阵与一个n行 p 列的矩阵可以相乘，得到的结果是一个m 行 p列的矩阵，其中的第 i行第 j

4、列位置上的数为第一个矩阵第i 行上的 n 个数与第二个矩阵第 j 列上的 n个数对应相乘后所得的n 个乘积之和。实验结果3精选文库实验随机产生的矩阵B 的数据4精选文库并行以及串行计算时间对比实验代码1. 并行计算矩阵相乘代码：#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)/每个子线程要完成的任务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()/ 随即产生两个矩阵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();/开始计时pthread_t tidsN;for(i=0;i<N;i+)if(pthread_create(&tidsi,NULL,func,(void*)&i)/产生线程， 去完成矩阵相乘的部分工作量perror("

7、;pthread_create");exit(1);for(i=0;i<N;i+)pthread_join(tidsi,NULL);/等待所有的子线程计算结束for(i=0;i<M;i+) /合。for(j=0;j<M;j+)for(k=0;k<N;k+)resij+=arrijk;clock_t finish=clock();/结束计算printf("并行计算用时%.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. 串行计算矩阵相乘代码：#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()/ 随即产生两个矩阵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();/开始计时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();/结束计算printf("串行计算用时%.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);实验总结由于本次随机矩阵相乘的计算量不是很大， 所以最终的比较结果是， 串行计算时间要远远小于并行计算时间， 其主要原因是因为并

15、行计算中要创建， 销毁线程， 这个过程消耗了大部分时间。与此同时，我对串行编程有了更加深刻的了解，对并行编程也有了初步的感官，对我日后的优化编程有了很深的启发。9精选文库实验二：使用并行方法优化K-means 算法实验目的该项目要求学生了解并掌握对复杂问题进行并行程序设计和优化的方法。在相关工具和框架的帮助下， 利用数据划分和任务划分方法实现并行算法，并对并行算法进行优化。在了解熟悉 K-means问题的基础上建立合适的数据结构与程序结构，编写程序求解K-means问题，分析算法的时间与空间复杂度。 根据并行算法并行化过程中的问题分解和解除数据相关的方法。自行选取相关的并行程序开发工具和框架，

16、设计并行化的回溯算法，并用其解决K-means 问题，进而设计和调整解决BFS 问题并行算法的并行粒度，实现不同粒度下的并行化算法，对比分析其性能，最后，要求能够在Linux环境下使用C/C+ 语言编程实现，同时测量算法执行时间，与串行程序进行对比分析。实验概述K-means 算法：k-means 算法接受参数k；然后将事先输入的n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。Kmeans 算法具体流程：输入： k, datan;（ 1） 选择 k个初

17、始中心点，例如c0=data0,ck-1=datak-1;（ 2）对于 data0.datan,分别与 c0ck-1比较，假定与ci差值最少，就标记为i;（ 3） 对于所有标记为i点，重新计算ci=所有标记为i的 dataj之和 /标记为 i的个数；（ 4） 重复 (2)(3),直到所有ci值的变化小于给定阈值。实验结果10精选文库随机产生的100000 个数据程序运行结果选择不同的线程数得到计算结果的时间：线程数234567计算时间0.1476290.0979340.0929820.0991600.1051730.113001实验代码1. 随机产生 100000 个数据：#include&l

18、t;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、：#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 CreateRandomAr

20、ray(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)/重复randtheonly=TRUE;break;if(j=i)/不重复12精选文库aveindexi=a;randtheonly=FALSE;void AverageBackup()/聚类均值数组的备份int i=0;for(i=0;i<K;

21、i+)AverageCopyi=Averagei;void InitAverage()int i=0;CreateRandomArray(N,K,AverageIndex);/随机产生 K 个均值序列for(i=0;i<K;i+)Averagei=AllDataAverageIndexi;/将对应数据赋值给均值数组AverageBackup();/均值备份void InitData()/数据初始化char * FileName="cbldata.txt"FILE * DF;int i=0;N=0;int DataRead;if(DF=fopen(FileName,&q

22、uot;r")=NULL)/判断文件是否为空printf("File not exist!n");exit(0);while(!feof(DF)/统计数据个数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(in

23、t)*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)/从文件读数据fscanf(DF,"%d",&DataRead);if(i=N) break;AllDatai

24、+=DataRead;fclose(DF);for(i=0;i<K;i+)Clusteri=(double *)malloc(sizeof(double)*N);ElementNumi=0;/初始每个聚类的元素个数为 0InitAverage();/K个聚类的均值初始化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)<mi

25、n)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+)/计算每个聚类的均值sum=0;for(j=0;j<ElementNumi;j+)/计算某聚类的元素值和sum+=Clusterij;if(ElementNumi>0)Averagei=sum/ElementNumi;intEqualJudge(double* ave1,double* ave2)/compare比较前后两次聚类均值是&

26、gt;否相同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)/di

27、splay 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(MPI

28、_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);else

29、MPI_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