并行程序， 编译与函数库简介，应用软件的调优 高性能服务器产品部 应用支持处：胡自玉（博士）

Presentation on theme: "并行程序， 编译与函数库简介，应用软件的调优 高性能服务器产品部 应用支持处：胡自玉（博士）"— Presentation transcript:

1 并行程序， 编译与函数库简介，应用软件的调优 高性能服务器产品部 应用支持处：胡自玉（博士）
并行程序， 编译与函数库简介，应用软件的调优 高性能服务器产品部 应用支持处：胡自玉（博士）

2 主要内容 并行程序 MPI函数库的设计基础 并行算法的设计基础 应用软件调优-化工方向 高性能计算与并行计算简介 并行计算机的发展
并行计算体系结构 并行计算机的性能评价技术 MPI函数库的设计基础 并行算法的设计基础 应用软件调优-化工方向

3 高性能计算 高性能计算(High Performance Computing) 并行计算(Parallel Computing）
并行计算，就是在并行机上所做的计算 计算科学与传统的两种科学，即理论科学和实验科学，并立被认为是人类认识自然的三大支柱，他们彼此相辅相成地推动科学发展与社会进步。在许多情况下，或者是理论模型复杂甚至理论尚未建立，或者实验费用昂贵甚至无法进行时，计算就成了求解问题的唯一或主要的手段。

4 高性能计算的应用领域

5 高性能计算的分类 计算密集（compute-intensive） 科学计算与数字模拟 数据密集（data-intensive）
数字图书馆、数据仓库、图像处理 网络密集（network-intensive） 网络应用 以上三种的混合

6 并行计算机 并行计算机就是由多个处理单元组成的计算机系统，这些处理单元相互通信和协作以快速、高效求解大型复杂问题。 处理单元有多少
处理单元的功能有多强 处理单元之间怎样连接 处理单元的数据如何传递 各处理单元如何相互协作 并行程序如何编写

7 并行计算机的发展 (1)并行机的萌芽阶段（1964-1975） (2)向量机/ SMP的发展和鼎盛阶段(1976-1990)
(3)MPP出现和蓬勃发展阶段（ ） (4)Cluster出现，并成为并行计算机的主流（1995年后）

8 常见的几种并行计算体系结构 SMP DSM（CC-NUMA） MPP Cluster

9 SMP- Symmetric MultiProcessing
多个CPU连接于统一的内存总线, 多CPU共用一个内存 内存地址统一编址，单一操作系统映像 可扩展性较差，一般CPU个数少于32个 目前商用服务器多采用这种架构 Chipset Memory NIC System CPUs I/O Bus Memory Bus >4 CPUs may require switching Local Area Network SMP具有如下特征： 对称共享存储：系统中任何处理器均可直接访问任何存储模块中的存储单元和I/O模块联接的I/O设备，且访问的延迟、带宽和访问成功的概率是一致的。所有内存地址单元统一编址。各个处理器之间的地位等价，不存在任何特权处理器。操作系统可在任意处理器上运行。 单一的操作系统映像：全系统只有一个操作系统驻留在共享存储器中，它根据各个处理器的负载情况，动态地分配各个进程到各个处理器，并保持各处理器间的负载平衡。 局部高速缓存Cache及其数据一致性：每个处理器均配备局部Cache，它们可以拥有独立的局部数据，但是这些数据必须保持与存储器中数据是一致的。 低通信延迟：各个进程通过读/写操作系统提供的共享数据缓存区来完成处理器间的通信，其延迟通常小于网络通信的延迟。 共享总线带宽：所有处理器共享总线的带宽，完成对内存模块和I/O模块的访问。 支持消息传递、共享存储并行程序设计。 SMP具有如下缺点： 欠可靠：总线、存储器或操作系统失效可导致系统崩溃。 可扩展性（scalability）较差：由于所有处理器共享总线带宽，而总线带宽每3年才增加2倍，跟不上处理器速度和内存容量的增加步伐，因此，SMP并行机的处理器个数一般少于32个，且只能提供每秒数百亿次的浮点运算性能。 SMP典型代表： SGI POWER Challenge XL系列并行机（36个MIPS R1000微处理器）； COMPAQ Alphaserver 84005/440 （12个Alpha 21264个微处理器）； HP9000/T600 （12个HP PA9000微处理器）； IBM RS6000/R40（8个RS6000微处理器）。

10 DSM- Distributed Shared Memory
物理上分布存储、所有内存模块统一编址 非一致内存访问（NUMA）模式 基于Cache的数据一致性，又称CC-NUMA 节点数可扩展到几百个，小型机多为此类架构 Local Area Network ... System NIC Memory CPUs Chipset I/O Bus Memory Bus I/O Bus NUMA Link DSM较好地改善了SMP并行机的可扩展能力，具有如下特征： 并行机以结点为单位，每个结点包含一个或多个CPU，每个CPU拥有自己的局部Cache，并共享局部存储器和I/O设备，所有结点通过高性能互联网络相互联接； 物理上分布存储：内存模块局部在各结点中，并通过高性能互联网络相互联接，避免了SMP访存总线的带宽瓶颈，增强了并行机的可扩展能力。 单一的内存地址空间：尽管内存模块分布在各个结点，但是，所有这些内存模块都由硬件进行了统一的编址，并通过互联网络联接形成了并行机的共享存储器。各个结点即可以直接访问局部内存单元，又可以直接访问其他结点的局部内存单元。 非一致内存访问（NUMA）模式：由于远端访问必须通过高性能互联网络，而本地访问只需直接访问局部内存模块，因此，远端访问的延迟一般是本地访问延迟的3倍以上。 单一的操作系统映像：类似于SMP，在DSM并行机中，用户只看到一个操作系统，它可以根据各结点的负载情况，动态地分配进程。 基于Cache的数据一致性：通常采用基于目录的Cache一致性协议来保证各结点的局部Cache数据与存储器中数据的一致性。同时，我们也称这种DSM并行机结构为CC-NUMA结构。 低通信延迟与高通信带宽：专用的高性能互联网络使得结点间的延迟很小，通信带宽可以扩展。例如，目前最先进的DSM并行机SGI Origin 3000的双向点对点通信带宽可达3.2GB/秒，而延迟小于1个微秒。 DSM并行机可扩展到上百个结点，能提供每秒数千亿次的浮点运算性能。例如，SGI Origin 2000可以扩展到64个结点（128个CPU），而SGI Origin 3000可以扩展到256个结点（512个CPU）。但是，由于受Cache一致性要求和互联网络性能的限制，当结点数目进一步增加时，DSM并行机的性能也将大幅下降。 支持消息传递、共享存储并行程序设计。 DSM典型代表： SGI Origin 2000； SGI Origin 3800。

11 MPP- Massively Parallel Processors
节点个数可达成百上千个 节点类型可以是DM、SMP、DSM 节点之间采用专用高速互连设备 排列在Top500前面的多数系统属于这种类型 ... 专用高速互联 NIC Memory I/O Bus System 局部总线/互连网络 CPUs

12 Cluster ... ... LAN Memory System Chipset SAN CPUs System LAN Memory
独立的节点、商品化网络连接 开放的硬件设备、操作系统、应用编程接口 节点数可达几百个，性能已接近超级计算机系统 近年来发展很快，已广泛应用到高性能科学计算领域 LAN Memory I/O Bus Memory Bus System Chipset SAN CPUs System LAN Memory I/O Bus Memory Bus System Chipset SAN CPUs CPUs ... Memory Bus ... Chipset Memory I/O Bus LAN SAN System Area Network Local Area Network

13 Cluster 集群：将多个计算机系统通过网络连接起来如同一个系统一样提供服务。
集群一般可以获得高并行处理能力、高可用性、负载均衡和管理便捷性。 高并行处理能力: 多结点间通过并行环境和并行程序设计实现应用的高效并行处理。 高可用性：通过“failover”(失效恢复)集群技术获得。当然某结点发生故障时候，资源可以自动在2个或者多个结点间自动迁移。 负载均衡：通过在多个结点上实现应用的负载均衡实现。 管理便捷性：通过机群系统软件和机群管理软件对整个机群实现单一管理。

14 Linpack Linpack是国际上流行的用于测试高性能计算机系统浮点性能的benchmark
通过对高性能计算机求解线性代数方程组能力的测试，评价高性能计算机的浮点性能 HPL(High Performance Linpack) 针对大规模的并行计算机系统的测试 HPL版Linpack一般用于并行超级计算机 用户可以选择矩阵的大小(问题规模)、使用各种优化方法来执行测试程序，寻求最佳的测试结果 计算量(2/3 * N^3 – 2*N^2) / 计算时间

15

16 NAS并行基准测试 数值空气动力学模拟(NAS22)并行基准测试NPB(NAS Parallel Benchmark)是由NASA
Ames 于1991 年研究开发的 由8 个来源于计算流体动力学(CFD23)的程序组成，这8 个不同的程序从不同的方面反映了CFD 计算的特点，包括5 个核心和3 个模拟CFD 应用 目前每个基准测试有4 类问题规模：A、B、C、D，A 规模最小，D 最大。

17 SPEC HPC 测试 SPEC 成立于20 世纪80 年代末，它的目的就是建立、维持和认证相关的基准测试以应用于新一代的高性能计算机，它的主要工作有两个：开发测试计算机性能的测试工具。 SPEC HPC 软件包有三大组成部分： SPEC CHEM(化学) SPEC ENV（环境） SPEC SEIS（地震） 最新的测试程序是SPEC HPC2002，SPEC HPC2002 的评价指标说明了一个系统在24 小时能运行的性能测试次数

18 主要内容 并行程序 MPI函数库的设计基础 并行算法的设计基础 应用软件调优-化工方向 MPI的简介 MPI的核心函数 MPI的编辑与运行

19 什么是MPI? MPI(Message Passing Interface ) MPI是一个库，而不是一门语言；
目标: 是提供一个实际可用的、可移植的、高效的和灵活的消息传递接口标准. MPI提供C/C++和Fortran语言的绑定

20 MPI的实现 MPICH：最重要的MPI实现。 Intel MPI： MVAPICH：
mpich1.* ； mpich2.* （www-unix.mcs.anl.gov/mpi/ mpich Intel MPI： ( MVAPICH： ( LAM MPI： Ohio State University开发。 (

21 MPI程序的编译与运行 MPI程序的编译： mpicc–o mpi_prog mpi_proc.c
mpiCC–o mpi_prog mpi_prof.C mpif77 –o mpi_prog mpi_prog.f mpif90 –o mpi_prog mpi_prof.f90 ifort mpi_prog.f -L/usr/local/mpich-1.2.7/lib –lmpich -lfmpich MPI程序的运行命令： mpirun –machinefile filename –np N <program name> （machinefile：机器列表文件； np:运行的进程数） MPI程序的运行过程： 找到机器列表 通过SSH或RSH找到所有机器 在所有机器上执行程序 结束所有机器上的程序 图!!!!!!!!!!

22 MPI程序的运行 3 1 Execute on node1: mpirun –np 4 mpi_prog 2
Check the MPICH machine file: node1 node2 node3 node4 node5 node6 2 mpi_prog (rank 0) mpi_prog (rank 1) mpi_prog (rank 2) mpi_prog (rank 3) 3

23 例1：简单的Hello world程序 #include <stdio.h> #include “mpi.h”
int main (int argc, char* argv[]) { MPI_Init (&argc, &argv); printf (“Hello world”); MPI_Finalize (); }

24 MPI程序的一般结构

25 MPI并行程序设计基础 MPI简介 MPI的核心函数 MPI并行程序的两种基本模式 MPI的启动和结束 点对点通信 非阻塞通信 集合通信
（MPI提供C语言和Fortran语言接口，它包含了129个函数（根据1994年发布的MPI标准），1997年修订的标准（MPI-2），已超过200多个，目前最常用的也有约30个）

26 MPI的核心函数 MPI的初始化和结束 –MPI_Init, MPI_Finalize
–MPI_Comm_size, MPI_Comm_rank 点到点通信 –MPI_Send, MPI_Recv 非阻塞通信 –MPI_Isend, MPI_Irecv, MPI_Wait 集合通信 –MPI_Bcast, MPI_Reduce MPI的四种通信模式

27 MPI的初始化和结束 MPI初始化： MPI结束： Fortran：MPI_INIT（ierr）
C： int MPI_Init（int* argc , char** argv） MPI的初始化例行函数，用于初始化MPI运行环境　 每一个MPI进程调用的第一个MPI函数都是MPI_Init。该函数指示系统完成所有的初始化工作，以备对后续MPI库的调用进行处理。 MPI结束： Fortran： MPI_FINALIZE（ierr） C：int MPI_Finalize（void） 结束MPI执行环境。该函数一旦被应用程序调用时，就不能调用MPI的其它例行函数（包括MPI_Init），用户必须保证在进程调用MPI_Finalize之前把与完成进程有关的所有通信结束。

28 通信域函数 确定通信域中的进程数量 确定进程的标识符
C：MPI_Comm_size(MPI_Comm comm, int * size) 当MPI初始化后，每一个活动进程变成了一个叫做MPI_COMM_WORLD（全集）的通信域中的成员。通信域是一个不透明的对象，提供了在进程之间传递消息的环境。 进程通过调用函数MPI_Comm_size来确定一个通信域中的进程总数。 确定进程的标识符 C： MPI_Comm_rank(MPI_Comm comm, int *rank) 在一个通信域内的进程是有序的。在一个有p个进程的通信域中，每一个进程有一个唯一的序号（ID号），取值为0~p－１。 进程可以通过调用函数MPI_Comm_rank来确定它在通信域中的序号。

29 例2：简单的C+MPI程序 #include <stdio.h> #include “mpi.h”
int main (int argc, char* argv[]) { int numProc, myRank; MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &myRank); MPI_Comm_size (MPI_COMM_WORLD, &numProc); printf (“Hello. Process %d of %d here.\n”, myRank, numProc); MPI_Finalize (); }

30 点到点通信 消息发送函数 MPI_Send(buf,count,datatype,dest,tag,comm)
参数说明： 　　　　IN buf:发送缓冲区的起始地址 　　　　IN count:将要发送的数据的个数 　　　　IN datatype:发送数据的数据类型 　　　　IN dest:目的进程标识号 　　　　IN tag:消息标志 　　　　IN comm：通信域　 MPI_Send将发送缓冲区中的count个datatype数据类型的数据发送到目的进程，目的进程在通信域中的标识号是dest,本次发送的消息标志是tag,使用这一标志，就可以把本次发送的消息和本进程向同一目的进程发送的其他消息区别开。

31 阻塞通信 消息传送机制 阻塞方式： 它必须等到消息从本地送出之后才可以执行后续的语句 保证了缓冲区等资源的可再用性

32 非阻塞通信 非阻塞方式： 它不须等到消息从本地送出就可以执行后续的语句 但非阻塞调用的返回并不保证资源的可再用性
非阻塞通信主要用于计算和通信的重叠，从而提高整个程序执行的效率。

33 非阻塞通信 非阻塞消息发送函数： MPI_Isend(buf, count, datatype, dest, tag, comm, request) 参数说明： IN buf 发送缓冲区的起始地址 IN count 发送数据的个数 IN datatype 发送数据的数据类型 IN dest 目的进程号 IN tag 消息标志 IN comm 通信域 OUT request 返回的非阻塞通信（状况的）对象 MPI_ISEND的功能是启动一个（标准的）非阻塞发送操作它调用后立即返回，MPI_ISEND的调用返回并不意味着消息已经成功发送，它只表示该消息可以被发送。

34 非阻塞通信 非阻塞消息接收函数： MPI_Irecv(buf, count, datatype, dest, tag, comm, request) 参数说明： OUT buf 接收缓冲区的起始地址 IN count 接收数据的最大个数 IN datatype 每个数据的数据类型 IN source 源进程标识 IN tag 消息标志 IN comm 通信域 OUT request 非阻塞通信（状况的）对象 MPI_IRECV的功能是启动一个（标准的）非阻塞接收操作，它调用后立即返回。MPI_IRECV调用的返回并不意味着已经接收到了相应的消息，它只表示符合要求的消息可以被接收。

35 非阻塞通信 非阻塞通信的完成 MPI_WAIT(request,status) MPI_TEST(request,flag,status)
对于非阻塞通信调用的返回并不意味着通信的完成，需要专门的通信语句来完成或检查该非阻塞通信。 完成调用结束后，可以保证该非阻塞通信已正确完成。 MPI_WAIT(request,status) 等到与该非阻塞通信对象相应的非阻塞通信完成后才返回，同时释放该阻塞通信对象。 MPI_TEST(request,flag,status) 它的返回不一定等到与非阻塞通信对象相联系的非阻塞通信的结束。 若调用时该阻塞通信已经结束，则与MPI_WAIT效果相同，完成标志flag=true 若调用时该阻塞通信还没完成，可以返回，但完成标志flag=false

36 集合通信 集合通信是包含在通信因子中的所有进程都参加操作 集合通信一般实现三个功能 集合操作的三种类型： 通信：组内数据的传输
同步：组内所有进程在特定的地点在执行进度上取得一致 计算：对给定的数据完成一定的操作 集合操作的三种类型： 通信：广播(broadcast)、分散(scatter)、收集(gather)、全互换(alltoall)等 同步(barrier)：集合中所有进程都到达后，每个进程再接着运行 规约(reduction)：集合中的其中一个进程收集所有进程的数据并计算（如：求最大值、求最小值、加、乘等）

37 集合通信的通信功能 多对一通信 多对多通信 一对多通信 广播 MPI_Bcast() 收集 MPI_Gather()
散发 MPI_Scatter() 多对一通信 收集 MPI_Gather() 多对多通信 组收集MPI_Allgather() 全互换MPI_Alltoall()

38 组通信的同步功能 在组中建立一个同步栅栏 当每个进程都到达MPI_Barrier调用后，程序才接着往下执行
MPI_Barrier(MPI_Comm，comm) 在组中建立一个同步栅栏 当每个进程都到达MPI_Barrier调用后，程序才接着往下执行 等待所有的进程都到达同步调用点，也就是陆续地都执行了同步操作，才可以从同步调用返回，继续并行执行其他的操作。

39 集合通信的计算功能 归约操作MPI_Reduce()，就是接收缓冲区中数据的改变，而这是直接与各个进程发送缓冲区中的数据密切相关的。
归约、组归约、归约并散发、扫描及用户自定义归约操作等 MPI预定义的归约操作有：求最大值、最小值、求和、求积、逻辑与、逻辑或等

40 例2：并行PI程序 π 的并行求解算法： 由三角函数和积分公式可知： 假设将区间[0，1] 分成n等份，记 ，则采
用梯形积分公式计算上式积分如下： 由极限的定义，可以将 作为计算π的近似值。 即取 ，这里

41 例2：并行PI程序 算法的几何意义： 设计求π值并行算法的关键是构造一个合适的函数f ( x) ,使得它计算起来既简便，误差又小。

42 例2：并行PI程序 #include "mpi.h" #include <stdio.h>
#include <math.h> double f(double); double f(double x) /* 定义函数f(x) */ { return (4.0 / (1.0 + x*x)); } int main(int argc,char *argv[]) int done = 0, n, myid, numprocs, i; double PI25DT = ; /* 准确的π值*/ double mypi, pi, h, sum, x; double startwtime = 0.0, endwtime; int namelen; char processor_name[MPI_MAX_PROCESSOR_NAME];

43 例2：并行PI程序 MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&numprocs); /*参加运算进程数*/ MPI_Comm_rank(MPI_COMM_WORLD,&myid); /*当前进程标识号*/ MPI_Get_processor_name(processor_name,&namelen); /*本进程机器名字*/ fprintf(stdout,"Process %d of %d on %s\n",myid, numprocs, processor_name); n = 0 if (myid == 0) {   printf("Please give N="); scanf(&n); startwtime = MPI_Wtime(); } MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);/*将n值广播*/ h = 1.0 / (double) n;/*得到矩形的宽度所有矩形的宽度都相同*/ sum = 0.0; /*给矩形面积赋初值*/

44 mypi = h * sum; /*各个进程并行计算得到的部分和*/
for (i = myid + 1; i <= n; i += numprocs) /*每一个进程计算一部分矩形的面积，若进程总数numprocs为4，将0-1区间划分为100个矩形，则各个进程分别计算矩形块： 0进程 1进程 2进程 3进程 */ { x = h * ((double)i - 0.5); sum += f(x); } mypi = h * sum; /*各个进程并行计算得到的部分和*/ MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0,MPI_COMM_WORLD); /*将部分和累加得到所有矩形的面积该面积和即为近似π值*/

