中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 十二、并行程序设计基础
十二、并行程序设计基础
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 并行程序设计基础 121并行程序设计概述 122进程 123线程 124同步 125通信 12.6并行程序设计模型 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 2 2021/2/19 并行程序设计基础 ▪ 12.1 并行程序设计概述 ▪ 12.2 进程 ▪ 12.3 线程 ▪ 12.4 同步 ▪ 12.5 通信 ▪ 12.6 并行程序设计模型
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 并行程序设计欐述 并行程序设计难的原因 2并行语言的构造方法 3并行性问题 4交互/通信问题 5五种并行编程风范 6计算圆周率的样本程序 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 3 2021/2/19 并行程序设计概述 1 并行程序设计难的原因 2 并行语言的构造方法 3 并行性问题 4 交互/通信问题 5 五种并行编程风范 6 计算圆周率的样本程序
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 1并行程序设计难的原因 ◇技术先行,缺乏理论指导 ◇程序的语法/语义复杂,需要用户自已处理 >任务/数据的划分/分配 数据交换 同步和互斥 性能平衡 ◇并行语言缺乏代可扩展和异构可扩展,程序移植困难, 重写代码难度太大 ◇环境和工具缺乏较长的生长期,缺乏代可扩展和异构可 扩展 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 4 2021/2/19 1 并行程序设计难的原因 ❖ 技术先行,缺乏理论指导 ❖ 程序的语法/语义复杂, 需要用户自已处理 ➢ 任务/数据的划分/分配 ➢ 数据交换 ➢ 同步和互斥 ➢ 性能平衡 ❖ 并行语言缺乏代可扩展和异构可扩展, 程序移植困难, 重写代码难度太大 ❖ 环境和工具缺乏较长的生长期, 缺乏代可扩展和异构可 扩展
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 2并行语言的构造方法 串行代码段 (c)加编译注释构造并行程序的方法 for(i=0;i<N;++)A[=b[”b[i+1 pragma parallel for(=0;i<N;i++)c]=A]+A[+1] #pragma shared(A, b, c) #pragma local() (a)使用库例程构造并行程序 id=my_process id 0; pragma pfor iterate (i=0; N 1) p=number of _ processes for(=0;iN;}++)A]=b"b[+1]; for(i=id; i<N; i=i+p)A[]=b[]"b[i+1]; pragma synchronize barriero pragma pfor iterate(i=0; N; 1) for(=id;N=计p)A四+A+1:for(=0N+)c=A[+A+1 例子:MPl,PVM, Pthreads 例子: SGI power C (b)扩展串行语言 my_process _id, number- of_processes(, and barriero A(0:N-1)=b(0:N-1)*b(1:N) c=A(O:N-1)+A(1:N) 例子: Fortran90 回家同住能计异十心(口胎
国家高性能计算中心（合肥） 5 2021/2/19 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
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 2并行语言的构造方法 种并行语言构造方法比较 方法 实例 优点 缺点 库例程MP,PVM 易于实现,不需要新编|无编译器检查, 译器 分析和优化 扩展 Fortran90 允许编译器检查、分析实现困难需要新 和优化 编译器 编译器注释 SGI powerC,HPF介于库例程和扩展方法之间,在串行平台 上不起作用 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 6 2021/2/19 方法 实例 优点 缺点 库例程 MPI, PVM 易于实现, 不需要新编 译器 无 编 译 器 检 查 , 分析和优化 扩展 Fortran90 允许编译器检查、分析 和优化 实现困难,需要新 编译器 编译器注释 SGI powerC, HPF 介于库例程和扩展方法之间, 在串行平台 上不起作用. 三种并行语言构造方法比较 2 并行语言的构造方法
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 3并行性问题 3.1进程的同构性 ☆SIMD:所有进程在同一时间执行相同的指令 ☆MMD各个进程在同一时间可以执行不同的指令 SPMD:各个进程是同构的,多个进程对不同的数据执 行相同的代码(一般是数据并行的同义语) 常对应并行循环,数据并行结构,单代码 MPMD各个进程是异构的,多个进程执行不同的代码 般是任务并行,或功能并行,或控制并行的同义语 常对应并行块,多代码 要为有1000个处理器的计算机编写一个完全异构的并行 程序是很困难的 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 7 2021/2/19 3 并行性问题 3.1 进程的同构性 ❖SIMD: 所有进程在同一时间执行相同的指令 ❖MIMD:各个进程在同一时间可以执行不同的指令 ➢SPMD: 各个进程是同构的，多个进程对不同的数据执 行相同的代码(一般是数据并行的同义语) 常对应并行循环，数据并行结构，单代码 ➢MPMD:各个进程是异构的， 多个进程执行不同的代码 （一般是任务并行，或功能并行，或控制并行的同义语） 常对应并行块，多代码 要为有1000个处理器的计算机编写一个完全异构的并行 程序是很困难的
中国料学火计算机科学与波术系 进程的同构性 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 3并行性问题 并行块 parbegin SI S2 S3...Sn parend SIS2 S3 Sn可以是不同的代码 并行循环:当并行块中所有进程共享相同代码时 parbegin S1 S2 S3 Sn parend S1S2S3.n是相同代码 简化为 parfor(i-1; K<=n, i++s(i 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 8 2021/2/19 并行块 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) 进程的同构性 3 并行性问题
中国料学火计算机科学与波术系 进程的同构性 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 3并行性问题 SPMD程序的构造方法 用单代码方法说明SPMD 用数据并行程序的构造方法 要说明以下SPMD程序 要说明以下SPMD程序 arfor (i-0; K<=N, i++)i parfor (F0; K<=N, 1++) foo(O) C[]=A[]+B[i]; 用户需写一个以下程序 pid=my process ido 用户可用一条数据赋值语句 numproc=number of processes; C=A+B parfor (ipid; K<=N, F=i+numproc)foo(i) 或 forall (i-l, N)C[]=A[+Bl] 此程序经编译后生成可执行程序A,用 shell 脚本将它加载到N个处理结点上 run a-numnodes n 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 9 2021/2/19 用单代码方法说明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程序的构造方法 用数据并行程序的构造方法 要说明以下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] 进程的同构性 3 并行性问题
中国料学火计算机科学与波术系 进程的同构性 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 3并行性问题 MPMD程序的构造方法 用多代码方法说明MPMD用SPMD伪造MPMD 对不提供并行块或并行循环的语言要说明以下MPMD程序 要说明以下MPMD程序 parbegin SI S2 S3 parend parbegin SI S2 $3 parend 可以用以下SPMD程序 用户需写3个程序分别编译生成3 parfor(=03,计+) 个可执行程序S1S2S3,用shel|脚 if(F0)SI 本将它们加载到3个处理结点上 if (i1)S2 run si on node 1 if(i-2)S3 run s2 on node 1 run s3 on node 1 因此,对于可扩展并行机来说, S1,82和S3是顺序语言程只要支持SP就足够了 序加上进行交互的库调用 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 10 2021/2/19 用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就足够了 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是顺序语言程 序加上进行交互的库调用. 进程的同构性 3 并行性问题