并行编程报告

并并 行行 编编 程程 报报 告告 课程名称 课程名称 并行编程原理并行编程原理 专业班级 专业班级 物联网物联网 11021102 班班 学号学号 U201114483U201114483 学生姓名 学生姓名 陈炳良陈炳良 指导教师 指导教师 金海金海 报告日期 报告日期 2014 6 11 计算机科学与技术学院计算机科学与技术学院 目录目录 实验一 利用实验一 利用 pthreadpthread 并行实现矩阵的乘法运算并行实现矩阵的乘法运算 3 3 实验目的 3 实验概述 3 实验结果 3 实验代码 5 实验总结 9 实验二 使用并行方法优化实验二 使用并行方法优化 K meansK means 算法算法 10 10 实验目的 10 实验概述 10 实验结果 10 实验代码 11 实验总结 18 实验一 利用实验一 利用 pthreadpthread 并行实现矩阵的乘法运算并行实现矩阵的乘法运算 实验目的实验目的 该实验旨在让学生掌握利用 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 1 并行计算矩阵相乘代码 并行计算矩阵相乘代码 include include include include include include 定义矩阵中元素的上限 避免相乘后溢出 define RANGE 150 矩阵 A 有 M 行 N 列 矩阵 B 有 N 行 M 列 define M 200 define N 300 int 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 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 2 串行计算矩阵相乘代码 串行计算矩阵相乘代码 include include include include include include 定义矩阵中元素的上限 避免相乘后溢出 define RANGE 150 矩阵 A 有 M 行 N 列 矩阵 B 有 N 行 M 列 define M 200 define N 300 int 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 实验总结实验总结 由于本次随机矩阵相乘的计算量不是很大 所以最终的比较结果是 串行计算时间要 远远小于并行计算时间 其主要原因是因为并行计算中要创建 销毁线程 这个过程消耗 了大部分时间 与此同时 我对串行编程有了更加深刻的了解 对并行编程也有了初步的 感官 对我日后的优化编程有了很深的启发 实验二 使用并行方法优化实验二 使用并行方法优化 K meansK means 算法算法 实验目的实验目的 该项目要求学生了解并掌握对复杂问题进行并行程序设计和优化的方法 在相关工具 和框架的帮助下 利用数据划分和任务划分方法实现并行算法 并对并行算法进行优化 在了解熟悉 K means 问题的基础上建立合适的数据结构与程序结构 编写程序求解 K means 问题 分析算法的时间与空间复杂度 根据并行算法并行化过程中的问题分解和解 除数据相关的方法 自行选取相关的并行程序开发工具和框架 设计并行化的回溯算法 并用其解决 K means 问题 进而设计和调整解决 BFS 问题并行算法的并行粒度 实现不 同粒度下的并行化算法 对比分析其性能 最后 要求能够在 Linux 环境下使用 C C 语 言编程实现 同时测量算法执行时间 与串行程序进行对比分析 实验概述实验概述 K meansK means 算法 算法 k means 算法接受参数 k 然后将事先输入的 n 个数据对象划分为 k 个聚类以便使 得所获得的聚类满足 同一聚类中的对象相似度较高 而不同聚类中的对象相似度较小 聚类相似度是利用各聚类中对象的均值所获得一个 中心对象 引力中心 来进行计算的 KmeansKmeans 算法具体流程 算法具体流程 输入 k data n 1 选择 k 个初始中心点 例如 c 0 data 0 c k 1 data k 1 2 对于 data 0 data n 分别与 c 0 c k 1 比较 假定与 c i 差值最少 就标记为 i 3 对于所有标记为 i 点 重新计算 c i 所有标记为 i 的 data j 之和 标记为 i 的个数 4 重复 2 3 直到所有 c i 值的变化小于给定阈值 实验结果实验结果 随机产生的 100000 个数据 程序运行结果 选择不同的线程数得到计算结果的时间 线程数 234567 计算时间 0 1476290 0979340 0929820 0991600 1051730 113001 实验代码实验代码 1 1 随机产生随机产生 100000100000 个数据 个数据 include include include define RANGE 200 void main FILE file if file fopen cbldata txt wt NULL perror fopen exit 1 int N 100000 int i 0 for i 0 i N i fprintf file d n rand fclose file 2 2 KmeansKmeans 算法实现 算法实现 include include include include mpi h define TRUE 1 define FALSE 0 int 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 i k i int randtheonly TRUE while randtheonly int a rand n for j 0 j i j if aveindex j a 重复 randtheonly TRUE break if j i 不重复 aveindex i a randtheonly FALSE void AverageBackup 聚类均值数组的备份 int i 0 for i 0 i K i AverageCopy i Average i void InitAverage int i 0 CreateRandomArray N K AverageIndex 随机产生 K 个均值序列 for i 0 iN printf K N 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 if i N break AllData i DataRead fclose DF for i 0 i K i Cluster i double malloc sizeof double N ElementNum i 0 初始每个聚类的元素个数 为 0 InitAverage K 个聚类的均值初始化 int GetIndex double value double ave int i 0 int index i 距离最小的聚类索引 double min fabs value ave i 距聚类均值最小距离 for i 0 i K i 找到距离最小的聚类索 引 if fabs value ave i min index i min fabs value ave i return index void UpdateAverage 添加元素后更新聚类均值 int i 0 j 0 double sum 0 for i 0 i K i 计算每个聚类的均值 sum 0 for j 0 j0 Average i sum ElementNum i int EqualJudge double ave1 double ave2 compare 比较前后两次聚类均值 是 否相同 int i for i 0 i K i if fabs ave1 i ave2 i return FALSE return TRUE void Print int i j printf n for i 0 i K i printf 第 d 组 中心值 f n i 1 Average i printf 聚类成员 n for j 0 j ElementNum i j printf f Cluster i j 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 MPI Comm rank MPI COMM WORLD MPI Comm size MPI COMM WORLD star MPI Wtime if MyId 0 InitData MPI Bcast MPI Bcast 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 MPI Bcast 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 AllData