45 例2：并行PI程序 if (myid == 0) /*执行累加的0号进程将近似值打印出来*/ {
printf("pi is approximately %.16f, Error is %.16f\n", pi, fabs(pi - PI25DT)); endwtime = MPI_Wtime(); printf("wall clock time = %f\n", endwtime-startwtime); fflush( stdout ); } MPI_Finalize();

46 MPI的四种通信模式 标准通信模式（standard mode） MPI_SEND MPI_RECV
缓存通信模式（buffered-mode） MPI_BSEND 使用缓冲区发送消息, 只要缓冲区足够大, 而不管接收进程是否开始接收它都将立即返回, 也就是说, 在发送消息时是不需要等待的。 消息发送能否进行及能否正确返回不依赖于接收进程，完全依赖于是否有足够的通信缓冲区可用。 同步通信模式（synchronous-mode） MPI_SSEND 它可以在没有接收信号时就开始发送, 但要等到接收完成之后才能结束通信操作, 好处是无需用户自己申请缓冲区. 就绪通信模式（ready-mode） MPI_RSEND 只当已经有接收信号时才开始发送消息, 否则将出现错误.

47 主要内容 并行程序 MPI函数库的设计基础 并行算法的设计基础 应用软件调优-化工方向 并行程序的设计方法 并行算法的相关的基本概念
并行算法的分解 并行算法的分类 应用软件调优-化工方向

