并行算法实践.

Presentation on theme: "并行算法实践."— Presentation transcript:

1 并行算法实践

2 SMP集群上MPI与OpenMP混合编程
国家高性能计算中心（合肥） 2018/11/16

3 SMP集群体系架构 国家高性能计算中心（合肥） 2018/11/16

4 SMP集群体系架构 每节点为单个计算机系统且配备一份OS 节点间属分布存储；节点内为共享存储 两级并行 典型机器
节点间－－消息传递 节点内－－共享变量 典型机器 IBM ASCI White、Sun Ultra HPC、SGI Origin 国产的曙光3000 国家高性能计算中心（合肥） 2018/11/16

5 SMP集群编程模型 根据呈现给程序员的编程界面层次数分为两类 ： 单一存储模型SMM(Single Memory Model)
混合存储模型HMM(Hybrid Memory Model) 国家高性能计算中心（合肥） 2018/11/16

6 SMP集群编程模型 单一存储模型－－具有编程界面简单、直观，大量细节被隐藏，易于算法实现等优点，但其性能大大影响了该模型的广泛应用，因为性能受底层硬件实现机制的约束。 它又可以细分为： 纯共享ASMM(All Shared Memory Model) 如各种DSM和SVM系统。 纯消息传递模型AMPM(All Message Passing Model) 如不支持共享存储，则将SMP集群看作普通的集群。 国家高性能计算中心（合肥） 2018/11/16

7 SMP集群编程模型 混合存储模型 －－在SMP集群体系结构下，同时使用共享变量和消息传递两种编程界面的模型。针对SMP集群的特点，节点内利用共享存储进行通信，节点间采用分布式存储的消息传递进行通信。 混合存储模型，因为它是针对SMP集群体系结构提出的，是SMP集群体系结构下编程模型中性能最高的。但它也有着难以使用的缺点，因为程序员需要同时掌握两种编程界面，无疑对普通程序员来说困难一些。 国家高性能计算中心（合肥） 2018/11/16

8 SMP集群混合编程模型 节点内 节点内 消息传递 共享变量 共享变量 多线程 OpenMP MPI 多线程 OpenMP
国家高性能计算中心（合肥） 2018/11/16

9 MPI+Thread VS. MPI+OpenMP
OpenMP和Thread的根本实现机制一致，都是由操作系统支持的线程实现 OpenMP比Thread易用性高很多。OpenMP直接提供了大量的并行操作语句，也封装了线程的同步和互斥操作，而使用Thread模型时却还要考虑繁杂的线程间的同步和互斥，无疑易用性远远不及OpenMP。 例如，Pthreads不支持增量并行化，给定一个串行计算程序，用户很难使用Pthreads将其并行化，用户必须考虑很多低级细节，因而Pthreads不能很自然的支持循环级并行，用户需大量修改串行代码，而OpenMP能灵活的支持粗粒度和细粒度并行化，很多串行代码能够简单的并行化 国家高性能计算中心（合肥） 2018/11/16

10 MPI+Thread VS. MPI+OpenMP
虽然Thread的计算性能好于OpenMP，但只是略优于OpenMP，而这点性能差别与易用性和其他性能的巨大差别比较起来微不足道。 我们选择MPI＋OpenMP 国家高性能计算中心（合肥） 2018/11/16

11 MPI+OpenMP混合编程 MPI执行模型 … MPI_Init( &argc, &argv ); MPI_Comm_size( … );
MPI_Comm_rank(…, &rank ); if (rank==0) MPI_Send(A,…); else MPI_Recv(A,…); 国家高性能计算中心（合肥） 2018/11/16

12 MPI+OpenMP混合编程 OpenMP执行模型 … double A[N][N]; #pragma omp parallel for
for(i=0;i<N;i++) for(j=0;j<N;j++) A[i][j] = … #pragma omp parallel { } 国家高性能计算中心（合肥） 2018/11/16

13 MPI+OpenMP混合编程 国家高性能计算中心（合肥） 2018/11/16

14 ①在每个节点上只有一个MPI进程，该进程首先进行初始化；
MPI+OpenMP混合编程 ①在每个节点上只有一个MPI进程，该进程首先进行初始化； 国家高性能计算中心（合肥） 2018/11/16

15 MPI+OpenMP混合编程 ②每个节点上的MPI进程可以独立作一些局部计算，需要时也可以进行节点间的通信； 国家高性能计算中心（合肥）
2018/11/16

16 MPI+OpenMP混合编程 ③在MPI进程内的主要计算部分（通常是循环部分），采用OpenMP多线程并行求解； 国家高性能计算中心（合肥）
2018/11/16

17 MPI+OpenMP混合编程 ④在OpenMP求解部分结束后，MPI进程也可以做局部计算、通信或同步； 国家高性能计算中心（合肥）
2018/11/16

18 MPI+OpenMP混合编程 ⑤OpenMP多线程求解部分和MPI进程局部计算、通信都可以穿插进行，当全部计算工作结束后，MPI进程结束；
国家高性能计算中心（合肥） 2018/11/16

19 MPI+OpenMP混合编程 节点内并行化粒度－－有粗粒度并行化和细粒度并行化两种方法。 国家高性能计算中心（合肥） 2018/11/16

20 MPI+OpenMP混合编程 节点内选择细粒度并行化，将可以达到性能和易用性两方面的兼顾，这是因为：
绝大多数程序主要的计算量都在循环中，而细粒度并行化主要针对循环进行并行化； 细粒度并行化比粗粒度并行化的工作量大大降低，程序员几乎不用关心其它并行化的细节，而只要在循环计算外使用OpenMP编译制导指令并行化即可，这样的工作量即便是相对单一编程界面来讲，也大不了多少； 细粒度并行化方法对已有的MPI程序移植到SMP集群上，无疑也是最好的方法。 国家高性能计算中心（合肥） 2018/11/16

