南开大学并行程序设计2019.doc

装订处

一、请同学们在下列题目中任选一题，写成期末论文。

（一）并行算法研究类

对某一问题，研究其并行算法的设计、实现，分析其性能，进行实验验证，撰写研究论文。例如：

1、对矩阵相乘问题，设计pthread多线程结合SSE/AVX的两层并行算法，实现并行程序。讨论算法层面不同策略对性能的影响，例如多个线程间不同的任务分配方式、不同的线程同步策略等，讨论不同并行编程方法对性能的影响，例如SSE/AVX的对齐和不对齐内存访问等等。对不同的矩阵规模、不同的线程数测试程序性能，撰写研究论文。

2、对高斯消去法问题（其串行算法伪代码示意如下面算法1所示），设计pthread多线程结合SSE/AVX的两层并行算法，实现并行程序。讨论算法层面不同策略对性能的影响，例如多个线程间不同的任务分配方式、不同的线程同步策略等，讨论不同并行编程方法对性能的影响，例如SSE/AVX的对齐和不对齐内存访问等等。对不同的矩阵规模、不同的线程数测试程序性能，撰写研究论文。

3、其他类似难度的问题。

（二）并行编程工具调研类

对某种并行编程工具进行调研，选取某个问题（例如矩阵相乘问题），用这种编程工具编写并行程序求解这个问题，进行实验验证，撰写研究论文介绍这种并行编程工具的特色、基本编程（使用）方法、如何用它解决实际问题（以你选定的问题为例）。例如：

1、C++、Java等语言本身对并行编程提供的支持。

2、HadoopMapReduce编程工具。

3、其它并行编程工具。

二、论文写作要求

（一）并行算法研究类

1、论文应详细描述清楚所研究的问题，并行算法的设计。

2、鼓励大家选择课堂教学之外的问题，通过文献调研，研究其并行求解方法，甚至有自己提出新的方法。

3、最好能有求解一个问题的多种并行算法之间的对比分析。

（二）并行编程工具调研类

1、应调研较新的工具，避免调研太“古老”的工具。

2、不能只是工具相关资料的调研和文字的汇总、整理，重点仍是并行编程——用调研的工具编程解决一个具体问题。

3、鼓励大家进行不同并行编程工具间的对比，例如调研的工具与课堂讲授的工具之间的对比。

三、论文写作格式要求：

论文题目要求为宋体三号字，加粗居中；

正文部分要求为宋体小四号字，标题加粗，行间距为1.5倍行距；

应符合科技论文写作规范，题目、摘要、关键字、章节、参考文献等等完整、正确。这方面可参考附件范文。

四、论文提交注意事项：

1、论文一律以此文件为封面，写明学习中心、专业、姓名、学号等信息。论文保存为word文件，以“课程名+学号+姓名”命名。

2、论文一律采用线上提交方式，在学院规定时间内上传到教学教务平台，逾期平台关闭，将不接受补交。

3、不接受纸质论文。

4、与论文一同打包提交源程序，注意，是提交.cpp、.h等源程序，不要将工程文件、编译后的目标文件等打包提交。

5、如有抄袭雷同现象，将按学院规定严肃处理。

矩阵相乘并行化处理

摘要：矩阵相乘是一个比较复杂的计算。本次实验分别使用串行算法、Cache优化算法、SSE编程和分片策略算法实现了矩阵乘法运算，实验采用同一个样本，即矩阵大小为512个元素，元素值为由时间生成的随机数，每个算法对此样本运行十次，并记录每次运行时间和十次运算的平均运行时间。通过不同算法结果来讨论不同并行编程方法对性能的影响。

关键词：矩阵相乘；并行化；SSE编程；分片策略；串行算法

一、引言

矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数（column）和第二个矩阵的行数（row）相同时才有意义。一般单指矩阵乘积时，指的便是一般矩阵乘积。一个m×n的矩阵就是m×n个数排成m行n列的一个数阵。由于它把许多数据紧凑的集中到了一起，所以有时候可以简便地表示一些复杂的模型，如电力系统网络模型。本文通过实验分别使用串行算法、Cache优化算法、SSE编程和分片策略算法实现了矩阵乘法运算，实验采用同一个样本，即矩阵大小为512个元素，元素值为由时间生成的随机数，每个算法对此样本运行十次，并记录每次运行时间和十次运算的平均运行时间。通过不同算法结果来讨论不同并行编程方法对性能的影响。

二、试验环境

属性

操作系统

macOSHighSierra10.13.5

物理内核数

2个

编程语言

C/C++

内存大小

8GB

编译器

VSCODE

三、矩阵相乘并行化分析

1数据初始化

在矩阵样本设计方面，考虑大越大规模的数据越能体现不同算法在运行上的差距，因而将矩阵大小设置为512个元素，并且为了减少元素数据对实验的影响，采取了随机数赋值的方法。代码如下：

srand((unsigned)time(NULL));

floata[maxN][maxN];

floatb[maxN][maxN];

for(int