48 并行程序设计方法 分割 按任务分割 按数据分割 通信 确定通信 聚合 合理组织各任务 映射 按处理器来设计聚合后 的任务

49 分割 数据分割 任务分割 优点： 优点： 难度小，扩展性好，负载均衡 开发成本低，天然的分割 缺点 缺点： 粒度较细
负载均衡，扩展性，加速比 数据分割 优点： 难度小，扩展性好，负载均衡 缺点 粒度较细 按数据分割，从北京地区到世界，可以从2进程增加到200进程，扩展性好 按任务分割，假设有4个任务，从北京地区到世界，任然是4个任务，扩展性不好 一般情况，将任务分割与数据分割结合在一起。

50 通信 考虑分割后的各个模块关系，确定通信模式 点对点通信 集合通信 都有哪些数据需要共享 模块间是否有依赖关系 一个进程对另一个进程
一组进程共享数据 数据共享 消息传递 多线程 消息发送和接受 消息广播 消息散发和收集 本地共享内存存储数据 内存统一寻址 注意数据保护、线程同步问题

51 聚合 如何将分割的各模块组合给进程运行 提高性能，减少通信量，增大粒度 将通信频繁的小模块分为同一组
保证程序的可扩展性，随着数据规模的增大可使用更多的CPU资源 易于编写和维护程序

