并行计算实验上机 国家高性能计算中心（合肥）

主要内容 资料下载 关于上机 上机题目(OpenMP、MPI、GPU、MapReduce) 国家高性能计算中心（合肥）

实验资料 实验资料下载： http://home.ustc.edu.cn/~wpc520/alg/ 国家高性能计算中心（合肥）

主要内容 资料下载 关于上机 上机题目(OpenMP、MPI、GPU、MapReduce) 国家高性能计算中心（合肥）

关于上机 上机地点：电三楼4楼机房 上机时间： 上机成绩： 上机检查打分+实验报告打分 第9~12周的周六，分两批次： 学号末位奇数8:30-11:30，学号末位偶数14:00-17:00 OpenMP： 4.27 8:30-11:30/14:00-17:00 MPI： 5.4 8:30-11:30/14:00-17:00 GPU： 5.18 8:30-11:30/14:00-17:00 MapReduce: 5.25 8:30-11:30/14:00-17:00 上机成绩： 上机检查打分+实验报告打分 每次上机后，请在两周内提交你的实验报告(模板)，命名“学号+姓名+实验名”，如：PB10011001+张三+实验一，并发至邮箱：algorithm225@163.com 国家高性能计算中心（合肥）

关于上机 实验报告(模板) 国家高性能计算中心（合肥）

主要内容 资料下载 关于上机 上机题目(OpenMP、MPI、GPU、MapReduce) 国家高性能计算中心（合肥）

实验1: OpenMP 简介： OpenMP是一个共享存储并行系统上的应用程序接口。它规范了一系列的编译制导、运行库例程和环境变量。 它提供了C/C++和FORTRAN等的应用编程接口，已经应用到UNIX、Windows NT等多种平台上。 OpenMP使用FORK-JOIN并行执行模型。所有的OpenMP程序开始于一个单独的主线程（Master Thread）。主线程会一直串行地执行，直到遇到第一个并行域（Parallel Region）才开始并行执行。 ①FORK：主线程创建一队并行的线程，然后，并行域中的代码在不同的线程队中并行执行；②JOIN：当诸线程在并行域中执行完之后，它们或被同步或被中断，最后只有主线程在执行。 国家高性能计算中心（合肥）

实验1: OpenMP 实验环境： 在Linux上编译和运行OpenMP程序 编译OpenMP程序： gcc a.c –fopenmp –o a 运行OpenMP程序： ./a 国家高性能计算中心（合肥）

实验1: OpenMP 实验环境： 在Windows Microsoft Visual Studio中编写程序，可直接配置使用OpenMP。属性-C/C++-语言-OpenMP支持 国家高性能计算中心（合肥）

实验1: OpenMP 题目： 示例：Pi 用4种不同并行方式的OpenMP实现π值的计算 用OpenMP实现PSRS排序(附1) 国家高性能计算中心（合肥）

实验1: OpenMP Pi (串行)： #include <stdio.h> static long num_steps = 100000;//越大值越精确 double step; void main(){ int i; double x, pi, sum = 0.0; step = 1.0/(double)num_steps; for(i=1;i<= num_steps;i++){ x = (i-0.5)*step; sum=sum+4.0/(1.0+x*x); } pi=step*sum; printf("%lf\n",pi); 在这里简单说明一下求π的积分方法，使用公式arctan(1)=π/4以及(arctan(x))'=1/(1+x^2). 在求解arctan(1)时使用矩形法求解： 求解arctan(1)是取a=0, b=1. 国家高性能计算中心（合肥）

实验1: OpenMP Pi (使用并行域并行化的程序)： 国家高性能计算中心（合肥） #include <stdio.h> #include <omp.h> static long num_steps = 100000; double step; #define NUM_THREADS 2 void main () { int i; double x, pi, sum[NUM_THREADS]; step = 1.0/(double) num_steps; omp_set_num_threads(NUM_THREADS); //设置2线程 #pragma omp parallel private(i) //并行域开始，每个线程(0和1)都会执行该代码 double x; int id; id = omp_get_thread_num(); for (i=id, sum[id]=0.0;i< num_steps; i=i+NUM_THREADS){ x = (i+0.5)*step; sum[id] += 4.0/(1.0+x*x); } for(i=0, pi=0.0;i<NUM_THREADS;i++) pi += sum[i] * step; printf("%lf\n",pi); //共2个线程参加计算，其中线程0进行迭代步0,2,4,...线程1进行迭代步1,3,5,.... 国家高性能计算中心（合肥）

