并行处理与体系结构实验指导书.doc

并行处理与体系结构实验指导书 Guide Book of Parallel Processing and Architecture Experiment 编 者 王璿 教 务 处 2015 年 10 月 目 录 实验一实验一 MPIMPI 安装与程序编译 运行和调试安装与程序编译 运行和调试 1 实验二实验二 共享存储模型与消息传递模型的比较共享存储模型与消息传递模型的比较 3 实验三实验三 矩阵运算矩阵运算 5 实验四实验四 八皇后问题八皇后问题 10 实验五实验五 快速排序快速排序 12 实验六实验六 快速傅氏变换快速傅氏变换 14 1 实验一实验一 MPIMPI 安装与程序编译 运行和调试安装与程序编译 运行和调试 一 实验目的 搭建 MPI 并行编程环境 开发并行程序 学习并行程序的编写 编译 运行步骤 了解系统结 构对编程模式和环境工具的影响 二 实验内容 在计算机局域网上安装 MPICH2 虚拟机 用一个简单的计算实例进行测试 运行 实验代码 MPI 运行程序 文件夹下面的 hello c who c message c isend c 和 mtpi c 程序实例 体会 MPI 中获取进程标识 消息传递及非阻塞通信等工作模式 三 实验步骤 推荐的 MPI 使用环境是 Linux 但实际应用中 Windows 系统应用广泛 本实验主要给出 Windows 下 MPI 环境的搭建方法及 MPI 程序的编写 编译连接及运行 大致步骤及说明如下 1 创建用户创建用户 以管理员的身份登录主机 在主机上建立一个 MPI 账户 如 用户名 mympi 密码 mympi 若在局域网环境下所有主机均推荐创建相同的 MPI 账户 且创建相同的工作目录 如 D mpijob 将并行编译成功的可执行文件均存放在同一目录下 2 安装安装 MPICH 例如 本实验采用的 mpich2 1 4 1p1 win ia32 安装程序的下载地址为 http www mcs anl gov research projects mpich2 downloads tarballs 1 4 1p1 mpich2 1 4 1p1 win ia32 msi 推荐局域网中准备 进行并行计算的所有计算机都要安装 MPICH2 虚拟机 且要安装在相同的路径下 本实验以设置安 装在 C Program Files MPICH2 目录下为例 1 运行 mpich2 目录下的 mpich2 1 4 1p1 win ia32 msi 将 MPICH2 虚拟机安装到计算机上 2 测试 MPI 是否安装成功前首先需要注册一个用户 具体操作如下 开始 按钮 所有程 序 MPICH2 wmpiregister exe 输入用户名 密码 即我们第一步建立的系统管理员账户和系 统登录密码 如图 1 1 所示 图 1 1 MPICH 用户注册界面 3 用例程测试 选择开始 所有程序 MPICH2 wmpiexec exe 选择 Application 为 c program files mpich2 examples cpi exe 就是自带的一个计算圆周率的例子程序 可在 Number of processes 的数量选择 2 表示用二个进程来协同完成 选中 run in separate window 选项 再点击 Excute 执行 如图 1 2 所示 2 图 1 2 测试例程 cpi exe 然后在控制台窗口下提示输入 number of intervals 随便输入个大点的数字 50000 5000000 就可以看到求的的圆周率值 如图 1 3 所示 图 1 3 cpi exe 执行结果显示 3 在 VC6 0 中配置 MPI 1 新建 Win32 Console Application 工程 2 先在 VC6 0 中加入 mpi 的 include VC6 0 程序菜单中 工具 选择 目录 然后 添加 如图 1 4 所示 加入 lib 方法相同 图 1 4 在 VC6 0 中添加 MPI 的 include 3 在所在工程 设置 link 中 加入 mpi lib cxx lib 4 加入讲过的 helloworld 程序 测试运行结果 注 这里以 windows 下 MPI VC 实现为例进行的说明 同学可以根据自己的操作系统或开发 语言自行选择版本下载安装 3 实验二实验二 共享存储模型与消息传递模型的比较共享存储模型与消息传递模型的比较 一 实验目的 比较共享存储模型与消息传递模型之间的区别 了解多线程并行和消息传递并行的工作机制 二 实验内容 1 统计 10000 个随机数中 3 出现的次数 OPENMP 线程数可为 1 2 4 等 MPI 程序进程 数可为 1 2 4 等 2 比较相同线程 进程数下 采用 OPENMP 和 MPI 实现 N BODY 问题的性能 如 OPENMP 线程数可为 1 2 4 等 MPI 程序进程数可为 1 2 4 等 三 实验步骤 1 共享存储模型中 用 openMP 写一个程序 实现在一个长度为 10 000 的随机 array 里面 计算出 3 出现的次数 线程数为 1 2 或者 4 等 openMP 可以拆分循环 比如 2 个线程 第一个 线程负责 array 1 5000 第二个线程负责 5001 10000 各循环 5000 次 这样两个线程可以同时遍 历数组的两部分进行搜索计数 4 个线程也类似 拆分成 4 部分同时进行 OPENMP 在 VS2005 以上支持 其他版本可查阅文献进行适当配置即可使用 消息传递编程模型循环拆分的思量类似 比如 2 个进程 第一个进程负责 array 1 5000 第二 个线程负责 5001 10000 各循环 5000 次 这样两个线程可以同时遍历数组的两部分进行搜索计数 4 个线程也类似 拆分成 4 部分同时进行 最后结果可以返回 0 号进程 源代码清单 1 共享存储模型 计算随机数中 3 的个数 参考程序如下 可根据自己掌握的多线程知识自己编 写新的 OPM 程序 include include include define N 10000 int main int argc char argv int i int array N int count nthreads tid chunk unsigned num chunk 100 count 0 double start end printf please choose number of threads 1 2 or 4 n scanf d 提示输入计算线程数 omp set num threads num pragma omp parallel shared nthreads tid omp get thread num if tid 0 4 nthreads omp get num threads printf nStarting count with d threads n nthreads start omp get wtime pragma omp parallel for reduction count schedule static chunk for i 0 ik then Leftmoveonestep a end if a 循环左移至同行相邻处理器中 if j k then Upmoveonestep b end if b 循环上移至同列相邻处理器中 end for 8 3 for i 0 to m 1 do for j 0 to m 1 do c i j 0 end for end for 4 for k 0 to 1 do p for i 0 to m 1 do for j 0 to m 1 do for k1 0 to m 1 do c i j c i j a i k1 b k1 j end for end for end for Leftmoveonestep a 子块 a 循环左移至同行相邻的处理器中 Upmoveonestep b 子块 b 循环上移至同列相邻的处理器中 end for End b B阵起始对准 a A阵起始对准 0 0 1 0 2 0 3 0 0 1 1 1 2 1 3 1 0 2 1 2 2 2 3 2 0 3 1 3 2 3 3 3 0 0 1 0 2 0 3 0 0 1 1 1 2 1 3 1 0 2 1 2 2 2 3 2 0 3 1 3 2 3 3 3 AAAABBBB AAAABBBB AAAABBBB AAAABBBB 0 1 A 0 0 A 0 3 A 0 2 A 1 2 A 1 1 A 1 0 A 1 3 A 2 3 A 2 2 A 2 1 A 2 0 A 3 0 A 3 3 A 3 2 A 3 1 A 0 0 B 1 0 B 2 0 B 3 0 B 0 1 B 1 1 B 2 1 B 3 1 B 0 2 B 1 2 B 2 2 B 3 2 B 0 3 B 1 3 B 2 3 B 3 3 B 0 2 A 0 1 A 0 0 A 0 3 A 1 3 A 1 2 A 1 1 A 1 0 A 2 0 A 2 3 A 2 2 A 2 1 A 3 1 A 3 0 A 3 3 A 3 2 A 1 0 B 2 0 B 3 0 B 0 0 B 1 1 B 2 1 B 3 1 B 0 1 B 1 2 B 2 2 B 3 2 B 0 2 B 1 3 B 2 3 B 3 3 B 0 3 B d 第一次移位后的子阵位置 c 对准后的A和B 0 3 A 0 2 A 0 1 A 0 0 A 1 0 A 1 3 A 1 2 A 1 1 A 2 1 A 2 0 A 2 3 A 2 2 A 3 2 A 3 1 A 3 0 A 3 3 A 2 0 B 3 0 B 0 0 B 1 0 B 2 1 B 3 1 B 0 1 B 1 1 B 2 2 B 3 2 B 0 2 B 1 2 B 2 3 B 3 3 B 0 3 B 1 3 B e 第二次移位后的子阵位置 0 3 A 1 0 A 2 1 A 3 2 A f 第三次移位后的子阵位置 0 0 B 1 0 B 2 0 B 3 0 B 0 1 A 0 0 A 0 2 A 1 2 A 1 1 A 1 3 A 2 3 A 2 2 A 2 0 A 3 0 A 3 3 A 3 1 A 0 1 B 1 1 B 2 1 B 3 1 B 0 2 B 1 2 B 2 2 B 3 2 B 0 3 B 1 3 B 2 3 B 3 3 B 9 图图 3 2 16 个处理器上的个处理器上的 Cannon 乘法过程乘法过程 这里函数 Leftmoveonestep a 表示子块 a 在编号处于同行的处理器之间以循环左移的方式移至 相邻的处理器中 函数 Upmoveonestep b 表示子块 b 在编号处于同列的处理器之间以循环上移的方 式移至相邻的处理器中 这里我们以函数 Leftmoveonestep a 为例 给出处理器间交换数据的过程 算法算法 3 4 函数函数 Leftmoveonestep a 的基本算法的基本算法 Begin 1 if j 0 then 最左端的子块 1 1 将所存的 A 的子块发送到同行最右端子块所在的处理器中 1 2 接收其右邻处理器中发来的 A 的子块 end if 2 if j sqrt p 1 and j mod 2 0 then 最右端子块处理器且块列号为偶数 2 1 将所存的 A 的子块发送到其左邻处理器中 2 2 接收其同行最左端子块所在的处理器发来的 A 的子块 end if 3 if j sqrt p 1 and j mod 2 0 then 最右端子块处理器且块列号为奇数 3 1 将所存的 A 的子块在缓冲区 buffer 中做备份 3 2 接收其同行最左端子块所在的处理器发来的 A 的子块 3 3 将在缓冲区 buffer 中所存的 A 的子块发送到其左邻处理器中 end if 4 if j sqrt p 1 and j mod 2 0 and j 0 then 其余的偶数号处理器 4 1 将所存的 A 的子块发送到其左邻处理器中 4 2 接收其右邻处理器中发来的 A 的子块 end if 5 if j sqrt p 1 and j mod 2 1 and j 0 then 其余的奇数号处理器 5 1 将所存的 A 的子块在缓冲区 buffer 中做备份 5 2 接收其右邻处理器中发来的 A 的子块 5 3 将在缓冲区 buffer 中所存的 A 的子块发送到其左邻处理器中 end if End 当算法执行在的二维网孔上时 若使用切通 CT 选路法 算法 18 7 第 2 步的循环移位时pp 间为 第 4 步的单步移位时间为 运算时间为 所以在二维p p n tt ws 2 2 p p n tt ws 2 2 pn 3 网孔上 Cannon 乘法的并行运行时间为 pnp p n ttT wsp 4 3 2 简单划分的矩阵相乘源代码和 Cannon 相乘源代码见附件 10 实验四实验四 八皇后问题八皇后问题 一 实验目的 1 八皇后问题是计算机中经典智能搜索问题 掌握在 MPI 虚拟机上进行八皇后问题求解算法 及其程序设计 运行 2 在分析八皇后的并行算法和 MPI 源程序基础上 查找相关参考资料 对于一般的 n 皇后问 题 设计其并行算法及其程序 并运行结果 二 实验内容 在单机或多机上完成 8 12 16 32 等 n 皇后问题求解 并比较运行时间 计算加速比 三 实验步骤 1 了解八皇后问题及其串行算法 所谓八皇后问题 Eight Queens Problem 是在 8 8 格的棋盘上 放置 8 个皇后 要求每行每 列放一个皇后 而且每一条对角线和每一条反对角线上最多只能有一个皇后 即对同时放置在棋盘 的任意两个皇后和 不允许或者的情况出现 11 ij 22 ij 1212 iijj 1122 ijij 八皇后问题的串行解法为如下的递归算法 算法算法 4 1 八皇后问题的串行递归算法八皇后问题的串行递归算法 从 chessboard 的第 row 行开始放置皇后 procedure PlaceQueens chessboard row Begin if row 8 then OutputResult chessboard 结束递归并输出结果 else for col 1 to 8 do 判断是否有列 对角线或反对角线冲突 1 no collision true 2 i 1 3 while no collision and i 0 do 2 1 从某个从进程 i 接收信号 signal 2 2 if signal Accomplished then 从从进程 i 接收并记录解 end if 2 3 if has more boards then 向从进程 i 发送 NewTask 信号 向从进程 i 发送一个新棋盘 else 向从进程 i 发送 Terminate 信号 active slaves active slaves 1 end if end while End EightQueensMaster 2 从进程算法 procedure EightQueenSlave Begin 1 向主进程发送 Ready 信号 2 finished false 3 while not finished do 3 1 从主进程接收信号 signal 3 2 if signal NewTask then 从主进程接收新棋盘 if 新棋盘合法 then 在新棋盘的基础上找出所有合法的解 并将解发送给主进程 end if else signal Terminate finished true end if end while End EightQueenSlave 八皇后问题源代码见附件 12 实验五实验五 快速排序快速排序 一 实验目的 快速排序是计算机中常用的 典型非数值算法 熟悉并掌握在 MPI 虚拟机上进行快速排序的算 法及其程序设计 运行 二 实验内容 在单机或多机上完成快速排序 并比较运行时间 计算加速比 并与枚举排序对比分析结果 三 实验步骤 1 了解快速排序及其串行算法 了解快速排序及其串行算法 快速排序 Quick Sort 是一种最基本的排序算法 它的基本思想是 在当前无序区 R 1 n 中取一个记录作为比较的 基准 一般取第一个 最后一个或中间位置的元素 用此基准将当前 的无序区 R 1 n 划分成左右两个无序的子区 R 1 i 1 和 R i n 1 i n 且左边的无序子区 中记录的所有关键字均小于等于基准的关键字 右边的无序子区中记录的所有关键字均大于等于基 准的关键字 当 R 1 i 1 和 R i n 非空时 分别对它们重复上述的划分过程 直到所有的无序 子区中的记录均排好序为止 算法算法 5 1 单处理机上快速排序算法单处理机上快速排序算法 输入 输入 无序数组 data 1 n 输出 输出 有序数组 data 1 n Begin call procedure quicksort data 1 n End procedure quicksort data i j Begin 1 if i j then 1 1 r partition data i j 1 2 quicksort data i r 1 1 3 quicksort data r 1 j end if End procedure partition data k l Begin 1 pivo data l 2 i k 1 3 for j k to l 1 do if data j pivo then i i 1 exchange data i and data j end if end for 4 exchange data i 1 and data l 5 return i 1 End 13 快速排序算法的性能主要决定于输入数组的划分是否均衡 而这与基准元素的选择密切相关 在最坏的情况下 划分的结果是一边有 n 1 个元素 而另一边有 0 个元素 除去被选中的基准元素 如果每次递归排序中的划分都产生这种极度的不平衡 那么整个算法的复杂度将是 n2 在 最好的情况下 每次划分都使得输入数组平均分为两半 那么算法的复杂度为 O nlogn 在一般 的情况下该算法仍能保持 O nlogn 的复杂度 只不过其具有更高的常数因子 2 快速排序的并行算法 快速排序的并行算法 快速排序算法并行化的一个简单思想是 对每次划分过后所得到的两个序列分别使用两个处理 器完成递归排序 例如对一个长为 n 的序列 首先划分得到两个长为 n 2 的序列 将其交给两个处 理器分别处理 而后进一步划分得到四个长为 n 4 的序列 再分别交给四个处理器处理 如此递归 下去最终得到排序好的序列 当然这里举的是理想的划分情况 如果划分步骤不能达到平均分配的 目的 那么排序的效率会相对较差 算法 13 4 中描述了使用 2m个处理器完成对 n 个输入数据排序 的并行算法 算法算法 5 2 快速排序并行算法快速排序并行算法 输入 输入 无序数组 data 1 n 使用的处理器个数 2m 输出 输出 有序数组 data 1 n Begin para quicksort data 1 n m 0 End procedure para quicksort data i j m id Begin 1 if j i k or m 0 then 1 1 Pid call quicksort data i j else 1 2 Pid r patrition data i j 1 3 P id send data r 1 m 1 to Pid 2m 1 1 4 para quicksort data i r 1 m 1 id 1 5 para quicksort data r 1 j m 1 id 2m 1 1 6 Pid 2m 1 send data r 1 m 1 back to Pid end if End 在最优的情况下该并行算法形成一个高度为 logn 的排序树 其计算复杂度为 O n 通信复 杂度也为 O n 同串行算法一样 在最坏情况下其计算复杂度降为 O n2 正常情况下该算法 的计算复杂度也为 O n 只不过具有更高的常数因子 快速排序问题源代码见附件 14 实验六实验六 快速傅氏变换快速傅氏变换 一 实验目的 长期以来 快速傅氏变换 Fast Fourier Transform FFT 和离散小波变换 Discrete Wavelet Transform DWT 在数字信号处理 石油勘探 地震预报 医学断层诊断 编码理论 量子物理及 概率论等领域中都得到了广泛的应用 各种 FFT 和 DWT 算法不断出现 成为数值代数方面最活跃 的一个研究领域 而其意义远远超过了算法研究的范围 进而为诸多科技领域的研究打开了一个崭 新的局面 掌握在 MPI 虚拟机上进行快速傅氏变换求解算法及其程序设计 运行 二 实验内容 在单机或多机上完成快速傅氏变换问题求解 并比较运行时间 计算加速比 三 实验步骤 1 了解快速傅里叶变换 了解快速傅里叶变换 FFT 离散傅里叶变换是 20 世纪 60 年代是计算复杂性研究的主要里程碑之一 1965 年 Cooley 和 Tukey 所研究的计算离散傅里叶变换 Discrete Fourier Test 的快速傅氏变换 FFT 将计算量从 n2 下 降至 nlogn 推进了 FFT 更深层 更广法的研究与应用 FFT 算法有很多版本 但大体上可分为 两类 迭代法和递归法 本实验采用迭代法 假定 a 0 a 1 a n 1 为一个有限长的输入序列 b 0 b 1 b n 1 为离散傅里叶变换的结 果序列 则有 其中 W 实际上 上式可写成矩阵 W 和向 1 2 1 0 1 0 nkWkakb n m km n n i n e 2 量 a 的乘积形式 公式 6 1 1 2 1 0 1 1 1 2 1 0 1 2420 1210 0000 1 2 1 0 n nnnn n n n a a a a wwww wwww wwww wwww b b b b 一般的 n 阶矩阵和 n 维向量相乘 计算时间复杂度为 n2 但由于 W 是一种特殊矩阵 故可以 降低计算量 FFT 的计算流图如图 6 1 所示 其串行算法如下 算法算法 6 1 单处理器上的单处理器上的 FFT 迭代算法迭代算法 输入 输入 a a0 a1 an 1 输出 输出 b b0 b1 bn 1 Begin 1 for k 0 to n 1 do ck ak end for 2 for h logn 1 downto 0 do 2 1 p 2h 2 2 q n p 2 3 z wq 2 2 4 for k 0 to n 1 do if k mod p k mod2p then i ck ck ck p ii ck p ck ck p z k modp ck不用 i 计算的新值 end if 15 end for end for 3 for k 1 to n 1 do br k ck r k 为 k 的位反 end for End a0 a1 a2 a3 a4 a5 a6 a7 b0 b4 b2 b6 b1 b5 b3 b7 0 0 0 0 0 0 2 2 1 2 3 0 图图 6 1 n 4 时的时的 FFT 蝶式变换图蝶式变换图 显然 FFT 算法的计算复杂度为 O nlogn 2 并行 FFT 算法 设 P 为处理器的个数 一种并行 FFT 实现时是将 n 维向量 a 划分成 p 个连续的 m 维子向量 这里 第 i 个子向量中下标为 i m i 1 m 1 其元素被分配至第 i 号处理器 i 0 1 pnm p 1 由图 5 1 可以看到 FFT 算法由 logn 步构成 依次以 2logn 1 2logn 2 2 1 为下标跨 度