52 映射 按处理器来设计聚合后的任务 每颗CPU分配1个任务还是多个任务 动态负载均衡还是静态负载均衡 最大化的CPU利用率

53 并行算法 并行计算的相关基本概念 并行算法设计基本原则 并行化分解方法 并行算法分类 数值计算并行算法

54 并行计算的相关基本概念 并行算法设计：将一个任务分解为多个可同时执行的子任务，这些子任务分别运行在不同的处理器上，通过相互之间的数据交换完成同一个任务。 与并行计算有关的概念： 粒度：各个处理机可独立并行执行的任务大小的度量。 加速比： 效率： 性能：

55 并行算法设计基本原则 与体系结构相结合——线性结构，二维网络结构…… 具有可扩展性——并行算法是否随处理机个数增加而能够线性或近似线性的加速
粗粒度——通常情况，粒度越大越好 减少通信——减少通信量和通信次数 优化性能——单机计算效率和并行效率

56 并行化分解方法 区域分解法：分解被执行的数据
非重叠的区域分解，这种分解将离散化后的方程化成一些独立的小规模问题和一个与每个小问题关联的全局问题，此种分解给出的方法是子结构方法。 带重叠的区域分解

57 并行化分解方法 功能分解法：功能分解是将不同功能组成的问题，按照其功能进行分解的一种手段，其目的是逐一解决不同功能的问题，从而获得整个问题的解。 例如：使用Newton 法求解非线性方程F(x) = 0 在求解方程的过程中，需要用到函数值和导数值。因此，如果一部分处理机负责计算函数值，另一部分处理机负责计算导数值，就可以得到一种并行计算方法。 这时候计算是按照功能进行分配的，也既是所谓的功能分解。

