3.1 并行程序设计基础与样例_软件学院_徐悦甡_第一部分

Size: px

Start display at page:

Download "3.1 并行程序设计基础与样例_软件学院_徐悦甡_第一部分"

堡古
5 years ago
Views:

1 并行计算 :Parallel Computing 结构编程算法应用 3.1 并行程序设计基础与样例 ( 第一部分 ) 徐悦甡 (Yueshen Xu) ysxu@xidian.edu.cn 软件工程系西安电子科技大学

2 上节回顾并行计算机性能测评 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

3 上节回顾并行计算机性能测评等效率度量标准 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 = T o T e = = p 1 + T o T e = 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 本节提纲并行程序设计语言构造与分类并行程序样例与引入并行语言的构造方法并行语言的分类并行程序设计通信与编程规范并行程序设计的一般性问题并行性问题进程间的交互问题并行程序设计的编程规范计算圆周率程序样本从编程语言的角度从编程范式的角度 4

5 并行程序样例与引入找出最大值思考 : 一般的串行程序应该怎么写程序语言 + 数据结构 + 算法载体工具逻辑载体并行程序设计部分所涉及的内容 5

6 并行程序设计样例求最大数 ( 一 ) CPU 0 CPU 1 CPU 2 CPU 3 6

7 并行程序设计样例求最大数 ( 二 ) CPU 0 CPU 1 CPU 2 CPU 3 7

8 并行程序设计样例求最大数 ( 三 ) CPU 0 CPU 1 CPU 2 CPU 3 8

9 并行程序设计样例求最大数 ( 四 ) CPU 0 CPU 1 CPU 2 CPU 3 9

10 并行程序设计样例求最大数 ( 五 ) CPU 0 CPU 1 CPU 2 CPU 3 10

11 并行程序设计样例求最大数 ( 八 ) CPU 0 CPU 1 CPU 2 CPU 3 11

12 并行程序设计样例求最大数 ( 七 ) CPU 0 CPU 1 CPU 2 CPU 3 12

13 并行程序设计样例求最大数 ( 九 ) CPU 0 CPU 1 CPU 2 CPU 3 13

14 并行程序设计样例求最大数 ( 十 ) CPU 0 CPU 1 CPU 2 CPU 3 14

15 串 / 并行程序设计过程串行程序设计过程应用问题设计算法软件设计选择语言工具实现调试优化硬件大部分情况下透明 15

16 串 / 并行程序设计过程并行程序设计过程 ( 传统 ) 应用数据并行问题任务并行网络并行并行应用分类软件设计共享存储, 消息传递设计并行算法选择语言工具实现调试优化并行编程范式硬件 SMP PVP MPP Cluster DSM 并行计算机体系结构天河曙光 Nvidia 的 GPU Intel 的多核 CPU 物理机 16

17 并行语言的构造方法并行语言的构造方法串行代码段 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

18 并行语言的构造方法并行语言的构造方法方法二 : 扩展串行语言 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

19 并行语言的构造方法并行语言的构造方法方法三 : 加编译注释 / 宏构造并行程序 #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

20 并行语言的构造方法三种并行语言构造方法比较方法实例优点缺点库例程 MPI, PVM 易于实现, 不需要新编译器无编译器检查, 分析和优化扩展串行语言 Fortran90 允许编译器检查分析和优化实现困难, 需要新编译器编译器注释 SGI powerc 介于库例程和扩展方法之间, 在串行平台上不起作用名词解释 1 MPI: Message passing interface, 消息传递接口 2 PVM: Parallel Virtual Machine, 并行虚拟机 20

21 并行语言的分类两种分类方法共享存储的模型和语言 Pthread [ 注 ],OpenMP 适用于 PVP, SMP, DSM 从体系结构与存储结构角度分类消息传递的模型和语言 MPI,PVM 适用于 MPP, Cluster, COW 数据并行的模型和语言 Fortran 90,HPF 适用于 MPP,Cluster 特定应用注 :Pthread: POSIX threads; HPF: High Performance Fortran 21