实验1: OpenMP Pi (使用共享任务结构并行化的程序)： 国家高性能计算中心（合肥） #include <stdio.h> #include <omp.h> static long num_steps = 100000; double step; #define NUM_THREADS 2 void main () { int i; double x, pi, sum[NUM_THREADS]; step = 1.0/(double) num_steps; omp_set_num_threads(NUM_THREADS); //设置2线程 #pragma omp parallel //并行域开始，每个线程(0和1)都会执行该代码 double x; int id; id = omp_get_thread_num(); sum[id]=0; #pragma omp for //未指定chunk，迭代平均分配给各线程（0和1），连续划分 for (i=0;i< num_steps; i++){ x = (i+0.5)*step; sum[id] += 4.0/(1.0+x*x); } for(i=0, pi=0.0;i<NUM_THREADS;i++) pi += sum[i] * step; printf("%lf\n",pi); }//共2个线程参加计算，其中线程0进行迭代步0~49999，线程1进行迭代步50000~99999. 国家高性能计算中心（合肥）

实验1: OpenMP Pi (使用private子句和critical部分并行化的程序)： 国家高性能计算中心（合肥） #include <stdio.h> #include <omp.h> static long num_steps = 100000; double step; #define NUM_THREADS 2 void main () { int i; double pi=0.0; double sum=0.0; double x=0.0; step = 1.0/(double) num_steps; omp_set_num_threads(NUM_THREADS); //设置2线程 #pragma omp parallel private(x,sum) //该子句表示x,sum变量对于每个线程是私有的 int id; id = omp_get_thread_num(); for (i=id, sum=0.0;i< num_steps; i=i+NUM_THREADS){ x = (i+0.5)*step; sum += 4.0/(1.0+x*x); } #pragma omp critical //指定代码段在同一时刻只能由一个线程进行执行 pi += sum*step; printf("%lf\n",pi); } //共2个线程参加计算，其中线程0进行迭代步0,2,4,...线程1进行迭代步1,3,5,....当被指定为critical的代码段 正在被0线程执行时，1线程的执行也到达该代码段，则它将被阻塞知道0线程退出临界区。 国家高性能计算中心（合肥）

实验1: OpenMP Pi (使用并行规约的并行程序)： 国家高性能计算中心（合肥） #include <stdio.h> #include <omp.h> static long num_steps = 100000; double step; #define NUM_THREADS 2 void main () { int i; double pi=0.0; double sum=0.0; double x=0.0; step = 1.0/(double) num_steps; omp_set_num_threads(NUM_THREADS); //设置2线程 #pragma omp parallel for reduction(+:sum) private(x) //每个线程保留一份私有拷贝sum，x为线程私有，最后对线程中所以sum进行+规约，并更新sum的全局值 for(i=1;i<= num_steps; i++){ x = (i-0.5)*step; sum += 4.0/(1.0+x*x); } pi = sum * step; printf("%lf\n",pi); } //共2个线程参加计算，其中线程0进行迭代步0~49999，线程1进行迭代步50000~99999. 国家高性能计算中心（合肥）

主要内容 资料下载 关于上机 上机题目(OpenMP、MPI、GPU、MapReduce) 国家高性能计算中心（合肥）

实验2: MPI 简介： MPI（Message Passing Interface）是目前最重要的一个基于消息传递的并行编程工具，它具有移植性好、功能强大、效率高等许多优点，而且有多种不同的免费、高效、实用的实现版本，几乎所有的并行计算机厂商都提供对它的支持，成为了事实上的并行编程标准。 MPI是一个库，而不是一门语言，因此对MPI的使用必须和特定的语言结合起来进行。MPI不是一个独立的自包含系统，而是建立在本地并行程序设计环境之上，其进程管理和I/O均由本地并行程序设计环境提供。例如，MPI可以建立在IBM SP2的POE/MPL之上，也可以建立在Intel Paragon的OSF/NX。除了这些商业版本的MPI实现，还有一些免费版的MPI实现，主要有MPICH，LAM和CHIMP。 国家高性能计算中心（合肥）

