《并行计算：Parallel Computing》 结构编程算法应用 §3.2并行程序设计基础与样例 (第二部分，续) 徐悦牲Yueshen Xu)) ysxu@xidian.edu.cn 软件工程系 西安电子科技大学
§3.2 并行程序设计基础与样例 （第二部分，续） 徐悦甡(Yueshen Xu) ysxu@xidian.edu.cn 软件工程系 西安电子科技大学 《并行计算：Parallel Computing》 结构 编程 算法 应用
上节内容回顾 历些子种枝大” XIDIAN UNIVERSITY →并行程序设计模型（计算圆周率的样本程序） 口π的计算 ■π的近似计算公式 1+(0刀 ■ 串行程序→不同程序设计模型下并行程序的编写 >并行程序设计模型（四种） -隐式并行(Implicit Parallel) 数据并行(Data Parallel) 消息传递(Message Passing) 共享变量(Shared Variable)
上节内容回顾 并行程序设计模型（计算圆周率的样本程序） 𝜋的计算 𝜋的近似计算公式 2 𝜋 = න 0 1 4 1 + 𝑥 2 𝑑𝑥 ≈ 0≤𝑖<𝑁 4 1 + 𝑖 + 0.5 𝑁 2 ⋅ 1 𝑁 串行程序 不同程序设计模型下并行程序的编写 ➢ 并行程序设计模型（四种） - 隐式并行（Implicit Parallel） - 数据并行（Data Parallel） - 消息传递（Message Passing） - 共享变量（Shared Variable）
上节内容回顾 历些荒子科枚大学 XIDIAN UNIVERSITY →并行程序设计模型（计算圆周率的样本程序） ■π计算的串行计算程序 #define N 1000000 >其中，N是等分间隔数 int main( N值越大越精确，但计 double local,pi =0.0,w; 算时间越长 long i; w=1.0/N; for (i 0;i<N;i++){ local (i+0.5)*w; pipi +4.0/(1.0+local local); } printf("pi is %f \n",pi *w); return 0; 关键字 3
上节内容回顾 并行程序设计模型（计算圆周率的样本程序） 3 #define N 1000000 int main() { double local, pi = 0.0, w; long i; w=1.0/N; for (i = 0; i<N; i ++) { local = (i + 0.5)*w; pi = pi + 4.0/(1.0+local * local); } printf(“pi is %f \n”, pi *w); return 0; } ➢ 其中，N是等分间隔数 ➢ N值越大越精确，但计 算时间越长 关键字 𝜋计算的串行计算程序
并行程序设计模型 历些毛子种枝大学 XIDIAN UNIVERSITY 计算圆周率的样本程序 口隐式并行(Implicit Parallel) ■内涵 >程序员用熟悉的串行语言编程 >编译器或运行支持系统自动转化为并行代码 ■特点 >语义简单 >可移植性好 >单线程，易于调试和验证正确性 >效率很低
并行程序设计模型 计算圆周率的样本程序 隐式并行（Implicit Parallel） 内涵 ➢ 程序员用熟悉的串行语言编程 ➢ 编译器或运行支持系统自动转化为并行代码 特点 ➢ 语义简单 ➢ 可移植性好 ➢ 单线程，易于调试和验证正确性 ➢ 效率很低 4
并行程序设计模型 历些毛子科枚大多 XIDIAN UNIVERSITY →计算圆周率的样本程序 ▣数据并行(Data Parallel) ■SMD的自然模型，基于局部计算和数据选路操作 ■特点 >单线程、并行操作于聚合数据结构（数组）、松散同步、单一地 址空间、隐式交互作用、显式数据分布 main({ C:pi=sum(temp); 1ongN=1000000 D:printf("pi is %f n",pi*w); double local[N],temp[N],pi,w; long i,j,t; A:W=1/N; B:forall(i=0;i<N;i++) P:local[i]=(i+0.5)*w; Q:temp[i]=4.0/(1.0+local[i]*local[i]); 关键字 5
并行程序设计模型 计算圆周率的样本程序 数据并行（Data Parallel） SIMD的自然模型，基于局部计算和数据选路操作 特点 ➢ 单线程、并行操作于聚合数据结构（数组）、松散同步、单一地 址空间、隐式交互作用、显式数据分布 main(){ long N= 1000000 double local[N], temp[N], pi, w; long i, j, t; A: w=1/N; B: forall(i=0;i<N;i++){ P: local[i]=(i+0.5)*w; Q: temp[i]=4.0/(1.0+local[i]*local[i]); } C: pi=sum(temp); D: printf(“pi is %f\n”,pi*w); } 关键字 5
并行程序设计模型 历安毛子代枚大学 XIDIAN UNIVERSITY 计算圆周率的样本程序 ▣消息传递(Message Passing) ■MPP,COW的自然模型 ■特点 >多线程、异步、多地址空间、显式同步、显式数据映射和负载分 配、显式通信 #define N 1000000 main({ double local,pi,w; long i,processid,numprocess; A:w=1/N; MPI Init(&argc,&argv); 关键字 MPP Massively Parallel Processor;COW,Cluster Of Workstation 6
并行程序设计模型 计算圆周率的样本程序 消息传递（Message Passing） MPP, COW的自然模型 特点 ➢ 多线程、异步、多地址空间、显式同步、显式数据映射和负载分 配、显式通信 6 #define N 1000000 main(){ double local, pi, w; long i, processid, numprocess; A: w=1/N; MPI_Init(&argc, &argv); 关键字 注：MPP, Massively Parallel Processor; COW, Cluster Of Workstation
并行程序设计模型 历忠毛子代枚大学 XIDIAN UNIVERSITY →计算圆周率的样本程序 ▣消息传递(Message Passing,续) //get the current process id MPI Comm rank(MPI COMM WORLD,&processid); //get the number of processes MPI_Comm_size(MPI_COMM_WORLD,numprocess); B:for(i=processid;i<N;i=i+numprocess)M/注意观察processid P:local =(i+0.5)*w; Q:local 4.0/(1.0+local*local); } C:MPI_Reduce(&local,&pi,1,MPI_Double,MPI_SUM,0, MPI COMM WORLD); D:if(processid ==0)printf("pi is %f n",pi*w); 关键字 MPI Finalize(); 7
并行程序设计模型 计算圆周率的样本程序 消息传递（Message Passing，续） //get the current process id MPI_Comm_rank(MPI_COMM_WORLD, &processid); //get the number of processes MPI_Comm_size(MPI_COMM_WORLD, & numprocess); B: for (i=processid; i<N; i= i+numprocess){ //注意观察processid P: local = (i+0.5)*w; Q: local = 4.0/(1.0+local*local); } C: MPI_Reduce(&local, &pi, 1, MPI_Double, MPI_SUM, 0, MPI_COMM_WORLD); D: if(processid == 0) printf(“pi is %f\n”,pi*w); MPI_Finalize(); } 关键字 7
并行程序设计模型 历些毛子代枝大等 XIDIAN UNIVERSITY 计算圆周率的样本程序 口MP归约函数补充 ■函数声明 > int MPI Reduce(void *sendbuf,void *recvbuf,int count, MPI Datatype datatype,MPI Op op,int root,MPI Comm comm) >参数描述 sendbuf:数据发送缓冲区； recvbuf:数据接收缓冲区； count:发送的数据个数； datatype:发送的数据类型； op:执行的归约操作， root:指定根节点； comm:通讯域； #include 6
并行程序设计模型 计算圆周率的样本程序 MPI归约函数补充 函数声明 ➢ int MPI_Reduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm) ➢ 参数描述 - sendbuf ：数据发送缓冲区； - recvbuf ：数据接收缓冲区； - count ：发送的数据个数; - datatype：发送的数据类型; - op：执行的归约操作; - root：指定根节点; - comm：通讯域; 8 #include
并行程序设计模型 历些毛子科枚大》 XIDIAN UNIVERSITY )计算圆周率的样本程序 ▣共享变量(Shared Variable) ■PVP,SMP,DSM的自然模型 注：PVP Parallel Vector Processor; SMP,Symmetric Multi-processor ■特点 DSM,Distributed shared memory 多线程(SPMD,MPMD)、异步、单一地址空间、显式同步、 隐式数据分布、隐式通信 #define N 1000000 main(){ double local,pi 0.0,w; long i; A:w=1.0/N; B:#Pragma Parallel 关键字 #Pragma Shared(pi,w) 9
并行程序设计模型 计算圆周率的样本程序 共享变量（Shared Variable） PVP, SMP, DSM的自然模型 特点 ➢ 多线程（SPMD, MPMD）、异步、单一地址空间、显式同步、 隐式数据分布、隐式通信 #define N 1000000 main() { double local, pi = 0.0, w; long i; A: w=1.0/N; B: #Pragma Parallel #Pragma Shared(pi, w) 关键字 9 注：PVP, Parallel Vector Processor; SMP, Symmetric Multi-processor DSM, Distributed shared memory
并行程序设计模型 历些毛子种枝大等 XIDIAN UNIVERSITY 计算圆周率的样本程序 ▣共享变量(Shared Variable,续) #Pragma Local(i,local) { #Pragma pfor iterator(i=0;N;1) for (i=0;i<N;i++) P:local (i+0.5)*w; Q:local 4.0/(1.0+local*local); } C:#Pragma Critical pi pi local; D:printf("pi is %f n",pi*w); 关键字 }//main 注释 10
并行程序设计模型 计算圆周率的样本程序 共享变量（Shared Variable，续） #Pragma Local(i,local) { #Pragma pfor iterator(i=0;N;1) for (i=0; i<N; i++) P: local = (i+0.5)*w; Q: local = 4.0/(1.0+local*local); } C: #Pragma Critical pi = pi + local; D: printf(“pi is %f\n”,pi*w); } //main 关键字 注释 10