并行编程报告

.并 行 编 程 报 告课程名称： 并行编程原理 专业班级： 物联网1102 班 学号 : U201114483 学生姓名： 陈炳良 指导教师： 金海 报告日期： 2014-6-11 计算机科学与技术学院目录实验一：利用 pthread 并行实现矩阵的乘法运算.3实验目的.3实验概述.3实验结果.3实验代码.5实验总结.9实验二：使用并行方法优化 K-means 算法 .10实验目的.10实验概述.10实验结果.10实验代码. .11实验总结. .18实验一：利用 pthread 并行实现矩阵的乘法运算实验目的 该实验旨在让学生掌握利用 pthread 进行并行程序设计和性能优化的基本原理和方法，了解并行程序设计中数据划分和任务划分的基本方法，并能够利用pthread 实现矩阵的乘法运算的并行算法，然后对程序执行结果进行简单分析和总结。具体包括：利用 for 循环编写串行的矩阵乘法运算；熟悉 pthread 进行线程创建、管理和销毁的基本原理和方法；利用 pthread 对上述串行的矩阵乘法运算加以改造；通过调整数据划分和任务划分的粒度(改变工作线程的数目)，测试并行程序的执行效率；对实验结果进行总结和分析。实验概述使用 pThread 完成这项工作。创建一个新的线程：int pthread_create( pthread_t *thread,const pthread_attr_t *attr, void *(*func) (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 列位置上的数为第一个矩阵第 i 行上的 n 个数与第二个矩阵第 j 列上的 n 个数对应相乘后所得的 n 个乘积之和。实验结果实验随机产生的矩阵 B 的数据并行以及串行计算时间对比实验代码1. 并行计算矩阵相乘代码：#include#include#include#include#include#include /*定义矩阵中元素的上限，避免相乘后溢出*/#define RANGE 150/*矩阵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; int i,j; for(i=0;iM;i+) for(j=0;jM;j+) arrijk=matrixAik*matrixBkj; pthread_exit(NULL);main() /随即产生两个矩阵 int i,j,k; srand(unsigned)time(NULL); for(i=0;iM;i+) for(j=0;jN;j+) matrixAij = rand()%RANGE; for(i=0;iN;i+) for(j=0;jM;j+) matrixBij = rand()%RANGE; clock_t start=clock();/开始计时 pthread_t tidsN; for(i=0;iN;i+) if(pthread_create(&tidsi,NULL,func,(void *)&i) /产生线程，去完成矩阵相乘的部分工作量 perror(pthread_create); exit(1); for(i=0;iN;i+) pthread_join(tidsi,NULL);/等待所有的子线程计算结束 for(i=0;iM;i+) /合。 for(j=0;jM;j+) for(k=0;kN;k+) resij+=arrijk; 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); 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;iM;i+) for(j=0;jN;j+) fprintf(file1,%-8d,matrixAij); fprintf(file1,n); fclose(file1); for(i=0;iN;i+) for(j=0;jM;j+) fprintf(file2,%-8d,matrixBij); fprintf(file2,n); fclose(file2); for(i=0;iM;i+) for(j=0;jM;j+) fprintf(file3,%-8d,resij); fprintf(file3,n); fclose(file3);2. 串行计算矩阵相乘代码：#include#include#include#include#include#include /*定义矩阵中元素的上限，避免相乘后溢出*/#define RANGE 150/*矩阵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();main() /随即产生两个矩阵 int i,j,k; srand(unsigned)time(NULL); for(i=0;iM;i+) for(j=0;jN;j+) matrixAij = rand()%RANGE; for(i=0;iN;i+) for(j=0;jM;j+) matrixBij = rand()%RANGE; clock_t start=clock();/开始计时 for(i=0;iM;i+) for(j=0;jM;j+) for(k=0;kN;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); 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;iM;i+) for(j=0;jN;j+) fprintf(file1,%-8d,matrixAij); fprintf(file1,n); fclose(file1); for(i=0;iN;i+) for(j=0;jM;j+) fprintf(file2,%-8d,matrixBij); fprintf(file2,n); fclose(file2); for(i=0;iM;i+) for(j=0;jM;j+) fprintf(file3,%-8d,resij); fprintf(file3,n); fclose(file3);实验总结由于本次随机矩阵相乘的计算量不是很大，所以最终的比较结果是，串行计算时间要远远小于并行计算时间，其主要原因是因为并行计算中要创建，销毁线程，这个过程消耗了大部分时间。与此同时，我对串行编程有了更加深刻的了解，对并行编程也有了初步的感官，对我日后的优化编程有了很深的启发。实验二：使用并行方法优化 K-means 算法实验目的该项目要求学生了解并掌握对复杂问题进行并行程序设计和优化的方法。在相关工具和框架的帮助下，利用数据划分和任务划分方法实现并行算法，并对并行算法进行优化。在了解熟悉 K-means 问题的基础上建立合适的数据结构与程序结构，编写程序求解 K-means 问题，分析算法的时间与空间复杂度。根据并行算法并行化过程中的问题分解和解除数据相关的方法。自行选取相关的并行程序开发工具和框架，设计并行化的回溯算法，并用其解决 K-means 问题，进而设计和调整解决BFS 问题并行算法的并行粒度，实现不同粒度下的并行化算法，对比分析其性能，最后，要求能够在 Linux 环境下使用 C/C+语言编程实现，同时测量算法执行时间，与串行程序进行对比分析。实验概述K-means 算法：k-means 算法接受参数 k ；然后将事先输入的 n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。Kmeans 算法具体流程：输入：k, datan;（1） 选择 k 个初始中心点，例如 c0=data0,ck-1=datak-1;（2）对于 data0.datan, 分别与 c0ck-1比较，假定与 ci差值最少，就标记为 i;（3） 对于所有标记为 i 点，重新计算 ci= 所有标记为 i 的 dataj之和/标记为 i 的个数；（4） 重复(2)(3),直到所有 ci值的变化小于给定阈值。实验结果随机产生的100000个数据程序运行结果选择不同的线程数得到计算结果的时间：线程数234567计算时间0.1476290.0979340.0929820.0991600.1051730.113001实验代码1. 随机产生100000个数据：#include#include#include#define RANGE 200void main() FILE *file; if(file=fopen(cbldata.txt,wt)=NULL) perror(fopen); exit(1); int N=100000; int i=0; for(i=0;iN;i+) fprintf(file,%dn,rand(); fclose(file);2. Kmeans算法实现：#include #include #include #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 CreateRandomArray(int n,int k,int * aveindex) int i=0,j=0; srand(unsigned)time(NULL); for(i=0;ik;i+) int randtheonly=TRUE; while(randtheonly) int a=rand()%n; for(j=0;ji;j+) if(aveindexj=a) /重复 randtheonly=TRUE; break; if(j=i) /不重复 aveindexi=a; randtheonly=FALSE; void AverageBackup() /聚类均值数组的备份 int i=0; for(i=0;iK;i+) AverageCopyi=Averagei; void InitAverage() int i=0; CreateRandomArray(N,K,AverageIndex); /随机产生K个均值序列 for(i=0;iN) printf(KN is wrong!); exit(0); Average=(double *)malloc(sizeof(double)*K); AverageIndex=(int *)malloc(sizeof(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) /从文件读数据 fscanf(DF,%d,&DataRead); if(i=N) break; AllDatai+=DataRead; fclose(DF); for(i=0;iK;i+) Clusteri=(double *)malloc(sizeof(double)*N); ElementNumi=0; /初始每个聚类的元素个数为0 InitAverage(); /K个聚类的均值初始化int GetIndex(double value,double * ave)int i=0; int index=i; /距离最小的聚类索引 double min=fabs(value-avei); /距聚类均值最小距离 for(i=0;iK;i+) /找到距离最小的聚类索引 if(fabs(value-avei)min) index=i; min=fabs(value-avei); return index;void UpdateAverage() /添加元素后更新聚类均值 int i=0,j=0; double sum=0; for(i=0;iK;i+) /计算每个聚类的均值 sum=0; for(j=0;j0) Averagei=sum/ElementNumi; int EqualJudge(double * ave1,double * ave2) /compare比较前后两次聚类均值是否相同 int i; for(i=0;iK;i+) if(fabs(ave1i!=ave2i) return FALSE; return TRUE;void Print() int i,j; printf(-n); for(i=0;iK;i+) printf(第 %d 组：中心值： %f n,i+1,Averagei);/* printf(聚类成员：n); for(j=0;jElementNumi;j+) printf(%f ,Clusterij); if(j+1)%8)=0) /display 8 data per line printf(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_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 MPI_Bcast(&N,1,MPI_DOUBLE,0,MPI_COMM_WORLD); 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_DOUBLE,0,MPI_COMM_WORLD); for(LocalStart=0;LocalStart(N/ProcessNum);LocalStart+) TemAveIndex=GetIndex(AllDataLocalSt