实验2: MPI 实验环境： 本次实验，要求自己在Linux环境下搭建单结点的MPI环境，有条件的同学，可以尝试多节点。 用的版本是MPICH-3.0.4，下载后，解压，安装配置如下： ./configure --enable-fc --enable-cxx --enable-romio --enable-threads=multiple --prefix=${HOME}/soft/mpich2/3.0.4 --with-pm=mpd make make install 设置环境变量： 编辑~/.bashrc，在文件的末尾，添加如下几行 export PATH=${HOME}/soft/mpich2/3.0.4/bin:${PATH} export LD_LIBRARY_PATH=${HOME}/soft/mpich2/3.0.4/lib:${LD_LIBRARY_PATH} export MANPATH=${HOME}/soft/mpich2/3.0.4/share/man:${MANPATH} 更新环境变量，source 编辑${HOME}/.mpd.conf文件，添加一行：MPD_SECRETWORD=mypasswd 修改该文件权限，chmod 600 启动进程管理器：mpdboot 查看：mpdtrace 国家高性能计算中心（合肥）

实验2: MPI 编译运行： 编译mpi程序： mpicc demo.c –o demo.o 运行mpi程序： mpirun -np 4 ./demo.o (-np选项指定需要运行的进程数，大家可以自由设置，而非固定使用此处的4) 国家高性能计算中心（合肥）

实验2: MPI 题目： 用MPI编程实现PI的计算。 用MPI实现PSRS排序(附1)。 国家高性能计算中心（合肥）