58 并行化分解方法 流水线技术：流水线技术是并行计算中一个非常有效的、常用的手段，在并行计算中起着非常重要的作用。
以求解一簇递推问题为例加以说明： 上述计算中，沿 j 方向的计算是互相独立的，而沿 i 方向的计算则存在着向前依赖关系(递推关系)，无法独立进行。 不失一般性，我们假设数据划分仅沿 i 方向进行，即假设在有3 个处理器的分布式系统上，ai,j 被分成 3 段,如图所示，相同颜色的部分是可以并行计算的。 流水线计算示意图

59 并行化分解方法 分而治之方法： 以一个简单的求和问题为例，说明什么是分而治之方法。假设在q = 2*2*2个处理机上计算：
可以将计算依次分解为两个小的求和问题，用下图简单的描述（图中给出的是处理机号）。在图中，从上至下是分解的过程，从下至上是求部分和的过程。这就是有分有治的一个简单过程，也既是一种分而治之方法。 分而治之计算示意图

60 并行算法分类 按运算的基本对象 按进程间的依赖关系 按并行计算任务的大小 数值并行算法 非数值并行算法 同步并行算法 异步并行算法
纯并行算法 按并行计算任务的大小 粗粒度并行算法 细粒度并行算法

61 并行算法分类 数值计算是指基于代数关系运算的计算问题 非数值计算是指基于比较关系运算
如矩阵运算、多项式求值、线性代数方程组求解等。求解数值计算问题的方法称为数值算法（Numerical Algorithm） 科学与工程中的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题 非数值计算是指基于比较关系运算 诸如排序、选择、搜索、匹配等符号处理，相应的算法也称为非数值算法（Non-numerical Algorithm） 非数值计算在符号类信息处理中获得广泛应用，如数据库领域的计算问题，海量数据挖掘等 近年来广泛关注的生物信息学主要也是非数值计算