22 并行语言的分类两种分类方法 ( 第二种 ) 从对于并行性通信同步表达的程度分类可显示地提供对于并行性通信与同步等的语法支持或接口支持只部分提供对于并行性通信与同步等的语法支持或接口支持我们所讲述的语言与技术均提供语法或接口的全部支持 Python, Java MPI(Message Passing Interface) 22

23 并行语言的分类并行语言的评价并行程序设计的复杂性要求并行语言框架尽可能屏蔽底层实现, 实现透明, 包括程序到并行进程或线程的分解线程到处理器的映射进程或线程间的通信进程或线程间的同步语言体系结构相对独立能提供一套完整的软件开发方法有充分的性能保障为什么会涉及到进程与线程? 进程与线程是并行程序的基本组成单位 23

24 进程与线程回顾向并行程序设计过渡回顾 : 进程操作系统程序在计算机上的一次执行活动系统进行资源分配和调度运行的一个独立单位使多个程序并发执行, 改善资源利用率提高系统的吞吐量并行程序设计也会涉及到多线程 24

25 进程与线程回顾向并行程序设计过渡线程进程的一个实体, 是轻量级的进程拥有很少的系统资源 : 程序计数器寄存器和栈同一进程的各线程共享进程的全部资源 25

26 并行程序设计的一般性问题并行语言并行程序设计并行程序设计中需要解决的一般性问题并行性问题 - 针对一个程序 / 进程, 如何实现并行化 - 并行性与数据流的关系, 静态并行性与动态并行性进程编组划分与分配等交互性问题 - 不同的程序 / 进程, 在并行执行过程中, 如何交互 - 多种交互方式 26

27 并行程序设计的一般性问题并行性问题并行性问题 : 并行性与数据流 SIMD(Single Instruction Multiple Data) 所有进程在同一时间执行相同的指令 MIMD(Multiple Instructions Multiple Data) 各个进程在同一时间可以执行不同的指令上一章是从数据流的角度, 这一章从进程的角度进行解读 27

28 并行程序设计的一般性问题并行性问题 MIMD (Multiple Instructions Multiple Data), 两种 SPMD (Single Program Multiple Data) 单程序多数据流各个进程是同构的, 多个进程对不同的数据执行相同的代码 ( 也叫做数据并行 ) 常对应并行循环, 数据并行结构, 单代码 MPMD(Multiple Programs Multiple Data) 多程序多数据流各个进程是异构的, 多个进程执行不同的代码 ( 也叫做任务并行, 或功能并行, 或控制并行 ) 常对应并行块, 多代码 28

29 并行程序设计的一般性问题并行性问题 // 并行块 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

30 并行程序设计的一般性问题并行性问题 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

31 并行程序设计的一般性问题并行性问题 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

32 并行程序设计的一般性问题并行性问题开发动态并行性的一般方法 Fork/Join 静态并行性程序的结构以及进程的个数在运行之前 ( 如编译时, 连接时或加载时 ) 就可确定动态并行性进程要在运行时创建和终止静态并行性的例子 parbegin P, Q, R parend 其中 P,Q,R 是静态的动态并行性的例子 while (C>0) begin fork (foo(c)); C:=boo(C); end 32

33 并行程序设计的一般性问题并行性问题开发动态并行性的一般方法 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

34 3.1 并行程序设计基础与样例 ( 第二部分 ) 结构编程算法应用

PowerPoint Presentation

PowerPoint Presentation 并行计算十三并行程序设计基础并行程序设计基础 13.1 并行程序设计概述 13.2 并行程序设计模型并行程序设计难的原因技术先行, 缺乏理论指导程序的语法 / 语义复杂, 需要用户自已处理任务 / 数据的划分 / 分配数据交换同步和互斥并行语言缺乏代可扩展和异构可扩展, 程序移植困难, 重写代码难度太大环境和工具缺乏较长的生长期, 缺乏代可扩展和异构可扩展并行语言的构造方法