21 MPI+OpenMP混合编程 细粒度并行化中循环选择可以遵循以下原则：
应该选择计算时间占全局计算时间比例大的循环来进行并行化，这样才能显著提高性能； 由于循环并行化会带来调度的开销，我们应该选择那些并行化后性能仍可以提高的循环。这就意味着对于计算量小的循环，我们应该直接放弃对它并行化； 循环选择还有一个重要的问题就是并行化循环不能改变循环的原来语义。对循环进行并行化时，可能会改变循环的原来语义，这种情况存在跨迭代依赖关系的循环中可能会出现。因而对于并行化可能会改变原来语义的循环，我们也不能进行并行化。 （可以考虑修改原有循环。） 国家高性能计算中心（合肥） 2018/11/16

22 MPI+OpenMP混合编程 优化措施 在OpenMP并行区域内不要通信（这里的通信指的是不同节点内的线程间的通信），在节点中多线程共用的代码间的通信会急剧增加带宽竞争； 在单个线程中也尽量不要通信，因为通信一般都蕴含着同步操作，这会使得性能大大下降。如果必须在线程中通信，也应把通信次数尽可能的减少，或者把需要进行消息传递的代码改写到线程的外面进行通信； 国家高性能计算中心（合肥） 2018/11/16

23 MPI+OpenMP混合编程 优化措施 线程中的同步次数也是影响性能的一个重要因素，应该慎重使用同步操作和那些蕴含同步的操作。实际上，有很多程序员为了确保程序的正确性，习惯于在代码中加入大量的同步操作。这样的做法虽然减少了程序受一些并行计算时不确定因素的影响，但在性能上也损失了很多； 避免节点内不必要的数据拷贝； 在细粒度并行化时，可能有一些循环因为数据的相互依赖性而无法进行并行化。 国家高性能计算中心（合肥） 2018/11/16

24 MPI+OpenMP混合编程 MPI函数的使用情况 这个模型要求MPI的实现必须线程安全 ;
因为在同一个MPI进程内的OpenMP并行区域内的每个线程共用同样的MPI通信符和主线程的线程号，所以MPI_Init()不能在并行区域内调用，否则MPI_Init()将被调用多次； MPI的通信函数调用只能在SINGLE或是MASTER区域内，并且要注意在多线程的情况下发送和接收的顺序，最好是都在MASTER的线程内完成；如： #pragma omp master MPI_Send(…); 国家高性能计算中心（合肥） 2018/11/16

25 MPI+OpenMP混合编程 使用MPI通讯的线程间同步 接收必须在数据使用前完成 数据在发送完成前不能修改 计算必须在发送操作调用前完成
MPI函数调用必须保持有序，如只在master线程中调用 国家高性能计算中心（合肥） 2018/11/16

26 MPI+OpenMP混合编程 使用MPI通讯的线程间同步 在MPI_Send前设置路障（barrier） . . .
#pragma omp parallel for for(…) { … ; A = … ;} #pragma omp barrier #pragma omp MASTER MPI_Send ( A,... ); 国家高性能计算中心（合肥） 2018/11/16

27 MPI+OpenMP混合编程 使用MPI通讯的线程间同步 在MPI_Recv或MPI_Wait之后设置路障（barrier） . . .
#pragma omp master MPI_IRecv ( A, ... ); #pragma omp MASTER MPI_Wait ( ... ); #pragma omp barrier ... = A(i) 国家高性能计算中心（合肥） 2018/11/16

28 Pi-MPI+OpenMP混合编程示例 #include "mpi.h" #include "omp.h"
#include <math.h> #define N int main( int argc, char* argv[] ){ int rank, nproc; int i,low,up; double local = 0.0, pi, w, temp; MPI_Status status; MPI_Init( &argc, &argv ); MPI_Comm_size( MPI_COMM_WORLD, &nproc ); MPI_Comm_rank( MPI_COMM_WORLD, &rank ); w = 1.0/N; low = rank*(N / nproc); up = low + N/nproc - 1; #pragma omp parallel for reduction(+:local) private(temp,i) for (i=low;i<up; i++){ temp = (i+0.5)*w; local = local + 4.0/(1.0+temp*temp); } MPI_Reduce(&local, &pi, 1, MPI_DOUBLE, MPI_SUM, 0,MPI_COMM_WORLD); if(rank==0) printf("pi = %.20f\n",pi*w); MPI_Finalize(); 国家高性能计算中心（合肥） 2018/11/16

29 omcc –omnicc=mpicc –o exefile sourcefile
MPI+OpenMP程序的编译 MPI编译器：mpicc Omni-OMP编译器：omcc 编译命令： omcc –omnicc=mpicc –o exefile sourcefile mpicc -cc=omcc -o pi-mpi-omp pi-mpi-omp.c -lm -O3 运行命令： export OMP_NUM_THREADS=xxx mpirun –np PROCNUM exefile 国家高性能计算中心（合肥） 2018/11/16

30 ### for compile your hybrid program with MPI and OpenMP
mpicc -o your_mpi_omp_c_file -fopenmp your_mpi_omp_c_file.c ### for run your hybrid program with MPI and OpenMP mpirun -np num_of_processes -machinefile ~/ma ./your_mpi_omp_c_file 国家高性能计算中心（合肥） 2018/11/16