南开大学现代远程教育学院考试卷
2020年度春季学期期末(2020.9） 《并行程序设计》
主讲教师： 王刚
学习中心：____________________________ 专业：_______________________ 姓 名：_________________ 学 号：_______________ 成绩：___________
一 、请同学们在下列题目中任选一题，写成期末论文。 （一）并行算法研究类
对某一问题，研究其并行算法的设计、实现，分析其性能，进行实验验证，撰写研究论文。例如：
1、对矩阵相乘问题，设计pthread多线程结合SSE/AVX的两层并行算法，实现并行程序。讨论算法层面不同策略对性能的影响，例如多个线程间不同的任务分配方式、不同的线程同步策略等，讨论不同并行编程方法对性能的影响，例如SSE/AVX的对齐和不对齐内存访问等等。对不同的矩阵规模、不同的线程数测试程序性能，撰写研究论文。
2、对高斯消去法问题（其串行算法伪代码示意如下面算法1所示），设计pthread多线程结合SSE/AVX的两层并行算法，实现并行程序。讨论算法层面不同策略对性能的影响，例如多个线程间不同的任务分配方式、不同的线程同步策略等，讨论不同并行编程方法对性能的影响，例如SSE/AVX的对齐和不对齐内存访问等等。对不同的矩阵规模、不同的线程数测试程序性能，撰写研究论文。 3、其他类似难度的问题。
（二）并行编程工具调研类
对某种并行编程工具进行调研，选取某个问题（例如矩阵相乘问题），用这种编程工具编写并行程序求解这个问题，进行实验验证，撰写研究论文介绍这种并行编程工具的特色、基本编程（使用）方法、如何用它解决实际问题（以你选定的问题为例）。例如：
1、C++、Java等语言本身对并行编程提供的支持。 2、Hadoop MapReduce编程工具。 3、其它并行编程工具。
二、论文写作要求 （一）并行算法研究类
1、论文应详细描述清楚所研究的问题，并行算法的设计。
2、鼓励大家选择课堂教学之外的问题，通过文献调研，研究其并行求解方法，甚至有自己提出新的方法。
3、最好能有求解一个问题的多种并行算法之间的对比分析。
（二）并行编程工具调研类
1、应调研较新的工具，避免调研太“古老”的工具。
2、不能只是工具相关资料的调研和文字的汇总、整理，重点仍是并行编程——用调研的工具编程解决一个具体问题。
3、鼓励大家进行不同并行编程工具间的对比，例如调研的工具与课堂讲授的工具之间的对比。
三、论文写作格式要求：
论文题目要求为宋体三号字，加粗居中；
正文部分要求为宋体小四号字，标题加粗，行间距为1.5倍行距；
应符合科技论文写作规范，题目、摘要、关键字、章节、参考文献等等完整、正确。这方面可参考附件范文。 四、论文提交注意事项：
1、论文一律以此文件为封面，写明学习中心、专业、姓名、学号等信息。论文保存为word文件，以“课程名+学号+姓名”命名。
2、论文一律采用线上提交方式，在学院规定时间内上传到教学教务平台，逾期平台关闭，将不接受补交。
3、不接受纸质论文。
4、与论文一同打包提交源程序，注意，是提交.cpp、.h等源程序，不要将工程文件、编译后的目标文件等打包提交。
5、如有抄袭雷同现象，将按学院规定严肃处理。
矩阵乘法的并行化的设计与实现
摘要：矩阵乘法是最基本的矩阵运算之一,由于其计算密集的特点,适合于在FPGA上实现。本文给定两个n阶矩阵A与B，矩阵乘法是指计算C=A×B ，现在对两个矩阵乘法进行串行和并行的实验和分析。
关键词：矩阵乘法；并行算法；实验；
一、算法原理:
1、串行算法
通常的O(n3)矩阵乘矩阵的串行计算过程如算法1所示，此外为计算矩阵相乘，还可以有对3层循环采用其他嵌套形式的串行算法。
算法1: 稠密矩阵相乘的i,j,k形式串行算法
2、并行算法
两个矩阵相乘的行列划分并行算法假设一共有P个进程，将矩阵A按行分成P个块，将矩阵B按列分成P个块：
每块包含连续若干个行．为使得负载平衡，应使得每块中的行数尽量相等．将Ak与Bk分别存储在进程Pk的A’与B’中．将C分为P×P块，且将Ci,j存储在的p’i中，如算法2
算法2 稠密矩阵乘C=A×B的行列划分并行算法
实验由MPICH2在VS2010上进行并行环境的配置来完成，单机情况下用进程数的个数模拟多处理器。
在实验中算法由以下几个函数实现：
void readData();此函数被rankID为0的进程调用，负责从dataIn.txt文件中A[M,K],B[P,N]两个相乘矩阵的数据，并为结果矩阵C[M,N]分配空间。其中C[N,N]=A[M,K]*B[P,N]。
int gcd(int M,int N,int group_size) 此函数用来返回两个整数的不大于group_size的最大公因子，即算法所用到的处理器个数，为了保证行划分和列划分可以平均的划分，通过求M，N不大于group_size的最大公因子来确定实际用到的处理器p。
void printResult();此函数被rankID为0的进程调用，用来将A,B,C矩阵打印输出给用户，并输出用于分发数据和并行计算的时间。
int main(int argc, char **argv) ;程序的主函数。
算法分析（可扩展性分析）：
在LogP模型上，算法2并行执行时间为：
由此可知，并行效率为：
因此，等效率函数为：
3、算法的MPI程序:
// matrix.cpp : 定义控制台应用程序的入口点。 //
#include \#include \#include \#include \#include
#define intsize sizeof(int) #define floatsize sizeof(float) #define charsize sizeof(char) #define A(x,y) A[x*K+y] #define B(x,y) B[x*N+y] #define C(x,y) C[x*N+y] #define a(x,y) a[x*K+y] #define b(x,y) b[x*n+y]
#define buffer(x,y) buffer[x*n+y] /* 此宏用来简化对标号为奇数的处理器内的缓冲空间的访问 */
#define c(l,x,y) c[x*N+y+l*n]
float *a,*b,*c,*buffer; int s;
float *A,*B,*C; /* A[M,K],B[P,N].正确的情况下K应该等于P,否则无法进行矩阵相乘 */ int M,N,K,P ; int m,n; int myid; int p; /* 保存工作站集群中处理器数目，也即通信子大小 */
FILE *dataFile; /* 用于读取输入文件内容和将计算结果输出到结果文件的临时文件指针 */ MPI_Status status; double time1;
double starttime,endtime; /*
* 函数名: readData
* 功能： 此函数被rankID为0的进程调用，负责从dataIn.txt文件中读入 * A[M,K],B[P,N]两个相乘矩阵的数据，并为结果矩阵C[M,N]分配空间。
* 其中C[N,N]=A[M,K]*B[P,N]
并行程序设计-王刚(2002) 矩阵乘法的并行化的设计与实现