62 数值计算并行算法 矩阵并行计算 线性方程组并行求解 对称正定线性方程组并行解法 代数特征值问题并行解法 迭代算法并行化 行列分块算法
行行分块算法 列行分块算法 列列分块算法 Cannon算法 线性方程组并行求解 并行LU分解算法 三角方程组的并行分解算法 对称正定线性方程组并行解法 代数特征值问题并行解法 迭代算法并行化

63 数值计算并行算法 矩阵并行计算 矩阵存储方式——卷帘式

64 数值计算并行算法 串行矩阵乘法（i-j-k形式） 行列分块并行算法

65 数值计算并行算法 行列分块算法示意图

66 数值计算并行算法 线性方程组的并行求解 线性方程组的定义和符号 a1,1x1 + a1,2x2 + … + a1,nxn = b1
a2,1x1 + a2,1x2 + … + a2,nxn = b2 ，记为 AX=b an,1x1 + an,1x2 + … + an,nxn = bn

67 数值计算并行算法 线性方程组的LU分解算法 第一步：LU分解 第二步：解三角方程组

68 数值计算并行算法 分块矩阵在处理器阵列的数据分布情况 随机生成的稠密矩阵 被分成 的块，循环分布在 的二维处理器阵列上。

69 数值计算并行算法 分块矩阵的LU分解过程示意

70 主要内容 并行程序 MPI函数库的设计基础 并行算法的设计基础 应用软件调优-化工方向 应用软件瓶颈分析 应用软件的优化方法
应用软件优化举例 应用软件特征分析

71 应用软件存在的瓶颈分析 软件是瓶颈 软件架构跟不上硬件架构的发展 重硬不重软，软件升级更新慢 计算算法陈旧 理论突破困难 交叉背景人员匮乏
单位：核 70%的应用都是小应用，这样建设大型超级计算机的意义就打了折扣，在为很多想计算的未知科学问题还是计算不了。 很多软件都是上世纪60~70年代发展的，是针对当时的计算机结构的。软件照搬，我国自主的行业计算软件几乎是空白（适当发挥，展开一下） 问题很多，如何使的应用软件也能跟上硬件和需求的发展，就是每过个5~6年，软件的性能也翻个100X，我们该怎么办？ 应用软件是性能的瓶颈 注：参考上海超算中心2011年数据

72 浪潮之应用软件性能提升之应对策略 模型算法革新 持续循环 技术架构创新 系统平台优化 输入参数优化 代码级优化 物理模型创新 算法优化
平 台 为 依 据 应 用 为 导 向 理 论 为 指 引 持续循环 GPU MIC 专用机 技术架构创新 针对这种情况，浪潮结合自身多年从事高性能计算研究的经验，提出了三位一体的金字塔应对策略，即： 应用特征分析 硬件优化 软件优化 系统平台优化 通向性能提高100倍之路

73 基于应用主要性能特征指导硬件和软件优化 准备 特征收集 应用调优 平台调优 结果
特定计算平台、典型应用(Application)、合适算例(workload) 特征收集 收集CPU/ Memory/ Netowrk/ IO 四部分的系统级、应用级和微架构级性能数据。 应用调优 应用特征分析； 调整应用参数； 调整并行方式； 调整应用负载； 平台调优 平台特征分析； 更改硬件配置； 调整硬件参数； 调整中间软件； 一直以来浪潮非常重视应用程序的特征分析，并建立了一整套完善的应用特征分析理论，用以指导以应用为导向的系统优化。 结果 提供实测数据及分析支撑，设计行业应用的最优化系统构建方案

74 平衡多样的计算需求，构建可扩展的高性能计算系统，
浪潮HPC系统平台优化 内存约束型 网络密集型 计算密集型 I/O密集型 HPC应用需求按硬 件主要组成划分： CPU 内存 存储 互联 通过对特定平台上应用特征的分析，我们可以把应用划分为不同的类型，如：计算密集型、内存约束型，它又分为…、IO密集型、以及网络密集型，如… 不同行业的应用对计算资源的需求特点是完全不同的，在这方面浪潮做了大量的工作，在下午的报告中，我们会按不同的行业划分，分别对一些典型的应用做详细的描述。 平衡多样的计算需求，构建可扩展的高性能计算系统， 最大化发挥现有海量应用的性能。

