并行编程报告课程名称：并行编程原理专业班级：物联网1102 班学号 : U*********学生姓名：***指导教师：**报告日期：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<stdio.h>#include<time.h>#include<pthread.h>#include<stdlib.h>#include<unistd.h>#include<memory.h>/*定义矩阵中元素的上限，避免相乘后溢出*/#define RANGE 150/*矩阵A有M行N列，矩阵B有N行M列*/#define M 200#define N 300int matrixA[M][N];int matrixB[N][M];int arr[M][M][N];int res[M][M]={0};void *func(void *arg);void put();void *func(void *arg)//每个子线程要完成的任务{int k=*(int *)arg;int i,j;for(i=0;i<M;i++)for(j=0;j<M;j++)arr[i][j][k]=matrixA[i][k]*matrixB[k][j];pthread_exit(NULL);}main(){//随即产生两个矩阵int i,j,k;srand((unsigned)time(NULL));for(i=0;i<M;i++)for(j=0;j<N;j++)matrixA[i][j] = rand()%RANGE;for(i=0;i<N;i++)for(j=0;j<M;j++)matrixB[i][j] = rand()%RANGE;clock_t start=clock();//开始计时pthread_t tids[N];for(i=0;i<N;i++){if(pthread_create(&tids[i],NULL,func,(void *)&i)) //产生线程，去完成矩阵相乘的部分工作量{perror("pthread_create");exit(1);}}for(i=0;i<N;i++)pthread_join(tids[i],NULL);//等待所有的子线程计算结束for(i=0;i<M;i++) //合。

for(j=0;j<M;j++)for(k=0;k<N;k++)res[i][j]+=arr[i][j][k];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;i<M;i++){for(j=0;j<N;j++)fprintf(file1,"%-8d",matrixA[i][j]); fprintf(file1,"\n");}fclose(file1);for(i=0;i<N;i++){for(j=0;j<M;j++)fprintf(file2,"%-8d",matrixB[i][j]); fprintf(file2,"\n");}fclose(file2);for(i=0;i<M;i++){for(j=0;j<M;j++)fprintf(file3,"%-8d",res[i][j]);fprintf(file3,"\n");}fclose(file3);}2.串行计算矩阵相乘代码：#include<stdio.h>#include<time.h>#include<pthread.h>#include<stdlib.h>#include<unistd.h>#include<memory.h>/*定义矩阵中元素的上限，避免相乘后溢出*/#define RANGE 150/*矩阵A有M行N列，矩阵B有N行M列*/#define M 200#define N 300int matrixA[M][N];int matrixB[N][M];int arr[M][M][N];int res[M][M]={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++)matrixA[i][j] = rand()%RANGE;for(i=0;i<N;i++)for(j=0;j<M;j++)matrixB[i][j] = rand()%RANGE;clock_t start=clock();//开始计时for(i=0;i<M;i++)for(j=0;j<M;j++)for(k=0;k<N;k++)res[i][j]+=matrixA[i][k]*matrixB[k][j]; 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;i<M;i++){for(j=0;j<N;j++)fprintf(file1,"%-8d",matrixA[i][j]);fprintf(file1,"\n");}fclose(file1);for(i=0;i<N;i++){for(j=0;j<M;j++)fprintf(file2,"%-8d",matrixB[i][j]);fprintf(file2,"\n");}fclose(file2);for(i=0;i<M;i++){for(j=0;j<M;j++)fprintf(file3,"%-8d",res[i][j]);fprintf(file3,"\n");}fclose(file3);}实验总结由于本次随机矩阵相乘的计算量不是很大，所以最终的比较结果是，串行计算时间要远远小于并行计算时间，其主要原因是因为并行计算中要创建，销毁线程，这个过程消耗了大部分时间。