并行计算 :Parallel Computing 结构编程算法应用 3.1 并行程序设计基础与样例 ( 第一部分 ) 徐悦甡 (Yueshen Xu) ysxu@xidian.edu.cn 软件工程系西安电子科技大学
上节回顾 并行计算机性能测评 Amdahl 定律 S = W s + W p W s + W p Τp = f + (1 fሻ f + 1 f p = p 1 + f(p 1 ሻ = 1 (p 1ሻ 1 + f p
上节回顾 并行计算机性能测评 等效率度量标准 T e : 有效计算时间 ( 即串行算法时间 ) T p : 并行计算时间 T e + T o = p T p p: 处理器个数 E: 效率 S = T e T p E = S p = T e T e + T o p = 1 1 + T o T e = = p 1 + T o T e = 1 1 + T o W p 1 + T o W p 1 T e = i=0 p 1 T o = i=0 t e i t o i 如果问题规模 W 保持不变 处理器数 p 增加, 开销 T o 增大 效率 E 下降
本节提纲 并行程序设计语言构造与分类 并行程序样例与引入 并行语言的构造方法 并行语言的分类 并行程序设计通信与编程规范 并行程序设计的一般性问题 并行性问题 进程间的交互问题 并行程序设计的编程规范 计算圆周率程序样本 从编程语言的角度 从编程范式的角度 4
并行程序样例与引入 找出最大值 思考 : 一般的串行程序应该怎么写 程序 语言 + 数据结构 + 算法 载体工具逻辑载体 并行程序设计部分所涉及的内容 5
并行程序设计样例 求最大数 ( 一 ) CPU 0 CPU 1 CPU 2 CPU 3 6
并行程序设计样例 求最大数 ( 二 ) CPU 0 CPU 1 CPU 2 CPU 3 7
并行程序设计样例 求最大数 ( 三 ) CPU 0 CPU 1 CPU 2 CPU 3 8
并行程序设计样例 求最大数 ( 四 ) CPU 0 CPU 1 CPU 2 CPU 3 9
并行程序设计样例 求最大数 ( 五 ) CPU 0 CPU 1 CPU 2 CPU 3 10
并行程序设计样例 求最大数 ( 八 ) CPU 0 CPU 1 CPU 2 CPU 3 11
并行程序设计样例 求最大数 ( 七 ) CPU 0 CPU 1 CPU 2 CPU 3 12
并行程序设计样例 求最大数 ( 九 ) CPU 0 CPU 1 CPU 2 CPU 3 13
并行程序设计样例 求最大数 ( 十 ) CPU 0 CPU 1 CPU 2 CPU 3 14
串 / 并行程序设计过程 串行程序设计过程 应用 问题 设计算法 软件设计 选择语言 工具实现 调试 优化 硬件 大部分情况下透明 15
串 / 并行程序设计过程 并行程序设计过程 ( 传统 ) 应用 数据并行 问题 任务并行 网络并行 并行应用分类 软件设计 共享存储, 消息传递 设计并行算法 选择语言 工具实现调试 优化 并行编程范式 硬件 SMP PVP MPP Cluster DSM 并行计算机体系结构 天河曙光 Nvidia 的 GPU Intel 的多核 CPU 物理机 16
并行语言的构造方法 并行语言的构造方法 串行代码段 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]; 关键字 1 MPI: Message passing interface, 消息传递接口 2 PVM: Parallel Virtual Machine, 并行虚拟机 方法一 : 使用库函数构造并行程序 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 并行程序设计框架 : 提供语法支持与 API 支持 17
并行语言的构造方法 并行语言的构造方法 方法二 : 扩展串行语言 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 名词解释 : 1 Fortran 90: Fortran 在 90 年代的标准 18
并行语言的构造方法 并行语言的构造方法 方法三 : 加编译注释 / 宏构造并行程序 #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 名词解释 1 SGI power C: SGI 公司的并行 C 语言版本 并行程序设计框架 : 提供语法支持与 API 支持 19
并行语言的构造方法 三种并行语言构造方法比较 方法实例优点缺点 库例程 MPI, PVM 易于实现, 不需要新编译器 无编译器检查, 分析和优化 扩展串行语言 Fortran90 允许编译器检查 分析和优化 实现困难, 需要新编译器 编译器注释 SGI powerc 介于库例程和扩展方法之间, 在串行平台上不起作用 名词解释 1 MPI: Message passing interface, 消息传递接口 2 PVM: Parallel Virtual Machine, 并行虚拟机 20
并行语言的分类 两种分类方法 共享存储的模型和语言 Pthread [ 注 ],OpenMP 适用于 PVP, SMP, DSM 从体系结构与存储结构角度分类 消息传递的模型和语言 MPI,PVM 适用于 MPP, Cluster, COW 数据并行的模型和语言 Fortran 90,HPF 适用于 MPP,Cluster 特定应用 注 :Pthread: POSIX threads; HPF: High Performance Fortran 21
并行语言的分类 两种分类方法 ( 第二种 ) 从对于并行性 通信 同步表达的程度分类 可显示地提供对于并行性 通信与同步等的语法支持或接口支持 只部分提供对于并行性 通信与同步等的语法支持或接口支持 我们所讲述的语言与技术均提供语法或接口的全部支持 Python, Java MPI(Message Passing Interface) 22
并行语言的分类 并行语言的评价 并行程序设计的复杂性要求并行语言框架尽可能屏蔽底层实现, 实现 透明, 包括 程序到并行进程或线程的分解 线程到处理器的映射 进程或线程间的通信 进程或线程间的同步 语言体系结构相对独立 能提供一套完整的软件开发方法 有充分的性能保障 为什么会涉及到进程与线程? 进程与线程是并行程序的基本组成单位 23
进程与线程回顾 向并行程序设计过渡 回顾 : 进程 操作系统 程序在计算机上的一次执行活动 系统进行资源分配和调度运行的一个独立单位 使多个程序并发执行, 改善资源利用率提高系统的吞吐量 并行程序设计也会涉及到多线程 24
进程与线程回顾 向并行程序设计过渡 线程 进程的一个实体, 是轻量级的进程 拥有很少的系统资源 : 程序计数器 寄存器和栈 同一进程的各线程共享进程的全部资源 25
并行程序设计的一般性问题 并行语言 并行程序设计 并行程序设计中需要解决的一般性问题 并行性问题 - 针对一个程序 / 进程, 如何实现并行化 - 并行性与数据流的关系, 静态并行性与动态并行性 进程编组 划分与分配等 交互性问题 - 不同的程序 / 进程, 在并行执行过程中, 如何交互 - 多种交互方式 26
并行程序设计的一般性问题 并行性问题 并行性问题 : 并行性与数据流 SIMD(Single Instruction Multiple Data) 所有进程在同一时间执行相同的指令 MIMD(Multiple Instructions Multiple Data) 各个进程在同一时间可以执行不同的指令 上一章是从数据流的角度, 这一章从进程的角度进行解读 27
并行程序设计的一般性问题 并行性问题 MIMD (Multiple Instructions Multiple Data), 两种 SPMD (Single Program Multiple Data) 单程序多数据流 各个进程是同构的, 多个进程对不同的数据执行相同的代码 ( 也叫做数据并行 ) 常对应并行循环, 数据并行结构, 单代码 MPMD(Multiple Programs Multiple Data) 多程序多数据流 各个进程是异构的, 多个进程执行不同的代码 ( 也叫做任务并行, 或功能并行, 或控制并行 ) 常对应并行块, 多代码 28
并行程序设计的一般性问题 并行性问题 // 并行块 parbegin S1 S2 S3.Sn parend // S1 S2 S3.Sn 可以是不同的代码 // 并行循环 : 当并行块中所有进程共享相同代码时 parbegin S1 S2 S3.Sn parend //S1 S2 S3.Sn 是相同代码 简化为 parfor (i=1; i<=n, i++) S(i) 29
并行程序设计的一般性问题 并行性问题 SPMD 程序的构造方法 ( 两种 ) 用单代码方法说明 SPMD // 要说明以下 SPMD 程序 parfor (i=0; i<=n, i++) foo(i) // 用户需写一个以下程序 pid=my_process_id(); numproc=number_of _processes(); parfor (i=pid; i<=n, i=i+numproc) foo(i) // 此程序经编译后生成可执行程序 A, 用 //shell 脚本将它加载到 N 个处理结点上 run A numnodes N 用数据并行程序的方法 // 要说明以下 SPMD 程序 parfor (i=0; i<=n, i++) { C[i]=A[i]+B[i]; } 用户可用一条数据赋值语句 C=A+B 或 forall (i=1,n) C[i]=A[i]+B[i] 关键字注释 30
并行程序设计的一般性问题 并行性问题 MPMD 程序的构造方法 ( 两种 ) 用多代码方法说明 MPMD /* 对不提供并行块或并行循环的语言, 要说明以下 MPMD 程序 */ parbegin S1 S2 S3 parend /* 用户需写 3 个程序, 分别编译生成 3 个可执行程序 S1 S2 S3, 用 shell 脚本将它们加载到 3 个处理结点上 */ run S1 on node1 run S2 on node1 run S3 on node1 /*S1, S2 和 S3 是顺序语言程序加上进行交互的库调用 */ 用 SPMD 伪造 MPMD // 要说明以下 MPMD 程序 parbegin S1 S2 S3 parend // 可以用以下 SPMD 程序 parfor (i=0; i<3, i++) { if (i=0) S1 if (i=1) S2 if (i=2) S3 } /* 因此, 对于可扩展并行机来说, 只要支持 SPMD 就足够了 */ 关键字注释 31
并行程序设计的一般性问题 并行性问题 开发动态并行性的一般方法 Fork/Join 静态并行性 程序的结构以及进程的个数在运行之前 ( 如编译时, 连接时或加载时 ) 就可确定 动态并行性 进程要在运行时创建和终止 静态并行性的例子 parbegin P, Q, R parend 其中 P,Q,R 是静态的 动态并行性的例子 while (C>0) begin fork (foo(c)); C:=boo(C); end 32
并行程序设计的一般性问题 并行性问题 开发动态并行性的一般方法 Fork/Join Process A Process B Process C begin end Z:=1 fork(b); T:=foo(3); begin fork(c); X:=foo(Z); join(c); output(x+y); end begin end Y:=foo(Z); Fork: 派生一个子进程 Join: 强制父进程等待子进程 33
3.1 并行程序设计基础与样例 ( 第二部分 ) http://web.xidian.edu.cn/ysxu/ 结构编程算法应用