75 浪潮HPC系统平台优化 计算密集型应用优化思路 应用优化 软件平 台优化 硬件平 台优化 输入参数：精度、收敛条件、边界条件
代码优化：数组向量化，循环、函数优化 模型理论：如赝势、DFT、QMC、CI 应用优化 OS：Linux、精简内核、向量化支持 编译器: ifort/icpc O2/O3 SSE AVX … 数学库: MKL、IMSL、Goto… 软件平 台优化 CPU：提升频率 HT： 关 硬件平 台优化

76 浪潮HPC系统平台优化 I/O密集型应用优化思路 阵列性能：硬盘、RAID、控制器、整机性能、多路径模式 硬件平 台优化
网络性能：存储网络、数据网络 硬件平 台优化 软件平 台优化 应用优化 文件系统参数：依应用调整参数 协议转换：Samba协议转换 作业调度：合理分配处理器与IO资源 输入参数：与文件系统相匹配的数据块 代码优化：与文件系统匹配的并行IO模型

77 浪潮HPC系统优化---示例 某研究所CFD自研代码， 要求在固定硬件平台下， 进行应用运行性能优化。 测试软件环境： 测试硬件环境：
CFD自研代码，27M cells Intel composer xe 2012 测试硬件环境： 1个管理结点、1 个IO 结点，8 个刀片计算节点 Inifiband计算网络

78 浪潮HPC系统优化---示例 Idle Sleeping 问题定位及分析 分析： CPU的sy,与id项说明CPU没有得到充分的应用。
图：系统负载、进程运行状态截图 Sleeping Idle 分析： CPU的sy,与id项说明CPU没有得到充分的应用。 应用程序出现了多个进程处于sleep状态。 程序处于sleep状态，一般是由于进程运行步调不一致，部分进程出现等待其它进程的数据的情况。 图：CPU运行状态监控图

79 浪潮HPC系统优化---示例 问题定位及分析 App运行时间 MPI_Waitall时间
分析：由MPI函数运行时间看出MPI_Waitall平均占了22.5%的wall time.

80 浪潮HPC系统优化---示例 优化对比 优化选项 优化参数 性能提升 优化前 优化后 OS版本 RHEL 5.* RHEL 6.* 12%
Openmpi版本 1.4.3 1.5.4 3% OpenMPI参数 不使用paffinity、maffinity等参数 使用paffinity、maffinity等参数 18% Compiler Gnu Intel 2% OFED 1.5.2/1.5.1 1.5.3 基本没差别 数学库 Liblapack、libblas MKL库中的Liblapack、libblas

81 浪潮HPC系统优化---示例 优化对比 CPU: 调优前 调优后 User% 81.5% 89.1% Sys% 18.1% 8.5%
Wait% 0.0 1.7 Idle% 0.4 0.7 CPU% 99.6 97.6

82 浪潮HPC系统优化---示例 优化对比 调优前 调优后 Wavg Disk Read MB/s 0.628 136.861
Wavg Disk Write MB/s 74.554 WAvg. IO/sec 53 646

83 浪潮HPC系统优化---示例 优化结果 应用经过系统优化后，性能得到了明显提升，加速比也较优化前有了近似线性的表现。
仅仅依靠平台优化所能实现的性能提升比较有限。那么还有没有其他的办法？这就是浪潮策略的第二部分，充分利用和跟上技术的发展和架构的创新。

84 浪潮HPC模型与算法革新 LDA\GGA… QMD 应用程序使用的是几十年前的算法 Thomas-Fermi Kohn-Sham PAW 1950 1960 1970 1980 1990 2000 2010 DFT Car-Parrrinello HF 并行方式 band basis K point Spin 并行度 ~100 2 我们先来看一个时间轴... … 那么我们应该如何实现模型和算法的创新呢？ 模型算法创新是突破性能的关键

85 浪潮HPC模型与算法革新 理论模型 物理模型 数学算法 分子动力学 …… …… 系统/中间件平台 硬件平台 密度泛函 有限元 线性方程
FFT …… 程序代码 并行模式 算法参数 收敛条件 …… 系统/中间件平台 硬件平台

86 例B. 浪潮HPC模型与算法革新---示例 中科院某研究所新型量子材料研究 自研代码(973项目)优化 研究背景： 物理模型、算法分析：
该课题研究了半导体量子点中少电子的自旋轨道耦合性质，通过控制自旋轨道耦合强度的外加电场，来调控电子的自旋态，以实现自旋电子学器件，对电子信息产业发展意义重大 物理模型、算法分析： 使用全Configuration Interaction (CI) 方法计算少电子态，其中对哈密顿量的对角化采用QR算法 优化前性能表现： 内存占用量极大,最大矩阵规模~10^4,并行度差~10核，所能研究体系~3个电子态

87 浪潮HPC模型与算法革新---示例 优化分析 (理论入手并指导实现) 使用部分CI方法(大幅减少弱相关 性计算)
使用Iteration方法(提高并行度) Fortran代码实现，相对C/C++有 ~10%左右性能提升 使用大量列矢量，适合AVX指令向 量化加速，向量化率99% 优化集合通信 (理论入手并指导实现)

