并行计算
十三 并行程序设计基础
并行程序设计基础 13.1 并行程序设计概述 13.2 并行程序设计模型
并行程序设计难的原因 技术先行, 缺乏理论指导 程序的语法 / 语义复杂, 需要用户自已处理 任务 / 数据的划分 / 分配 数据交换 同步和互斥 并行语言缺乏代可扩展和异构可扩展, 程序移植困难, 重写代码难度太大 环境和工具缺乏较长的生长期, 缺乏代可扩展和异构可扩展
并行语言的构造方法 串行代码段 for ( i= 0; i<n; i++ ) A[i]=b[i]*b[i+1]; for (i= 0; i<n; i++) c[i]=a[i]+a[i+1]; (a) 使用库例程构造并行程序 id=my_process_id(); p=number_of_processes(); for ( i= id; i<n; i=i+p) A[i]=b[i]*b[i+1]; barrier(); for (i= id; i<n; i=i+p) c[i]=a[i]+a[i+1]; 例子 : MPI,PVM, Pthreads (b) 扩展串行语言 my_process_id,number_of_processes(), and barrier() A(0:N-1)=b(0:N-1)*b(1:N) c=a(0:n-1)+a(1:n) 例子 : Fortran 90 (c) 加编译注释构造并行程序的方法 #pragma parallel #pragma shared(a,b,c) #pragma local(i) { # pragma pfor iterate(i=0;n;1) for (i=0;i<n;i++) A[i]=b[i]*b[i+1]; # pragma synchronize # pragma pfor iterate (i=0; N; 1) for (i=0;i<n;i++)c[i]=a[i]+a[i+1]; } 例子 :SGI power C
并行语言的构造方法 方法实例优点缺点 库例程 MPI, PVM 易于实现, 不需要新编译器 扩展 Fortran90 允许编译器检查 分析 和优化 无编译器检查, 分析和优化实现困难, 需要新编译器 编译器注释 SGI powerc, HPF 介于库例程和扩展方法之间, 在串行平台 上不起作用.
并行层次与代码粒度 并行级别 消息 消息 代码粒度 任务级 任务 i-1 任务 i 任务 i+1 粗粒度 控制级 func1() {... } func2() {... } func3() {... } 中粒度 数据级 a[0]=... b[0]=... a[1]=... b[1]=... a[2]=... b[2]=... 细粒度 指令级 + / 甚细粒度
并行层次 甚细粒度指令级并行 粒度 ( 指令数 ) 几十条, 如多指令发射 内存交叉存取 并行实施 硬件处理器 编程支持 细粒度数据级并行 几百条, 如循环指令块 编译器 共享变量 中粒度控制级并行 几千条, 如过程 函数 程序员 ( 编译器 ) 共享变量 消息传递 粗粒度任务级并行 数万条, 如独立的作业任务 操作系统 消息传递
并行程序开发策略 现有的串行源代码 有目的稍许修改源代码 自动并行化 并行应用程序 (a) 自动并行化 现有的串行源代码 开发并行库 重新链接 并行应用程序 (b) 并行库 现有的串行源代码 作重大修改 编译器支持并行化 并行应用程序 (c) 重新编写并行代码
并行编程风范 相并行 (Phase Parallel) 分治并行 (Divide and Conquer Parallel) 流水线并行 (Pipeline Parallel) 主从并行 (Master-Slave Parallel) 工作池并行 (Work Pool Parallel)
相并行 (Phase Parallel) 一组超级步 ( 相 ) 步内各自计算 步间通信 同步 BSP(4.2.3) 方便查错和性能分析 计算和通信不能重叠 C C... C Synchronous Interaction C C... C Synchronous Interaction
主 - 从并行 (Master-Slave Parallel) 主进程 : 串行 协调任务 子进程 : 计算子任务 划分设计技术 ( 6.1) 与相并行结合 主进程易成为瓶颈 Master Slave Slave Slave
主 - 从式 (Master-Slave) 基本思想是将一个待求解的任务分成一个主任务 ( 主进程 ) 和一些从任务 ( 子进程 ) 主进程负责将任务的分解 派发和收集诸子任务的求解结果并最后汇总得到问题的最终解 诸子进程接收主进程发来的消息 ; 并行进行各自计算 ; 向主进程发回各自的计算结果 分配任务 收集结果 主进程 子进程 1 子进程 2 子进程 i-1 子进程 i
分治并行 (Divide and Conquer Parallel) 父进程把负载分割并指派给子进程 递归 重点在于归并 分治设计技术 (6.2) 难以负载平衡
分治策略 (Divide and Conquer) 其基本思想是将一个大而复杂的问题分解成若干个特性相同的子问题分而治之 若所得的子问题规模仍嫌过大, 则可反复使用分治策略, 直至很容易求解诸子问题为止 问题求解可分为三步 :1 将输入分解成若干个规模近于相等的子问题 ; 2 同时递归地求解诸子问题 ; 3 归并各子问题的解成为原问题的解 分解 归并 归并 分解 原问题 分解过程 归并过程 子问题
流水线并行 (Pipeline Parallel) 一组进程 流水线作业 流水线设计技术 (6.5) P1 P2 P3
数据流水线 (Data Pipelining) 其基本思想是将各计算进程组织成一条流水线, 每个进程执行一个特定的计算任务, 相应于流水线的一个阶段 一个计算任务在功能上划分成一些子任务 ( 进程 ), 这些子任务完成某种特定功能的计算工作, 而且一旦前一个子任务完成, 后继的子任务就可立即开始 在整个计算过程中各进程之间的通信模式非常简单, 仅发生在相邻的阶段之间, 且通信可以完全异步地进行 输入 阶段 1 阶段 2 阶段 i 进程 1 进程 2 进程 i 输出
工作池并行 (Work Pool Parallel) 初始状态 : 一件工作 进程从池中取任务执行 可产生新任务放回池中 直至任务池为空 易于负载平衡 临界区问题 ( 尤其消息传递 ) Work Pool P1 P2 P3
并行程序设计基础 12.1 并行程序设计概述 12.2 并行程序设计模型
并行程序设计模型 隐式并行 (Implicit Parallel) 数据并行模型 (Data Parallel) 消息传递模型 (Message Passing) 共享变量模型 (Shared Variable)
π 的计算 π 1 4 4 dx 0 2 2 1+ x 0 i N i + 0.5 1+ N = 1 N 4 3 2 1 0 1
计算 π 的串行 C 代码 #define N 1000000 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); }
隐式并行 (Implicit Parallel) 概况 : 程序员用熟悉的串行语言编程 编译器或运行支持系统自动转化为并行代码 特点 : 语义简单 可移植性好 单线程, 易于调试和验证正确性 效率很低
数据并行 (Data Parallel) 概况 : SIMD 的自然模型, 也可运行于 SPMD MIMD 机器上 局部计算和数据选路操作 适合于使用规则网络, 模板和多维信号及图像数据集来求解细粒度的应用问题 数据并行操作的同步是在编译时而不是在运行时完成的 特点 : 单线程 并行操作于聚合数据结构 ( 数组 ) 松散同步 全局命名空间 隐式相互作用 隐式 / 半隐式数据分布
计算 π 的数据并行代码 main( ) { long i,j,t,n=100000; double local [N],temp [N],pi,w; A: w=1.0/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 ); } / *main( ) * /
消息传递 (Message Passing) 概况 : MPP, COW 的自然模型, 也可应用于共享变量多机系统, 适合开发大粒度的并行性 广泛使用的标准消息传递库 MPI 和 PVM 特点 : 多线程 异步并行性 分开的地址空间 显式相互作用 显式数据映射和负载分配 常采用 SPMD 形式编码
计算 π 的 MPI 代码 # define N 100000 main ( ){ double local=0.0,pi,w,temp=0.0; long i,taskid,numtask; A: w=1.0/n; MPI_ Init(&argc,& argv); MPI _Comm _rank (MPI_COMM_WORLD,&taskid); MPI _Comm _Size (MPI_COMM_WORLD,&numtask); B: for (i= taskid; i< N; i=i + numtask){ P: temp = (i+0.5)*w; Q: local=4.0/(1.0+temp*temp)+local; } C: MPI_Reduce (&local,&pi,1,mpi_double,mpi_sum,0, MPI_COMM_WORLD); D: if (taskid = =0) printf( pi is %f \ n,pi* w); MPI_Finalize ( ) ; } / * main ( )*/
共享变量 (Shared Variable) 概况 : PVP, SMP, DSM 的自然模型 特点 : 多线程 :SPMD, MPMD 异步 单一共享地址空间 显式同步 隐式 / 隐式数据分布 隐式通信 ( 共享变量的读 / 写 )
计算 π 的共享变量程序代码 # define N 100000 main ( ){ double local,pi=0.0,w; long i ; A : B : C : w=1. 0/N; # Pragma Parallel # Pragma Shared (pi,w) # Pragma Local (i,local) { # Pragma pfor iterate(i=0;n;1) for (i=0;i<n,i++){ P: local = (i+0.5)*w; Q: local=4.0/(1.0+local*local); } # Pragma Critical pi =pi +local ; } D: printf ( pi is %f \ n,pi *w); }/ *main( ) */
三种显式并行程序设计模型主要特性 特性数据并行消息传递共享变量 控制流 ( 线 ) 单线程 多线程 多线程 进程间操作 松散同步 异步 异步 地址空间 单一地址 多地址空间 单地址空间 相互作用 隐式 显式 显式 数据分配 隐式或半隐式 显式 隐式或半隐式
并行编程语言和环境概述 早期机制近代机制并行说明性机制 共享存储分布存储共享存储分布存储逻辑语言函数语言 Semaphores ( 信号灯 ) CCRs ( 条件临界区 ) Monitors ( 管理 ) Sockets ( 套接字 ) RPCs ( 远程过程调用 ) Rendezvous ( 汇合 ) Pthreads Java Threads SHMEM OpenMP HPF ( 虚拟共享 ) Pthreads Ada MPI PVM DCE dist. Java IC-Prolog PARLOG GHCs Multilisp Sisal