附（1） 划分方法 示例：MIMD-SM模型上的PSRS排序 begin n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p 示例：MIMD-SM模型上的PSRS排序 begin (1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个pi处理 A[(i-1)n/p+1..in/p] (2)局部排序：pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序 (3)选取样本：pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素 (4)样本排序：用一台处理器对p2个样本元素进行串行排序 (5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并 播送给其他pi (6)主元划分：pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段 (7)全局交换：各处理器将其有序段按段号交换到对应的处理器中 (8)归并排序：各处理器对接收到的元素进行归并排序 end. 国家高性能计算中心（合肥） 2019/7/1

附（1） 例6.1 PSRS排序过程。N=27，p=3，PSRS排序如下： 国家高性能计算中心（合肥） 2019/7/1

主要内容 资料下载 关于上机 上机题目(OpenMP、MPI、GPU、MapReduce) 国家高性能计算中心（合肥）

实验3: GPU 简介： 编译： 实验环境： CUDA™是一种由NVIDIA推出的通用并行计算架构，该架构使GPU能够解决通用的计算问题。 它提供了C/C++和FORTRAN等的应用编程接口，已经应用到UNIX、Windows NT等多种平台上。 编译： Windows下可直接使用Windows Microsoft Visual Studio等集成开发环境。 Linux下编译：nvcc cuda.cu。 实验环境： 自己的笔记本 or 我们提供的超算中心的GPU集群 国家高性能计算中心（合肥）

实验3: GPU Windows下安装： Linux下安装： 在设备管理器中查看GPU是否支持CUDA。 安装开发包，需要预先安装Visual Studio 2010 或者更高版本。 验证安装，打开命令提示框，输入命令nvcc – V。 Linux下安装： 使用lspci |grep nvidia –I 命令查看GPU型号。 在CUDA下载页面选择合适的系统平台，下载对应的开发包(*.run)。 安装：使用： chmod a+x cuda_7.0.28_linux.run sudo ./cuda_7.0.28_linux.run。 设置环境变量： PATH=/usr/local/cuda/bin:$PATH export PATH source /etc/profile 国家高性能计算中心（合肥）

实验3: GPU Windows下创建及调试： Linux下创建及调试： 新建项目-CUDA 7.0 Runtime。 调试：使用Nsight 进行调试： Nsight->start CUDA debugging Linux下创建及调试： 创建*.cu以及*.cuh文件，需包含<cuda_runtime.h>头文件。 调试：使用cuda-gdb进行调试： nvcc–g –G *.cu –o binary nvcc为cuda程序编译器。 -g 表示可调试。 *.cu 为cuda源程序。 -o 生成可执行文件。 国家高性能计算中心（合肥）

实验3: GPU 实验题目： 向量加法。定义A,B两个一维数组，编写GPU程序将A和B对应项相加，将结果保存在数组C中。分别测试数组规模为10W、20W、100W、200W、1000W、2000W时其与CPU加法的运行时间之比。 矩阵乘法。定义A，B 两个二维数组。使用GPU 实现矩阵乘法。并对比串行程序，给出加速比。 示例： GPU上的矩阵乘法。 国家高性能计算中心（合肥）

实例: GPU上矩阵乘法 GPU上矩阵乘法： 每一个线程计算C矩阵中的一个 元素。 每一个线程从全局存储器读入A 矩阵的一行和B矩阵的一列。 方位N =BLOCK_SIZE次。 国家高性能计算中心（合肥）

实例: GPU上矩阵乘法 GPU上矩阵乘法(主机端函数)： 国家高性能计算中心（合肥） #include <stdio.h> #include <stdlib.h> #include <time.h> //CUDA RunTime API #include <cuda_runtime.h> //单个block大小 #define THREAD_NUM 256 ///矩阵大小 #define MATRIX_SIZE 1000 ///block个数 int blocks_num = (MATRIX_SIZE + THREAD_NUM - 1) / THREAD_NUM; int main() { //定义矩阵 float *a, *b, *c, *d; int n = MATRIX_SIZE; //分配主机端内存 a = (float*)malloc(sizeof(float)* n * n); b = (float*)malloc(sizeof(float)* n * n); c = (float*)malloc(sizeof(float)* n * n); d = (float*)malloc(sizeof(float)* n * n); float *cuda_a, *cuda_b, *cuda_c; … 国家高性能计算中心（合肥）

实例: GPU上矩阵乘法 GPU上矩阵乘法(主机端函数)： 国家高性能计算中心（合肥） … //分配设备端显存 cudaMalloc((void**)&cuda_a, sizeof(float)* n * n); cudaMalloc((void**)&cuda_b, sizeof(float)* n * n); cudaMalloc((void**)&cuda_c, sizeof(float)* n * n); ///生成矩阵a, b generateMatrix(a, b); //cudaMemcpyHostToDevice - 从内存复制到显存 //cudaMemcpyDeviceToHost - 从显存复制到内存 cudaMemcpy(cuda_a, a, sizeof(float)* n * n, cudaMemcpyHostToDevice); cudaMemcpy(cuda_b, b, sizeof(float)* n * n, cudaMemcpyHostToDevice); ///设备端函数 CUDAkernal << < blocks_num, THREAD_NUM, 0 >> >(cuda_a , cuda_b , cuda_c , n , time); //cudaMemcpy 将结果从显存中复制回内存 cudaMemcpy(c, cuda_c, sizeof(float)* n * n, cudaMemcpyDeviceToHost); //Free cudaFree(cuda_a); cudaFree(cuda_b); cudaFree(cuda_c); } 国家高性能计算中心（合肥）

实例: GPU上矩阵乘法 GPU上矩阵乘法(设备端函数)： 国家高性能计算中心（合肥） __global__ static void CUDAkernal (const float* a, const float* b, float* c, int n) { //block内的threadID const int tid = threadIdx.x; //blockID const int bid = blockIdx.x; //全局threadID const int idx = bid * THREAD_NUM + tid; const int row = idx / n; const int column = idx % n; …. 国家高性能计算中心（合肥）

实例: GPU上矩阵乘法 GPU上矩阵乘法(设备端函数)： 国家高性能计算中心（合肥） …. //计算矩阵乘法 if (row < n && column < n) { float t = 0; for (i = 0; i < n; i++) t += a[row * n + i] * b[i * n + column]; } c[row * n + column] = t; 国家高性能计算中心（合肥）

实例: GPU上矩阵乘法 GPU上矩阵乘法(shared memory)： 国家高性能计算中心（合肥） __global__ static void CUDAkernal (const float* a, const float* b, float* c, int n) { ///静态分配shared memory __shared__ int s[64]; …. } … ///动态分配shared memory CUDAkernal << < blocks_num, THREAD_NUM, N >> >(cuda_a , cuda_b , cuda_c , n , time); 国家高性能计算中心（合肥）

主要内容 资料下载 关于上机 上机题目(OpenMP、MPI、GPU、MapReduce) 国家高性能计算中心（合肥）

实验4: MapReduce 我们提供了丰富的学习和实验资料： 国家高性能计算中心（合肥）

实验4: MapReduce 实验题目： 1. 按照Hadoop安装运行说明文档中的指导自己搭建伪分布式Hadoop环境，熟悉HDFS的常用操作（参考 Hdoop实战 第31-36页），运行WordCount程序，得到统计结果。请详细写出你每一步的操作，最好有截图，最后的结果部分必须有截图。 国家高性能计算中心（合肥）

实验4: MapReduce 实验题目： 2. 实现一个统计输入文件中各个长度的单词出现频次的程序。假如输入为： Input1. txt a bc de fg hdk e gh f tt dhs Input2.txt b cd e g tt dd 由于输入文件中 长度为1的单词出现6次 长度为2的单词出现8次 长度为3的单词出现2次 所以，最后的输出结果是 1 6 2 8 3 2 备注：输入文件需要你自动用程序生成，每一行的各个单词之间用空格分隔 国家高性能计算中心（合肥）