88 浪潮HPC模型与算法革新---示例 优化结果 优化后的程序可以用来研究多电子自旋相互作用，也可以用来研究拓扑绝缘体的边缘态，意义重大！
最大矩阵规模~10^8 并行度~200核 研究体系~10个电子态 N=7 优化前 最大矩阵规模~10^4 并行度~10核 研究体系~3个电子态 N=2 优化后的程序可以用来研究多电子自旋相互作用，也可以用来研究拓扑绝缘体的边缘态，意义重大！

89 CPU Memory Network I/O Main index Explanation Monitoring tools
Computing time Application Time ITAC，TAU,teye Load average CPU Load，To determine whether the need for more resources TOP，ganglia,teye CPU sys% The CPU usage in the system the proportion of the kernel TOP，PAPI，TAU ,teye L3 Cache Miss% the higher L3cache miss rate ,the poorer data prefetch effect PAPI，Vtune,teye CPI Clock cycle Per Instruction，The higher CPI The larger optimization space Vtune,teye Memory Mem capacity the memory capacity be consumed during application running free，NMON，Ganglia,teye Mem bandwidth the memory bandwidth be used during application running Stream,teye SWAP Swap NMON，Ganglia,teye NUMA Ratio Program remote memory access proportion Vtune Network Communication Time% MPI Time%，The proportion of MPI Communications ITAC，TAU MPI Wait Time% MPI communication in the process of waiting time ratio Network In Nmon，Ganglia，ethtools,teye Network Out Latency The transmission latency between nodes during the application running OSU，IMB Bandwidth The network bandwidth between nodes during the application running OSU，Iperf I/O Disk IO% Procedures for the treatment of IO time total time ratio Nmon，Ganglia，sar，iostat,teye IO bandwidth File system IO bandwidth size IOzone，Iometer,teye Data size The output results datasize du Particle size In the operation of each stored data size Nmon，Ganglia Frequency Operation data storage number 不用指标数据能够反映应用的性能特征，所以监控性能指标非常关键 Different index data can reflect the application of performance characteristics, so monitoring the performance index is the very important

90 Some science research software application
Mode Basis sets Parallelization Diagonalization Plane Atom band basis K point Spin CG PC-CG DAV RMM CP VASP √ Abinit PWSCF Siesta Castep CPMD Gaussian OK, take a look at this table, in which we list some application’s theorical method. Please look at the VASP. Form this table we know it relay on the planewave method. This method would lead to a very serious memory bandwidth sensitive.

91 Characteristic Features---Gaussian
Test Information TS850 NF 5280M3 Hardware： CPU Intel(R) Xeon(R) CPU Intel(R) Xeon(R) CPU Memory 64*8 G, Samsung DDR3 1333Mhz 8*8 G, Samsung DDR3 1333Mhz Disk 3* SAS 600 G Raid 0 7* SAS 300 G Raid 0 Network Ethernet InfiniBand 5.6Gb/s Software： Operating System： RedHat Enterprise Linux 6.1 x86_64 RedHat Enterprise Linux 6.3 x86_64 Software Version： Gaussian 09 Now, take the Gaussian application as a example. Gaussian is a very famous software package in quantum chemistry. Here we use a very small workload to see what would happen on the E NF5280M3 and E TS850 sandybridge platform.

92 Gaussian examples Animating Optimizations and Reaction Paths
ChemDraw Gaussian examples Animating Optimizations and Reaction Paths Steps from a geometry optimization of benzene This sequence displays a series structures from an Intrinsic Reaction Path (IRC) calculation of the 1,2 hydrogen shift reaction in which formaldehyde transforms into trans hydroxy carbene

93 Speedup and Network comparison
The chart shows the comparison of Gaussian example’s running time on the TS850 and NF5280M3 platform Dark grey represents the case of TS850, while the light grey represents the case of NF5280M3, Results show that TS850 platform can exhibit good performance characteristics for Gaussian platform The speedup is better on the sandybridge platform. In the node, the speedup takes the better state. Between the nodes, the speedup for the TS850 shows better state. 1×NF5280M3（ Use OpenMP to run the Gaussian，using 16 CPU for each node ） 2×NF5280M3（Use Linda to run the Gaussian，using 8 CPU for each node） Operation mode Run times Open-MP Seconds Linda ( IB） Seconds

94 Run characteristics on E5-2670 Platform
CPU：Higher CPU coefficient of utilization, nearly 100%; Gflops: Maximum peak is 160Gflops, High requirement on the CPU frequency; Memory: little memory bandwidth 15Gb/s higher performance Disk IO：High requirement high data to storage and communicate, only at the initial and the final of program running need the data to read the files; The summary of the characteristics of Gaussian are all listed in this picture. The CPU, Gflops, Memory, Disk information can be seen in this picture.

95 The Gaussian characteristic summary
Computationally intensive：Higher CPU frequency higher performance Storage IO: High requirement Need high disk space to storage data Network: High requirement high data to storage and communicate Memory band-width sensitive：little memory bandwidth higher performance

96 诚信﹒尊重﹒追求卓越